Н.С. Бахвалов, Н.П. Жидков, Г.М. Кобельков - Численные методы (djvu) (1160088), страница 12
Текст из файла (страница 12)
Вследствие (2), (3) то*псами экстремума 7,',(х) на [ — 1,Ц будут точки, гда [Тг(х)[ = 1. Решая шо уравнение, получим ;япы х(„,1 = сое ( — ), гп = О,..., и, причем Тц(х1,1) = сгилт = ( — 1)м. Тц(х) = 2г "Тц(х) = х -~- ° Мнагочлепы называвгг мпогочлеиами, наименее уклогспощимися от прлл.
Это опреде- ление обьясняегся слсдуюпгим свойством. Лемма. Если Рг(х) —.многочлен стсигци и со сторши,и когфб)ицггеиогом 1, гпо гпак (Рц(х)[ > шак [Т„(х) [ = 2' ". (б) ( — ЦЦ ( — г,Ц Задача 2. Доказать более сильное утверждение: если Р„(х) = х" + .- е Т„(х), гоах [Р„(х)[ > 2г **. 1 — г,г) доказательство. Предположим проливное. Многочлен Т„(х) — Р„(х) имеет степень п — 1; в то жо время з1йгг(Т (х(,1) — Р„(г1 1)) = з1йп((-1)'"2г "— Р (х1,„1)) = (-1)'", так как, согласно предположеншо, [Р, (х( 1)[ < 2' " прн всех гп.
Таким образоы, мсжпу каждыми двумя точками т(ц,1, х( гц многочлен Т (х)— Р„(х) меняет знак. Многочлен йч (:с) — Рг(г) степени и — 1, отличный от нул» (поскольку он отличен от нули в тачках х(„,)), имеет п различных нулей. Мы пришли к ггративоречиго. 61 8 8. Мноючленьт Чебышева Т„' (х) =- (Ь вЂ” а)»2т т»Т» ( ( )) со старпптм коэффициентом 1 являегси лтногочленолт, наименее уклоня- ющимся от нуля на отрезке [а,б]. Это означает, что двя .эюбого мнп- гочлсна 7»„(х) степени и со старшиы кеэффттциентом 1 справедливо не- равенство пшх ]Р„(х)] > швх [Т„* ( т)[ = (8 — а)э 2т 2». ' — ! *ь), ' ° т-т» (,ь! (Д (6) — 1 Д Нетрудно проверить, что пулями многочлена Т„' (х) янляются точки Ь -1- а 6 — а /к(2тп — 1) 'т х,„= — + — сов [ тп = 1,..., и. 2 2 [, 2п Мттоючлсмьт Тс(х) = 1/ь'2, Т„(т) = Т„(х) при и, > 1 образуэтт на [-1,Ц ортонормированную систему с весом 2/(я~/1 — хэ).
Проверим свойство ор'гонормироваиносги этих функций. После замены х = соэВ имеем /ч е/с» ' 2Т (г)тм(э;) 1 Ук т)х =- — 71 соэпрсоэп»ВВВ = /):хэ /, '» 2г 7 = — / (сов«п — тл)В) + соэ«п + тп)В)) т(В = 6;, + 6,„". Второе слатвсмос обращается в нуль при тт, тп > П, если пэ -1- тпз Ф О. Отшгща вытекаес требуеыое равенство Г-'- "— "=- т 2Т (х)Ты(т) кчт1х~2 Пусть нноючлены Чебышева вычиглшотся по рекурреитаой формуле (Ц. В процессе реальных вычпслевий змеею значений 7'„(х) папучасм приблнлсен- ные эаачевиэ 7'„*, улоилетворлюшве соотношениям Т»" — — 1, Т, =х-~-бт, Тыт — — 2хТ„' — Т;,, +6„»т, где дь — погрешности, вызванные округлениями. Задача 3.
Получить представление погрешности Т'(х) — Т (,)=Ч 6 «2+1 т=1 1 — х Линейной заменой переменных х' =-- — +." + =х отрезок [ — 1, Ц можно — уй — тьь т1 перевести в заданный отрезок [а,б]. В миогочлене Т„( — +=/ старший коэффициент равен (2/(6 — а))". В соответствии с леммой можно утверждать, что многочлен Глава 2.
Интерполяция и числеаасе лифференцароваяие Задача 4. Получить, используя решение задачи 2, оценку погрешности ]2л(х) — Тл(х)] < 1лах )Ьг]. 1У. шш! !У, ) . (7) 1 1<1<К '[ л:--. Задача б. Непосредственной проверкой убедитьс», что в нулях много- / 12 -111 членов Чсбьппсва х = сов 1 ь. 1 справедливо равенство !у ]Тй(хш)] = — —. Отскша заключаем, что лри явлении х в окрестности этих ъ улей с погрешностью Б погрешность вычисления значения т„[х) будет велэч1люй, башкой к ги! ; эпэ оэню1ает, что оцевкэ (7) нс иоягет быть существенно улучшена.
Задача 6. Пусть [У вЂ” нокоторое фиксированное число. Доказать, '1то вектоРы, об1Реаованвыс значелицми многочлснов Тц(х), и < 1У в нУлвх Тл[х), образу1от некоторую ортогональную систему, а именно — ~тч ( )Тц,( ) =Ь,',в пРи 0<п, т<77 — 1. (8) З Я. Минимизация оценки остаточного члена интерноляционной формулы Г!усть функция [(х) приближаетт11 па [а,Ь] с помощью интерполяционного многочлспа степени и — 1 с узлами интерполяции т1,..., хэ Е [о,Ь]. Согласно (3.1) имеем 1 1"! [б)ил (х) .1'( ) — б ( ) =— 71! где б Е [а,Ь], если э: Е [а,Ь]. Отсюда гшедуег оценка погрешности интерполяции ]]Х вЂ” 1.)] < [].['1[] ]] .[] Здесь ][ ° ][ есть обозна юлие равномерной нормы1 []д(х)]] =-вцр]д(х)].
[,ь! Займемся минимизациой правой чвсгн оценки (1) за счет выбора узлов х,,..., хв. многочлен ил(х) = (х — хг)...(х — х„) имеет стаРлгии «оэффициент 1, поэтому []и„][ й (Ь вЂ” а)"21 э" согласно (8.6). Если взять в кшистве узлов интерполяции Ь -~- а Ь вЂ” а г'я(2т — 1) г (2) 2 2 Г 211 вз 19. Ыиннмизаорм оценки осгетачного члена (2х — (Ь+ а)) иь(э) = (Ь вЂ” а)ь2 — ьТ„ н )) 1) = (Ь вЂ” а)"2' Оледовюткьно, при таком расположении узлов спразедлнаа паилучпгэя из оценок, которая может быль получена как гледс"гвие оценки (1): ()Х вЂ” б.)( < )фь1))(Ь вЂ” и)о2~ (3) При получении оценки (1) максимум произведения замопен на произееденне максимумов сомножителей.
Поэтому пожег нозпикнугь надежда получить оценку пгярсгннгх'ти, лучшую, чем (3). Однако это не "гэк. Нсли 1(х) = а„хь т - -~- ае — многочлен степени и, то Убд(() = аьп1 = сопэг, поэтому неравенство (1) преэращантгл е равенспэо; тогда, ж:ло „, не (8.6), при любых узлах интерпояюгип имеем (Ф-')и — ).
'-" ))г — Ьч,)) >, — = )а„)(Ь вЂ” а)ь2 Как уже отмечалась, важной проблемой вычислительной магемагики яелжтся проблема спгимизации мепр1ов решапиа зюач некоторого класса. Общая постановка ес такова. Задается некоторый класс Р рсгааемых задач р. Задается некотороо мцожесгво М методов решения. Пусть с(р,т) - погрсшншггь мшода т прн решении задачи р. Величину е(Р га) = зпрс(р, га) гер пазывакгг поэрешноснгью метода па классе задач Р. Величину е(Р,М) = ш( с(1э,~л) ем назынюот оптимальной оценггой погрешности мгоподоо аз мне:нсесшоа М на классе задач Р. Вяли сущсстауот метод гл б М, ца котором тга оценка достигается, т.е.
е(1',М) = гг(р,пг), то такой метод называют спшымальнмм. Полученное нами решение задачи сб оптимизации узлов распределения интсрпсляциоиной г)юрмулы можно сх~эормулнровать а описанных вьппе терминах. Пусть Р— множество задач приближения функций, определенных на (а,Ь) и удовлетворяющих условию )11ь1(х)) < А . Пусса М вЂ” множество методов приближенна, состоящих в том, что функция заменяется ее ингерполяционным многочленом м„(х) по совокупности узлов ем..., хьд Глава 2. Интерполяция и чисвеииое дифференцирование таким образом. метод решения гл определяется заданием узлов интеря попяции хм.... хы. Наконец, пусть мера погрешности е(р.ш) =-((( — Гв~). Согласно (1) имеем е(Р,гв) < Ав((м„(( и! С другой стороны, для задачи приближения многочлепа А Рьы (х) = — х" -~- гй относящейся к рассматриваемому кггассу, имеем Ал()и„)) е(р,ш) и! Следовательно, е(Р,гл] = — —.
А„((мл)) о! Как мы видели выше, е(Р,И) = шуе(Р,т) = шЕ /Ап()ме(('~ Ап(6 — а)л2г и! Таким образом, способ интерполяции по узлам ьпюгочлена Чебышева (2) является оптимальным в рассматриваемоьг смысле. В заключение произведеьг сравнение оценки (3) с оценкой погрешности разложения функции в ряд Тейлора.
Согласно результатам 3 б отрезок ряда Тейлора ~б>((а+ 6)/2) / а -6611 3 (, 2 ) г=с Р совпадает с ииторполяционным многочленом Лагранжа при единственном, и-кратиом узле игперполяции (а+ 6)/2. Поэтому, есттютеенью, при сиггимальпом распределении узлов внтерполяции (2) мы должны иметь лучшую оценку. В самом деле, оценка ((11">()(6-- о)"2 " погрешнсяли отршка ряда Тейлора уступает оценке (3) в 2" ' раз. Принедем для сведения оценки погрешности интерполяции с узлами е нулях мпогочлена Чебышева. Ддя просгсгпя всньмем случай, когда (а,6) = ( — 1,Ц.
Оценка 1. Если 1(х) удовлетворяет неравенству вюрф'"1(х)) <со, то справедлино соотношевие ()1[х) — Ья(х])( = 0(п ™1пп) при о -ь оо. Оценка 2. Если функция 1"(х) аналитична в каждой точке отрезка "-1,1), то ))~(х) — йп(х))( =- 0(сь), где с < 1. 11а Коночные резвости Последнюю оцеиху можно конкрегизигювать Пусть 1(з), г = з.
тзр функции, аналитическая в эллипсе на плоскости (адр) с фокусами в точках — 1, 1; тогда ()1(з:) — бь(.с))( = 0(с "), где с > 1..сумма полуосей этого эллипса. Таким образом, ари интерполяции по узлаы мпогочленз Чебышева погрешность автоматически уменьшаепя, мши алгоритм применяетсв к более гладкой функции. Такие гзпоритмы называют иснасмщаемммп. Если узлы интерполяции распределены существенно иначе. например равномерно, то даже двя аналитической функции лотре!поасть интерполяции может зшремзггься к бесконечности с ростом числа узлов. Например, для функции Дк) = (1+25гз)-' имжт пес!о соотиошопие У(з!) — 1 з(з))) д Аа", А > О, и > 1. Зада.га 1. Пользуясь формулой (8.8), показагть ччо иятгрполяциоипый мпогочлев с узлами е пулях многочлснов Чебьппева звписывэется в виде 1ь(з) = ' а..Тз(з1), а = — ~ /(з )Т ~ — /1.
и ' ! 2п з=о Такая запись илтерполяциопного многочлепа позволяет быстро и с малой чувствительностью по отношевию к вычислительной погропшосчи вычислять гго значения (см. э 4.8). 8 10. Конечные разности Пусть узлы таблицы зз расположены на равных расстояниях: зз ко е зл, 1, — соответствующие значения функции; зюличину л называют шагом таблицы. Разности Лзз — Л иазыешот рзикоспшми первого порядки. В зависимости от точки, к которой ее сзгпо1яз; этг величину обозначшот: ЬЛ-- разность вперед, 17Лэз - разность пагад, бЛ+,/2 = Лз+,/ — цгншрольказ развез!пзь. Таким образом, Л Л з з /з бЛ 1/2 Л.11/2 Разности анси!его оорздка образуют при помощи рекуррептных соотноПзвпий /у !7 зз(/г — 1/) . у -17 ь — 17 '!7 у — 17(17 1/) = тз'" 1Л вЂ” 17"' 1Л Лз=б(б Л)=б Лы/2 б Л Нз 7 1 -1 з — 1 +1/2 — 1/2' Глава 2.
Интернопяцвя н численное дяфференцяроваине 66 Таблицу разностей обычно располагают в виде В нтготорых ннтерпопяционных формулах наряду с упомянутыми выпге величинами яспользуготся средние арифметические двух погледовательных величин одного и того же столбца: р/т = (У! ! 6 У" ! )/2при т нечетном, РУ,"+г! —— (Щ + Ут)/2 пРн т чегноьс Лемма 1. Разности т-за яарлдка емражаюоюл через значения фрикции яо формуле ,бн'У, = ) (-Ц Сг„/г„ннм (2) у=о здс Сг — коэффициентам бииаиа Ньютона. Даказагпсльсяюо проводим методом индукции. При т = 1 ссютношепне (2) выполняется согласно (Ц.
Пусть оно доказано нри т =. 1. Имеем 2!им/; = Л'Уом — 21'У! =- ~(-Ц С,'У„„,, — ) ( — Ц С!Ус„,. Собирая коэффициенты нрн одинаковых Уь и повьзуясь равенством С' + С'" ' = С' ~, гм ' получим требуемое выражение дпя величины бгм У,. Лемма доказана. Из (2) гледует, что аяератор каиечяай разиотпи является линейным.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
