 |
Метод Гаусса для решения систем линейных алгебраических уравнений
|
|
|
|
Рассмотрим систему линейных алгебраических уравнений
 ,
| (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) значение yi по формуле (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) имеет единственное решение при любой правой части.
|
|
|
