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