c++ - 牛顿-拉夫森算法:找到所有包含负的根

如何使用牛顿方法找到多项式的所有根，不仅是唯一的？

链接到代码:http://quantcorner.wordpress.com/2012/09/14/an-implementation-of-the-newton-raphson-algorithm-in-c-cpp-and-r/

例如，我有一个等式:x^2-12x+34=0，当我使用此公式时，我只得到一个根4.5857，如何得到第二个根7.4142？

最佳答案

从其他起始位置重新启动Newton Raphson。

我在这里粘贴了一些在开发金融工具定价库时实现的代码。在这里查看我的Newton Raphson代码。您将起始位置double start视为输入参数之一。您可以从网格上的不同位置开始，例如并将解决方案与您已经找到的解决方案进行比较。

#include "math.h"
#include "ExceptionClass.h"

template <class T, double (T::*Value)(const double) const,
                   double (T::*Derivative)(const double) const>
        double NewtonRaphson(double Target, double start, double Tolerance,
                             size_t max_count, const T& Object)
    {
    size_t count = 0;
    double diff = Target-(Object.*Value)(start);
    double x = start;
    double derivative = (Object.*Derivative)(start);

    do{
        count++;
        if(fabs(derivative) < 1.E-6)
            throw DivideByZeroException("Dividing by a derivative smaller than: 1.E-6!");

        x = x - diff/(-derivative);

        diff = Target-(Object.*Value)(x);
        derivative = (Object.*Derivative)(x);
    } while((fabs(diff)>Tolerance)&&(count < max_count));

    if(count >= max_count)
        throw("Newton-Raphson did not converge in the defined number of steps!");
    else return x;
    }

T是一类，您在其中定义了一些函数来评估您的(二次方)方程(此处为模板中的double (T::*Value)(const double) const所指)和该方程的导数(此处为模板中的double (T::*Derivative)(const double) const所指)。
注意由于牛顿·拉夫森(Newton Raphson)存在一些问题，因此我包括了一个异常类。

将二分法用于更稳定的算法。
实际上，您可以使用小于1.E-6的数字。

此处的值应为指向评估您的二次函数的函数的指针，目标应设置为0，导数应为指向评估您的函数的导数的函数的指针。

在您的情况下，我的模板代码可以简化:
用diff = Target-(Object.*Value)(x);替换代码diff = (Object.*Value)(x);用x = x - diff/(-derivative);替换x = x - diff/(derivative);此代码将更易于识别为Newton Raphson算法。
如果要提高收敛速度，请使用Halley(是 cometd 的家伙)算法或Householder算法。

有关替代实现，请参见c++中的数字配方。 C++的数字配方是一本用于解决此类问题的书。