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

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

${\displaystyle P_{n}(x_{i})=f(x_{i}),\quad i=0,1,...,n}$

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

${\displaystyle 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}$

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

${\displaystyle \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) завжди можлива і єдина, але в залежності від завдання її зручно записувати різними формулами.

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

Отриману інтерполяційну формулу ${\displaystyle f(x)\approx P_{n}(x)}$ часто використовують для наближеного обчислення значень функції f при значеннях аргументу x, відмінних від вузлів інтерполяції. При цьому розрізняють інтерполяцію у вузькому значенні, коли ${\displaystyle x\in \left[x_{0},x_{n}\right]}$, і екстраполяцію, коли ${\displaystyle x\in \left[a,b\right]}$, ${\displaystyle x\not \in \left[x_{0},x_{n}\right]}$

Формула Лагранжа

Докладніше: Многочлен Лагранжа

Функція ${\displaystyle f(x)=f_{0}+f_{1}x+f_{2}x^{2}+\ldots }$ може бути інтерпольована на відрізку ${\displaystyle [x_{0},x_{n}]}$ інтерполяційним поліномом ${\displaystyle P_{n}(x)}$, записаним у формі Лагранжа:

${\displaystyle f(x)\approx P_{n}(x)=\sum _{k=0}^{n}y_{k}{\frac {(x-x_{0})(x-x_{1})\ldots (x-x_{k-1})(x-x_{k+1})\ldots (x-x_{n})}{(x_{k}-x_{0})(x_{k}-x_{1})\ldots (x_{k}-x_{k-1})(x_{k}-x_{k+1})\ldots (x_{k}-x_{n})}},}$

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

${\displaystyle |f(x)-P_{n}(x)|\leq {\frac {\|f^{(n+1)}(x)\|}{(n+1)!}}\cdot \|\Pi _{n}(x)\|,\qquad \Pi _{n}(x)=(x-x_{0})(x-x_{1})\ldots (x-x_{n}).}$

У просторі дійсних неперервних функцій відповідні норми набирають вигляду:

${\displaystyle \|f^{(n+1)}(x)\|=\max _{x\in [x_{0},x_{n}]}|f^{(n+1)}(x)|,\qquad \|\Pi _{n}(x)\|=\max _{x\in [x_{0},x_{n}]}|\Pi _{n}(x)|.}$

Формула Ньютона

Докладніше: Многочлен Ньютона

Якщо точки ${\displaystyle x_{0},\ x_{1},\ \ldots ,\ x_{n}}$ розташовані на рівних відстанях ${\displaystyle \ (x_{k}=x_{0}+kh)}$, поліном можна записати:

${\displaystyle P_{n}(x_{0}+th)=y_{0}+{\frac {t}{1!}}\Delta y_{0}+{\frac {t(t-1)}{2!}}\Delta ^{2}y_{0}+\ldots +{\frac {t(t-1)\cdots (t-n+1)}{n!}}\Delta ^{n}y_{0}}$

(тут ${\displaystyle \ x_{0}+th=x}$, а ${\displaystyle \ \Delta ^{k}}$ — різниці k-го порядку: ${\displaystyle \ \Delta ^{k}y_{i}=\Delta ^{k-1}y_{i+1}-\Delta ^{k-1}y_{i}}$).

Це формула Ньютона для інтерполяції вперед; назва формули вказує на те, що вона містить задані значення ${\displaystyle \ y}$, що відповідають вузлам інтерполяції, що знаходяться тільки праворуч від ${\displaystyle \ x_{0}}$. Ця формула зручна при інтерполяції функцій для значень ${\displaystyle \ x}$, близьких до ${\displaystyle \ x_{0}}$.

При інтерполяції функцій для значень ${\displaystyle \ x}$, близьких до ${\displaystyle \ x_{k}}$, формулу Ньютона доцільно перетворити, змінивши початок відліку (див. Нижче формули Стірлінга і Бесселя).

Формулу Ньютона можна записати і для нерівновіддаленими вузлів, вдаючись для цієї мети до розділених різниць. На відміну від формули Лагранжа, де кожен член залежить від всіх вузлів інтерполяції, будь-який ${\displaystyle k}$-й член формули Ньютона залежить від перших (від початку відліку) вузлів і додавання нових вузлів викликає лише додавання нових членів формули (в цьому перевага формули Ньютона).

Коротка форма інтерполяційної формули Ньютона для випадку рівновіддалених вузлів:

${\displaystyle P_{n}(x)=\sum _{m=0}^{n}\left(C_{x}^{m}\sum _{k=0}^{m}(-1)^{k}\,C_{m}^{k}\,f_{m-k}\right)}$

де ${\displaystyle C_{x}^{m}}$ — узагальнені на область дійсних чисел біноміальні коефіцієнти.

Інтерполяційна формула Стірлінга

${\displaystyle f(x_{0}+th)=y_{0}+{\frac {t}{1!}}\mu \delta y_{0}+{\frac {t^{2}}{2!}}\delta ^{2}y_{0}+{\frac {t(t^{2}-1^{2})}{3!}}\mu \delta ^{3}y_{0}+{\frac {t^{2}(t^{2}-1^{2})}{4!}}\delta ^{4}y_{0}+}$

${\displaystyle +{\frac {t(t^{2}-1^{2})(t^{2}-2^{2})}{5!}}\mu \delta ^{5}y_{0}+\cdots +{\frac {t^{2}(t^{2}-1^{2})(t^{2}-2^{2})\cdots [t^{2}-(k-1)^{2}]}{(2k)!}}\delta ^{2k}y_{0}}$

(про значення символу ${\displaystyle \ \mu }$ зв'язку центральних різниць ${\displaystyle \ \delta ^{m}}$ з різницями ${\displaystyle \Delta ^{m}}$ див. Кінцевих різниць числення)

Застосовується при інтерполяції функцій для значень ${\displaystyle \ x}$, близьких до одного з середніх вузлів ${\displaystyle \ a}$; в цьому випадку природно взяти непарне число вузлів ${\displaystyle x_{-k},\ \ldots ,\ x_{-1},\ x_{0},\ x_{1},\ \ldots ,\ x_{k}}$, вважаючи ${\displaystyle \ a}$ центральним вузлом ${\displaystyle \ x_{0}}$.

Інтерполяційна формула Бесселя

${\displaystyle f(x_{0}+th)\approx \mu y_{1/2}+{\frac {(t-1/2)}{1!}}\delta y_{1/2}+{\frac {t(t-1)}{2!}}\mu \delta ^{2}y_{1/2}+{\frac {t(t-1)(t-1/2)}{3!}}\delta ^{3}y_{1/2}+}$

${\displaystyle +{\frac {t(t-1)(t+1)(t-2)}{4!}}\mu \delta ^{4}y_{1/2}+{\frac {t(t-1)(t+1)(t-2)(t-1/2)}{5!}}\delta ^{5}y_{1/2}+\cdots +}$

${\displaystyle +{\frac {t(t-1)(t+1)\cdots (t-k)(t+k-1)(t-1/2)}{(2k+1)!}}\delta ^{2k+1}y_{1/2}}$

Застосовується при інтерполяції функцій для значень ${\displaystyle \ x}$, близьких середин ${\displaystyle \ a}$ між двома вузлами; тут природно брати парне число вузлів ${\displaystyle x_{-k},\ \ldots ,\ x_{-1},x_{0},x_{1},\ldots ,x_{k},x_{k+1}}$, і розташовувати їх симетрично щодо ${\displaystyle a(x_{0}<a<x_{1}).}$

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

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

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

де

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

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

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

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

Доведення

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

${\displaystyle R_{n}(x)=f(x)-p_{n}(x)}$

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

${\displaystyle Y(t)=R_{n}(t)-{\frac {R_{n}(x)}{W(x)}}W(t)}$

де

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

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

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

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

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

${\displaystyle R_{n}^{(n+1)}(t)=f^{(n+1)}(t)}$

Отже

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

Із того, що ξ є коренем ${\displaystyle Y^{(n+1)}(t)}$, маємо

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

Відтак

${\displaystyle 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].

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

Докладніше: Феномен Рунге

Наведена помилка^{[прояснити]} пропонує вибирати інтерполяційні точки x_i так, щоб добуток

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

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

Переваги

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

Недоліки

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

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

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

Докладніше: Феномен Рунге

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

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

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

${\displaystyle ~y(x)=\sum _{i=1}^{n}a_{i}x^{n-i}}$

який у точках ${\displaystyle ~x_{i}}$ приймає значення ${\displaystyle ~y_{i}=1/(1+x_{i}^{2})}$. На малюнку представлені графіки самої функції (штрих-пунктирна лінія) і трьох інтерполяційних кривих при ${\displaystyle ~n=3,5,9}$:

• інтерполяція на сітці ${\displaystyle ~x_{1}=-5,x_{2}=0,x_{3}=5}$ - квадратична парабола;
• інтерполяція на сітці ${\displaystyle ~x_{1}=-5,x_{2}=-2.5,x_{3}=0,x_{4}=2.5,x_{5}=5}$ - многочлен четвертого степеня;
• інтерполяція на сітці ${\displaystyle ~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}$ - многочлен восьмого степеня.

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

Див. також

• Інтерполяція Ерміта
• Інтерполяційна формула Віттекера — Шеннона
• Інтерполяційна формула Гаусса
• Поліноми Чебишова
• Вейвлет