Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 90
Текст из файла (страница 90)
рис. 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б) должна быть «согласована» с желаемым ходом вычислительного процесса. Если при колебаниях значений ~' в пределах СВ-погрешности происходит монотонное понижение /Р, все «идет так, как надою Конечно, мы могли бы с самого начала задать слишком малое значение С и завысить требования к точности выполнения условий. Эту ситуацию можно распознать по слишком малой величине »1 (шаг Я слишком мал, точность линейного приближения излишне высока). В этом случае значение С несколько увеличивается. Ограничимся этим не очень строгим и не исчерпывающе полным описанием.
Стремление к точному описанию алгоритма затруднило бы понимание основных идей. Здесь же мы ставим целью не безупречность описания, а подго'- товку читателя к знакомству с более точным изложением. Для иллюстрации сказанного выше приведем пример решения не очень сложной модельной задачи. Она входит в набор тестов, принятых для оценки фактической эффективности алгоритмов. Задача имеет следующий вид (! = 1, 2, ..., 5): !р 5 5 5 У!1(х) = — ~ Ь,.х, + ~ ~Х; с1.х,р,.х, . + 2~Х' д,.х!р н 1=! !=1! 1 1 1 !р 5 2 1 ! Кроме того, поставлены условия х! в О (1 = 1, 2, ..., 15). Таким образом, мы имеем в задаче 15 неизвестных и 5 условий- равенств.
В качестве начального вектора берется х! = бО, остальные х1 = О. Требуемая точность выполнения условий определялась числами е! = 1О 5, С = 1ОВ, 5 = 1.3, Значения параметров, входящих в выражения для функций, можно найти в известной монографии Д. Химмельблау «Прикладное нелинейное программирование» (см. задачу 18). Процесс решения задачи иллюстрирует табл. 1б. Поясним обозначения: т — номер шага (итерации); г = шах Д'(х') ( — характеристика погрешности выполнения условий (1= 1, 2, ..., 5); 5— шаг варьирования„«1 — характеристика погрешности линейного приближения; к — число вычислений функций /! (вычисление 21 для каждого отдельного ! увеличивает счетчик К на единицу). Каждый шаг процесса стоит примерно шести вычислений 21, !'„'.
На некоторых шагах приходится повторять вариацию меньшим шагом; поэтому К 1.35 (У+ 1)В, Прн В = О условия (2б) выполнены с допустимой на данном этапе погрешностью. Эта погрешность есть !О при »< 32. После 325й итерации допустимая погрешность 8 гб! 429 поиск мИИИМ7МЛ есть 0.45, после 4!-й — 0.02, после 6!-й — 5.!О ". Фактическая точность заметно выше. Расчет требует около минуты работы Таблица 16 буо дуо БЭСМ-6, причем половина этого времени тратится на вычисление У и их производных, половина — на решение задач линейного про- граммирования. Решением является точка х = 10, О, 5.17278, О, 3.06138, 11,83698, О, О, 0.10337, О, 0.30007, 0.33342, 0.400!3, 0.42823, 0.22397).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
