Русская Википедия:Схема Эйткена
Схема Эйткена — итерационный способ вычисления интерполяционного многочлена Лагранжа, позволяющий за квадратичное относительно количества узлов интерполяции время внедрять в многочлен информацию о новых точках.
Определение
Обозначим через <math>P_{i,\dots,j}(x)</math> многочлен Лагранжа, полученный интерполяцией базовых точек <math>(x_i,y_i), (x_{i+1},y_{i+1}), \dots, (x_j,y_j)</math>. Тогда верно следующее соотношение
<math>P_{i}(x) = y_{i}</math> (вырожденный случай, многочлен нулевой степени — константа)
<math>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}</math>
Доказательство
Доказательство легко произвести по индукции. Не ограничивая общности, для удобства примем <math>i=0</math>, <math>j=n</math>.
Пусть <math>P_{0,\dots,n-1}(x)</math> и <math>P_{1,\dots,n}(x)</math> — многочлены Лагранжа для соответствующих наборов точек. Это значит, что <math>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}}}</math> и <math>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}}}</math>
Если обозначить <math>A_{i} = \prod \limits_{j=0 ; j \not = i}^{n} {(x-x_{j})}</math>; <math>T_i = y_i \prod \limits_{j=0 ; j \not = i}^{n} {\frac{x-x_j}{x_i-x_j}}</math> и <math>X_i = \prod \limits_{j=1 ; j \not = i}^{n-1} {(x_{i}-x_{j})}</math>, то очевидно, что
<math>\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)} =</math>
<math>= 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} </math>,
что совпадает с многочленом Лагранжа.
Производительность
Время вычисления
При известных коэффициентах многочленов <math>P_{0,\dots,n-1}(x)</math> и <math>P_{1,\dots,n}(x)</math> вычисление многочлена <math>P_{0,\dots,n}(x)</math> возможно за линейное время непосредственно по формуле.
Однако, если рассматривать применение схемы Эйткена при добавлении новой точки <math>(x_n,y_n)</math> в набор базовых точек, то в этом случае <math>P_{1,\dots,n}(x)</math> также будет неизвестным и его надо будет вычислить за линейное время на основе <math>P_{1,\dots,n-1}(x)</math> и <math>P_{2,\dots,n}(x)</math>. Для этого надо будет предварительно вычислить <math>P_{2,\dots,n}(x)</math>, и так далее.
Таким образом, добавление точки возможно только за квадратичное время путём последовательного получения полиномов <math>P_{n-1,n}(x), P_{n-2,n-1,n}(x), \dots, P_{2,\dots,n}(x), P_{1,\dots,n}(x)</math>. Если при этом в программе уже будут храниться <math>P_{1,\dots,n-1}(x), P_{2,\dots,n-1}(x), \dots, P_{n-2,n-1}(x), P_{n-1}(x)</math>, то вычисление каждого из требуемых полиномов осуществимо за линейное относительно количества точек-параметров время. Это даёт в сумме асимптотически <math>O(n^2)</math> времени для добавления новой точки и, соответственно, <math>O(n^3)</math> для вычисления полинома Лагранжа по заранее заданному набору из <math>n</math> точек.
Расходы памяти
Если использовать оптимальный по времени способ вычисления, то необходимым является хранение многочленов вида <math>P_{i,\dots,n}(x) (i=0,\dots,n)</math>. <math>i</math>-й из этих многочленов требует <math>O(n-i)</math> памяти для хранения коэффициентов, что требует в сумме <math>O(n^2)</math> памяти.
Следует заметить, что объём памяти <math>O(n^2)</math> необходим, даже если нет расчёта на последующее добавление точек — хранение многочленов <math>P_{i,\dots,n}(x)</math> неизбежно по ходу расчёта самого многочлена.
См. также
