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

У меня есть корни монического многочлена, т.е.

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 корня в список n коэффициентов. Я считаю, что должен быть какой-то разумный способ повторного использования большинства промежуточных результатов, но я его не нашел.


c++ performance algorithm polynomial-math
person user2690527    schedule 20.01.2014    source источник
comment
Вы можете рекурсивно построить полином с помощью свертки. Если это очень большой многочлен, в какой-то момент БПФ превзойдет метод O (n ^ 2).   -  person Aki Suihkonen    schedule 20.01.2014

Ответы (1)


arrow_upward
8
arrow_downward

Вы можете сделать это в 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) и постепенно стройте массив коэффициентов по приведенной выше формуле для каждого корня многочлена.

person Shahbaz    schedule 20.01.2014
comment
Умпф! Если земля не решит поглотить меня, я добровольно заползу под камень и умру. Все равно спасибо. :-) - person user2690527; 20.01.2014
comment
@user2690527 user2690527, на самом деле это просто простой цикл for внутри другого. Всего 3-4 строчки кода. Не сдавайся! - person Shahbaz; 20.01.2014
comment
Я знаю. Я считаю, что вы неправильно истолковали мой 1-й комментарий к вашему решению. Мой комментарий предназначен для того, чтобы сказать: позор мне. Такое простое решение, и я не сам его придумал. Две степени магистра (информатика и математика), но я потратил весь день на эту проблему. - person user2690527; 20.01.2014
comment
ахахаха, теперь понял. Поскольку я не являюсь носителем языка, иногда оказывается, что некоторые выражения имеют значение, отличное от того, что я интерпретировал. В любом случае, рад, что смог помочь. - person Shahbaz; 20.01.2014
comment
Просто мои 2 ¢: разве вокруг (x_k+1) не должно быть скобок? Умножение имеет более высокий приоритет, и умножение на 1 не изменяет значение. ГКНР. - person Heiko Schäfer; 14.02.2016
comment
Нет, это x индексируется k+1. SO не поддерживает tex math, поэтому форматирование математики затруднено. Технически я мог бы написать x_(k+1), но там и так достаточно скобок, так что большее их количество выглядело бы еще более запутанным. - person Shahbaz; 14.02.2016
comment
В ответе я еще указал это: обратите внимание, что k+1 — это индекс, и нет суммирования по 1 - person Shahbaz; 14.02.2016