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