Градиентный метод Дифференциальное и интегральное исчисление Введение в анализ. Предел Декартова, полярная и сферическая системы координат

Решение алгебраических и трансцендентных уравнений

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

Пусть функция  непрерывно дифференцируема на , а Î

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

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

Пусть  выбрано. Тогда градиентный метод заключается в построении последовательности {} по правилу , .

- длина шага или просто шаг градиентного метода.

Если , то шаг можно выбрать так, чтобы . Если , то - точка минимума функции . В этом случае итерационный процесс прекращается.

Существуют различные способы выбора величины в градиентном методе. В зависимости от способа выбора можно получить различные варианты градиентного метода.

На луче, направленном по антиградиенту, введем функцию одной переменной , и определим  из условий .

Этот метод принято называть методом наискорейшего спуска. На практике итерации продолжают до тех пор, пока не будет выполнен некоторый критерий окончания счета

, или , или , где - заданные числа.

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

Для более детального знакомства с данной темой предлагается книга Ф. П. Васильева "Численные методы решения экстремальных задач".

Упражнение 7. Найти наименьшее n, начиная с которого точность метода золотого сечения больше точности метода деления отрезка пополам в 2 раза, в 10 раз.Упражнение 8. Написать алгоритм описанного метод.

В чем суть классического подхода к решению задач нахождения экстремума функций одной переменной?

Линейное программирование Постановка задачи. Графический метод.

Пример 3 (распределение ресурсов) Предприятие производит два вида продукции из двух видов сырья, причем известны запасы обоих видов сырья, расход сырья на каждый вид продукции и доход с одной единицы каждой продукции:

Двойственная задача В матричном виде задача, двойственная к задаче линейного программирования в общем виде, имеет вид: АtY ³ C, Y ³ 0, V=(b,y) -> max.


На главную