8 Метод Ньютона.

Дана нел.ф-ия действ. переменного f(x) на отрезке [a,b]R. Требуется решить уравнение f(x)=0 (1),т.е. найти значение x^* из отрезка [a,b], , а функция f(x) дважды непрерывно-дифференцируемая в окрестности этого корня. Будем искать решение методом Ньютона. Иначе он наз. методом касательных или методом линеаризации.

Геом. идея метода Ньютона заключается в следующем. Построим график функции f(x), совместив ось абсцисс и отрезок [a,b]. Возьмем некоторую точку и построим касательную к кривой f(x) в точке .Найдем точку пересечения этой касательной с осью 0Х и обозначим ее как . Построим касательную к кривой f(x) в точке . Найдем точку пересечения этой касательной с осью 0Х и обозначим ее как . Продолжаем, пока очередное приближение не станет достаточно близким к корню x^*. Т. о. в этом методе мы участок кривой y=f(x) на отрезке заменяем отрезком касательной, проведенной к кривой на одном из концов отрезка.

функция f(x) дважды непрерывно-дифференцируемая на отрезке [a,b], следовательно, на этом отрезке существуют отличные от 0 1ая и 2ая производные этой функции. Рассмотрим касательную к кривой f(x) в точке, абсцисса которой . За принимаем угол наклона касательной в точке к оси абсцисс и учтем, что . Тогда ур-ие касательной в точке можно записать (2) Запишем ур-ие для пересечения касательной и оси 0Х, т.е. учтем,что в этом случае y=0. Получаем (3).Аналогичные формулы для всех посл. точек, т.е. для произвольной точки с учетом f(x)0 имеем k=0,1,2,… (5)-эта формула выражает метод Ньютона, который получается из ур-ия касательной, проведенной к графику функции f(x) в точке .Метод Ньютона можно рассматривать как частный случай метода простой итерации x=(x), если взять в качестве функции (6). Особенности метода Ньютона.

1.Это одношаговый итерационный метод.

2.Быстро сходящийся метод: имеет квадратичную скорость сходимости, т.е. после каждой итерации число верных знаков удваивается.

3.Сходимость метода односторонняя.

4.Допускает различные модификации.

5.Однако этот метод эффективен при весьма жестких ограничениях на характер функции f(x) внутри отрезка поиска решения: функция должна быть непрерывной, дважды дифференцируемой, первая производная должна быть отличной от нуля.

6.Метод нельзя применять для сеточных функций, т.е. для случая, когда функция задана таблицей, а также при существовании неограниченных вторых производных.

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

8.При неудачном выборе начального приближения метод может не сойтись.

9.Для практической реализации метода используется оценка , однако если на некоторой итерации значение производной резко возрастет, то результат может оказаться неверным.

9.Условие сходимости метода Ньютона

ур-ие касательной в точке можно записать (2) Запишем ур-ие для пересечения касательной и оси 0Х, т.е. учтем,что в этом случае y=0. Получаем (3).Аналогичные формулы для всех посл. точек, т.е. для произвольной точки с учетом f(x)0 имеем k=0,1,2,…(5)-эта формула выражает метод Ньютона, который получается из ур-ия касательной, проведенной к графику функции f(x) в точке .Метод Ньютона можно рассматривать как частный случай метода простой итерации x=(x), если взять в качестве функции (6).Для метода простой итерации условие сходимости соответствует выполнению неравенства вида (7).Для метода Ньютона условие (7) с учетом равенства (6) будет выглядеть следующим образом (8) .

Т .о. надлежащий выбор начального приближения и выполнение условия сходимости (8) делают метод Ньютона сходящимся к значению корня уравнения (1) x*. Начальн приближение нужно выбрать таким образом, чтобы вся последовательность приближений принадлежала интервалу [a,b].

Теорема. Пусть на отрезке [a,b] ур-ие f(x)=0 имеет 1 корень и фу-ия f(x) дважды непрерывно-дифференцируемая в окрестности этого корня. Тогда:1если для всех 1 и 2 производные имеют один знак, т.е.f(x)f(x)>0 (9),то последовательность приближений , определяемая как k=0,1,2,… (10) с будет монотонно убывающей и сходящейся к корню .

2.если для всех 1 и 2 производные имеют разные знаки, т.е.f(x)f(x)<0 (11),то посл-сть приближений , определяемая как (10) с будет монотонно возрастающей и сходящейся к корню.

Если начальное приближение выбрано достаточно близко к корню, то метод Ньютона имеет квадратичную сходимость. Иначе, на нач. итерациях погрешность будет убывать достаточно медленно, но с какого-то момента сходимость будет иметь второй порядок. Для метода Ньютона вблизи корня справедлива оценка погрешности следующего вида (12) погрешность каждой следующей итерации пропорциональна квадрату погрешности на предыдущей итерации. Однако квадратичная погрешность метода касательных гарантируется лишь при близких к корню начальных приближениях. Если же начальное приближение выбрано неудачно, то метод может сходиться медленно, либо не сойдется вообще.