Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
min {max If0'J(x) + f°’J(x) <3jc]}. (14)
6х jSj(x)
Замена (10) на (14) не создает никаких проблем для хороших программ симплекс-метода.
В алгоритме следует пользоваться другим определением множества индексов j(x): j Є j(x), если f°'j(x) > f°(x) — є. По/ґожитель-
432
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИЗИКИ
ное ЧИСЛО 8 должно быть таким, чтобы при переходе ОТ ТОЧКИ X к
X + Ьх не достигался max /0,/(х+ Ьх) при значении у, не входив-
J
шем в /(*)• 8 противном случае вариация Ьх может быть выбрана такой, что шах/°^(х + Ьх) < /°(х), но /°(х + Ьх) > /°(х), и алго-
JeJM
ритм не обеспечивает монотонного понижения /°(х). Выбор є особых трудностей не содержит, так как значительное увеличение є часто приводит лишь к включению в /(х) нескольких лишних индексов, что делает задачу линейного программирования несколько сложнее, чем она могла бы быть.
Более трудные задачи (так называемые минимаксные задачи) возникают при определении /°(х) формулой
/°(х) = max /°(х, у). (1.$)
уЄУ
Здесь существенные сложности связаны с тем, что нужно найти все точки множества
у(х) ” arg max /°(х, _у)« (16)
у
Стандартная ситуация в задачах такого типа такова. Имеется множество у*(х), состоящее из всех точек локальных максимумов f°(x, у) по у. Это множество состоит из конечного числа точек. Их число обычно того же порядка, что и размерность х. Мы ограничимся случаем, когда У — какая-то простая область (шар или прямоугольник, например). Часть этих точек входит в множество у(х), и производная по направлению е от функции /°(х) вычисляется просто:
D(x, е) = max (f°x(x, у), е). (17)
Формула (17) почти очевидна. Единственное обстоятельство, требующее анализа, связано со следующим. При изменении х на малую величину te значение /°(х) изменяется не только за счет изменения значений f°(x, у) на е(/°(л:, у), е) для у Є у(х) (эти изменения учтены в (17)), но и за счет смещения точек множества у(х). Однако эти смещения изменяют величину /°(х + te) на о(є), поэтому на первую производную они не влияют. Причина здесь та же, что и в теореме 2.
Алгоритм поиска минимума функции f°(x) типа (15) отличается от алгоритма решения задачи (12) (когда У есть конечное множество) тем, что требуется достаточно надежно отслеживать множество у*(х), выбирая из него на каждой итерации подмножество у(х). Оно используется При формирований задачи типа (14). При переходе от точки х к близкой точке X 4- 6л; множество у* (х + Sjc) обычно слегка смеща-
ПОИСК МИНИМУМА
433
ется относительно множества у*(х). Однако, в принципе, при этом могут «рождаться» новые точки множества у*(х) и нужно считаться с тем, что до данного этапа процесса программа работала с неполным множеством .у*(х) и значение /° вычислялось неверно.
Проиллюстрируем сказанное выше примером решения следующей задачи (она имеет прикладное происхождение, но мы будем рассматривать задачу как пример):
/°(х, у) = J «р(х) - У) <p{xj - у2), где J-I н
*<2> “5fcSe4> (-iiJr-) Л-
— А ' '
Здесь у = {у1, у2} Є R2, X — {*], Ху}у=і Є Rlj\ область Y — единичный квадрат. В рассматриваемом ниже примере J= 16, Л = 0.1. Кроме того, решалась задача max min /°(х, у). В качестве начального прибли-
х У
жения брались точки Xj Є R2, расположенные равномерно на окружности радиусом 0.1 с центром в центре единичного квадрата.
Расчет начинался с того, что при фиксированном х генерировались случайные точки у Є Y, каждая из которых была стартовой точкой поиска min/°(х, у). Таким образом формировались множе-у
ства у*(х) и у(х). После каждого перехода от х к х + 6х уточнялись положения точек у(х + 6х). Для этого каждая точка у Є у*(х) бралась в качестве стартовой в процессе поиска max /°(х + 6х, у), де-
У
лалось небольшое число шагов подъема по градиенту, т.е. корректировалось множество у*(х + 6х).
Однако множество у*(х + 6х) может быть принципиально неполным. В нем может отсутствовать какая-то еще не обнаруженная точка локального максимума /°(х, у) по у. Поиск таких точек должен продолжаться. Для этого берется некоторое число случайных точек в У, каждая из них используется в качестве стартовой при решении задачи max /°(х + 6х, у). Получающиеся после некоторого числа шагов у
подъема по градиенту точки анализируются. Некоторые из них могут оказаться близкими к точкам, уже входящим в/(х + 6х), они, естественно, игнорируются. Ho некоторые могут оказаться новыми, и тогда они включаются в у"(х + 6х), расширяя его.
Хотя мы ограничились выше общим описанием, не уточняя деталей, читатель не ошибется, если сочтет алгоритм не абсолютно надежным. Это действительно так, и для таких задач практически
434
ПРИБЛИЖЕННЫЕ МЕТОДЫ ВЫЧИСЛИТЕЛЬНОЙ ФИ’ЗПКН
[Ч. II
неизбежен некоторый риск. Мы можем повышать надежность различных элементов алгоритма, но лишь ценой существенного увеличения вычислительной работы, причем полной надежности никогда не достигнем (при конечном числе операций).
Итак, перейдем к описанию результатов вычислений, представленных в табл. 17. Поясним обозначения: v — номер шага по х;
