Вычисление многочлена в последовательных точках. ШАД 2014

[M1ham]

Добрый день. Наткнулся на интересную задачку из вступительных в ШАД, вроде 2014 года.
По известным значениям $P(0),P(1),\ldots, P(n)$ неизвестного многочлена $P$ степени $n$ (по всей видимости над полем действительных чисел)
найти значения $P(n+1), P(n+2),\ldots, P(2n)$. Ограничение по времени $O(n^2)$.

Ясно, что интерполяционные вещи типа формулы Лагранжа с последующим вычислением многочлена в точках $n+1,\ldots, 2n$ отпадают, так как сложность будет $O(n^3)$. Так же была идея притянуть многочлен Тейлора...но тут непонятно как вычислять значения производных. Понятно, что точки специфичные и надо использовать именно это, не находя самого многочлена. Может нужно использовать память.

В общем на мой взгляд интересная и красивая задачка...

[Xaositect]

M1ham в сообщении #1209623 писал(а):

Ясно, что интерполяционные вещи типа формулы Лагранжа с последующим вычислением многочлена в точках $n+1,\ldots, 2n$ отпадают, так как сложность будет $O(n^3)$.

Почему? Коэффициенты интерполирующего многочлена вычисляются за $O(n^2)$ (напр. с помощью конечных разностей), дальше $n$ значений вычисляются тоже за $O(n^2)$.
Здесь можно еще проще - просто продолжить ряд конечных разностей с учетом того, что $\Delta^n P = \operatorname{const}$.

[M1ham]

Xaositect в сообщении #1209623 писал(а):

дальше $n$ значений вычисляются тоже за $O(n^2)$.

Спасибо. У меня остался еще вопрос.
Если мы представляем многочлен в виде

$$ P(x)=\sum\limits_{j=0}^{n}\frac{\Delta^jP(0)}{j!}x^{(j)}, $$

где $x^{(j)}$ это факториальная степень, то как затем вычислять за $O(n)$ значение в одной точке. Вроде для Горнера нужен многочлен расписанный по степеням $x$?

[worm2]

Что-то сложное у вас.
Проще надо.
Выписываем разности $\Delta^1_0=P(1)-P(0)$, $\Delta^1_1=P(2)-P(1)$, ...
Затем под ними разности разностей $\Delta^2_0=\Delta^1_1-\Delta^1_0$, $\Delta^2_1=\Delta^1_2-\Delta^1_1$, ...
И так $n$ раз, когда должны получиться константы (хотя константа будет всего одна).
Затем продлеваем эту константу ещё $n$ раз в своём ряду.
На ряд выше продлеваем последовательность $\Delta^{n-1}$, исходя из выписанных ниже разностей (поскольку в самом нижнем ряду константа, у нас получится арифметическая прогрессия).
Ещё на ряд выше продлеваем последовательность $\Delta^{n-2}$, исходя из выписанных ниже разностей.
И т.д.
В самом верхнем ряду получается искомая последовательность. Нам понадобится где-то около $1.5n^2$ ячеек памяти для записи разностей. И столько же операций, чтобы их вычислить.

[M1ham]

worm2 в сообщении #1209663 писал(а):

В самом верхнем ряду получается искомая последовательность.

Спасибо. Может я что-то не понял. Но в верхнем ряду уже $n$ разностей куда его продолжать?
Или я что-то не понял?

[Xaositect]

M1ham в сообщении #1209660 писал(а):

Вроде для Горнера нужен многочлен расписанный по степеням $x$?

Строго говоря да, но здесь можно действовать совершенно аналогично Горнеру: $\sum a_k x^{\underline{k}} = a_0 + a_1(x + a_2((x-1) + a_3((x - 2) + \dots + a_n(x - n + 1)\dots)))$

Да и вообще, для вычисления за $O(n)$ Горнер не нужен. Можно за $O(n)$ вычислить последовательно $x^{\underline{2}}, x^{\underline{3}}, \dots, x^{\underline{n}}$, а потом из них вычислить многочлен, тоже за $O(n)$. Горнер - это уже оптимизация константы.

worm2 в сообщении #1209663 писал(а):

Что-то сложное у вас.
Проще надо.

Да, это я и имел в виду под

Xaositect в сообщении #1209624 писал(а):

Здесь можно еще проще - просто продолжить ряд конечных разностей с учетом того, что $\Delta^n P = \operatorname{const}$.

[worm2]

M1ham в сообщении #1209666 писал(а):

Или я что-то не понял?

Допустим, у нас $P(0)=3$, $P(1)=1$, $P(2)=4$, $P(3)=1$,
3   1   4   1
 -2   3  -3
    5  -6
    -11

Продолжаем последнюю строчку:
-11 -11 -11 -11 -11
Третья строчка:
5 -6 -17 -28 -39 -50
Вторая строчка:
-2 3 -3 -20 -48 -87 -137
Первая строчка:
3 1 4 1 -19 -67 -154 -291
Проверяйте.

[M1ham]

worm2 в сообщении #1209684 писал(а):

M1ham в сообщении #1209666 писал(а):

Или я что-то не понял?

Допустим, у нас $P(0)=3$, $P(1)=1$, $P(2)=4$, $P(3)=1$,
3   1   4   1
 -2   3  -3
    5  -6
    -11

Продолжаем последнюю строчку:
-11 -11 -11 -11 -11
Третья строчка:
5 -6 -17 -28 -39 -50
Вторая строчка:
-2 3 -3 -20 -48 -87 -137
Первая строчка:
3 1 4 1 -19 -67 -154 -291
Проверяйте.

Огромное Вам спасибо. Вычисления я не проверял, но идею понял и осознал.

-- 16.04.2017, 00:52 --

Xaositect в сообщении #1209668 писал(а):

Строго говоря да, но здесь можно действовать совершенно аналогично Горнеру: a_0 + a_1(x + a_2((x-1) + a_3((x - 2)

Действительно, что-то я протупил Спасибо.

[Евгений Машеров]

(Оффтоп)

Задачу предложил лично Бэббедж? Потому как "дифференциальная машина" его разрабатывалась именно для этой задачи...