Інтерполяція поліномами Лагранжа та Ньютона
Матеріал із MachineLearning.
Зміст
Постановка задачі
Нехай задана функція. Нехай задані точки з певної області. Нехай значення функції відомі лише у цих точках. Точки називають вузлами інтерполяції. - крок інтерполяційної сітки. Завдання інтерполяції полягає у пошуку такої функції із заданого класу функцій, що
Метод вирішення задачі
Поліном Лагранжа
Представимо інтерполяційну функцію у вигляді полінома
де - поліноми степелу n виду:
Очевидно, що набуває значення 1 у точці та 0 в інших вузлах інтерполяції. Отже в точці вихідний поліном набуває значення Таким чином, побудований поліном є інтерполяційним поліномом для функції на сітці.
Поліном Ньютона
Інтерполяційний поліном у формі Лагранжа не зручний для обчислень тим, що зі збільшенням числа вузлів інтерполяції доводиться перебудовувати весь поліном наново. Перепишемо поліном Лагранжа в іншому вигляді:
де - поліноми Лагранжа ступеня i ≤ n. Нехай . Цей поліном має ступінь i і перетворюється на нуль при . Тому він представимо у вигляді: , де - Коефіцієнт при . Так як не входить в , то збігається з коефіцієнтом при поліномі . Таким чином, з визначення отримуємо:
Напишемо формулу у вигляді
Рекурентно виражаючи променям остаточну формулу для полінома:
Таке уявлення полінома зручне обчислення, оскільки збільшення числа вузлів на одиницю вимагає додавання лише одного доданку.
Похибка інтерполювання
Поставимо питання про те, як добре інтерполяційний поліном наближає функцію на відрізку [a,b]. Розглянь залишковий член: , x ∈ [a, b]. За визначенням інтерполяційного поліномаR_n(x_i) = 0, x_i \in \bf X" alt= " R_n(x_i) = 0, x_i \in \bf X" /> тому йдеться про оцінку при значеннях >Нехай має безперервну (n+1) похідну на відрізку [a, b]. Тоді похибка визначається формулою: , де , - точка з [a, b]. Оскільки точка відома, то ця формула дозволяє лише оцінити похибку:
де З виду множника слід, що оцінка має сенс лише за . Якщо це не так, то при інтерполяції використовують поліноми низьких ступенів (n = 1,2).
Вибір вузлів інтерполяції
Так як від вибору вузлів заздрить точність інтерполяції, виникає питання про те, як їх вибирати. За допомогою вибору вузлів можна мінімізувати значення для оцінки похибки. Це завдання вирішується за допомогою багаточлена Чебишева [1]:
Як вузли слід взяти коріння цього многочлена, тобто точки:
Як приклад розглянемо інтерполяцію синуса. Візьмемо рівномірну решітку x = [-3,-1.5,0,1.5,3]; Інтерполяція поліномом Лагранжа:
