2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки





Начать новую тему Ответить на тему
 
 Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 12:49 
Аватара пользователя


15/04/17
15
Добрый день. Наткнулся на интересную задачку из вступительных в ШАД, вроде 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)$. Так же была идея притянуть многочлен Тейлора...но тут непонятно как вычислять значения производных. Понятно, что точки специфичные и надо использовать именно это, не находя самого многочлена. Может нужно использовать память.

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

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 13:00 
Заслуженный участник
Аватара пользователя


06/10/08
5697
M1ham в сообщении #1209623 писал(а):
Ясно, что интерполяционные вещи типа формулы Лагранжа с последующим вычислением многочлена в точках $n+1,\ldots, 2n$ отпадают, так как сложность будет $O(n^3)$.
Почему? Коэффициенты интерполирующего многочлена вычисляются за $O(n^2)$ (напр. с помощью конечных разностей), дальше $n$ значений вычисляются тоже за $O(n^2)$.
Здесь можно еще проще - просто продолжить ряд конечных разностей с учетом того, что $\Delta^n P = \operatorname{const}$.

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 14:59 
Аватара пользователя


15/04/17
15
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$?

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 15:12 
Заслуженный участник
Аватара пользователя


01/08/06
2114
Уфа
Что-то сложное у вас.
Проще надо.
Выписываем разности $\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$ ячеек памяти для записи разностей. И столько же операций, чтобы их вычислить.

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 15:27 
Аватара пользователя


15/04/17
15
worm2 в сообщении #1209663 писал(а):
В самом верхнем ряду получается искомая последовательность.


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

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 15:29 
Заслуженный участник
Аватара пользователя


06/10/08
5697
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}$.

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 17:15 
Заслуженный участник
Аватара пользователя


01/08/06
2114
Уфа
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
Проверяйте.

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение15.04.2017, 23:51 
Аватара пользователя


15/04/17
15
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
Первая строчка: :D
3 1 4 1 -19 -67 -154 -291
Проверяйте.


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

-- 16.04.2017, 00:52 --

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


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

 Профиль  
                  
 
 Re: Вычисление многочлена в последовательных точках. ШАД 2014
Сообщение18.04.2017, 13:18 
Заслуженный участник
Аватара пользователя


11/03/08
5295
Москва

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Модераторы: Toucan, maxal, Karan, PAV, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group