|
|
| Строка 1: |
Строка 1: |
| - | == Постановка задачи ==
| |
| - | Рассмотрим задачу поиска минимума функции <tex>f(x): \mathbb{R}^n \to \mathbb{R} </tex>, записываемую в виде:
| |
| - | {{eqno|1}}
| |
| - | ::<tex>f(x) \to \min_{x \in \mathbb{R}^n}</tex>
| |
| | | | |
| - | == Метод градиентного спуска ==
| |
| - |
| |
| - | === Идея метода ===
| |
| - |
| |
| - | Основная идея метода заключается в том, чтобы идти в направлении наискорейшего спуска, а это направление задаётся антиградиентом <tex>-\nabla f</tex>:
| |
| - |
| |
| - | <tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>
| |
| - |
| |
| - | где <tex>\lambda^{[j]}</tex> выбирается
| |
| - | *постоянной, в этом случае метод может расходиться;
| |
| - | *дробным шагом, т.е. длина шага в процессе спуска делится на некое число;
| |
| - | *наискорейшим спуском: <tex>\lambda^{[j]}=\arg \min_{\lambda} \,f(x^{[j]}-\lambda\nabla f(x^{[j]})) \!</tex>
| |
| - |
| |
| - | === Алгоритм ===
| |
| - | '''Вход:''' функция <tex>f: \mathbb{R}^n \to \mathbb{R}</tex>
| |
| - |
| |
| - | '''Выход:''' найденная точка оптимума <tex>x</tex>
| |
| - |
| |
| - | # Повторять:
| |
| - | # <tex>x^{[j+1]}=x^{[j]}-\lambda^{[j]}\nabla f(x^{[j]}) </tex>, где <tex>\lambda^{[j]}=\arg\min_{\lambda} \,f(x^{[j]}-\lambda \nabla f(x^{[j]})) </tex>
| |
| - | # если выполен критерий останова, то возвращаем текущее значение <tex>x^{[j+1]}</tex>
| |
| - |
| |
| - | ===Критерий останова===
| |
| - | Критерии остановки процесса приближенного нахождения минимума могут быть основаны на различных соображениях.
| |
| - | Некоторые из них:
| |
| - | # <tex>||x^{[k+1]}-x^{[k]}||\leq\eps</tex>
| |
| - | # <tex>||f(x^{[k+1]})-f(x^{[k]})||\leq\eps</tex>
| |
| - |
| |
| - | Здеcь <tex>x^{[k]} \in \mathbb{R}^n</tex> - значение, полученное после <tex>k</tex>-го шага оптимизации.
| |
| - | <tex>\eps</tex> - наперед заданное положительное число.
| |
| - |
| |
| - | ===Сходимость метода===
| |
| - |
| |
| - | == Числовые примеры ==
| |
| - | == Рекомендации программисту ==
| |
| - | == Заключение ==
| |
| - | == Ссылки ==
| |
| - | * [[Практикум ММП ВМК, 4й курс, осень 2008|Практикум ММП ВМК, 4й курс, осень 2008]]
| |
| - |
| |
| - | == Список литературы ==
| |
| - | * ''А.А.Самарский, А.В.Гулин.'' Численные методы. Москва «Наука», 1989.
| |
| - | * ''Н.С.Бахвалов, Н.П.Жидков, Г.М.Кобельков.'' Численные методы. Лаборатория Базовых Знаний, 2003.
| |
| - | * ''Н.Н.Калиткин.'' Численные методы. Москва «Наука», 1978.
| |
| - |
| |
| - | {{stub}}
| |
| - | [[Категория:Учебные задачи]]
| |
