1.      Метод Ньютона и его модификация

 

Одним из наиболее простых и быстрых методов решения нелинейных уравнений вида

f(x) = 0                                                                        (4.1)

 

является метод Ньютона или метод касательных, основанный на формуле Тейлора или формуле Лагранжа.  Пусть функция f(x) дважды дифференцируема на отрезке       [a, b], содержащем корень x уравнения (4.1). Пусть xk Î [a, b] известный член последовательности приближений к x, полученный данным методом, начиная с x0. По формуле Тейлора для любой точки x Î[a, b] имеем

                      (4.2)

где точка qk лежит между точками x и xk. Для корня x =x Î[a, b] уравнения (4.1) по этой формуле получаем:

.                          (4.3)

Так как xk близко к x, то разность x - xk по модулю достаточно мала, но тогда величина (x - xk)2 будет еще меньше и ее можно отбросить. Далее полагая qk = xk получим формулу,

,                                                      (4.4)

по которой будем находить следующее приближение xk+1 к корню x

.                                                           (4.5)

Заметим, что xk+1 абсцисса точки пересечения касательной

проведенной к графику функции y = f(x) в точке (xk, f(xk)).

Геометрический смысл метода Ньютона: приближение к корню x уравнения (4.1) совершается по абсциссам точек пересечения касательных к графику функции y = f(x), проводимых в точках соответствующим предыдущим приближениям.

Скорость приближений последовательности (xk) к x следует из следующей теоремы.

Теорема 4.1. Пусть функция f(x) удовлетворяет условиям

.                                         (4.6)

Тогда если члены последовательности (xk), определяемой методом Ньютона принадлежат отрезку [a, b] и эта последовательность сходится на [a, b] к корню x уравнения (4.1), то для любого k Î N справедливы неравенства:

.                               (4.7)

Доказательство. Подставляя в правую часть формулы (4.3) вместо нуля формулу (4.4) получим равенство:

,

,

.

Переходя к модулям, получаем первую формулу (4.7).

По формуле Тейлора имеем

.

Тогда из формулы (4.4) получим . Переходя к модулям, имеем

.                                                       (4.8)

По формуле Лагранжа , где q лежит между точками x и xk. Так как f(x) = 0, то имеем. Отсюда получаем вторую формулу (4.7). 

Начальную точку x0 в методе Ньютона необходимо выбирать исходя из следующей теоремы.

Теорема 4.2. Пусть на отрезке [a, b] функция f(x) имеет первую и вторую производные постоянного знака и пусть f(a) f(b) <0. Тогда если точка x0 выбрана на [a, b] так, что

 f(x0) f (x0) > 0,                                                          (4.9)

то начиная с нее последовательность (xk), определяемая методом Ньютона, монотонно сходится к корню x  Î [a, b] уравнения (4.1).

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

Модификации метода Ньютона. Теоремы 4.1 и 4.2 и формула (4.5) предполагают, что производная функции f(x) внутри отрезка [a, b] не обращается в нуль. Если число x кратный корень уравнения (4.1) то f ' (x) =0. Но итерационный процесс Ньютона сходится, когда x кратный корень уравнения (4.1), но сходимость линейная. Если известен m- показатель кратности корня x, то рекомендуется вести вычисление по формуле:

 .                                                (4.10)

 

Такую модификацию называют методом Ньютона-Шредера.

Для уменьшения затрат, связанных с вычислением производной вычисление можно вести по формуле:

.                                                (4.11)

Такую модификацию называют упрощенным методом Ньютона. Этот метод утрачивает высокую сходимость.

Вместо производной в формуле (4.5) берут ее приближенное значение по формуле

.

Это приводит к так называемому разностному методу Ньютона:

.                                              (4.12)

Параметр hk связывается с номером итерации.

Если взять параметр hk = xk -1 - xk  , то получим формулу

. ,(4.12)

где числа x0 и x1 должны задаваться. Такую модификацию называют двух шаговым методом Ньютона или методом секущих.

Метод секущих обеспечивает за два шага квадратичную сходимость, но худшую сходимость, чем метод Ньютона. Число x1 выбирается близким к числу x0. Окончание счета контролируют малостью модулей невязок |f(xk)|, или поправок | xk -1 - xk |.

Алгоритм нахождения корня методом Ньютона.

Ввод: Функция f(х), производная f'(х), точность вычисления e корня, допуск d - малое число, связанное с реальной точностью вычисления f(х), f'(х). Промежуток [a, b] существования корня.

Вывод: корень с уравнения.

c:=a; если f(c)*f ''(c) < 0, то c:=b; 

1.  d:= c -f(c)/f '(c));

если |c - d| <e, то конец

в противном случае вычислить f(c);

если |f(c)| <d, то конец

идти к шагу 1.

Пример. Методом Ньютона найти корень уравнение x2sin x 1 = 0 (точность 0,01) в интервале (1, p). Имеем  f(х) = x2sin x 1, a = 1, b = p » 3,1416, e = 0,01, d = 0,001. Находим

 f ' (х) = 2xcos x, f '' (х) = 2 – sin x, c = b.

Шаг

1

2

3

4

5

c

3,1416

1,9238

1,5034

1,4141

1,4096

f(c)

8,8700

1,7626

0,2626

0,0121

-

f ' (c)

7,2832

4,1932

2,9396

2,6722

-

Корень уравнения: x = 1,41 ±0,01 .