Лекция №6. Описания методов решения СЛАУ

1. 
   Метод Гаусса.
   
2. 
   Метод прогонки.
   

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

Он основан на приведении матрицы системы к треугольному виду. Это достигается последовательным исключением неизвестных из уравнений системы.

Сначала с помощью первого уравнения исключается х₁ из всех последующих уравнений системы. Затем с помощью второго уравнения исключается х₂ из третьего и всех последующих уравнений. Этот процесс, называемый прямым ходом метода Гаусса, продолжается до тех пор, пока в левой части последнего (-го) уравнения не останется лишь один член с неизвестным , т.е. матрица системы будет приведена к треугольному виду.

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



Для исключения из второго уравнения прибавим к нему первое, умноженное на _.



Затем, умножив первое уравнение на и прибавив результат к третьему уравнению, исключим из него .



Общие формулы пересчета коэффициентов при этом выглядят следующим образом:





Т.е. система имеет вид



Теперь из третьего уравнения системы надо исключить . Для этого надо умножить второе уравнение на и прибавить результат к третьему. В результате получится



где и .

Матрица полученной системы имеет треугольный вид.

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

Обратный ход начинается с решения третьего уравнения системы



Используя это значение, можно найти х₂ из второго уравнения, а затем х₁ из первого:



Аналогично строится вычислительный алгоритм для линейной системы с произвольным числом уравнений. При этом расчетные формулы принимают вид:

Прямой ход метода Гаусса

, , где



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

Обратный ход метода Гаусса

; , где .

В этих формулах номер неизвестного, которое определяется из го уравнения; номера уже найденных неизвестных.

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

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

Объем вычислений определяется порядком системы :число арифметических операций примерно равно .

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

Многие прикладные задачи сводятся к системам ЛАУ, имеющих так называемые диагональные матрицы.

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

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



Прямой ход:

Шаг 1: , где , .

Шаг 2: подставим во 2-е уравнение системы

,

,

Выразим :

; ; и т.д.

Шаг :

,

После прямого хода система принимает вид:



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

Шаг 1: Из 2-х последних уравнений выражаем через :





.

Шаг 2: Подставляя в уравнение находим и т.д.