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

Материал из 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))}
где P_i(x) - полиномы Лагранжа степени i ≤ n.
Пусть Q_i(x) = P_i(x) - P_{i-1}(x) \qquad(*)
. Этот полином инеет степень i и обращается в нуль при x = x_0, x = x_1, ..., x = x_{i-1}{.
Поэтому он представим в виде:
Q_i(x) = A_i(x - x_0)...(x - x_{i-1}), где A_i - коэффициент при x^i. Так как x^i не входити в P_{i-1}(x), то A_i совпадает с коэффициентом при x^i в полиноме P_i(x). Таким образом из определения P_i(x) получаем:
 A_i = \sum_{k=0}^i\frac{f(x_k)}{w_{k,i}}
где
 w_{k,i} = (x_k - x_0)...(x_k - x_{k-1})(x_k - x_{k+1})...(x_k - x_i)
Препишем формулу \qquad(*) в виде
P_n(x) = P_{n-1} + A_n(x - x_0)...(x - x_{n-1})
Рекуррентно выражая P_i(x) пролучам окончательную формулу для полинома:
P_n(x) = A_0 + A_1(x-x_0) + ...+ A_n(x - x_0)...(x - x_{n-1})
Такое представление полинома удобно для вычисления, потому что увеличение числа узлов на единицу требует добавления только одного слагаемого.


Погрешность интерполирования

Поставим вопрос о том, насколько хорошо интерполяционный полином P_n(x) приближает функцию f(x) на отрезке [a,b].
Рассмотри м остаточный член:
R_n(x) = f(x) - P_n(x), x ∈ [a, b].
По определению интерполяционного полинома <br>R_n(x_i) = 0, x_i \in \bf X
поэтому речь идет об оценке R_n(x) при значениях x \not= x_i.
Пусть f(x) имеет непрерывную (n+1) производную на отрезке [a, b].

Пример

Литература