ВУЗ:
Составители:
48
приближение к значению
∗
x :
∗+
+= hxx
nn 1
. Для минимизации функции
)(
hq вычислим производную )(hq
′
и приравняем ее к нулю, что дает
)(
)(
n
n
xf
xf
h
′′
′
−=
∗
.
Таким образом, алгоритм метода Ньютона описывается итерационной
формулой
)(
)(
1
n
n
nn
xf
xf
xx
′′
′
−=
+
. (3.1)
Условие сходимости итерационного процесса (3.1) можно
сформулировать как следующее утверждение. Пусть 0)(,0)( ≠
′′
=
′
∗∗
xfxf
и )(
∗
′′′
xf непрерывна. Тогда существует окрестность точки
∗
x такая, что
если начальное приближение
0
x принадлежит этой окрестности, то
последовательность значений
n
x , вычисляемых по формуле (3.1), сходится
к
∗
x при ∞→n . Для функций не являющихся унимодальными при
0)( >
′′
n
xf итерации (3.1) сходятся к локальному минимуму, а при
0)( <
′′
n
xf – к локальному максимуму.
Когда метод Ньютона сходится, скорость сходимости квадратична.
Это означает, что если точка
n
x достаточно близка к
∗
x , то
2
1 ∗∗+
−≤− xxCxx
nn
,
где
C – неотрицательная константа, зависящая от вида минимизируемой
функции. Проще говоря, число верных значащих цифр приближения
n
x
удваивается с каждой новой итерацией.
Главный недостаток метода Ньютона заключается в том, что он
требует вычисления производных функции )(
x
f
. В сложных практических
задачах это может оказаться трудным или попросту невозможным. Кроме
того, для сходимости метода начальное приближение
0
x необходимо
выбирать достаточно близко к искомой точке локального минимума. На
практике предварительная оценка положений минимумов может вызвать
затруднения. В этом случае единственная возможность оценки –
вычислить значения функции в некоторой последовательности точек и
выбрать наименьшее значение.
Отметим, что одномерная оптимизация тесно связана с задачей
решения нелинейных уравнений. Так, формула (3.1) получается, если
методом Ньютона решать, уравнение
0)( =
′
xf ,
Страницы
- « первая
- ‹ предыдущая
- …
- 46
- 47
- 48
- 49
- 50
- …
- следующая ›
- последняя »
