Лекция 16.

ИНТЕРПОЛИРОВАНИЕ

§ 16.1. Постановка задачи интерполирования

Пусть на отрезке [a, b] заданы n+1 точки a=x₀, x₁, …, x_n=b, которые называются узлами интерполяции, и значения некоторой функции f(x) в этих точках

f(x₀)=y₀, f(x₁)=y₁, …, f(x_n)=y_n (16.1)

Р

y=φ(x)

M_n

y_n

y=f(x)

y₁

M₁

M₀

y₀

0 x₀ x₁ x_n x

y

исунок 16.1. Геометрическая интерпретация задачи интерполирования

Рис. 1.1

Рис. 16.1.

Требуется построить функцию φ(x) близкую к f(x) и принимающую в узлах интерполяции те же значения, что и f(x), т.е. такую, что

φ(x₀)=y₀, φ(x₁)=y₁, …, φ(x_n)=y_n. (16.2)

Функция φ(x) называется интерполирующей или интерполяционной для функции f(x) на отрезке [a, b], если ее значения в узлах интерполяции совпадают со значениями функции f(x).

Функция φ(x)должна обладать "хорошими" свойствами, позволяющими легко производить над ней те или иные аналитические или вычислительные операции. Геометрически это означает, что нужно найти кривую y=φ(x), проходящую через заданную систему точек M_i(x_i, y_i) (i=0, 1, 2, …, n) (рис. 16.1).

В такой общей постановке задача может иметь бесчисленное множество решений или совсем не иметь решений в зависимости от того класса функций, в котором ищется интерполяционная функции. Однако эта задача становится однозначной, если вместо произвольной функции φ(x) искать полином P_n(x) степени не выше n, удовлетворяющий условиям (16.2), т.е. такой, что P_n(x₀)=y₀, P_n(x₁)=y₁, …, P_n(x_n)=y_n. В этом случае будем говорить о полиномиальной аппроксимации. Для вычислительной математики многочлены привлекательны тем, что они являются линейными функциями своих параметров (коэффициентов), и их вычисления сводятся к выполнению конечного числа простейших арифметических операций – сложения и умножения.

Полученную интерполяционную формулу y=φ(x) обычно используют для приближенного вычисления значений данной функции f(x) для значений аргумента x, отличных от узлов интерполирования. Такая операция называется интерполированием функции f(x). При этом различают интерполирование в узком смысле, когда x[x₀, x_n], и экстраполирования, когда x[x₀, x_n]. В дальнейшем под термином интерполирование будем понимать как первую, так и вторую операцию.

§ 16.2. Интерполяционный многочлен Лагранжа

Интерполяционная формула Лагранжа используется для произвольно заданных узлов интерполирования.

Пусть в точках x₀, x₁, …, x_n таких, что a x₀<…< x_nb, известны значения функции y=f(x), т.е. на отрезке [a, b] задана табличная (сеточная) функция f(x):

x	x0	x1	…	xn
y	y0	y1	…	yn

(16.3)

Требуется построить полином

L_n(x) =a₀ + a₁x + a₂x² + … + a_n xⁿ (16.4)

степени n, имеющий в заданных узлах x₀, x₁, …, x_n те же значения, что и функция f(x), т.е. такой, что

L_n(x_i)=y_i (i=0, 1, 2,…, n).

Это значит найти его n+ 1 коэффициент a₀, a₁, a₂ , …, a_n . Для этого имеется как раз п + 1 условие (16.2). Таким образом, чтобы многочлен (16.4) был интерполяционным для функции (16.3), нужно, чтобы его коэффициенты удовлетворяли системе уравнений

,

Из курса алгебры известно, что определитель этой линейной системы (так называемый определитель Вандермонда) отличен от нуля, т.е. решение этой системы существует и единственно. Однако практическое построение интерполяционного многочлена таким путем малоэффективно. Поэтому изберем другой путь.

Будем строить многочлен n-ой степени L_n(x) в виде линейной комбинации многочленов n-й же степени l_i(x) (i=0, 1, 2,…, n). Индекс i показывает номер многочлена. Для того чтобы этот многочлен был интерполяционным для функции f(x), достаточно зафиксировать в качестве коэффициентов c_i этой линейной комбинации заданные в табл. (16.3) значения y_i=f(x_i), а от базисных многочленов l_i(x) потребовать выполнения условия

(16.5)

где _ij – символ Кронекера.

В этом случае для многочлена в каждом узле x_j (j{0, 1,…,n}), в силу (2.2), справедливо

L_n(x_j)=l₀(x_j)y₀+…+l_j-1(x_j)y_j-1+l_j(x_j)y_j+l_j+1(x_j)y_j+1+…+l_n(x_j)y_n=0+…+0+y_j+0+…+0=y_j

Чтобы конкретизировать базисные многочлены l_i(x), учтем, что они должны удовлетворять условиям (16.5). Равенство нулю i-го многочлена во всех узлах, кроме i-го, означает, что l_i(x) можно записать в виде

l_i(x)=A_i(x-x₀)…(x-x_i-1)(x-x_i+1)…(x-x_n),

а коэффициент A_i этого представления легко получается из содержащегося в (16.5) требования l_i(x_i)=1. Подставляя в выражение l_i(x) значение x=x_i и приравнивая результат единице, получаем:

Таким образом, базисные многочлены Лагранжа имеют вид:

,

а искомый интерполяционный многочлен Лагранжа:

(16.6)

Пример. Построить интерполяционный полином для функции y=sin x.

Возьмем сетку, состоящую из трех точек: x₀=0; x₁= ; x₂= , выпишем соответствующие этим аргументам значения функции sin x: y₀=0; y₁= ; y₂=1.

Построим по этой таблице интерполяционный полином второй степени. По формуле Лагранжа (2.3):

.

Легко проверить, что в точках сетки этот полином принимает нужные значения. Чтобы получить представление о погрешности интерполирования, сравнивая значения sin x и интерполяционного полинома в точке х= .

.

Значительная величина погрешности определяется тем, что на отрезке длиной мы взяли грубую сетку, состоящую всего из трех точек. Чтобы улучшить точность интерполирования, нужно либо увеличить число точек n и повысить соответственно степень интерполяционного полинома L_n(x), либо уменьшить длину исходного отрезка.

Будем выяснять величину отклонения f(x) от L_n(x) в произвольной точке x[a, b], иначе, величину остаточного члена

R_n(x)= f(x)  L_n(x)

интерполяционной формулы Лагранжа (16.6) в предположении, что f(x)  Сⁿ⁺¹[a, b], т.е. данная функция n + 1 раз непрерывно дифференцируема.

Обозначим

определенный через узлы x₀, x₁, …, x_n многочлен (n + 1)-й степени. Тогда можно показать, что

(16.7)

где   некоторая точка из промежутка интерполяции (a, b).

Теперь можно пытаться отвечать на вопросы о погрешности приближенного вычисления значения f(x) с помощью L_n(x) в какой-либо конкретной точке промежутка [a, b] о величине максимальной погрешности, допускаемой при подмене функции f(x) многочленом L_n(x) на отрезке [a, b] о сходимости интерполяционного процесса, т.е. о том, имеет ли место (f(x), L_n(x)) 0, при n по метрике (у) того или иного определенного на [a, b] функционального пространства.

Так, если известна величина

'

то оценить абсолютную погрешность интерполяционной формулы (16.6) в любой точке [a, b] можно с помощью неравенства

Максимальная погрешность интерполирования на отрезке [a, b] оценивается величиной

(16.8)

Так как максимумы модулей функций /^(я+1)(x) и П_n+1(х) достигаются, вообще говоря, в разных точках отрезка [a, b], то более точной, но более трудно реализуемой по сравнению с (16.8) следует считать оценку

Недостатком интерполяционной формулы Лагранжа является то, что каждое слагаемое зависит от всех узлов интерполяции. При добавлении узла интерполяции и, следовательно, повышении порядка полинома необходимо вычислять не только слагаемое, относящееся к новому узлу, но и перевычислять заново слагаемые, относящиеся ко всем узлам интерполяции.