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

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

$P_n(x_i)=f(x_i),i=0,1,...,n$

Система рівнянь, що визначають коефіцієнти такого многочлена, має вигляд

$P_n(x_i)=a_0+a_1{x}_i+a_2{x}_i^2+...+a_n{x}_i^n=f(x_i),i=0,1,...,n$

Її визначником є визначник Вандермонда.

$\mathrm{△}=\left|\begin{array}{ccccc}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{array}\right|=\prod _{i,j=1,i<j}^n(x_i-x_j)$

Він відмінний від нуля при всяких попарно різних значеннях x_і, і інтерполяція функції f по її значеннях у вузлах x_і за допомогою многочлена P_n(x) завжди можлива і єдина.

Застосування

Отриману інтерполяційну формулу $f(x)\approx P_n(x)$ часто використовують для наближеного обчислення значень функції f при значеннях аргументу x, відмінних від вузлів інтерполяції. При цьому розрізняють інтерполяцію у вузькому значенні, коли $x\in [x_0,x_n]$, і екстраполяцію, коли $x\in [a,b]$, $x\in ̸[x_0,x_n]$

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

Нехай у просторі задані $n$ точок $P_1,P_2,\dots ,P_n$, які в деякій системі координат мають радіус-вектори ${𝐫}_1,{𝐫}_2,\dots ,{𝐫}_n$.

Завдання інтерполяції полягає в побудові кривої, що проходить через зазначені точки у зазначеному порядку.

Розв'язання задачі

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

Будемо будувати криві у вигляді $𝐫(t)$, де параметр $t$ змінюється на деякому відрізку $[a,b]$: $a\le t\le b$. Введемо на відрізку $[a,b]$ сітку $\{t_i\}$ з $n$ точок: $a=t_1<t_2<t_3<\dots <t_n=b$ і зажадаємо, щоб при значенні параметра $t=t_i$ крива проходила через точку $P_i$, так що $𝐫(t_i)={𝐫}_i$.

Введення параметризації й сітки може бути виконане різними способами. Звичайно вибирають або рівномірну сітку, вважаючи $a=0$, $b=n-1$, $t_i=i-1$, або, що більш переважно, з'єднують точки відрізками й як різницю значень параметра $t_{i+1}-t_i$ беруть довжину відрізка ${𝐫}_{i+1}-{𝐫}_i$.

Одним з розповсюджених способів інтерполяції є використання кривої у вигляді многочлена від $t$ степеня $n-1$, тобто у вигляді функції

$𝐫(t)={𝐩}^{(n-1)}(t)=\sum _{k=1}^n{𝐚}_k{t}^{n-k}$

Многочлен має $n$ коефіцієнтів ${𝐚}_k$, які можна знайти з умов $𝐫(t_i)={𝐫}_i$.

Ці умови приводять до системи лінійних рівнянь для коефіцієнтів ${𝐚}_k$

$\left(\begin{array}{ccccc}1& t_1& t_1^2& \dots & t_1^{n-1}\\ 1& t_2& t_2^2& \dots & t_2^{n-1}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& t_n& t_n^2& \dots & t_n^{n-1}\end{array}\right)\left(\begin{array}{c}{𝐚}_n\\ {𝐚}_{n-1}\\ ⋮\\ {𝐚}_1\end{array}\right)=\left(\begin{array}{c}{𝐫}_1\\ {𝐫}_2\\ ⋮\\ {𝐫}_n\end{array}\right)$

Звернемо увагу, що потрібно розв'язати три системи рівнянь: для $x$, $y$ і $z$ координат. Усі вони мають одну матрицю коефіцієнтів, знаходячи обернену до якої, за значеннями радіус- векторів ${𝐫}_i$ точок обчислюються вектори ${𝐚}_k$ коефіцієнтів многочлена. Визначник матриці

$W(t_1,t_2,\dots ,t_n)=\left|\begin{array}{ccccc}1& t_1& t_1^2& \dots & t_1^{n-1}\\ 1& t_2& t_2^2& \dots & t_2^{n-1}\\ ⋮& ⋮& ⋮& & ⋮\\ 1& t_n& t_n^2& \dots & t_n^{n-1}\end{array}\right|=\prod _{i,j,i>j}(t_i-t_j)$

називається визначником Вандермонда. Якщо вузли сітки не збігаються, він відмінний від нуля, так що система рівнянь має розв'язок.

Крім прямого знаходження оберненої матриці, є інші способи обчислення інтерполяційного многочлена. У силу одиничності многочлена мова йде про різні форми його запису.

Похибки інтерполяції

Інтерполюючи певну функцію f поліномом степеня Шаблон:Mvar у точках x₀,...,x_n ми отримуємо похибку

$f(x)-p_n(x)=f[x_0,\dots ,x_n,x]\prod _{i=0}^n(x-x_i)$

де

$f[x_0,\dots ,x_n,x]$

це розділена різниця.

Якщо f це Шаблон:Math раз неперервно диференційовна на закритому інтервалі I і $p_n(x)$ це многочлен степеня не більше Шаблон:Mvar, що інтерполює f у Шаблон:Math відмінних точках {x_i} (i=0,1,...,n) у цьому інтервалі. Тоді для кожного x в інтервалі існує Шаблон:Mvar у цьому інтервалі, таке що

$f(x)-p_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\prod _{i=0}^n(x-x_i)$

Доведення

Запишемо похибку як

$R_n(x)=f(x)-p_n(x)$

і впровадимо допоміжну функцію:

$Y(t)=R_n(t)-\frac{R_n(x)}{W(x)}W(t)$

де

$W(u)=\prod _{i=0}^n(u-x_i)$

Оскільки Шаблон:Math є коренями Шаблон:Math і $p_n$, ми маємо Шаблон:Math, що означає, що Шаблон:Mvar і Шаблон:Math є коренями (тут ми маємо справу з певним x, для якого ми й шукаємо похибку). Із теореми Роля, $Y^{\prime }(t)$ має Шаблон:Math коренів, тоді $Y^{(n+1)}(t)$ має один корінь Шаблон:Mvar, тут Шаблон:Mvar перебуває в інтервалі Шаблон:Mvar.

Отже, ми можемо отримати

$Y^{(n+1)}(t)=R_n^{(n+1)}(t)-\frac{R_n(x)}{W(x)}(n+1)!$

Оскільки $p_n(x)$ це многочлен степеня не більше ніж Шаблон:Mvar, тоді

$R_n^{(n+1)}(t)=f^{(n+1)}(t)$

Отже

$Y^{(n+1)}(t)=f^{(n+1)}(t)-\frac{R_n(x)}{W(x)}(n+1)!$

Із того, що Шаблон:Mvar є коренем $Y^{(n+1)}(t)$, маємо

$Y^{(n+1)}(\xi )=f^{(n+1)}(\xi )-\frac{R_n(x)}{W(x)}(n+1)!=0$

Відтак

$R_n(x)=f(x)-p_n(x)=\frac{f^{(n+1)}(\xi )}{(n+1)!}\prod _{i=0}^n(x-x_i)$.

Отже, залишковий член у формі Лагранжа теореми Тейлора це особливий випадок інтерполяційної похибки, коли інтерполяційні точки Шаблон:Math лежать на однаковій відстані.

У випадку рівновіддалених вузлів інтерполяції $x_i=x_0+ih$, випливає, що інтерполяційна похибка є O$(h^{n+1})$. Однак, це має на увазі, що $f^{(n+1)}(\xi )$ домінована $h^{n+1}$, тобто $f^{(n+1)}(\xi )h^{n+1}<<1$. У деяких випадках відбувається зростання похибки з Шаблон:Math Шаблон:Докладніше

Наведена помилкаШаблон:Прояснити пропонує вибирати інтерполяційні точки Шаблон:Math так, щоб добуток

$|\prod (x-x_i)|,$

був якомога меншим. Таку властивість мають нулі поліномів Чебишова. Саме вони є оптимальними вузлами інтерполяційних схем.

Переваги

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

Недоліки

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

Приклад осциляції

Інтерполяция на послідовності сіток. Приклад Рунге.

Шаблон:Main Класичним прикладом Рунге, що показує виникнення осциляцій в інтерполяційного многочлена, слугує інтерполяція на рівномірній сітці значень функції

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

Введемо на відрізку $[-5,5]$ рівномірну сітку $x_i=-5+(i-1)h$, $h=10/(n-1)$, $1\le i\le 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$ - многочлен восьмого степеня.

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

Див. також

• Інтерполяційний многочлен Лагранжа
• Многочлени Чебишова
• Вейвлет