Бабенко - Основы численного анализа (947491), страница 34
Текст из файла (страница 34)
Поэтому возььшм его в форме интерполяционного многочлена Лагранжа (см. п. 4 51 гл. 3). В качестве узлов интерполярования возьмем нули многочлена Чебыдддева первого рода Х'„(х) (см. п. 5 5 3 данной главы). Принимая во внимание условие нормировки Эс(0) = 1, потребуем, чтобы среди корней многочлена Т (х) был нуль, т. е. и должно быть нечетным числом. а учитывая, что в качестве явного паралдетра нам нужно иметь щ(1), добавим к взятым узлам точки тс —" 1, х„ьд =-. — 1; положим и = 21 — 1. Поскольку ищется четное решение уравнения (1), то интерполяционный многочлен возьмем четным. Нули многочлена 7;,,(х) равны х, — -- сов(21 — 1)к,д(2п) (1' =. 1, 2, ..., и).
Обозначая через йд(т) искомый многочлен и учитывая его четность, получим бд = йдд(хд) = дй(--хд) = йд(х —, д.д) О =- 1, 2,..., 1), дддд(хд,.д) =- сдд(0) =. 1. Положим 5 —.— — йд (хо) = — й(х -д.д). П1диводя подобные члены в формуле Лш ранжа, задающей вид интерполяционного многочлена, и переобозначая неизвестные через бдд, а удьчы через хд, получим ~( )=~ ' ~дхх "(х) ( х) "(') --5 т ( ) (э) 1-х,', (х' — х;,)Т~,(х„) хТд(0) Величины бд, 0 =- О, 1, ..., Н вЂ” искомые и могут быть найдены из условия, что вшогочлен хд(х) удовлетворяет уравнонию (1) в узлах интерполяции.
Таким образом, мы приходим к следующей системе уравнений: 1 бдд = — — йд о йл (бдохдд), д' = 1, 2, ..., 1, бда с ",до = — утд о удд(ьдо) ьда или,преобразовав их,получим систему бдобдд + дрд йдд(бдохдд) 1' = 1 2, до йд сд 4дд(бде) = 0 (3) Полученная алгебраическая система из 1+1 уравнений с 14-1 неизвестными может быть решена методом Ньютона. Однако если возьмем 1 = 2 либо 1 = =- З.мы столкнемся с совершонно бесперспективной ситуацией: система имеет много решений, а какие из них пригодны — неясно и как брать начальное приближение — также совершенно неясно. Поэтому возникает естественная мысль решить систему (3) при минимальном 1 = 0 и затем, отправляясь от полученного решения, перейти к 1 —.
1 и т. д. При 1 .—.. 0 уравнения (3) сводятся к единственному алгебраическому уравнению для величины бенд ро(х) —. хв — йх —, х — ' 2х — 1 —. О. (4) Ыьд отмечали, что будем искать решение уравнения (1), вогнутое снизу, и так как дс(0) = 1, то следует ожидать, что Эд(1) < О, т. е. боо > О, и поэтому будем отыскивать положительный корень уравнения (4). Проблемы, связанные с решеяием алгебраических уравнений, будут нами разобраны в гл.
8, а здесь мы отметим, что. прежде чем применять метод Ньютона к отысканию решений уравнения (4), желательно произвести локализацию его корней. Из курса алгебры (23) известна следующая 152 Глава 3. Математические основью численного анализа. 'Теорема 1 (Декарта).
Число положительных корней многочлена р(к) равно числу перемен знаков в системе коэффициенюпов этоса многочлена или зьеююьте этого ~исаа на четное число (при*ем каждьюй корень считаетсч с(полька раз, какова его кратность, равные нулю козффициенюпы не учатыВаюоюгюсл) . В нашем случае две перемены знака, и поскольку ро(0) < О, ро(оо) = =- -(-оо, то положительных корней два. Использовать теорему Штурма (см. п. 3 5 6 гл. 8) для дальнейшей локализации корней довольно сложно, и поэтому мы применим следующий простой результат (9). Теорема 2. Длл многочлена р(к) = т" — 'аюк" ю — '...+ап с произвольнылюи коэффициентами число !+шах,аь служит верхней границей длл модулей ю.
всес его корней (действюипельных и комплекснык). Поэтолюу положительные корни многочлена (4) лежат на интервале (0,3), а делая замену переменных:с = 1(у и применяя к многочлену у ро(1(у) аназ логичное рассуждение., получим, что все корни по модулю болыпе 1,('3. Таким образом, положительные корни многочлена (4) лежат на интервале (1,73, 3). Беря в качестве начальных данных ко = 1,(3 и хо = 3 и применяя метод Ньютона, получеюм два корня: 'соо = 0 40219699869 ' бо(а = 0 85971740141 (5) Организация вычислений в данном случае тривиальна, и поэтолюу мы на ней не останавливаемся. Таким образом, мы нашли фо(к) = 1 — (1 боо)тз и для соо имеем значения (5).
Поэтому, беря 1 = 1, мы в качестве начальных данных для ньютоновских интераций при решении системы (3) будем иметь значения бюю = 1 — (1 т боо ) сов~(к(6), бюо =- 5 „~ либо значения бюю = 1— — (1 + боо ) сов (х((бю), .бю —" боо . В обоих случаях итерации сошлись (числен- (2( 2 (2( но), и первая па1(а приводит к многочлену фю(к), график которого вогнут на (-. 1, Ц. Вторая пара дала многочлен с невогнутым графиком и потому была отбропн на.
Мью не будем выписывать формулы, по которым делались вычисления: они были почучены стандартным путем. Опишем пробу на конец итераций. Это нажный момент, поскольку погрешность, с которой можно получить приближенное решение системы, тесным образом связана с величиной разрядной сетки компьютера. Если через 5(;Ю (( =- О, 1„..., 1) обозначить решения системы (3) на о-й итерации и пат(южить е( = (пах (, ( — 5( ~, то итерации ,( -юю (ю ю=о,ю, прекращались по достижении неравенства е(н < е, и в качестве решения брались величины 5(' (з = О, 1,..., 1).
Мы вели вычисления на ЭВМ БЭСМ-6 (чэц в арифметике двойной то юности (80 бит в мантиссе числа). Причины, по которым использовалась арифметика двойной точности, будут обьяснены ниже. В вычислениях принималось е =- 10 . Вот как менялось ею в процессе итера — 9 ций (напомним, что речь идет о расчете при ( = 1): 153 3 5. Численный пример на лштпд Ньюшона шах /ез(к)! < Л шах!ел(к э)/, с(-ь 0 (6) где х (! = 1. 2, ..., т) — нули многочлена Т,(т), Л„, — константа Пебега лагранжева ннтерполяционного многочлена с узлалеи ттэ.
Отметим, что в неравенстве (6) взяты в качестве уазов нули многочлена Чебышева, потому что для них константа Пебега асимптотически оптилеальна по величине (см. п. 1 3 3 гл. 3). Так как Л,ь медленно растет с ростом т, Лт < (2!'к) 1п ш+ 1 (см.
и. 1 33 гл. 3), то мы получим правильное представление о величине пшх ~ьл(ш) ~ *е! — ь г по ш! = шах~ш!(я,пэ)~. Так, вычисления дают ш! = 5,488207... 10 ~, что замечательно для многочлена сталь невысокой степени, как 61(к). Ход дальнейших вычислений однозначно определен. Предполагая, что вычислен многочлен ен 1(х), мы при решегши системы (3) в качестве начальных данных для ньютоновских нтерацпи возьмем величины 8! =. ьз 1(т!э) О = е = 1, 2,..., !), б!ее = 0ь.1(Ц н затем реализуех1 итерационный процесс.
В табл. 1 представлены результаты вычислений для ! —.- 2, 3,..., 12. В ней приведены величины е!,, б! и ел, вычисляемью для удобства на каждой итерации. РеЗультаты дальнейших вычислений мы не привОдим, хотя прОделали их и для ! — -- И, 14,..., 17. Уже при ! = 13 величина югэг не меньше ш1эм а при ! = 15, 16, ..., 17 шп начинает расти. Аналогичная картина наблюдается для величин е! и д! .
Причина этого эффекта очевидна: погрешноети округления начинают играть нреобладаюшую роль и невязка д! и ш! при ! > 12 формируются за счет неверных мта!1ших разрядов и могут не иметь пи одного верного знака. Если бы мы вычисления делали с одинарной точностью, то этот эффект наблюдали бы уже при ! > 5. В 3 2 гл. 1 мы рассмотрели представление чисел в ЭВМ и установьши, как оцепить погрешность округления при выполнении простейших арифметических операций. Как указывалось, числа с двойной точностью на ЭВМ БЭСМ-6 имеют ! = 80 разрядов в мантиссе.
Поэтому величина е = Ь' ',!2 в данном случае равна 2 эо = 8,27... 10 эе. Мы нашли, что юшг = 9,049... 10 э', и при Косвенным свидетельством тому, насколько хорошо мы решили систему (3) при 1 = 1, служит величина неелэки, т. е, величина, получаюшаяся. если в уравнение (3) подставить найдшпгые приближенные значения. Мы будем вычислять невяэку на каждой итерации для каждого уравнения и затем брать максимальную по модулю величину, которую обозначим через дю, если рассматривается и-я итерация. Имеехя 61л =- 4,34э630...
10 ", что согласуется с величиной еем Поскольку вычисления мы делаем с двойной точностькь те погрешноСти округлЕния не окаЗывают влияния на Старшие раЗряды чисел ы н дгл, Если попытаться решать систему (3) при ! .— —. 1, отправляясь от случайных начальных данных, что мы и проделали, то получим некоторое ее решение, но не имеющее никакого отношения к уравнению (1); при некоторых вполне естественных начальных данных мы наблюдали пе сходимость процесса, а его расходимость и получали переполнение по порядку. Построенный многочлен должен являться приближенным решением уравнения (1), и поэтому естественно попытаться подставить его в уравнение н вычислить певязку.
Чтобы это сделать, заметим, что функция гч о 4л(к) — многочлен степени (2! 4- 2)', и поэтому выражение еэ(ш) = Ез(к) —,, 01эй о йп( — эй(1)(ш)) так же многочлен степени (2! л-2) . Если вычислим невязху ш!(т) в нулях многочлена '1'„(ш) (тп = (2!+ 2)э 1), то по неравенству (3,3.7) 154 Глава 2. Математические осиооьг численного анализа, Таблица 1 бш еш 1,63108... 10-' 3,269П... 10- 1,68745...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
