牛頓迭代法的基本思想

1、Newton迭代法的基本思想,設(shè) 是f(x)=0的一個(gè)近似根，把f(x)在 處作泰勒展開 若取前兩項(xiàng)來近似代替f(x)(稱為f(x)的線性化)，則得近似的線性方程 設(shè) ,令其解為 ,得 （1) 這稱為f(x)=0的牛頓迭代格式。,下一頁,它對(duì)應(yīng)的迭代方程為 顯然是f(x)=0的同解方程， 故其迭代函數(shù)為 在 f(x)=0的根 的某個(gè)鄰域 內(nèi), 在 的鄰域R 內(nèi)，對(duì)任意初值 ，應(yīng)用由公式（1）來解方程的方法就稱為牛頓迭代法。它是解代數(shù)方程和超越方程的有效方法之一.,返回,下一頁,上一頁,牛頓法的幾何意義,由（1）式知 是點(diǎn) 處 的切線 與X軸的交點(diǎn)的橫坐標(biāo)（如圖）。也就是說，新的近似值 是用代替

2、曲線y=f(x)的切線與x 軸相交得到的。繼續(xù)取點(diǎn) ,再做切線與x軸相交，又可得 。由圖可見，只要初值取的充分靠近 ,這個(gè)序列就會(huì)很快收斂于 。 Newton迭代法又稱切線法,下一頁,上一頁,返回,返回,下一頁,上一頁,牛頓迭代法的步驟,步一、準(zhǔn)備。選定初始近似值 ，計(jì)算 步二、迭代。按公式 迭代一次，得到新的近似值 ，計(jì)算 步三、控制。如果 滿足 。 則終止迭代，以 作為所求的根；否則轉(zhuǎn)步四。此處 是允許誤差,返回,下一頁,上一頁,而 。其中c是取絕對(duì)值或相對(duì)誤差 的控制常數(shù)，一般可取c=1。 步四、修改。如果迭代次數(shù)達(dá)到預(yù)定指定的次數(shù)N，或者 則方法失?。环駝t以 代替 轉(zhuǎn)步二繼續(xù)迭代。,返

3、回,下一頁,上一頁,例題,例1:用牛頓法求下面方程的根 解 因 ,所以迭代公式為 選取 ,計(jì)算結(jié)果列于下表 從計(jì)算結(jié)果可以看出,牛頓法的收斂速度是很快的,進(jìn)行了四次迭代就得到了較滿意的結(jié)果.,返回,下一頁,上一頁,例2 計(jì)算 的近似值。 =10-6 x0=0.88 解： 令x= 問題轉(zhuǎn)化為求(x)= x2-0.78265=0的正根 由牛頓迭代公式 xk+1= xk-(xk)/(xk)= xk/2+0.78265/2xk 迭代結(jié)果 k 0 1 2 3 xk 0.880000 0.884688 0.884675 0.884675 滿足了精度要求 =0.884675,返回,下一頁,上一頁,返回,下一

4、頁,上一頁,2)修正Newton法求m重根迭代公式 注：若 是方程 的m重根，而 在 的 某一鄰域內(nèi)連續(xù)，則修正 Newton法是局部收斂的，并具有至少二階的收斂速度。 因?yàn)椋?上一頁,下一頁,返回,考察函數(shù),用定義求導(dǎo),Tailor展開,所以,由定理2知,至少是二階收斂,上一頁,下一頁,返回,牛頓迭代法的優(yōu)缺點(diǎn),1、優(yōu)點(diǎn)：牛頓迭代法具有平方收斂的速度，所以在迭代過程中只要迭代幾次就會(huì)得到很精確的解。這是牛頓迭代法比簡(jiǎn)單迭代法優(yōu)越的地方。 2、缺點(diǎn)：選定的初值要接近方程的解，否則有可能的不到收斂的結(jié)果。再者，牛頓迭代法計(jì)算量比較大。因每次迭代除計(jì)算函數(shù)值外還要計(jì)算微商值。,返回,下一頁,上一頁,設(shè)(x )在有根區(qū)間 (a,b)上存在二階導(dǎo)數(shù)，且滿足 （1）(a)