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

Рассматриваемый метод реализует третий подход к решению задачи. Предварительно исходное уравнение f(х) = 0 преобразуют к виду φ(х)=х, что является частным случа­ем более общей структуры g(х)=f(x).Затем выбирают началь­ное значение х₀ и подставляют его в левую часть уравнения, но φ(x)≠х₀, поскольку x₀ взято произвольно и не является корнем уравнения.

Полученное φ(x)=x₁ рассматривают как очередное приближение к корню. Его снова подставляют в правую часть уравнения φ(х₁) и получают следующее значение х₂ (х₂ = φ(x₁) и т.д., в общем случае х_i+1 =φ(х_i). Получающаяся таким образом последовательность х₀, x₁, х₂, х₃, х₄,… при определенных услови­ях может сходиться к корню х^* (рис. 1.a).

Условие сходимости |φ’(x)| <= 1 на [а,b], причем, чем ближе модуль к нулю, тем выше окажется скорость сходимости к решению. В про­тивном случае последовательность расходится от искомого решения (“метод не сходится”).

На рисунке 2 приведён один из возможных случаев, когда итерационный

процесс не сходится. Видно, что последовательность х₀, x₁, х₂,… удаляется от

корня х^*. Это всегда будет иметь место в том случае, если тангенс угла наклона φ(x) в окрестности корня по модулю больше единицы.

Существуют различные способы преобразования уравнения f(x) = 0 к виду φ(x) = x; одни могут привести к выполнению условия сходимости всегда, другие – в отдельных случаях.

Самый простой способ следующий:

f(x) + x = 0 + x, f(x) + x = φ(x)

(а)	(б)	(в)
а) 0 < φ’(х) < 1;	б) – 1 < φ’(х) < 0
	Pис.6

но он не всегда приводит к успеху. Существует другой способ, в соответствии с которым φ(х)=х-f(х)/к, причем k следует вы­бирать так, чтобы

|k| >Q/2, где Q=mах |f'(х)| и знак к совпадал бы со знаком f'(х) на [а, b].

Погрешность решения можно оценить из соотношения

|x^* - x_i| <= (q/(1 – q))*|X(i) – X(i+1)|, где q = max φ(х), на отрезке [a,b].

Вследствие этого для окончания вычислений в методе итера­ций применят соотношение (q/(q – 1))*|X(i) – X(i + 1)|<= ε, где ε — заданная погрешность решения.

Часто используют упрощенное условие окончания поиска
|X(i) – X(i + 1)|<=ε не вычисляя максимальное значение производной, но в этом случае погрешность решения может не соответствовать заданной (т.е. быть больше или меньше).

4). Метод хорд

В этом методе нелинейная функция f(х) на отделенном ин­тервале [а, b]

заменяется линейной, в качестве которой берется хорда — прямая,

стягивающая концы нелинейной функции. Эта хорда определяется как прямая, проходящая через точки с координатами (а, f(a)) и (b,f(b)). Имея уравнение хорды у = сх + d, можно легко найти точку ее пересечения с горизонтальной осью, подставив в уравнение у = 0 и найдя из него х. Естественно, в по­лученной таким путем точке x1 не будет решения, ее принимают за новую границу

отрезка, где содержится корень. Через эту точку с координатами (x1, f(x1)) и соответствующую границу предыду­щего интервала опять проводят хорду, находят х₂ и т.д. несколько раз, получая последовательностьх3, х4,х5,..., сходящуюся к корню.

Метод хорд применим только для монотонных функций.

Алгоритм метода зависит от свойств функции f(х). Если f(b)*f ”(b) > 0, то строящаяся на каждом этапе хорда имеет правый фиксированный ("закрепленный") конец, и алгоритм выглядит следующим образом:

xi+1=xi-(f(xi)/(f(b)-f(xi)))*(b-xi);

при этом последовательность х1,х2,,…будет приближаться к кор­ню слева.

Если f(а)f"(а) > 0, то строящаяся на каждом этапе хорда име­ет левый фиксированный ("закрепленный") конец, и алгоритм выглядит следующим образом: xi+1 = a +(f(a) / (f(a) – f(xi)))*(xi – a);

Рис.7

при этом последовательность х₁,х₂,… будет приближаться к корню справа.

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

Теоретически доказано, что если первые производные на кон­цах интервала при монотонной и выпуклой функции f(х) не раз­личаются более чем в 2 раза, то справедливо соотношение |х^* - х_i| < |х_i – х_i-1| и условием прекращения пополнения после­довательности может быть |х_i+1 - х_i| <= ε, а в качестве корня принято x_i+1 (можно также окончить процесс и при достижении f(х_i) <= δ, о чем указывалось в концепции методов). На практике указанные условия можно применять и без предварительной про­верки производных, отклонение погрешности результата при по­логих функциях не будет существенным.