Математика / Курсовая работа: Минимум функции многих переменных

Курсовая работа: Минимум функции многих переменных

Докажем, что тогда спуск по координатам из данного нулевого приближения сходится к минимуму, причем линейно.

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

где через обозначены расстояния между точками. Отсюда получаем . Выполним второй шаг цикла – спуск по направлению в точку , после которого и . Аналогичные рассуждения дают соотношение с . Объединяя эти неравенства, найдем

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

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

и ~.

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

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

Фактическая скорость сходимости будет неплохой при малых , когда линии уровня близки к эллипсам, оси которых параллельны осям координат. Для эллипсов, сильно вытянутых под значительным углом к осям координат, величина и сходимость очень медленная.

Если сходимость медленная, но траектория уже попала в близкую окрестность минимума, то итерации можно уточнять процессом Эйткена; разумеется, при этом надо брать в качестве исходных значения не на трех последних спусках, а на трех циклах спусков (т. е. не точки , а точки и третья точка, которой нет на рис. 3, а).

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

Метод спуска по координатам несложен и легко программируется на ЭВМ. Но сходится он медленно, а при наличии оврагов – очень плохо. Поэтому его используют в качестве первой попытки при нахождении минимума.

Пример. Рассмотрим квадратичную функцию и выберем нулевое приближение . Выполняя вычисления, получим

Уточнение по Эйткену дает , т. е. точное положение минимума (заметим, что делать уточнение с использованием нулевого приближения нельзя).

2.3 Наискорейший спуск

Спускаться можно не только параллельно осям координат. Вдоль любой прямой функция зависит только от одной переменной, , и минимум на этой прямой можно найти.

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

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

Если функция является положительно определенной квадратичной функцией

, (16)