牛頓迭代法收斂定理

1、f(x)在X0處的泰勒級(jí)數(shù)展式的前兩項(xiàng)做為函數(shù) 個(gè)線性函數(shù)，通過(guò)線性表達(dá)式替代方程f(x)的近似表達(dá)f(x) = 0中的f(x)求得近似解Xn 12(Xn 2/Xn),(n = 0, 1, 2,關(guān)于牛頓迭代法的課程設(shè)計(jì)實(shí)驗(yàn)指導(dǎo)非線性方程(或方程組)問(wèn)題可以描述為求x使得f(x) = 0。在求解非線性方程的方法中，牛頓迭代法是求非線性方程(非線性方程組)數(shù)值解的一種重要的方法。牛頓是微積 分創(chuàng)立者之一，微積分理論本質(zhì)上是立足于對(duì)世界的這種認(rèn)識(shí)：很多物理規(guī)律在微觀上是線性的。近幾百年來(lái)，這種局部線性化方法取得了輝煌成功，大到行星軌道計(jì)算，小到機(jī)械部 件設(shè)計(jì)。牛頓迭代法正是將局部線性化的方法用于求解

2、方程。一、牛頓迭代法及其收斂速度牛頓迭代法又稱為牛頓 -拉夫遜方法(Newton-Raphson method)，是一種在實(shí)數(shù)域和復(fù) 數(shù)域上通過(guò)迭代計(jì)算求出非線性方程的數(shù)值解方法。方法的基本思路是利用一個(gè)根的猜測(cè)值X0做初始近似值，使用函數(shù)式。由于該表達(dá)式是，XI。即將方程f(x) = 0在X0處局部線性化計(jì)算出 近似解XI,重復(fù)這一過(guò)程，將方程f(x) = 0在X1處局部線性化計(jì)算出X2,求得近似解X2,。詳細(xì)敘述如下：假設(shè)方程的解X*在X0附近(X0是方程解X*的近似)，函數(shù)f(x)在點(diǎn)X0處的局部線化 表達(dá)式為f (Xpx f(X。)+(X-X°)f(X0)由此得一次方程f (

3、x°) +(x-x°)f "(x°) =0求解，得f (Xc)Xi譏f (Xg)如圖1所示，X1比X0更接近于x*。該方法的幾何意義是：用曲線上某點(diǎn)( X0, y0)的切線 代替曲線，以該切線與 x軸的交點(diǎn)(X1, 0)作為曲線與x軸的交點(diǎn)(x*, 0)的近似(所以 牛頓迭代法又稱為切線法)。設(shè)Xn是方程解X*的近似，迭代格式Xn 1 =Xn - f (Xn)( n = 0, 1, 2,)f (Xn)就是著名的牛頓迭代公式，通過(guò)迭代計(jì)算實(shí)現(xiàn)逐次逼近方程的解。牛頓迭代法的最大優(yōu)點(diǎn)是收斂速度快，具有二階收斂。以著名的平方根算法為例，說(shuō)明二階收斂速度的意義。例

4、1 已知21.4，求、2等價(jià)于求方程f(x) = x2 -2 = 0的解。由于f (x)二2x。應(yīng)用牛頓迭代法，得迭代計(jì)算格式取X0= 1.4為初值，迭代計(jì)算 3次的數(shù)據(jù)列表如下 表1牛頓迭代法數(shù)值實(shí)驗(yàn)迭代次數(shù)近似值15位有效數(shù)誤差01.4-1.42e-00217.21e-00521.84e-0093-2.22e-016其中，第三欄15位有效數(shù)是利用 MATLAB的命令sqrt(2)計(jì)算結(jié)果。觀察表中數(shù)據(jù)，第一次 迭代數(shù)據(jù)準(zhǔn)確到小數(shù)點(diǎn)后四位， 第二次迭代數(shù)據(jù)準(zhǔn)確到小數(shù)點(diǎn)后八位， 。二階收斂速度 可解釋為，每迭代一次，近似值的有效數(shù)位以二倍速度遞增。對(duì)于計(jì)算任意正數(shù)C的平方根，牛頓迭代法計(jì)算同樣

5、具有快速逼近的性質(zhì)。二、牛頓迭代法的收斂性牛頓迭代法在使用受條件限制，這個(gè)限制就是通常所說(shuō)的牛頓迭代法的局部收斂性。定理 假設(shè)f(x)在x*的某鄰域內(nèi)具有連續(xù)的二階導(dǎo)數(shù)，且設(shè)f(x*)=o, (x*) = 0,則對(duì)充分靠近x*的初始值xo,牛頓迭代法產(chǎn)生的序列 xn收斂于下面例子是牛頓迭代法不收斂的反例。反例說(shuō)明，牛頓迭代法局部收斂性要求初始點(diǎn)要取得合適，否則導(dǎo)致錯(cuò)誤結(jié)果。3例2用牛頓迭代法解方程f(x) = x3 -x -3 = 0。分析：利用 MATLAB求多項(xiàng)式零點(diǎn)命令roots(p)，計(jì)算得三次方程的三個(gè)根如下表表2三次方程的三個(gè)根rir2r31.6717-0.8358 - 1.046

6、9i-0.8358 + 1.0469i顯然，三次方程有一個(gè)實(shí)根3。3為了使用牛頓迭代法計(jì)算，對(duì)于f(x) = x3 -x -3，首先求導(dǎo)數(shù)，得(x) = 3x - 1。取X。= 0和X0 = 1取分別用牛頓迭代法計(jì)算，得表3不同初始值的迭代計(jì)算結(jié)果對(duì)于迭代初值取算法將陷入死循環(huán)。X001X1-3.00002.5000X2-1.96151.9296X3-1.1472 1.7079X4-0.00661.6726X5-3.00041.6717X6-1.96181.6717而迭代初值取xo=1，可以使牛頓迭代法得到收斂。三、特殊代數(shù)方程的牛頓迭代法收斂區(qū)域?qū)⑴ｎD迭代法用于求解高階代數(shù)方程時(shí)，首先回顧一

7、個(gè)代數(shù)基本定理，即“一個(gè)n階多項(xiàng)式在復(fù)數(shù)域內(nèi)有 n個(gè)根”。根據(jù)牛頓迭代法的局部收斂性質(zhì)，任意取一個(gè)數(shù)據(jù)做為牛頓迭 代的初值，可能導(dǎo)致迭代不收斂，即使這一個(gè)初值可以使迭代法收斂，下一個(gè)有趣的問(wèn)題是“迭代序列將收斂于哪一個(gè)根”例3牛頓迭代法的收斂區(qū)域問(wèn)題: 該方程在復(fù)平面上三個(gè)根分別是，其規(guī)律如何？Newt on迭代法可以用于求解復(fù)數(shù)方程Z3 -1 = 0 ,4 丄 V3.Z3i2 2選擇中心位于坐標(biāo)原點(diǎn)， 邊長(zhǎng)為4的正方形內(nèi)的任意點(diǎn)作初始值，進(jìn)行迭代，定義為第一類，給它們標(biāo)一種顏色；再把收斂到三個(gè)根的初值分為三類， 色。對(duì)充分多的初始點(diǎn)進(jìn)行實(shí)驗(yàn)，繪出牛頓迭代法對(duì)該方程的收斂域彩色圖。Z1= 1

8、, z2將不收斂的點(diǎn) 并分別標(biāo)上不同顏0-i2-11圖3牛頓迭代法收斂區(qū)域色圖問(wèn)題分析：記f(z) = z3 -1,則f (z)二3z2，所以牛頓迭代公式為2Zn 1 =Zn -(Zn -1/Zn)/3由于牛頓迭代法的二階收斂速度，對(duì)于一個(gè)取定的初值Z0,如果Z0是一個(gè)可以導(dǎo)致迭代收斂的初值，則迭代10次已經(jīng)達(dá)到足夠精度，故可以取迭代次數(shù)為 10?？紤]以坐標(biāo)原點(diǎn)為中 心的正方形區(qū)域11 =（X, y）| _2x2, _2冬 y乞 2取步長(zhǎng)h=0.02,在區(qū)域內(nèi)取離散網(wǎng)格點(diǎn)Xj = 2 + j 漢 h小一 2+kS，（ j，k =0，1，200）由此可以構(gòu)造出規(guī)則的復(fù)數(shù)Zk = Xj + i y

9、k, ( j, k =0, X ，200)對(duì)于這些點(diǎn)，逐一用牛頓迭代法取初值進(jìn)行迭代實(shí)驗(yàn)，判斷是否收斂？如果收斂，到底以該點(diǎn)為初值的迭代序列收斂到哪方程的一個(gè)根？為了記錄實(shí)驗(yàn)結(jié)果，構(gòu)造四個(gè)階數(shù)均為201 X 201矩陣：Z0、Z1、Z2、Z3,開(kāi)始時(shí)這四個(gè)矩陣都設(shè)為全零矩陣。如果以Zk為初值的迭代實(shí)驗(yàn)結(jié)果是不收斂，則將Z0的第j行第k列的元素改寫(xiě)為1；如果以Zjk為初值的迭代實(shí)驗(yàn)結(jié)果是收斂到第一個(gè)根，則將乙的第j行第k列的元素改寫(xiě)為1 ；如果以Zjk為初值的迭代實(shí)驗(yàn)結(jié)果是收斂到第二個(gè)根，則將Z2的第j行第k列的元素改寫(xiě)為1 ;如果以Zk為初值的迭代實(shí)驗(yàn)結(jié)果是收斂到第三個(gè)根，則將乙的第j行第k列

10、的元素改寫(xiě)為1。首先分析矩陣Zo的數(shù)據(jù)，由于該矩陣在開(kāi)始時(shí)刻為全零矩陣，而在迭代實(shí)驗(yàn)結(jié)束后，不收斂的點(diǎn)對(duì)應(yīng)元素被改寫(xiě)為“ 1 ”所以，矩陣的元素只可能是“ 0”或“ 1”根據(jù)該矩陣 的全部的非零元素所在的位置可以使用MATLAB的圖形繪制命令 spy()或pcolor()等顯示出一個(gè)特殊的圖形。根據(jù) Zo數(shù)據(jù)繪的圖形如下所示圖4牛頓迭代法不收斂區(qū)域色圖導(dǎo)致牛頓迭代法不收斂的初始點(diǎn)所形成的平面點(diǎn)集是一個(gè)著名的集合，稱為茹莉亞集(為紀(jì)念法國(guó)女?dāng)?shù)學(xué)家茹莉亞而命名)。為了得到全局的收斂或不收斂情況，需要對(duì)四個(gè)矩陣進(jìn)行疊加。如果直接相加將導(dǎo)致一個(gè)全“1”矩陣，不可能得出希望的結(jié)果。故，對(duì)矩陣做如下組合處

11、理，令Z = Zo + 2Z1 + 3Z2 + 4Z3則矩陣Z的元素由“ 1” “2” “3”、“4”這四個(gè)元素組成。該矩陣的某一位置上數(shù)據(jù)為“1 ”說(shuō)明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法不收斂；位置上數(shù)據(jù)為“2”說(shuō)明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法收斂到第一個(gè)根；位置上數(shù)據(jù)為“ 3 ”說(shuō)明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法收斂到第二個(gè)根；位置上數(shù)據(jù)為“ 4”說(shuō)明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法收斂到第三個(gè)根。所以該矩陣包含了矩陣區(qū)域內(nèi)離散點(diǎn)集合做為牛頓迭代法收斂實(shí)驗(yàn)結(jié)果的全部信息。將這一矩陣用MATLAB作圖命令pcolor()作用，將繪出圖 3所示的收斂區(qū)域色圖。導(dǎo)致牛頓迭代法

12、收斂到第一個(gè)根的初始點(diǎn)所形成的平面點(diǎn)集，可以根據(jù)Z1數(shù)據(jù)繪圖形四、關(guān)于實(shí)驗(yàn)的注記1. MA TLAB相關(guān)命令介紹(1)求多項(xiàng)式零點(diǎn)命令roots()該命令用于求多項(xiàng)式P(x) =a1xn+ a2 xn-1+anx+an+1的全部零點(diǎn)。例如z3-1=0的三個(gè)零點(diǎn)，只需用命令： roots(1 0 0 -1)，可得ans =-0.5000 + 0.8660i-0.5000 - 0.8660i1.0000(2 )繪偽彩色圖命令 pcolor()該命令主要用于繪制矩陣色圖，根據(jù)矩陣中元素?cái)?shù)據(jù)的大小不同繪不同顏色。常常與命令shadi ng in terp結(jié)合使用效果會(huì)更好。在 MATLAB命令窗口中鍵

13、入 help pcolor，可獲得英文幫助信息。2.例題3所用MATLAB程序及注釋：X=roots(1,0,0,-1); r1= X(1);r2=X(2);r3=X(3); h=0.02;N=1+4/h; zO(N,N)=O;z 仁z0;z2=z0;z3=z0; t=(-2:h:2)+eps; x,y=meshgrid(t); z=x+y*i;forj=1:Nfor k=1:N p=z(j,k); for n=1:10 p=p-(p-1/pA2)/3;endif abs(p-r1)<0.01z1(j,k)=1;elseif abs(p-r2)<0.01 z2(j,k)=1;els

14、eif abs(p-r3)<0.01 z3(j,k)=1;else z0(j,k)=1;endendendZ=z0+2*z1+3*z2+4*z3; figure(1) pcolor(x,y,Z),shading interp figure(2) pcolor(x,y,z0),shading interp%利用MATLAB命令求三次方程的根%確定網(wǎng)格步長(zhǎng)及網(wǎng)格點(diǎn)規(guī)模%定義四個(gè)大矩陣為全零矩陣%確定網(wǎng)格點(diǎn)坐標(biāo)%提取迭代初始點(diǎn)%牛頓迭代操作%確定收斂到第一個(gè)根的初始點(diǎn)%確定收斂到第二個(gè)根的初始點(diǎn)%確定收斂到第三個(gè)根的初始點(diǎn)%確定不收斂的初始點(diǎn)%繪牛頓迭代法收斂域%繪牛頓迭代法不收斂域課程設(shè)計(jì)實(shí)

15、驗(yàn)題目1 牛頓迭代法解復(fù)方程 z n + 1=0的收斂域問(wèn)題。 實(shí)驗(yàn)?zāi)康模?0(n> 3)時(shí)收斂域的結(jié)構(gòu)。了解Newton迭代法解復(fù)方程 z n + 1z n + 1 = 0 ,例如對(duì)z6 + 1 = 0 ,該方程在復(fù)平實(shí)驗(yàn)原理：Newt on迭代法可以用于求解復(fù)數(shù)方程 面上六個(gè)根分別是Z1li1 ?231.i , zz= i ,2v31Z6 -i2 2選擇中心位于坐標(biāo)原點(diǎn)，邊長(zhǎng)為 代，將不收斂的初值點(diǎn)歸為第一類， 色做圖。對(duì)充分多的初始點(diǎn)進(jìn)行實(shí)驗(yàn)， 2 牛頓迭代法計(jì)算隱函數(shù)值實(shí)驗(yàn)實(shí)驗(yàn)?zāi)康模毫私怆[函數(shù)存大定理與牛頓迭代法之間的聯(lián)系。 實(shí)驗(yàn)原理：31 .+ i2 2 ，的正方形(或半徑為4

16、的圓)內(nèi)的任意點(diǎn)作初始值進(jìn)行迭 再把收斂到六個(gè)根的初值歸為另外六類，分別以不同顏繪出牛頓迭代法對(duì)該方程的收斂域彩色圖。隱函數(shù)存在定理敘述為：如果f(x, y)及fy (x, y)皆在(xo, yo)附近連續(xù)，而且f(xo, yo) = 0, fy(Xo,yo)=O則在(xo, yo)的附近，方程f(x, y) = 0恰有一個(gè)連續(xù)解 y =y(x)。隱函數(shù)存在定理具有局部性，這種局部性與牛頓迭代法的局部收斂性有相通之處。在鄰域、(xo，yo) = (xo) x (yo)=(x, y) | x _xo| <、，|y -yo| <、內(nèi)計(jì)算隱函數(shù)的值。取xi 、(xo)=x | x-xo|

17、< ，存在yi 、(yo)=y | |y-yo|< .，使得yi =y(xi)滿足f(xi, yi) = o。由此導(dǎo)出關(guān)于函數(shù)值 y的一元非線性方程g(y) = f(xi, y) = o由于f(x, y)及fy(x,y)皆在.(xo, yo)連續(xù)，故fy(xi,yj = 0，且y件yo。應(yīng)用牛頓迭 代法，得迭代計(jì)算格式(k+1)(k) Q 、,(k)、/£/、,(k)、y = y-f(xi, y )/fy(xi, y )迭代初值取為：y(o)= yo。由牛頓迭代法的局部收斂性可知，迭代計(jì)算可求得隱函數(shù)的高精度函數(shù)值。將這一過(guò)程進(jìn)行下去可計(jì)算出一系列的函數(shù)值并制做出函數(shù)表。例如對(duì)于二元多項(xiàng)式函數(shù) G(x, y) = 3x7 + 2