Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Дд=/„. п = 0, 1, ..., N. (3)
Аккуратное обозначение этого полинома есть, очевидно, LN(t\ {tn}, {/„}), но мы будем вспоминать список аргументов только тоща, когда это потребуется по существу дела. Пока аргументы N, {г,;}, {/„} фиксированы, мы их опускаем. Вопросы существования и единственности интерполяционного полинома рассматриваются в анализе (определитель Ван-дер-Монда), мы их решим по ходу дела, написав явно выражение для L. Сначала построим базис из функций <pJv(0 (аккуратнее, {г*})). Функции (p'y(t) — полиномы степе-
ни N, каждый из которых сопоставлен со своим узлом сетки tn таким
образом, что *Pjv(^) = Ьпк. Легко угадать явное выражение для фд,(ґ):
4^(0 = П
/5*П
(Произведение берется по всем индексам, кроме і = «.)
Имея интерполяционный базис, можно написать явное выражение интерполяционного полинома (в так называемой форме Лагранжа):
¦ LN{t; Un], {/„}) = ? Л чй (*;{/„». (4)
і = 0
32
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[Ч.І
Выполнение условий (3) очевидным образом следует из (4). Если записать L в общем виде: L(t) = aN tN + ... + а0, то условия (3) превращаются в N + 1 линейное уравнение для коэффициентов а0, O1, ..., aN. Таблица {/„} определяет правую часть этой системы. Так как для любой такой правой части решение (в форме Лагранжа) существует, то оно в силу известных теорем линейной алгебры и единственно.
Переходя к оценке погрешности интерполяции, введем остаточный член интерполяционного полинома
{*„}. {/„}) = № - LN(t\ {*„}, {/„}). (5)
Точка t может находиться как внутри интервала [О, T] (и тогда говорят об интерполяции), так и вне его (и тогда употреібляют термин экстраполяция). Обозначим а = тіп(ґ, t0) и Ъ = тах(г, tN). Таким образом, t Є [а, й]. Основу для конкретных оценок I f(t) — L(t) I составляет следующая лемма.
Лемма (об остаточном члене). Пусть функция f(t) на [а, Ь] имеет N + 1 ограниченную производную. Тогда
=WTш(ґ ~ *о)(* - h)-(t - tN) f(N+im> (6)
ще X — некоторая (зависящая от t, {tn} и /) точка, о которой известно только, что ? Є [а, Ъ\.
Доказательство. Считая, что і не совпадает ни с одним узлом сетки (при t = tn соотношение (6) очевидным образом выполнено), рассмотрим функцию одного переменного
F(x) = f(x) - L(x) - RN(t) (7)
Об этой функции нам известно, что на [а, Ь] она имеет по меньшей мере N +1 непрерывную производную, поскольку ее имеет функция f(x), а остальные два слагаемых правой части (7) — Яолиномы от х.
Далее, функция F(x) на [а, А] имеет не менее N + 2 нулей. Мы их просто укажем: очевидно, точки x — tn (п — О, 1, ..., N) — нули F(x) в силу того, что f(tn) =L(tn), а третье слагаемое правой части (7) обращается в нуль. В силу определения (5) остаточного члена (N + 2)-м нулем F(x) является точка х = t. Между каждыми двумя нулями непрерывно дифференцируемой функции имеется хотя бы один нуль ее производной. Таким образом, на [а, Ъ] имеется по крайней мере N + 1 нуль F'.
Применяя это рассуждение последовательно к F", F'", ..., установим, что существует точка % Є [а, Ъ] такая, что 7?(л,+1)(^) = 0.
§ 3] ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ 33
Вычислим (N + 1)-ю производную правой части (7), учитывая, что L^N+l\x) = 0, произведение fl (х — tn) = + Axn + ... и его
(N + 1)-я производная равна (N + 1)!:
<8)
Из (8) непосредственно следует утверждение леммы (6).
Выражение (6) для остаточного члена позволяет получить серию более конкретных результатов. Приведем некоторые из них.
Теорема 3 (о точности интерполяции на равномерной сетке). Пусть сетка равномерна, т.е. tn = nx, х = T/N, t Є [О, Г]. Тогда
JV+1
1/(0 — ДО I С= max |/<W+1>(0I. (9)
<e[o,rj
Доказательство. Положим t = tk + ат (а Є (0, 1), к Є О, N-I).,
N
Рассмотрим выражение (t — tn), входящее в формулу (6). Оче-
п — 0
видно,
t — tn = кх + ах — пх = (к + а — и) г.
Таким образом,
п=0 п=0
Для оценки (к + а — n)/(N + 1)! воспользуемся табл. 4, в которой приведены значения | к + а — п | и соответствующим образом расположенные мажорирующие их множители из Ni. Видно, что оцениваемое произведение состоит из множителей, не превосходящих единицы, и дополнительного множителя \/(N + 1). Отсюда следует (9).
Посмотрим, как изменяется оценка при переходе к задаче экстраполяции. Она ухудшается при удалении точки t от «носителя информации» — интервала [ґ0, tN}. Анализ, аналогичный только что приведенному, показывает, что:
1) при t Є [ґд,, tN + x]
\RN(t)\< x»+' max |/<"+1>(Ol;
2) при t Є [ґд, + x, tN + 2x]
|J?w(0|.<(JV+s2)tw+1 max |/^+1ЧОИ
2 — 1833
34
ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ
[4-І
3) при t Є Itjv + 2т, tN + Зт}
IRnV) I « <* + »<#±» x*+i max I/("-”>(01;
И Т.д.
Таким образом, оценка ухудшается как за счет появления множителей, так и за счет увеличения оценки \f(N+l)\ при расширении интервала. Хотя это — оценка сверху, она правильно отражает общую тенденцию: экстраполяция функции менее надежна, чем интерполяция, и ее точность резко падает по мере удаления от носителя информации. (Этим, в частности, объясняется ненадежность