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

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

(Различия между версиями)

Версия 16:01, 20 октября 2008

Содержание

1 Постановка задачи
2 Метод решения задачи
- 2.1 Полином Лагранжа
- 2.2 Полином Ньютона
3 Погрешность интерполирования
4 Выбор узлов интерполяции
5 Пример
6 Литература

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

Пусть задана функция $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].
Тогда погрешность определяется формулой:
$|R_n(x)| = \frac{f^{n+1}(\varepsilon)}{(n+1)!}w_{n+1}(x)$ ,
где $w_{n+1} = (x - x_0)...(x - x_n)$ ,
$\varepsilon$ - точка из [a, b].
Так как точка $\varepsilon$ наизвестна, то эта формула позволяет только оценить погрешность:
$|R_n(x)| \le \frac{M_{n+1}}{(n+1)!}|w_{n+1}(x)|$
где $M_{n+1} = \max_{x\in[\alpha, \beta]}|f^{n+1}(x)|$
Из вида множетеля $w_{n+1}$ следует, что оценка имеет смысл только при $x \in [x_0, x_n]$ . Если это не так, то при интерполяции используются полиномы низких степеней (n = 1,2).

Выбор узлов интерполяции

Пример

Литература

Источник — «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»

@@ Строка 48: / Строка 48: @@
 По определению интерполяционного полинома <tex><br>R_n(x_i) = 0, x_i \in \bf X</tex> <br>
 поэтому речь идет об оценке  <tex>R_n(x)</tex> при значениях <tex>x \not= x_i</tex>.<br>
-Пусть <tex>f(x)</tex> имеет непрерывную (n+1) производную на отрезке [a, b].
+Пусть <tex>f(x)</tex> имеет непрерывную (n+1) производную на отрезке [a, b].<br>
+Тогда погрешность определяется формулой:<br>
+<tex>|R_n(x)| = \frac{f^{n+1}(\varepsilon)}{(n+1)!}w_{n+1}(x)</tex>,<br>
+где <tex>w_{n+1} = (x - x_0)...(x - x_n)</tex>,<br>
+<tex>\varepsilon </tex>- точка из [a, b].<br>
+Так как точка <tex>\varepsilon </tex> наизвестна, то эта формула позволяет только оценить погрешность:<br>
+<tex>|R_n(x)| \le \frac{M_{n+1}}{(n+1)!}|w_{n+1}(x)|</tex><br>
+где <tex>M_{n+1} = \max_{x\in[\alpha, \beta]}|f^{n+1}(x)|</tex><br>
+Из вида множетеля <tex>w_{n+1}</tex> следует, что оценка имеет смысл только при <tex>x \in [x_0, x_n]</tex>. Если это не так, то при интерполяции используются полиномы низких степеней (n = 1,2). <br>
+== Выбор узлов интерполяции ==
 == Пример ==
 == Литература ==