1.5. Метод секущих
Если итерации хk и xk+1 расположены достаточно близко друг к другу, то производную f'(xk) в алгоритме Ньютона (1.13) можно заменить ее приближенным значением в виде отношения приращения функции f=f(xk)-f(xk-1) приращению аргумента x=xk-xk-1. Таким образом, запишем формулу метода секущих
(1.19)
Геометрический смысл такого изменения алгоритма Ньютона в том, что от аппроксимации функции f(x) касательной мы переходим к секущей (рис. 1.6).
Рис. 1.6. Метод секущих
Для того чтобы начать итерационный процесс, необходимо задать два начальных приближения x0 и x1. Затем каждое новое приближение к корню получаем по формуле (1.19). Заканчиваем процесс уточнения корня при выполнении условия
|xk+1-xk|<
где - заданная абсолютная погрешность определения корня.
Метод секущих несколько уступает методу Ньютона в скорости сходимости, однако, не требует вычисления производной левой части уравнения.
По алгоритму метод секущих близок к методу хорд (п. 1.3), однако в отличие от последнего начальные приближения в методе секущих могут располагаться как с разных сторон от корня, так и с одной стороны; кроме того, при уточнении корня не повторяются знаки функции f(x).
1.6. Метод простых итераций
Исходное уравнение (1.1)
f(x)=0
всегда можно преобразовать к эквивалентному уравнению
х = (х) (1.24)
Пусть известно начальное приближение к корню x0, тогда подставим его в правую часть уравнения (1.24) и получим новое приближение x1 = (х0), затем аналогичным образом получим x2 = (х1) и так далее. Таким образом, итерационное уравнение метода простых итераций имеет вид:
xk+1 = (хk) (1.25)
Необходимо установить, при каких условиях итерационный процесс (1.25) будет сходиться к корню уравнения х*.
Построим графики двух функций:
y1(x)=x
y2(x)=(x)
Координаты пересечения графиков этих функций и дадут корень исходного уравнения (1.24) х*.
а)- односторонний сходящийся процесс |
б)- односторонний расходящийся процесс |
в)- двухсторонний сходящийся процесс |
г)- двухсторонний расходящийся процесс |
Рис. 1.7. Метод простых итераций:
Рассмотрим процесс графически (рис. 1.7). Из графиков видно, что при ’(х)> 0 и при ’(х) < 0 возможны как сходящиеся, так и расходящиеся итерационные процессы. Скорость сходимости зависит от абсолютной величины производной ’(х). Чем меньше |’(х)| вблизи корня, тем быстрее сходится процесс.
Установим теперь критерий сходимости математически. Пусть х* - корень уравнения (1.26), т.е. имеем
х*=( х*)
Пусть kиk+1- отклоненияkиk+1 приближения корня от точного значения корнях*:
хk=х*+k
хk+1=х*+k+1
Если процесс уточнения осуществляется вблизи корня х*, то функцию (х) можно приближенно представить двумя членами ряда Тейлора:
( хk)=( х*+k)=( х*)+’( х*)k
. Тогда итерационная формула (1.25) примет вид
Учитывая, что х* является корнем уравнения: х* = (х*), получим:
или
(1.26)
Для того чтобы итерационный процесс был сходящимся, должно выполняться условие
(1.27)
или
(1.28)
Из (1.26) видно, что максимальная сходимость будет в случае, если .
Переход от уравнения (1.1) к уравнению (1.24) можно осуществить различными способами в зависимости от вида функции f(x) . При таком переходе необходимо построить функцию такую (х), чтобы выполнялось условие сходимости (1.26). Рассмотрим один из общих алгоритмов перехода от уравнения (1.1) к уравнению (1.24). Умножим левую и правую части уравнения (1.1) на произвольную константу b и добавим к обеим частям неизвестное х. При этом корни исходного уравнения не изменятся
x+bf (х) = х +0b (1.27)
Введем обозначение
(х)=x+bf(x) (1.28)
и перейдем от соотношения (1.27) к уравнению (1.24).
Произвольный выбор константы b позволит обеспечить выполнение условия сходимости (1.26). Необходимо выбрать величину b такой, чтобы , тогда сходимость итерационного процесса будет двухсторонней (рис. 1.11, в). В этом случае в наиболее простом виде можно представить критерий окончания итерационного процесса
|xk+1-xk|< (1.29)
где - заданная абсолютная погрешность вычисления корня.
Если функция (х) выбрана в виде (1.28), то производная по х от этой функции будет
’(х) = 1+bf’(х)
Т.е. условие (1.26) имеет вид:
или
Или
Поэтому константу b необходимо выбирать из интервала:
А) если f’(х)>0
-2/f’(х*)<b<0
Б) если f’(х)<0
0<b<-2/f’(х*)
Наибольшую скорость сходимости получим при ’(х*)=0, тогда
b = -1/f’(х*)
и итерационная формула (125) переходит в формулу Ньютона
xk+1 =xk - f(хk)/f’(хk)
Таким образом, метод Ньютона имеет самую высокую скорость сходимости из всех итерационных процессов.