--PAGE_BREAK--1.1 Градиентные методы
Основная идея методов заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом :
где λ[j] выбирается
· постоянной, в этом случае метод может расходиться;
· дробным шагом, то есть длина шага в процессе спуска делится на некое число;
· наискорейшим спуском:
1.2 Метод наискорейшего спуска (метод градиента)
Выбирают , где все производные вычисляются при , и уменьшают длину шага λ[j] по мере приближения к минимуму функции F.
Для аналитических функций F и малых значений fi тейлоровское разложение F(λ[j]) позволяет выбрать оптимальную величину шага
(5)
где все производные вычисляются при . Параболическая интерполяция функции F(λ[j]) может оказаться более удобной.
Алгоритм
1. Задаются начальное приближение и точность расчёта
2. Рассчитывают , где
3. Проверяют условие останова:
o Если \epsilon" v:shapes="_x0000_i1050">, то j = j + 1 и переход к шагу 2.
o Иначе и останов.
1.3 Метод покоординатного спуска (Гаусса—Зейделя)
Улучшает предыдущий метод за счёт того, что на очередной итерации спуск осуществляется постепенно вдоль каждой из координат, однако теперь необходимо вычислять новые раз за один шаг.
Алгоритм
1. Задаются начальное приближение и точность расчёта
2. Рассчитывают , где
3. Проверяют условие останова:
o Если \epsilon" v:shapes="_x0000_i1056">, то и переход к шагу 2.
o Иначе и останов.
продолжение
--PAGE_BREAK--1.4 Метод сопряжённых градиентов
Метод сопряженных градиентов— метод нахождения локального минимума функции на основе информации о её значениях и её градиенте. В случае квадратичной функции в минимум находится за n шагов.
Определим терминологию:
Пусть .
Введём на целевую функцию .
Вектора называются сопряжёнными, если:
·
·
где — матрица Гессе .
1.4.1 Обоснование метода Нулевая итерация
Рисунок 2 — Иллюстрация последовательных приближений метода наискорейшего спуска (зелёная ломаная) и метода сопряжённых градиентов (красная ломаная) к точке экстремума.
Пусть
Тогда .
Определим направление так, чтобы оно было сопряжено с :
Разложим в окрестности и подставим :
Транспонируем полученное выражение и домножаем на справа:
В силу непрерывности вторых частных производных . Тогда:
Подставим полученное выражение в (3):
Тогда, воспользовавшись (1) и (2):
Если , то градиент в точке перпендикулярен градиенту в точке , тогда по правилам скалярного произведения векторов:
Приняв во внимание последнее, получим из выражения (4) окончательную формулу для вычисления :
продолжение
--PAGE_BREAK--