Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
min {f°(xj) + f°(xj) 6*}, И6х|| =S є. (3)
Ьх
Ограничение ||6х|| необходимо, чтобы избежать бесконечного решения.
Решение легко находится методом множителей Лагранжа. Формируем функцию Лагранжа
(Ьх, X) = f°(xj) + f°x(x-') Ьх + 0.5 ЦЬх, Ьх)
с неопределенным пока множителем X и ищем точку ее минимума по Ьх. Задача решается просто. Приравнивая нулю производную по Ьх, находим Ьх(Х) = —(1 А)/°(ху). Множитель X определяется условием (6х(Х), Sx(X)) = є2. Теперь можно использовать Ьх двумя способами: либо считать Ьх направлением спуска и определять Xі+i = xj + sbx после решения задачи минимизации по s, либо определять XJ + > = Xj + дх.
В первом случае величина є, очевидно, никакой роли не играет. Этот способ надежный, но требует нескольких дополнительных вычислений /° для определения s. Второй способ более экономный, HO величину є надо назначать очень ответственно: она должна быть достаточ-
412
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. И
но мала, чтобы линейная аппроксимация f°(x + 6х) ~ f°(x) + fx Ьх была достаточно точной. Однако є не должно быть слишком малой величиной, чтобы «движение» Xі проходило не слишком малыми шагами. В своей работе автор обычно использовал второй способ (в сложных задачах вычисление /° часто оказывается одной из наиболее дорогих операций).
Для определения є используется алгоритм адаптации. Сначала є назначается из каких-то грубых соображений. После очередного шага сравнивается приращение Af0 = f°(xJ+l) — f°(xj) с вариацией 6/ = fx(xJ) Ьх. Если они совпадают с высокой точностью, значение є, соответственно, увеличивается; если совпадение плохое, — уменьшается. (Обычно увеличение и уменьшение є осуществляются умножением на числа, не сильно отличающиеся от единицы. В дальнейшем мы подробнее обсудим эти вопросы в более сложной ситуации.) Если A/0 > 0, происходит «возврат» в точку х> и Ьх вычисляется заново после пересчета є := є/2, например.
Метод случайного спуска. Он отличается от описанных выше тем, что в качестве направления движения выбирается «случайное» направление, т.е. единичный вектор е, генерируемый каким-либо датчиком случайных векторов, равномерно распределенных на единичной сфере в Rn (такие датчики входят в состав математического обеспечения современных ЭВМ). «Почти любое» направление е является направлением «спуска», если, конечно, рассматривать как положительные, так и отрицательные значения s. Стационарными точками процесса построения минимизирующей последовательности являются только точки локального минимума /°.
Эффективность методов спуска. «Овраги». Задача поиска минимума гладкой функции с общематематической точки зрения является одной из простейших. Основная идея решения (построение минимизирующей последовательности) очевидна, да и конструктивная ее реализация не очень сложна. Проблема существования решения и сходимости процесса решается тоже не очень сложными средствами. Ответ дают такие простые факторы, как непрерывность и принадлежность всех точек х* некоторому компакту. Поэтому сведение какой-либо задачи к поиску min f°(x) на компакте справедливо считают почти исчерпывающим ее решением.
Многие сложные задачи естествознания и техники стремятся оформить именно как вариационные задачи. Однако внешняя простота решения обманчива. Дело в том, что задача проста, если она решается «в принципе»: на уровне доказательства сходимости. Ho пока не обсуждался важнейший фактор — эффективность процесса поиска минимума, количество вычислений функции /°, которое по-
§26]
ПОИСК МИНИМУМА
413
надобится для определения min f°(x) с какой-то (часто не очень высокой) степенью точности.
Продолжающееся до сих пор конструирование алгоритмов поиска минимума имеет основной целью повышение их эффективности и надежности. Такая работа должна опираться на достаточно четкую теоретическую концепцию, объясняющую причины возможной крайне низкой скорости убывания Конечно, одной из причин
этого может быть существенная фактическая негладкость /°, даже если формально она имеет сколько угодно непрерывных производных. С точки зрения вычислителя гладкость — это не число существующих производных, а константы, ограничивающие их значения. Если эти константы просто «конечны», то нет особой разницы между классами гладких и негладких функций. Эту причину (существенную негладкость /°) оставим пока в стороне. Ведь отношение вычислителя к тем или иным методам определяется не столько их способностью решать задачу данного типа в ее общей формулировке, сколько эффективностью метода в классе тех задач, которые нуждаются в фактическом решении.
Итак, в каком случае методы спуска оказываются эффективными, а в каком нет? Этот вопрос сейчас изучен достаточно полно. Основной моделью, на которой получаются точные результаты, является класс квадратичных функций /°(х) = (а, х) + 0.5(Лх, х) с положительно-определенной самосопряженной матрицей А. В окрестности точки минимума (слово «локальный» будем для краткости опускать) гладкая функция /° хорошо аппроксимируется именно квадратичной функцией. Матрица А в данном случае аналогична матрице d2f° / QxiQxj, именуемой гессианом. Существенным фактором, определяющим эффективность метода спуска по градиенту, является обусловленность матрицы А, т.е. отношение т] = І/L, где L и
