Эффективное вычисление коэффициентов полинома от его корней

Question

у меня есть корни унитарным полинома, т.е.

p(x) = (x-x_1)*...*(x-x_n) 

и мне нужны коэффициенты a_n, ..., a_0 от

p(x) = x^n + a_{n-1}x^{n-1} + ... + a_0. 

кого-ли знать вычислительно эффективным способом сделать это? Если кто-то знает реализацию C/C++, это будет на самом деле лучше. (Я уже посмотрел на GSL, но он не обеспечил функции.)

Конечно, я знаю, как к нему математически. Я знаю, что коэффициент a_i является суммой всех продуктов подмножеств с элементами n-i. Но если бы я сделал это немой путь, это означает, что для перебора всех подмножеств, я должен был бы

sum^{n-1}_{k=1} (k choose n) * (k-1) 

умножений и

sum^n_{k=0} (k choose n) - n 

дополнения. Следовательно, оба термина растут с O(n!), что является слишком большим вычислением, чтобы преобразовать список n root в список коэффициентов n. Я считаю, что должен быть разумный способ повторного использования большинства промежуточных результатов, но я его не нахожу.

Answer 1

Вы можете сделать это в O(n^2) очень легко, если вы постепенно создаете свой многочлен. Давайте определим:

p_k(x) = (x-x_1)*...*(x-x_k) 

Это p_k(x) является умножение первого k(x-x_i) из p(x). Мы имеем:

p_1(x) = x-x_1 

Другими словами, массив коэффициентов (a) будет (индексы начинаются с 0 и слева направо):

-x_1 1 

Теперь предположим, что мы имеем массив коэффициентов для p_k(x):

a_0 a_1 a_2 ... a_k 

(сторона примечание: a_k 1). Теперь мы хотим вычислить p_k+1(x), который (обратите внимание, что k+1 является индексом, и нет суммирования по 1):

p_k+1(x) = p_k(x)*(x-x_k+1) 
=> p_k+1(x) = x*p_k(x) - x_k+1*p_k(x) 

Переводя это в массив коэффициентов, то это означает, что новые коэффициенты предыдущие из них смещается вправо (x*p_k(x)) минус k+1 го корня, умноженный на один и тот же коэффициенты (x_k+1*p_k(x)):

  0 a_0 a_1 a_2 ... a_k-1 a_k 
- x_k+1 * (a_0 a_1 a_2 a_3 ... a_k) 
----------------------------------------- 
-x_k+1*a_0 (a_0-x_k+1*a_1) (a_1-x_k+1*a_2) (a_2-x_k+1*a_3) ... (a_k-x_k+1*a_k-1) a_k 

(примечание стороны: и то, как a_k остается 1) Существует ваш алгоритм. Начните с p_1(x) (или даже p_0(x) = 1) и пошаговое построение массива коэффициентов по приведенной выше формуле для каждого корня многочлена.