Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Поиск условного минимума. Начнем постепенное усложнение постановки задачи. Рассмотрим задачу (1) при условии (2а). В этом случае применимы предыдущие алгоритмы спуска по различным направлениям с- небольшим алгоритмически несложным дополнением — «проецированием» точек на прямоугольник в Rn: п=[Х~,Х+]. Пусть в точке Xі найдено направление е (например, е = — Z0x(Xi)) и образуется «линия» (в общем случае ломаная) x(s) = P(xJ + se), где Pz — операция проецирования точки
14 — 1833
418
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
z на л. Проецирование z сводится к нахождению в л точки, ближайшей К Z.
Решение этой задачи элементарно и состоит в покомпонентной «срезке»:
(Pz)n = {Х-, Zn < Х~- Zn, X~*zn*X+n; х;, zn > *+}. Параметр s находится решением задачи min f°(P(xj + s<?)). Надо,
S
правда, иметь в виду, что в некоторых случаях при гладкой функции /° функция /0OPO + se)) может иметь разрывы производных. Вместо условий Х~ =S X 5? X+ можно ввести общее условие хЄ/, где Sf — некоторое замкнутое множество. Ho, конечно, с усложнением геометрии Sf операция проецирования на Sf усложняется.
Метод множителей Лагранжа. Следующий класс задач был исследован очень давно. Это — задачи поиска min f°(x) при условиях /'(х) = 0 (г = 1, 2, ..., /). Подчеркнем, что в рассматриваемой задаче отсутствуют условия-неравенства. Анализ (проведенный еще Лагранжем) достаточно прост и поучителен. Пусть точка х допустима, т.е. /'(*) =0 (г = 1, 2, ..., /). Выясним: может ли точка х быть точкой минимума и, если нет, как ее улучшить, т.е. найти допустимую точку с меньшим значением /°?
Исследование проводится методами анализа бесконечно малых. Рассмотрим последствия малого возмущения точки х. Пусть Ьх — малое возмущение. Тогда все функции изменятся на 6/' ~ f‘x Ьх. Итак, следует рассмотреть разрешимость задачи:
/°(х)Ьхт*0, f‘x(x)bx = 0, і = 1,2, ...,/.
Если для всех Ьх из f‘x(x) Ьх = 0 (/ = 1,2,...,7) следует
/Х(х) Ьх = 0, задача неразрешима и рассматриваемая точка удовлетворяет необходимым условиям экстремума. Известная теорема линейной алгебры утверждает, что в этом случае вектор f°(x) есть
линейная комбинация векторов f‘x(x) (і = I, 2, ..., 7), т.е. сущест-
/
вуют множители Лагранжа Xi, такие, что f°(x) = ^lXi fx(x). Если
i = l
такого представления не существует, то задача для Ьх разрешима и существует вариация Ьх, такая, что условия f‘(x ± Ьх) = 0 вьь полняются (в первом порядке) и /°(х + Ьх) (или /°(х — Ьх)) меньше /°(х).
§26]
ПОИСК МИНИМУМА
419
Вышеприведенное рассуждение необходимо дополнить не очень сложным процессом коррекции на величины 0(116х||2), с тем чтобы доказать существование таких малых Ax = Ьх + 0(||6х||2), чтосуче-том нелинейности f°(x + Ах) < /°(х) и f‘(x + Ах) = /'(х + Ах).
С этим результатом связаны два возможных алгоритма решения задачи. Первый следует классическому рецепту Лагранжа. Образуется функция Лагранжа и ищется точка ее безусловного минимума
х(Х) = arg min -2*(х, X) 5f(x, X) = (X, f(x)), |Х0| = 1. (4)
Множители X здесь пока не определены.
Разумеется, при произвольных множителях X условия будут нарушены и для их определения ставится естественная задача
O^IdXl = fl(x(X)) = 0, і =1,2, ...,/.
Это — система / нелинейных уравнений с I неизвестными. Ее следует решать подходящим методом, например методом Ньютона. Здесь есть, конечно, осложнения. Зависимость (4) для х(Х) реализуется решением задачи поиска безусловного минимума, а ее придется решать много раз при разных значениях X. Положение несколько облегчается тем, что при вычислении х(Х) предыдущие значения х могут служить хорошим начальным приближением.
Сложным является и вычисление производных д/‘(х(Х))/дХ, т.е. дифференцирование функций х(Х), определенных не совсем обычным образом. Численное дифференцирование в принципе реша- у о, уо
ет проблему, HO это требует до-полнительных вычислений х(Х).
К тому же не хотелось бы вычислять х(Х) слишком уж точно: это требует большого объема вычислительной работы.
Теперь разъясним самое важное обстоятельство — сходимость предложенной процедуры требует (и это по существу дела) предположения о выпуклости так называемой области достижимости. Так называют область 9> в пространстве R,+l точек (Z0(X)1Z1(X), ..., /7(х)}, которые могут быть получены при всех допустимых X.
He будем пока давать строгих определений некоторых понятий (выпуклость, строгая выпуклость и т.п.), апеллируя к простым геометрическим образам. На рис. 47 показаны типичные ситуации. Ось абсцисс представляет /-мерное пространство. Точка х(Х) является самой низкой точкой области 3> в направлении X. Вектор X является
Л 1 9>
У
&
Рис. 47
14*
420
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
нормалью к дЗ в точке х(Х), если в этой точке граница гладкая (если х(Х) является угловой точкой границы, X принадлежит множеству «опорных векторов»).
Рассмотрим характерные ситуации, представленные на рис. 47.
а) Нижняя граница 3! строго выпукла вниз. Описанный выше метод имеет шансы на успех, так связь между X и Jt(X) однозначна: каждому X соответствует единственная точка х(Х).