WikiSort.ru - Не сортированное

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

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

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

${\displaystyle P_{n}(x_{i})=a_{0}+a_{1}x_{i}+a_{2}x_{i}^{2}+...+a_{n}x_{i}^{n}=f(x_{i}),\quad i=0,1,...,n}$

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

${\displaystyle \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, и интерполирование функции f по её значениям в узлах x_i с помощью многочлена P_n(x) всегда возможно и единственно.

Применение

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

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

Пусть в пространстве заданы ${\displaystyle n}$ точек ${\displaystyle P_{1},P_{2},\dots ,P_{n}}$ , которые в некоторой системе координат имеют радиус-векторы ${\displaystyle \mathbf {r} _{1},\mathbf {r} _{2},\dots ,\mathbf {r} _{n}}$ .

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

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

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

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

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

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

${\displaystyle \mathbf {r} (t)=\mathbf {p} ^{(n-1)}(t)=\sum _{k=1}^{n}\mathbf {a} _{k}t^{n-k}}$

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

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

${\displaystyle {\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}}}$

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

${\displaystyle 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})}$

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

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

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

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

Недостатки

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

Пример

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

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

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

${\displaystyle y(x)=\sum _{i=1}^{n}a_{i}x^{n-i}}$

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

• интерполяция на сетке ${\displaystyle x_{1}=-5,x_{2}=0,x_{3}=5}$ — квадратичная парабола;
• интерполяция на сетке ${\displaystyle x_{1}=-5,x_{2}=-2.5,x_{3}=0,x_{4}=2.5,x_{5}=5}$ — многочлен четвертой степени;
• интерполяция на сетке ${\displaystyle 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}$ — многочлен восьмой степени.

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

См. также

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