Навигация
2.2 Спуск по координатам
Казалось бы, для нахождения минимума достаточно решить систему уравнений типа (11) методом линеаризации или простых итераций и отбросить те решения, которые являются седловинами или максимумами. Однако в реальных задачах минимизации эти методы обычно сходятся в настолько малой окрестности минимума, что выбрать подходящее нулевое приближение далеко не всегда удается. Проще и эффективнее провести спуск по координатам. Изложим этот метод на примере функции трех переменных 
.
Выберем нулевое приближение 
. Фиксируем значения двух координат 
. Тогда функция будет зависеть только от одной переменной 
; обозначим ее через 
. Найдем минимум функции одной переменной 
и обозначим его через 
. Мы сделали шаг из точки 
в точку 
по направлению, параллельному оси ; на этом шаге значение функции уменьшилось.
Затем из новой точки сделаем спуск по направлению, параллельному оси 
, т. е. рассмотрим 
, найдем ее минимум и обозначим его через 
. Второй шаг приводит нас в точку 
. Из этой точки делаем третий шаг – спуск параллельно оси 
и находим минимум функции 
. Приход в точку 
завершает цикл спусков.
Будем повторять циклы. На каждом спуске функция не возрастает, и при этом значения функции ограничены снизу ее значением в минимуме 
. Следовательно, итерации сходятся к некоторому пределу 
. Будет ли здесь иметь место равенство, т. е. сойдутся ли спуски к минимуму и как быстро?
Это зависит от функции и выбора нулевого приближения. На примере функции двух переменных легко убедиться, что существуют случаи сходимости спуска по координатам к искомому минимуму и случаи, когда этот спуск к минимуму не сходится.
Будем двигаться по выбранному направлению, т. е. по некоторой прямой в плоскости 
. В тех участках, где прямая пересекает линии уровня, мы при движении переходим от одной линии уровня к другой, так что при этом движении функция меняется (возрастает или убывает, в зависимости от направления движения). Только в той точке, где данная прямая касается линии уровня (рис. 3, а), функция имеет экстремум вдоль этого направления. Найдя такую точку, мы завершаем в ней спуск по первому направлению, и должны начать спуск по второму направлению (поскольку направления мы сейчас выбираем параллельно координатным осям, то второе направление перпендикулярно первому).
Пусть линии уровня образуют истинный овраг. Тогда возможен случай (рис. 3, б), когда спуск по одной координате приводит нас на «дно» оврага, а любое движение по следующей координате (пунктирная линия) ведет нас на подъем. Никакой дальнейший спуск по координатам невозможен, хотя минимум еще не достигнут; процесс спуска по координатам в данном случае не сходится к минимуму.
Наоборот, если функция достаточно гладкая, то в некоторой окрестности минимума процесс спуска по координатам сходится к этому минимуму. Пусть функция имеет непрерывные вторые производные, а ее минимум не вырожден. Для простоты опять рассмотрим функцию двух переменных 
. Выберем некоторое нулевое приближение 
и проведем линию уровня через эту точку. Пусть в области 
, ограниченной этой линией уровня, выполняются неравенства, означающие положительную определенность квадратичной формы (12):
. (15)
Докажем, что тогда спуск по координатам из данного нулевого приближения сходится к минимуму, причем линейно.
Значения функции вдоль траектории спуска не возрастают; поэтому траектория не может выйти из области , и неравенства (15) будут выполняться на всех шагах. Рассмотрим один из циклов, начинающийся в точке 
(рис. 3, а). Предыдущий цикл окончился поиском минимума по направлению , следовательно, 
и 
. Первый шаг нового цикла спускает нас по направлению в точку 
, в которой 
и 
. Поскольку вторые производные непрерывны, можно применить теорему о среднем; получим
где через 
обозначены расстояния между точками. Отсюда получаем 
. Выполним второй шаг цикла – спуск по направлению в точку 
, после которого 
и 
. Аналогичные рассуждения дают соотношение с 
. Объединяя эти неравенства, найдем
.
Следовательно, за один цикл 
уменьшается в 
раз; то же справедливо для 
, если рассмотреть цикл, сдвинутый на один шаг, т. е. начинающийся в точке и кончающийся в точке 
.
Значит, когда число циклов 
, то все первые производные линейно стремятся к нулю:
и 
~
.
Первые производные одновременно обращаются в нуль в точке минимума и вблизи него являются линейными однородными функциями приращений координат. Поэтому координаты точек спуска линейно стремятся к координатам точки минимума, т. е. в данном случае спуск по координатам сходится, причем линейно.
Случай (15) заведомо реализуется в достаточно малой окрестности невырожденного минимума, ибо эти условия эквивалентны требованию положительной определенности квадратичной формы (12). Такими образом, вблизи невырожденного минимума достаточно гладкой функции спуск по координатам линейно сходится к минимуму. В частности, для квадратичной функции этот метод сходится при любом нулевом приближении.
Фактическая скорость сходимости будет неплохой при малых , когда линии уровня близки к эллипсам, оси которых параллельны осям координат. Для эллипсов, сильно вытянутых под значительным углом к осям координат, величина 
и сходимость очень медленная.
Если сходимость медленная, но траектория уже попала в близкую окрестность минимума, то итерации можно уточнять процессом Эйткена; разумеется, при этом надо брать в качестве исходных значения не на трех последних спусках, а на трех циклах спусков (т. е. не точки 
, а точки 
и третья точка, которой нет на рис. 3, а).
Разрешимый овраг напоминает сильно вытянутую котловину (см. рис. 3, б). При попадании траектории спуска в такой овраг сходимость становится настолько медленной, что расчет практически невозможно вести. Отметим, что в стохастических задачах наличие ошибок эквивалентно превращению истинных оврагов и гребней в разрешимые; расчет при этом можно продолжать, хотя практическая ценность такого расчета невелика: сходимость очень медленная.
Метод спуска по координатам несложен и легко программируется на ЭВМ. Но сходится он медленно, а при наличии оврагов – очень плохо. Поэтому его используют в качестве первой попытки при нахождении минимума.
Пример. Рассмотрим квадратичную функцию 
и выберем нулевое приближение 
. Выполняя вычисления, получим
.
Уточнение по Эйткену дает 
, т. е. точное положение минимума (заметим, что делать уточнение с использованием нулевого приближения нельзя).
Похожие работы
... , Флетчера-Ривса). Методы второго порядка, использующие, кроме того, и информацию о вторых производных функции f (x) (метод Ньютона и его модификации). Метод конфигураций (Хука - Дживса) Следует выделить два этапа метода конфигураций: 1) исследование с циклическим изменением переменных и 2) ускорение поиска по образцам. Исследующий поиск начинается в точке х0, называемой старым базисом. ...
... (x, y) выполняется неравенство: . При этом, т. е. приращение функции > 0. Определение 3: Точки локальных минимума и максимума называются точками экстремума. Условные Экстремумы При отыскании экстремумов функции многих переменных часто возникают задачи, связанные с так называемым условным экстремумом. Это понятие можно разъяснить на примере функции двух переменных. Пусть заданы функция ...
... p и q, получим некоторые наборы (в зависимости от p и q) на которых функция достигает максимума. 3. Решение задачи с использованием метода покоординатного спуска 3.1 Описание метода покоординатного спуска Изложим этот метод на примере функции трех переменных . Выберем нулевое приближение . Фиксируем значения двух координат . Тогда функция будет зависеть только от одной переменной ; ...
... , которые содержат неизвестную функцию, её производные и аргументы. Обыкновенным называется дифференциальное уравнение, в котором неизвестная функция является функцией одной переменной. Если неизвестная функция является функцией многих переменных, то соответствующее уравнение называется дифференциальным уравнением в частных производных. Порядком дифференциального уравнения называется наивысший ...
0 комментариев