Федоренко Р.П. Введение в вычислительную физику (1185915), страница 85
Текст из файла (страница 85)
При г = Т имеем у,(х) ш и(Т, х) = ~Ч с е ~ "гр„ Внесем в У, «погрешности измерению и превратим ее в функцию у(х) = ~ч' (сье " "~ + Ь«) р Решая регуляризованную обратную задачу теплопроводносги (5) с начальными данными /(х) и параметром е, получаем И*(Х) — Х~; (С Е-А ° т+ б )Еа А 0- «>Г,р ар ~, (1 е-а«а Г)с ар +~Ч, б е«а (1-аа а агар В решении задачи и' выделены три основные компоненты: точное решение и,(х), погрешность регуляризации (вторая сумма) и «погрешность некорректиостиь (третья сумма). Положим, для определенности, аи,а = 1, з'=0.01, 6 = 0.01 и вычислим при разных е значения Р 1 сааб г аа 001е«й 0-а« «аг Д Д Они имеют простой содержательный смысл.
Если, например, и, = р„, то в функции и'(х) погрешность регуляризации достигает величины Р . Если функция У,(х) возмущена только членом Ь р, то ен дает вклад в погрешность восстановления порядка ды лгихлижвииыа матоды вычиелитальиоя бизихи !ч. и В табл. 15 представлены значения этих величин. При 8- величина га- 1, при А 1/т'2изе величина 7 достигает максимального значения Ьег"4'. Прокомментируем табл. 15, приняв не очень высокие требования к точносгн восстановления и, (будем считать допустимой погрешность порядка 10 %). При а = 5 10 3 погрешность некорректности О достаточно мала, но погрешность регуляризации г такова, что удовлетворительный Таблица 15 9 10 5 б 0.074 0.01 4 Олн 0.014 О.О05 о.о! 0.32 о.016 0.95 0.006 510 3 О.ОШ 0.015 0.076 О,О22 0.22 О.О38 О.ОО1 0.01 .46 07! 0.064 0.10 0.90 0.12 10 3 0.10 7 10 0.01 0.01 0.015 0.06 0.023 0.17 0.04 0.36 0.61 0.075 0.14 0.82 0.22 7.5 1О 0.25 0.28 4 10 0.01 0.008 0.015 0,96 1.21 1.5 0.11 0.042 0.038 0.023 0.26 0.09 0.46 0.19 0.69 0.39 0,86 0.75 5 Ю 1.2 результат получается лишь в случае, когда функция и, состоит из двух первых гармоник.
При а = 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}
