Бабенко - Основы численного анализа (947491), страница 109
Текст из файла (страница 109)
528 Глава 3, Творил исавраций и методы рвшвиин ивкоторих аадач Тогда с1о = р(б). Учитывая формулу (1.2.8), получим с1а с —.— (Яда .,тз(1 — сс„) --:- ас~(1 бс), где,,:а,~ < с, '6,, '< в. Поэтому р(8) = Аос" —, ... — А„сс т А„, где А, — а,(1+5„)(1 а,.„л)(1+5, з)...
(1-ров)(1+О„). Отсюда в силу соотношений (2.4.12), (2.4.13) А, .—. а,(1 + с,), где в, < (2г + 1)(1 —, ,Ь)сз что и требовалось. сз Если 8 -- корень мпогочлепа р(х), то погрешность может быть значителыюй, поскольку (18) р® = еЯ", алев зс" +... + асз, звзб — ' а„, а коэффлшиенты а ъсогут быть большими. В п. 1 мы наблюдали на примере многочлена 2 затзТи(2х — 1), что хотя корни и лежат на отрезке (О, 1,з коэффициенты мпогочлепа велики. Если воспользовспься тождеством сова лиссоз(2х — 1) = сов2н х х атосов лсх и заметить, что сов 2н агссов лсх = получим, что сумма модулей коэффициентов многочлена 2 "т Т„(2х— — 1) равна 2 "" '( — 1)" сов 2п атосов ъГ.-Т = ((1+ лсс2) с2) за + ((лс 2 — 1)с2)ва, т.е.
зкспоненциально велика. Отметим, что зто имеет место и для полиномов, отличных от 2 з"нзТ„(2х — 1). Для многочлена р(х) степени и, удовлетворяющею на (О, 1 опенке р(со)~ < 1, типичная оценка суммы модулей коэффипиентов имеет внд 2,' ~ао~ .= С", где С ) 1 —. некоторая а=о константа. Это, как уже отмечалось выше, связано со свойстволс переполненности степенного базиса.
Поэтому целесообразно, .если многочлен р(х) задан в явном видо своими козффициенталси, перейти к другому базису, скажем из многочленов Чебышева, используя при этом арифметику многократной точности. Тогда в — з 1 р(х) = ~ ~сздТ (х) + — сза, 2 о=о 'Зб. Реиимие. нсаинейных Лратшний и систем ураеаптй 829 и в силу равенства Парсеваля (см.
гл. 2) 1 2 Г рв(х) и и / а=о Е".ели на ( — 1, !] выполнено неравенство ,'р(х), ( ЛХ, то получим границы для коэффициентов о . Вычисление значения многочлена в форме (19) или его производной выполняется по схеме Горнера (см. п. 6 З4 гл. 2) и основано на рекуррентной формуле, которой удовлетворяют ортогональные многочлены. В нашем случае — это формула (2Л.о2). Анализ погрешностей округления и в этом случае производится как и выше, и для погрешности значения многочлена получим формулу, аналогичную (18), в которой вместо а нужно подставить ою а вместо Са подставить Та а(С).
Ясно, что погрешность в данном случае будет намного меньше, чем раньше, и вычисления можно делать с одиаеарной точностью. Наличие погрешностей округления приводит к тому, что для каждого корня уравнения р(х) =- О будет существовать область неопределенности, внутри которой лежит вычисляемый на ЭВМ корень.
В самом деле, рассмотрим для конкретности метод Ньютона, и если приближенное значение корня ха близко к искомому корню, то, поскольку мы вычисляем хьт1 по формуле хат1 = хабр(хь)Вр (хь), где р(хь) и р (хь) вычисляемые значения многочлена и его производной, в силу формулы (1.2,8) получим хьз1 = (хь — (1 — и),, 1(1+о1), р(х„) -т (бр)(ха) 1 р'(хь) - (бр'Н ь)" где (др)(хь), (бр')(хь) погрешности, сделанные при вычислении соответственно р(хь), р'(ха), а ка(, (сс1( < е.
Отсюда, если искомый корень равен С., получим хат1 — ~ —.— р(х ) (бр)(х )ф(х ) ( . )(б с)(, )„ 1( ) р'(хь) р'(хь)(р'(хь) + (бр')(хь)) где р(х ) (бр)(хь) р'(хь) + (бр')(хь) Используя формулу Тейлора, получим О = р® = р(à — хь - хь) = р(хь) — (с — хь)р (хь) э р (хь), (ь — ха)з „- где ххв — некоторая точка, лежащая между точками х = С и х = хю 530 Глава д, Теория иеаерачий и методы решеаия иекоторих задач Отсюда хьт1 — б = (хь — 4)'Ро(ха) (бр)(хь)Р'(хь) — Р(хь)(бр')(хь)1 1(1 — п1) + Ъ.
2Р'(ха) Р'(хи)(Р'(хь) + (бр')(хь)) (20) (че х )зро(х ) ( Р'(хь) где 1--. |исло разрядов, используемых при представлении чисел в системе с плавающей запятой, то хь з — С будет определяться величиной (бр)(хь)р'(ха) — Р(ха)(бр')(хь) (бр)(хь) ти — (1 т ее1) + пи = , †, ць = Р'(хь)(р'(хь) + (бр')(хи)) Р'(хь) (бр)( ь) р(хь) бр(хь) Р'(С) ' Р'(хь) Р'(С) Таким образом, область неопределенности корня в основном определяется погрешностью, которую мы делаем при вычислении значения много- члена, и числом обусловленности корня.
Чем больше число обуслов.пенности, тем обширнее область неопределенности. Когда хь попадает в область неопределенности корня,.при дальнейших итерациях не будет происходить уточнения приближенного значения корня, а соответствующие знаки в представлении хая г в виде двоичного числа будут изменяться, следуя капризам погрешностей округления. и-. — 1 тз( ь — ь)1 1 ха ... гьб где -ь —. -ь...„ В(еь г, ..., вь) = 5. Метод секущих.
Некоторые иторапионные методы решения уравнения д'(е) = 0 основываются на следующем соображении. Допустим, что мы знаем значения 1(еь,) = (ь „, ..., д (хь) = дь. Построим ьеногочлен й(г) степени г, принимающий в точках ид значение 1 (д = .—.- й — г, Л вЂ” г —, 1,..., й). Корень зат1 многочлена й(-), ближайший к -ро принимаем за очередную итерацию корня уравнения г(з) =- О.
Таким образом получаем итерационный процесс отыскания корня. Система функций 1, з, ..., з" в любой области е-сферы образует систему Чебышева, так как многочлен о„"+... + ое имеет не более г различных корней (см. и. 3 3 1 гл. 3). Этого свойства достаточно, чтобы записать иптерполяционный многочлен в виде 'гб. Решение нсаинейння уравнений и систем уравпешлй 531 В самом деле, легко проверить непосредственно, что д(е) —.
искомый многочлен, а кроме того, это следует из результата задачи б п. 3 3 1 гл. 3. При г — — 1, 2 легко проделать все вычисления, и мы получим соответственно гу-~Уь — еьХь-г'( г — ев — г) [2(А- — уь) + Хл г гь-2 — = Ь вЂ” г ь — г ге гь д(х)— ел †г 2 2 гь-1 " " г г ь 2 е/ 2 яь-1 г иь ее — 2 Мы не будем двлыпе преобразовывать выражение для д(-) при г=2. Отсюда получаем, что при г = 1 единственный корень многочлена д(г) дается формулой яь, г =- (~ы гхь — уьяа ~)~с((ь г .
Я, й = 1. 2,... (21) Этот метод, примененный на шаге Й вЂ” —. 1, носит название правила логссного положения (или гейп1а Ыз1). Примененный к произвольному шагу итераций, он называется методом секуп1иаа Заметим, что если используется правило ложного положения, то, получив:г, мы приходим к ситуации, когда имеем значения функции при 2 = ве, и =- -г, и снова повторяем первую итерапию со значениями функции при - = ео, г = г~ — — 22, Другими словами, итерации по правилу ложного положения выполняются согласно формуле ог(ее) — его(го) У( ь) — У( е) Таким образом, итернруется функция еоУ(2) — У(ео) 42) = 1 (е) — Г (ео ) и., следовательно, гь,г = ууь(яе), где фь(е) =- 1ся ' о яе). 3 а д а ч а й. Рассмотрите правило ложного положения в веществешюм случае и укажите условия, при которых корень т = 6 будет притягивающей точкой отображения ин а, 6) — В., где (а, Ь; — некоторый отрезок, на котором лежит корень б.
Дайте геометрическую интерпретацию полученного условия. Коли г =- 2, то уравнение д(-) = О можно привести к удобному виду, положив предварительно Ь, = -, — г, ы Лг = 1г,/61 ы 6, = 1 + Л,. В качестве искомого примем Ль, г и тогда получим уравнение Ль,,Лл6„'(Я 2Ль —,уь.. гдл уь) -. Ль-16., 1уь+ )ь = О, где дь — -- гсь аЛгь — Д гос ' 1ь(Лл + 6ь). Отсюда ват1 = гь — 2Ьь~ь6ь~ дь.г [д~~ — 4Я6ьЛь®„.
2Ль —,Уь 16ь+гсь)1 ), (22) 532 Глава д, Теория изаерачий и мгтоды решеаия некотории аадач и знак в знаменателе берется тот, при котором соответствующее решение вьч з будет ближе к ею Использовать предлагаемый метод при г > 2 вряд ли целесообразно. Вопрос о глобиаыюй сходимости итераций (21). (22) не проще, чем вопрос о сходимости ньютоновских итераций, но он почти тривиален, когда речь идет об асимптотической сходимости в малой окрестности простого корня е = С уравнения Д(е) .—.
О. Пусть е =. с —. ~, ее = с + е„. Используя разложение в ряд '1ейлора, получим Л = И .) = я+и = М'а+ — ', ~а®+ . Подставляя зти разложения в (21), получим ч.з — ~ 2 (ььь;, з — е„,ьь — з) т ~(ьь — з — ьь) ~~ (че)+ . 1У (с) - - — з е «') Отсюда, если з,а з(, 'р,ь( < б и Б достаточно мало, то 1~а- <,,:(1 М!Сь- чь, (23) где 6 некоторая константа, причем ее можно сделать сколь угодно малой, выбрав соответствующим образом б. Пусть зз = (1 + + 6) ) ~о(С) ) у'(2/~'(С) ~); рассмотрим решение мажорангного уравнения ~и- з = Ж4ь — з чь. Если а',а~Х < а < 1, 'з,"зрз' < е1 < 1, то, положив Ж~ь = йы из мажорантного уравнения получаем, что йь < д~", где Га удовлетворяют уравнению Гь, з =- Гь — Гь з и начальным условиям Гв = Гз = 1, Но тогда Гь числа Фибопаччи (см.
(2.4.3)). Поскольку ~еь~ < сь (й = 2, 3,,), то ,'ч,ь ~ < Л' 'др', откупа ешедует сверхсходимость предложенного метода итерации, так как 1 [(1 +,зб ь (1 — зз5)ь~ ! (1 + зз5)а Коли мы находимся в достаточно малой окрестности корня С, то соотно- шение (23) можно заменить асимптотическим равенством уо(С) ' 2дзз(с) и тогда (~ь)Хез = з1~', где Хв = ро(С))'(2Г'(С)) . Отсзода з -рз.
/ро — З р зр~ ьь — з =' в ~ча' '86. Риивнис нсаинейнмв уравнений и систем уравкснн12 333 и, следовательно, л г — с/~а ~: гс< 11рс а учитывая (24), отсюда получим 1ЯЛ вЂ” 1)/2~. дгг5~1Ц2 ~0618 ~ 1,618 (20) 3 а д в ч а 9. Покажите, что при г = 2 ~~««1~ № 8« -2Г«-.18«~«гДЕ № = = )/а(С)/(й/'(С))!. Выведите из этого соотношения, что )С«г~! дса с«)ь Интересно сравнить асимптотическую эффективность «1етода секущих и метода Ньютона.
За единицу сложности алгоритма примем сложность вычисления значения функции или ее производной. Ясно, что при таком условии два шага метода секущих нужно сравнить с одним шагом метода Ньютона. Если в формуле (20) убрать все члоны, возникающие нз-за погрешностей округления, и учесть, что тогда формула будет справедливой для произвольной функнии / В С~, то получим ( « — О'1'а(х«) (к« - 02/аЫ),-(,)2 о/~(т«) 2/~(с) Для двух шагов метода секущих д«0,618 ~ у0,618( с)1,618~ 1 81" №1,62 ( б) 2,618 и мы получаем выигрыш по сравнению с методом Ньютона.
Следовательно, метод секущих дает асимптотически более высокую скорость сходи- мости. Для квадратичной интерполяции выигрыш будет еще больше. Если вычисление производной — более сложная процедура, чем вычисление функции, то контраст между этими методами будет еше более резким. 6. Вычисление кратных корней. Если корень с = б имеет кратность 8, то, используя метод Ньютона и считая, что 2«близко к С, получим «~ 1 = « — = 2« — ~ / ' (С) + О((с« — ()' )) х Х( «) 1(2« — с)' йй эь1 Г(в«) ~ 81 х [ ~', /1'1(~) + О((㫠— р)')~ поскольку по формуле Тейлора ( с)а /(2«) =- /(С -~ з« -- С) =., /~'~(8) + 0((л« -- С)') (аналогичная формула имеет место и для произволной). Такил1 образом, в«эг = 6« —, 0((8« — б) ), 8 534 Глава 3.
Тоорил итораций и ллвтоды рзтвииа иокоторих задач откуда хатг — ~ = (1 — в ~)(ха — с) + 0((хь — с) ). (26) Таким образом, метод Ньютона теряет свойство сверхсходмости. Для того чтобы сохранить это свойство ньютоновских итераций, в том случае когда априори известно, что корень г = р имеет кратность в, следует итерации вести по формуле , У(ха) — гь — 8 В самом деле, (х.-аг ~" (:) хьюг = хь — [гь — ~+ +..., х х 1ч- о л(лч-»(о) Р'(с) и, приводя к общему знаменателю, после приведения подобных получим — —.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
