Метод простой итерации нахождения корней нелинейных уравнений

При использовании метода простой итерации для уточнения корня уравнение f(x) = 0 заменяется эквивалентным уравнением

Это означает, что из f{x[1]) — 0 следует х[1] = ф(х[1]) и наоборот. Привести уравнение (1.16) к уравнению (1.17) можно многими способами, например, положив ср(х) = х + ф(х)/Чх), где vy(x) — непрерывная произвольная знакопостоянная функция.

Геометрически на интервале отделения корня уравнение (1.17) представляется в виде двух пересекающихся линий у = ф(х) и у = х (рис. 1.3). Полагая, что известно начальное приближение х(0) для значения корня х*, построим итерационный процесс

Рис. 1.3

изображенный на рис. 1.3 ломаной линией со стрелочками, указывающими направление движения. Для представленного на рис. 1.3 случая взаимного расположения линий у = х и у = ф(х) неограниченное повторение вычислений по соотношению (1.18) позволяет сколь угодно близко подойти к точному значению корня х*.

Исследуем сходимость метода. Если ф (х) имеет непрерывную производную, то из теоремы Лагранжа о конечном приращении

следует, что точка лежит между точками xW и х*. Поэтому если всюду |ф'(дг)| < q < 1, то отрезки )*<*> - ас* | убывают не медленнее геометрической прогрессии со знаменателем q < 1. Действительно, из (1.19), которое можно рассматрггвать как рекуррентное соотношение, следует, что |xw - ас*| = qk jx(0) - ас* | и последовательность х(*> сходится при любом нулевом приближении.

Итак,условие

является достаточным условием сходимости итераций. Если |ф'(х)( > 1, то итерации могут не сходиться. Если |ф'(*)| < 1, но вдали от корня [ ф'(ас) | > 1, то итерации сходятся, если начальное приближение выбрано достаточно близко к корню. При произвольном начальном приближении сходимости может не быть. Таким образом, в методе простой итерации важен выбор начального приближения. Из соотношения (1.19) следует, что если на интервале отделения корня выполняется условие

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

Рис. 1.4

Четыре случая взаимного расположения линий у = х и у = (р(х) вблизи корня и соответствующие им итерационные процессы показаны на рис. 1.4. Рис. 1.4, а и 1.4,6 соответствуют случаю |ф'(*)| <1 — процесс итераций сходится. При этом в первом случае <р'(*) > 0 и сходимость носит односторонний характер (рис. 1.4, а), а во втором ф'(х) < 0 и сходимость носит двусторонний характер (рис. 1.4, б). Рис. 1.4, в и 1.4, г соответствуют случаю |ф'(*)| >1 — процесс итерации расходится, при этом имеет место односторонняя и двусторонняя расходимость.

Подчеркнем, что условие (1.20) сходимости метода итераций является лишь достаточным. При этом все приближения должны попадать в отрезок отделения корня. Выполнение условия (1.20) гарантирует сходимость процесса (1.18), но невыполнение условия (1.20) в общем случае не означает, что итерационный процесс окажется расходящимся. Например, для случая, проиллюстрированного рис. 1.5, условие (1.20) на интервале [х, дг,0)] не выполняется, но метод итераций сходится.

Используя соотношения (1.19) и (1.20), можно записать

Рис. 1.5

где q — max |ф'(х)|, х е [а, Ь]. Из этого соотношения следует, что скорость сходимости метода итерации зависит от величины q: чем меньше q, тем быстрее сходится метод.

Исходное уравнение f(x) = 0 может быть преобразовано к виду х = <р (лг) многими способами, и, очевидно, для метода итерации целесообразно брать то уравнение х = <р(дг), для которого q имеет наименьшее значение.

Для пояснения рассмотрим классический пример вычисления квадратного корня. Исходное уравнение f(x) = х2 - а - 0 (а > 0) преобразуем к виду х = ф(х) тремя способами, приведенными в табл. 1.1 в первом столбце.

Таблица 1.1

<<*х)

ф'(х)

Поведение |<р'(х)|

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

а

X

Q

"ДГ2

|ф'(х)| -* 1 при д: —»± -/а

не сходится

х2 + х - а

I- 1

|ф'(х)|<1 при х е (-1,0), |фЧх)|> 1 при х г (-1,0)

сходится в ограниченном интервале к отрицательному значению корня

(х + а/х) 2

(х - а/х2) 2

|ф'(х)Н0 при х -*±Ja

сходится, и очень быстро

Анализ поведения |ф'(х)| вблизи корня (третий столбец таблицы) показывает, что при удачном выборе представления х = ф(х) можно обеспечить высокую скорость сходимости итерационного процесса без ограничения диапазона параметра а. Третье уравнение х = (х + а/х)/2 используется для вычисления квадратного корня на компьютерах. Таким образом, в методе простой итерации важен выбор вида функций ф(х). Отметим, что метод простой итерации обобщается на случай систем нелинейных уравнений.

  • [1] Дихотомия — от греческого слова 5iXoTop?C) — разделяю на две части.
  • [2] Дихотомия — от греческого слова 5iXoTop?C) — разделяю на две части.
  • [3] Дихотомия — от греческого слова 5iXoTop?C) — разделяю на две части.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >