2014 dxdy logo

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

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




 
 Как упростить произведение многочленов?
Сообщение29.03.2009, 21:45 
Пусть
$$
Q_n(z)=1+z+z^2+\ldots+z^{n-1}=\frac{1-z^n}{1-z}.
$$

Рассмотрим произведение
$$
P_{n,k}(z)=Q_n(z) Q_n(z^2) Q_n(z^3)\cdots Q_n(z^k).
$$
Нужно найти или явное выражение для многочлена $P_{n,k}(z)$, или рекурентную формулу или хотя бы сильно упростить чтобы можно было его вычислять при достаточно больших $n$ и $k.$

 
 
 
 
Сообщение29.03.2009, 22:26 
Аватара пользователя
Пусть $p(n,k,m)$ - это коэффициент при $z^m$ в $P_{n,k}(z)$.
Тогда $p(n,0,m) = \delta_{0m}$ и для $k>0$
$$p(n,k,m) = \sum_{j=0}^{\min\{n-1,\lfloor m/k\rfloor\}} p(n,k-1,m-jk).$$

Добавлено спустя 12 минут 38 секунд:

Что же касается самого многочлена $P_{n,k}(z)$, то его можно записать в виде отношения q-символов Похгаммера:
$$P_{n,k}(z) = \lim_{a\to 1} \frac{(a;z^n)_{k+1}}{(a;z)_{k+1}}$$

 
 
 
 
Сообщение30.03.2009, 08:28 
maxal писал(а):
Пусть $p(n,k,m)$ - это коэффициент при $z^m$ в $P_{n,k}(z)$.
Тогда $p(n,0,m) = \delta_{0m}$ и для $k>0$
$$p(n,k,m) = \sum_{j=0}^{\min\{n-1,\lfloor m/k\rfloor\}} p(n,k-1,m-jk).$$

Добавлено спустя 12 минут 38 секунд:

Что же касается самого многочлена $P_{n,k}(z)$, то его можно записать в виде отношения q-символов Похгаммера:
$$P_{n,k}(z) = \lim_{a\to 1} \frac{(a;z^n)_{k+1}}{(a;z)_{k+1}}$$


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

 
 
 
 Re: Как упростить произведение многочленов?
Сообщение30.03.2009, 10:35 
А что если определить все корни $P_{n,k}(z)$ и для нахождения коэффициентов использовать формулы Виета?

 
 
 
 Re: Как упростить произведение многочленов?
Сообщение30.03.2009, 10:41 
Аватара пользователя
Dandan писал(а):
А что если определить все корни $P_{n,k}(z)$ и для нахождения коэффициентов использовать формулы Виета?


Кстати, тоже об этом думал. Там корни довольно легко находятся.

Но при больших $n$ и $k$ вычисления будут идти чересчур долго. Явно не быстрее, чем через простое перемножение многочленов.

Мне вот, кстати, интересно, что автору в конечном счёте требуется. Выписывать сам многочлен $P_{n,k}$ или быстро находить его значения при заданных значениях переменной.

 
 
 
 Re: Как упростить произведение многочленов?
Сообщение30.03.2009, 17:44 
Профессор Снэйп писал(а):

Мне вот, кстати, интересно, что автору в конечном счёте требуется. Выписывать сам многочлен $P_{n,k}$ или быстро находить его значения при заданных значениях переменной.


Автору нужно совсем другое. Пусть имеется многочлен
$$
P_{n,k}(z)=\sum a_i z^i.
$$
Требуется как-то эфективно вычислить "подмногочлен"
$$
\sum a_{ni} z^{ni}.
$$
Один из способов есть - нужно найти
$$
\frac{1}{n}\sum_i P_{n,k}(z\,\zeta^i),
$$
$\zeta$ -- первообразный корень степени $n.$

Но при больших $n$ $(n>30)$ это уже не так просто-много умножений, поэтому надеюсь, что можно найти явную формулу для коэфициентов$a_{ni}.$

Добавлено спустя 5 минут 4 секунды:

Dandan писал(а):
А что если определить все корни $P_{n,k}(z)$ и для нахождения коэффициентов использовать формулы Виета?


нужно подумать

 
 
 [ Сообщений: 6 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group