Бабенко - Основы численного анализа (947491), страница 108
Текст из файла (страница 108)
5 з4 гл. 2: достаточно, чтобы существовал нейтральный цикл (а, Л(а),..., Л'" (сь))ь д,т которого (Л™)'(а) = ехр(2кьЛ) и Л -- иррациональное число, плохо приближающееся рациональными дробями. Итак, областью сходимостп метода Ньютона является только множество Ц А(-,), где объединение берется по всем притягивающим неподвижным точкам. Заканчивая этот краткий рассказ о свойствах множества 8, отметим такой интересный факт, установленный П. Фату; если Л(-) имеет хотя бы один притягиваюьций цикл, то орбита по крайней мере одной из критических точек Л ь(г) сходится к этому циклу, Скажем несколько слов о структуре множества У.
Предложение 5. Множество У совпадает с замыканием множеспьва отталкивающих циклов нвриода п, > 1. Еющ С й У,,УŠ— множество предшгствепников ь,, ьпо его замыкание У!. = У. Следующее свойство множества У характеризует его свойство однородности. Пусть С произвольная область, и допустим, что У О С = =- У' ф о. Тогда существует целое ьч' такое, что У .— -- Лза(У*). Если коснуться метрических свойств множества У, то нужно прежде всего отметить, что только в исключительных случаях его компоненты могут быть гладкими кривыми. При выполнении некоторых условий множоство У содержит бесконечное число жордановых кривых.
Эти кривые, вообще говоря, не имеют касательной ни в одной точке. Бывают ситуации, когда множество У' полностью разрывно. Пусть г, произвольный простой нуль многочлена р(г). Нетрудно видеть, что существуют круги К =(г; г — г < г,ь2), 1!'(г: - — г ~ < г) 524 Глава 8, Творил игавраиий и лгвтоды рвшышя нвкошорих задач такие, что в круге Л* выполняются соотношения зпр ~ ,'р(з)' ( =. тг, зпр 1ро(х) =.- пгв, т < 2утгпгз. (11) ек' »ек' В силу этих соотношений по теореме 18 гл. 2, если Тии(х) б К при некотором ио, то для всех последующих итераций справедливо Т»ич а(х) Е К; (гг = 1, 2,...), и эти итерации сходятся к х,, причем ~Т о „(х) — - ~ <~ < г .
2 -' . Если хв Е А(в,), то последовательность (Т (зв)) сходится к хо. Пусть р(хв) минимальное целое такое, что Тирад б К . Ясно, что множество А(х;) состоит из объединения множеств А*(х ) и Л»'(А'(в ) ) (г» =- 1, 2,...): (12) Когда о е А(х ) и теоретически последовательность (10) сходится к х„дело осложняется тем, что даже для А*(г,) (13) зпр о(х) =- оо. »ел" ре1 Поэтому при численном исследовании трудно будет отличить факт расходимости от сходимости последовательности (Т,(хв)) при условии, что о(хв) велико. Даже не учитывая наличия множеств вида .4((-а, ..., „г)) (п > Ц, соотношение (13) приводит к довольно пессимистическому выводу, что для успешного решения алгебраических уравнений методом 11ьютона нужно иметь хорошее начальное приближение» т.е.
нужно предварительно хорошо локализовать корни. При вычислениях нас интересует не столько лгножество (12), сколько его подмножество Ак(хо) = (х; х й А(зт), Р(х) < г»»), гДе Х некотоРое фиксиРованное число, скажем»ч = по (»1 > О). Мы можем грубо произвести локализацию корней многочлена р( ) = е" — аг -"'" ~..., заметив, что его корни лежат в круге дв' = (х: Ц < 2 шах ~аь,'гга)» и только из этого круга г«а<в брать начальные данные.
С точки зрения вычислителя, важно, насколько массивны множества А*(з ) Ж', Ам(г ) Л' г — 1 2, »п, (14) н соответствующие множества, огвечаюгцие устойчивым циклам периода и > 1. Другими словами, важно выяснить вопрос о том» будут ли множества (14) и аналогичные нм лля устойчивых циклов измеримыми и какова мера их объединения по отношению к площади круга яц На эти вопросы ответы не известны. 3 а д а ч в 5. Пусть р(х) — кубический многочлеи с тремя различными вещественными корнями.
рассмотрите поведение ньютоновских итераций, 66, Рыисние нслиныпсых уравнений и систем уравнений 525 предполагая, что начальная точка лежит на вещественной прямой В.. Докажите, что область сходимости корня может быть счетным объединением открытых интервалов.
Установите структуру множеств А(( с, г1)), если таковые имеются. Затронутые в этом пункте вопросы более подробно изложены в (129). 3. Теория Штурма. Предыдущие рассуждения показывают, сколь важны проблемы локализации корней уравнения. В том случае, когда все корни мпогочлона (1) действительны, существуют алгоритмы, позволяющие локализовать корни. Из курса алгебры нам известен метод Штурма, позволяющий определить число корней на заданном отрезке (а, 6 вещественной прямой. Пусть р(х) —. многочлен с вещественными коэффициентами, не имеющий кратных корней. Конечная упорядоченная система многочленов с вещественными коэффициентами р(х) — ро( ), ", р.(я) (1о) называется системой Штурма для многочлена, р(х), если выполнены следующие условия: 1) соседние многочлены системы (15) не имеют общих корней; 2) последний многочлен не имеет вещественных корней; 3) если 5 --- действительный корень многочлена рь(х) 6 = 1, '2,...
..., з — 1, то ру. ~(5) и рутс(5) имеют разные знаки; 4) если 5 действительный корень мпогочлена р(х), то произведение р(х)р1(х) меняет знак с минуса на плюс, когда х, возрастая, проходит через точку 5. Пусть с действительное число, пе являющееся корнем мпогочлс па р(х); в послеловательности чисел ро(с), ..., рг(с) вычеркнем все числа, равные нулю, и обозначим через И'(с) число перемен знаков в оставшейся последовательности. Теорема 1 (1Птурма). Если а, 6 —. вещесгавенные числа (а ( 6) и не явлтотсл корнями мпогочлена р(х), то Ит(а) — РИ(6) равно числу вещественных нулей многочлена р(т), заключенных между а и Ь.
Доказательство теоремы Штурма можно найти в курсе общей алгебры. Покажем., что много тен р(х) с вещественными козф4иоиентами, не имеющий кратных корней, обладает системой Шогурма. Положим рз(х) =- р'(х) и тем удовлетворим условспо 4). В самом деле, р'(5) у' О, и если р'(С) ) О, то в окрестности корня 5 многочлен р(х) возрастает и произведение меняет знак с минуса на плюс.
Если р'(с) ( О, то аналогично убеждаемся в справодливости условия (4). Затем делим р(х) па р1(х) и остаток от дгтепия, взятый с обратным знаком, принимаем за рт(х): р(т) =рс(х)Ч (х) —. (х) Если многочлепы рь 1(х), ру(х) уже найдены, .то рь 1(х) будет остатком от деления ру 1(х) яа рь(х), взятым с обратным знаком: рь с(х) = рь(х)уь(х) — рьт1(х). (16) 526 Глава 8, Теория итераций и методы реигегшя некоторых задач Процедура отыскания многочленов ряда Штурма отличается от алгоритма Евклида, рассмотренного в гл. 1, лишь тем, что у остатка каждый раз знак меняется на обратный. Ясно, что наш процесс остановится на многочлене р,(х), который будет наиболыпим общим делителем ъшогочленов р(х) и р'(х). 'Хаким образом, ра(х) = сопгс в силу отсутствия кратных корней, и, следовательно, условие 2) выполнено. Условие !) очевидным образом выполняется: есин рь г(г;) н рь(х) имеют общий корень Г, то он будет корнем и рьз г(х), а значит, и всех последующих многочленов.
Но это невозможно, поскольку р,(х) =- сопга Нз формулы (16) непосредственно следует выполнимость условия (3). Тем самым мы указали алгоритм построения ряда Штурма. Теорема Штурма позволяет производить локализацию корней уравнения (1).
Если )а, Ь, 'отрезок, содержащий нули мпогочлена р1х), то метод деления пополам позволяет произвести локализацию корней. Вычислив Иг((а -~. 6),г2), найдем число корней на отрезках ~а, (ел + Ь)уг2] н [(а вь 6)у'2, 6], которое по теореме Штурма равно соответственно ИУ(ег)— — И'1(а+ 6)гг2) и ИУ((а+ 6)гг2 — Иг(6)). Затем этот пРоцесс пРодолжаетсЯ на тех отрезках половинной длины, в которых содержится больше чем один корень. В принципе таким способом можно локализовать корень с любой точностью, но это не экономно. Лучше локализацию провести грубо, а затем применить один из итерационных методов решения.
Однако такой алгоритм локализации корней будет успешным, если он устойчив по отношению к погрешностям округления. Устойчивость алгоритма Штурма пр<"жде всего зависит от того, как влиякгт погрешности на последовательность Штурма. Этот вопрос выходит за пределы наших возможностей. Отметим только, что в некоторых случаях последовательность Штурма можно строить с помощькг простых рекуррентных формул, н гогда мы полу 1аем высоконадежный метод локализации корней. 4. О точности вычисления корня. Наиболее простым и надежным методом отыскания корня уравнения р(г) — -- О является метод деления отрезка пополам.
При реализации этого метода может быть полезно следующее простое достаточное условие существования корня уравнения. Предложение 6. Пусть а круге К .—.. 1г: г — гс~ < г) производная р'(г) многочлгна (1) отлична от нуля и шах~1(р'(г) < 3,'. Талек гда, если р(гс)~ < ео, бео < г,г2, то в круге имеется решение уравнения р(г) = О.
В более общем случае это предложение 2 З 1 гл. 2, и там же указан итерационный процесс, используемый для отыскания корня. Там же было устаяовлено, что в вещественном случае имеет место более сильное 627 'Зб. Релиение нелинейных урлтгений и систем ураанштй утверждение: если )"(х) Е С [а, 6), , 'г'(х)! > д г при х Е [а, 6), а ! (",'и -'," то на отрезке [а. 6) имеется корень уравнения г(х) = О. Рассхиотрим несколько более общую ситуацию, когда отыскивается решение уравнения 1(гг) =-- О, где 1 С[а, 6), причем 1(гг)((6) ( О. Сложность алгоритма, вычисляющего корень уравнения, мы будем характеризовать временем его выполнения, причем будем считаттч что на вычисление функции нли ее производной требуется единица времени, остальные операции будем игнорировать.
Тогда за г единиц времени можно найгти корень уравнения с точностью г1 < (6 — а)2 (17) Если рассматривать произвольные функции у О С',а, 6| и допускать произвольные алгоритмы, то эту опенку уменьшить нельзя. 3 ад ач н. й. Докажите, что если Т: 'а, 6) К, ~'(х) ( ЛХ лдя всех х е ',а, 6'; или Г(х) > т > О, У(а) < О, Т(Ь) > О, то оценку (17) улучшить нельзя.
7. докажите, что если г'::а, Ь: —. К, О < т ( Г(х) ( й! дпявсехх е (а, Ь), Т(а) с О., Т(Ь) > О, то существует алгоритм, который за г единиц времени вычнслягт корень е тОчнастью (6 — а) [(1 — гггйей ) )2) Ясно, что использование алгоритма деления пополалг не целесообразно для вычисления корня многочлена.
После того как корень хорошо локализован, следует применять какой-либо из итерационных методов. Естественно возникает вопрос о том, как влияют погрешности округления на погрешность, с которой вычисляется корень. Поскольку метод Нютогга, метод деления пополам и другие итерационные методы основаны на использовании значений функции и ее производной, то рассмотрим влияние погреппюстей округления на вычисляемое значение многочлена.
Отметим, что в п. 1 мы рассмотрели вопрос о влиянии вариации коэффициентов на вариацию корней. Предложение 7. Пуегггь р(Г) — регультапг вычисления гначенил мнагачлена (1) при х —.. ~, в системе е тглавающей запятой на основании схемы Гарнергг (ем. и. О З 4 гл. 2). Тогда, если (2п -' 1)е < Ь(1 + Ь), та р(С) =- (1 з- е,)К вЂ” аг(1 — е„ 1)б †' ... -' аг(1 + егД вЂ” а„, где ~е,~ < (22 + 1) е (1 — Ь). Доклзлгкльство. Вычислення по схеме Горнера выполняются в следующей последовательности: находилг Ов =1, г1а г =бйгаг, ег,-г.=.ч Зч г За„г, ..., О„, — -40гг, г Еьа,, г.—.. 3, 4, ..., п.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
