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

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

Определение править

Обозначим через $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}}}{\begin{vmatrix}x-x_{i}&P_{i,\dots ,j-1}(x)\\x-x_{j}&P_{i+1,\dots ,j}(x)\end{vmatrix}}$

Доказательство править

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

Пусть $P_{0,\dots ,n-1}(x)$ и $P_{1,\dots ,n}(x)$ — многочлены Лагранжа для соответствующих наборов точек. Это значит, что $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}}}}$ и $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}}}}$

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

${\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)}=$

$=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}}$ ,

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

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

Время вычисления править

При известных коэффициентах многочленов $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)$ неизбежно по ходу расчёта самого многочлена.