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