Численные методы поиска минимума функции нескольких переменны

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

7 Метод координатного спуска

Пусть требуется найти минимум f (x, y). Выберем нулевое приближение (x ₀, y ₀). Рассмотрим функцию одной переменной f (x, y ₀) и найдем ее минимум, используя любой из рассмотренных выше способов. Пусть этот минимум оказался в точке (x ₁, y ₀). Теперь точно так же будем искать минимум функции одной переменной f (x ₁, y). Этот минимум окажется в точке (x ₁, y ₁). Одна итерация спусков завершена. Будем повторять циклы, постепенно приближаясь ко дну котловины, пока не выполнится условие .

x

y

Сходимость метода зависит от вида функции и выбора нулевого приближения. Вблизи невырожденного минимума гладкой функции спуск по координатам линейно сходится к минимуму. Если линии уровня образуют истинный овраг, возможен случай, когда спуск по одной координате приводит на дно оврага, а любое движение по следующей координате ведет на подъем. Процесс координатного спуска в данном случае не сходится к минимуму.

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

Дата добавления: 2014-01-07