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

Рассмотрим систему линейных алгебраических уравнений

,

(3.1)

где – вектор неизвестных;

– вектор свободных членов;

, – невырожденная матрица размерами .

В силу невырожденности матрицы для однородной системы уравнений с вектором правых частей имеем единственное тривиальное решение . Для неоднородной системы имеем единственное решение , где – матрица, обратная .

Алгоритм метода исключения неизвестных был изобретен в 3 веке до нашей эры, хотя и носит имя Гаусса. Идея алгоритма состоит в приведении СЛАУ к эквивалентной ей системе с треугольной матрицей (прямой ход исключения), а затем к нахождению неизвестных последовательными подстановками (обратный ход). Данный метод требует числа арифметических операций порядка . Он используется для решения СЛАУ с размерностью .

Объединим матрицу и вектор в расширенную матрицу.

размерами , которая содержит всю известную информацию о системе (3.1).

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

Введем обозначение

.

C матрицей можно обращаться так же, как с исходной системой (3.1), например, осуществлять элементарные преобразования. В качестве последних будем использовать перестановки строк, прибавление к элементам данной строки элементов какой-либо другой строки, умноженных на одно и то же число.

Найдем ненулевой элемент в первом столбце матрицы . Такой элемент найдется всегда ибо, в противном случае, весь первый столбец состоит из нулей и матрица – вырожденная. Пусть , тогда поменяем местами строки номера и . Если , то, естественно, перестановка не требуется. Затем вычтем из каждой строки номера первую строку, умноженную на число , где

.

В результате все элементы -й строки изменят свои значения и станут равными

(3.2)

Здесь мы предполагаем, что хотя перестановка строк и могла состояться, однако нумерация элементов матрицы осталась прежней. Введем обозначения

(3.3)

С учетом введенных обозначений (3.2) и (3.3) матрица преобразуется к матрице и станет равной

.

(3.4)

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

В матрице полученные нули располагаются в столбцах с номерами от до ниже диагонали. Эти нули сохраняются во время следующих шагов алгоритма. В результате применения алгоритма раз система (3.1), в конечном счете, преобразуется в систему вида

,

(3.5)

где – верхняя (правая) треугольная матрица, т.е.

.

(3.6)

Значения неизвестных можно вычислить из (3.6) по формулам

, .

(3.7)

Процесс приведения системы (3.1) к треугольному виду (3.6) называется прямым ходом, а нахождение неизвестных по формулам (3.7) называется обратным ходом.

Произведем подсчет числа арифметических операций в методе Гаусса. Число арифметических операций, необходимое для реализации прямого хода в методе Гаусса для решения систем уравнений порядка , равно

.

(3.8)

При обратном ходе

.

(3.9)

Из формул (3.8) и (3.9) получаем оценку общего числа арифметических действий:

.

Если имеется систем вида (3.1) с одинаковыми матрицами и разными правыми частями ,то целесообразно прямой ход осуществлять для всех систем одновременно, для чего следует вместо одной правой части, задаваемой вектором-столбцом, производить операции над правыми частями (матрицей порядка ). Количество арифметических операций, необходимое для реализации прямого метода Гаусса с учетом (3.8) и (3.9), есть

.

Количество арифметических операций, необходимое для реализации обратных ходов (для систем) методом Гаусса, есть . Откуда следует, что общее количество арифметических операций, необходимое для реализации систем с разными правыми частями, равно

.

Алгоритм LU-разложения

Данный алгоритм можно рассматривать как конкретную форму метода Гаусса. Алгоритм LU-разложения используется не только для решения СЛАУ, но и также для обращения матрицы, т.е. вычисления матрицы, обратной данной.

Пусть и будем искать представление в виде

,

(3.10)

где и – соответственно нижняя и верхняя треугольные матрицы вида

.

Известно, что если все угловые миноры матрицы отличны от нуля, т.е.

то разложение вида (3.10) существует и единственно. Для того чтобы получить расчётные формулы, поступим следующим образом. Обозначим произведение -ой строки матрицы на -й столбец матрицы , причём будем считать вначале, что .

Тогда .

Выразим из последней формулы :

.

(3.11)

Как это принято, будем считать в формуле (3.11) и далее, что сумма вида равна нулю, если значение верхней границы индекса суммирования меньше нижней границы.

В случае имеем

Учитывая, что , и выражая из последнего соотношения , получаем:

.

(3.12)

Наконец, при получаем

откуда, с учетом того, что , приходим к формуле

.

(3.13)

Итак, расчетные формулы (3.11) – (3.13) получены. Для того чтобы при их применении не использовались неизвестные (не вычисленные) величины, необходимо выбрать соответствующий порядок вычисления элементов матриц и .

Например, можно рекомендовать порядок расчета элементов матриц и , схематически изображенный на рис. 3.1. На нем цифры слева для матрицы и сверху – для матрицы означают, что на первом шаге рассчитывается по формуле (3.12), затем вычисляется элемент по формуле (3.11).

Далее (3 шаг) определяются элементы второй строки матрицы в порядке, указанном стрелкой: и (по формулам (3.13) и (3.12) соответственно).

На 4 шаге выполняется расчет элементов 3 столбца матрицы в порядке, обозначенном стрелкой: (формулы (3.11)) и т.д.

Рис. 3.1. Порядок расчета элементов матриц и

 

Рассмотрим теперь применение LU-разложения для решения СЛАУ вида

,

где

.

Введем вспомогательный вектор :

.

(3.14)

Тогда исходную систему можно записать так

.

(3.15)

В силу формул (3.14) и (3.15) решение исходной СЛАУ сводится к последовательному решению систем (3.15) и (3.14) соответственно с верхней и нижней треугольной матрицами.

Метод прогонки

Метод прогонки представляет собой вариант метода Гаусса, примененный к специальным системам линейных алгебраических уравнений и учитывающий ленточную структуру матрицы системы. Пусть имеем СЛАУ со специальной трехдиагональной формой матрицы:

(3.16)

или в матричной форме: , где - вектор неизвестных; – вектор правых частей; – квадратная матрица:

Системы вида (3.16) возникают при конечно-разностной аппроксимации краевых задач математической физики, описываемых обыкновенными дифференциальными уравнениями второго порядка с постоянными и переменными коэффициентами, а также уравнениями в частных производных. Ставится задача разработать экономичные методы решения задач вида (3.16), число арифметических операций для которых пропорционально числу неизвестных. Таким методом для системы (3.16) является метод прогонки. Специфика матрицы состоит в расположении ненулевых элементов, матрица – разреженная матрица, из элементов которой ненулевыми являются не более элементов. Это позволяет получить для решения СЛАУ простые расчетные формулы.

Будем искать решение (3.16) в виде

(3.17)

с неопределенными коэффициентами . Выражение подставим в (3.16):

,

c учетом (3.17) имеем

.

Это равенство имеет место для любых , если

, .

Отсюда получаем рекуррентные формулы для определения :

;	(3.18)
.	(3.19)

Коэффициенты , называются прогоночными.

Если коэффициенты и известны, а также известно , то, двигаясь справа налево (от к ) последовательно определяем все . Задача нахождения по формулам (3.18), (3.19) решается слева направо (от к ). Начальные значения прогоночных коэффициентов можно определить следующим образом. Полагаем в формуле (3.17) , имеем , а из первого уравнения (3.16) , откуда

.

(3.20)

Значение определяется следующим образом. Полагаем в формуле (3.17) , имеем , а из последнего уравнения (3.18) –

,

откуда

.

(3.21)

Расчетные формулы (3.17) – (3.21) можно получить также из (3.16), если применить метод исключения Гаусса. Прямой ход метода заключается в том, что на первом шаге из всех уравнений системы (3.16) при помощи первого уравнения исключается , затем из преобразованных уравнений для при помощи уравнения, соответствующего , исключается и т.д. В результате получим одно уравнение относительно . На этом прямой ход метода прогонки заканчивается. На обратном ходе для находятся .

Порядок счета в методе прогонки следующий:

1) исходя из значений , вычисленных по формулам (3.20), все остальные коэффициенты для определяются последовательно по формулам (3.18) и (3.19);

2) исходя из значения , рассчитанного по формуле (3.21), все остальные неизвестные , определяются последовательно по формуле (3.17).

Изложенный метод поэтому называется правой прогонкой.

Аналогично выводятся формулы левой прогонки:

	(3.22)
	(3.23)
yi+1 = xi+1yi + hi+1, i = N-1, N-2, …, 0; y0 = h0.	(3.24)

Здесь находятся последовательно для значений ; ход вычислений – слева направо.

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

Произведем подсчет числа арифметических действий для метода правой прогонки. Анализ формул (3.17)-(3.21) показывает, что общее число арифметических операций есть . Коэффициенты не зависят от правой части СЛАУ (3.16) и определяются только элементами матрицы . Поэтому, если требуется решить серию задач (3.16) с различными правыми частями, то прогоночные коэффициенты вычисляются только для первой серии. Для каждой последующей серии задач определяются только коэффициенты и решение , причем используются ранее найденные .

На решение первой из серии задач расходуется операций, а на решение каждой следующей задачи – операций. Число арифметических операций, необходимое для решения СЛАУ (3.16) методом левой прогонки и методом встречных прогонок, такое же, т.е. . Метод правой прогонки будем называть корректным, если при .

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

.

(3.25)

Вычитая из (3.25) значение y_i по формуле (3.17), имеем для погрешности с заданным . Отсюда ясно, что если по модулю больше единицы и если достаточно велико, то вычисленное значение будет значительно отличаться от искомого решения . В этом случае говорят, что алгоритм прогонки неустойчив.

Определение. Алгоритм прогонки называется устойчивым, если .

Условия корректности и устойчивости алгоритма правой прогонки определяются следующей теоремой.

Теорема. Пусть коэффициенты системы (3.16) действительны и удовлетворяют условиям:

, , , , , , ;

, ;	(3.26)
, ,	(3.27)

причем хотя бы в одном из неравенств (3.26) и (3.27) выполняется строгое неравенство, т.е. матрица А имеет диагональное преобладание. Тогда для алгоритма (3.17) – (3.21) имеют место неравенства: , , т.е. алгоритм метода правой прогонки корректен и устойчив.

Условия (3.26) и (3.27) теоремы обеспечивают также корректность и устойчивость алгоритмов левой и встречных прогонок. Эти условия сохраняются и для случая системы (3.16) с комплексными коэффициентами .

Легко показать, что при выполнении условий (3.26) – (3.27) теоремы система (3.16) имеет единственное решение при любой правой части.

 

Пример выполнения лабораторной работы №3

Решите систему уравнений методом Гаусса и методом LU -разложения

 

Решите систему уравнений методом прогонки