Ортега Дж., Пул У. Введение в численные методы решения дифференциальных уравнений. Под ред. А.А.Абрамова (1986) (1095855), страница 29

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 29)

Удобно переписать (4.2.7) в виде формул Дх;) г(х;) — Дх;, ) х+,=х; — — ', 4= (4.2.8) 4 ' х; — хг которые, как легко проверить, математически идентичны (4.2.7) и которые лучше использовать для вычислений, так как прн этом происходит меньшая потеря верных знаков. Можем рассматривать величину д1 в (4.28) как одностороннюю разностную аппроксимацию ~'(х;) и, следовательно, рассматривать (4.2.8) как *'дискретную форму" итерационного метода !"(х;) Х;+1 =Х;— (4.2.9) ~'(х;) Этот метод известен как метод Ньютона и является самым знаменитым методом для нахождения корней уравнений (а также, как мы увидим в следующем разделе, для решения систем нелинейных уравнений).

Геометрически метод Ньютона можно интерпретировать как аппроксимацию функции !' линейной функцией Цх) = Дх;) + (х — х;) Г" (х;), х;,, =х(х;), (4.2.10) (4.2.1 !) где я(х) = х — Дх)/~'(х) . 118 график которой является касательной в точке х; к графику ~, н выбор затем в качестве следующего приближения х;+ 1 нуля Ях) . Это интерпретация проиллюстрирована на рис. 4.8. Итерационную формулу Ньютона (4.2.9) можно переписать в виде В общей форме (4.2.10) могут быль записаны и многие другие итерационные методы. Так, например, если положить я(х) = х — аДх), (4.2.12) Ф где а — некоторая постоянная, имеющая тот же знак, что и ~, то получим очень простой метод, который проиллюстрирован на рис.

4.9. Этот метод иногда называют методом хорд. Итерационные методы в форме (4.2.10) называют одношаговыми методами, поскольку х~ ~ зависит только от предыдущего приближениях;. с Гх-х,) Рис. 4.8. Метод Ньютона Рис, 4.9. Метод хорд В отличие от этого метод секущих (4.2.8) использует два приближения, х; и х1 ~, и является примером многошаговога метода. (Обратите внимание на аналогию с одношаговыми и многошаговыми методами для задачи Коши.) Чтобы быть пригодной, итерируемая функция я должна обладать следующим свойством: х' =8(х'), (4.2.13) если х' — корень функции 1'.

Ясно, что для функций (4,2.11) и (4.2.12) это имеет место. (Для (4.2,11) это справедливо, если даже г'(х') = О, хотя в этом случае я (х *) следует определять как предел при х-+х', см. упражнение 4.2.3,) Значение х', которое удовлетворяет условию (4,2,13), называется неподвижной точкой функции я, Теперь обсудим основное свойство., которое обеспечивает сходимость итераций по крайней мере в том случае, когда начальное приближение достаточно близко к х', Будем предполагать, что: (1) функция я непрерывно дифференцируема в окрестности х', (2) выполняется условие (4,2.13) и (3) !К~(х) ! < у < 1, если !х — х' ! < !3. (4,2.14) Согласно известной из анализа теоремы Лагранжа о среднем значении я(х) -я(х') =я Щ(х — х'), (4.2.15) где $ лежит между х и х'.

Отсюда, в силу (4.2.14), можем заключить, что !я(х) — я(х') ! К у !х — х' !, если !х — х' ! < Д. (4.2.16) Предположим теперь, что !хо — х' ! ~ !1. Тогда, используя (4.2.10) и (4.2.13), видим из (4.2.16), что !хв — х ! = !8(хо) — 8(х )! < 7!хо — х ! ° 119 Так как 7 < 1, отсюда следует, что х, лежит ближе к х', чем хо. Таким образом, ! х, — х' ! ~ Р, и мы можем повторить наши рассуждения: !Хт х [~7!Х1 х !~7 !хо х ! или, в общем случае, !хл — х ! ~ 7!хо — 1 — х ! ~ - ~ 7 [хо — х ! ° (4.2.17) с» + й со) + 2 (4.'.19) Теперь можем снова скорректировать зто приближение, подставив его вместо у„„в (4.2.19).

Повторяя эту процедуру, гюлучим последосо) вательность (4.2.20) Ясно„что (4.2.20) — это просто итерационный процесс у„, =я (у„, ), где С~'+г) сс) Иу) = Уа + —. [Х(У) +й1. л Если у~+1 — точное решение уравнения (4.2.18); то, применяя изложенный выше анализ, можем заключить, что последовательность (4.2.20) будет сходиться к уь+1 прн условии, что у„+, (спрогнозированное значение) достасо) точно близко к у„+ и !8 (У) ! !,г (у) ! < 1 в окрестности уь+1.

Если шаг и достатояо мал, то оба зти условия выполняются. Поскольку 7 < 1, то х„- х' при л-+ (предполагаем отсутствие ошибок округления или каких-либо иных ошибок) . Здесь может быть выдвинуто возражение, что условие (4.2.14) нельзя проверить, так как для этого требуется инфо рмация о поведении 8' вблизи точки х', которая нам неизвестна.

Как это ни удивительно, мы, однако, можем получить полезные сведения из предыдущего анализа, даже не зная значения х'. В качестве первой иллюстрации проанализируем приведенную в разделе 2.4 формулу Адамса — Моултона второго порядка для решения обыкновенного дифференциального уравнения у =,) (у). Эта неявная формула дана в (2.4.9) в виде У ° У~+ 2 [йу~.~)+61. й (4.2.18) Мы здесь для простоты опустили зависимость | от х.

Соотношение (4.2.18) можно рассматривать как уравнение для определения у~+ с, хотя в разделе 2.4 мы его использовали только как "формулу коррекции", т.е. прогносо) зируемое значение у„„бьшо вычислено по явной формуле и затем использовано в (4.2.18) для получения нового приближения к уь+1 . В качестве другой иллюстрации использования анализа сходимости рассмотрим метод Ньютона. Предположим, что У'(х') Ф О и что ~(х) дважды непрерывно дифференцируема в окрестности х . Тогда, в силу непрерывности 3' (х), следует, что г" (х) Ф О в некоторой окрестности х', и мы можем проднфференцнровать итерируемую в методе Ньютона функцию (4.2.11), получив У'(х)1' — У(х)у "(х) Лх) У "(х) (У'(х)1' (У'(х ) 1' Так как Ях') = О, то я'(х') = О.

Отсюда, в силу непрерывности я'(х), .Й) й~ ~ и б Рис. 4.10. Примеры "плохогс~'* поведения метода Ньютона: и) ~'(ху) = О; следующее приближение не определено; б) оспиллипии; в) расходимость спедует, что условие (4.2.14) должно выполняться в некоторой окрестности х'. Таким образом, если хо достаточно близко к х', то итерации Ньютона будут сходиться. Мы сейчас показали, что при довольно мягких предположениях построенные по методу Ньютона приближения должны сходиться к корню уравнения, если только хе (или какое. либо другое приближение хь) достаточно близко к х', Теоремы сходимости такого рода обычно называют теоремами о локальной сходимосги.

Хотя эти теоремы и не позволяют , ответить на вопрос, будут ли сходиться итерации прн заданном начальном приближении хо, они характеризуют очень важное свойство, внутренне присущее анализируемому итерационному методу. Если приближение далеко от решения, то при использовании метода Ньютона могут возникнуть различные типы "плохого" поведения итери1ий, которые продемонстрированы на рис.

4,10. С другой стороны, имеются ситуации, когда метод Ньютона будет сходиться при любом начальном приближении. Вероятно, самым простым случаем является тот, когда Ях) имеет нуль, ~ (х) не обращается в нуль, г (х) выпукла, т.е. при любых х н у и любом О < а < 1 выполняется неравенство ,г (ах+ (1 — а)у) ( а~(х) + (1 — а) 1'(у). Если функция ~ дважды дифференцируема, то она будет выпуклой в том и только том случае, если ~ ~ (х) ~ О при всех х. Поведение метода Ньютона при выпуклой функции показано на рис. 4.11, В тех случаях, когда можно гарантировать, что итерационный метод будет сходиться при любом начальном приближении, мы будем говорить, что имеет место глобальная сходимость.

Результаты этого типа обычно требуют наложения очень жестких ограничений на функцию ~, таких как, например, выпуклость, С экономической точки зрения, т,е. с точки зрения затрат машинного времени, вопрос о скорости, с которой итерации сходятся к корню уравне- 121 ния, почти так же важен, как и вопрос о том, сходятся ли итерации вообш . редположим„в соответствии с оценкой (4.2.17), что ошибки ведут себя е. таким образом: 1х' — хи | 1 = 71х' — х;1, 1х' — х;+| 1 < с1х' — х;1', (4.2.21) где с — константа, зависящая от отношения ~ к г вблизи точки х'.

Если последователып |е итерации удовлетворяют соотношению (4.2.21) гово ), то орят, что имеет место квадратичная сходимость. В этом случае и и п и- ближе реднии к корню итерации начинают сходиться чрезвычайно быст~. П положим, например, что с = 1 и 1х* — х|1 ~ 10 ~. То 10 так так о огда х — х|+1 , так что за одну итерацию число верных знаков удваивается, Именно наличие квадратичной сходимости придает методу Ньютона особое значение. рис. 4.11.

Сходимость метода Ньютона в случае выпуклой функции Рис. 4.12. Функция.Г (х) = 1/х + 1п 2 — 2 В качестве демонстрации использования метода Ньютона рассмотрим задачу нахождения нулей функции г"(х) = 1/х+! и х — 2. Эта функция определена при всех положительных х и, как показано на рис. 4.12, имеет два нуля: один между х = 0 и х = ! и другой между х = 6 и х = 7. В табл. 4.1 приведены данные о первых шести итерациях по методу Ньютона при начальном приближении х = 0,1. Обратите внимание, что, как только п иближение оказалось '"достаточно близким" (в данном случае после трех итераций), число верных знаков стало удваиваться после каждой ите а и у вает на упомянутую выше квадратичную сходимость, казы рации, что 122 где 7 очень близко к 1, скажем, 7 = 0,999.

Характеристики

Список файлов книги