Методы Оптимизации Систем Автоматизированного Проектирования

Метод Ньютона (метод касательных).

Стратегия поиска.

Одним из самых эффективных и точных методов уточнения корней нелинейного уравнения является метод Ньютона.

Идея метода Ньютона заключается в том, что в окрестности имеющегося приближения задача f(x) =0 заменяется некоторой вспомогательной линейной задачей. Эта задача выбирается так, чтобы погрешность замены имела более высокий порядок малости, чем первый (порядок малости) в окрестности имеющегося приближения. За следующее приближение принимается решение этой вспомогательной задачи. Рассмотрим разложение функции f(x) в ряд Тейлора до членов 1-го порядка включительно в окрестности точки :

Тогда в качестве вспомогательной задачи берется линейная задача:

Ее решение принимается за следующее приближение к решению исходного уравнения, т.е. итерации ведутся по формуле:
.

Таким образом, метод состоит в замене кривой y= f(x) на касательную к ней в процессе каждой итерации. Это видно из уравнения касательной, проведенной в точке
из которого расчетная формула метода Ньютона получается, если положить y=0.

Достаточные условия сходимости определяются теоремой.

Теорема: Пусть f(х) определена и дважды дифференцируема на отрезке [а,b], причем
f(а), f(b)< 0, а производные и сохраняют знак на отрезке [а,b]. Тогда, исходя из начального приближения , удовлетворяющего неравенству , можно построить последовательность
, n=0,1,...
сходящуюся к единственному на отрезке [а,b] решению уравнения .

Для достижения заданной погрешности при использовании метода Ньютона потребуется порядка итераций.

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

Стр.: ..., 2