Fedorenko-RP-Vvedenie-v-vychislitelnuyu-fiziku (810773), страница 7
Текст из файла (страница 7)
Положим г = ге+ ат (а е (О, 1), й е О, Ф вЂ” 1) Рассмотрим выражение П (г — г„), входящее в формулу (6). Оче- «О видыо, г — /„=* йт + ат — пт = (2+ а — п) с. Таким образом, П('-') = ""П(й+ — л) Для оценки П (х + а — и)/(А/+ 1)1 воспользуемся табл. 4, в которой приведены значения ! х+ а — л~ и соответсп|ующим образом расположенные мажорирующие их множители из Ф1.
Видно, что оцениваемое произведение состоит из мыожителей, не превосходящих еднинпы, и дополиительного множителя 1/(К+ 1). Отсюда следует (9). Посмотрим, как изменяется оценка при переходе к задаче экстраполяции. Она ухудшается при удалении точки / от «носителя информацинь — интервала [г, г [.
Анализ, аналогичный только что приведенному, показывает, что: 1) пРи Г Я [1н, гн + т[ ~/З (Г)~ к тн+1 щах ~/(н+О(Р) ~. с,«~ «С 2) при г е [гн+ т, г + 2т[ ~/1н(Г) ~,а (А1+'2)тн+' 1пах ~/<н+О (Г') [; з — !ззз Ю0«~ «! Из (8) непосредствеыно следует утверждение леммы (6). Выражение (6) для остаточного члена позволяет получить серию более конкретных результатов. Приведем некоторые из них. Теорема 3 (о точности интерполяции ыа равномерной сетке).
Пусть сетка равномерна, т.е. г„= лт, т = Т/Х, / Е [О, Т[, Тогда асиозы вычислитзльной матзматихи 3) прн ( Е [(л + 2х, (л + Зх] (К+2)(У+3) а ы [/(л+~)( «) [. ~,ас а~ и т.д. Таким образом, оценка ухудшается как за счет появления множителей, так и за счет увеличения оценки [/("+') [ при расширении интервала. Хотя это — оценка сверху, она правильно отражает общую тенденцию: экстраполяция функции менее надежна, чем интерполяция, и ее точность резко падает по мере удаления от носителя информации. (Этим, в частности, объясняется ненадежность Таблица Ф разного рода прогнозов, многие из которых основаны на той или иной экстраполяции измеренных в прошлом значений прогнозируемой величины.) Итак, интерполяционный полипом на равномерной сетке дает существенно более высокую точность, чем кусочно-линейная интерполяция.
Их погрешности суть (Т/Ф) "+' шах [/("+') )/())(+ 1) и, в лучшем случае, (Т/г/)з шах [/" [/2 соответственно, Правда, прямое сравнение этих величин невозмоа(но, ведь оценки включают значения разных производных. Наилучший выбор сетки. Рассмотрим следуюшую задачу. Можно ли повысить точность интерполяции за счет рационального размещения узлов сетки на интересуюшем нас интервале [О, Т[? Если об интерполируемой функции мы не знаем ничего, кроме того что она Л(+ 1 раз непрерывно дифференцируема, единственным средством улучшить' оценку остаточного члена является выбор узлов сетки [(„) решением характерной задачи на минимакс: ппп шах с,, сг ..., (, ~ оы а т Эта задача, известная как задача о построении полинома, наименее уклоняющеп)ся от нуля на заданном интервале [О, Т[ (с нормировкой «коэффициент при старшей степени ( равен единицеь), была решена (по другому поводу) П.
Л. Чебышевым. интшполяция ьгнкций Ьз1 Таким образом, «наилучшей» является сетка, узлы которой совпадают с корнями полннома Чебышева степени Ф на интервале (О, Т), Для этих корней имеются простые явные формулы. Чтобы не отвлекаться, приведем необходимые нам сведения о полиномах Чебышева в конце параграфа, Заметим только, что это один из важнейших обьектоз численного анализа, и в дальнейшем мы еще не раз встретимся с задачами, в которых полиномы Чебышева окажутся очень полезными для построения эффективных вычислительных методов. Сетки с узлами, равными корням полинома Чебышева, играют большую роль в разных вопросах и называются чебышевскими. Чебышевская сетка является «наилучшей» с точки зрения целого класса функций, выделенного, например, условием ~,Т<Я+0(Г) ~ К С.
Для конкретной же функции У(~) может оказаться лучшей своя индивидуальная сетка, и такие сетки часто используются в расчетах. Построение индивидуальной сетки требует гораздо большей информации о строении функции. Прн построении сетки используются простые соображения: например, сетка должна быть гуще там, где функция «устроена» более сложно, имеет резкие градиенты, совершает частые колебания. Там же, где функция очень гладкая, сетку можно взять более редкой. Собственно говоря, приведенные соображения тоже связаны с оценкой производных, но если эти производные принимают на (О, Т'1 существенно разные значения, имеет смысл (если это технически возможно) разбить интервал (О, Т'1 на части с разными оценками производной и на каждой части строить сетку по-своему.
Например, один из практических принципов построения сетки — «принцип равномерности погрешности». При нспользовании кусочно-линеиной интерпопринцип рекомендует расставлять узлы таким образом„ чтобы величина (г««1 1«) С«»нт' где С «нз 2 Рис. 4 оценка ~У"! на (г„, т„«,1, была более или менее равномерной, не зависящей от и.
Рисунок 4 поясняет, что примерно имеется в виду под индивидуальной сеткой. Сравним точности интерполяций на равномерной и чебышевской сетках. Мы приведем только результат, сравнив оценки величины (10) для двух типов сеток. В случае равномерной сетки, как было показано выше, эта величина оценивается числом (Т/Щ~ '!(И+ 1). В 2« зь основы вычислитвльноа мАтвмАтики случае чебышевской сетки, как следует из сведений, приведенных в конце параграфа, для (10) имеем оценку (Т!4)»1(» + 1)1. Используя формулу Стирлинга М (Ф/е)», получаем выигрыш примерно в (4/е)» раз.
Это само по себе может быть и не очень много. Однако чебышевские сетки обладают и более важными преимуществами перед равномерными. Перейдем к их обсу:кдению. Устойчивость иытерполяционного полннома относительно погрешностей вычисления Ф. Рассмотрим следующий вопрос: пусть таблица (Т„) вычислена не точно, а с погрешностями, связаннымн хотя бы с конечной разрядностью машинной арифметики. Как повлияет неточыость вычисления у на интерполяционный полинам? Итак, пусть полипом вычисляется по таблице (/„+ Ь„), где ܄— погрешность, относительно которой нам известна только оценка ~ Ь„~ ~ Ь.
Тогда «машинный» интерполяционный многочлен связан с истинным очевидным соотношением С,„(г; (г„), (г„+ Ь„)) = Ь„(0 (г„), У„)) + Ь„(0 (г„), (Ь„)). (11) Это следствие линейности полинома по У„, Второе слагаемое правой части (11) есть погрешность, связанная с ыеточностью вычисления т. Оиа и подлежит оценке. Естественно в качестве меры погрешности взять величину шах ( шах ~ Е (0 (г„), (Ь„) ~), 1в„~«в о«~«т т.е. оцеыить ее при самой неблагоприятной комбиыации погрешностей Ь„в пределах заданной точности. В силу линейности по Ь„ можно заменить эту велнчиыу на Ьд((1„)), где т)((г„)„" р) =шах (и|ах ~Ь»(ц (г„), (Ь„)~), (12) 1в„!«~ о«~«т Величина т1((Г„)„" ) является характеристикой сетки и оценивает чувствительность интерполяционного многочлена к погрешностям в У„.
В теории интерполяции такие характеристики были вычислены и оказалось, что т1 яв 2" для равномерной сетки и 11 1и М для чебышевской. Величину и((г„)) называют также нормой интерполяционного полинома на даныой сетке. Этот термин связан с тем, что если определить Я(г"„) Я ев шах ~~„~, то при г Е (О, Т) имеем « !С (Ц (г„) У„)И к!НУ„И! т1((г„)). ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ Мы выяснили важное обстоятельство: интерпол яционный полипом на равномерной сетке очень чувствителен к погрешностям вычисления /„(!1 ж 2"); полипом же на чебышевской сетке слабо реагирует на зти погрешности: его погрешность мало отличается от погрешности вычисления / — только не очень большим множителем 1и л!. Конечно, зти факторы существенны при высоких степенях интерполяционного полинома (!у' = 10, 20, ...). При низких же степенях интерполяционного полинома (л! Ре 5) зто еще не очень существенное различие.
Оценка (12) приводит к еще одному важному достоинству чебышевских сеток. Устойчивость ннтерполяциониого полинома относительно априорной информации. К априорной информации мы отнесем предположение о наличии у ицтерполируемой функции / нужного числа производных. Поставим следующий вопрос: пусть для функции /(!) На сетке (г„)» построен интерполяционный полипом степени Ж, а фактически функция / на (О, Т*1 не имеет требуемой теорией (/ч'+ 1)-й производной. Например, пусть какая-то ее производная невысокого порядка терпит разрыв. Как это скажется на качестве аппроксимации такой функции интерполяционным пали- номом /»(и (г„), (/«))2 Оказывается, ответ существенно связан с характером сетки.
С. Н. Бернштеином было показано, что полиномы, интерполирующие на равномерной сетке функцию /( г) = ~ ! ! с ростом /ч не только не сходятся к интерполнруемой функции, по Рвах ~1.»(!) — ~ г~ ~ — ! при лг ««. -!«!«! Совсем иначе и совершенно замечательно ведут себя интерполяционные полиномы с чебышевской сеткой. Для того чтобы объяснить это их свойство, нам понадобятся некоторые факты из так называемой «конструктивной теории функций».
Введем полипом степени л!, наилучшим образом аппроксимирующий данную функцию /(г) на (О, т'ь т,е. полинам, реализующий ш!и (шах ~Р (г) — /(!) ~) =Е»(/). Р О«!«г Здесь ш1п берется по всем полиномам степени не выше /ч. Полипом наилучшей аппроксимации существует, но его фактическое построение является очень трудной задачей. Такие полиномы находятся только сложными итерационными алгоритмами так называемой Негладкой оптимизации и требуют большого объема вычислений. Таким образом, полипом наилучшего приближения к /(!) на (О, Т) является обьектом по существу не конструктивным, его использование в практической вычислительной работе в общем !ч.с зз основы вычислитвльной млтвмлтики случае просто невозможно.
Однако теоретические его свойства хорошо изучены. В частности, известна асимптотика величины Е,(У) при М- ° . Она оказалась однозначно связанной с гладкостью У(с). Несущественно огрубляя формулировки, приведем основные факты, Если у(с) имеет на (О, Т) ограниченную г-ю производную, то Е„Ц) = О(1/М").
И наоборот, если Е„(У) имеет такую асимптотику, то /„имеет ограниченную г-ю производную. Хотелось бы иметь конструктивный метод построения полиномов, дающих аппроксимацию функции у(с), близкую к наилучшей. Оказывается, таким является интерполяцнонный полипом иа чебышев- ской сетке! Этот факт мы сейчас докажем.