Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 102
Текст из файла (страница 102)
Более точно это означает следующее. В начальном приближении среднее значение 1, 2 максимальное значение 1„,„, 5. В конце расчета (при Рж0.18 в большей части области для 1 0.0002 . 0.002) пгиклижкннык мктолы вычислительной бианки !ч. н 482 1,р 0.027, У„а„, = 2.2, Имеется небольшая подобласть в б, в которой значение функции 1!х, у) достаточно велико, причем вместо требуемой в точном решении коллинеарностн в и 3 наблюдалась почти антиколлинеарность этих векторов. В этот момент с.ь эанима- Таблица 21 ла значительную часть гг и никакие ухищрения в рамках описанной выше мегодики не приводили к улучшению решения.
(Впрочем, как показали дальнейшие расчеты, для грубых выводов часто бывает до- статочно и полученного таким образом решения.) 0 ! 2 3" 3 5' 5 б 7* 7 В 9 9 !О 11 гг 13" !з 14 15* 15 16 !7 г! 25 29 33 ! 3.83 4.83 3.46 !.772 1.772 0.988 0.864 0.864 0.477 0.4! З 0.4! З 0.307 0.268 0.268 0.24! О.237 0.229 0.212 0.21г олюг О. !97 ОЛ97 0.193 0.19! одвб О.1В4 Онзг 0.18! 10.8 6.0 4.2 З,б 1.8 1.1 !.3 0.67 0,35 0.43 о.гг ол! О.! 5 0.075 0.058 0.072 0,052 О.О45 0,023 О.О1З 0.017 О.ОО9 0.0056 0.0064 0.0029 О.ОО!7 0.0009 0.0005 8.8 !.36 1.69 -0.46 олв олз — 0.002 0.39 0.064 -О,О!В ол! 0.039 -О.О25 0.026 0.004 0.008 0.0! б -0 0014 о.о! ! 0,005 -о.оо! О,ОО4 олюг 0.00! 0,0006 0.0005 0.0002 о.ооог гг 27 гг гг 11 11 8.6 4.3 4.3 3.5 1Л !.7 !.7 0,86 О.вб 0.69 055 0.55 0.28 0.28 О,гз 0.14 ОЛ4 0.14 0.07 0.036 0.029 о.огз ВАРИАЦИОННЫЕ ЗАДАЧИ МЕХАНИКИ 483 Для того чтобы получить более аккуратные и достоверные результаты, пришлось существенно усложнить метод.
Метод линейного программирования. Этот сложный алгоритм мы опишем в самых общих чертах. Ои основан на некоторой аппроксимации приращения недифференцируемого слагаемого Г, более простым, ио тоже недифференцируемым. Используется возможность аппроксимировать круговой конус, как поверхность в трехмерном пространстве (С, В, ~ф+ цз), шестигранным конусом (г„ть Ф(С, ц)), где Ф(г„д) определяется решением следующей задачи линейного программирования: ФД, В) = 054 ш!и (а'+ а" + р'+ р«+ у'+ т") «',...Н« при условиях ('-')М+(2//ЗНК-а") =В, -Е'-К')+( '-Т") =Ч, (а' — а") + (р' — р") + (у' — у") = О, а', а", р', р", у', у" в О.
Не будем доказывать этого. Читатель, желающий понять, в чем тут дело, пусть начнет с вопроса о том, почему ) Ц = ппп (а'+ а") при а' — а" =ч, а ~0, а'вО, Используем введенную аппроксимацию конуса. Введем, кроме Ьт(х, у), новые вспомогательные переменные а'(х, у), ..., /"(х, у), (х, у) ~ С,. В терминах этих переменных задача выбора направле- ния спуска для недифференцируемого функционала ставится следу- ющим образом. Требуется найти Ьт(х, у), а'(х, у), ..., У«(х, у), обеспечивающие ппп ((~ (/З(х, у), Ьт(х, у)) Их Иу+ с + 0.54 ~ ~ /(х, у) (а'(х, у) + а "(х, у) + ... + у" (х, у)) Их а~у) о, при условиях з,(х', у') — ~ ~(Ь,(х — х', у — у'), Ьт(х, у)) с(х Ыу— с — «а' — а")/Л + (2/з/З)(р' — Д"))„, „, = О, зз(х, у ) — ~ ~ (Ьз(х — х, у — у ), Ьт(х, у)) Фх ну+ + «~'-Д") — (у — у"))„ч, =О, «а' — а") + (р' — р«) +(у' — у«))„, „, =О, т'(х', у') Е с . Здесь Ь„Ьз — первая и вторая строки матрицы В, (а), „= а(х, у).
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}
