Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 63
Текст из файла (страница 63)
Таким образом, исходная задаЧа минимизации функции т переменных свелась к минимизации функции одной переменной, каждое значение которой определяется минимизацией функции (щ-1)-й переменной. В свою очередь мяиимизацию функЦии Ф„,(х, ) сведем к минимизации фуиции одной переменной, каждое Глава 7. Решение систем нелинейных уравнений значение которой определнется минимизациея функции от (ш — 2)-х пе- роменных, и жд. Получим цепочку глотношений А =- плиФ„,(х„,), Фш(х ) =- ншгФ г(х„, г, х„,), — \ Фг(хэ,..., т.,) =.
лннФг(хг,..., хв,), Фг(гг,..., т,) =шшФ|(ги..., и,). Кажущейся простоте меп>да сопутствует его болыпвя трудоемкость. Предположим, что каждая минимизация функций одной переменной потребует вычисления в значений минимизируемой функции. Тогда минимизация Ф (т. ) требует нахождения ппп Ф„, 2(тв, г, т,) при в значениях параметра х „т.е. в вычислений значений функции г Ф о(т„, и х ). Это в свою очередь потребует вычислении л зваге- 2 ний Ф„, 2(х„, г, хю г, хе,) н т.д. В ковечном счете потребуегтя вы гисление е значений функции Ф. Уже при умеренных в и ш, например в = 10, гл = 10, такой объеы вычислений окажется недопустимо большим. Однако при малых гл некгнорьге модификации рассматриваемой идеи оказываются полезными.
Например, возможен такой вариант. Задаются начальным приближением (хег,..., те,). Реализуют уквзагшый алга- ритм при не очень болыпом значении в, например е = 3 или и = 4. При этом значения функции вычисляются в точках некоторого параллелепипеда )хг — хе( < 42~.
Получаемуго точку минимума (х',..., т' ) принимают за следующее приближение; приближение (хг,..., лг ) находят аналогичным образом, но значения функции Ф вычислюотгя в то*псах параллелешшеда )х, — х,') < гл,' и т.д. Рассмотрим еще один метод, общая структура которого похожа на структуру опигжнного выше. Если линии уровня функгши Ф похожи на сферы, то при применении методов спуска происходит быстрое смел(гение в направлении минимума (рис. 7.4.1). Опнако практически более типичен глучай, когда эти линии похожи на эллнпсоиды с больпгим разбросом полуосей. Тогда при движении по градиенту смещение в направлении точки минимума будет довольно менленным (рис. 7.4.2). Предположим, что оси этих «эллггпгоидов» естественным образом разбивавугси на две группы: первая группа ггютоит нэ тг осей одного порядка и относительно малых, вторая гругша состоит из лж осей одного порядка и относительно больших.
При решении некоторых задач такого рода хорошо зарекомендовал себя следующий метод, называемый ыеиюдоы оврагов. Задаются какимито приближениями хе и х и производят ншжолько шагов метода опус" ка, исходя из каждого из этих приближений. Будут получены прибли- 343 $4 Другие методы сведения Рис. 7.4.2 Рис.
7.4.1 х' Рис. 7.4.4 Рис. 7.4,3 жения Хе и Х'. И! рнс. 7.4.3 видно, что зти приближения будут лежать в многообразии, расположенном в окрестнгсти осей второй группы. П1юцесс итераций состоит в получонии послгдовательныя приближений Хо, Х,..., лежагцих в окрестногти этого многообразия. В случае !пз = 1 приближение Х'+' отыскивается следующим образом. Проведем через Х' ! и Х' прямую и найдем приближение х" ! к точке ьжнимума Ф(в) на этой прямой. Таким образом, это приближение ищется в виде х'+! = Х! 1- о(Х! — Х! !).
Далее щюводнм несколько итераций исхгщя из х!+! и получаем цри5лижение Хм~, также лежащее е аврам. В случае гпз > 1 приближение иногпа удобно отыскивать в вгще !+! х!т! = Х! .!- О(Х! — Х! !) -~-,0 йгаб Ф(Х ). нз рис. 7.4.4 вцдно, что описанный способ оказывается эффективным н н ряде случаев, когда линии уровня функции Ф(х) иьгеют боаее сложную ИРУк хУР1. Глава 7. Решение сивым велинейвык уравнений Решение системы уравноний Яхы...,х )=О, 1=1,,ш (2) [[хм...,х )=О, г'=2,...,ш, (3] относительно неизвестных хэ,..., х . Пусть хт(хг),..., х (хг) — ее решение. Г!сдставлвн выражения хз(хг),..., х (х~) в первое из уравнений (2), получим уравнение Р~(хг) = уг(хы хт[х~),..., х (хг)) =- О (4) относительно одной неизвестной хь Отыскание значений хэ(хг),..., х„,(хг) и решение уравнения (4) люжво проводить численно. Выбирается какой-то метод решения (4) по значениям функпии Р(хг); при каждом требуемоы значении хг в рвультате решения (3] получаютсв знюгенив хз(хэ),..., х„,[х~), которые подгтавлвзотсв затем в правую часть (4).
Для решения системы уравнений (3) при каждом значении хг прилэеним тот же приель Пусть хз(ты хэ],..., хж(хы хз) — решение систеыы уравнений Л(хм..., х„) =О, 1=3,..., чп, (5) относительно неизвестных хэ,..., х . Подставляя хэ(х„хз),..., х,(хн хз) во второе уравнение системы, получим уравнение Рт[хг хг) = [з(хы хж хз(хы хт), °, х, (хы хг)) = О.
При каждом хг это уравнение может быть разрешено относительно хг. Его решение хэ(хг), а также хэ(хв хт[х~)),..., хм(хы хэ(хг)) сбржзуют решение системы (3). Систему (5) при каждых хм хз опять решаем, сводя в системе, где число неизнестныт па единицу меньше, и т.д. Если для решения каждого вспомогательного уравнения с одной неизвеопюй потребуется э вычислений функций, то суммарно этот алгоритм потребует порядка э'" вычислений правых частей уравнений системы. По поводу реального применения этого алгоритма можно сказать все то же, что в по поводу применения описанного в начале параграфа мехада минимизации. Зццача 1.
Рвссмотретгч во что переходит описанный метод в случае, ко- гда система уравнений (2) линейная. также формально сводитсв к последовательному решению уравнений с одним негывестным. Рассмотрим систему уравнений 345 З б. Решевие стэционарнь1х задач путав установления 3 5. Решение стационарных задач путем установления 4х — .~-бтаб Ф(х) = О. 41 Вектор Их/Й пропорционален градиаггу функции Ф(х), т.с. ортогоиален ее линиям уровня и направлен в сторону убывания значений функции Ф(х).
Таким образом, при перемещении вдоль траектории системы (1) значение Ф(х) не возрастает. Формально справепливость этого утверждения следует из неравенства — = (угабФ(х), — / = -(рабФ(х),йсвбФ(х)), (2) 4Ф(х) / 4хй а ~ 41) означающето, что 4Ф(х)/Ж < О всюду, за исключением стационарных точек функции Ф(х). Друсой нестационарный процесс, решение которого при весьма общих предположениях устанавливаетсв к точке минимума функции Ф(х), описьшаеты системой дифференциальных уравнений 4зх 4х — + у — + йтаб Ф(х) = О, у > О. сйз (3) Зля решений этой системы имеем (4) 1 /4х 4х'~ если только йх/41 ф- О. Функцию Ф(х) в первом случае н — ~ —,— / + 2 1 41 ' 41 ) Ф(х) — во втором можне рассматривать как энергию материальной системы, движение которой описывается системами уравнений (1) и (3).
Соотношения (2) и (4) показывают, что рассматриваемые нестационарвые пуюцессы характеризуются оттоком или, как пуворят, дпсоипацпей шврсии. распространенным методом решения ссациоиарных задач является метод уссваиоелеиил. В этом случае дпя решения стационарной задачи строится нестационарный процесс, решение когорого с течением времени оказмвэется независилсым от него и устанавливается к решенюо исходной стационарной задачи. Рассмотрим сисселсу дифференциальных уравнений Глава 7.
Решение сисхем нелинейных уравнений Чтобы прояснить вопрос о разумном выборе у, раесьягтрим проошй. ах шую модель: х — скаляр, Ф[х) =; тогда (3) приобретает вид 2 х +ух+ах=О. Ссютвьтогвугощее характеристическое уравнг ние Л +'уЛ+аз = О, его корни Лг г = — 4 (( — — аг, и при Лг ф Лг, т. е. прл у ф 2а общое 7 г 2 )(4 Решение есть ау ехР(Лгг) -~- сеехР(Лгг). Скорость убывания решений рассьгатриваеьгого уравнения определяет.
ся величиной о(у) = шах(КеЛО КеЛг). При у < 2а имеем уг/4 — аг < О, и поэтому КеЛг .— — КеЛг = о( у) = — 712 > — а,. При у > 2а величины Лг и Лг вещественны и КеЛг = — + )( — . — аг > КеЛг = — — — г ( — — аг. )( 4 Тогда (7) = К Л, = --+ г,у — — г = 7 7 'УУ 4 а » — — — а. / г 7 — 4 — — аг 2 )'4 Таким образом, график г( у) имеет вид, а изображенный на рнс.7.5.1, и т)па(7) = о(2а) =- — а.
Из рюулыатов рвссмотреу ний этой лгодельной задачи можно сде- лать следующие качественные выводы. (2а,— а) 1. Если коэффициент трития у очень мал (в нашем случае у « 2а), то решение Рис. 7.5.1 системы (3) медленно устанавливается к положению равновесия; при этом (вследствие условия 1шЛг, )шЛг Р О) происходят колебания около положения равновесия. 2. Если у велико (у » 2а), то решение также медленно устанавлива ется; причина состоит е том, что при большом коэффициенте трения 7 лвижение не может приобрести большой скорости. 3 б. Решыше стационарных задач путем установления 3. Оптимальное значение г лежит где-то посередине и зависит от свойств конкретной функции Ф(с). Метод установления с помощью решения системы (3] иногда называ,от методом вшжелого шарика.
Это название обусловлено следующими соображениями. Рассмотрим движение материальной точки по поверхности р =- Ф(:г) в поле тяжести, направленном в отрицательном иапренвспии оси у. Предположим, что трение пропорционально скорости и точка иг может отрываться от поверхности. Тогда ог движение опишегся систелюй уравнений Азх Их ~раг(Ф(х) ДВ Д~ 1 + )) бгаб Ф(х)))з Ясно, что регпенве этой систегеы с течением времени усгановится к некоторой стационарной тачка функции Ф(х).
Вблизи экстремума )(огас(Ф(х))~ << 1 этв система близка к система (3). Большинство известных мопедов уссзновления описывается уравнениями вида дх1 сбс I Ах Ае (х, — ( — + Аг ~х, —, р-ж) Ф(х)) = О 'а( й ~'й' (б) Ве (х, — ) — + В1 (х, —, бган Ф(х)) = О, (б) где Ае(Х о) Фо А1(Х,о,о] = о, в (х,о) Фо, в (х,о,о) =о и выполнены условия ди«сипативпосги, обеспечивающие сходиыость к точке экстремума Х. Вообще говоря, можно обратить операторы Ае и Ве и преобразовать эти уравнении к виду, где Ао и Ве — южцествеиные операторы. ()днако исходная форма записи часто пракгически удобнее. Может показаться, что построение таких нестационарвых процессов, устававливающихся к решению, уже полностью решает проблему огысканиа минимума функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
