\section{Интерполяционная формула Ньютона} \begin{myUnnumberedDefinition} Назовем разделенной разностью первого порядка, построенной по узлам \(x_i\) и \(x_j\), следующее соотношение: \begin{equation} \label{eq_2_3_1} f(x_i, x_j) = \frac{f(x_j) - f(x_i)}{x_j - x_i} \end{equation} Разделенной разностью второго порядка по узлам \(x_{i-1}, x_i, x_{i+1}\) называется соотношение: \[ f(x_{i-1}, x_i, x_{i+1}) = \frac{f(x_{i-1}, x_i) - f(x_i, x_{i+1})}{x_{i-1} - x_{i+1}} \] Аналогично определяем разделенную разность больших порядков. \end{myUnnumberedDefinition} \begin{myUnnumberedStatement} Разделенную разность \(k\)--го порядка можно представить в виде: \[ f(x_0, x_1, \ldots, x_k) = \sum_{i=0}^k{\frac{f(x_i)}{\omega'_{0, k}(x_i)}} \] Причем запись \( \omega_{a, b}(x) \) означает: \[ \omega_{a, b}(x) = (x - x_a)(x - x_{a+1})\cdot \ldots \cdot (x - x_b), a < b \] \end{myUnnumberedStatement} \begin{proof} Не ограничивая общности, будем рассматривать узлы с индексами \( 0..k, k \in \mathbf{N} \). Докажем утверждение по индукции.\\ База: \[ k=1: f(x_0, x_1) = \frac{f(x_0)}{x_0-x_1} + \frac{f(x_1)}{x_1-x_0} = \] \[ \frac{f(x_0)}{\omega'_{0, 1}(x_0)} + \frac{f(x_1)}{\omega'_{0, 1}(x_1)} \] Переход: \[ k = l: \] \[ f(x_0, \ldots, x_l) = \sum_{i=0}^l { \frac{f(x_i)}{\omega'_{0, l}(x_i)} } \] Покажем что \( f(x_0, \ldots, x_{l+1}) = \sum_{i=0}^{l+1} { \frac{f(x_i)}{\omega'_{0, l+1}(x_i)} } \) : \[ f(x_0, \ldots, x_{l+1}) = \frac{f(x_1, \ldots, x_{l+1}) - f(x_0, \ldots, x_l)}{x_{l+1}-x_0} = \] \[ \frac{1}{x_{l+1}-x_0}( \sum_{i=1}^{l+1} { \frac{f(x_i)}{ \omega'_{1, l+1}(x_i) } } - \sum_{i=0}^l { \frac{f(x_i)}{ \omega'_{0, l}(x_i) } }) = \] \[ \frac{1}{x_{l+1}-x_0}( \frac{f(x_{l+1})}{ \omega'_{1, l+1}(x_{l+1}) } - \frac{f(x_0)}{ \omega'_{0, l}(x_0) } + \sum_{i=1}^l { \frac{f(x_i)}{ \omega'_{1, l+1}(x_i) } - \frac{f(x_i)}{ \omega'_{0, l}(x_i) } } ) \] Рассмотрим знаменатели слагаемых отдельно: \[ (x_{l+1}-x_0) \omega'_{1, l+1}(x_{l+1}) = \omega'_{0, l+1}(x_{l+1}) \] \[ (x_{l+1}-x_0) \omega'_{0, l}(x_0) = - \omega'_{0, l+1}(x_0) \] \[ \frac{1}{ \omega'_{1, l+1}(x_i) } - \frac{1}{ \omega'_{0, l}(x_i) } = \frac{(x_i - x_0)}{ \omega'_{0, l+1}(x_i) } - \frac{(x_i - x_{l+1})}{ \omega'_{0, l+1}(x_i) } = \frac{(x_{l+1} - x_0)}{ \omega'_{0, l+1}(x_i) } \] Подставив преобразованные слагаемые, получим: \[ \frac{f(x_{0})}{ \omega'_{0, l+1}(x_{0}) } + \frac{f(x_{l+1})}{ \omega'_{0, l+1}(x_{l+1}) } + \sum_{i=1}^l { \frac{f(x_i)}{ \omega'_{0, l+1}(x_i) } } \] Что и требовалось доказать. \end{proof} \begin{myUnnumberedDefinition} Назовем интерполяционным полиномом Ньютона функции \( f(x) \) по узлам \( \{X_i\}_0^n \) полином степени \(n \): \begin{equation} \label{eq_2_3_2} N_n(x) = f(x_0) + (x - x_0)f(x_0, x_1) + \ldots + \Pi_{i=0}^{n-1}f(x_0,x_1,\ldots, x_n)(x - x_i) \end{equation} \end{myUnnumberedDefinition} Покажем, что \(N_n(x)\) интерполяционный полином: \[ N_n(x_i) = f(x_0) + (x_i - x_0)f(x_0, x_1) + \ldots + \Pi_{i=0}^{i-1}f(x_0,x_1,\ldots, x_i)(x - x_i) + 0 \] Эта сумма представляет собой разделенную разность порядка i, равную как раз \(f(x_i)\). \begin{myUnnumberedNote} Полученный полином -- тот же полином Лагранжа, только записанный в другой форме. \\ Соответственно, его погрешность та же, что и у полинома Лагранжа. \end{myUnnumberedNote} Отличие полинома Ньютона от Лагранжа в том, что для увеличения точности \( N_n(x)\) надо только добавить информацию о новых узлах и не надо пересчитывать значения для старых. \section{Интерполирование с кратными узлами. Интерполяционная формула Эрмита} Пусть имеется m узлов: \(x_0, x_1, \ldots, x_m\), при этом \( a_k \in \mathbf{N}, k = \overline{0, m} \) -- кратность каждого узла ( \( a_0 + \ldots a_m = n+1\), где n -- степень интерполирующего полинома ). \begin{myUnnumberedDefinition} Назовем интерполяционным полиномом Эрмита полином: \begin{equation} \label{eq_2_4_1} H_n(x) = \sum^{m}_{k=0}{\sum_{i=0}^{a_k-1}{c_{k, i}(x)f^{(i)}(x_k) }}, \end{equation} где \(c_{k, i}(x)\) - полином \(n\)-й степени, коэффициенты которого находятся из условия: \[ H^{(i)}_n(x_k) = f^{(i)}(x_k), k = \overline{0, n}, i = \overline{0, a_k-1} \] \end{myUnnumberedDefinition} Существование и единственность данного полинома очевидны, перейдем сразу к построению \(H_n(x)\). В общем случае выражение для полинома Эрмита достаточно громоздко, поэтому ограничимся рассмотрением конкретной задачи: \\ Построить \( H_3(x) = c_0(x)f(x_0) + c_1(x)f(x_1) + c_2(x)f(x_2) + b(x)f'(x_1) \). \\ Запишем условия, при которых данный полином будет интерполяционным: \[ c_0(x_0) = 1, c_1(x_0) = 0, c_2(x_0) = 0, b(x_0) = 0, \] \[ c_0(x_1) = 0, c_1(x_1) = 1, c_2(x_1) = 0, b(x_1) = 0, \] \[ c_0(x_2) = 0, c_1(x_2) = 0, c_2(x_2) = 1, b(x_2) = 0, \] \[ c_0'(x_1) = 0, c_1'(x_1) = 0, c_2'(x_1) = 0, b'(x_1) = 1. \] Будем искать \( c_0(x)\) в виде \(k(x-x_1)^2(x-x_2), k \) выбираем из условия \(c_0(x_0) = 1\): \[ 1 = k(x_0-x_1)^2(x_0-x_2) \Longrightarrow c_0(x) = \frac{(x-x_1)^2(x-x_2)}{(x_0-x_1)^2(x_0-x_2)} \] Аналогично получаем выражение для \( c_2(x) \): \[ c_2(x) = \frac{(x-x_1)^2(x-x_0)}{(x_2-x_1)^2(x_2-x_0)} \] Теперь вычислим \( b(x) \): \[ b_1(x) = k(x - x_0)(x - x_1)(x - x_2) \] \[ b'_1(x_1) = k(x_1 - x_0)(x_1 - x_2) = 1 \] Откуда получаем \( b_1(x) = \frac{(x-x_0)(x-x_2)}{(x_1-x_2)^2(x_1-x_2)}(x-x_1) \). Далее пусть \(c_1(x) = (x-x_0)(x-x_2)(ax+b)\): \[ c_1(x_1) = 1 = (x_1-x_0)(x_1-x_2)(ax_1+b) \] \[ c_1'(x_1) = 0 = a(x_1-x_0)(x_1-x_2) + (ax_1+b)(2x_1-x_0-x_2) \] Из этих уравнений получаем: \[ a = -\frac{(2x_1-x_0-x_2)}{{(x_1-x_0)}^2{(x_1-x_2)}^2} \] \[ b = \frac{1}{(x_1-x_0)(x_1-x_2)}[1 + \frac{x_1(2x_1-x_0-x_2)}{(x_1-x_0)(x_1-x_2)}] \] Подставляя найденные выражения, имеем: \[ H_3(x) = f(x_0) \cdot \frac{(x-x_1)^2(x-x_2)}{(x_0-x_1)^2(x_0-x_2)} + f(x_1) \cdot \frac{(x-x_0)(x-x_2)}{(x_1-x_0)(x_1-x_2)}\cdot \] \[ (1 + \frac{(x_1-x)(2x_1 - x_0 - x_2)}{(x_1-x_0)(x_1-x_2)}) + f(x_2) \cdot \frac{(x-x_1)^2(x-x_0)} {(x_2-x_1)^2(x_2-x_0)} + \] \[ f'(x_1) \cdot \frac{(x-x_0)(x-x_2)}{(x_1-x_2)^2(x_1-x_2)}(x-x_1) \] \subsection{Погрешность полинома Эрмита} \[ \psi_{H_3(x)} = f(x) - H_3(x) \] Введем функцию \( g(s) = f(s) - H_3(s) - k \omega(s) \), где \( k \) -- константа, \( \omega(s) = (x - x_0){(x - x_1)}^2(x - x_2) \). Константу \( k \) получаем из условия \( g(x) = 0:\) \[ k = \frac{f(x) - H_3(x)}{\omega(x)} \] Далее для применения теоремы Ролля требуем \( \exists f^{(4)}(x) \in [a, b] \). Применив несколько раз теорему Ролля к g(s), получим: \[ \exists \xi \in (a, b) : g^{(4)}(\xi) = 0, \] откуда и получем окончательную оценку \[ f(x) - H_3(x) = \frac{f^{(4)}}{4!}\omega(x) \]