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

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

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

Тогда для уменьшения погрешности на заданной итерации в 10 раз потребовалось бы более двух тысяч итераций. Разумеется, мы бы хотели, чтобы константа 7 в оценке (4.2.17) была настолько малой, насколько это возможно. Но из вывода оце да оценки ( ..16) ясно, что она не может быть меньше, чем 1я'(х')1.

Если я (х ), то говорят, что скорость сходимости является линейной или 'гх'1 Ф 0 геометрической. Напомним, однако, что для метода Ньютона мы показали ! что а (х') = 0 (в предположении, что г ~ (х') Ф 0) . Отсюда, конечно, не следует, что итер|щии сойдутся за один шаг, но это свидетельствует о том, что скорость сходимости имеет высокий порядок. В частности, можно показать (см. упражнение 4.2.4), что в методе Ньютона ошибки удовлетворяют соотношению Таблица 4.1 Сходямоста метода Ньютона для Г(х) = 1/х + 1л х — 2 5,6974149 2,3113878 0,7800322 0,1740346 0,0141811 0,0001134 0,1 0,16330461 0,23697659 0,29438633 0,31576121 0,31782764 0,16330461 0,23697659 0,29438633 0,31576121 0,31782764 0,31784443 До сих пор обсуждение метода Ньютона основывалось на предположении о точном вычислении приближений.

Однако ясно, что ошибки округления или какие-либо другие ошибки неизбежно приведут к тому, что приближения будут иметь некоторую погрешность. Если, например, при вычислении ~(х1) и ~'(х~) были допущены соответственно ошибки е~ и е', то л в качестве следующего приближения хт+1 получим х;„= х; е (~(х;) + е;) е (~'(х;)+ е,.'), где взятые в кружок знаки операций говорят о том, что при вычитании и делении также возникают ошибки округления. Полный анализ влияния этих ошибок очень сложен, если вообще возможен, так что ограничимся только несколькими замечаниями.

Если ошибки е1 и е~ малы, то, пока мы находимся не слишком близко к корню, можно ожидать, что вычисленные приближения будут вести себя примерно так же, как и точные. Когда же значения становятся сравнимыми по величине с е~, вычисленные приближения начинают вести себя иначе. Так, в частности, в случае метода половинного деления мы видели, что когда знак 1 точно не определяется, метод перестает работать, так как может быть неправильно выбран интервал, в котором находится корень. Аналогичная вещь может произойти и с методом Ньютона: если знак Яхг) будетопределеннеправильно, а знак ~ (хг) правильно (естественное предположение, если ~ (х') не очень мало), то значение 7 (х;) / Г (хт) будет иметь неверный знак и следующее приближение сдвинется в противоположную сторону.

Как и в случае метода половинного деления, к методу Ньютона (а по существу, ко всем итерационным методам) применимо понятие интервала неопределенности вблизи корня х'. В гл. 3 мы обсудили вопрос о плохой обусловленности решения системы линейных уравнений. Аналогичная проблема может возникнуть при вычислении корней нелинейных уравнений. Простейший пример такого рода дает рассмотрение тривиальною полиномиального уравнения х" =О, которое имеет л-кратный нулевой корень, и полиномиального уравнения х = е, е ) О, корни которого равны умноженным на е 7" корням л-й степени из единицы, 123 так что все они по абсолютной величине равны е')".

Если, например, и = 10 и е = 10 ' о, то корни второго полинома имеют абсолютную величину 10 '. Таким образом, изменение одного коэффициента исходного полинома на 10 ' приводит к изменению корней в 10~ раз большему. Этот простой пример есть частный случай того общего факта, что если корень х' полинома ~ имеет кратность гп, то изменение коэффициентов Х на величину порядка е может привести к изменению значения х' на величину порядка е .

С помощью разложения в ряд Тейлора в окрестно- 1/юп Рис. 4.13. Большое изменение х ' прн малом изменении ~ а сти х можно показать, что аналогичное утверждение справедливо и относительно функций, которые не являются полиномами. Необходимым условием кратности корня х' является равенство Р ,г (х') = О. Если г (х') Ф О, но ~' (х) мала в окрестности х', то, как показывает рис. 4.13, небольшие изменения,1' могут приводить к значительным изменениям х'. Вероятно, самым знаменитым примером того, насколько плохо обусловленными могут оказаться некратные корни, является следующий. л Пусть ~ — полипом двадцатой степени с корнями 1, ..., 20 и пусть ("— тот же самый полипом, но у которого коэффициент при х'э изменен -гз на 2 ж 10 .

Тогда, с точностью до одного знака после запятой корни л полинома ) будут иметь значения: 1,0; 2,0; 3,0; 4,0; 5,0; 6,0; 7,0; 8,0; 8,9; 10,1 + 0,6(; 11,8 + 1,7г; 14,0 + 2,5 ю'; 16,7 1 2,8г; 19,5 + 1,91; 20,8. Так как коэффициент при х'э в Ях) равен 210, видим, что изменение одного коэффициента примерно на 10 т% приводит к такому большому изменению корней, что некоторые из них даже становятся невещественными! Долг)лнигельные замечания и ссылки 4.2 Детальное изложение теории итер~щионных методов нахождения корней уравнений имеется в книге [80[, превосходный анализ ошибок округления дан Дж.

Уилкинсоном ([82, 841). В частности, Уилкинсону мы обязаны приведенным выше примером плохо обусловленного полинома двадцатой степени. Для отыскания нулей полиномов имеется ряд специальных методов, таких как: метод Бэрстоу для полиномов с вещественными коэффициентами, но могущих иметь невещественные нули; метод Лягерра, обладающий кубической сходимост~ью (т.е.

оценка погрешности вида (4.2,21) имеет в правой части множитель )х — х( ['); алгоритм Трауба — Дженкинса, который имеет глобальную сходимость. В последние годы наметилась тенденция в направлении разработки лолаялгоригмов, которые представляют собой комбинации двух-или более методов. Например, можно использовать метод половинного деления до тех пор, пока приближение не окажется настолысо близко к корню, что метод Ньютона будет сходиться, и после этого для ускорения сходимости перейти на метод Ньютона. Тем не менее вопрос о том, когда переходить с одного метода на другой, оказывается сложным, и для его $24 решения как для этой. так и для других комбинаций методов бьши предложены различные эвристические стратегии.

другая проблема, которая также не имеет определенного решения, заключается в том, когда прекращать итерации. Обычно используют простейшие условия: 1)'(х;) 1 < с или 1х~+1 — х;! < е, где е — некотороезаданноедопустимоеотклонение. Первое условие может ввести в заблуждение, если функция Г вблизи корня уравнения оказывается очень пологой, как ..то имеет место в случае кратного корня. Второе условие может привести к неверному результату в самых различных ситуациях, в зависимости от конкретного итерационного метода.

Например, в случае метода Рис. 4.!4 Ньютона это может произойти, если на некоторой итерации производная окажется очень большой. Эти две возможности показаны на рис. 4.14. УП РА ЖНЕИИЯ 4. 2 4.2.1. Используя теорему Лагранжа о среднем значении (см. приложение 1), покажите, что если функция !' непрерывно дифференцируема и выполняется условие (4.2. 3), то (' имеет на интервале (а, Ц не более одного нуля. 4.2.2. Пусть )'(х) = с х.

Покажите, что, хотя 1'(х) > О при всех х, функция 1' не имеет нулей. 4.2.3. Пусть х* — нуль дважды непрерывно дифференцируемой функции 1', причем )'(х") = О, но 1'(х) ~ О в окрестности х'. Покажите, что в этом случае предел при х х' итерируемой функции х (х) из (4.2.11) существует и равен х'. 4.2.4. Пусть х' — нуль дважды непрерывно дифференцируемой функции 1' и 1' (ха) ~ О. Покажите, что погрешности итераций по методу Ньютона в некоторой окресгности х' удовлетворяют соотношению (4.2.21). (Указание. Разрешите соотношение О = ~ (ха) = ('(х) + с' (х) (х'- х) + 1/21'"(() (х* — х) ' относительно х' н затем используйте (4.2.9) .) 4.2.5.

Рассмотрите уравнение Г(х) = О, где Г(х) = х — х~, имеющее корни О и + 1: а) покажите, что метод Ньютона локально сходится к каждому нз этих корней; б) выполните несколько шагов по методу Ньютона, взяв в качестве начального приближения х, = 2. Проанализируйте скорость сходимостн, которую вы наблюдаете при проведении итераций; в) выполните несколько шагов по методу половинного деления и по методу секущих, начиная с интервала (3(4, 2); сравните скорость сходи- мости итераций в этих методах и ы методе Ньютона; г) определите интервал, дпя которого итерации Ньютона будут сходиться (в отсутствие ошибок округления) к корню 1 при любом начальном приближении х, из этого интервала.

Проделайте то же самое для корней О и — 1. 4.2.6. Рассмотрите уравнение х — 2 з1лх = О: а) покажите на графике, что это уравнение имеет ровно трн корня: О, и по одному в каждом из интервалов (сп2, 2) и ( — 2, — к/2); б) покажите, что итерации хс+~ = 2 з(пхс (1 = О. 1, .

) сходятся к корню нз (к/2, 2) при любом х, из этого интервала; в) примените метод Ньютона к этому уравнению н установите, прн каких начальных значениях итерации будут сходиться к корню нз интервала (л/2, 2). Сравните скорость сходимости итераций Ньютона с итерациями пункта б. 4.2.7. Пусть л — положительное целое и а — положительное число.

Покажите, что применение метода Ньютона к уравнению хл — а = О приводит к последовательности итераций а ха+1 = - Г(и — 1)хя+ 1, в=0,1,..., П ~ .л — 1~ х, которая схолится прн любом х > О. 125 4.2.8. установите, справедливы ли следующие предложения, и обоснуйте ваша выводы: а) пусть (хД вЂ” поспедовательность итераций Ньютона для непрерывно днфференцируемой функции 1; если дпя некоторого ! выполняются неравенства !1'(х!) ! 4 0,01 и ! х!+! — х! ! < 0,01, то х!+з удалено от корня уравнения !'(х) 0 не более чем на 0,01; б) итерации Ньютона сходятся к единсшенному решению уравнения х' — 2 х+ 1' = 0 при любом х, Ф 1 (ошибки округления не у птываются) . 4.2.9.

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

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