Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 64
Текст из файла (страница 64)
Осталось «лишь» найти решение получившейся системы диффергзщнальвых уравнений, используя какой-либо гв численных методов решения задачи Коши. В действительности сведение решения стационарной задачи к решению нестационарной не всегда давг удовлетворитеяьное решение щюблемы минимизации. Осшется еще неясным существенный вопрос о выборе валвчины шагов численного интегрировании. Предположим, что решение несгационарной задачи устанавливается с требуемой точностью к решению стационарной за некоторый промежуток времени Т.
Если внтегри~юЫшие производится с малым шагом Ь, то получаемые расчетные точки будут блвзки к рассматриваемой траектории и можно рассчитывать иа нопцлдвие в малую окрестность точки минимума. Однако при этом число Глава 7. Решение систем нелинейных урвввеияй Рис. 7.5.2 Рис. 7.5.5 шагов Т))Л может оказаться недопустимо болыним (рис. 7.5.2). Если шаг интегрирования берется очень балыпим, то может случиться, что расчет. ные точки начнут сильно отклонятыя от рассматриваемого решения и никогда не попадут в искомую окрестность точки минимума (рис.
7.5.3). Метод установления применим не только к задачам на экстремум функционала, но и к любым стационарным задачам Р(х) = О. Строится некоторый процесс вида (5) или (6), где вместо йгвс(Ф(х) стоит Р(х), и такой, что х(1) -+ Х при 1-+ оа, Х вЂ” корень уравнения Р(Х) = О.
Рассмотрим подробнее случай системы линейных уравнений Ах — Ь = О в предположении, что жорданова форма матрицы дишоналыпш и влв ее собственные значения Л, лежат в пределах О < д < Лл б Лз Ч... ь Л,„< М, где ел,...,е„, — соответствующие собственные векторы, абрвзуюшяе поеную систеллу. Напишем простейшую аппроксимацию метода установления л(х — +(Ах — Ь) = О лй (7) на временной сетке с постоянным шагом х"+1 — х" + (Ах" — Ь) = О. т Сгютветствующая расчетная формул' хв'лг =- х" — т(Ахв — Ь) совладает с расчетной формулой из 5 6.3.
Погрешности г = х" — Х удовлетворяют соатношенило г"+1 = (К вЂ” тА)г". При г" = 1 с,е, име- 1 ем гв = 2,'с;(1 — гЛ1)"ел и скорость убывания погрешности определяется 1 величиной лпах(1 — тЛ (. Там уже было установлено, что наиболее це. д лмхюбразно брать т = 2/(д -1- М), и тогда можно утверждать, что погрешность недет себя как О(((М вЂ” д)/(М+д))в). Метод наискорейшего спуска можно также рытыатривать как аппроксимацию метода устано- 2 б. Решевяе стационарных юдач путем установления аления, лю уже па сетке с переменным шагом: х"+1 = х" — т„(Ах™ — Ь); !наг т„определяетса «аждый раз из условия пппФ(хвтг).
Рассмотрим аппроксимацию метцца установления 1Рх ах — +7 — + (А — Ь) =О вйг Аг на временной сетке с пОстоянным шагом ха+1 — 2х +х 1 х +! — Хв 1 +7 +(Ах" — Ь) =0; тг 22 0 ( у — скзлярнмй л!ножитель. Погрешности г" удовлетворяют соотношениям г"~' — 2г" + гв ' г""' — г' ' +7 2 +А™ О. (8) тг 2т Разложим векторы г" по собсгвепныы векторалл матрицы А: — с; е,. ы! с + — 2сз+с" св+ — ср +7 *' * +Л1~=0. .г 2т Решения этих разностных уравнений злпнсывакпся в виде Св = ~С(2() + ~С(В ) если з1л, зг--простые корни характеристического уравнения 2 — 22Ф1 2 — 1 г 2 + 1 — ФЛ2=0, т2 2т (9) и в виде ! 1 1( *)в ! 1 2 ( ')в если корень (9) кратный. Во всех случаях определяющим фактором убы- шп!ия ((г"(( является величина пил(пшх((з1(,(221()), которую можно ма- жорировать сверху величиной !пах (2(Л)(, «<хйм (10) где 2(Л) — максимальный по мцзулю корень уравневия 2 — 2л+1 2 — 1 + 1 +Ля=О.
22 2т подставим выражения г" 1, г'*, г"+! в (8); поскольку векторы ел не- зависимы, то коэффициенты при них обращалпгся в нуль и получается система соотношений 350 Глава 7. Решение систем иы|инейных уравнений мы не будем приводить полного решения загпюи на экстремум (10), а ограничимся наводящими сгюбражениями и выписыванием ответа. При хг = хе-1-сг(Ах" — Ь) приближения х записываются в виде (6.6.2). Поэтому рассматриваемый итерационный процесс не лгожел дать лучшего приближения, чем оптилгалыпяй липегшый итерационный процосс (6.6.19).
При и -т оо оптимальный линейный итерационный процесс пе. реходит в итерационный процесс (6.6.23), который с учетом явного «ырвжении Лс = (1.~- л/д/М)/(1 — ь/д/М) может быть записан в виде Е ь г лМ вЂ” //11 ь ь, 4 х + г =. х -1- — (хь — хь 1) — (Ах" — Ь). (11) ь/М+ /д/ (-ь/М/+ /р)г Можно подобрать т и 7 гак, чтсбы июрационный процесс совпадал с расстнатривгюмым. Ддя этого следует взять 2 2л/Лг/р т= 7= ъ/И+ 7 ЪЯХ+ Р Таким образом, в рамках схемы установления с постоянным у можно получить итерационный процесс, несуществеНно отличюощнйгя от Оптилгэльного линейного процесса. Обратны внимание на поведение корней «(Л), соответствующих (П); имеем характеристическое уравнение Запишем это уравнение в виде ' — А(Л)х г- д, '= 0, де = ( /М вЂ”,//г) /( /и+ /д) Здесь А(Л) — линейная функция от Л,'причем А(М) = — 2ре, А(р) = 2де. Следовательно, (А(Л)) < 2до при р < Л < М.
Поэтому хпг(д) = дш А(Л) /А(Л)'1 гцг(М) де хдгР) — х ~ — ! — д именгт ненулевую мнимуто чж:тъ и /хг г(/г)( =" де п1ли /г < Л < М. Таким образом, указала совокупность кснффициента 7 и шюа т, для которой )з(Л)( = (ъ/М вЂ” Я/(ъ/М + рг). в<л<м Неулучшаемость этой опеиви усматривается из оценки скорости сходимости оптимального линейного итерациоююго процесса. 4 5. Решение стационарных задач путем установления Как аналог метода сопряжешгык градиентов в случае минимизации функционала Ф(х) общего вила можно рассматривать следующий метод. погледуютцие приближения ищутся в виде х" =х +о„(х" — х" ')+Д,йгат(Ф(х"), о„и Д, определяются из условия шш Ф(хм).
Осответпгвие ыежлу методами решения стационарных задач путем установления и обычпыл1н итерационными лтетодвми позволяет строить новые итерационные методы или новые процессы установления. Рассмотрим, например, расчетные формулы Ньктгонв хжш — хв =- — (Еч(хв)) Р(хв) (12] рыления системы нелинейных уравнений Р(х) = О. Этны форьтулал~ ыожно дать слцлующую ивтерпретацню: нведем непрерывное время 1 н будем рыхматривать величины хм как чнатепия некоторой функции в молтенты времени 1„= и.
Тогда оютношение (12), переписанное в ниде = — (Р'(х")) Р(х" ), можно интерпретировать как получитапгася при аппроксимации системы — = — (Е'( )) Р( )- (1 (13) Решение исходной задачи являеття стационарной точкой этой системы. При х = Х + т1 имеем (Е" (х)) ' = (Р'(Х)) ' Ф О()(т1)(), Р(х) = Р(Х) + г'(х)т1+ ОЦт1)) ) = Е'(Х)т1 Ф ОЦт1)( ). Таким образом, -,1 = $ =- — (( '(Х))щ РО(И()( '(Х)ц+ОЦМ))з)) = = — 1+ О(()ц())'). Отсюда следует, что х = Х является асимптотически устойчивым решением (13). Заменяя производную ох/тй рэзностным отноглением по зтшченяяьт ФУнкции в некотоРых точках 1е = О, П,..., полУчаел~ соотношениЯ х +г — х" Лн = — (Ет(Х")) Р(Х"), т3 = 1 Ы вЂ” йн виаче, х"+' = х" — 1„(Р'(х.))-тр(хв).
(14) Глава й решение систем нелш1ейиыт уравнений Таким абразалг, построение нестационарного процесса, соответствующего метгду Ньютона, привело нас к получению итерационного процесса (14) более общего вида. Рассмотренный пример показывает, что переход аг некото1юго иъера. циопного алгоритма к соответствующему ему нестационарвому процессу имеет много общих черт с построением замыкания вычисленного алгоритма (понятие замыкания алгоргпма будет введено в гл.9). Нами была доказана скодимость метода Ньютона лшпь при достаточно хорошем начальном приближении к решению.
С целью расширения области скодимости иногда прибегают к следующей модификации метода Ньютона. Задшоъся функционалолг Ф(х), например ()Р(х)~)ъ, нижняя грань которого, рввиан нулю, достигается при решении задачи. Последовательные пРиближениЯ отыгкивеютсв в виде (14), пРичем Глн опРедевиетсЯ из условия ш1пФ (х — Ь (Р'(хн)) ги(х")) . Возникает вопРос о пРактическом нахожДении величины 21ю пРи котоРой достигается этот минимум. Одна из распрастраненнык процедур определения Ь„сошоит в следующем. Задавая Л б (0,1), 0 б [О,Ц и 1 > 0 — целое, при каждом н последовательно вычисляют х" +г" = х" — Л'(Р (х")) 1Р(х"), л = 0,...,1, и 0"'гй = Ф(ъй+гй). Если при некотором й <1 оказалось д"лгл < ОФ(хв), то вычисления прекращшот и полшшаг х"+ = х"+1л; в других процедурах ггажщят пйп дилл' =- О" л|л' и полагают х"лг = х"ъ~ш. е<гй~ Если д +г,е д Ый > ИФ(х ) то возможны, например, такие варианты: 1) временный переход к друюму лгетсду; 2) осталовюь; 3) изменение значений параметров 1, Л, О.
Отметим в заключение, чъа мштды установления могут применнтьгл и в случае минимизации функции в областях с ограниченияыи. Тогда уравнения (1), (3) следует дополнить какими-то уравнелгиями, коюрым будет подчиняться траектория точки, попавшей иа границу. З 6. Как оптимизировать? После выбора модели, целевой функции и парамеъризвции задачи возникает задача минимизации функции обычна большого числа переменных в области, пришлдлежность к которой задавгся условием выполнения большого числа ограничений — равш~ств или неравенств. Наличие оъраниче- в б.
Квк оптимизировать? внй существенно унеличивает сложность задачи минимизации: как правило, точкой экстремума оказывается некоторая граничная точка области. Вследствие большой важности решения задач оптимизации для самых взличных сторон жизни общесгва, в нщтоящее время накопился больдой башж методов и стандартных программ решения задт оптимизации Поэтому при решении единичной конкретной задюги часто наиболее оправдано обращение к одной нз имеющихся стандартных программ. При решении попых задач оптимизации полезно помнить о следующих моментах. Для рассматриваемых в этой главе методов сховиыогть приближений всегда доказывалась в предположении наличия достаточно хоРошего начш~ьного приближения. Это ограничение на метод вызываетгж существом дела.
Так, поверхность уровня ьпюгочлсна умеренной сзапонн „т умеренного числа переменных может содержать весьма ыпою нс связанных между собой компонеггг со свожпыы взаимныьг расположением. Псвтому, например, бтнадежно рассчитывать на построение юпоритмв, позволягощего быстро найти минимум лгобого многочлена восьмой степени от десяти переменных. Вышесказалшое гледует учвтывать прв использовании стандартных программ, в описании которых указывается на возможность минимизации функций очень большого числа переменных. В лучшем случае оказынавгся, что: а) программа эффективно решает задачи минимизации из класса, с которым автор программы обычно нмпгг дело, или б) программа, формально говор», может решить любую задачу минимизации, но требуемое для решения время в подавляющем числе глучаев выходит за всякие разумные пределы.
Мы придерживаемся точки зрени», что всякий унвеерсальный» метод решения ыногожернмх зова г мпнижгтоггпп долэкеп облооопгь сущестеенпымп педосгпатжьнп и е дейстептсльпостп не леллстсл йявэерсальньиг. При решении новых задач зачастую приходится разрабатывать специальные, приспособленные именно для этого класса задач, методы отыскания начального приближения к регпениго. Сложность отыскания пригн илемого ыачщ~ьного приближения можно проиллюстрировать следующим примером. Существует ряд стацвартных программ наилучшего приближения функций отношением многочленов Рж! )Я,,)з) щцанных степеней т и и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
