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