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

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

Означення[ред.ред. код]

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

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

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

для j > 0 і .

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

де

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

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

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

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

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

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

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

Головна ідея[ред.ред. код]

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

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

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


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

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

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

Приклад[ред.ред. код]

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

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

Дивіться також[ред.ред. код]

Посилання[ред.ред. код]

  1. http://nptel.iitm.ac.in/courses/Webcourse-contents/IIT-KANPUR/Numerical%20Analysis/numerical-analysis/Rathish-kumar/rathish-oct31/fratnode5.html