!!§!! Вспомогательная страница к разделу
☞
((:interpolation ИНТЕРПОЛЯЦИЯ))
----
!!?!! Придумать упрощение схемы вычисления интерполяционного полинома для таблицы
с набором узлов симметричным относительно $ 0_{} $:
$$
\begin{array}{c|cccccccc}
x & -x_n & -x_{n-1} & \dots & -x_1 & x_1 & \dots & x_{n-1} & x_n \\
\hline
y & y_{-n} & y_{-(n-1)} &\dots & y_{-1} & y_1 & \dots & y_{n-1} & y_n
\end{array}
$$
**Решение.** Теорема ((:interpolation о существовании интерполяционного полинома)) гарантирует, что существует полином $ f_{}(x) $ степени $ \le 2n-1 $, принимающий значения по данной таблице. Разобьем этот полином на сумму четных и нечетных одночленов: если
$$ f(x) = a_0+a_1x+a_2x^2+\dots+a_{2n-1}x^{2n-1} \ , $$
то
$$ f(x)\equiv F_1(x^2)+xF_2(x^2) \equiv F_1(X)+xF_2(X) \quad npu \quad X=x^2 $$
и
$$F_1(X)=a_0+a_2X+\dots+a_{2n-2}X^{n-1},\quad F_2(X)=a_1+a_3X+\dots+a_{2n-1}X^{n-1} \ . $$
Подстановка в $ f_{}(x) $ узлов $ x_{j} $ и $ - x_{j} $ дает систему уравнений
$$
\left\{
\begin{array}{ccc}
y_j&=&F_1(X_j)+x_jF_2(X_j) \\
y_{-j}&=&F_1(X_j)-x_jF_2(X_j)
\end{array}
\right. \quad , \ X_j=x_j^2
$$
относительно чисел $ F_1(X_j) $ и $ F_2(X_j) $. Разрешив эту систему, получим сведение исходной интерполяционной задачи к двум аналогичным, но с двукратным уменьшением числа узлов интерполяции:
$$
F_1(X): \quad
\begin{array}{c|cccc}
X & x_1^2 & x_{2}^2 & \dots & x_n^2 \\
\hline
y & (y_1+y_{-1})/2 & (y_2+y_{-2})/2 &\dots & (y_n+y_{-n})/2
\end{array} \quad ;
$$
$$
F_2(X): \quad
\begin{array}{c|cccc}
X & x_1^2 & x_{2}^2 & \dots & x_n^2 \\
\hline
y & (y_1-y_{-1})/(2x_1) & (y_2-y_{-2})/(2x_2) &\dots & (y_n-y_{-n})/(2x_n)
\end{array}
$$
Иными словами, симметрия системы узлов относительно $ 0_{} $ позволяет разбить задачу на независимые подзадачи: отдельно --- для четной составляющей интерполяционного полинома и отдельно --- для нечетной. Нужно только сформировать новые интерполяционные таблицы.
♦
!!?!! Можно ли распространить эту схему и дальше --- скажем, для системы равноотстоящих узлов в количестве $ n= 2^m $?