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


Вспомогательная страница к разделу ☞ ИНТЕРПОЛЯЦИЯ


?

Придумать упрощение схемы вычисления интерполяционного полинома для таблицы с набором узлов симметричным относительно 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?


2012/01/27 22:08 редактировал au