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

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

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

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

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

Применение

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

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

Пусть в пространстве заданы точек , которые в некоторой системе координат имеют радиус-векторы .

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

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

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

Будем строить кривые в виде , где параметр изменяется на некотором отрезке : . Введем на отрезке сетку из точек: и потребуем, чтобы при значении параметра кривая проходила через точку , так что .

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

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

$~ \mathbf{r}(t) = \mathbf{p}^{(n-1)}(t) =\sum_{k=1}^n \mathbf{a}_k t^{n-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}$

Обратим внимание, что нужно решить три системы уравнений: для , и координат. Все они имеют одну матрицу коэффициентов, обращая которую, по значениям радиус-векторов точек вычисляются векторы коэффициентов многочлена. Определитель матрицы

$~ 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}$

Введем на отрезке равномерную сетку , , и рассмотрим поведение многочлена

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

который в точках принимает значения . На рисунке представлены графики самой функции (штрих-пунктирная линия) и трех интерполяционных кривых при :

интерполяция на сетке — квадратичная парабола;
интерполяция на сетке — многочлен четвертой степени;
интерполяция на сетке — многочлен восьмой степени.

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

См. также

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

Light-industry-up.ru

Экосистема промышленности

Публикации