Задача полиномиальной интерполяции при наличии в таблице несистематических погрешностей в значениях функции решается методом наименьших квадратов (при наличии гипотезы о степени полинома). В настоящем разделе мы будем решать задачу о поиске полинома $ f(x) $, для которого изначально истинная интерполяционная таблица: $$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & \widehat y_1 & \widehat y_2 & \ldots & \widehat y_N \end{array} \quad npu \ \{ y_j=f(x_j)\}_{j=1}^N $$ впоследствии была подвергнута искажениям в некоторых своих значениях $$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & y_1 & y_2 & \ldots & y_N \end{array} $$ При этом, нам заранее не известны ни количество испорченных значений, ни их расположение в таблице. Делается следующее предположение: количество оставшихся верными значений $ y $ в испорченной таблице избыточно по отношению к степени полинома $ f(x) $, т.е. если $ E $ — верхняя оценка количества ошибок в таблице, то $ N-E > 1+\deg f $. Можно ли восстановить по испорченной таблице исходный полином $ f(x) $?

Всюду в дальнейшем теоретические результаты иллюстрируются примерами полиномов над $ \mathbb Q $. Это ограничение не принципиально: все результаты будут справедливы в $ \mathbb R, \mathbb C $ и, при некоторых ограничениях, в конечных полях.

Предположим, что задана таблица $$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & y_1 & y_2 & \ldots & y_N \end{array} \quad \quad \{x_j,y_j\}_{j=1}^N \subset \mathbb Q, $$ узлы $ \{x_j\}_{j=1}^N $ — все различны. Эта таблица однозначно определяет полином $ f(x) \in \mathbb Q[x] $ такой, что $ \left\{f(x_j)=y_j \right\}_{j=1}^N $ и $ \deg f \le N-1 $. Если же оказывается, что $ n=\deg f < N-1 $, то получается, что таблица избыточна: тот же полином $ f(x) $ можно построить — например, в формах Лагранжа или Ньютона — по любой выборке из этой таблицы, состоящей из $ (n+1) $-го узла.

Можно ли установить точную степень полинома $ f(x) $, не вычисляя его непосредственно?

Обозначим $$ W(x)=\prod_{j=1}^N (x-x_j) $$ и вычислим две последовательности: $$ \tau_k = \sum_{j=1}^{N} y_j \frac{x_j^{k}}{W^{\prime}(x_j)} \quad npu \ k \in \{0,\dots, 2\,n-2 \} $$ и, при дополнительном предположении $ \{ y_j\ne 0\}_{j=1}^N $, $$ \widetilde \tau_k = \sum_{j=1}^{N} \frac{1}{y_j} \frac{x_j^{k}}{W^{\prime}(x_j)} \quad npu \ k \in \{0,\dots, 2\,n-2 \} \, . $$ Каждое из этих выражений является симметрической функцией пар значений $ (x_1,y_1),\dots, (x_N, y_N) $ в том смысле, что значение выражения не меняется при произвольной перестановке этих пар.

Теорема 1. Для того, чтобы полином, построенный по таблице, имел степень $ n<N-1 $ необходимо и достаточно, чтобы были выполнены условия $$ \tau_0=0,\dots, \tau_{N-n-2}=0, \tau_{N-n-1} \ne 0 \, . $$

Доказательство следует из равенства Эйлера-Лагранжа: $$ \sum_{j=1}^N \frac{x_j^k}{W'(x_j)}=\left\{ \begin{array}{cc} 0 & npu \ k< N-1; \\ 1 & npu \ k= N-1. \end{array} \right. $$ Если $ f(x)=a_0x^n+\dots + a_n $ при $ a_0 \ne 0 $ и $ \{y_j=f(x_j)\}_{j=1}^N $, то $$ \tau_0 = a_0 \sum_{j=1}^N \frac{x_j^n}{W'(x_j)} + a_1 \sum_{j=1}^N \frac{x_j^{n-1}}{W'(x_j)}+\dots + a_n \sum_{j=1}^N \frac{1}{W'(x_j)}=0 \, . $$ Аналогично, если $ n< N-2 $ то $$ \tau_1 = a_0 \sum_{j=1}^N \frac{x_j^{n+1}}{W'(x_j)} + a_1 \sum_{j=1}^N \frac{x_j^{n}}{W'(x_j)}+\dots + a_n \sum_{j=1}^N \frac{x_j}{W'(x_j)}=0 \, . $$ И так далее вплоть до значения $ \tau_{N-n-2} $, которое также равно $ 0_{} $ на основании равенств Эйлера-Лагранжа. Но вот $$ \tau_{N-n-1} = a_0 \sum_{j=1}^N \frac{x_j^{N-1}}{W'(x_j)} + a_1 \sum_{j=1}^N \frac{x_j^{N-2}}{W'(x_j)}+\dots + a_n \sum_{j=1}^N \frac{x_j^{N-n-1}}{W'(x_j)}=a_0 \ne 0 \, . $$

♦

Теорема $ 1 $ позволяет проверить наличие ошибок в интерполяционной таблице, изначально составленной с избыточным количеством значений: $ N-1 > n:= \deg f $. Начинаем последовательно вычислять $ \tau_0, \tau_1, \dots , \tau_{N-n-2} $. Если хотя бы одно из этих значений отлично от нуля, то в таблице присутствует хотя бы одна ошибка.

Если факт наличия ошибки установлен, то на основании вычисленных величин $ \{\tau_k\} $ можно организовать и процедуру определения числа этих ошибок и их расположения в таблице: определить конкретные узлы $ \{x_j\} $, в которых произошло искажение значений полинома $ f(x) $. Это алгоритм будет изложен в следующем пункте, а пока произведем подготовительные работы.

Последовательности $ \{ \tau_k\} $ и $ \{\widetilde \tau_k \} $ порождают соответствующие последовательности ганкелевых полиномов $$ \mathcal H_1(x; \{\tau\})=\left|\begin{array}{cc} \tau_0 & \tau_1 \\ 1 & x \end{array} \right| ,\mathcal H_2(x; \{\tau\}) = \left|\begin{array}{ccc} \tau_0 & \tau_1 & \tau_2 \\ \tau_1 & \tau_2 & \tau_3 \\ 1 & x & x^2 \end{array} \right|, \mathcal H_3(x; \{\tau\}) = \left|\begin{array}{cccc} \tau_0 & \tau_1 & \tau_2 & \tau_3 \\ \tau_1 & \tau_2 & \tau_3 & \tau_4 \\ \tau_2 & \tau_3 & \tau_4 & \tau_5 \\ 1 & x & x^2 & x^3 \end{array} \right|, \dots $$ и $$ \mathcal H_1(x; \{\widetilde \tau\})=\left|\begin{array}{cc} \widetilde \tau_0 & \widetilde \tau_1 \\ 1 & x \end{array} \right| ,\mathcal H_2(x; \{\widetilde \tau\}) = \left|\begin{array}{ccc} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 \\ 1 & x & x^2 \end{array} \right|, \mathcal H_3(x; \{\widetilde \tau\}) = \left|\begin{array}{cccc} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 & \widetilde \tau_4 \\ \widetilde \tau_2 & \widetilde \tau_3 & \widetilde \tau_4 & \widetilde \tau_5 \\ 1 & x & x^2 & x^3 \end{array} \right|, \dots $$ Посмотрим как ведут себя эти полиномы при различных таблицах значений. Начнем со второй последовательности.

Теорема 2. Пусть таблица

$$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & y_1 & y_2 & \ldots & y_N \end{array} $$ состоит из значений полинома $ f(x) $ степени $ n \le N-1 $ и, вдобавок, $ \{ y_j\ne 0\}_{j=1}^N $. Тогда этот полином может быть представлен в виде $$ f(x)\equiv (-1)^{n(n+1)/2} \left(\prod_{j=1}^N y_j \right) \mathcal H_{n}(x; \{ \widetilde \tau \}) \equiv (-1)^{n(n+1)/2} \left(\prod_{j=1}^N y_j \right) \left| \begin{array}{lllll} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 & \dots & \widetilde \tau_{n} \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 & \dots & \widetilde \tau_{n+1} \\ \vdots & \vdots & \vdots & & \vdots \\ \widetilde \tau_{n-2} & \widetilde \tau_{n-1} & \widetilde \tau_{n} & \dots & \widetilde \tau_{2n-1} \\ 1 & x & x^2 & \dots & x^{n} \end{array} \right|\, . $$

Таким образом, теорема дает еще одно представление интерполяционного полинома — альтернативное формам Лагранжа и Ньютона. Практическая польза от такой альтернативы неочевидна, поскольку вычисление определителя, зависящего от параметра — та еще проблема! К счастью, имеются соображения, упрощающие процедуру вычисления ганкелевого полинома.

Пример 1. Построить интерполяционный полином по таблице $$ \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\})=\left|\begin{array}{ccc} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 \\ 1 & x & x^2 \end{array} \right| \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\})= \left|\begin{array}{cccc} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 & \widetilde \tau_4 \\ \widetilde \tau_2 & \widetilde \tau_3 & \widetilde \tau_4 & \widetilde \tau_5 \\ 1 & x & x^2 & x^3 \end{array} \right|=\widetilde h_{3,0}x^3+\widetilde h_{3,1}x^2+\dots $$ может быть организовано с помощью 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} $ и $ \widetilde h_{3,1} $. Для нахождения первой из этих констант, используем разложение его детерминантного представления по последней строке: $$ \widetilde h_{3,0}=\left|\begin{array}{lll} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 \\ \widetilde \tau_2 & \widetilde \tau_3 & \widetilde \tau_4 \end{array} \right|= \widetilde \tau_4 \widetilde h_{2,0}+ \widetilde \tau_3 \widetilde h_{2,1}+ \widetilde \tau_2 \widetilde h_{2,2}=-\frac{7159}{111767040000} \, . $$ А определитель, выражающий $ \widetilde h_{3,1} $ сначала транспонируем, а потом также разложим по последней строке $$ \widetilde h_{3,1}=-\left|\begin{array}{lll} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_3 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_4 \\ \widetilde \tau_2 & \widetilde \tau_3 & \widetilde \tau_5 \end{array} \right|=- \left|\begin{array}{lll} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 \\ \widetilde \tau_1 & \widetilde \tau_2 & \widetilde \tau_3 \\ \widetilde \tau_3 & \widetilde \tau_4 & \widetilde \tau_5 \end{array} \right|= -(\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} $$ и интерполяционный полином равен $ 349272000 \mathcal H_6(x;\{\widetilde \tau\}) $. ♦

Рассмотрим теперь другую последовательность ганкелевых полиномов — ту, что порождается последовательностью $$ \tau_k = \sum_{j=1}^{N} y_j \frac{x_j^{k}}{W^{\prime}(x_j)} \quad npu \ k \in \{0,\dots, 2\,n-2 \} $$ Поисследуем как она будет вести себя на интерполяционных таблицах — избыточных, но содержащих некоторое количество ошибочных значений.

Пример 2. Таблица

$$ \begin{array}{c||c|c|c|c|c|c|c} x & -2 & \mathbf{-1} & 0 & 1 & 2 & 3 & 4 \\ \hline y & 30 & {\color{Red}{12} } & 8 & 9 & 18 & 35 & 60 \end{array} $$ состоит из значений полинома $ f(x)=4\,x^2-3\, x+ 8 $ за исключением единственного ошибочного занчения при $ x_2=-1 $. Последовательность ганкелевых полиномов $$ \mathcal H_{1}(x; \{ \tau \})\equiv \frac{1}{40}(x+1), \ \mathcal H_{2}(x; \{ \tau \})\equiv 0, \ \mathcal H_{3}(x; \{ \tau \})\equiv -\frac{2}{5}(x+1), \dots $$ и можно наблюдать, что ошибочный узел оказывается корнем двух ганкелевых полиномов: $ \mathcal H_{1}(x;\{\tau\}) $ и $ \mathcal H_{3}(x;\{\tau\}) $.

Теорема 3. Пусть полином $ f(x)=a_0x^n+\dots+a_n $ имеет степень $ n< N-2 $. Пусть таблица

$$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & y_1 & y_2 & \ldots & y_N \end{array} $$ удовлетворяет условиям

1. $ y_j=f(x_j) $ при $ j \in \{1,\dots, N\} \setminus \{ e \} $,

2. $ \widehat y_{e}:=f(x_{e}) \ne y_{e} $.

Тогда $$ \mathcal H_{1} (x) \equiv \frac{( y_{e} - \widehat y_{e})}{W^{\prime}(x_{e})} (x-x_{e}) \, . $$

Доказательство. Будем считать $ x_{e} = x_1 $ и положим $ \varepsilon := y_1 - \widehat y_1 $. Имеем: $$ \tau_{\ell}=\frac{x_1^{\ell}y_1}{W^{\prime}(x_1)}+\frac{x_2^{\ell}y_2}{W^{\prime}(x_2)}+\dots+\frac{x_N^{\ell}y_N}{W^{\prime}(x_N)}= $$ $$ =\left(\frac{x_1^{\ell}\widehat y_1}{W^{\prime}(x_1)}+ \frac{\varepsilon x_1^{\ell}}{W^{\prime}(x_1)}\right) +\frac{x_2^{\ell}y_2}{W^{\prime}(x_2)}+\dots+\frac{x_N^{\ell}y_N}{W^{\prime}(x_N)}= $$ $$ =\sum_{j=1}^N \frac{f(x_j)x_j^{\ell}}{W^{\prime}(x_j)}+\frac{\varepsilon x_1^{\ell}}{W^{\prime}(x_1)}= $$ и, на основании равенства Эйлера-Лагранжа: $$ =\frac{ \varepsilon x_1^{\ell}}{W^{\prime}(x_1)} \quad npu \quad \ell \in \{ 0 ,1\} \, . $$ Таким образом, $$ \mathcal H_{1} (x) \equiv \left|\begin{array}{cc} \tau_0 & \tau_1 \\ 1 & x \end{array} \right| \equiv \left|\begin{array}{cc} \varepsilon /W^{\prime}(x_1) & \varepsilon x_1 /W^{\prime}(x_1) \\ 1 & x \end{array} \right|=\frac{\varepsilon}{W^{\prime}(x_1)}(x-x_1) \, , $$ что и доказывает утверждение теоремы. ♦

Пример 3. Таблица

$$ \begin{array}{c||c|c|c|c|c|c|c} x & -2 & \mathbf{-1} & 0 & 1 & \mathbf{2} & 3 & 4 \\ \hline y & 30 & {\color{Red}{-7} } & 8 & 9 & {\color{Red}{11} } & 35 & 60 \end{array} $$ состоит из значений полинома $ f(x)=4\,x^2-3\, x+ 8 $ за исключением двух ошибочных значений в узлах $ x_2=-1 $ and $ x_5=2 $. Последовательность ганкелевых полиномов $$ \mathcal H_{1}(x; \{ \tau \})\equiv \frac{1}{80}(3\,x+38), \ \mathcal H_{2}(x; \{ \tau \} )\equiv -\frac{77}{320}(x+1)(x-2), \dots $$ в этот раз обнаруживает ошибочные узлы в корнях полинома $ \mathcal H_{2}(x; \{ \tau \}) $. ♦

Результат теоремы $ 3 $ обобщается на случай наличия $ E\ge 2 $ ошибок в таблице $ \{y_j=f(x_j)\}_{j=1}^N $ следующим образом.

Теорема 4. Пусть $ E \in \{2,3,\dots, \lfloor N/2 \rfloor-1 \} $ и $ e_1,\dots,e_E $ — различные числа из $ \{1,2,\dots, N\} $. Пусть $ f(x) $ имеет степень $ n< N-2E $. Пусть интерполяционная таблица

$$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & y_1 & y_2 & \ldots & y_N \end{array} $$ удовлетворяет условиям

1. $ y_j=f(x_j) $ при $ j \in \{1,\dots, N\} \setminus \{ e_1,\dots,e_E \} $,

2. $ \widehat y_{e_s}:=f(x_{e_s}) \ne y_{e_s} $ при $ s\in \{1,\dots, E \} $.

Тогда $$ \mathcal H_{E} (x;\{\tau\}) \equiv \frac{ \displaystyle \prod_{s=1}^E ( y_{e_s} - \widehat y_{e_s}) \prod_{1\le s < t \le E } ( x_{e_t} - x_{e_s})^2 }{\displaystyle \prod_{s=1}^E W^{\prime}(x_{e_s})} \prod_{s=1}^E (x-x_{e_s}) \, . $$

Доказательство ☞ ЗДЕСЬ.

При выполнении условий теоремы полином $ \mathcal H_{E} (x;\{\tau\}) $ имеет все свои корни принадлежащими множеству узлов $ \{x_j\}_{j=1}^N $ интерполяционной таблицы. Они соответствуют ошибочным значениям $ y $. В теории кодов, исправляющих ошибки (к которой излгаемый материал имеет непосредственное отношение), такое полином называется полиномом локаторов ошибок¹⁾.

Безнаказанно последовательно портить интерполяционную таблицу не получится.

Пример 4. Таблица

$$ \begin{array}{c||c|c|c|c|c|c|c} x & -2 & \mathbf{-1} & 0 & 1 & \mathbf{2} & \mathbf{3} & 4 \\ \hline y & 30 & {\color{Red}{-7} } & 8 & 9 & {\color{Red}{11} } & {\color{Red}{-1} } & 60 \end{array} $$ — всё та же злополучная, порожденная полиномом $ f(x)=4\,x^2-3\, x+ 8 $, но испорченная теперь уже в трёх узлах. Неповрежденных значений достаточно (даже избыточно!) для восстановления этого полинома. Тем не менее, последовательность $ \{\mathcal H_{k}(x; \{ \tau \}) \} $ уже не локализует ошибочные узлы. И это — принципиальный порог. Ту же самую таблицу можно посчитать полученной в результате порчи таблицы $$ \begin{array}{c||c|c|c|c|c|c|c} x & -2 & -1 & 0 & 1 & 2 & 3 & 4 \\ \hline y & -31 & -7 & 8 & 14 & 11 & -1 & -22 \end{array} $$ сгенерированной полиномом $ f_1(x)= -9/2 \, x^2+21/2\,x+8 $ и впоследствии испорченной в значениях $ f_1(-2), f_1(1) $ и $ f_1(4) $. ♦

После того как в таблице установлены узлы с ошибочными значениями $ y $, их можно выбросить из таблицы и восстановить полином $ f(x) $ по оставшимися верными значениям. Благо их все еще избыточно. Но для полноты картины, покажем еще один трюк.

Снова вернемся к последовательности $$ \widetilde \tau_k = \sum_{j=1}^{N} \frac{1}{y_j} \frac{x_j^{k}}{W^{\prime}(x_j)}, \quad \ k \in \{0,1,\dots \} $$ и порождемых ею ганкелевых полиномах $$ \mathcal H_1(x; \{\widetilde \tau\})=\left|\begin{array}{cc} \widetilde \tau_0 & \widetilde \tau_1 \\ 1 & x \end{array} \right| ,\mathcal H_2(x; \{ \widetilde \tau\}) = \left|\begin{array}{ccc} \widetilde \tau_0 & \widetilde \tau_1 & \widetilde \tau_2 \\ \widetilde \tau_1 & \widetilde \tau_2 & \tau_3 \\ 1 & x & x^2 \end{array} \right|, \dots $$ В теореме $ 2 $ утверждается, что полином $ \mathcal H_N(x; \{\widetilde \tau\}) $ фактически (с точностью до числового множителя) совпадает с традиционным интерполяционным полиномом, построенным по таблице $$ \begin{array}{c||c|c|c|c} x & x_1 & x_2 & \ldots & x_N \\ \hline y & y_1 & y_2 & \ldots & y_N \end{array} $$ Снова предположим, что таблица изначально была составлена из значений полинома $ f(x) $ степени $ n<N-2 $, но впоследствии некоторые значения $ y $ были искажены. В этом случае отношение полинома $ \mathcal H_N(x; \{ \widetilde \tau\}) $ к исходному полиному $ f(x) $ не очевидно. Посмотрим на структуру остальных ганкелевых полиномов.

Пример 5. Если попробовать факторизовать ганкелевы полиномы, полученные в ходе решения примера $ 1 $, т.е. построенные для таблицы значений

$$ \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} $$ то полином $ \mathcal H_4(x;\{\widetilde \tau\}) $ оказывается приводимым над $ \mathbb Z $: $$ \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) $ во всех остальных узлах интерполяции совпадают с табличными! (Эту же таблицу мы рассматривали в примере $ 3 $, и там обоснованием приведенного ответа было «можно проверить подстановкой»). ♦

Итак, в некотором полиноме $ \mathcal H_k(x; \{\widetilde \tau\}) $ заложена информация и о полиноме локаторов ошибок и об исходном полиноме $ f(x) $, по которому строилась таблица.

Статья не закончена!

[1]. Uteshev A.Yu., Baravy I. Solution of Interpolation Problems via the Hankel Polynomial Construction. 2016. arXiv:1603.08752

[2]. Uteshev A.Yu., Marov A. Faulty share detection in Shamir's secret sharing. Вестн. С.-Петербург. ун-та. Сер. 10. Прикл. матем. Информ. Проц. упр., 15:2 (2019), 274–282. Текст ☞ ЗДЕСЬ (pdf).

[3]. Welch L.R., Berlekamp E.R. Error correction for algebraic block codes. US Patent No $ 4\,633\,47 $, Dec. 30, 1986