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

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

(Различия между версиями)
Перейти к: навигация, поиск
Строка 1: Строка 1:
-
Статья в процессе написания... Ожидается в скором времени :)
+
== Постановка задачи ==
-
[[Категория:Учебные курсы]]
+
Пусть задана функция <tex>\varphi(x)</tex> на некотором интервале <tex>[x_0,x_n]</tex>. Предположим, что мы знаем значения этой функции в ''n'' точках. Известно, что через ''n''+1 точек на плоскости можно провести кривую, являющуюся графиком степенного многочлена (полинома) степени ''n'', причем такой полином единственный.
 +
 
 +
Этот факт лежит в основе так называемой полиномиальной интерполяции, при которой функцию <tex>\varphi(x)</tex> строят в виде полинома степени ''n''.
 +
 
 +
Если на всём интервале <tex>[x_0,x_n]</tex>, содержащем ''n''+1 узлов, строят один полином степени ''n'', то говорят о глобальной интерполяции. Если же интервал разбивается на отрезки, и на каждом из отрезков строится свой полином, то говорят о локальной интерполяции.
 +
 
 +
=== Полином в каноническом виде ===
 +
 
 +
В качестве аппроксимирующей функции выбирается полином степени <tex>n</tex> в каноническом виде:
 +
 
 +
<math> \varphi(x)=P_n(x)=c_0+c_1x+c_2x^2+ \ldots + c_nx^n </math>
 +
 
 +
Коэффициенты полинома <tex>c_i</tex> определяются из условий Лагранжа <tex>P_n(x_i)=y_i</tex>, <tex>i=1, \ldots, n</tex>, что с учётом предыдущего выражения даёт систему уравнений с ''n''+1 неизвестными:
 +
 
 +
<tex>
 +
\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 \\
 +
\hdotsfor{1} \\
 +
c_0 + c_1x_n + c_2x_n^2 + \ldots + c_nx_n^n = y_n
 +
\end{matrix}
 +
</tex>
 +
 
 +
Обозначим систему таких уравнений символом (*) и перепишем её следующим образом:
 +
 
 +
<tex> \sum_{p=0}^n c_i^p = y_i, \quad i=1, \ldots, n </tex>
 +
 
 +
или в матричной форме: <tex>\mathbf{Ac}=\mathbf{y},</tex> где <tex>\mathbf{c}</tex> --- вектор-столбец, содержащий неизвестные коэффициенты <tex>c_i</tex>, <tex>\mathbf{y}</tex> --- вектор-столбец, составленный из табличных значений функции <tex>y_i</tex>, а матрица <tex>\mathbf{A}</tex> имеет вид:
 +
 
 +
<tex> \mathbf{A} =
 +
\begin{pmatrix}
 +
1 & x_0 & x_0^2 & \ldots & x_0^n \\
 +
1 & x_1 & x_1^2 & \ldots & x_1^n \\
 +
\hdotsfor{5} \\
 +
1 & x_n & x_n^2 & \ldots & x_n^n \\
 +
\end{pmatrix}
 +
</tex>
 +
 
 +
Система линейных алгебраических уравнений (*) относительно неизвестных <tex>c_i</tex> будет иметь решение, если определитель матрицы <tex>\mathbf{A}</tex> отличен от нуля.
 +
 
 +
Определитель матрицы <tex>\mathbf{A}</tex> называют определителем Вандермонда, его можно вычислить по следующей формуле:
 +
 
 +
<tex> \text{det}\mathbf{A} = \prod_{\substack{i,j=0 \\ i \neq j }}^n (x_i - x_j) \neq 0 </tex>
 +
 
 +
{{Stub}}

Версия 12:10, 26 сентября 2008

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

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

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

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

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

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

<math> \varphi(x)=P_n(x)=c_0+c_1x+c_2x^2+ \ldots + c_nx^n </math>

Коэффициенты полинома 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 \\
\hdotsfor{1} \\
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 \\
   \hdotsfor{5} \\
   1 & x_n & x_n^2 & \ldots & x_n^n \\
 \end{pmatrix}

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

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

 \text{det}\mathbf{A} = \prod_{\substack{i,j=0 \\ i \neq j }}^n (x_i - x_j) \neq 0

Личные инструменты