Решение СЛАУ методом итерации.

 

Рассмотрим СЛАУ, записанную в матричной форме

Ax = b,                                                                           (7.1)

где b = (b1, b2,…, bn)T -  вектор свободных членов, x = (x1, x2,…, xn)T - вектор неизвестных. Преобразуем систему (7.1) к виду

x =Bx + c,                                                                        (7.2)

где B и c некоторые новые матрица и вектор соответственно. Систему (7.2) можно трактовать, как задачу о неподвижной точке линейного отображения  B в пространстве Rn. Можно определить последовательность x(k) приближений к неподвижной точке x* рекуррентным равенством:

x(k+1)  =B x(k)  + c,                                                                        (7.3)

Итерационный процесс (7.3), начинающийся с некоторого вектора x(0) = (x1(0), x2(0),…, xn(0))T, называем методом простой итерации (МПИ). Возникают два вопроса:

1) Какие требования нужно предъявлять к B, c и x(0),чтобы последовательность x(k) при k® ¥ имела пределом - неподвижную точку x* задачи (7.2)?

2) С какой скоростью сходится этот процесс? Каков закон убывания абсолютных погрешностей, получаемых по формул (7.3)? Сколько нужно сделать итераций (7.3), чтобы при заданном начальном приближении найти решение задачи с заданной точностью?

На эти вопросы отвечают следующие теоремы.

Теорема 7.1. Для того, чтобы при любом начальном векторе x(0) метод простой итерации (7.3) сходился к решению x* системы (7.2) необходимо и достаточно, чтобы все собственные числа матрицы B были бы по модулю меньше 1.

Теорема 7.2. Пусть ||B|| £ q. Тогда при любом начальном векторе x(0) МПИ (7.3) сходился к единственному решению x* системы (7.2), и при всех kÎN справедливы оценки погрешностей:

 (апостериорная оценка),

(априорная оценка).

Следствие. Если вектор с свободных членов задачи (7.2),то при всех kÎN имеем оценку

.

Рассмотрим МПИ Якоби. Представим матрицу A СЛАУ (3.1) в виде A = L + D +U, где D - диагональная, L - нижняя строго треугольная, U- верхняя строго треугольная матрицы (на диагоналяхх стоят нули). Тогда СЛАУ (7.1) можно записать в виде

Lx + Dx +Ux = b,                                                                       (7.4)

Если на диагонали исходной матрицы нет нулей, то это равносильно равенству

 x = -D -1(L +U)x + D -1b,                                                                (7.5)

и мы приходим к системе вида (7.2), где B = -D -1(L +U), c = D -1b. Тогда уравнение (7.3) МПИ принимает вид

x(k+1)  = -D -1(L +U) x(k)  + D -1b,                                                        (7.6)

В развернутом виде систему (7.5) можно представить в виде:

                                        (7.7)

Итерационный процесс, определяемый (7.6) можно представить в виде:

                                   (7.8)

Говорят, что в матрице А имеет место диагональное преобладание, если справедливы неравенства

.

Имеет место следующий достаточный признак сходимости МПИ (7.6)

Теорема 7.3. Если для матрицы А имеет место диагональное преобладание то метод итерации Якоби сходится.

Теорема 7.4. МПИ Якоби сходится тогда и только тогда, когда все корни уравнения

по модулю меньше 1.

Доказательство. Действительно по теореме 7.1 достаточно показать, что все характеристические корни матрицы B = -D -1(L +U) по модулю меньше 1. Характеристическое уравнение этой матрицы равно det(-D -1(L +U)-lE) = 0. Последнее эквивалентно уравнению det(L +U -lD) = 0, которое совпадает с уравнением, указанным в теореме