Научная литература
booksshare.net -> Добавить материал -> Физика -> Федоренко Р.П. -> "Введение в вычислительную физику" -> 163

Введение в вычислительную физику - Федоренко Р.П.

Федоренко Р.П. Введение в вычислительную физику — М.: Физ-тех, 1994. — 528 c.
ISBN 5-7417-0002-0
Скачать (прямая ссылка): vvedenievvichesleniyah1994.djvu
Предыдущая << 1 .. 157 158 159 160 161 162 < 163 > 164 165 166 167 168 169 .. 210 >> Следующая


Поиск условного минимума. Начнем постепенное усложнение постановки задачи. Рассмотрим задачу (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 соответствует единственная точка х(Х).
Предыдущая << 1 .. 157 158 159 160 161 162 < 163 > 164 165 166 167 168 169 .. 210 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed