Интерполяция полиномами Лагранжа и Ньютона

Материал из MachineLearning.

Перейти к: навигация, поиск

Содержание

Постановка задачи

Пусть задана функция y = f(x) .
Пусть заданы точки \bf{x} = \{ x_i | i = 1..n \} из некоторой области \bf D .
Пусть значения функции f известны только в этих точках.
Точки \bf{x} называют узлами интерполяции.
\delta x_i = x_i - x_{i-1} - шаг интерполяционной сетки.
Задача интерполяции состоит в поиске такой функции F из заданного класса функций, что F(x_i) = y_i

Метод решения задачи

Полином Лагранжа

Представим интерполяционную функцию в виде полинома
P_n(x) = \sum_{i=0}^n y_i Q_{n,i}(x)
где Q_{n,i}(x) - полиномы степели n вида:
Q_{n,i}(x) = \prod_{j=0, j\neq i}^{n} \frac{(x-x_j)}{(x_i-x_j)}
Очевидно, что Q_{n,i}(x) принимает значение 1 в точке x_i и 0 в остальных узлах интерполяции. Следовательно в точке x_i исходный полином принимает значение y_i
Таким образом, построенный полином P_n(x) является интерполяционным полиномом для функции y = f(x) на сетке \bf{x} .

Полином Ньютона

Интерполяционный полином в форме Лагранжа не удобен для вычислений тем, что при увеличении числа узло интерполции приходится перестраивать весь полином заного.
Перепишем полином Лагранжа в другом виде:
P_n(x) = P_0(x) + \sum_{i=1}^n{(P_i(x) - P_{i-1}(x))}

Пример

Литература

Источник — «http://machinelearning.ru/wiki/index.php?title=%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D1%8F_%D0%BF%D0%BE%D0%BB%D0%B8%D0%BD%D0%BE%D0%BC%D0%B0%D0%BC%D0%B8_%D0%9B%D0%B0%D0%B3%D1%80%D0%B0%D0%BD%D0%B6%D0%B0_%D0%B8_%D0%9D%D1%8C%D1%8E%D1%82%D0%BE%D0%BD%D0%B0»
Личные инструменты