牛頓公式：x(k+1) = x(k) - f(x(k)) / f '(x(k))

  迭代函數：Ф(x) = x - f(x) / f'(x)

  屬性：方程求根迭代法
 
  此時的迭代函數必須保證X(k)有極限，即迭代收斂。

《數值計算方法與算法》-2 Editon -科學出版社 P93
《C#數值計算算法編程》-周長發 P210
   
 代碼維護：2007.04.20   pengkuny
**/

#include<iostream>
#include<cmath>

using namespace std;

#define f(x) (x*x*(x-1.0)-1.0)  //舉例函數x^3-x^2-1
#define g(x) (3.0*x*x-2.0*x)  //導函數3x^2-2x
#define epsilon 0.0000001  //精度
#define MAXREAPT 100

bool RootNewton(double &x)
{
    double xk1,xk0;

    xk0 = x;
    for (int k=0; k<MAXREAPT; k++)
    {
        if (g(xk0) == 0.0)//牛頓迭代法缺陷在于:收斂是否與初值x0密切相關
        {//如果g(xk0)數值特別小時,有可能發生從一個根跳到另一個根附近的情況
            cout<<"迭代過程中導數為0."<<endl;
            return false;
        }

        xk1 = xk0 - f(xk0)/g(xk0);//key step

        if (fabs(xk1-xk0) < epsilon && fabs(f(xk1)) < epsilon)
        {//注意迭代結束條件是: |f(xk1)| < ε和|xk1-xk0| < ε同時成立,防止根跳躍
            x = xk1;
            return true;
        }
        else
        {
            xk0 = xk1;
        }
    }

    //迭代失敗
    cout<<"迭代次數超過預期."<<endl;
    return false;
}

int main()
{
    double x;
    cout<<"牛頓迭代法求方程根,請輸入初始迭代x0值:"<<endl;
    cin>>x;

    if(RootNewton(x))
    {
        cout<<"該值附近的根為:"<<x<<endl;
    }
    else
    {
        cout<<"迭代失敗!"<<endl;
    }

    system("pause");
    return 0;
}