3. Методы решения систем линейных алгебраических уравнений

- прямые (точные)- методы, которые при отсутствии ошибок округления, за конечное число операций дают точное вычисление.

К ним относятся методы Крамера и Гаусса.^{[1], c272-282}

Описание методов:

1. Метод Гаусса

Наиболее известным и популярным прямым методом решения СЛАУ является метод Гаусса. Этот метод заключается в последовательном исключении неизвестных. Пусть в системе уравнений ^{[2], c.48-50}

первый элемент . Назовем его ведущим элементом первой строки. Поделим все элементы этой строки на и исключим x₁из всех последующих строк, начиная со второй, путем вычитания первой (преобразованной), умноженной на коэффициент приx₁в соответствующей строке.

Получим:

Если то, продолжая аналогичное исключение, приходим к системе уравнений с верхней треугольной матрицей

.

Из нее в обратном порядке находим все значения x_i:

Процесс приведения к системе с треугольной матрицей называется прямым ходом, а нахождения неизвестных –обратным. В случае если один из ведущих элементов равен нулю, изложенный алгоритм метода Гаусса неприменим. Кроме того, если какие–либо ведущие элементы малы, то это приводит к усилению ошибок округления и ухудшению точности счета. Поэтому обычно используется другой вариант метода Гаусса – схема Гаусса с выбором главного элемента. Путем перестановки строк, а также столбцов с соответствующей перенумерацией коэффициентов и неизвестных добиваются выполнения условия:

, j = i+1,i+ 2, …, m

т.е. осуществляется выбор первого главного элемента. Переставляя уравнения так, чтобы в первом уравнении коэффициент a₁₁был максимальным по модулю. Разделив первую строку на главный элемент, как и прежде, исключают x₁из остальных уравнений. Затем для оставшихся столбцов и строк выбирают второй главный элемент и т.д.

Рассмотрим применение метода Гаусса с выбором главного элемента на примере следующей системы уравнений:

В первом уравнении коэффициент при x₁=0, во втором = 1 и в третьем = -2, т.е. максимальный по модулю коэффициент в третьем уравнении. Поэтому переставим третье и первое уравнение.

Исключим x₁ из второго и третьего уравнений с помощью первого. Во втором уравнении исключать не надо. Для исключения из третьего уравнения умножим первое на 0.5 и сложим с третьим:

Рассмотрим второе и третье уравнения. Максимальный по модулю элемент при x₂в третьем. Поэтому поместим его на место второго:

Исключим x₂из третьего уравнения. Для этого умножим второе на -0.5 и сложим с третьим:

Обратный ход: .

Проверка: 0.5*8+0=4, -3+8-0=5, -2*(-3)+0=6.

Такая перестановка уравнений необходима для того, чтобы уменьшить влияние ошибок округления на конечный результат.

3.1.1 Условия применимости метода Гаусса

Выше было показано, что метод Гаусса преобразует исходную систему уравнений^[2]c.51-53

(1)

в эквивалентную систему

, (2)

где С — верхняя треугольная матрица с единицами на главной диагонали.

Выясним теперь, как связаны между собой векторы правых частей f и у. Для этого обратимся к формулам (16), из которых последовательно получим

и вообще

, (3)

где - числовые коэффициенты, причем. Соотношения (3) можно записать в матричном виде

, (4)

где В - нижняя треугольная матрица с элементами ,, () главной диагонали. Напомним, что основное допущение при формулировке метода Гаусса состояло в том, что все. Поэтому на диагонали матрицы В стоят ненулевые элементы, и, следовательно, матрица В имеет обратную.

Подставляя в уравнение (2) выражение для в виде, приходим к уравнению

или, что-то же самое, к уравнению

(5)

Сопоставляя (5) с уравнением (1), приходим к выводу, что в результате применения метода Гаусса получено разложение исходной матрицы А в произведение А = ВС, где В - нижняя треугольная матрица с ненулевыми элементами на главной диагонали и С -верхняя треугольная матрица с единичной главной диагональю. Теперь мы имеем право трактовать метод Гаусса следующим образом. Пусть заданы матрицы А и вектор f. Сначала проводится разложение А в произведение двух треугольных матриц, А = ВС.

Затем последовательно решаются две системы уравнений

(6)

(7)

с треугольными матрицами, откуда и находится искомый вектор х. Разложение А = ВС соответствует прямому ходу метода Гаусса, а решение системы (6) — (7) - обратному ходу. Заметим, что в алгоритме, изложенном выше, разложение А = ВС и решение системы (6) проводится одновременно. Далее, следуя стандартным обозначениям, нижние треугольные матрицы будем обозначать буквой L (от английского lower - нижний) и верхние треугольные — буквой U (от английского upper - верхний).