Метод простых итераций

Заменим уравнение (5.1) эквивалентным ему уравнением

x = j (x).(5.2)

Естественно, это преобразование можно выполнить неединственным образом. Но функция, стоящая в правой части, должна быть, по крайней мере, определена и дифференцируема на [ a, b ].

Зададим какое-либо начальное приближение к корню х ₀. Дальнейшие приближения будем вычислять по итерационной формуле

x_{k+ 1} = j (x_k), k= 1, 2, ... (5.3)

Очевидно, что если x_k стремятся к некоторому значению x_*, то x_* есть корень уравнения (5.1): . Исследуем, есть ли ограничения на сходимость. Для этого рассмотрим разность (5.3) – (5.2) и разложим j (x_k) в ряд Тейлора в окрестности точки х = х_{* .}:

Если всюду на некотором отрезке [ a,b ]

, (5.4)

то получаемая последовательность { x_k } сходится при любом начальном приближении x ₀Î[ a, b ], так как тогда .

Если , но вдали от корня , то итерации будут сходиться, если начальное приближение выбрано достаточно близко к корню (рис.5.3).

Если , то в силу непрерывности функции будет больше единицы и в некоторой окрестности корня. В этом случае итерации расходятся.

Условие (5.4) называют достаточным условием сходимости метода простых итераций. Очевидно, чем меньше q, тем быстрее сходимость. В качестве оценки для q можно принять наименьшее значение модуля производной при x Î[ a, b ].

Вычислительный процесс следует остановить тогда, когда будет выполнено неравенство

| x_k – x _*| < e, (5.5)

где e – заданная точность. Но это правило не годится для практического применения. Казалось бы, естественное условие – разность двух последовательных приближений должна стать меньше заданной точности | x_{k +1} – x_k | < e –может подвести (рис. 5.4).

Найдем верхнюю оценку левой части неравенства (5.5). Для этого преобразуем разность x_{k+ 1} – x_k двумя способами.

С одной стороны,

С другой стороны,

Следовательно,

.

Если итерационный процесс сходящийся, то выполняется условие (5.4).

0< j ¢(x)<1 -1< j ¢(x)<0 «спираль»

а)

j ¢(x)>1 j ¢(x)<-1

б)

Рис. 5.3 – Графическая интерпретация метода простых итераций:

а) метод простых итераций сходится;

б) метод простых итераций расходится

Рис.5.4 – Хотя | x_{k +1} -x_k | <e, но до корня еще далеко!

Тогда .

Выберем .

Тогда .

Следовательно, итерационный процесс следует продолжать до тех пор, пока для двух последовательных приближений x_{k –1} и x_k не будет обеспечено выполнение неравенства

, (5.6)

где e – заданная предельная абсолютная погрешность корня. В этом случае мы получаем x_* = x_k ± e.

Пример. Построить итерационный процесс для уравнения x ² = 3. Корень находится на отрезке [1,5; 2].

Способ 1. На отрезке [1,5; 2] функция убывающая, следовательно . Процесс расходящийся.

Способ 2. , т.е. можно принять . Следовательно, процесс сходящийся и для обеспечения точности e = 10^–3 необходимо выполнение условия