|
|
| Строка 1: |
Строка 1: |
| | | | |
| − | == Постановка задачи ==
| |
| − | Рассмотрим задачу поиска минимума функции <math>f(x)\colon \mathbb{R}^n \to \mathbb{R}</math>
| |
| − | :<math>
| |
| − | \begin{align}
| |
| − | f(x) \rightarrow \min_{x \in \mathbb{R}^n}
| |
| − | \end{align}
| |
| − | </math>
| |
| − | Будем считать, что функция <math>f(x)</math> такова, что можно вычислить её градиент.
| |
| − |
| |
| − | === Общее описание алгоритма ===
| |
| − | Наискорейший спуск<ref>, Н. Н. Калиткин “Численные методы.” Москва <<Наука>>, 1978</ref> — это вариант градиентного спуска: метода нахождения локального экстремума функции с помощью движения вдоль направления градиента.
| |
| − |
| |
| − | ===Математическое описание алгоритма ===
| |
| − | Основная идея метода состоит в том, чтобы идти в направлении <math>-\nabla f</math>, то есть в направлении, в котором функция быстрее всего убывает при бесконечно малом движении из данной точки:
| |
| − | :<math>
| |
| − | \begin{align}
| |
| − | x^{k+1} = x^{k} - \lambda^{k}(\nabla f),
| |
| − | \end{align}
| |
| − | </math>
| |
| − | где выбирается <math>\lambda^{k} </math>по следующему правилу: <math>\lambda^{k} = \operatorname{arg}\min_{\lambda} f(x^{k} - \lambda^{k}(\nabla f))</math>.
| |
| − |
| |
| − | === Вычислительное ядро алгоритма ===
| |
| − |
| |
| − | === Макроструктура алгоритма ===
| |
| − |
| |
| − | === Схема реализации последовательного алгоритма ===
| |
| − |
| |
| − | === Последовательная сложность алгоритма ===
| |
| − |
| |
| − | === Информационный граф ===
| |
| − |
| |
| − | === Ресурс параллелизма алгоритма ===
| |
| − |
| |
| − | === Входные и выходные данные алгоритма ===
| |
| − |
| |
| − | === Свойства алгоритма ===
| |
| − |
| |
| − | == Программная реализация алгоритма ==
| |
| − | === Особенности реализации последовательного алгоритма ===
| |
| − |
| |
| − | === Локальность данных и вычислений ===
| |
| − |
| |
| − | === Возможные способы и особенности параллельной реализации алгоритма ===
| |
| − |
| |
| − | === Масштабируемость алгоритма и его реализации ===
| |
| − |
| |
| − | === Динамические характеристики и эффективность реализации алгоритма ===
| |
| − |
| |
| − | === Выводы для классов архитектур ===
| |
| − |
| |
| − | === Существующие реализации алгоритма ===
| |
| − |
| |
| − | == Литература ==
| |
| − | <references />
| |
