Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
’!(WJ'-o) = ™ {“ах ILn (t; {tj, {S„}|}. (12)
|6Л|«1 о
Величина і]({ґп}^=0) является характеристикой сетки и оценивает чувствительность интерполяционного многочлена к погрешностям
в /»•
В теории интерполяции такие характеристики были вычислены и оказалось, что ^ ^ 2N для равномерной сетки и ^ «In N для чебышевской. Величину г] ({*„}) называют также нормой интерполяционного полинома на данной сетке. Этот термин связан с тем, что если определить ||{/ге}|| = max |/J, то при t Є [0, T] имеем
П
ILn (і; {*„}. {/п})| «»{/„}Il T1(W).
§3]
ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ
37
Мы выяснили важное обстоятельство: интерполяционный полином на равномерной сетке очень чувствителен к погрешностям вычисления /в (т] =» 2^); полином же на чебышевской сетке слабо реагирует на эти погрешности: его погрешность мало отличается от погрешности вычисления / — только не очень большим множителем In N. Конечно, эти факторы существенны при высоких степенях интерполяционного полинома (N= 10, 20, ...). При низких же степенях интерполяционного полинома (N «к 5) это еще не очень существенное различие.
Оценка (12) приводит к еще одному важному достоинству чебы-шевских сеток.
Устойчивость интерполяционного полинома относительно априорной информации. К априорной информации мы отнесем предположение о наличии у интерполируемой функции / нужного числа производных. Поставим следующий вопрос: пусть для функции fit) на сетке построен интерполяционный полином сте-
пени N, а фактически функция / на [0, Т] не имеет требуемой теорией (N + 1)-й производной. Например, пусть какая-то ее производная невысокого порядка терпит разрыв. Как это скажется на качестве аппроксимации такой функции интерполяционным полиномом LN(t\ {*„}, {/„})?
Оказывается, ответ существенно связан с характером сетки. С. Н. Бернштейном было показано, что полиномы, интерполирующие на равномерной сетке функцию f(t) = 11\ с ростом N не только не сходятся к интерполируемой функции, HO
max \LN(t) — 1t\ I -> oo при N-*<*>,
—I
Совсем иначе и совершенно замечательно ведут себя интерполяционные полиномы с чебышевской сеткой. Для того чтобы объяснить это их свойство, нам понадобятся некоторые факты из так называемой «конструктивной теории функций». Введем полином степени N, наилучшим образом аппроксимирующий данную функцию f(t) на [О, Г], т.е. полином, реализующий
min {max \PN(t) - f(t)\) = EN(f).
Pfl OStGT
Здесь min берется по всем полиномам степени не выше N. Полином наилучшей аппроксимации существует, но его фактическое построение является очень трудной задачей. Такие полиномы находятся только сложными итерационными алгоритмами так называемой негладкой оптимизации и требуют большого объема вычислений.
Таким образом, полином наилучшего приближения к f(t) на [0, T] является объектом по существу не конструктивным, его использование в практической вычислительной работе в общем
38 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ [Ч. I
случае просто невозможно. Однако теоретические его свойства хорошо изучены. В частности, известна асимптотика величины Еы(/) при N-* Она оказалась однозначно связанной с гладкостью f(t). Несущественно огрубляя формулировки, приведем основные факты.
Если f(t) имеет на [О, Т\ ограниченную r-ю производную, то
EN(f) = O(IINr). И наоборот, если En(J) имеет такую асимптотику, то /„ имеет ограниченную r-ю производную. Хотелось бы иметь конструктивный метод построения полиномов, дающих аппроксимацию функции f(t), близкую к наилучшей. Оказывается, таким является интерполяционный полином на чебышевской сетке! Этот факт мы сейчас докажем.
Теорема 4. Пусть LN(t; {tn}, {/„}) — интерполяционный полином для f(t) на интервале [О, Т] с чебышевской сеткой. Тогда
\LN(t)~f(t)\ ^(\+\nN)EN(f), і Є [О, Г],
т.е. такой полином дает почти наилучшую для полиномов степени N аппроксимацию функции f(t) на [О, Г].
Доказательство. Пусть Pn (t) — полином наилучшей аппроксимации f(t). Тогда /„ = PN(tn) + 6„, причем погрешности Sfl удовлетворяют условиям 16„ I ^ Eh,(f). Обозначая рп = PN(tn), имеем
LN(t; {tn}, {/„}) = LN(t; {tj, {рп + Ьп}) =
-Ln(t; {?„}, {pn}) + LN(t\ {ї„},{6„}).
Ho LN(t; {tn}, {p^}) = Pn (t), так как интерполяционный полином степени N, построенный для полинома степени не выше N, в точности совпадает с интерполируемым (при любой сетке).
Для второго слагаемого имеем оценку
I LN(t; {/„}, {6„})| *? lnJV||{6J Il =In N EN(f).
Используя представление PN(t) = f(t) + &(t), где 16(t) | ^ EN(f), получаем
Ln (t, {/„}, {/„})=/(/) + 6(0 + Ln (t; {у, {&„}).
Для погрешности аппроксимации имеем оценку
|6(0 +Ln (t; {/„}, (SJ) | S= (I + In N)EN(f).
Теорема доказана.' Таким образом, интерполяционный полином на чебышевской сетке (напомним, что он легко выписывается в явном виде, так как корни полиномов Чебышева вычисляются по простым формулам) замечательным образом адаптируется к фактическим свойствам гладкости интерполируемой функции.
§3]
ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ
39
Дифференцирование интерполяционного многочлена. Из того, что две функции близки, как известно, еще не следует близость их производных. Однако в рассматриваемом случае ситуация более благополучная: L(t) аппроксимирует f(t), а производные L(t) — производные /(/)> хотя точность аппроксимации, конечно, падает с ростом порядка производной. Ограничимся здесь лишь указанием на следующий факт: производная Ln (t) является интерполяционным полиномом степени N-I для функции /'(О» построенным на сетке, отличающейся от исходной. Это почти очевидно: между каждыми двумя нулями функции
