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

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

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

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

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

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

Застосування[ред.ред. код]

Отриману інтерполяційну формулу часто використовують для наближеного обчислення значень функції f при значеннях аргументу x, відмінних від вузлів інтерполяції. При цьому розрізняють інтерполяцію у вузькому значенні, коли , і екстраполяцію, коли ,

Задача інтерполяції[ред.ред. код]

Нехай у просторі задані точок , які в деякій системі координат мають радіус-вектори .

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

Розв'язання задачі[ред.ред. код]

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

Будемо будувати криві у вигляді , де параметр змінюється на деякому відрізку : . Введемо на відрізку сітку з точок: і зажадаємо, щоб при значенні параметра крива проходила через точку , так що .

Введення параметризації й сітки може бути виконане різними способами. Звичайно вибирають або рівномірну сітку, вважаючи , , , або, що більш переважно, з'єднують точки відрізками й у якості різниці значень параметра беруть довжину відрізка .

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

Многочлен має коефіцієнтів , які можна знайти з умов .

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

Звернемо увагу, що потрібно розв'язати три системи рівнянь: для , і координат. Усі вони мають одну матрицю коефіцієнтів, знаходячи обернену до якої, за значеннями радіус- векторів точок обчислюються вектори коефіцієнтів многочлена. Визначник матриці

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

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

Помилка інтерполяції[ред.ред. код]

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

де

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

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

Доведення[ред.ред. код]

Запишемо помилку як

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

де

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

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

Оскільки це многочлен степеня не більше ніж n, тоді

Отже

З того, що ξ є коренем , маємо

Відтак

.

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

У випадку рівновідстаннєвих вузлів інтерполяції , випливає що інтерполяційна помилка є O. Однак, це має на увазі, що домінована , тобто . У декількох випадках, відбувається зростання помилки із n → ∞ (див. Феномен Рунге).

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

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

Переваги[ред.ред. код]

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

Недоліки[ред.ред. код]

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

Приклад осциляції[ред.ред. код]

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

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

Введемо на відрізку рівномірну сітку , , і розглянемо поведінку многочлена

який у точках приймає значення . На малюнку представлені графіки самої функції (штрих-пунктирна лінія) і трьох інтерполяційних кривих при :

  • інтерполяція на сітці - квадратична парабола;
  • інтерполяція на сітці - многочлен четвертого степеня;
  • інтерполяція на сітці - многочлен восьмого степеня.

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

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

Примітки[ред.ред. код]