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

Геометрическая иллюстрация метода дробления шага для функции 2-х переменных.

Метод с дроблением шага

Градиентные методы

Замечание: градиент указывает направление перемещения прямой для определения максимума.

Градиент функции f(x) некоторой функции направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения функции f(x), проходящей через точку .

Направление наискорейшего убывания функции показывает антиградиент (или градиент )

В качестве будем брать антиградиент

(3.2)

Итерационные методы, в которых направление движения совпадают с антиградиентами, называются градиентными.

выбирается равным нормированному антиградиенту

Тогда соотношение(3.1.) будет преобразовано к виду

Метод простой, так как необходимо найти только первую производную, но возникает проблема выбора .

Из точки мы будем двигаться влево, так как антиградиент имеет знак «–».

Если малое число, то получим слишком много вычислений.

Рассмотрим, если – большое число.

(3.3)

Это условие используется для выбора . Для этого выбирается константа и (часто ).

Полагается , находится и проверяется выполнение условия (3.3). Если не выполняется, то и опять проверяется (3.3). Если опять не выполняется, то полагается и т.д.

1)Задаются . Вычисляются .

Полагается k=1.

2)Полагается .

3)Вычисляются ,,.

4)Проверяется условие выбора

Если выполняется, то осуществляется переход к пункту 5. Если нет, то полагается и переход к пункту 3.

5)Вычисляются

6)Проверяется . Если условие выполняется, то вычисления завершаются. Если нет, то полагается и переход к пункту 2.

Ответ: ,

Замечание: Если функция достаточно гладкая, то удобно начинать с , если как в примере, то лучше взять . При этом в пункт 1 добавляется , а в пункт 2 записывается . Каждая итерация требует незначительных вычислений, но итераций может быть много.