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

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

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

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

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

Доказательство легко произвести по индукции. Не ограничивая общности, для удобства примем $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}} | \begin{matrix} x - x_{0} & P_{0, \dots, n - 1} (x) \\ x - x_{n} & P_{1, \dots, n} (x) \end{matrix} | = T_{0} + T_{n} + \sum_{i = 1}^{n - 1} y_{i} (\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})}) =$

$= 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)$ неизбежно по ходу расчёта самого многочлена.

См. также[править]