§ 7.2. Метод простой итерации

1. Описание метода.

Предположим, что требуется найти решение системы (7.1) с заданной точностью Преобразуем систему (7.1) к следующему эквивалентному виду (к виду, удобному для итераций):

Если ввести вектор-функцию то система (7.5) запишется так:

Пусть начальное приближение задано.

Подставляя его в правую часть системы (7.6), получим Подставляя в правую часть (7.6), найдем и т.д. Продолжая вычисления по формулам

получим последовательность приближений к решению х.

Запись (7.7) означает, что очередное приближение вычисляется через предыдущее приближение следующим образом:

Отметим существенную аналогию с методами простой итерации для решения одного нелинейного уравнения (см. гл. 4) и системы линейных алгебраических уравнений (см. гл. 6).

2. Сходимость метода.

Пусть матрица Якоби, отвечающая вектор-функции (см. § 7.1). Сформулируем теорему о сходимости метода простых итераций, являющуюся аналогом теорем 4.2 и 6.1.

Теорема 7.1. Пусть в некоторой -окрестности решения х функции дифференцируемы и выполнено неравенство

где постоянная.

Тогда независимо от выбора начального приближения из указанной -окрестности корня итерационная последовательность не выходит из этой окрестности, метод сходится со скоростью геометрической прогрессии и справедлива следующая оценка погрешности:

Замечание 1. Условие (7.8), грубо говоря, означает, что в окрестности решения производные для всех должны быть "достаточно малы по модулю". Иными словами, систему (7.1) следует преобразовать к такому виду (7.5), чтобы функции слабо менялись при изменении аргументов, т.е. были "почти постоянными". Каких-либо общих рецептов, как это следует делать, в общем случае нет.

Замечание 2. В условиях теоремы 7.1 верна апостериорная оценка погрешности

которая удобна для формулирования критерия окончания итераций, если известна величина Однако найти значение удовлетворяющее неравенству (7.8) для всех из некоторой -окрестности корня, далеко не просто. В ряде случаев при наличии достаточно хорошего начального приближения можно, считая, что использовать следующий практический критерий окончания итерационного процесса:

Пример 7.3. Используя метод простой итерации, найдем с точностью решение системы (7.4).

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

Здесь Проверим выполнение условия сходимости вблизи точки С. Вычислим матрицу Якоби

Так как и , то для и имеем

Тогда Следовательно, метод простой итерации

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

Возьмем и будем вести итерации по формулам (7.11), используя критерий окончания (7.10), в котором Результаты вычислений с шестью знаками мантиссы приведены в табл. 7.1.

Таблица 7.1 (см. скан)

При критерий окончания выполняется и можно положить

3. Влияние погрешности вычислений.

В силу наличия погрешностей при вычислении на ЭВМ получается не последовательность удовлетворяющая равенству (7.7), а последовательность удовлетворяющая равенству

Будем считать, что абсолютная погрешность вычисляемых значений вектор-функции мала и что Наличие погрешности вычисления приводит к появлению области неопределенности решения х, радиус которой можно приближенно оценить, пользуясь неравенством в том случае, если

Сформулируем следующий результат, являющийся аналогом теорем 4.5 и 6.2.

Теорема 7.2. Пусть выполнены условия теоремы 7.1 и для всех х из -окрестности решения х выполнено неравенство Предположим, также что (т.е. величина достаточно мала). Тогда если вычисления по формулам начинаются с одною начальною приближения принадлежащею -окрестности решения то последовательность не выходит за пределы -окрестности решения х и для всех справедливы оценки

4. Модификации метода простой итерации.

В некоторых случаях для ускорения сходимости полезно использовать следующий аналог метода Зейделя (см. § 6.2):

Более общий вариант метода Зейделя состоит в следующем: -я компонента решения на итерации метода определяется как решение нелинейного уравнения

Преимущества этого подхода состоят в возможности использования методов решения уравнений с одним известным и в отсутствии необходимости приведения системы уравнений к виду, удобному для итераций. Указанный метод сходится, если для матрицы Якоби выполнены условия диагонального преобладания.

Иногда существенный выигрыш дает использование метода, являющегося аналогом метода релаксации (см. § 6.3). В нем после вычисления очередной компоненты приближения по формуле метода Зейделя

приближение вычисляют по формуле