从根计算多项式系数的最佳方法是什么？

Question

poly 函数将多项式的根作为输入，returns 将多项式的系数作为输入。底层算法是什么？

有没有更好的方法从根计算多项式的系数？

Answer 1

注意：

要获得多项式p(x)（前导系数1）你需要乘形式为x−r的所有项，其中r是一个根。（多根要根据其重数考虑几次。）
多项式的乘法相当于卷积。事实上，documentation of conv 表示

w = conv(u,v) returns the convolution of vectors u and v. If u and v are vectors of polynomial coefficients, convolving them is equivalent to multiplying the two polynomials.

所以：

roots = [1 -2 3]; %// input (roots)
result = 1;  %// initiallize
for r = roots
    result = conv(result, [1 -r]);
end

在这个例子中，结果是

result =
     1    -2    -5     6

与 poly returns.

相同的向量

或者，您可以进行卷积手动:

roots = [1 -2 3]; %// input (roots)
result = 1;  %// initiallize
for r = roots
    result = [result 0] + [0 -r*result];
end

这等同于以下带有 显式循环的代码 ，应该更接近 C++ 实现：

roots = [1 -2 3]; %// input (roots)
result = nan(1,numel(roots)+1);  %// preallocate. Values will be overwritten
result(1) = 1; %// initiallize
for n = 1:numel(roots)
    result(n+1) = -roots(n)*result(n); %// update from right to left, due to overwriting
    for k = n:-1:2
        result(k) = result(k) - roots(n)*result(k-1);
    end
end

Answer 2

自从您请求 c++ 答案以来。一个典型的实现看起来像。

std::vector<int> poly( std::vector<int> roots )
{
    std::vector<int> result{1};
    for( size_t i = 0 ; i < roots.size() ; ++i)
    {
        std::vector<int> temp{result.begin(),result.end()};

        for(auto & item : temp )
            item *= ( -roots[i] );

        result.push_back(0);
        for( size_t j = 1 ; j < result.size() ; ++j)
        {
            result[j] += temp[j-1];
        }
    }
    return result;
}

希望对您有所帮助

从根计算多项式系数的最佳方法是什么？

What's the best way to compute the coefficients of a polynomial from its roots?

matlab

polynomials