Введение в вычислительную физику - Федоренко Р.П.
ISBN 5-7417-0002-0
Скачать (прямая ссылка):
Первая задача состоит в том, чтобы сопоставить этой функции конечный набор чисел, по которому ее можно будет восстановить (конечно, с той или иной точностью). Задачу будем решать очень просто. Введем на [О, TJ некоторую сетку
t0<tl<t%<...<tlf, гпЄ[0, Г], и = О, I, ..., N.
В частности, ради простоты будем использовать равномерную сетку с шагом т = T/N: tn = пх.
В качестве конечномерного представителя функции f(t) используем таблицу чисел
if JLо> гДе /и = /СО-
Оператор, сопоставляющий функции / такую таблицу, играет большую роль в современных методах приближенных вычислений. Ему
§3]
ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ
29
присвоено особое наименование «оператор ограничения на сетку» (Restriction) и стандартное обозначение Rs, где индекс s — символ
сетки Wn=O- Существуют и другие способы составления таблиц, представляющих функцию /. Например, можно составить таблицу пар чисел {/„, /'„} — значений f(tn) и производных f'(tn), но мы ограничимся самым простым способом.
Теперь возникает следующая задача: по таблице {/„} восстановить непрерывную функцию. Разумеется, это будет какая-то другая функция^/(О и надо оценить «потерю информации», т.е. величину 1/(0 — 7(0 I при t Є [О, Т]. Это восстановление неоднозначно, оно осуществляется тем или иным оператором интерполяции (обозначим его /), а потеря информации, как легко догадаться, зависит от сетки, типа оператора I и свойств гладкости функции /. Итак, мы имеем дело со схемой
/(0 - {/„}?-о - 7(0- (!)
Ниже мы рассмотрим некоторые конкретные формы оператора интерполяции /.
Кусочно-линейная интерполяция. Это простейший вариант I, рассчитанный на функции / с небольшим запасом гладкости. Сам аппарат очень прост: точки (tn, /„) соединяются отрезками прямых
7(0 = * є К’ '«+іJ-
‘п+1 1п
Таким образом, функция f{t) рассматривается как аппроксимация функции /(0 и следует оценить погрешность 1/(0 ~ 7(01 • Проблемы такого сорта возникли в классической математике, когда появилась необходимость работать с некоторыми специальными функциями (sin, In, exp, функции Бесселя и т.д.), а естественным способом описания функций были таблицы. В наше время способом описания многих функций стали алгоритмы их вычисления, «запаянные» в процессорах карманных, например, калькуляторов.
Итак, предположим, что функция f{t) всего лишь удовлетворяет условию Липшица с постоянной С:
1/(0 -/(Ol «Cl*- t'\, Vt, ґ'Є[0,Г]. (2)
В этом случае погрешность интерполяции оценивает следующая тео^ рема.
Теорема 1. Для любых t Є [ 0 , Г] погрешность
1/(0 — 7(01 ^ Сх/2> гДе х = max (ґп+1 — tn).
Эта оценка неулучшаема в классе (2).
30 ОСНОВЫ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ [Ч. I
Доказательство. Пусть t Є [tk, /4+1]. Тогда, вводя обозначение h = tk+1 — tk, представим t в виде
t = tk + ah, а Є (0, 1).
Очевидно, f{t)=- a fk+1 + (I — a) fk. Проведем оценку:
1/(0 - 7(0 1 = 1« fk+1 -Ь (1 - «) At - а /(0 - (1 - «) /(01 <
^ a|/t+i-/(0l + (1-а) I/*-/(01-
Ho /А+1 = f(tk + h), поэтому
I/*+!¦-/(01 = \f(tk + h)-f(tk + ah) \ <С(1-а)А. Аналогично
|/*-/(01<СаА.
Итак,
1/(0 - /(01 jS 2<*(1 - a)Ch *? C/z/2.
Тот же аппарат кусочно-линейной интерполяции имеет более высокую точность, если функция /(0 имеет ограниченную вторую производную.
Теорема 2. Пусть |/''(O I ^ С- Тогда
1/(0 -7(01 *sCx2/2, * є [0,74,
и эта оценка неулучшаема.
Доказательство этой теоремы непосредственно следует из теоремы 3 (см. ниже). Пример функции, на которой достигается эта оценка, предоставим построить читателю.
Кусочно-линейная интерполяция послужит нам поводом для введения некоторых полезных объектов. С сеткой {tn} можно связать набор стандартных функций — интерполяционный базис, состоящий из функций ф°(0, <рЧ0> •••» 9^(0- (Правильнее было бы использовать обозначения Рис з типа yaN(t, (U?U), содержащие все
определяющие базис величины, но мы этого делать не будем.) Каждая функция ф"(0 сопоставляется своему узлу сетки In и определяется следующим образом: в узлах сетки
lPn(tIc) = в остальных точках она вычисляется кусочно-линейной интерполяцией (рис. 3). Используя этот базис, можно представить / в форме
7(0 = 2 /„*"(0-
я = 0
ИНТЕРПОЛЯЦИЯ ФУНКЦИЙ
31
Аппарат кусочно-линейной интерполяции можно трактовать и как способ непрерывного восполнения сеточной функции до функции, определенной при всех t Є [О, Т], и как способ конечномерной аппроксимации некоторого функционального пространства — в данном случае, пространства непрерывных функций, имеющих кусочно-непрерывную первую производную. Наконец, функции базиса ір'1(г) можно рассматривать и как простейший пример так называемых «конечных элементов». Это один из весьма важных и широко используемых в современных численных методах объектов, позволяющих моделировать (аппроксимировать) те или иные функциональные пространства. Ниже мы обсудим это подробнее.
Рассмотрев интерполяцию функций с малым запасом гладкости, обратимся к аппарату, напротив, рассчитанному на очень гладкие функции.
Интерполяционный . полином. Итак, пусть имеется сетка (iJn=O И сеточная функция {/п}^=0, являющаяся ограничением некоторой гладкой функции f(t) на сетку. Через точки (tn, fn) проведем полином степени N. Другими словами, построим полином Lit) степени N, коэффициенты которого (их N + 1) определяются из (JV+ 1)-го условия:
