Интерполяция каноническим полиномом

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

Версия от 12:27, 28 сентября 2008; Leo (Обсуждение | вклад)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)

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

Пусть задана функция $\varphi(x)$ на некотором интервале [x₀,x_n]. Предположим, что мы знаем значения этой функции в n точках. Известно, что через n+1 точек на плоскости можно провести кривую, являющуюся графиком степенного многочлена (полинома) степени n, причем такой полином единственный.

Этот факт лежит в основе так называемой полиномиальной интерполяции, при которой функцию $\varphi(x)$ строят в виде полинома степени n.

Если на всём интервале $[x_0,x_n]$ , содержащем n+1 узлов, строят один полином степени n, то говорят о глобальной интерполяции. Если же интервал разбивается на отрезки, и на каждом из отрезков строится свой полином, то говорят о локальной интерполяции.

Полином в каноническом виде

В качестве аппроксимирующей функции выбирается полином степени $n$ в каноническом виде:

$\varphi(x)=P_n(x)=c_0+c_1x+c_2x^2+ \ldots + c_nx^n$

Коэффициенты полинома $c_i$ определяются из условий Лагранжа $P_n(x_i)=y_i$ , $i=1, \ldots, n$ , что с учётом предыдущего выражения даёт систему уравнений с n+1 неизвестными:

$\begin{matrix} c_0 + c_1x_0 + c_2x_0^2 + \ldots + c_nx_0^n = y_0 \\ c_0 + c_1x_1 + c_2x_1^2 + \ldots + c_nx_1^n = y_1 \\ \ldots \ldots \ldots \ldots \ldots \\ c_0 + c_1x_n + c_2x_n^2 + \ldots + c_nx_n^n = y_n \end{matrix}$

Обозначим систему таких уравнений символом (*) и перепишем её следующим образом:

$\sum_{p=0}^n c_i^p = y_i, \quad i=1, \ldots, n$

или в матричной форме: $\mathbf{Ac}=\mathbf{y},$ где $\mathbf{c}$ --- вектор-столбец, содержащий неизвестные коэффициенты $c_i$ , $\mathbf{y}$ --- вектор-столбец, составленный из табличных значений функции $y_i$ , а матрица $\mathbf{A}$ имеет вид:

$\mathbf{A} = \begin{pmatrix} 1 & x_0 & x_0^2 & \ldots & x_0^n \\ 1 & x_1 & x_1^2 & \ldots & x_1^n \\ \ldots & \ldots & \ldots & \ldots & \ldots \\ 1 & x_n & x_n^2 & \ldots & x_n^n \\ \end{pmatrix}$

Система линейных алгебраических уравнений (*) относительно неизвестных $c_i$ будет иметь решение, если определитель матрицы $\mathbf{A}$ отличен от нуля.

Определитель матрицы $\mathbf{A}$ называют определителем Вандермонда, его можно вычислить по следующей формуле:

$\mathbf{detA} = \prod_{i,j=0 \\ i \neq j }^n (x_i - x_j) \neq 0$