Метод простой итерации Якоби

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)

 

б)  - симметричная и положительно-определённая матрица.