Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 88
Текст из файла (страница 88)
Описанная выше операция носит название сканирования. Единственное возражение против ее использования — число (Х/Ь)~ вычислений у» на каждом этапе. Сканирование используется в пространствах невысокой размерности (М = 1, 2, 3) на достаточно грубых сетках, но серьезного практического значения эта универсальная процедура поиска не имеет. Более реалистичной и достаточно часто используемой является процедура случайного поиска. При поиске ппп У»(х) в кубе !ха ж Х (величина Х задает априорную информацию о расположении минимума) значение Г~ вычисляется в последовательности точЕк х~, генерируемых датчиком случайных чисел, равномерно распределенных в кубе.
Из этих точек выбирается точка с минимальным значением У». Доказательство того, что найденная точка находится на расстоянии а, от точки минимума с вероятностью 1 — ез, где еп ез могут быль сделаны сколь угодно малыми за счет' соответственно большого числа «испытаний», является упражнением. по теории вероятностей студенческого уровня и особого интереса ие представляет. Ответ почти очевиден. Действительно трудной и интересной алгоритмической задачей является конструирование программных датчиков так называемых «псевдослучайных» чисел с равномерным распределением.
Хороший датчик генерирует такую последовательность точек, что каждый ее отрезок достаточно хорошо имитирует равномерное распрЕ- деление: точки отрезка не должны «сбиваться в кучу», с одной стороны, и не должны оставлять «пустот» в кубе — с другой. Имея такие генераторы точек, можно (при приемлемом числе вычислений У») «прощупать» ее значение в кубе и найти не слишком уж грубую оценку пнп у»(х).
Число необходимых испытаний (вычислений У») существенным образом зависит от размерности куба, 417 526\ ПОИСК МИНИМУМА требуемой точности и гладкости ув(х). Ограничимся этими общими и почти очевидными сведениями. Случайный поиск давно оформился в самостоятельную дисциплину, и по этому вопросу есть богатая специальная литература. Метод исчерпываиия. Пусть известно, что ув удовлетворяет условию Липшипд с константой С. Генерируется последовательность точек куба, выбирается точка с минимальным значением у«. Обозначим через У' минимальное значение функции после у-го испытания, Вычислим значение в очередной точке хз»'.
Если ув(хз+1) > /", то около точки х1~1 можно «вырезать» сферу радиусом (У~(хз+') — У')/с, в которой значение У~ заведомо не меньше ! уз и в которой в дальнейшем вычислять значения /В не имеет / смысла. Таким образом, после каждого испытания накапливается информация о тех частях куба, в которых минимум заведомо не находится. Реализация столь простого аюбражения связана с большими алгоритмическими сложностями, касающимися в сущности двух проблем: хранения накапливающейся информации (и, возможно, ее коррекции; если после очередного испытания значение 7' изменилось, исключаемые из просмотра части куба могут быть, соответственно, расширены) и ее использования (не так-то просто генерировать разумным образом распределенные точки в оставшемся «дырявом» множестве).
Так что и эта конструкция имеет достаточно ограниченные возможности практической реализации. Одним из наиболее часто применяемых способов хоть какой-то борьбы с «опасностью локального минимума» является поиск локального минимума при разных выборах стартовых точек хо; а для выбора хе используются соображения, например, случайного поиска.
Итак, простейшая задача (1) послужила поводом познакомить читателя с основными понятиями этой темы. Перейдем к более сложным задачам. Поиск условного минимума. Начнем постепенное усложнение постановки задачи. Рассмотрим задачу (1) при условии (2а). В этом случае применимы предыдущие алгоритмы спуска по различным направлениям с небольшим алгоритмически несложным дополнением — «проецированием» точек на прямоугольник в ФУ: и = [Х, Х+1, Пусть в точке хз найдено направление е (например, е«« — у~(ху)) и образуется «линия» (в общем случае ломаная) х(г) = Р(х' + зе), где Рз — операция проецирования точки 14 — 1ЗЗЗ ЕРИБЛИЖЕИИЫЕ МЕТОДЫ ВЫЧИГЛИТЕЛЬИОЙ ФИЗИКИ [ч, и 418 е на н. проецирование е сводится к нахождению в х точки, ближайшей к е.
Решение этой задачи элементарно и состоит в покомпонеитной БСРЕЗКЕБЕ (Ре)„= (Х„, з„( Х„; з„, Х„Н е„ж Х+; Х+, г„> Х+), параметр л находится решением задачи ппп УО(Р(х1+ ее)). надо, правда, иметь в виду, что в некоторых случаях прн гладкой функции уз функция Ув(Р(х+ ее)) может иметь разрывы производных. Вместо условий Х 6 х н ХТ можно ввести общее условие х 1= Х, где Я' — некоторое замкнутое множество.
Но, конечно, с усложнением геометрии' лг' операция проецирования на е' усложняется. Метод множителей Лагранжа. Следующий класс задач был исследован очень давно. это — задачи поиска ппп /В(х) прн условиях /1(х) =.О (1 = 1, 2, ..., 1).
Подчеркнем, что в рассматриваемой задаче отсутствуют условия-неравенства. Анализ (проведенный еще Лагранжем) достаточно прост и поучителен. Пусть точка х допустима, т,е. Г1(х) =О (1= 1, 2, ..., 1). Выясним; может лн точка к быть точкой минимума и, если нег, как ее улучшить, т.е. найти допустимую точку с меньшим значением РВ? Исследование проводится методами анализа бесконечно малых. Рассмотрим последствия малого возмущения точки х. Пусть Ьх— малое возмущение. Тогда все функции изменятся на Ы1ж /' Ьх. Итак, следует рассмотреть разрешимость задачи: у~(х) Ьх ВВ О, у1(х) Ьх = О, ! = 1, 2, ..., А Если для всех Ьх из У1(х) Ьх= О (1=1,2, ..., 2) следует Уе(х) Ьх =О, задача неразрешима и рассматриваемая точка удовлетворяет необходимым условиям экстремума.
Известная теорема линейной алгебры утверждает, что в этом случае вектор у~(х) есть линейная комбинация векторов Р'„1(х) (1 = 1, 2, ..., 1), т.е. сущест- 1 вуют множители Лагранжа Л„такие, что У~(х) = ~ Х, У„'(х). Если 1 1 такого представления не существует, то задача для Ьх разрешима и существует вариация Ьх, такая, что условия /1(х+Ьх) =О вы" полняются (в первом порядке) н уВ(х + Ьх) (нли ~В(х — Ьх)) меньше /О(х).
з 26! ПОИСК МИНИМУМА Вышеприведенное рассуждение необходимо дополнить не очень сложным процессом коррекции на величины 0()~Ьхй ), с тем чтобы доказать существование таких малых Ьх = Ьх + 0(11 Ьх112), что с учетом нелинейности УО(х + Ьх) < 7О(х) и /'(х + Ьх) = Г'1(х + Ьх). С этим результатом связаны два возможных алгоритма решения задачи. Первый следует классическому рецепту Лагранжа.
Образуется функция Лагранжа и ищется точка ее безусловного минимума Х(Х) =аГКППП х'(Х, Л) .х-"(Х, Х) = — (Л,ДХ)), 1ХО! = К (4) Множители Х здесь пока не определены. Разумеется, при произвольных множителях Х условия будут нарушены и для их определения ставится естественная задача д.У/дХ,. = у1(х(Х)) = О, 1' = 1, 2, ..., 1. Это — система 1 нелинейных уравнений с / неизвестными. Ее следует решать подходящим методом, например методом Ньютона. Здесь есть, конечно, осложнения.
Зависимость (4) для х(Х) реализуется решением задачи поиска безусловного минимума, а ее придется решать много раз при разных значениях Х. Положение несколько облегчается тем, что при вычислении х(Х) предыдущие значения х могут служить хорошим начальным приближением. Сложным является и вычисление производных д/1(х(Х))/дА, т,е. дифференцирование функций х(А), определенных не совсем обычным образом. Численное дифференцирование в принципе реша- уо о ;о ст проблему, но это требует до- ~ ы Ы полнительных вычислений х(Х). Г К тому же не хотелось бы вычислять х(А) слишком уж точно: это требует большого объема вычислительной работы. Теперь разъясним самое важное обстоятельство — сходнмость предложенной процедуры требует (и это по существу дела) предположения о выпуклости так называемой аблпсти достижииосл1и.
Так называют область Я в пространстве Ф~' точек (/о(х), г1(х), ..., уг(х)), которые могут быть получены при всех допустимых х. Не будем пока давать строгих определений некоторых понятий (выпуклость, строгая выпуклость и т.п,), апеллируя к простым геометрическим образам. На рис. 47 показаны типичные ситуации. Ось абсцисс представляет 1-мерное пространство.
Точка х(А) является самой низкой точкой области Я в направлении Х. Вектор Х является 14* 4Ю пгизлвжвнныв мкгоды вычислительной «изики 1ч. ц Метод условного градиента, Более употребительна другая форма использования идей Лагранжа, к которой можно прийти разными путями. (В зависимости от этого одинаковые по существу методы получают разные названия: метод линеаризации, метод приведенного градиента и т.п.) Мы предпочтем вывести основную конструкцию иа основе линеарнзации. Итак, пусгь точка х допустима в смысле выполнения всех условий ~' =О (1= 1, 2, ..., 2). Ищем малую поправку Ьх, линеаризуя задачу н добавляя ограничение на Ьх.
Смещение Ьх определяегся задачей (3) при условиях У'(»)+У,'(х) Ьх=О, 1=1,2, ...,1. (5) Составляя для этой задачи функцию Лагранжа: .У(Ьх, Л, р) = Ув Ьх + 2,' Х,(~'+ /„' Ьх) — йз (Ьх, Ьх), находим минимум из уравнений Э.У/эЬ» = О. В результате имеем систему уравнений для Ьх, Х, р: Ь» =-'(Уэ+ ~ 1.,У„').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
