14. Метод Ньютона с одномерным поиском
При минимизации произвольной целевой функции 
формулы метода Ньютона (2.3), основанные на аппроксимации функции квадратичной функцией в малой окрестности текущей точки поиска, могут приводить к возрастанию значений функции. Для повышения надежности метода Ньютона и обеспечения убывания значений целевой функции применяется одномерная минимизация функции в направлении поиска 
, найденном по формулам (2.1) или (2.2). На каждой итерации такого модифицированного метода Ньютона из точки 
выполняется одномерный поиск в направлении метода Ньютона 
.
Таким образом, получим формулы метода Ньютона с одномерным поиском:
, 
, . (2.5)
Итерации продолжаются до тех пор, пока выполняется условие
,
Где 
– допустимая погрешность, 
. По формулам (2.5) составим алгоритм метода Ньютона с одномерным поиском.
Алгоритм метода Ньютона с одномерным поиском.
Входные параметры: 
– начальная точка поиска, 
– процедура вычисления функции, – допустимая погрешность.
Выходной параметр – конечная точка поиска.
1. Вычислить 
, 
.
2. Решить СЛАУ 
.
3. Вычислить 
, 
.
4. Положить 
.
5. Если 
, то перейти к шагу 1.
6. Остановиться.
По сравнению с предыдущим алгоритмом в этом алгоритме добавлен шаг 3, на котором выполняется одномерный поиск. Шаг перехода в следующую точку поиска обозначен через . Итерации продолжаются, пока норма больше допустимой погрешности.
Пример 2.3. Для нахождения точки минимума квадратичной функции (1.3) с допустимой погрешностью 10–3 метод Ньютона с одномерным поиском использовал 3 итерации и выполнил 28 вычислений функции. Траектория поиска минимума этим методом такая же, как и на рис. 2.1. На первой итерации найдено приближение точки минимума с погрешностью 4,8∙10–3. На последующих двух итерациях лучшие точки итераций приблизились к точке минимума и достигнутая конечная погрешность составила 7,2∙10–17.
Пример 2.4. На рис. 2.3 представлена траектория поиска минимума функции Розенброка методом Ньютона с одномерным поиском. Для нахождения точки минимума с допустимой погрешностью 10–3 метод затратил 12 итераций и выполнил 260 вычислений функции.
Метод Ньютона с одномерным поиском надежнее исходного метода Ньютона. Однако его эффективность существенно зависит от того, является ли направление поиска направлением спуска.
| < Предыдущая | Следующая > |
|---|
