Interested Article - Схема Эйткена

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

Определение

Обозначим через многочлен Лагранжа, полученный интерполяцией базовых точек . Тогда верно следующее соотношение

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

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

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

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

Если обозначить ; и , то очевидно, что

,

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

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

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

При известных коэффициентах многочленов и вычисление многочлена возможно за линейное время непосредственно по формуле.

Однако, если рассматривать применение схемы Эйткена при добавлении новой точки в набор базовых точек, то в этом случае также будет неизвестным и его надо будет вычислить за линейное время на основе и . Для этого надо будет предварительно вычислить , и так далее.

Таким образом, добавление точки возможно только за квадратичное время путём последовательного получения полиномов . Если при этом в программе уже будут храниться , то вычисление каждого из требуемых полиномов осуществимо за линейное относительно количества точек-параметров время. Это даёт в сумме асимптотически времени для добавления новой точки и, соответственно, для вычисления полинома Лагранжа по заранее заданному набору из точек.

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

Если использовать оптимальный по времени способ вычисления, то необходимым является хранение многочленов вида . -й из этих многочленов требует памяти для хранения коэффициентов, что требует в сумме памяти.

Следует заметить, что объём памяти необходим, даже если нет расчёта на последующее добавление точек — хранение многочленов неизбежно по ходу расчёта самого многочлена.

См. также

Источник —

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