УказательРазделыОбозначенияАвторО проекте


p(x)= p_{0}x^{n-1} + p_{1}x^{n-2} + \ldots + p_{n-1}
p(x_j) = y_j \quad npu \ j \in \{1,\dots, n \}
W(x)=\prod_{j=1}^n (x-x_j)
Т

Теорема. Пусть y_j \ne 0 при j \in \{1,\dots, n \}. Вычисляем последовательность значений

\widetilde \tau_k = \sum_{j=0}^{n} \frac{1}{y_j} \frac{x_j^{k}}{W^{\prime}(x_j)} \quad npu \ k \in \{0,\dots, 2\,n-2 \}

Интерполяционный полином может быть представлен в виде ганкелевого полинома

p(x)= (-1)^{n(n-1)/2} \left(\prod_{j=1}^n y_j \right) \underbrace{\left| \begin{array}{lllll} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 & \dots & \widetilde \tau_{n-1} \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 & \dots & \widetilde \tau_{n} \\ \vdots & \vdots & \vdots & & \vdots \\ \widetilde \tau_{n-2} & \widetilde \tau_{n-1} & \widetilde \tau_{n} & \dots & \widetilde \tau_{2n-3} \\ 1 & x & x^2 & \dots & x^{n-1} \end{array} \right|}_{\mathcal H_{N-1}(x; \{ \widetilde \tau \})} \, .

П

Пример. Построить интерполяционный полином по таблице

\begin{array}{c||c|c|c|c|c|c|c} x & -2 & -1 & 0 & 1 & 2 & 3 & 4 \\ \hline y & 30 & -7 & 8 & 9 & 11 & 35 & 60 \end{array}

Решение. Вычисляем последовательность

\widetilde \tau_0=\frac{\scriptstyle 48569}{\scriptstyle 19958400}, \ \widetilde \tau_1=-\frac{\scriptstyle 1501}{\scriptstyle 1247400},\ \widetilde \tau_2=\frac{\scriptstyle 1021}{\scriptstyle 249480},\ \widetilde \tau_3=\frac{\scriptstyle 1733}{\scriptstyle 311850}, \dots, \widetilde \tau_{12}=\frac{\scriptstyle 168257557}{\scriptstyle 623700}

и вычисляем первые два ганкелевых полинома

\mathcal H_1(x;\{\widetilde \tau\}) \equiv \frac{48569}{19958400}x+\frac{1501}{1247400}\, ,
\mathcal H_2(x;\{\widetilde \tau\}) \equiv \underbrace{\frac{79273}{9313920000}}_{\widetilde h_{2,0} }x^2 \underbrace{-\frac{128867}{6985440000}}_{\widetilde h_{2,1} }x\underbrace{-\frac{40927}{1746360000}}_{\widetilde h_{2,2} } \, .

Вычисление \mathcal H_3(x;\{\widetilde \tau\}) может быть организовано с помощью JJ-тождества:

\mathcal H_3(x;\{\widetilde \tau\}) \equiv - \left(\frac{\widetilde h_{3,0}}{\widetilde h_{2,0}}\right)^2 \mathcal H_1(x;\{\widetilde \tau\})+ \frac{h_{\widetilde 3,0}}{\widetilde h_{2,0}}\left(x-\frac{\widetilde h_{2,1}}{\widetilde h_{2,0}}+\frac{\widetilde h_{3,1}}{\widetilde h_{3,0}} \right)\mathcal H_2(x;\{\widetilde \tau\})

где все константы известны, кроме \widetilde h_{3,0}=H_3(\{\widetilde \tau\}) and \widetilde h_{3,1}. Для нахождения этих констант, используем разложение определителя H_3 по последней строке:

\widetilde h_{3,0}= \widetilde \tau_4 \widetilde h_{2,0}+ \widetilde \tau_3 h_{2,1}+ \widetilde \tau_2 \widetilde h_{2,2}=-\frac{7159}{111767040000} \, ,
\widetilde h_{3,1}=-(\widetilde \tau_5 \widetilde h_{2,0}+ \widetilde \tau_4 \widetilde h_{2,1}+\widetilde \tau_3 \widetilde h_{2,2})=\frac{277}{1128960000} \, .

Поэтому

\mathcal H_3(x;\{\widetilde \tau\}) \equiv \frac{1}{111767040000}(-7159\,x^3+27423\,x^2-21498\,x-40400)\, ,

Продолжая рекурсивное применение JJ-тождества, получаем ганкелевы полиномы следующих порядков:

\begin{array}{lll} \mathcal H_4(x;\{\widetilde \tau\}) & \equiv & -\frac{1}{\scriptstyle 1451520000}(4\,x^4-7\,x^3+3\,x^2-2\,x-16) \ , \\ \mathcal H_5(x;\{\widetilde \tau\}) & \equiv & \frac{1}{\scriptstyle 9313920000}\left(-\frac{77}{12}\,x^5+\frac{77}{2}\,x^4-\frac{61}{4}\,x^3-\frac{715}{6}\,x^2+124\,x+\frac{304}{3}\right) , \\ \mathcal H_6(x;\{\widetilde \tau\})& \equiv & \frac{1}{\scriptstyle 349272000} \bigg(\frac{3}{80}\,x^6-\frac{59}{80}\,x^5+\frac{51}{16}\,x^4-\frac{9}{16}\,x^3-\frac{409}{40}\,x^2+\frac{93}{10}\,x+8\bigg) \end{array}

и интерполяционный полином равен p(x) \equiv 349272000 \mathcal H_6(x;\{\widetilde \tau\}).

П

Пример. В предположении, что интерполяционная таблица предыдущего примера изначально содержащая значения полинома f(x) степени \deg f(x) \le 2, впоследствии могла подвергнуться искажениям в количестве до двух значений. Определить места искажений и восстановить истинный полином f(x).

Решение. Если проверить полиномы из решения предыдущего примера на приводимость над \mathbb Z, то оказывается, что у полинома \mathcal H_4 выделяются линейные множители:

\mathcal H_4(x;\{\widetilde \tau\})\equiv -\frac{1}{1451520000}(x-2)(x+1)(4\,x^2-3\,x+8) \, .

Значения x=-1 и x=2 показывают места искажений значений полинома f(x)= 4\,x^2-3\,x+8:

f(-1) \ne - 7, f(2) \ne 11 \, .

Но значения f(x) во всех остальных узлах интерполяции совпадают с табличными!


2018/02/27 12:20 редактировал au