2015-08-21
1110
В отличии от методов прямого поиска градиентные методы поиска используют информацию о производных функции. Это позволяет уменьшить
количество необходимых вычислений значений функции. Эти методы делятся на две группы: методы, использующие информацию только о первых производных, и методы, учитывающие информацию и первых, и вторых производных.
3.1. Метод Коши
Описание алгоритма:
В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.
- градиент функции 
Алгоритм метода выглядит следующим образом:
, где 
- градиент.
Значение 
на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума 
вдоль направления градиента 
. Если в качестве 
взять некоторое положительное число, то получится простейший градиентный алгоритм:
Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие:
Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.
|
|
|
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку х(0) ;
2. Условие окончания поиска. Перейти к шагу 2.
Шаг 2. Вычислить направление поиска в виде антиградиента функции
s(x(k) ) = - ∇f(x(k) );
. Перейти к шагу 3.
Шаг 3. Найти новое приближение
, где - величина шага относительно текущего приближения. Перейти к шагу4.
Шаг 4. Проверка условия окончания поиска.
Да: закончить поиск;
Нет: перейти к шагу 2.
Ход решения:
Исходные данные:
Шаг 1.
Пусть 
Шаг 2.
Вычислим компоненты градиента:
Итерация 1:
Шаг 3
Новое приближение определим по формуле:
Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по 
и приравниваем к 0, получаем:
Получаем:
Итерация 2:
Шаг 3
Новое приближение определим по формуле:
Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Итерация 3:
Шаг 3
Новое приближение определим по формуле:
Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Итерация 4:
Шаг 3
Новое приближение определим по формуле:
Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Решение поставленной задачи методом Коши представлено на рисунке 4.
|
| Рисунок 4 – решение задачи методом Коши |
3.2.Метод Ньютона
Описание алгоритма:
Этот метод использует информацию о вторых производных целевой функции. Эта информация появляется при квадратичной аппроксимации целевой функции, когда при её разложении в ряд Тейлора учитываются члены ряда до второго порядка включительно. Алгоритм метода выглядит следующим образом:
|
|
|
, где:
- гессиан (матрица Гессе)
В случае, когда гессиан положительно определён, направление по методу Ньютона оказывается направлением спуска.
Алгоритм метода:
Шаг 1. Задать: начальную точку х (0). Перейти к шагу 2.
Шаг 2. Вычислить направление поиска в виде
s (x ( k )) = – 
× 
.
Шаг 3. Найти новое приближение (являющееся решением задачи для квадратичной функции)
x (k +1) = x (k) + s (x (k)) = x (k) – × .
Шаг 4.Проверка на условие окончания вычислений.
Да: закончить процесс;
Нет: перейти к шагу 2.
Ход решения:
Исходные данные:
Шаг 1.
.
Шаг 2.
.
Шаг 3.
Из формулы
,
Получаем:
, что совпадает с точным решением.
Решение поставленной задачи методом Ньютона представлено на рисунке 5.
|
| Рисунок 5 – решение задачи методом Ньютона |
