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

Question

poly函数的输入是多项式的根，输出为多项式系数。其背后的算法是什么？

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

- swap96

Answer 1

因为您要求提供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;
}

希望这有所帮助。

- g-217

---

为什么你会在多项式和临时向量中使用 int 数据类型？我建议使用浮点数数据类型。 - Dan Doe

Answer 2

请注意：

• 要获得带有首项系数1的多项式p(x)，您需要将所有形式为x−r的项相乘，其中r是一个根。（多重根应根据它们的重数考虑多次。）

• 多项式乘法等价于卷积。实际上，conv的文档说：

  w = conv(u,v)返回向量u和v的卷积。如果u和v是多项式系数的向量，则将它们进行卷积等价于将两个多项式相乘。

因此：

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

在这个例子中，结果是：

result =
     1    -2    -5     6

这是与poly返回相同向量的方法。

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

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

- Luis Mendo

---

我想知道这个能否在 C++ 中也轻松实现？ - swap96

我对C++不是很了解，但我已经添加了一个新版本，应该接近使用那种语言的方式。请检查编辑后的答案。 - Luis Mendo