Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Таблица 4
п к —к к-г к — 1 к * + 1 к + 2 N
)А + а —и| к + а 2 + а 1 + а a 1-а 2-а N — k — d
JV! к +1 3 2 1 1 2 + к N
разного рода прогнозов, многие из которых основаны на той или иной экстраполяции измеренных в прошлом значений прогнозируемой величины.)
Итак, интерполяционный полином на равномерной сетке дает существенно более высокую точность, чем кусочно-линейная интерполяция. Их погрешности суть (T/N)n+1 max | /(ы+1^1(Ы + 1) и, в лучшем случае, (T/N)2 max | /" |/2 соответственно. Правда, прямое сравнение этих величин невозможно, ведь оценки включают значения разных производных.
Наилучший выбор сетки. Рассмотрим следующую задачу. Можно ли повысить точность интерполяции за счет рационального размещения узлов сетки на интересующем нас интервале [О, T]? Если об интерполируемой функции мы не знаем ничего, кроме того что она JV + 1 раз непрерывно дифференцируема, единственным средством улучшить оценку остаточного члена является выбор узлов сетки {fn} решением характерной задачи на минимакс:
JV
min max П('-о
tv .... t„ о «¦=0
Эта задача, известная как задача о построении полинома, наименее уклоняющегося от нуля на заданном интервале [0, 7 ] (с нормировкой «коэффициент при старшей степени t равен единице»), была решена (по другому поводу) П. JI. Чебышевым.
§3]
ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ
35
Таким образом, «наилучшей» является сетка, узлы которой совпадают с корнями полинома Чебышева степени N на интервале [О, Г]. Для этих корней имеются простые явные формулы. Чтобы не отвлекаться, приведем необходимые нам сведения о полиномах Чебышева в конце параграфа. Заметим только, что это один из важнейших объектов численного анализа, и в дальнейшем мы еще не раз встретимся с задачами, в которых полиномы Чебышева окажутся очень полезными для построения эффективных вычислительных методов. Сетки с узлами, равными корням полинома Чебышева, играют большую роль в разных вопросах и называются чебышевскими.
Чебышевская сетка является «наилучшей» с точки зрения целого класса функций, выделенного, например, условием |/^iV+1)(0l ^ С. Для конкретной же функции f(t) может оказаться лучшей своя индивидуальная сетка, и такие сеі-ки часто используются в расчетах. Построение индивидуальной сетки требует гораздо большей информации о строении функции. При построении сетки используются простые соображения: например, сетка должна быть гуще там, где функция «устроена» более сложно, имеет резкие градиенты, совершает частые колебания. Там же, где функция очень гладкая, сетку можно взять более редкой.
Собственно говоря, приведенные соображения тоже связаны с оценкой производных, но если эти производные принимают на [О, T] существенно разные значения, имеет смысл (если это технически возможно) разбить интервал [О, T] на части с разными оценками производной и на каждой части строить сетку по-своему. Например, один из практических принципов построения сетки — «принцип равномерности погрешности». При использовании кусочно-линейной интерполяции для гладкой функции этот принцип рекомендует расставлять узлы таким образом, чтобы величина
(*n + l ~ O2 ^п + 1/2’ ГДЄ + 1/2
оценка I/''I на [tn, *„+1], была более
или менее равномерной, не зависящей от п. Рисунок 4 поясняет, что примерно имеется в виду под индивидуальной сеткой.
Сравним точности интерполяций на равномерной и чебышевской сетках. Мы приведем только результат, сравнив оценки величины
Рис. 4
max
о
1
(ЛГ + 1)!
тП U-U
(10)
п=0
для двух типов сеток. В случае равномерной сетки, как было показано выше, эта величина оценивается числом (T/N)n+1/(N + I). В 2*
36
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[Ч. I
случае чебышевской сетки, как следует из сведений, приведенных в конце параграфа, для (10) имеем оценку (T/4)n/(N + 1)!. Используя формулу Стирлинга Ni (N/e)N, получаем выигрыш примерно в (4/е)N раз. Это само по себе может быть и не очень много. Однако чебышевские сетки обладают и более важными преимуществами перед равномерными. Перейдем к их обсуждению.
Устойчивость интерполяционного полинома относительно погрешностей вычисления f. Рассмотрим следующий вопрос: пусть таблица {/„} вычислена не точно, а с погрешностями, связанными хотя бы с конечной разрядностью машинной арифметики. Как повлияет неточность вычисления / на интерполяционный полином? Итак, пусть полином вычисляется по таблице {/n + Sfl), где Sfl — погрешность, относительно которой нам известна только оценка I Sn I ^ 6. Тогда «машинный» интерполяционный многочлен связан с истинным очевидным соотношением
Ln (t; {О. {/. + Sn» = Ln (и {/„}, {/„}) + Ln (*; {*„}, {6„}). (11)
Это следствие линейности полинома по /„.
Второе слагаемое правой части (11) есть погрешность, связанная с неточностью вычисления /. Она и подлежит оценке. Естественно в качестве меры погрешности взять величину
max { max |Ln (t; {tn}, {6„}|},
|6Л|«6
т.е. оценить ее при самой неблагоприятной комбинации погрешностей Sre в пределах заданной точности. В силу линейности по Sra можно заменить эту величину на 6т|({ґи}), где
