Эрмитова интерполяция

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

Эрмитова интерполяция - метод полиномиальной интерполяции, названный в честь французского математика Шарля Эрмита. Многочлены Эрмита тесно связаны с многочленами Ньютона.

В отличие от интерполяции Ньютона, эрмитова интерполяция строит многочлен, значения которого в выбранных точках совпадают со значениями исходной функции в этих точках, и производные многочлена в данных точках совпадают со значениями производных функции (до некоторого порядка m). Это означает, что n(m + 1) величин


\begin{matrix}
(x_0, y_0), &(x_1, y_1), &\ldots, &(x_{n-1}, y_{n-1}), \\
(x_0, y_0'), &(x_1, y_1'), &\ldots, &(x_{n-1}, y_{n-1}'), \\
\vdots & \vdots & &\vdots  \\
(x_0, y_0^{(m)}), &(x_1, y_1^{(m)}), &\ldots, &(x_{n-1}, y_{n-1}^{(m)})
\end{matrix}

должны быть известны, тогда как для ньютоновской интерполяции необходимы только первые n значений. Полученный многочлен может иметь степень не более, чем n(m + 1) − 1, максимальная степень многочлена Ньютона же равна n − 1. (В общем случае m не обязательно должно быть фиксировано, то есть в одних точках может быть известно значение большего количества производных, чем в других. В этом случае многочлен будет иметь степень N − 1, где N - число известных значений.)

Использование[править | править вики-текст]

Простой случай[править | править вики-текст]

При использовании разделенных разностей для вычисления многочлена Эрмита, первым шагом является копирование каждой точки m раз. (Здесь мы рассмотрим простой случай, когда для всех точек m = 1.) Поэтому, дана n + 1 точка x_0, x_1, x_2, \ldots, x_n, и значения f(x_0), f(x_1), \ldots, f(x_n) и f'(x_0), f'(x_1), \ldots, f'(x_n) функции f, которую мы хотим интерполировать. Определим новый набор данных

z_0, z_1, \ldots, z_{2n+1}

такой, что

z_{2i}=z_{2i+1}=x_i

Теперь определим таблицу разделенных разностей для точек z_0, z_1, \ldots, z_{2n+1}. Однако, для некоторых разделенных разностей

z_i = z_{i + 1}\implies f[z_i, z_{i+1}] = \frac{f(z_{i+1})-f(z_{i})}{z_{i+1}-z_{i}} = \frac{0}{0}

что есть неопределенность! В этом случае заменим эту разделенную разность значением f'(z_i), а другие вычислим обычным способом.

Общий случай[править | править вики-текст]

В общем случае полагаем, что в данных точках x_i известны производные функции f до порядка k включительно. Тогда набор данных z_0, z_1, \ldots, z_{N} содержит k копий x_i. При создании таблицы разделенных разностей при j = 2, 3, \ldots, k одинаковые значения будут вычислены как

\frac{f^{(j)}(x_i)}{j!}.

Например,

f[x_i, x_i, x_i]=\frac{f''(x_i)}{2}
f[x_i, x_i, x_i, x_i]=\frac{f^{(3)}(x_i)}{6}

и так далее.

Пример[править | править вики-текст]

Рассмотрим функцию f(x) = x^8 + 1. Вычислив значения функции и ее первых двух производных в точках x \in \{-1, 0, 1\}, получим следующие данные:

x ƒ(x) ƒ'(x) ƒ''(x)
−1 2 −8 56
0 1 0 0
1 2 8 56

Так как мы работаем с двумя производными, строим множество \{z_i\} = \{-1, -1, -1, 0, 0, 0, 1, 1, 1\}. Таблица разделенных разностей тогда имеет вид:


\begin{matrix}
z_0 = -1  &  f[z_0] = 2  &                          &                         &                           &      &     &   &    & \\
          &              &  \frac{f'(z_0)}{1} = -8  &                         &                           &      &     &   &    & \\
z_1 = -1  &  f[z_1] = 2  &                          & \frac{f''(z_1)}{2} = 28 &                           &      &     &   &    & \\
          &              &  \frac{f'(z_1)}{1} = -8  &                         &  f[z_3,z_2,z_1,z_0] = -21 &      &     &   &    & \\
z_2 = -1  &  f[z_2] = 2  &                          & f[z_3,z_2,z_1] = 7      &                           &  15  &     &   &    & \\
          &              &  f[z_3,z_2] = -1         &                         &  f[z_4,z_3,z_2,z_1] = -6  &      & -10 &   &    & \\
z_3 =  0  &  f[z_3] = 1  &                          & f[z_4,z_3,z_2] = 1      &                           &   5  &     & 4 &    & \\
          &              &  \frac{f'(z_3)}{1} = 0   &                         &  f[z_5,z_4,z_3,z_2] = -1  &      &  -2 &   & -1 & \\
z_4 =  0  &  f[z_4] = 1  &                          & \frac{f''(z_4)}{2} = 0  &                           &   1  &     & 2 &    & 1 \\
          &              &  \frac{f'(z_4)}{1} = 0   &                         &  f[z_6,z_5,z_4,z_3] =  1  &      &   2 &   &  1 & \\
z_5 =  0  &  f[z_5] = 1  &                          & f[z_6,z_5,z_4] = 1      &                           &   5  &     & 4 &    & \\
          &              &  f[z_6,z_5] = 1          &                         &  f[z_7,z_6,z_5,z_4] =  6  &      &  10 &   &    & \\
z_6 =  1  &  f[z_6] = 2  &                          & f[z_7,z_6,z_5] = 7      &                           &  15  &     &   &    & \\
          &              &  \frac{f'(z_7)}{1} = 8   &                         &  f[z_8,z_7,z_6,z_5] =  21 &      &     &   &    & \\
z_7 =  1  &  f[z_7] = 2  &                          & \frac{f''(z_7)}{2} = 28 &                           &      &     &   &    & \\
          &              &  \frac{f'(z_8)}{1} = 8   &                         &                           &      &     &   &    & \\
z_8 =  1  &  f[z_8] = 2  &                          &                         &                           &      &     &   &    & \\
\end{matrix}

и получаем многочлен


\begin{align}
P(x) &= 2 - 8(x+1) + 28(x+1) ^2 - 21 (x+1)^3 + 15x(x+1)^3 - 10x^2(x+1)^3 \\
&\quad{} + 4x^3(x+1)^3 -1x^3(x+1)^3(x-1)+x^3(x+1)^3(x-1)^2 \\
&=2 - 8 + 28 - 21 - 8x + 56x - 63x + 15x + 28x^2 - 63x^2 + 45x^2 - 10x^2 - 21x^3 \\
&\quad {}+ 45x^3 - 30x^3 + 4x^3 + x^3 + x^3 + 15x^4 - 30x^4 + 12x^4 + 2x^4 + x^4 \\
&\quad {}- 10x^5 + 12x^5 - 2x^5 + 4x^5 - 2x^5 - 2x^5 - x^6 + x^6 - x^7 + x^7 + x^8 \\
&= x^8 + 1.
\end{align}

взятием коэффициентов диагонали таблицы разделенных разностей, и умножением коэффициента с номером k на \prod_{i=0}^{k-1} (x - z_i), как при получении многочлена Ньютона.

Ошибка[править | править вики-текст]

Назовем найденный многочлен H и исходную функцию f. Для точек x \in [x_0, x_n], функция ошибки определяется как

f(x) - H(x) = \frac{f^{(K)}(c)}{K!}\prod_{i}(x - x_i)^{k_i},

где c неизвестная из диапазона [x_0, x_N], K - общее число данных значений плюс один, а k_i - число производных, известных в каждой точке x_i, плюс один.

См. также[править | править вики-текст]