Метод наискорейшего спуска.

Данный метод является модификацией градиентного метода. Основная идея метода состоит в том, что направление поиска  из точки  совпадает с вектором , вычислением в точке  и не меняется до тех пор, пока функция  убывает по этому направлению. Точку, в которой получаем  по направлению  принимаем за точку .

В этой точке вновь определяется новое направление движения  и ищется новый  по этому направлению. Процесс поиска оканчивается тогда, когда расстояние между двумя последовательными минимумами окажется меньше некоторой, заранее заданной малой величины , т.е. при выполнении условия:

                                                                      (2.5)

Для нахождения  по заданному направлению существуют разные способы. Наиболее простой из них состоит в следующем.

Будем двигаться по прямой, соединяющей точки  и  с постоянным шагом до тех пор, пока в некоторой точке функция  не станет больше, чем в предыдущей. После этого поделим шаг пополам и продолжим движение в обратном направлении из точки, в которой функция  имела наименьшее значение и т.д. Поиск  по направлению (т.е. нахождение точки ) будем считать законченным, если величина текущего шага по абсолютной величине станет меньше некоторого, наперед заданного минимального шага . Таким образом, поиск  по заданному направлению из точки  к точке  условно можно рассматривать как колебания маятника с затухающей амплитудой.

Рассмотренный способ требует многочисленных вычислений значений функции  вдоль заданного направления.

Существенного увеличения скорости поиска минимума на прямой, соединяющей 2 соседние точки  и  можно достигнуть, если использовать следующий способ.

Сделаем из точки  3 пробных шага, величиной  и, соответственно, получим значения . По этим 3 значениям можно построить параболу, т.е. получить следующую зависимость: , тогда величина оптимального шага , при котором находится  по заданному направлению, вычисляется из условия . Следовательно, . Таким образом, новая точка  определяется в соответствии с формулой (2.3) как:

                                                                      (2.6)

Запишем алгоритм метода наискорейшего спуска в соответствии с первым способом.

Алгоритм градиентного метода и наискорейшего спуска.

Алгоритм градиентного метода.

1. Задать параметр точности , начальный шаг , выбрать , вычислить значение , принять k=0.

2. Найти градиент  и его норму , проверить . Если условие выполняется, перейти к п.5, иначе – к п.3.

3. Найти новую точку  в соответствии с формулой (2.4) и вычислить .

4. Если , то принять :  и перейти к п.2, иначе  и перейти к п.3.

5. Завершить вычисления, приняв .

Алгоритм метода наискорейшего спуска.

1. Задаем точность вычисления , начальный и минимальный шаги  и , начальную точку .

2. Вычисляем значение .

3. Задаем текущий шаг, запоминаем начальную точку , вычисляем градиент и его норму в этой точке.

4. Поиск  по направлению вектора-антиградиента:

а) вычисляем  в соответствии с формулой (2.6).

б) находим .

в) если , то , , иначе .

5. Если , то возврат на п.4, иначе перейти на п.6.

6. Последнее полученное значение  принимает за  и проверяем условие (2.5). Если оно не выполняется, то возврат на п.3, иначе завершаем вычисления, положив .