Интерполяция алгебраическими многочленами

Интерполяция алгебраическими многочленами функции f(x) на отрезке [a, b] — построение многочлена P_n(x) степени меньшей или равной n, принимающего в узлах интерполяции x₀, x₁, ..., x_n значения f(x_i):

$P_n(x_i) = f(x_i), \quad i = 0, 1, ..., n$

Система уравнений, определяющих коэффициенты такого многочлена, имеет вид

$P_n(x_i) = a_0 + a_1x_i + a_2x_i^2 + ... + a_nx_i^n = f(x_i), \quad i = 0, 1, ..., n$

Её определителем является определитель Вандермонда.

$\triangle = \begin{vmatrix} 1 & x_0 & x_0^2 & ... & x_0^n \\ 1 & x_1 & x_1^2 & ... & x_1^n \\ ....... \\ 1 & x_n & x_n^2 & ... & x_n^n\end{vmatrix} = \prod_{i,j=1, i < j}^n (x_i - x_j)$

Он отличен от нуля при всяких попарно различных значениях x_i, и интерполирование функции f по её значениям в узлах x_i с помощью многочлена P_n(x) всегда возможно и единственно.

Применение

Полученную интерполяционную формулу $f(x) \approx P_n(x)$ часто используют для приближённого вычисления значений функции f при значениях аргумента x, отличных от узлов интерполирования. При этом различают интерполирование в узком смысле, когда $x \in \left[ x_0, x_n \right]$, и экстраполирование, когда $x \in \left[ a, b \right]$, $x \not\in \left[ x_0, x_n \right]$

Задача интерполяции

Пусть в пространстве заданы $n$ точек $P_1, P_2,\dots, P_n$, которые в некоторой системе координат имеют радиус-векторы $\mathbf{r}_1, \mathbf{r}_2,\dots, \mathbf{r}_n$.

Задача интерполяции состоит в построении кривой, проходящей через указанные точки в указанном порядке.

Решение задачи

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

Будем строить кривые в виде $\mathbf{r}(t)$, где параметр $t$ изменяется на некотором отрезке $~ [a, b]$: $~ a\leq t \leq b$. Введем на отрезке $~ [a, b]$ сетку $~ \{t_i\}$ из $~ n$ точек: $~ a=t_1 < t_2 < t_3<\dots < t_n=b$ и потребуем, чтобы при значении параметра $~ t=t_i$ кривая проходила через точку $~ P_i$, так что $~ \mathbf{r}(t_i)=\mathbf{r}_i$.

Введение параметризации и сетки может быть выполнено различными способами. Обычно выбирают либо равномерную сетку, полагая $~ a=0$, $~ b=n-1$, $~ t_i=i-1$, либо, что более предпочтительно, соединяют точки отрезками и в качестве разности значений параметра $~ t_{i+1}-t_i$ берут длину отрезка $~ \mathbf{r}_{i+1}- \mathbf{r}_{i}$.

Одним из распространенных способов интерполяции является использование кривой в виде многочлена от $~ t$ степени $~ n-1$, то есть в виде функции

$~ \mathbf{r}(t) = \mathbf{p}^{(n-1)}(t) =\sum_{k=1}^n \mathbf{a}_k t^{n-k}$

Многочлен имеет $~ n$ коэффициентов $~ \mathbf{a}_k$, которые можно найти из условий $~ \mathbf{r}(t_i)=\mathbf{r}_i$.

Эти условия приводят к системе линейных уравнений для коэффициентов $~ \mathbf{a}_k$

$~ \begin{pmatrix} 1 & t_1 & t_1^2 & \ldots & t_1^{n-1} \\ 1 & t_2 & t_2^2 & \ldots & t_2^{n-1} \\ \vdots & \vdots& \vdots& & \vdots \\ 1 & t_n & t_n^2 & \ldots & t_n^{n-1} \end{pmatrix} \begin{pmatrix} \mathbf{a}_{n} \\ \mathbf{a}_{n-1} \\ \vdots \\ \mathbf{a}_1 \end{pmatrix}= \begin{pmatrix} \mathbf{r}_1 \\ \mathbf{r}_2 \\ \vdots \\ \mathbf{r}_n \end{pmatrix}$

Обратим внимание, что нужно решить три системы уравнений: для $~ x$, $~ y$ и $~ z$ координат. Все они имеют одну матрицу коэффициентов, обращая которую, по значениям радиус-векторов $~ \mathbf{r}_i$ точек вычисляются векторы $~ \mathbf{a}_k$ коэффициентов многочлена. Определитель матрицы

$~ W(t_1, t_2, \ldots , t_n) = \begin{vmatrix} 1 & t_1 & t_1^2 & \ldots & t_1^{n-1} \\ 1 & t_2 & t_2^2 & \ldots & t_2^{n-1} \\ \vdots & \vdots& \vdots& & \vdots \\ 1 & t_n & t_n^2 & \ldots & t_n^{n-1} \end{vmatrix} = \prod_{{i,j, i>j}} (t_i -t_j)$

называется определителем Вандермонда. Если узлы сетки не совпадают, он отличен от нуля, так что система уравнений имеет решение.

Кроме прямого обращения матрицы, имеются несколько других способов вычисления интерполяционного многочлен. В силу единственности многочлена речь идет о различных формах его записи.

Преимущества

• Для заданного набора точек и сетки параметра кривая строится однозначно.
• Кривая является интерполяционной, то есть проходит через все заданные точки.
• Кривая имеет непрерывные производные любого порядка.

Недостатки

• С ростом числа точек порядок многочлена возрастает, а вместе с ним возрастает число операций, которое нужно выполнить для вычисления точки на кривой.
• С ростом числа точек у интерполяционной кривой могут возникнуть осцилляции (см. пример ниже).

Пример

Интерполяция на последовательности сеток. Пример Рунге.

Основная статья: Феномен Рунге

Классическим примером (Рунге), показывающим возникновение осцилляций у интерполяционного многочлена, служит интерполяция на равномерной сетке значений функции

$~ f(x) = \frac{1}{1+x^2}$

Введем на отрезке $~ [-5, 5]$ равномерную сетку $~ x_i=-5+(i-1)h$, $~ h=10/(n-1)$, $~ 1 \leq i \leq n$ и рассмотрим поведение многочлена

$~ y(x) = \sum_{i=1}^n a_i x^{n-i}$

который в точках $~ x_i$ принимает значения $~ y_i=1/(1+x_i^2)$. На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при $~ n=3, 5, 9$:

• интерполяция на сетке $~ x_1=-5, x_2=0, x_3=5$ — квадратичная парабола;
• интерполяция на сетке $~ x_1=-5, x_2=-2.5, x_3=0, x_4=2.5, x_5=5$ — многочлен четвертой степени;
• интерполяция на сетке $~ x_1=-5, x_2=-3.75, x_3=-2.5, x_4=-1.25, x_5=0, x_6=1.25, x_7=2.5, x_8=3.75, x_9=5$ — многочлен восьмой степени.

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

См. также

• Интерполяционный многочлен Лагранжа
• Интерполяционный многочлен Ньютона
• Вейвлет