Метод Ньютона – Рафсона.

Метод Ньютона часто используется на завершающем этапе минимизации, когда х* - точка минимума грубо найдена другим, менее трудоемким способом и требуется найти х* с большой точностью. Кроме того, если функция f(х) содержит члены, включающие х в третьей и более высоких степенях, то непосредственное получение аналитического решения уравнения f '(х)=0 может оказаться затруднительным. В таких случаях используются приближенные методы последовательного поиска стационарной точки функции f(х). Ньютон разработал схему, ориентированную на нахождение корня нелинейного уравнения, которая позднее была уточнена Рафсоном.

В рамках схемы Ньютона – Рафсона предполагается, что f(х) – дважды дифференцируемая функция, причем f ''(x)>0 (это гарантирует выпуклость f(х)). Работа алгоритма начинается в точке , которая представляет начальное приближение координаты стационарной точки, или корня уравнения f '(х)=0. В очередной точке (к=0,1,...) строится линейная аппроксимация функции f '(х), и точка, в которой аппроксимирующая линейная функция обращается в нуль, принимается в качестве следующего приближения (рисунок 5.12).

Рис. 5.12. Метод Ньютона – Рафсона (сходимость).

Если точка принята в качестве текущего приближения к стационарной точке, то уравнение касательной к графику f(х) в точке x=имеет вид:

Y=f ()+f '()(x-)

Точка x=+1, найденная из условия y=0, определяется формулой:

+1=-f()/f '()

Полагая f(x)=f '(x), тогда для решения уравнения f '(x) необходимо построить последовательность

-f '()/f ''(), k=0,1,..., (5.11)

Где – точка, выбранная в качестве начального приближения.

В зависимости от выбора начальной точки и вида функции алгоритм может, как сходиться к истинной стационарной точке, так и расходиться, что изображено на рисунке 5.13. Если начальная точка расположена правее , то получаемые в результате последовательных приближений точки удаляются от стационарной точки x*.

)= -3,73, f ''()=17,6, =1,33- (-3,73/17,6)=1,54.

Итерация 3. =1,54, f '()= -0,59, f ''()=12,77, =1,54-(-0,59/12,77)=1,58.

Итерация 4. =1,58, f '()= -0,09, f ''()=12,12, =1,58-(-0,09/12,12)=1,587.

Так как то x*1,587, f*f()12,6.

5.2.4. Метод секущих.

Метод секущих является комбинацией метода Ньютона и общей схемы исключения интервалов. Как уже отмечалось, равенство f '(х)=0 является необходимым и достаточным условия глобального минимума выпуклой дифференцируемой функции f(х). Поэтому, если на концах отрезка [c;d] производная f '(х) имеет разные знаки, то есть f '(c)f '(d)<0, то на интервале (а;b) найдется точка, в которой f '(х) обращается в нуль, и поиск тоски минимума f(х) на [с;d] эквивалентен решению уравнения:

f '(x)=0, xÎ(a,b) (5.12)

Отсюда следует, что при f ' (c)f '(d)<0 любой приближенный метод решения уравнения (5.12) можно рассматривать как метод минимизации выпуклой дифференцируемой функции f(х) на отрезке [c;d].

Предположим, что в процессе поиска стационарной точки функции f(х) на интервале (a;b) обнаружены две точки c и d, в которых знаки производной различны. В этом случае алгоритм метода секущих позволяет аппроксимировать функцию f '(х) секущей прямой и найти точку, в которой секущая графика f '(х) пересекает ось абсцисс (рисунок 5.14). Таким образом, следующее приближение к стационарной точке х* определяется по формуле:

Рис. 5.14. Метод секущих.

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

Пример 5.7. Метод секущих.

Опять рассмотрим задачу из примера 5.6.

Минимизировать f(x) в интервале 1 £ x £ 5.

F '(x) = df(x)/dx = 4x-16/.

Итерация 1.

· Шаг 1. d=5, c=1, f '(d)= -12.

· Шаг 2. Z=5-

· Шаг 3. f '(z)=7,62>0; положить d=2,53.

Итерация 2.

· Шаг 2. z=2,53-

· Шаг 3. f '(z)=3,51>0; положим d=1,94. Итерации продолжаются до тех пор, пока не будет выполняться неравенство .