Метод итерации

Пусть дана линейная система. Введя в рассмотрение матрицы, систему коротко можно записать в виде матричного уравнения. Предполагая, что диагональные коэффициенты a_ij не равны 0 (i = 1, 2, …, n),

разрешим первое уравнение системы относительно х ₁, второе - относительно х ₂и т. д. Тогда получим эквивалентную систему

(1)

где

при i не равно j

и  _ij = 0 при i = j (i, j = 1, 2, …, n).

Введя матрицы

и ,

систему (1) можно записать в матричной форме

x =  +  x,

а любое (k + 1) приближение вычисляется по формуле

x ^(k+1) =  +  x ^(k).

(2)

Напишем формулы приближений в развернутом виде:

(2)

Приведем достаточное условие сходимости метода итераций.

Теорема: Процесс итерации для приведенной линейной системы (1) сходится к единственному ее решению, если какая-нибудь каноническая норма матрицы  меньше единицы, т.е. для итерационного процесса (2) достаточное условие есть

(3)

Следствие 1. Процесс итерации для системы (1) сходится, если:

1) < 1 (m- норма или неопределенная норма)

или

2) < 1 (l- норма или норма L 1)

или

3) < 1 (k- норма или Евклидова норма).

Следствие 2. Для системы процесс итерации сходится, если выполнены неравенства:

или 2.

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

Пример 1. Пусть

Имеем:

max(1+ 2 + 3, 4 + 5 + 6, 7 + 8 + 9) = max (6, 15, 24) = 24;

max(1+ 4 + 7, 2 + 5 + 8, 3 + 6 + 9) = max (12, 15, 18) = 18;

В Mathcad существуют специальные функции для вычисления норм матриц:

normi(A)

Возвращает неопределенную норму матрицы А.

norm1(A)

Возвращает L 1, норму матрицы А.

normе(A)

Возвращает Евклидову норму матрицы А.

В качестве условия окончания итерационного процесса можно взять условие

 - заданная погрешность приближенного решения х  x ^{(k + 1)}.

Пример 2. Решить систему

(4)

методом итераций.

Диагональные коэффициенты 100; 200; 100 системы (4) значительно преобладают над остальными коэффициентами при неизвестных, т.е., выполняется следствие 2.

Приведем эту систему к нормальному виду (1)