Бабенко - Основы численного анализа (947491), страница 19
Текст из файла (страница 19)
Тем самым задача о локализации решения уравнения (37) и о выборе начального приближения является основной в теории метода Ньютона. Приведем некоторые достаточные условия существования решения уравнения (37) и некоторые рекомендации по выбору начального приближения. Предположим, что в шаре Т(хе, ге) выполняется условие впр ~( (Р'(ха)] Хга(хЯ вЂ” - ЛХ < со; ет1*а, о) положим д = ~~ (Г (ха)] Р(хе) ~~. Допустим, что 24ЛХ < 1, (43) (1 -1- иг1 — 2аЛХ) б ч ~то 2 (44) При этих условиях ньютоновские итерации будут сходиться. Напомним классический принцип сжимающих отображений. Пусть (Х, р) — полное метрическое пространство, О С Х вЂ” замкнутое множество и Ф вЂ” отображение Ф: О э Х.
Отображение Ф называется саюимаюи1ила если Ф(О) С О и существует такая константа й < 1, что р(Ф(х), Ф(д)) < ор(х, р) Чх, р О О. 78 Глаза, 2. ЛХателлагп ические оснооы числсллиого анализа Предложение 10 (принцип сжимающих отображений) [61., с. 88]. Всякое сжимаюилее олпображение Ф имеет, одну и только одну иеподеижиую точку х. б О: х —. 1ппх, х = Ф(х л) (и = 1, 2,...), хо б О. Быстрота сходимоспли харакгперизуется неравенством р(х, х,) < д"'(1 — д) р(хо, х,). Пусть гл ( гг — корни квадратного трехчлена ЛХегл2 — 1 ' б: 23 (1 — ил1 2дЛХ)) (1+ ллТ вЂ” 2ЛЛХ) М Предложение 11. Допустим, что выполняются условия (43), (44), гл < г.
< ЛХ ', г ( го,. тогда отображение Ф(х) =- х — [Г'(хо)] Е'(х) е шаре Т(хо, г ) яолляется сжимаюилим. Докязлткльство. Проверим, что неравенство [х — хо [ < г,, влечет Ф(х) с Т(хо, г.). Обозначая для удобства [Е" (хо)] через А, имеем Ф(х) — хо = А[Р'(х)(х — хо) — Г(т)]; откуда Ф(х) — хо .=.
— Л [Е (х) — Г(хо) — Е' (хо)(х — хо)] — АЕ(хо) Применяя формулы (36), (31), получим л Ф(х) — хо = — -4 [/ (1 — Г) Г (хо л 16) [6 6] дс — -4Е ( го) = о = - ~(1-- 1)Л[Го(хо Нл)[6, 6]] дг - АГ(хо), о где 6 = х-.го. Отсюда, применяя неравенство треугольника и соотношение (30), имеем (45) [[Ф(х) — хо[[ ~ (р([ Ь[~), где р(1) = ЛХХ'(2+ б. Из этого неравенства следует, что шар Т(хо., л ) отображается сам в себя.
В самом деле, если [,6[ < гн то р([;6[,') < р(гл) .—. гл, если же гл < [6[ ( г*, то, поскольку на интервале гл < 1 < гг, выполняется неравенство р(1) 1 ( О, имеем р([ 6[') < [[6[, :( г,. Отметим, что Ф'(х) .= Х вЂ” ЛГ'(х) = А[Г'(хо) — Г'(т)]. и поэтому в силу форллулы Ньютона — Лейбница и соотношения (31) 1 Ф'(х)6 =- — ~ АГо(хо Х 16)'6, lс Ж, о где /с — произвольный вектор из В. Отсюда [Ф (х)Ь[ ( М[ 6] [[Ь ~[.
При произ- вольных хл, хг б Т(хо, г.) на основании формулы (33) имеем Ф(хг) — Ф(хл) = / Ф'(хл — ' Г(хг — хл))(хг — хл) дг, о 31. Теоремы гаопологип и функционального анализа откуда в силу последнего неравенства вытекает неравенство [[Ф(х ) — Ф(хг)[[ < ЛХг.
~[хг — х,[. По условии ЛХг..—. о < 1, и, зна гит, Ф вЂ” сжимающее отображение. Следствие. Из предлозхеггиб Вй 11 еытекает, что уравнение (37) а.иеегп в шаре Т(хс, г) (г = ппп(го, М ')) единственное решение х,. Модифицироеонньш ньютоновские итерации,.
оыполнлемые по формуле (39), стодлтсл; быстропга сходимости характеризуетсл неравенствами [х„— х. [ < 6(1 — 26ЛХ) Х (1 — (1 — 26ЛХ) Хг), и = 1, 2, В самом деле, чтобы сделать заключение о единственности решения, нужно в предложении 11 выбирать г. максимальным, т, е., если ЛХ ' < го, нужно считать, что г может быть любым числом больше ЛХ '. А чтобы оценить быстроту сходимости, нужно взять г = гг.
Перейдем к скодимосги ньютоновских итераций. Вместо условия (44) введем более грубое: 6 < —. (44') 'Теорема 17. Если вьиголнены условил (43), (44'), то итерации Ньютона, опредсллемые. формулой, (38), сходлтсл к регаснто х ураоненил (37); быстропга сходимости характеризуетсл нераоенсгаоами [х — х '<ЛХ 2 "(2ОМ), п=0,1,. Доказаткльствсь Исследуем переход от хо к хь Для этого оценим величины ог — —. [[[г'(хг)] Е(хг)[[, ЛХг = зир [[[г (хд)] Г (х)[[.
ет(о, Ю Ясно. что хг б Т(хс, го), так как [хг — то [ < го)2. Рассмотрим сначала оператор [Е'(хо)] Е'(хг) = П; заметим., что а силу формулы Ньютона — Лейбница 1 Х вЂ” П = [Е (хо)] [Г (хс) — Г (хг)] = — / [Е (хо)] Е (хо+16)[6, .) 6$, о где 6 .— — хг — хо Отсюда , 'Х вЂ” П [ < М [хг — хо,[ =" оМ, и если 6ЛХ < 1, то по предложению 4 оператор )Х обратим в ,'[(Х [' < (1 — 6М) Учитывая, что 6 —. — [Г'(хо)] ' Р(хо), по формуле Тейлора получим Е(хг) =- Е(хо 6)Е(хо) — Е (хо)6+ /(1 — 1)Г (хо 11г)[6, )г) ей = о 1 (1 1)Л' (хо эь 16) [6 о 80 Глаоп, 2.
Мадиемаглические оснооы числевного анализа Замечая, что [Гд(хд)] = П [Г (хо)], имеем д [Г(хд)] Г(гд) = П ' ~(1 - Х)[Г(хо)] Г(хо — ХЛ)[Л, Л) г(Х, о откуда, используя неравенство (ЗО), получим бд = )([Г (хд)] Г(хд)[! < — ЛХ (П [[Ь!(е < — (1 — 6(1Х) «бдМ, Применяя ту же формулу дзя [Гд(тд)], имеем [Г (хд)] Г (х) =' П [Г (хо)] Г (х), откуда Мд = еир ([[Г'(хд)] Гп(х)([ < (1 . 6М) 'М.
е'г(' о, 'пд дд < —,(1--боМо)' доМ, Мд ~ ((1-.доЛ!о) Мо; 2 а взяв их прОизведЕния, получим (4б) 6(ЛХд < — (боМп) (1 — боМо) 1 г — д 2 Считая, что уже найдены величины хд,..., х„, Определим х„, д и Оценим ЛХ = вир ([[Г (х )] Гп(х)[(, .б =- [х ед — х„! — — ([[Г'(х )] Г(х )((,. гет(го, «и( а также провврим выпалнимасть вклЮчения х, д Е Т(хдд, д'о). Так как переход от х„к х„+д делается в точности так же, как переход от хо к хд, то в силу (4б) 6„< -(1 — 6„,ЛХ„,)-'б'„,М„„М„< (1 — Л„,ЛХ„,)-'М„„(47) 2 если 6„(ЛХ .
д < 1. Мы будем предполагать, что это неравенство выполнено, и покажем, что оно влечет неравенство д„ЛХ„< 1. Поскольку беЛХа < — (6 дЛХь — д) (1 — бь — дЛХп — д) =- 'ф(бп — дЛХ вЂ” д). 2 то, взяв построенную выше последовательность (Хь) при условии (о =- бд(Х, получим бьЛХь < (ь (дс = 1, 2,..., а), и, следовательно, 6„ЛХ„< Х„< 1. Из первого неравенства (47) следует, что 1 бь < — б„-д, 2 1--(„ поскольку функпия Х(1 — Х) монотонно возрастает при О < Х < 1.
Построим последовательность (ть): 1 то = бо, гь.— — — ть д, *де — -- 1, 2, 2 1 — (ь (48) Присваивая индекс О величинам 6' и ЛХ, запишелд последние два неравенства в виде 3 1. Теоремы шопологии и функционального аналиоа !х ч~--хо~ <н(х —;г х !,'т!'х„- х„„.г!т...т!:хг-.хо!'<2 да~~~та. г=о ь=о Покажем, что ч ть < го. Из (48) следуещ что тя = ф~72те и и поэтому я=а зя г„= (2 "И...
! ) И~то. Загрубляя оценку (42), имеем !я < 2 '(2!о), и, зна шт, т„< ЛХ '2 " '(26ЛХ)г . Поэтому тя < 6~ 2 (2дЛХ) < д~ ~(дЛХ) — "' 6(1 — 6ЛХ) < 2д < го. я=о ь=о я=о Сходимость ряда 2", дь влечет сходчлмость ряда ч, (хь г — хь), т. е. сушествоваь=о ь=о ние !!ш хь. Этот предел совпадает с единственным решением х, уравнения (37). Поскольку. х„— х. = 2,' (хь — тнег), то я= ° ,'(хэ, — х,!, '< ~ дь < ~ тя < ЛХ 2 (26ЛХ), и, = О, 1 Эта теорема является бсшее грубым вариантом теоремы Канторовича (см. (5Ц), в которой вместо условия (44') требуется выполнение более слабого условия (44). Приведем еще один вариант теоремы о сходимости итерапий Ньютона, когда известны априорная информация о существовании оператора [г' (х)] и оценка его нормы.
Пусть в некотором шаре Т(у, го) = То существуют [Е'(х)] ', Гв(х) и впр !![г (х)] [! =- гпг < со, зпр [Г (х) ! = япг < оо. ето .я е ц Положим ЛХ = гпг тг. Допустим, что решение х уравнения (37) содержится в То так, что выполнено включение Т, = (х: (х - х,'! < 2ЛХ г) С То.
Теорема 18. Хакова бы ни была точки то Е Т., ньютоновский шперациоаный процесс (38) сходигасл к решению,г, уравнения (37), причем 2'" (.г„- х,), <2ЛХ ~ —,(х, -хо(ч~, п=0,1, (49) Доказлткльство. В силу предположений теоремы точка тг корректно определена,и несложно проверить,что хг — х. = — [К (хо)] (1'(хо) ч'- Х"(хо)(х. — хо)]. В силу построения 6„< тя (!с —.. 1, 2, ..., и). Поэтому, если мы покажем, что ~ х„+г — хо!' < го, то тем самым последовательность (хь)ь, будет корректно определена.Но 82 Глава 2. Математические основы чпсленнвгв апаливв. Обозначим х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
