Основное
Вспомогательная страница к разделу ☞ ИНТЕРПОЛЯЦИЯ
Придумать упрощение схемы вычисления интерполяционного полинома для таблицы с набором узлов симметричным относительно $ 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} $$
Решение. Теорема о существовании интерполяционного полинома гарантирует, что существует полином $ 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 $?