Схема Эйткена

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

Определение

Обозначим через $P_{i,\dots ,j}(x)$ многочлен Лагранжа, полученный интерполяцией базовых точек $(x_i,y_i),(x_{i+1},y_{i+1}),\dots ,(x_j,y_j)$. Тогда верно следующее соотношение

$P_i(x)=y_i$ (вырожденный случай, многочлен нулевой степени — константа)

$P_{i,\dots ,j}(x)=\frac{1}{x_j-x_i}\left|\begin{array}{cc}x-x_i& P_{i,\dots ,j-1}(x)\\ x-x_j& P_{i+1,\dots ,j}(x)\end{array}\right|$

Доказательство

Доказательство легко произвести по индукции. Не ограничивая общности, для удобства примем $i=0$, $j=n$.

Пусть $P_{0,\dots ,n-1}(x)$ и $P_{1,\dots ,n}(x)$ — многочлены Лагранжа для соответствующих наборов точек. Это значит, что $P_{0,\dots ,n-1}(x)=\sum _{i=0}^{n-1}{y}_i\prod _{j=0;j=i}^{n-1}\frac{x-x_j}{x_i-x_j}$ и $P_{1,\dots ,n}(x)=\sum _{i=1}^n{y}_i\prod _{j=1;j=i}^n\frac{x-x_j}{x_i-x_j}$

Если обозначить $A_i=\prod _{j=0;j=i}^n(x-x_j)$; $T_i=y_i\prod _{j=0;j=i}^n\frac{x-x_j}{x_i-x_j}$ и $X_i=\prod _{j=1;j=i}^{n-1}(x_i-x_j)$, то очевидно, что

$\frac{1}{x_n-x_0}\left|\begin{array}{cc}x-x_0& P_{0,\dots ,n-1}(x)\\ x-x_n& P_{1,\dots ,n}(x)\end{array}\right|=T_0+T_n+\sum _{i=1}^{n-1}{y}_i\left(\frac{A_i}{X_i(x_i-x_n)(x_n-x_0)}-\frac{A_i}{X_i(x_i-x_0)(x_n-x_0)}\right)=$

$=T_0+T_n+\sum _{i=1}^{n-1}{y}_i\frac{A_i{x}_n-A_i{x}_0}{X_i(x_i-x_n)(x_i-x_0)(x_n-x_0)}=T_0+T_n+\sum _{i=1}^{n-1}{y}_i\frac{A_i}{X_i(x_i-x_n)(x_i-x_0)}=\sum _{i=0}^n{T}_i$,

что совпадает с многочленом Лагранжа.

Производительность

Время вычисления

При известных коэффициентах многочленов $P_{0,\dots ,n-1}(x)$ и $P_{1,\dots ,n}(x)$ вычисление многочлена $P_{0,\dots ,n}(x)$ возможно за линейное время непосредственно по формуле.

Однако, если рассматривать применение схемы Эйткена при добавлении новой точки $(x_n,y_n)$ в набор базовых точек, то в этом случае $P_{1,\dots ,n}(x)$ также будет неизвестным и его надо будет вычислить за линейное время на основе $P_{1,\dots ,n-1}(x)$ и $P_{2,\dots ,n}(x)$. Для этого надо будет предварительно вычислить $P_{2,\dots ,n}(x)$, и так далее.

Таким образом, добавление точки возможно только за квадратичное время путём последовательного получения полиномов $P_{n-1,n}(x),P_{n-2,n-1,n}(x),\dots ,P_{2,\dots ,n}(x),P_{1,\dots ,n}(x)$. Если при этом в программе уже будут храниться $P_{1,\dots ,n-1}(x),P_{2,\dots ,n-1}(x),\dots ,P_{n-2,n-1}(x),P_{n-1}(x)$, то вычисление каждого из требуемых полиномов осуществимо за линейное относительно количества точек-параметров время. Это даёт в сумме асимптотически $O(n^2)$ времени для добавления новой точки и, соответственно, $O(n^3)$ для вычисления полинома Лагранжа по заранее заданному набору из $n$ точек.

Расходы памяти

Если использовать оптимальный по времени способ вычисления, то необходимым является хранение многочленов вида $P_{i,\dots ,n}(x)(i=0,\dots ,n)$. $i$-й из этих многочленов требует $O(n-i)$ памяти для хранения коэффициентов, что требует в сумме $O(n^2)$ памяти.

Следует заметить, что объём памяти $O(n^2)$ необходим, даже если нет расчёта на последующее добавление точек — хранение многочленов $P_{i,\dots ,n}(x)$ неизбежно по ходу расчёта самого многочлена.

См. также

• Интерполяционный многочлен Лагранжа
• Интерполяция