Участник:VJKarpov

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

Пусть в пространстве заданы $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})$. На рис. \ref{FigRunge} представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при $~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$ — многочлен восьмой степени.

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