Смекни!
smekni.com

Численные методы решения систем линейных алгебраических уравнений (стр. 2 из 5)

1.2 Метод Гаусса – прямой и обратный ход

Рассмотрим метод Гаусса. Например, пусть дана расширенная матрица некоторой системы m линейных уравнений c n неизвестными:

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

C2-(a21/a11)*C1,

...

Cm-(am1/a11)*C1,

т.е. Ci-(ai1/a11)*C1, i = 2, 3, ..., m.

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

В результате получим матрицу:

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

Теперь наша задача состоит в том, чтобы получить нули подо всеми диагональными элементами матрицы А – aij, где I = j.

Повторим наши элементарные преобразования, но уже для элемента α22.

C1-(a1222)*C2,

...

Cm-(αm222)*C2,

т.е. Ci-(αi222)*C2, i = 3, ..., m.

Т. е. от каждой строки расширенной матрицы (теперь кроме первой и второй) отнимаем вторую строку, умноженную на частное от деления первого элемента этой (текущей) строки на диагональный элемент α22.

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

Вспомнив, что каждая строка представляет собой одно из уравнений линейной системы уравнений, легко заметить, что последнее m-ое уравнение принимает вид:

γmn*xn = δm.

Отсюда легко можно найти значение первого корня – xn = δmmn.

Подставив это значение в предыдущее m-1-е уравнение, легко получим значение xn-1-ого корня.

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

Пример 1

Рассмотрим систему уравнений:

Главный определитель данной системы:

Δ = [1*(-4)*(-2)+2*2*1+(-1)*(-1)*(-1)]-[1*(-4)*(-1)+2*(-1)*(-2)+2*(-1)*1] = [8+4-1]-[4+4-2] = 11-6 =5,

т. е. Δ ≠ 0.

Т. е. система определена и разрешима. Решим ее по методу Гаусса.

Проведем прямой ход метода Гаусса, выписав предварительно расширенную матрицу системы:

Получим нули под главной диагональю в первом столбце расширенной матрицы. Для получения нуля в элементе a21 (т. е. под диагональю во второй строке матрицы) вторую строку матрицы преобразуем по формуле C2-(a21/a11)*C1 = C2-(2/1)*C1 = C2-2*C1:

Аналогично поступаем и с элементом а31 (т. е. под диагональю в третьей строке матрицы). Третью строку матрицы преобразуем по формуле C3-(a31/a11)*C1 = C3-(-1/1)*C1 = C3+C1:

Таким образом, мы получили нули под главной диагональю в первом столбце расширенной матрицы. Осталось получить нуль под главной диагональю во втором столбце матрицы, т. е. на месте элемента а32. Для этого третью строку матрицы преобразуем по формуле C3-(a32/a22)*C2 = C3-(1/-2)*C2 = C3+1/2C2:

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

Эта матрица эквивалентна системе:

Обратным ходом метода Гаусса найдем корни системы. Из последнего уравнения найдем корень х3:

-5/2x3 = 3/2,

x3 = (3/2):(-5/2) = 3/2*(-2/5) = -3/5.

Корень x3 = -3/5 найден. Подставим его в верхнее (второе) уравнение системы (-2x2-3x3 = 1):

-2x2-3(-3/5) = 1,

-2x2+9/5 = 1,

-2x2 = 1-9/5,

-2x2 = -4/5,

x2 = (-4/5):(-2) = (-4/5)*(-1/2) = 2/5.

Корень x2 = 2/5 найден. Подставим его и корень х3 в верхнее (первое) уравнение системы (x1-x2+x3 = 0):

x1-2/5+(-3/5) = 0,

x1-5/5 = 0,

x1 = 5/5 = 1.

Проверка:

т. е.

т. е.

и т. д [9].

Вывод: Итак, метод Гаусса (или, иначе, метод последовательного исключения неизвестных) состоит в следующем:

1. Путем элементарных преобразований систему уравнений приводят к эквивалентной ей системе с верхнее - треугольной матрицей. Эти действия называют прямым ходом.

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

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

1.3 Итерация для линейных систем

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

Для определенности ограничимся системой из четырех уравнений с четырьмя неизвестными (система четвертого порядка), которую запишем в виде:

Разрешим первое уравнение системы относительно х1:

х1 = (-a12/a112-a13/a11х3-a14/a11х4-a15/a11.

Затем разрешим второе уравнение относительно х2 и т. д. Тогда систему можно переписать в виде:

гдеα = -aik/aii, i = 1, 2, 3, 4; k = 1, 2, 3, 4, 5.

Система является частным случаем записи вида:

При этом линейная функция L1 фактически не зависит от х1.

Зададим какие-либо начальные значения неизвестных (нулевые приближения):

х1(0), х2(0), х3(0), х4(0).

Подставляя эти значения в правые части системы (*), получим первые приближения:

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

Условия сходимости итерационного процесса.

Установим условия, выполнение которых обеспечит сходимость получающихся приближений к истинному (точному) решению системы х1, х2, х3, х4.

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

Это условие можно сформулировать и более точно [20]:

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

1.4 Итерация Якоби

Рассмотрим систему линейных уравнений:

Уравнения можно записать в виде:

Это позволяет предложить следующий итерационный процесс:

или (другой вид записи)

Покажем, что если начать с точки P0 = (х1(0), х2(0), х3(0), х4(0)) = (1, 2, 2), то итерация (3) сходится к решению (2, 4, 3). Подставим х1 = 1, х2 = 2, х2 = 2 в правую часть каждого уравнения из (3), чтобы получить новые значения:

Новая точка P1 = (х1(1), х2(1), х3(1), х4(1)) = (1.75, 3.375, 3), ближе, чем P0.

Итерация, использующая (3), генерирует последовательность точек {Pk}, которая сходится к решению (2, 4, 3):

k х1(k) х2(k) х3(k)
0 1.0 2.0 2.0
1 1.75 3.375 3.0
2 1.84375 3.875 3.025
3 1.9625 3.925 2.9625
4 1.990625 3.9765625 3.0
5 1.99414063 3.9953125 3.0009375
15 1.99999993 3.99999985 3.0009375
19 2.0 4.0 3.0

Этот процесс называется итерацией Якоби и может использоваться для решения определенных типов линейных систем [19].