Многочлен Ньютона

Означення

Маючи множину з k + 1 точок

де немає двох однакових xj, інтерполяційний многочлен у формі Ньютона — це лінійна комбінація базових многочленів Ньютона

де базовий многочлен Ньютона задається так

для j > 0 і .

Коефіцієнти задаються як

де

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

Отже інтерполяційний многочлен Ньютона можна записати як

Інтерполяційний многочлен Ньютона можна представити у спрощеній формі якщо впорядковані послідовно і з рівними проміжками. Позначаючи для кожного і , різницю можна записати як . Так інтерполяційний многочлен Ньютона набуває форми:

така форма називається прямий інтерполяційний многочлен Ньютона.

Якщо вузли пересортувати в зворотньому порядку: , інтерполяційний многочлен Ньютона стає:

Якщо на рівних відстанях з , а для i = 0, 1, ..., k, тоді,

така форма називається зворотній інтерполяційний многочлен Ньютона.

Головна ідея

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

Для k + 1 точок ми будуємо базис Ньютона так:

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


Цю систему можна розв'язати покроково, розв'язуючи

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

Як можна бачити з означення розділеної різниці, ми можемо додавати нові точки, що отримати новий інтерполяційний многочлен без переобчислення старих коефіцієнтів. І якщо точка змінилась, зазвичай, нам не потрібно переобчислювати усі коефіцієнти. Ба, більше — якщо xi розташовані на рівних відстанях, обчислення стає набагато простішим. Тому, зазвичай, віддають перевагу формулі із розділеними різницями перед многочленом Лагранжа.

Приклад

Розділені різниці можна записати у вигляді таблиці. Наприклад, для функції f і точок . Записуємо

Тоді інтерполяційний многочлен формується використовуючи горішні елементи кожного стовпчика як коефіцієнти.

Див. також

Посилання

  1. https://web.archive.org/web/20100904060718/http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT-KANPUR/Numerical%20Analysis/numerical-analysis/Rathish-kumar/rathish-oct31/fratnode5.html
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.