Самарский А.А. Гулин А.В. - Численные методы (1078412), страница 39
Текст из файла (страница 39)
Воспользовавшись формулой Ньютона — Лейбница, получим ао Р(го) = г (2,)+ ~ г'(г) Йг, а, т. е. с (,) = ~ (» — «,))а( )Па. а Для этого сделаем в интеграле (32) замену переменной 2 = (га+ (! — 1) 2 и перепишем его в виде ! г'(го) = (го — 2.)" ~ 1)а ((го + П вЂ” 1) 2,) г((. (32) (33) Имеем 2 — 2 =((2„— 2), )2 — 2 (~()га — 2 («Г, т.
е. 2=(г,+(1 — 1)г е=(),(2), и согласно (25) выполняется оценка ))" ((2,+(1 — 1)г.) ) =М,. Отсюда и из (33) получаем оценку 1 ! Р' (го) ~ = .1а(о ! го — г„)о ')' 1Ш = 0 5 Ио ! го г )о о Учитывая (31), получим неравенство )г — - )- Л(о ~ г„— г, )а Фа 'а которое совпадает с неравенством (27) прп Ь.=). Предположим, что оценка (27) выполняется при )о=1)1, и докажем, что она выполняется и при 1=1+1. Заметим прежде всего, 206 Р (го) = ~ (2 — 2,) 1 (г) а(г. (30) а, Докажем оценку (27) по индукции.
При )о=0 из (29) получим 21 — г, = (31) 1 (го) Так как 2,~(7,(2.), имеем согласно (25), что ))'(2,)) = та О. Далее, оценим что из оценки (27) при А=! следует. что г~У,(г,). Поэтому согласно условию (25) имеем !!"'(г) /)лг,>О. Далее, оценим гч г (г~) = ~ (г — г ))" (г)Лг, л~ Учитывая, что г,ен(l,(г.), можно получить оценку этого интеграла гак же, как и оценку г (г,), а именно ) г (гг) (( — "(г, — г,!'. Тогда из (29) при 7г=( получим Мэ1г, — г. р (г~м — г )~~ 2м, и, учитывая (27) при !г=(, придем к неравенству (27) при а=!+!.
Теорема 5 доказана. Заметим, что условие сходнмости (26) означает близость на комплексной плоскости начального приближения г„ к искомому корню г, В частности, зто условие может не выполняться для вещественных начальных приближений. При численной реализации метода Ньюзона можно пользоваться комплексной арифметикой, однако иногда бывает удобнее разделить в формулах (24) действительные и мнимые части н проводить вычисления только с вещественными числами. й 4. Итерационные методы для систем нелинейных уравнений !.
Общие понятия. Рассмотрим систему нелинейных уравнений бг(хохм ..., х„,) =О, ~,(х„хз, ...,.;„) =О,' („(хн х,, ..., х, ) = О, где 1„(=1, 2... т,— функции вещественных переменных х,, ..., х„,. В дальнейшем систему (1) будем рассматривать как операторное уравнение в некотором линейном пространстве Н размерности т. Обозначим х=(х„х„, х„) ~Н, г(х) =(7,(х), ),(х)...., 1„,(х)) и запишем (1) в виде операторного уравнения (. (х) =О, (2) где г: Н- Н вЂ” отображение, нелинейное, вообще говоря, пз Н в Н.
Звт т,+,— числовые параметры, В„„— матрица гп,'эг',гп, имеющая обратную. Если Р— линейный оператор, то (3) совпадает с канонической формой одношагового итерационного метода (см. й ! гл. 2), т. е. в виде (3) можно записать любой одношаговый метод дли линейной системы уравнений. В случае нелинейной системы (!) возможны методы, содержащие новую итерацию х"+' нелинейно, и тем самым не представимые в виде (3).
Однако мы по-прежнему будем называть канонической формой запись итерационного метода в виде (3). Для нахождения х"+' по известному х' из уравнения (3) необходимо решить систему линейных алгебраических уравнений В„ ,х"+' = а (х"), (4) где й(х')=Вь.„х' — те„р(х'). Метод (3) называется явным, если Вь,,=Е для всех Й=О, 1,..., и неявным — в противном случае.
Метод (3) называется стационарным, если В и т не зависят от номера итерации Й. Систему линейных уравнений (4) можно решать либо прямым, либо итерационным методом. В последнем случае итерации, приводящие к решению системы (4), называются внутренними итерациями, а итерации (3) — внешними итерациями. 2. Сходимость стационарного метода.
Остановимся кратко на вопросе о сходнмости метода (3). Предположим, что метод (3)— стационарный, т. е. В и т не зависят от Й. Тогда уравнение (3) можно переписать в виде (б) х"+'=5 (х"), а исходное уравнение (2) — в виде х=5(х), (6) где 5(х) =х — гВ 'Е(х). Будем считать, что Н вЂ” конечномерное линейное нормированное пространство, т. е. что определен функционал 1)х~1, удовлетворяющий всем аксиомам нормы.
Точка х.гн!Н, для которой 5(х,) =х„называется неподвижной точкой оператора 5. Очевидно, что точка х. является решением операторного уравнения (2) тогда и только тогда, когда она является неподвижной точкой оператора 5. Таким образом, отыскание корней уравнения (2) эквивалентна отысканию неподвижных точек оператора 5. Говорят, что 5 является сжимающим оператором на множестве К=Н, отнр)тз, зи,г.сч,! цзпп существует число д~(() 1) такое .
пли я зцог « гн черавенство г" 11 аоа Многие одношаговые итерационные методы для решения си- стемы (2) можно записать в виде Вм, +Р(хз)=0, Й=О, 1, ..., хззадан, (3) „ззт „з таь1 где Й вЂ” номер итерации, з з з т х = (х„ км ..., х„), Теперь мы в состоянии сформулировать теорему, которая называется принципом сжимающих отображений и содержит условия сходимости метода простой итерации х*"' = 5 (х') (7) в конечномерном линейном нормированном пространстве Н.
Она является многомерным аналогом теоремы 1 из $ 2, Теорем а 1. Пусть оператор 5 определен на множестве Р„(а) =(хе-:Н: Пх — аИ~г) где 5(х) =х — тр(х). если !!5'(х,) !1(1. П данном случае 5'(х) = Метод сходится, =Š— тр'(х) и дй (х) дх, д(е (х) дх, дй (х) дх,„ д/, (х) дх дй (х) дх.
дВ (х) дх г'(х) д( (х) д(„, (х) д(., (х) дх| дх, дх П р н м е р 2, Метод Пикара. Пусть Р(х) представляется в виде Р(х) =Ах+6(х), где А — матрица т,к',т. Тогда итерации можно определить следую!цим образом: Ах"+'+6(х") =О. х09 и является сжимающим оператором на атом л!ножесгве с коэффициентом сжпгия д, причем Ц5(а) — а!)((1 — д)г, О~у(1. (8) Тогда в Г~„(а) оператор 5 имеет единствеяную неподвижную томку х и итерационный метод (7) сходится к х при любом х'~ енб',(а). Для погрешности справедливы оценки !!хх — л,((~ ух!(хь — «А!!, (9) (! м ~~ ч ~~5(хь) хю|~ (10) ! — д Доказательство теоремы 1 можно найти в (42). 3.
Примеры итерационных методов. П р и м е р ! . Метод релаксации представляет собой частный случай метода (3), когда В,,=Е, т,,=т. Это стационарный итерационный метод, который можно записать в виде х'+'=5(х'), Итерационный метод можно переписать в виде А (х' ' — х") +Е(х") =О, т. е. в канонической форме (3) с В„,=Л, т,„,=!. Можно и здесь ввести итерационный параметр и рассматривать более общий метод х х' — х А " ' +Е(х')=О. т 14 р имер 3.
Магог) Ньютона для системы уравнений (1) стро- ится следующим образом. Пусть приближение хх=(х~ х,, ..., х ) уже известно. Выпи- шем разложение функции 1,(х„х„..., х.,) по формуле Тейлора в точке х", х х х х д((" ! и ~г(хо хм ° ° ° ю х~~) =~'~(хо хз ., х,х1+ (хг — х,) ' + дх, Фг (х ) х дг, (х'-) +(хх — х) + ...
+(х,„— х,„) +0(!х — ха)х), дх. ' дх„, и отбросим величины второго порядка малости. Тогда система (1) заменится системой уравнений д!г 1') 'Я (х; — х;) ' +!';(х")=О, г=1,2,..., т, (12) /=1 линейной относительно приращений х; — х";, /=1, 2, ..., т. Решение х=(х„х,, ..., х )' системы (12) примем за следующее приближение н обозначим через Таким образом, итерационный метод Ньютона для (1) определяется системой уравнсний '~ ~(х;" — х;) — '+Г',(хх1=О, (=1, 2,..., т, (13) д); Гх~) дх.
/ =1 / из которой последовательно, начиная с заданного х' = (х'„...,х,', ), находятся век1оры х", й=!, 2,... Систему (!3) можно записать в векторном виде Е'(х") (л'ы — х')+Е(х') =О, й=О, 1, ..., х' задан, (14) где матрица Е'(х) определена согласно (11). Таким образом, метод Ньютона имеет канонический вид (3), где В„,=Е'(х"), т,,=!. Для реализации метода Ньютона необходимо существование матриц (Е'(х')) ', обратных Е'(х"). По поводу сходнмостн метода Ньютона для систем уравнений можно сказать то же, что и в слу. 210 чае одного уравнения, а именно, метод имеет квадратичную сходимость, если начальное приближение выбрано достаточно хорошо.
Приведем без доказательстве одну из теорем о сход!о!ости метода Ньютона. Пусть Š— множество т.мерных вешественных векторов с нормой !с!х!1= гсх',!!Л!! — норма матрены А, подчниенная пенной норме векторе. ли С/ , ! =1 Обозначим (С,(х') =(хшЕпч !!х — х'!)<г) и предположим, что в шаре С',(х') функпни [,(х), с=1, 2, ..., т, непрерывно дифференпируемы. Те о р е м а 2. Предположи.и, что в Г„(х') матрица Е'(х) удовлетвг!ряет условию Лсспшица с постоянной С, т. е. !1Е' (х' ) — Е'(хь) !! ( Е !! х' — х! !! для любых х', хтсмО,(хь). пусть в (с,(хь) матрица (Р'(х))-' существует, причем элементы вв непрерьсвны и [!(Е'(х))-с)(~М. Если начальное приближение хь таково, что !)Е(хь) ))(т) и МЧл~ ,1 = ч причем Ыт) '~~Р д! ! ( г ь=! та система уравнений (2) имеет решение х.снК(хь), к которому сходится л!етод Ньютона (14).
Оценка погрешности дается неравенством еэ, !! хч — х !! ( Мс) ц ь Доказательство теоремы 2 можно найти в [42). П р н и с р 4. Л[одсссссссцированньсй метод Ньютона имеет вид Г'(х') (х" ч! — х') + Г (х') = 0 (15) и обладает линейной сходимостью. Упрощение в численной реализации по сравнению с обычным методом Ньютона состоит в том, что матрицу Е'(х) надо обращать не на каждой итерации, а лишь один раз. Возможно циклическое применение модифицированного метода Ньютона, когда Г'(х) обращается через определенное число итераций. П р и и е р 5.
~Метод Ньютона е параметром имеет вид х ' — ч Р'(х') ' + Г(х') = 0. тем Рассмотренные до сих пор методы являлись лннейными относительно новой итерацви х"". Возможны и нелинейные методы, ког- да для вычисления х'+' приходится решать нелинейные системы уравнений. Приведем примеры таких методов. П р и м е р 6. Нелинейный метод Якоби для системы (1) имеет вид ь Ф ь кг.г д ьг Гг (х„х„..., х, „хг, хо о ..., х,„) = О, г=1,2,..., пг. (17) Здесь для отыскания х"' необходимо решить пг независимых скалярных уравнений. Для решения скалярного уравнения можно применить какой-либо из итерационных методов, рассмотренных в $ 1, причем не обязательно применять один и тот же метод для всех уравнений. П р н м е р 7.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
