Поліноміальна інтерполяція

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Поліноміальна інтерполяція (Інтерполяція алгебраїчними многочленами) функції f(x) на відрізку [a, b] - побудова многочлена Pn(x) степеня меншого або рівного n, що приймає у вузлах інтерполяції x0, x1, ..., xn значення f(xі):

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)

Він відмінний від нуля при всяких попарно різних значеннях xі, і інтерполяція функції f по її значеннях у вузлах xі за допомогою многочлена 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 - многочлен восьмого степеня.

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

Див. також[ред.ред. код]