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

Вычислив новое приближение, надо обязательно проверить, уменьшилась ли функция. Если оказалось, что

то значение Xg+i нельзя использовать и надо просто сделать от точки Xs какой-то шаг в сторону убывания функции. Обычно делают шаг величиной x{Xs+i - Xs) с t = V2 и проверяют условие убывания функции; если оно снова не выполнено, то уменьшают т вдвое и делают шаг опять из точки л:, и так до тех пор, пока не добьются убывания функции.

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

Если функция имеет несколько локальных минимумов, то итерационный метод может сойтись к любому из них. Удалять найденные минимумы можно только в том случае, когда мы располагаем явным выражением, для Ф (х) и решаем не исходную задачу (1), а уравнение Ф(х) = 0; тогда удаляют уже найденные корни этого уравнения при помощи техники, описанной в главе V.

Если так сделать не удается, то выбирают несколько начальных приближений в разных участках отрезка [а, Ь], и из каждого начального приближения проводят какой-нибудь итерационный процесс поиска минимума. Некоторые из этих итерационных процессов могут сходиться к одному и тому же локальному минимуму, а некоторые -к другим. Остается сравнить найденные локальные минимумы между собой и выбрать наименьший (если это требуется по условиям задачи).

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

4. Стохастические задачи. Опишем один алгоритм, рассчитанный на стохастические задачи. Он основан на предположении, что ошибки определения функции Ф (х) имеют статистическую природу, т. е. они целиком случайны, а систематической погрешности нет. Тогда можно определить минимум со сколь угодно высокой точностью (фактически игнорируя область неопределенности дхгУЬФ), если воспользоваться таким итерационным

Процессом:

ХпХ = Хп~{Ф (Хп + Ьп)-Ф (Хп - Ьп)1 (15)

где йп, Ь„ - последовательности положительных чисел, удовлетворяющие следующим условиям:

со со

/1 = 1 п=\

При выполнении этих условий л;„->-х с вероятностью единица при п-со (напомним, что стремление с вероятностью единица означает «почти всегда стремится», а не «обязательно стремится»). Условиям (16) удовлетворяют, например, ал=1/« и Ьп = п~к

Этот алгоритм является обобщением алгоритма Роббинса - Монро, описанного в главе V, на задачи поиска минимума. Он сходится весьма медленно, ибо изменение аргумента за шаг равно I х„ + , - х„ I 2а„ IФ(л:„) , а величины а„ убывают очень медленно, как видно из второго условия (16). Поэтому применять этот алгоритм к детерминированным задачам невыгодно.

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

1. Рельеф функции. Основные трудности многомерного случая удобно рассмотреть на примере функции двух переменных Ф (х, у). Она описывает некоторую поверхность в трехмерном пространстве с координатами х, у, Ф. Задача Ф (л:, у) = min означает поиск низшей точки этой поверхности.

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

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

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

имеет вид Ф{х, у) = Ф{х, ) + 1(Ах)2ф,,+

+ АхАуФ,у+~(АуУФуу+.-- ,

(18)

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

Рис. 37.

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

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

*) Квадратичная форма ik называется положительно определен-i, k

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