Newton-Raphson算法：找到所有的根都包含負數

Question

如何使用牛頓法找出多項式的所有根，不僅是唯一的？

鏈接代碼：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？

Answer 1

從不同的起始位置重新啓動您的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 = (Object.*Value)(x); 替換代碼diff = Target-(Object.*Value)(x);與x = x - diff/(derivative);這個代碼將被更容易識別的牛頓拉夫森算法替換x = x - diff/(-derivative);。 如果你想提高收斂速度，請使用哈雷（是彗星的傢伙）算法或Householder算法。

請參閱C++中的數字菜譜以供替代實現。 C++中的數值食譜是解決這類問題的書。