Метод применим только для монотонных функций.
Алгоритм метода зависит от свойств функции f(x) .
Если f(b)f’’(b)>0, то строящаяся на каждом этапе хорда имеет правый фиксированный (закрепленный) конец. Для определенности f’’(x)>0 (обратный случай сводится к первому, если записать уравнение –f(x)=0). Тогда кривая y=f(x) будет выпукла вниз, т. е. расположена ниже своей хорды (см. рис.1).
 |
Рис.1
Итак, если f(b)>0, то алгоритм выглядит следующим образом:
Применяя этот прием к тому из отрезков [a, x1] или [x1, b], на концах которого функция f(x) имеет противоположные знаки, получим второе приближение корня x2 и т. д. При этом последовательность x1, x2, будет приближаться к корню слева,
(в качестве x0 можно выбрать начало отрезка точку а).
Если f(a)f’’(a)>0, то строящаяся на каждом этапе хорда имеет левый фиксированный конец и алгоритм выглядит следующим образом:
При этом последовательность x1, x2, будет приближаться к корню справа, в качестве x0 можно выбрать точку b)
Приведем формулу оценки абсолютной погрешности приближенного значения хi , если известны два последовательных значения xi и xi+1.
Теоретически доказано, что если первые производные на концах интервала при монотонной и выпуклой функции f(x) не различаются более, чем в два раза, то справедливо соотношение |x* - xi | < |xi - xi-1| и условием прекращения итераций может быть |xi - xi-1 | £ e, а в качестве корня принято xi+1 (можно также окончить процесс и при достижении f(xi) £e). Таким образом, как только будет обнаружено, что
|xi - xi-1 | £ e,
где e - заданная погрешность, то гарантировано, что |x - xi | £ e.
3. Метод Ньютона
(метод касательных или метод линеаризации).
Одним из лучших общих методов решения уравнения f(x)=0 является метод Ньютона. Если есть некоторое приближение xi к решению x*, то метод Ньютона аппроксимирует функцию f(x) касательной к ее графику в точке xi. Точка пересечения касательной с осью абсцисс принимается за новое приближение. Метод Ньютона часто работает так, как показано на рис. 2 и приближения быстро сходятся к решению.
Рис. 2
Для вывода формул метода Ньютона разложим функцию f(x) в ряд Тейлора
в точке xi:
f(x) =f (xi) + f’(xi)(x - xi ) +…
Касательная задается при помощи первых двух членов ряда
Y = f(xi) + f’(xi)( x- xi )
Полагая y=0, получаем: xi+1 = xi - f(xi)/f’(xi).
В качестве начальной точки в зависимости от свойств функции берется или левая точка х0 =a, (если f(a) f’’(a) > 0),
или правая точка x0=b, (если f(b) f’’(b) > 0)., т.е. итерации сходятся к корню с той стороны, с которой f(x) f’’(x) > 0.
Метод Ньютона хорош тем, что быстро сходится, точнее, имеет квадратичную скорость сходимости.
Однако метод Ньютона не всегда работает так хорошо. Он может и не сходиться, например, если f’(xi)=0, метод не определен.
Если f’(xi)»0, могут возникнуть трудности, так как новое приближение xi+1может оказаться значительно худшим, чем xi.
Еще одним недостатком метода Ньютона является необходимость вычисления f’(x). В ряде случаев можно применять упрощенный алгоритм – вместо вычисления производной в каждой точке f’(xi) использовать значение в начальной точке f’(x0).