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

Интерполя́ция алгебраи́ческими многочле́нами функции $f(x)$$f(x)$ действительного аргумента на отрезке $[a,b]$$[a,b]$ — нахождение коэффициентов многочлена $P_n(x)$$P_n(x)$ степени меньшей или равной $n$$n$, принимающего при значениях аргумента $x_0,x_1,\dots <!--\; \dots \; -->,x_n$$x_0,\ x_1,\ \ldots,\ x_n$ значения $f(x_i)$$f(x_{i})$, множество $x_0,x_1,\dots <!--\; \dots \; -->,x_n$$x_0,\ x_1,\ \ldots,\ x_n$ называют узлами интерполяции:

$P_n(x_i)=f(x_i),i=0,1,...,n.$$P_{n}(x_{i})=f(x_{i}),\quad i=0,\ 1,\ ...,\ n.$

Система линейных алгебраических уравнений, определяющих коэффициенты $a_i$$a_{i}$ такого многочлена, имеет вид:

$P_n(x_i)=a_0+a_1{x}_i+a_2{x}_i^2+\dots <!--\; \dots \; -->+a_n{x}_i^n=f(x_i),i=0,1,\dots <!--\; \dots \; -->,n.$$P_{n}(x_{i})=a_{0}+a_{1}x_{i}+a_{2}x_{i}^{2}+\ldots +a_{n}x_{i}^{n}=f(x_{i}),\quad i=0,\ 1,\ \ldots ,\ 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=0 \atop i>j}^{n}(x_{i}-x_{j}).$

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

ПрименениеПравить

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

Задача интерполяции в пространствеПравить

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

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

Решение задачиПравить

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

Будем строить кривые в виде $\mathbf{r}(t)$${\mathbf {r}}(t)$ , где параметр $t$$t$  изменяется на некотором отрезке $[a,b]$$[a,\ b]$ :

$a\le <!--\; \le \; -->t\le <!--\; \le \; -->b$$a\leq t\leq b$ .

Введем на отрезке $[a,b]$$[a,b]$  сетку $\{t_i\}$$\{t_{i}\}$  из $n$$n$  точек: $a=t_{1}<t_{2}<t_{3}<\dots <t_{n}=b$  и потребуем, чтобы при значении параметра $t=t_i$$t=t_{i}$  кривая проходила через точку $P_i$$P_{i}$ , так что $\mathbf{r}(t_i)={\mathbf{r}}_i.$$\mathbf {r} (t_{i})=\mathbf {r} _{i}.$ 

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

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

$\mathbf{r}(t)={\mathbf{p}}^{(n-<!--\; -\; -->1)}(t)=\underset{k=1}{\overset{n}{\sum <!--\; \sum \; -->}}{\mathbf{a}}_k{t}^{n-<!--\; -\; -->k}.$$\mathbf {r} (t)=\mathbf {p} ^{(n-1)}(t)=\sum _{k=1}^{n}\mathbf {a} _{k}t^{n-k}.$ 

Многочлен имеет $n$$n$  коэффициентов ${\mathbf{a}}_k$$\mathbf {a} _{k}$ , которые можно найти из условий:

$\mathbf{r}(t_i)={\mathbf{r}}_i.$$\mathbf {r} (t_{i})=\mathbf {r} _{i}.$ 

Эти условия приводят к системе линейных уравнений для коэффициентов ${\mathbf{a}}_k$$\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$$x$ , $y$$y$  и $z$$z$  координат. Все они имеют одну матрицу коэффициентов, обращая которую по значениям радиус-векторов ${\mathbf{r}}_i$${\mathbf {r}}_{i}$  точек вычисляются векторы ${\mathbf{a}}_k$$\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})$ 

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

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

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

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

НедостаткиПравить

• С ростом числа точек порядок многочлена возрастает, а вместе с ним возрастает число операций, которое нужно выполнить для вычисления точки на кривой.
• С ростом числа точек у интерполяционной кривой могут возникнуть осцилляции (см. пример ниже).
• С ростом числа точек плохо подходит для экстраполяции, так как значение многочлена степени $n>0$$n>0$  вне отрезка интерполяции всегда расходится к бесконечности (тем быстрее, чем больше $n$$n$ ) вне зависимости от сходимости экстраполируемой функции.

ПримерПравить

 

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

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

Классическим примером (Рунге), показывающим возникновение осцилляций у интерполяционного многочлена, служит интерполяция на равномерной сетке значений функции $f(x)=\frac{1}{1+x^2}.$$f(x)={\frac {1}{1+x^{2}}}.$ 

Введем на отрезке $[-<!--\; -\; -->5,5]$$[-5,5]$  равномерную сетку $x_i=-<!--\; -\; -->5+(i-<!--\; -\; -->1)h$$x_{i}=-5+(i-1)h$ , $h=10/(n-<!--\; -\; -->1)$$h=10/(n-1)$ , $1\le <!--\; \le \; -->i\le <!--\; \le \; -->n$$1\leq i\leq n$  и рассмотрим поведение многочлена $y(x)=\underset{i=1}{\overset{n}{\sum <!--\; \sum \; -->}}{a}_i{x}^{n-<!--\; -\; -->i},$$y(x)=\sum _{i=1}^{n}a_{i}x^{n-i},$  который в точках $x_i$$x_{i}$  принимает значения $y_i=1/(1+x_i^2)$$y_{i}=1/(1+x_{i}^{2})$ .

На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при $n=3,5,9$$n=3,5,9$ :

• интерполяция на сетке $x_1=-<!--\; -\; -->5,x_2=0,x_3=5$$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}=-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$$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$  — многочлен восьмой степени.

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

См. такжеПравить

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