Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
К методу модифицированной функции Лагранжа можно прийти и из других соображений. Минимизируем функцию F(x, А) со слабым штрафом. Пусть х(Л) = arg min F(х, А). Тогда, как уже отмечалось, fl(x(A)) = г і Ф 0. Введем «невязки» гг в конструкцию (8) заранее. Используем простое соображение. Если введение штрафа А смещает
§ 26] поиск минимума 425
точку минимума на расстояния попробуем решать с этим же штрафом А задачу с условиями /‘(х) + гп надеясь, что новые условия будут выполнены С теми же погрешностями ГI в точке х(А):
fl(x) + ri = ri, т.е. /'О(Л))=0, г =1,2, 3, ...
Итак, новая штрафная функция будет такой:
/
F(x, А) = /°(х) + Л 2 Ift(X) + гJ2 =
I = I
= f°(x) +A^ Ui(X)]1 + ^ ArJi(X) +A^r].
Значения г і берутся с предыдущей итерации, Ari играют роль множителей Лагранжа Xi. Последнее слагаемое, очевидно, можно опустить.
Метод линеаризации. Вторая основная вычислительная конструкция, которую удалось довести до сравнительно эффективных алгоритмов, связана с одной из фундаментальных идей вычислительной математики. По традиции ее связывают с именем Ньютона. Задача линеаризуется в окрестности некоторого уже найденного приближения к решению, и следующее, лучшее, приближение находится решением линеаризованной задачи.
Пусть х — некоторое текущее приближение к решению задачи поиска условного экстремума. Следующее приближение ищется в виде х + Ьх, где Ьх — «малая» поправка, которая решает линеаризованную задачу
min {/0О) + /°0) dx} (10)
6х
при условиях
а) FJ fl(x) + f‘x(x) Ьх Ft, і = I, 2, ..., I,
(И)
б) Sn ** П = I’ 2> •••> N-
Числа s~, s* определяют «шаг» процесса. Задача (10), (11) является хорошо изученной задачей линейного программирования, для решения которой давно разработаны достаточно надежные алгоритмы (так называемый симплекс-метод). Эффективность конкретного алгоритма существенно определяется тактикой подбора шага (s~, s+), которая, конечно же, должна опираться на информацию, получаемую в процессе решения задачи.
Опишем основные технологические элементы метода линеаризации, разработанного автором в начале шестидесятых годов и применявшегося в существенно более сложной ситуации (подробнее об
426
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
[Ч. II
этом см. в § 28). При организации вычислений нужно избежать двух опасностей:
при слишком малом значении шага процесс протекает надежно, но медленно;
при слишком большом значении шага пренебрежение квадратичными членами становится необоснованным и процесс перехода от хк х + дх становится бессмысленным.
Итак, шаг должен быть максимально возможной величиной, при которой линеаризация функций обладает достаточной точностью. Это качественное соображение предстоит превратить в алгоритм подбора шага в зависимости от фактического хода вычислений. Введем параметры, управляющие процессом решения.
а) Числа ег (i = 1, 2, ..., I) определяют заданную постановкой
задачи точность выполнения условий (26).
б) Число 5 (шаг процесса) входит в алгоритм генерации чисел
s~ = O(S), s* = 0(5). Учет условий (2а) очевиден.
в) Число С в начале процесса — достаточно большое число (С = IO3-S- IO5). В процессе решения задачи это число автоматически меняется и стремится к единице. На данном этапе поиска решения в условиях (26) допускается погрешность Cer
Стандартный шаг алгоритма состоит из следующих операций.
1. Пусть уже получена точка х, выработались какие-то числа 5 и С.
2. Задача линеаризуется, т.е. вычисляются значения /'(*)> производные /'Х(х) и числа s~, s*. Таким образом, задача (10), (11) сформирована.
3. Решается задача (10), (11). При значительных нарушениях в точке х условий (26) задача может и не иметь решения. Алгоритм обнаруживает этот факт и переходит к определению дх с целью минимизации
г(6х) = 2 1Г(х) + Рх(х) бдс]?,
; = !
где
W\. = {I о} — FJI, а‘ < Fj; \a‘ — Ft\, а‘> Ft; иначе 0}.
Другими словами, игнорируя значение/0, мы стремимся получить так называемую допустимую точку х, в которой с требуемой точностью выполнены все условия. В любом случае получается вариация Ьх.
4. Вычисляются вариации функций bfl = fx Ьх и (после вычисления значений /'(х + Sjc)) их приращения А/' = /'(х + Sjc) — /'(*)•
5. После этого начинается логически наиболее сложная операция — анализ и принятие решений об изменении управляющих параметров. Выделяются характерные ситуации, в каждой из которых реализуется свое целесообразное поведение.
ПОИСК МИНИМУМА
427
5.1. Пусть точка х недопустима, т.е. [f‘(x) I, > Cti хотя бы при одном і. В этом случае вычисляется погрешность линейного приближения тг] = max I (6/' — Afi)/Afi |. При этом максимум вычисляется
(Э 1
лишь для тех индексов, для которых условие нарушено и в новой точке X + 6jc, т.е. \fl (х + 6х)], > Czl. В зависимости от значения т] изменяется шаг 5 для следующей итерации. Если т]« 0, шаг S увеличивается; если тг] SK 1, шаг 5 уменьшается. При определенных обстоятельствах (г(6х) > г(0)) итерация «отменяется», шаг 5 уменьшается (например, вдвое) и задача линейного программирования решается заново.
