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

 

Пусть дана линейная система. Введя в рассмотрение матрицы, систему коротко можно записать в виде матричного уравнения. Предполагая, что диагональные коэффициенты 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-норма или норма L1)

или

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

Следствие 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)

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

normе(A)

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

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

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

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

(4)

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

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

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

В матричной форме ее можно записать так:

 

.

 

Рисунок 1.

 

На Рисунке 1 приведен фрагмент рабочего документа Mathcad, содержащий дальнейшее решение этой системы.

 

5. Метод Зейделя

 

Метод Зейделя представляет собой некоторую модификацию метода итераций. Основная его идея заключается в том, что при вычислении (k + 1)-го приближения неизвестной x_i учитываются уже вычисленные ранее (k + 1)-е приближения неизвестных x₁, x₂, …, x_{i - 1}.

Пусть получена эквивалентная система (1). Выберем произвольно начальные приближения корней . Далее, предполагая, чтоk-ые приближения корней известны, согласно Зейделю будем строить (k + 1)-е приближения корней по формулам:

(5)

Заметим, что указанные выше условия сходимости для простой итерации остается верной для итерации по методу Зейделя. Обычно метод Зейделя дает лучшую сходимость, чем метод простой итерации, но приводит к более громоздким вычислениям.

Пример 3. Методом Зейделя решить систему уравнений

Приведем эту систему к виду, удобному для итерации:

В качестве нулевых приближений корней возьмем:

Применяя процесс Зейделя, последовательно получим:

Результаты вычислений с точностью до четырех знаков приведены в Таблице 1.

 

Таблица 1