Федоренко Р.П. Введение в вычислительную физику (1185915), страница 102
Текст из файла (страница 102)
Здесь Ь„Ьз — первая и вторая строки матрицы В, (а), „= а(х, у). 464 пгиелиженные методы вычислительной»изики 1ч. и Выше были опущены некоторые несложные технические детали, обеспечивающие условия йт(х, у) + Ьт(х, у)й ж Дх, у). Все это превращается в конечномерную задачу линейного программирования, матрица которой схематически изображена на рис. 54. Поясним ее: Ф есть число узлов в области гг (в расчете Н- 800), ггго— число узлов в гг, (на разных этапах расчета лг 300 . 600), Ь, — элементы матрицы В, рассматриваемые здесь как четырех- индексные матрицы (первая пара индексов ьо4 из О, вторая — из б,). В правой части мата, кы вь, о Рицы стоит РазРеженный блок 6Но х ЗН«, состоящий из коротких (по шесть элемен- 4 " " .
тов) строк, расположение которых показано Гчв О на рисунке, Ясно, что такая задача сама по себе практически непосильна для БЭСМ-6, а ее Рис. 54 предстоит решать много раз: на каждой ите- рации. Поэтому был использован прием, известный под названием «агрегирование неизвестных». Он состоит в том, что ячеики сетки Ьхл объединялись в блоки НхН, где Нж (3+ 4)Ь, например, и все переменные считались постоянными в каждом блоке. Иными словами, процесс проводился не на основной Л-сетке, а на более грубой Н-сетке. Это приводит к существенному сокрашению размеров задачи (до 360 неизвестных и 120 условий), Вышеприведенная громоздкая методика использовалась попеременно с методом регуляризации. Когда последний переставал работать, делалась одна итерация с применением линейного программирования, которая «сдвигала» точку т( ) со стационарной для метода регуляризации ситуации.
Снова применялся спуск по градиенту с регуляризацией, и т.д. В конечном счете было получено приближенное решение с такими характеристиками: В = 0.026, У„„, ж 0.15, причем только в семи узлах (из 800) значение 2 попадает в интервал [0,1, 0.15). Что касается затрат машинного времени (на БЭСМ-6), то первый этап стоил 25 мин, а в целом расчет занял 2 ч 15 мин. Это был один из первых расчетов, в процессе которого отрабатывалась «стратегия» проведения вычислений. В дальнейшем время подобных расчетов несколько сократилось. То, что было описано выше, представляет вторую, видимо, попытку решения задач подобного рода (она осуществлялась автором), если, конечно, не считать типичных в механике приближенных решений, основанных на тех или иных упрощающих предположениях, априорных гипотезах о решении и т.п.
Подобные решения оказываются удачными в той мере, в какой оправдываются такие гипотезы. Первый опыт решения задачи о качении в ма- 485 9 291 в«гилнионные з«дАчи мех«ники Метод двойственности. Опишем основные моменты другого подхода к решению неклассических вариационных задач, в котором используется так называемая двойственная формулировка задачи. Вычислительные алгоритмы такого рода разрабатываются группой математиков, возглавляемых Ж. Лионсом. Одним из первых приложений этик методов было решение задачи Бингама. Применительно к ней мы н будем вести изложение.
Итак, требуется минимизировать функционал Г(и( )) вида (3). Основной момент нижеследующего состоит в замене недифференцируемой функции ЗЦ Д вЂ” некоторый вектор) решением специальной задачи на экстремум, сформулированной в терминах только гладких функций. Нетрудно проверить, что 1Я = шах (р, Ц). 1»1 «4 (11) тематически замкнутой форме был предпринят И. И. Калькером. Он использовал несколько иную форму минимизируемою функционала и, соответственно, другие алгоритмы. Результаты его расчетов были проконтролированы решением по вышеизложенной методике.
На рис. 55 показаны данные сравнения решений одной задачи двумя разными 'методами. Показаны графики функций тз(х, О), 52(х, О). Линия у= 0 является линией симметрии, в силу которой т,(х, О) = 8,(х, О) = О. Решение Калькера изображено штриховой линией, решение по вышеописанной методике — сплошной.
Хотя в целом, качественно, картины близки, можно отметить явные, видные даже на глаз дефекты «штРихового» РешениЯ. Там, гДе 52 ««О, Должно х быть тз — — /5/~~ 58. Сплошная линия точно следует этому правилу: знак т меняется точно в том Рис. 55 месте, где гз проходит через нуль. Штриховая линия явно нарушает это правило точного решения.
Нарушено условие задачи 8тр ц / (примерно на 11 %). Нарушен и второй «закон»ч там, где 8 21! < ~, обязательно 5 = О. Вычислительные методы математического (в частности, линейного) программирования возникли, развивались и применялись в первую очередь в связи с внедрением математических методов в зкономические теории, Поэтому многие считают их некой «экзотикой», интересуюшей весьма узкий круг специалистов. Большинство физиков, механиков и представителей других естественных наук этих методов не знают. Между тем н в этих областях в последние годы все чаще возникают задачи, настоятельно требующие применения именно таких нетрадиционных алгоритмов.
484 нгнвлнженныв методы вычислительной «нзнкн (ч. п Очевидно, максимум достигается при р= ЩЦ[. Используя (11), задачу (3) можно переформулировать следующим образом: «2+«з ш!п $ $ (-" — х + шах (р, н (х, у)) — аи(х, у)) (Кх оу, «(') о 1( Р!! «( Р(х У) = [Р( Рз] н' = (и„и ]. Первый шаг в дальнейших преобразованиях имеет целью вынести операцию взятия максимума по р за пределы интеграла, т.е. осуществить преобразование ~ ~ вах (р(х, у), в(х, у)) ((х Иу = вах ~ ~ (р(х, у), н(х, у)) д>х д>у. г г('> о (12) Справедливость его почти очевидна: обе части (12) достигают максимума при р(х, у) = ы(х, у)/[[(«(х, у)][ н оба значения интегралов в (12) при этом совпадают. Следую(ций шаг — перемена порядка операций взятия минимума н максимума.
Определим функционал р от двух аргументов: Р[и( ° ), р( ° )] ш ]])) ( — [[и«[[з+ (р, н) — аи) с(х Иу. (1З) с Итак, надо использовать преобразование (п1п вах Г[и(. ), Р( ) [ = вах ппп Р[и(. ), Р( ) ]. (14) «( ) г( ) р( ) «( ) В общем случае ппп вах и вах вш. Перестановочность этих операций возможна только прн специальных свойствах Р[и, р].
В.нашем случае Г, очевидно, линеен по Р и выпукл (вниз) по и. Этих свойств достаточно для справедливости (14). Теперь определим функционал Ф[р( )] пнп Р!и(.), Р( )]. «( ) В терминах Ф исходная задача сводится к задаче вахФ[р( )], г( ) где Ф, однако, определен не явным выражением, а каким-то алгоритмом решения «внутренней» задачи на пнп по и( ).
Так как в дальнейшем предполагается искать вах Ф методом подъема по градиенту, то нужно уметь вычислять не только Ф[р( ) ], но и его градиент. Начнем с вычисления Ф[р( )]. Если в (14) убратыпах по р (считая р(х, у) заданной функцией), то минимизация функционала по а 291 влуилпионвыв злдлчи мвхлиики и( ) есть достаточно хорошо изученная вариационная задача, обобщающая задачу Дирихле. Ее решение сводится к решению относительно простого уравнения (уравнения Эйлера для вариационной формулировки) Ли+ д)у р+ а = О, и[,с = О. (15) Это уравнение получается стандартнмм способом. Подставляя в (13) вместо и возмущенное и + Ьи, разлагая подынтегральное выражение в ряд по Ьи (отбрасываем члены второго порядка), интегрируя по частям (учитываем, конечно, что Ьи = О на дО), получаем для первой вариации функционала выражение: ЬР[и( ), Ьи(.)[ = — ~~ (Аи + б>т р+ и) Ьи ~1х Ыу, т.е.
левая часть (15) есть производная Фреше для Р[и(.) [ в точке и( ). Уравнение (15) так или иначе решается, и для вычисления Ф[р( ) [ имеется аффективный алгоритм. Перейдем к вычислению цронзводной Ф. Проварьируем задачу, обозначив и(, р( )) = агя шш Р[и( ), р( )). ,«( ) Тогда можно написать «явное» выражение: Ф[р( )[ =Р[и(., р( )), р( )[. Дифференцируя его, получаем ае<р< В ар а«<,р< » + ар ар( > = а«< ) ар< ) + ар(.)' Здесь нас выручает то обстоятельство, что а ( ) =О в точке и(', р(')). Позтому сложный и практически трудно вычисляемый обьект— производная и(, р(.)) по р( ) — нам не нужен. Что же касается производной от Р[и( ), р( )[ по р( ) в точке и(, р(.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
