Главная > Математика > Численные методы
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 2. Минимум функции многих переменных

1. Рельеф функции.

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

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

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

и разложение функции по формуле Тейлора вблизи минимума имеет вид

причем квадратичная форма (18) — положительно определенная иначе эта точка не была бы невырожденным минимумом. А линии уровня знакоопределенной квадратичной формы — это эллипсы.

Рис. 37.

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

Отметим, что условию (17) удовлетворяют также точки максимумов и седловые точки.

Но в точках максимумов квадратичная форма (18) отрицательно определенная, а в седловинах она знакопеременна.

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

Рассмотрим овражный тип рельефа. Если линии уровня кусочно-гладкие, то выделим на каждой из них точку излома. Геометрическое место точек излома назовем истинным оврагом, если угол направлен в сторону возрастания функции, и гребнем — если в сторону убывания (рис. 37, б). Чаще линии уровня вхюду гладкие, но на них имеются участки с большой кривизной; геометрические места точек с наибольшей кривизной назовем разрешимыми оврагами или гребнями (рис. 37, в). Например, рельеф функции

изображенный на этом рисунке, имеет ярко выраженный извилистый разрешимый овраг, «дно» которого — синусоида, а низшая точка — начало координат.

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

Неупорядоченный тип рельефа (рис. 37, г) характеризуется наличием многих максимумов, минимумов и седловин. Примером может служить функция

рельеф которой изображен на этом рисунке; она имеет минимумы в точках с координатами максимумы в точках, сдвинутых относительно минимумов на по каждой координате.

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

<< Предыдущий параграф Следующий параграф >>
Оглавление