Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Минимизируя правую часть, определяем Ьх, т.е. Ьх = — fx.
После нахождения точки xJ+l = xJ + Ьх определяем fx(xJ + [) и пересчитываем матрицу Я, вычисляя Ht+1 таким образом, чтобы выполнялись N вышеупомянутых соотношений между N(N +1)/2 элементами гессиана.
Элементы H этими соотношениями, конечно, однозначно не определяются. Поэтому нужно привлечь какие-то дополнительные эвристические соображения, например минимизацию отличия W+1 от H1 или что-либо в этом роде. He будем доводить дело до конкретных расчётных формул (все это описано в обширной литературе по математическому программированию); ограничимся лишь изложением основных идей. В настоящее время квазиньютоновские ме-
416
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
тоды составляют основу наиболее эффективных алгоритмов безусловной минимизации. Правда, их высокая эффективность проявилась пока в задачах сравнительно невысокой размерности.
Поиск глобального минимума. Это характерный пример проблемы, которая с одной точки зрения тривиальна, с другой — в сущности неразрешима. В самом деле, вот ее тривиальное решение.
Введем в Rn куб I хп I =S X и сетку с шагом А, покрывающую куб.
Вычислим f°(x) в узлах сетки (это потребует конечного числа операций) и найдем точку сетки, в которой достигается минимальное значение /°. Затем удвоим размер куба (Х-=2Х), уменьшим шаг А вдвое и повторим вышеописанную операцию.
Нетрудно доказать, что для любой непрерывной функции /° можно получить последовательность точек, сходящихся к точке глобального (абсолютного) минимума. Описанная выше операция носит название сканирования. Единственное возражение против ее использования — число (X/h)N вычислений /° на каждом этапе. Сканирование используется в пространствах невысокой размерности (N = 1, 2, 3) на достаточно грубых сетках, но серьезного практического значения эта универсальная процедура поиска не имеет.
Более реалистичной и достаточно часто используемой является процедура случайного поиска. При поиске min f°(x) в кубе I х I ^ X (величина X задает априорную информацию о расположении минимума) значение /° вычисляется в последовательности точек дсу, генерируемых датчиком случайных чисел, равномерно распределенных в кубе. Из этих точек выбирается точка с минимальным значением /°. Доказательство того, что найденная точка находится на расстоянии E1 от точки минимума с вероятностью 1 — є2, где B1, є2 могут быть сделаны сколь угодно малыми за счет соответственно большого числа «испытаний», является упражнением, по теории вероятностей студенческого уровня и особого интереса не представляет. Ответ почти очевиден.
Действительно трудной и интересной алгоритмической задачей является конструирование программных датчиков так называемых «псевдослучайных» чисел с равномерным распределением. Хороший датчик генерирует такую последовательность точек, что каждый ее отрезок достаточно хорошо имитирует равномерное распределение: точки отрезка не должны «сбиваться в кучу», с одной стороны, и не должны оставлять «пустот» в кубе — с другой. Имея такие генераторы точек, можно (при приемлемом числе вычислений /°) «прощупать» ее значение в кубе и найти не слишком уж грубую оценку min f°(x). Число необходимых испытаний (вычислений /°) существенным образом зависит от размерности куба,
§26]
ПОИСК МИНИМУМА
417
требуемой точности и гладкости /°(х). Ограничимся этими общими и почти очевидными сведениями. Случайный поиск давно оформился в самостоятельную дисциплину, и по этому вопросу есть богатая специальная литература.
Метод исчерпывания. Пусть известно, что /° удовлетворяет условию Липшица с константой С. Генерируется последовательность точек куба, выбирается точка с минимальным значением /°. Обозначим через /j минимальное значение функции после у'-го испытания. Вычислим значение в очередной точке xJ+l. Если f°(xi+l) > /’, то около точки xJ+l можно «вырезать» сферу радиусом (/0(л;у+І) — /р/С, в которой значение /° заведомо не меньше /*• и в которой в дальнейшем вычислять значения /° не имеет смысла.
Таким образом, после каждого испытания накапливается информация о тех частях куба, в которых минимум заведомо не находится. Реализация столь простого соображения связана с большими алгоритмическими сложностями, касающимися в сущности двух проблем: хранения накапливающейся информации (и, возможно, ее коррекции; если после очередного испытания значение /* изменилось, исключаемые из просмотра части куба могут быть, соответственно, расширены) и ее использования (не так-то просто генерировать разумным образом распределенные точки в оставшемся «дырявом» множестве). Так что и эта конструкция имеет достаточно ограниченные возможности практической реализации.
Одним из наиболее часто применяемых способов хоть какой-то борьбы с «опасностью локального минимума» является поиск локального минимума при разных выборах стартовых точек х°; а для выбора X0 используются соображения, например, случайного поиска. Итак, простейшая задача (1) послужила поводом познакомить читателя с основными понятиями этой темы. Перейдем к более сложным задачам.
