Найти коэффиценты полинома.

[veg_nw]

Есть функция $p(x)$. Известно что она является полиномом. Нужно найти n-й коэффициент этого полинома.
Есть конечно метод Лагранжа но этот метод достаточно неэффективен. Есть ли более эффективный метод?

[ИСН]

Я нашёл, он равен 5.
Или всё-таки уточните, какую информацию мы имеем о функции?

-- менее минуты назад --

Впрочем, я догадался. У нас есть чёрный ящик, который выдаёт значение функции в любой точке, но как это делает - не говорит. Ну-с, тогда свободный член - это значение в нуле, а остальные там как-то через навороченные разности. Не знаю, что такое метод Лагранжа; возможно, это он и есть. А как иначе-то?

[veg_nw]

Совершенно верно мы имеем дело с черным ящиком. А про методы я нашел некоторые
http://math.stackexchange.com/questions/134212/determine-the-coefficients-of-an-unknown-black-box-polynomial
Но мне необходим эффективный метод.
Про метод Лагранжа:
https://ru.wikipedia.org/wiki/%D0%98%D0%BD%D1%82%D0%B5%D1%80%D0%BF%D0%BE%D0%BB%D1%8F%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D1%8B%D0%B9_%D0%BC%D0%BD%D0%BE%D0%B3%D0%BE%D1%87%D0%BB%D0%B5%D0%BD_%D0%9B%D0%B0%D0%B3%D1%80%D0%B0%D0%BD%D0%B6%D0%B0

[Pphantom]

Так все-таки: какими данными о функции Вы располагаете?

[veg_nw]

У меня есть значение функции в любой точке.
Многие методы не работают потому что порядок полинома очень высок.

[Sonic86]

С помощью трех телепатов, четырех экстрасенсов и двух Ванг мне открылось следующее:
Имеется устройство, которому можно подать на вход $x$, а устройство возвращает $p(x)$, где $p$ - полином. Подавать на вход можно разные иксы сколь угодно много раз. Надо определить $n$-й коэффициент полинома. Задача состоит в том, что число иксов следует минимизировать. Очевидно, что достаточно $n+1$ икса. Кто может меньше? А никто.
Тоже мне, проблема...

4-й экстрасенс мне намекал, что ТС знает еще какие-то условия на полином, но не говорит их. Но кто знает, наверное, он врет...

[veg_nw]

Совершенно верно:)
Но когда порядок полинома намного больше чем номер N коэффицента который нужно найти. То количество иксов растет очень быстро. А я бы хотел иметь N операций.

[Sonic86]

veg_nw в сообщении #910885 писал(а):

Но когда порядок полинома намного больше чем номер N коэффицента который нужно найти.

Error 84653: incorrect syntax construction
Наверное, Вы хотели сказать "Но у меня порядок полинома намного больше чем номер N коэффицента который нужно найти."

veg_nw в сообщении #910885 писал(а):

А я бы хотел иметь N операций.

ничего себе, все хотят.

Каких операций? ! Поставить задачу нормально слабо?

Если Вы потребуете находить коэффициент не точно, а с погрешностью, то можно юзать замену производных на конечные разности (вот сидите и думайте, что я Вам хотел сказать. Почему только я должен страдать-то?)

[main.c]

veg_nw в сообщении #910885 писал(а):

Совершенно верно:)
Но когда порядок полинома намного больше чем номер N коэффицента который нужно найти. То количество иксов растет очень быстро. А я бы хотел иметь N операций.

Ну не так уж это и быстро, линейная сложность для алгоритма - это просто замечательно!

[ИСН]

veg_nw в сообщении #910885 писал(а):

порядок полинома намного больше чем номер N коэффицента который нужно найти

Номер сверху или снизу?

[veg_nw]

Цитата:

Если Вы потребуете находить коэффициент не точно, а с погрешностью, то можно юзать замену производных на конечные разности

Да мне нужно найти не точные коэффиценты а коэффиценты с некоторым приближением. Есть ли известные методы?

-- 23.09.2014, 13:46 --

ИСН в сообщении #910897 писал(а):

veg_nw в сообщении #910885 писал(а):

порядок полинома намного больше чем номер N коэффицента который нужно найти

Номер сверху или снизу?

С низу. Например для полинома
$6x^{24}+4x^{26}+4x-15x^{8}-24x^{9}-22x^{10}-16x^{11}+2x^{12}+16x^{13}+28x^{14}+(80/3)x^{15}+4x^{5}+6x^{2}-8x^{7}-4x^{23}-(40/3)x^{21}+18x^{16}+4x^{17}-6x^{18}-16x^{19}-11x^{20}+x^{28}+(16/3)x^{3}+7x^{4}+(10/3)x^{6}$

Нужно найти 4-й коэффицент.

[Sonic86]

veg_nw в сообщении #910901 писал(а):

Да мне нужно найти не точные коэффиценты а коэффиценты с некоторым приближением. Есть ли известные методы?

Пусть $p(x)$ - многочлен.
Чему равно $p^{(k)}(0)$?
Как вычислить приближенно 1-ю производную? $k$-ю производную?

main.c в сообщении #910890 писал(а):

Ну не так уж это и быстро, линейная сложность для алгоритма - это просто замечательно!

Ага, при текущем описании - не факт. Например, если многочлен вычисляется у ТС на компе, то скорость расчета многочлена тоже надо учитывать, а она $O(n^2)$ без специальных извращений.

[veg_nw]

Sonic86 в сообщении #910907 писал(а):

Пусть $p(x)$ - многочлен.
Чему равно $p^{(k)}(0)$?
Как вычислить приближенно 1-ю производную? $k$-ю производную?

Конечно можно воспользоваться методом конечных разностей. Но коэффициенты растут быстро и расчеты приходится проводить с нереально высокой точностю.
А есть ли комплексные методы ? Я все больше склоняюсь к FFT.

[Sonic86]

veg_nw в сообщении #910911 писал(а):

Но коэффициенты растут быстро

Sonic86 в сообщении #910883 писал(а):

4-й экстрасенс мне намекал, что ТС знает еще какие-то условия на полином, но не говорит их.

Ладно, я пошел. Дождусь, когда 3 страницы будет, чтобы условие задачи все-таки появилось полностью в точном виде.

[sithif]

veg_nw, попробуйте AD, там нет проблем с точностью конечных разностей.