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

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

Определение

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

${\displaystyle P_{i}(x)=y_{i}}$ (вырожденный случай, многочлен нулевой степени — константа)

${\displaystyle P_{i,\dots ,j}(x)={\frac {1}{x_{j}-x_{i}}}{\begin{vmatrix}x-x_{i}&P_{i,\dots ,j-1}(x)\\x-x_{j}&P_{i+1,\dots ,j}(x)\end{vmatrix}}}$

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

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

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

Если обозначить ${\displaystyle A_{i}=\prod \limits _{j=0;j\not =i}^{n}{(x-x_{j})}}$; ${\displaystyle T_{i}=y_{i}\prod \limits _{j=0;j\not =i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}}$ и ${\displaystyle X_{i}=\prod \limits _{j=1;j\not =i}^{n-1}{(x_{i}-x_{j})}}$, то очевидно, что

${\displaystyle {\frac {1}{x_{n}-x_{0}}}{\begin{vmatrix}x-x_{0}&P_{0,\dots ,n-1}(x)\\x-x_{n}&P_{1,\dots ,n}(x)\end{vmatrix}}=T_{0}+T_{n}+\sum \limits _{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)}=}$

${\displaystyle =T_{0}+T_{n}+\sum \limits _{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 \limits _{i=1}^{n-1}{y_{i}{\frac {A_{i}}{X_{i}(x_{i}-x_{n})(x_{i}-x_{0})}}}=\sum \limits _{i=0}^{n}{T_{i}}}$,

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

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

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

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

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

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

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

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

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

См. также

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