Федоренко Р.П. Введение в вычислительную физику (1185915), страница 89
Текст из файла (страница 89)
— //(х))з). (8) / ! 424 игиелижеииые методы вычиглительиой «изики 1ч. и Здесь 1а) = а, если а > О, 1а) = О в противном случае; А — большой коэффициент «штрафа» за нарушение условий. Функцию Р(х, А) называют «штрафной функцией». Сведение задачи (1), (2) к минимизации Р(х, А), разумеется, приближенное, ио тем более точное, чем больше А. К сожалению, практика применения метода оказалась не очень успешной.
Введение в конструкцию (8) большого параметра А приводит к тому, что в точках х, где У~(х) ~ О (1 = 1, 2, 3, ...), функция Р оказывается очень негладкой, имеет сложное «овражноь~ строение и очень трудно минимизируется. Скорость сходимости методов поиска минимума оказывается столь медленной, что точки «мииимизирующей» последовательности хз практически «стоят на месте», и зто часто принимают за достижение минимума. Таким образом, метод дает неверные результаты, которые нередко принимаются за решение сложных задач. Полезно еще раз отметить, что эффективность методов приближенных вычислений существенным образом связана с гладкостью используемых функциональных зависимостей.
Метод штрафных функций достигает своих целей (замеиа задачи на условный экстремум задачей безусловной оптимизации) ценой именно этого важнейшего фактора, делая из «хороших» функций ~'(х) «плохую» функцию Р (см. (8)). Недостатки метода пытаются преодолеть следующим образом. Параметр А сначала берется не очень большим, так что свойства гладкости Р еще немногим хуже свойств ~. Найденное решение задачи х(А) = агй пйп Р(х, А), конечно, сильно нарушает условия ~' = О (1= 1, 2, 3, ...), и его используют как начальное приближение в задаче с несколько увеличенным значением А, и т.д. Однако и эта идея не привела к очень уж большим успехам.
Метод модифицированной функции Лагранжа. Перейдем к одной из наиболее удачных вычислительных конструкций. Исходная задача заменяется следующей: ппп Р(х, А) при условиях У'(х) =О, 1=1,2, ..., 1. (9) Суть дела в том, что теперь параметр А принимает умеренные значения. Его цель — сделать границу области достижимости выпуклой вниз (хотя бы локально, в окрестности искомого решения; см. рис. 47). Применим к задаче (9) алгоритм выпукдого программирования, К методу модифицированной функции Лагранжа можно прийти н нз других соображений.
Минимизируем функцию Р(х. А) со слабым штрафом. Пусть х(А) = аг8 ппп Р(х, А). Тогда, как уже отмечалось, У'(х(А)) = г,. мО, Введем «иевязки» г, в конструкцию (8) заранее. Используем простое соображение. Если введение штрафа А смещает пош к минимтмА 425 й 241 точку минимума на расстояния го попробуем решать с этим же штрафом А задачу с условиями У'(х) + гп надеясь, что новые условия будут выполнены с теми же погрешностями г; в точке х(А): У'(х) + г,. = г,, т.е. У'(х(А)) = О, 1««1, 2, 3, Итак, новая штрафная функция будет такой: Р(х, А) = Гв(х) + А ~Х ~/'(х) + г 12 = ( ! = Ув(х) + А ~х' (У'(х))2+ ~ Аг/'(х) + А ~ гз Значения г; берутся с предыдущей итерации, Аг,.
играют роль множителей Лагранжа Х,. Последнее слагаемое, очевидно, можно опустить. Метод лннеариаацин. Вторая основная вычислительная конструкция, которую удалось довести до сравнительно эффективных аагорнтмов, связана с одной из фундаментальных идей вычислительной математики. По традиции ее связывают с именем Ньютона. Задача линеаризуется в окрестности некоторого уже найденного приближения к решению, и следующее, лучшее, приближение, находится решением лннеаризованной задачи.
Пусть х — некоторое текущее приближение к решению задачи поиска условного экстремума. Следующее приближение ищется в вцде х + Ьх, где Ьх — «малая» поправка, которая решает лннеаризованную задачу ппп 12«(х) + /в(х) Ьх~ (10) при условиях а) Р, ж г" (х) +/,'(х) Ьх ж Г,'., 1= 1, 2, ..., 1, (11) б) з„цбх„аз~, и=1,2, ...,М.
Числа 5„, 5+ определяют «шаг» процесса. Задача (1О), (11) является хорошо изученной задачей линейного программирования, для решения которой давно разработаны достаточно надежные алгоритмы (так называемый симплекс-метод). Эффективность конкретного алгоритма существенно определяется тактикой подбора шага (з, з+), которая, конечно же, должна опираться на информацию, получаемую в процессе решения задачи.
Опишем основные технологические элементы метода линеаризацни, разработанного автором в начале шестидесятых годов и применявшегося в существенно более сложной ситуации (подробнее об 426 игивлижеииые методы вычислительной ьизики (ч. и этом см. в з 28). При организации вычислений нужно избежать двух опасностей: при слишком малом значении шага процесс протекает надежно, но медленно; при слишком большом значении шага пренебрежение квадратичными членами становится необоснованным и процесс перехода от х к х + Ьх становится бессмысленным.
Итак, шаг должен быть максимально возможной величиной, при которой линеаризация функций обладает достаточной точностью. Это качественное соображение предстоит превратить в алгоритм подбора шага в зависимости от фактического хода вычислений. Введем параметры, управляющие процессом решения, а) Числа е,.
(1= 1, 2, ..., Г) определяют заданную постановкой задачи точность выполнения условий (26). 6) Число 5 (шаг процесса) входит в алгоритм генерации чисел г„= О(5), в,+, = 0(5). Учет условий (2а) очевиден. в) Число С в начале процесса — достаточно большое число (С =!Оз —: 10т). В процессе решения задачи зто число автоматически меняется и стремится к единице. На данном этапе поиска решения в условиях (26) допускается погрешность Свг Стандартный шаг алгоритма состоит из следующих.
операций. 1. Пусть уже получена точка х, выработались какие-то числа 5 и С. 2. Задача линеаризуется, т.е. вычисляются значения ~'(х), производные („'(х) и числа з„, з„. Таким образом, задача (10), (11) сформирована. 3. Решается задача (10), (11). При значительных нарушениях в точке х условий (26) задача может и ие иметь решения. Алгоритм обнаруживает этот факт и переходит к определению Ьх с целью минимизации в «(Ьх) = ); [У'(х) + у'„'(х) Ьх],', ! 1 где (а'). = (!а' — Г, ), а'< Г~, ~а' — Р,':~, а'> Р,+.; иначе О), другими словами, игнорируя значение Гв, мы стремимся получить так называемую допустимую точку х, в которой с требуемой точностью выполнены все условия. В любом случае получается вариация Ьх. 4.
Вычисляются вариации функций ЬУ' = ~„' Ьх и (после вычисления значений /'(х + Ьх)) их приращения Л(' = г" (х + Ьх) — г" (х). 5. После этого начинается логически наиболее сложная операция — анализ и принятие решений об изменении управляющих параметров. Выделяются характерные ситуации, в каждой из которых реализуется свое целесообразное поведение.
427 й 2б1 ПОИСК МИНИМУМА 5.1. Пусть точка х недопустима, т.е, ~~'(х) 1„> С«,. котя бы при одном 1. В этом случае вычисляется погрешность линейного приближения т) =п1ак ~1ЬУ' — Лг')/Ь/'~. При этом максимум вычисляется !»1 лишь для тех индексов, для которых условие нарушено и в новой точке х + Ьх, т,е. 1У'(х + Ьх)], > С«и В зависимости от значения «1 изменяется шагб для следующей итерации. Если «1 О, шаг 5 увеличивается; если «1 ж 1, шаг 5 уменьшается.
При определенных обстоятельствах (г1Ьх) > г(0)) итерация «отменяется», шаг 5 уменьшается (например, вдвое) и задача линейного программирования решается заново. Описанная выше ситуация типична для начала решения задачи, когда взятая из каких-то соображений точка начального приближения х грубо нарушает условия (26). Какое-то число первых итераций процесса тратится на определение допустимой точки х. Значение ГО на этом этапе обычно растет. 5.2. Пусть точка х допустима и точка х + Ьх тоже удовлетворяет всем условиям с погрешностью С«.
При этом погрешность «1 вычисляется только по индексу 1= 0. Здесь могут представиться разные ситуации. а) о|Ос О, т.е. при выполнении условий с погрешностью Сс,. происходит уменьшение /и. В этом случае пересчитывается шаг Я (так же, как это было описано выше), точка х заменяется на х + Ьх и процесс продолжается с операции 5.1 (конечно, вычисления г' в точке х + Ьх не повторяются, они уже известны). б) Ь/О < О, но Л1о > О, Это означает, что шаг 5 слишком велик. Поэтому итерация «отменяется», шаг 5 уменьшается (например, вдвое) и задача линейною программирования решается заново.
в) Ь~» > 0 и точность линейного приближения удовлетворительна (ц 0.1, например). Решение задачи линейного программирования приводит к росту гО. Такая ситуация обычно связана не с погрешностью линеаризации, а с тем, что условия (2б) в точке х + Ьх выполнены с большей точностью, чем условия в точке х. Улучшение точки х + Ьх получено ценой некоторого увеличения у'О, хотя обе точки удовлетворяли условиям (2б) с погрешностью Са. В этом случае величина С уменьшается настолько, что точка х становится «недопустимой». Задача линейного программирования заново не решается, но анализ проводится заново, при новых требованиях к точности выполнения условий (2б).
Вышеописанное решение об изменении С основано на следующем простом соображении. Не следует с самого начала требовать очень точного выполнения условий (2б) (для всех промежуточных результатов): это приводит к слишком малому шагу. Точность вы- 428 пРиБлиженные методы Вычислительной Физики 1ч. н полнения условий (2б) должна быть «согласована» с желаемым ходом вычислительного процесса. Если при колебаниях значений ~' в пределах СВ-погрешности происходит монотонное понижение /Р, все «идет так, как надою Конечно, мы могли бы с самого начала задать слишком малое значение С и завысить требования к точности выполнения условий.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
