如何找到多项式的多个根?

计算科学 C++ 多项式 非线性方程
2021-12-23 12:51:19

该程序找到代码中定义的函数 f 的第一个根。这个函数有 5 个根。(x=1,2,3,4,5) 我希望找到该程序中的所有根并将它们打印到屏幕上。在 main 函数中,您可以看到我试图编写一个 while 循环来执行此操作(在下面的代码中注释掉)。但这不起作用,它只是将相同的结果无限地打印到屏幕上。任何帮助,将不胜感激。

// This program finds the roots of a polynomial using the half interval search method

#include <iostream> //preprocessor directive needed in order to use std::cout
                //and std::cin
#include <iomanip> //preprocessor directive needed in order to use
               //a manipulator which uses an argument

using namespace std; //avoids having to uses std:: with cout and cin

//declare the variables
const double a = 0.0, b = 6.0; //limits for f()
double px = 1e-6;              //define the precision
double x = a, dx = 1.0;        //start value and initial interval
double root;

//prototypes for f()
double f (double x);
double halfIntervalSearch (double a, double b, double dx, double px); 

int main (int argc, char* argv[])
{
    //Inform the user what the program does
    cout << "This program finds the roots of\n"
    "f(x) = x^5 - 15x^4 + 85x^3 - 225x^2 + 274x -120 = 0\n"
    "which is bracketed by [" << a << ", " << b <<
    "] using the half interval search method." << endl;

    cout << "Searching...\n"; //Lets user know what is happening

    root = halfIntervalSearch(a,b,dx,px); //pass the variable

    //print out results
    //while (x <= b)
    {
          //x = root + 2*px; //reset value of x
          cout << "\nRoot at x = " << setw(10) << setprecision(7) << fixed 
          << root << " of value " << f(root) << endl;      
    }    
    //allow user to see the results before ending the program
    cout << "\n\nPress Enter to end the program";
    cin.get();
}

////////////////////////////////////////////////////////////////////////////////
//define f()
double f (double x)
{
       return (x*x*x*x*x)-(15*x*x*x*x)+(85*x*x*x)-(225*x*x)+(274*x)-120;  
}
///////////////////////////////////////////////////////////////////////////////
//define halfIntervalSearch()
double halfIntervalSearch (double a, double b, double dx, double px)
{
       while ((x <= b) && (dx > px))
       {
             while ( f(x)* f(x+dx) > 0) //while there are no roots 
             {
                   //keep track while program finds roots
                   cout << "x = " << setw(18) << x << " | dx = " << setw(15) 
                        << right << dx << endl;
                   x += dx; //step forward
             }

             dx = dx/2; //half the interval
       }
       return x;
}
4个回答

如果您可以使用复杂的算术,那么同时迭代方法可能更适合计算多项式的所有根。最简单的同时迭代方法,即(Weierstrass-)Durand-Kerner 方法,实际上等效于将 Newton-Raphson 应用于将多项式的系数和根视为联立方程的 Vieta 关系。(另请参阅此 math.SE 答案。)因此,如果多项式没有重复根,则此方法也是二次收敛的。

通常,该方法从位于复平面中的圆周围的初始近似值开始,中心和半径由系数确定(这就是我提到需要复数算术的原因)。如果您事先知道根是真实的,并且您已经对所有根有了很好的近似值,那么也可以使用 Durand-Kerner 进行抛光。

一种相关的同时迭代方法是Ehrlich-Aberth(-Maehly),Gert 在他的回答中简要提及。如果多项式的根都很简单,则该方法具有三次收敛性,但迭代公式有点复杂,涉及多项式导数的评估(当然可以用霍纳来完成)。在这两种方法之间进行选择需要您进行一些测试。

正如 David Ketcheson 所指出的,一种方法是使用伴随矩阵并找到它的特征值(这是 Matlab 对roots函数所做的)。

但是,如果您想自己编写所有代码,可以尝试使用Sturm 序列,作为第一步,您可以找到只有一个零的区间。然后,您可以应用一种标准方法来查找该区间内的根(牛顿二等分...)。

这更容易编码,但可能不如第一种方法那么健壮。

让我们为函数应该做什么列出一些规范halfIntervalSearch,然后从那里开始对代码进行必要的更改。

我假设它应该使用区间二分法找到(和return)(硬编码)函数的根。f这背后的数学原理是,在区间内改变符号的连续函数必须在那里至少有一个根。

因此,一个典型的实现是调用具有这样一个区间的二分法,通过在中点的连续评估来细化区间,结果是每次评估都会导致找到一个(足够近似的)根或减少区间的宽度减半(通过保留已知函数改变符号的较早区间的一半)。

你的代码做这样的halfIntervalSearch事情,但我怀疑它的方法过于间接。在传递给这个函数的四个参数中,第一个根本没有使用。更重要的是,您的实现不是使用保留间隔的符号更改属性的单个循环构造,而是使用嵌套的循环构造对,其内部循环理论上能够“向前”跨越任何特定的根(可能全部)x += dx:。我不认为这是一个合理的方法。

现在搜索多项式的根很难完全概括,所以我们不应该把标准设置得太高。但是,回到数学动机(中值定理),我们最好实现一个例程,该例程通过符号变化迭代地细化区间,直到找到(足够近似的)根。

更高级别的问题是如何调用/使用这样的例程。这通常是通过粗略地搜索感兴趣的“大区间”(在您的程序中为[a,b])来检测符号变化来完成的。一旦找到函数更改符号的(适度大小)子区间,将仅在该子区间上调用二分法例程(保证我们至少从该子区间获得一个根)。

定位一般多项式的所有根是一个难题。如果一个根具有偶数多重性,则多项式将不会改变符号(除了它在那个根处正好变为零)。更一般地,您可能有一对非常靠近的根,粗略的搜索会一步通过它们,从而错过这些。

我仍然建议您专注于halfIntervalSearch函数的开发,以保留符号变化的区间,一旦到位,我们也许可以重新审视多重性 > 1 的根的一些令人烦恼的话题,等等。

另一种方法是通货紧缩方法。在这种方法中,您通常将像牛顿的迭代方法应用于原始多项式以找到第一个根。接下来,您再次应用牛顿算法,但这次是应用于放气多项式,即原始多项式除以xx1在哪里x1是第一个根。通过智能地使用霍纳规则,您可以稳定地评估放气多项式,而无需显式计算系数。您可以重复此操作,直到您完全放气多项式。通常,然后使用刚刚计算的根作为初始值对原始多项式执行一两个额外的牛顿步骤。我相信这种方法被称为 Maehly 算法。