Метод итерации
Пусть дана линейная система (13). Введя в рассмотрение матрицы (15), систему (13) коротко можно записать в виде матричного уравнения (14). Предполагая, что диагональные коэффициенты aij не равны 0 (i = 1, 2, …, n),
разрешим первое уравнение системы (13) относительно х1, второе - относительно х2 и т. д. Тогда получим эквивалентную систему
|
(18) |
где
при
i
не равно j
и ij = 0 при i = j (i, j = 1, 2, …, n).
Введя матрицы
и
,
систему (18) можно записать в матричной форме
x = + x,
а любое (k + 1) приближение вычисляется по формуле
x (k+1) = + x (k). |
(19) |
Напишем формулы приближений в развернутом виде:
|
(19' ) |
Приведем достаточное условие сходимости метода итераций.
Теорема: Процесс итерации для приведенной линейной системы (18) сходится к единственному ее решению, если какая-нибудь каноническая норма матрицы меньше единицы, т.е. для итерационного процесса (19) достаточное условие есть
|
(20) |
Следствие 1. Процесс итерации для системы (18) сходится, если:
1)
<
1 (m-норма
или неопределенная норма)
или
2)
<
1 (l-норма
или норма L1)
или
3)
<
1 (k-норма
или Евклидова норма).
Следствие 2. Для системы (13) процесс итерации сходится, если выполнены неравенства:
|
или , |
|
где штрих у знака суммы означает, что при суммировании пропускаются значения i = j, т. е. сходимость имеет место, если модули диагональных элементов матрицы А системы (13) или для каждой строки превышают сумму модулей недиагональных элементов этой строки, или же для каждого столбца превышают сумму модулей недиагональных элементов этого столбца.
Пример 6. Пусть
.
Имеем:
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).
Пример 7. Решить систему
|
(21) |
методом итераций.
Диагональные коэффициенты 100; 200; 100 системы (21) значительно преобладают над остальными коэффициентами при неизвестных, т.е., выполняется следствие 2.
Приведем эту систему к нормальному виду (18)
В матричной форме ее можно записать так:
.
Рисунок 10.
На Рисунке 10 приведен фрагмент рабочего документа Mathcad, содержащий дальнейшее решение этой системы.
Метод Зейделя
Метод Зейделя представляет собой некоторую модификацию метода итераций. Основная его идея заключается в том, что при вычислении (k + 1)-го приближения неизвестной xi учитываются уже вычисленные ранее (k + 1)-е приближения неизвестных x1, x2, …, xi - 1.
Пусть
получена эквивалентная система (18).
Выберем произвольно начальные приближения
корней
.
Далее, предполагая, что k-ые
приближения
корней
известны, согласно Зейделю будем строить
(k
+ 1)-е приближения корней по формулам:
|
(22) |
Заметим, что указанные выше условия сходимости для простой итерации остается верной для итерации по методу Зейделя. Обычно метод Зейделя дает лучшую сходимость, чем метод простой итерации, но приводит к более громоздким вычислениям.
Пример 8. Методом Зейделя решить систему уравнений
Приведем эту систему к виду, удобному для итерации:
В
качестве нулевых приближений корней
возьмем:
Применяя процесс Зейделя, последовательно получим:
Результаты вычислений с точностью до четырех знаков приведены в Таблице 2.
Таблица 2