Методы решения систем линейных уравнений (стр. 2 из 3)
(20)Относительная погрешность оценивается по формуле:
(21)где
.4. Итерационные методы решения систем линейных уравнений
Рассмотрим систему линейных уравнений, которая плохо решается методами Гаусса. Перепишем систему уравнений в виде:
(22)где
- заданная числовая матрица 
-го порядка, 
- заданный постоянный вектор.4.1 Метод простой итерации Якоби
Этот метод состоит в следующем: выбирается произвольный вектор
(начальное приближение) и строится итерационная последовательность векторов по формуле: 
, 
(23)Приведём теорему, дающую достаточное условие сходимости метода Якоби.
Теорема. Если
, то система уравнений (22) имеет единственное решение 
и итерации (23) сходятся к решению.Легко заметить, что эта теорема является простым обобщением теоремы о сжатых отображениях изученных нами раньше для одношагового итерационного процесса в общем виде. Все оценки, полученные ранее, переносятся и для системы уравнений, разница лишь в понятиях соответствующих норм. Обобщая метод простой итерации Якоби для случая системы уравнений:
(24)Строим алгоритм решения:
а) переписываем уравнение (24) в однородном виде и умножаем на постоянную
- которую далее найдём из условий сходимости итерационного процесса: 
(25)б) добавляем
к обеим частям (25) и получаем: 
(26)в) строим итерационную формулу Якоби:
(27)где постоянную
находим из условий сходимости итерационного процесса (27), который в данном случае имеет вид: 
(28)где
- вектор-функция из (26) или исходя из теоремы о сжатых отображениях 
, где 
- единичная матрица.Рассмотрим числовой пример:
Пусть имеем систему уравнений:
Переписываем систему в виде:
Составляем итерационную формулу:
Коэффициент
выбираем из условий: 
, т.е. 
.4.2 Метод Гаусса-Зейделя
Для решения линейной системы уравнений разработано множество итерационных методов. Тем более, что метод простой итерации Якоби сходится медленно. Одним из таких методов является метод Гаусса-Зейделя.
Для иллюстрации метода рассмотрим числовой пример:
(29)Уравнения переписаны таким образом, что на главной диагонали стоят максимальные для каждого уравнения коэффициенты.
Начинаем с приближения
. Используя первое уравнение, находим для новое значение 
при условии 
. 
(30)Беря это значение
и 
из второго уравнения, находим 
, далее из третьего уравнения находим 
, 
. Эти три величины дают новое приближение и можно повторить цикл с начала, получаем: 
, 
, 
и т.д. Итерации продолжаются до выполнения неравенства 
.Общий алгоритм метода Гаусса-Зейделя имеет вид:
Пусть
(31)где у матрицы
- все диагональные элементы отличны от нуля, т.е. 
(если 
, тогда переставляем строки так, чтобы добиться условия ). Если 
-ое уравнение системы (31) разделить на 
, а затем все неизвестные кроме 
- перенести в правую часть, то мы придём к эквивалентной системе вида:
(32)где
, 
, 
(33)Метод Гаусса-Зейделя состоит в том, что итерации производятся по формуле:
(34)где
- номер итерации, а 
.Замечание: для сходимости метода (34) достаточно выполнения хотя бы одного из условий:
а)
, (35)б)
- симметричная и положительно-определённая матрица.5. Решение системы линейных уравнений методом Ритца
Если
- симметричная и положительно-определённая матрица, то задача решения линейной системы уравнений: (36)эквивалентна задаче нахождения точки минимума функции многих переменных:
(37)где скалярные произведения понимаются в смысле
, т.е. 
(38)Иначе говоря, решение системы линейных уравнений (36) доставляет минимум функции многих переменных:
(39)И наоборот, точка минимума функции (39) является решением системы линейных уравнений (36).
Таким образом, метод Ритца позволяет решение линейной системы уравнений с симметричной и положительно-определённой матрицей свести к задаче нахождения точки минимума функций многих переменных. А эту задачу мы уже умеем решать.
6. Решение системы линейных уравнений с трехдиаганальной матрицей методом прогонки Томаса