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

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

$P_{n}(x_{i})=f(x_{i}),\quad 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}),\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_і за допомогою многочлена P_n(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 поліномом степеня $n$ у точках x₀,...,x_n ми отримуємо помилку

f(x)-p_{n}(x)=f[x_{0},\ldots ,x_{n},x]\prod _{i=0}^{n}(x-x_{i})

де

f[x_{0},\ldots ,x_{n},x]

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

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

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})

Оскільки $x i$ є коренями $f$ і $p_{n}$ , ми маємо $Y (x) = Y (x i) = 0$ , що означає, що $Y$ і $n + 2$ є коренями. (Тут ми маємо справу з певним x, для якого ми й шукаємо помилку.) З теореми Роля, $Y^{\prime }(t)$ має $n + 1$ коренів, тоді $Y^{(n+1)}(t)$ має один корінь $ξ$ , тут $ξ$ перебуває в інтервалі $I$ .

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

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

Оскільки $p_{n}(x)$ це многочлен степеня не більше ніж $n$ , тоді

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)!

З того, що $ξ$ є коренем $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})

.

Отже, залишковий член у формі Лагранжа теореми Тейлора це особливий випадок інтерполяційної помилки коли всі інтерполяційні точки $x i$ однакові.[1]

У випадку рівновідстаннєвих вузлів інтерполяції $x_{i}=x_{0}+ih$ , випливає що інтерполяційна помилка є O $(h^{n+1})$ . Однак, це має на увазі, що $f^{(n+1)}(\xi )$ домінована $h^{n+1}$ , тобто $f^{(n+1)}(\xi )h^{n+1}<<1$ . У декількох випадках, відбувається зростання помилки із $n \to \infty$ (див. Феномен Рунге).

Наведена помилка пропонує вибирати інтерполяційні точки $x i$ так, щоб добуток

\left|\prod (x-x_{i})\right|,

був якомога меншим. Таку властивість мають вузли Чебишова.

Переваги

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

Недоліки

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

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

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

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

$~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$ - многочлен восьмого степеня.

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

Див. також

Примітки

Помилки у поліноміальній інтерполяції. (англ.)

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

[1] Помилки у поліноміальній інтерполяції. (англ.)