牛頓疊代法

牛頓疊代法知識，以及求平方根的程式

1. 疊代公式建立

将

在

點的Taylor展開如下：

一階泰勒多項式：

近似于

解出x記為

，則

2. 牛頓疊代法的幾何解析

處做曲線的切線，切線方程為：

令

得切線與x軸的交點坐标為

，這就是牛頓疊代法的疊代公式。是以，牛頓法又稱“切線法”。

Newton疊代法的特點是：

1. 對初值

的選取要求較高。一般的，Newton疊代法隻有局部收斂性，當初值

在收斂區間裡時，收斂速度很快(平方收斂)。但初值

離方程根x*較遠時，不能保證Newton疊代法收斂。

2. Newton疊代法求單根時，收斂速度很快(平方收斂)。但如果方程根

是重根，則收斂速度較慢，且重數越高速度越慢。但當

是m重根時,用下面的疊代格式：

則至少能保持平方收斂。

3.應用：用有Newton疊代法求

求解：設

取

程式實作：

#define ABS(VAL) (((VAL)>0)?(VAL):(-(VAL)))   
//用牛頓疊代法求浮點數的平方根   
double mysqrt(float x) {   
    double g0,g1;   
    if(x==0) 
        return 0;   
    g0=x/2;   //初值
    g1=(g0+x/g0)/2;   
    while(ABS(g1-g0)>0.01) //終止條件  
    {   
        g0=g1;   
        g1=(g0+(x/g0))/2;   //疊代規則
    }   
    return g1;   
}      

或

double sqr(double n) {
    double k=1.0;
    while(abs(k*k-n)>1e-9) {
        k=(k+n/k)/2;
    }
    return k;
}      

附加：

1. Newton下山法

由于當初值

離方程根

較遠時，不能保證Newton疊代法收斂，但一旦

進入收斂區間，則收斂速度很快。為使

盡快進入收斂區間，常采用Newton下山法：

稱為下山因子

具體做法如下：

1. 選取初值

2. 取下山因子

（可修改）

3. 計算

4. 計算

并比較

與

的大小：

若

         1） 當

時，取

，結束；

         2） 當

時，将

作為新的

值繼續計算；

，則取

，傳回3。

2. 弦截法（方程常用的求解方法）

将Newton切線法中的切線斜率

用弦的斜率替換：