Перегляд вихідного коду сторінки Поліноміальна інтерполяція

'''Поліноміальна інтерполяція (Інтерполяція алгебраїчними многочленами)''' [[Функція (математика)|функції]] ''f(x)'' на [[Відрізок|відрізку]] ''[a, b]'' - побудова [[многочлен]]а ''P<sub>n</sub>(x)'' степеня меншого або рівного ''n'', що приймає у вузлах інтерполяції x<sub>0</sub>, x<sub>1</sub>, ..., x<sub>n</sub> значення f(x<sub>і</sub>):

<math>P_n(x_i) = f(x_i), \quad i = 0, 1, ..., n</math>

[[Система лінійних алгебраїчних рівнянь|Система рівнянь]], що визначають [[коефіцієнт]]и такого многочлена, має вигляд

<math>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</math>

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

<math>\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)</math>

Він відмінний від [[Нуль (число)|нуля]] при всяких попарно різних значеннях ''x<sub>і</sub>'', і інтерполяція функції ''f'' по її значеннях у вузлах ''x<sub>і</sub>'' за допомогою многочлена ''P<sub>n</sub>(x)'' завжди можлива і єдина.

== Застосування ==
Отриману інтерполяційну [[формула|формулу]] <math>f(x) \approx P_n(x)</math> часто використовують для наближеного обчислення значень функції ''f'' при значеннях аргументу ''x'', відмінних від вузлів інтерполяції. При цьому розрізняють ''[[Інтерполяція|інтерполяцію]]'' у вузькому значенні, коли <math>x \in \left[ x_0, x_n \right]</math>, і ''[[Екстраполяція|екстраполяцію]]'', коли <math>x \in \left[ a, b \right]</math>, <math>x \not\in \left[ x_0, x_n \right]</math>

== Задача інтерполяції ==
Нехай у просторі задані <math>n</math> точок <math>P_1, P_2,\dots, P_n</math>, які в деякій системі координат мають радіус-вектори <math>\mathbf{r}_1, \mathbf{r}_2,\dots, \mathbf{r}_n</math>.

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

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

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

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

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

<math>~
\mathbf{r}(t) = \mathbf{p}^{(n-1)}(t) =\sum_{k=1}^n \mathbf{a}_k t^{n-k}
</math>

Многочлен має <math>~ n</math> коефіцієнтів <math>~ \mathbf{a}_k</math>, які можна знайти з умов
<math>~ \mathbf{r}(t_i)=\mathbf{r}_i</math>.

Ці умови приводять до системи лінійних рівнянь для коефіцієнтів <math>~ \mathbf{a}_k</math>

<math>~
\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}
</math>

Звернемо увагу, що потрібно розв'язати три системи рівнянь: для <math>~ x</math>, <math>~ y</math> і
<math>~ z</math> координат. Усі вони мають одну матрицю коефіцієнтів, знаходячи обернену до якої, за значеннями радіус- векторів <math>~ \mathbf{r}_i</math> точок обчислюються вектори <math>~ \mathbf{a}_k</math> коефіцієнтів многочлена. Визначник матриці

<math>~
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)
</math>

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

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

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

Інтерполюючи певну функцію ''f'' поліномом степеня {{mvar|n}} у точках ''x''<sub>0</sub>,...,''x''<sub>''n''</sub> ми отримуємо [[Похибка|похибку]]

:<math>f(x) - p_n(x) = f[x_0,\ldots,x_n,x] \prod_{i=0}^n (x-x_i) </math>

де
:<math>f[x_0,\ldots,x_n,x]</math>

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

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

:<math> f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) </math>

=== Доведення ===
Запишемо похибку як 

:<math> R_n(x) = f(x) - p_n(x) </math>

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

:<math> Y(t) = R_n(t) - \frac{R_n(x)}{W(x)} W(t) </math>

де

:<math> W(u) = \prod_{i=0}^n (u-x_i) </math>

Оскільки {{math|''x<sub>i</sub>''}} є коренями {{math|&nbsp;''f''&nbsp;}} і <math>p_n</math>, ми маємо {{math|''Y''(''x'') {{=}} ''Y''(''x<sub>i</sub>'') {{=}} 0}}, що означає, що {{mvar|Y}} і {{math|''n'' + 2}} є коренями (тут ми маємо справу з певним x, для якого ми й шукаємо похибку). Із [[теорема Роля|теореми Роля]], <math>Y^\prime(t)</math> має {{math|''n'' + 1}} коренів, тоді <math>Y^{(n+1)}(t)</math> має один корінь {{mvar|ξ}}, тут {{mvar|ξ}} перебуває в інтервалі {{mvar|I}}.

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

:<math> Y^{(n+1)}(t) = R_n^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)!  </math>

Оскільки <math>p_n(x)</math> це многочлен степеня не більше ніж {{mvar|n}}, тоді

:<math> R_n^{(n+1)}(t) = f^{(n+1)}(t) </math>

Отже

:<math> Y^{(n+1)}(t) = f^{(n+1)}(t) - \frac{R_n(x)}{W(x)} \ (n+1)!  </math>

Із того, що {{mvar|ξ}} є коренем <math>Y^{(n+1)}(t)</math>, маємо

:<math> Y^{(n+1)}(\xi) = f^{(n+1)}(\xi) - \frac{R_n(x)}{W(x)} \ (n+1)! = 0 </math>

Відтак

:<math> R_n(x) = f(x) - p_n(x) = \frac{f^{(n+1)}(\xi)}{(n+1)!} \prod_{i=0}^n (x-x_i) </math>.

Отже, залишковий член у формі Лагранжа [[Теорема Тейлора|теореми Тейлора]] це особливий випадок інтерполяційної похибки, коли інтерполяційні точки {{math|''x<sub>i</sub>''}} лежать на однаковій відстані<ref>{{cite web|url=http://www.math.okstate.edu/~binegar/4513-F98/4513-l16.pdf|title=Errors in Polinomial Interpolation |type=Lecture 16|work=Math 4513: Numerical Analysis |year= 1998|author=Birne Binegar |publisher=[[Університет Оклахоми|Oklahoma State University]]|accessdate=5 серпня 2015|archive-date=4 липня 2010|archive-url=https://web.archive.org/web/20100704180840/http://www.math.okstate.edu/~binegar/4513-F98/4513-l16.pdf}} {{ref-en}}</ref>.

У випадку рівновіддалених вузлів інтерполяції <math>x_i = x_0 + ih</math>, випливає, що інтерполяційна похибка є O<math>(h^{n+1})</math>. Однак, це має на увазі, що <math>f^{(n+1)}(\xi)</math> домінована <math>h^{n+1}</math>, тобто <math>f^{(n+1)}(\xi) h^{n+1} << 1</math>. У деяких випадках відбувається зростання похибки з {{math|''n'' → ∞}} 
{{Докладніше|Феномен Рунге}}

Наведена помилка{{прояснити}} пропонує вибирати інтерполяційні точки {{math|''x<sub>i</sub>''}} так, щоб добуток

:<math>\left | \prod (x - x_i) \right |,</math>

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

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

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

=== Приклад осциляції ===
[[Файл:Runge01.svg|thumb|250px|right|Інтерполяция на послідовності сіток. Приклад Рунге.]]
{{Main|Феномен Рунге}}
Класичним прикладом [[Карл Рунге|Рунге]], що показує виникнення осциляцій в інтерполяційного многочлена, слугує інтерполяція на рівномірній сітці значень функції

<math>~
f(x) = \frac{1}{1+x^2}
</math>

Введемо на відрізку <math>~ [-5, 5]</math> рівномірну сітку <math>~ x_i=-5+(i-1)h</math>,
<math>~ h=10/(n-1)</math>, <math>~ 1 \leq i \leq n</math> і розглянемо поведінку многочлена

<math>~
y(x) = \sum_{i=1}^n a_i x^{n-i}
</math>

який у точках <math>~ x_i</math> приймає значення <math>~ y_i=1/(1+x_i^2)</math>.
На малюнку представлені графіки самої функції (штрих-пунктирна лінія) і трьох інтерполяційних кривих при <math>~ n=3, 5, 9</math>:
* інтерполяція на сітці <math>~ x_1=-5,  x_2=0, x_3=5</math> - квадратична парабола;
* інтерполяція на сітці <math>~ x_1=-5, x_2=-2.5, x_3=0, x_4=2.5, x_5=5</math> - многочлен четвертого степеня;
* інтерполяція на сітці <math>~ 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</math> - многочлен восьмого степеня.

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

== Див. також ==
* [[Інтерполяційний многочлен Лагранжа]]
* [[Многочлени Чебишова]]
* [[Вейвлет]]

== Примітки ==
{{reflist}}

[[Категорія:Інтерполяція]]
[[Категорія:Математичний аналіз]]
[[Категорія:Многочлени]]