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

Пусть требуется решить систему

Метод простой итерации (Метод Якоби) - student2.ru .

Представим Метод простой итерации (Метод Якоби) - student2.ru , где D – диагональная матрица с диагональными членами матрицы A; Метод простой итерации (Метод Якоби) - student2.ru – часть матрицы A, лежащая ниже центральной диагонали, Метод простой итерации (Метод Якоби) - student2.ru – часть матрицы A, лежащая выше центральной диагонали. Тогда

Метод простой итерации (Метод Якоби) - student2.ru ,

или

Метод простой итерации (Метод Якоби) - student2.ru .

Запишем итерационный метод

Метод простой итерации (Метод Якоби) - student2.ru

Разрешим его относительно Метод простой итерации (Метод Якоби) - student2.ru :

Метод простой итерации (Метод Якоби) - student2.ru

Эта форма удобна для реализации метода Якоби. Здесь итерационная матрица

Метод простой итерации (Метод Якоби) - student2.ru .

Матрица расщепления Метод простой итерации (Метод Якоби) - student2.ru . Следовательно, при построении метода Якоби в качестве матрицы ращепления используется диагональ матрицы СЛАУ.

Запишем метод Якоби в координатной форме для Метод простой итерации (Метод Якоби) - student2.ru системы общего вида:

Метод простой итерации (Метод Якоби) - student2.ru

 
  Метод простой итерации (Метод Якоби) - student2.ru

Нетрудно убедиться, что метод Якоби в координатной форме

есть не что иное, как разрешение каждого из уравнений системы относительно одной из компонент вектора. Из первого уравнения системы выражается Метод простой итерации (Метод Якоби) - student2.ru и его значение принимается за значение Метод простой итерации (Метод Якоби) - student2.ru . Из второго уравнения определяется Метод простой итерации (Метод Якоби) - student2.ru и его значение принимается за Метод простой итерации (Метод Якоби) - student2.ru и т. д. Переменные в правой части этих соотношений при этом полагаются равными их значениям на предыдущей итерации.

Рассмотрим пример системы линейных алгебраических уравнений с разреженной (пятидиагональной) матрицей A (рис. 4.1) и оценим эффективность решения такой системы методом Якоби. Будем хранить матрицуA в виде пяти одномерных массивов g, f, a, b, c. Тогда решаемая система в терминах указанных массивов примет вид

Метод простой итерации (Метод Якоби) - student2.ru . Метод простой итерации (Метод Якоби) - student2.ru

В этой записи следует учесть, что отдельные коэффициенты являются нулевыми. В частности Метод простой итерации (Метод Якоби) - student2.ru при i=1; Метод простой итерации (Метод Якоби) - student2.ru при Метод простой итерации (Метод Якоби) - student2.ru ; Метод простой итерации (Метод Якоби) - student2.ru при Метод простой итерации (Метод Якоби) - student2.ru ; Метод простой итерации (Метод Якоби) - student2.ru при Метод простой итерации (Метод Якоби) - student2.ru

Метод простой итерации (Метод Якоби) - student2.ru Метод простой итерации (Метод Якоби) - student2.ru Метод простой итерации (Метод Якоби) - student2.ru

Рис. 4.1. Система с пятидиагональной матрицей

Реализация метода Якоби для такой системы линейных алгебраических уравнений осуществляется просто:

Метод простой итерации (Метод Якоби) - student2.ru

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

Метод простой итерации (Метод Якоби) - student2.ru

Метод Гаусса–Зейделя.

Решаемую систему запишем в виде

Метод простой итерации (Метод Якоби) - student2.ru .

Итерационная схема Гаусса–Зейделя также следует из этого пред-ставления системы:

Метод простой итерации (Метод Якоби) - student2.ru ,

или

Метод простой итерации (Метод Якоби) - student2.ru .

Последняя форма такого итерационного метода удобна для реа-лизации.

Приведем метод Гаусса–Зейделя к стандартному виду:

Метод простой итерации (Метод Якоби) - student2.ru

Стандартная форма метода позволяет выписать его итерационную матрицу и провести над ней очевидные преобразования:

Метод простой итерации (Метод Якоби) - student2.ru .

Матрица расщепления

Метод простой итерации (Метод Якоби) - student2.ru

cодержит всю нижнюю треугольную часть матрицы A.

Запишем метод Гаусса–Зейделя в координатной форме для системы общего вида:

Метод простой итерации (Метод Якоби) - student2.ru

Координатная форма метода Гаусса–Зейделя отличается от координатной формы метода Якоби лишь тем, что первая сумма в правой части итерационной формулы содержит компоненты вектора решения не на k-й, а на (k+1)-й итерации. Но именно это означает, что матрица расщепления метода Гаусса–Зейделя включает не только диагональные члены матрицы A,но и все члены, расположенные ниже главной диагонали.

Оценим, как и ранее, временные затраты метода при решении тестовой задачи - СЛАУ с пятидиагональной матрицей. Реализация метода Гаусса–Зейделя для такой системы:

Метод простой итерации (Метод Якоби) - student2.ru

позволяет констатировать, что временные затраты на итерации метода

Метод простой итерации (Метод Якоби) - student2.ru

оказываются такими же, как и в методе Якоби. Ключ к пониманию более высокой эффективности метода Гаусса–Зейделя - количество итераций, требующееся для получения решения с заданной точностью. Более высокая сходимость к решению в методе Гаусса–Зейделя достигается за счет выбора матрицы расщепления, лучше аппроксимирующей матрицу A.

Наши рекомендации