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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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)

Он отличен от нуля при всяких попарно различных значениях xi, и интерполирование функции f по её значениям в узлах xi с помощью многочлена Pn(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 — многочлен восьмой степени.

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

См. также[править | править исходный текст]