logo

Решение контрольных по математике!!!

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 вычислений функции.

Метод Ньютона с одномерным поиском надежнее исходного метода Ньютона. Однако его эффективность существенно зависит от того, является ли направление поиска направлением спуска.

 
Яндекс.Метрика
Наверх