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

Есть случаи, когда уравнение (4.1) можно заменить эквивалентным ему уравнением

, иначе (4.2)

где .

Выберем некоторое нулевое приближение и вычислим дальнейшие приближения по формулам

, n = 0, 1, 2, … (4.3)

Очевидно, если стремится к некоторому пределу , то этот предел есть корень исходного уравнения.

Исследуем условия сходимости. Если  имеет непрерывную производную, тогда

, (4.4)

где точка  лежит между точками и . Поэтому, если всюду  q < 1, то отрезки убывают не медленнее, чем члены геометрической прогрессии со знаменателем q < 1, и последовательность сходится при любом нулевом приближении (рис. 4.3 а, в). Если |()| >1, то в силу непрерывности и в некоторой окрестности корня выполняется это неравенство; в этом случае итерации не могут сходиться. Если |()| < 1, но вдали от корня | (x)| > 1, то итерации сходятся при условии, что нулевое приближение выбрано достаточно близко к корню; при произвольном нулевом приближении сходимости может не быть.

Очевидно, что чем меньше q, тем быстрее сходимость. Вблизи корня асимптотическая сходимость определяется величиной | ()| и будет особенно быстрой при  () = 0. Значит, успех метода зависит от того, насколько удачно выбрано (x). Например, для извлечения квадратного корня, т.е. решения уравнения х²=а можно положить (x)= или (x) = [x + ] и соответственно написать такие итерационные процессы:

или . (4.5)

Первый процесс вообще не сходится, а второй сходится при любом x₀ > 0 и очень быстро, ибо  ()= 0. Второй процесс используют при извлечении корня на клавишных машинах.

Каков практический критерий сходимости, т. е. когда надо прекращать итерации (4.2)? Из (4.3) видно, что если () < 0, то итерации попеременно оказываются то с одной, то с другой стороны корня (рис 4.3, в, г), так что корень заключен в интервале (х_n, х_n+1). Это надежная, хотя несколько грубая оценка. Но она не применима при  > 0, когда итерации сходятся к корню монотонно (рис 4.3, а, б), т. е. с одной стороны.

Вблизи корня итерации сходятся примерно как геометриче­ская прогрессия со знаменателем q = . Чтобы сумма дальнейших ее членов не превосходила , должен выполняться критерий сходимости:

. (4.6)

y y

q < 1 q > 1

x

x

x

₀ x₁ x₂ x₀ x₁ x₀

а

y

б

q < 1 y q > 1

x ₀ x₂ x ₂ x₁ x x₂ x₂ x₁ x

в г

Рис. 4.3. Графики функции, иллюстрирующие сходимость или расходимость: а, в – процедуры сходятся; б, г – расходятся

При выполнении этого условия итерации можно прекращать.

Метод простых итераций и почти все другие итерационные методы имеют важное достоинство: в них не накапливаются ошибки вычислений. Ошибка вычислений эквивалентна некоторому ухудшению очередного приближения. Но это отразится только на числе итераций, а не на точности окончательного результата. Подобные методы устойчивы даже по отношению к грубым ошибкам (сбоям ЭВМ), если только ошибка не выбра­сывает очередное приближение за пределы области сходимости.