關(guān)于牛頓迭代法的課程設(shè)計實驗指導(dǎo)

1、關(guān)于牛頓迭代法的課程設(shè)計實驗指導(dǎo)非線性方程（或方程組）問題可以描述為求 x 使得f(x) = 0。在求解非線性方程的方法中，牛頓迭代法是求非線性方程（非線性方程組）數(shù)值解的一種重要的方法。牛頓是微積分創(chuàng)立者之一，微積分理論本質(zhì)上是立足于對世界的這種認(rèn)識：很多物理規(guī)律在微觀上是線性的。近幾百年來，這種局部線性化方法取得了輝煌成功，大到行星軌道計算，小到機(jī)械部件設(shè)計。牛頓迭代法正是將局部線性化的方法用于求解方程。一、牛頓迭代法及其收斂速度牛頓迭代法又稱為牛頓-拉夫遜方法（Newton-Raphson method），是一種在實數(shù)域和復(fù)數(shù)域上通過迭代計算求出非線性方程的數(shù)值解方法。方法的基本思路是利

2、用一個根的猜測值x0做初始近似值，使用函數(shù)f(x)在x0處的泰勒級數(shù)展式的前兩項做為函數(shù)f(x)的近似表達(dá)式。由于該表達(dá)式是一個線性函數(shù)，通過線性表達(dá)式替代方程f(x) = 0中的f(x)求得近似解 y xO x* x1 x0x1。即將方程f(x) = 0在x0處局部線性化計算出近似解x1，重復(fù)這一過程，將方程f(x) = 0在x1處局部線性化計算出x2，求得近似解x2，。詳細(xì)敘述如下：假設(shè)方程的解x*在x0附近（x0是方程解x*的近似），函數(shù)f(x)在點x0處的局部線化表達(dá)式為由此得一次方程圖1 牛頓迭代法示意圖求解，得如圖1所示，x1比x0更接近于x*。該方法的幾何意義是：用曲線上某點（x

3、0，y0）的切線代替曲線，以該切線與x軸的交點（x1，0）作為曲線與x軸的交點（x*，0）的近似（所以牛頓迭代法又稱為切線法）。設(shè)xn是方程解x*的近似，迭代格式 ( n = 0，1，2，)就是著名的牛頓迭代公式，通過迭代計算實現(xiàn)逐次逼近方程的解。牛頓迭代法的最大優(yōu)點是收斂速度快，具有二階收斂。以著名的平方根算法為例，說明二階收斂速度的意義。例1已知，求等價于求方程f(x) = x2 2 = 0的解。由于。應(yīng)用牛頓迭代法，得迭代計算格式，（n = 0，1，2，）取x0= 1.4為初值，迭代計算3次的數(shù)據(jù)列表如下表1 牛頓迭代法數(shù)值實驗迭代次數(shù)近似值15位有效數(shù)誤差01.41.414213562

4、37310-1.42e-00211.414285714285711.414213562373107.21e-00521.414213564213561.414213562373101.84e-00931.414213562373091.41421356237310-2.22e-016其中，第三欄15位有效數(shù)是利用MATLAB的命令sqrt(2)計算結(jié)果。觀察表中數(shù)據(jù)，第一次迭代數(shù)據(jù)準(zhǔn)確到小數(shù)點后四位，第二次迭代數(shù)據(jù)準(zhǔn)確到小數(shù)點后八位，。二階收斂速度可解釋為，每迭代一次，近似值的有效數(shù)位以二倍速度遞增。對于計算任意正數(shù)C的平方根，牛頓迭代法計算同樣具有快速逼近的性質(zhì)。二、牛頓迭代法的收斂性牛頓迭

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

6、。為了使用牛頓迭代法計算，對于 f(x) = x3 x 3 ，首先求導(dǎo)數(shù)，得。取x0 = 0和x0 = 1取分別用牛頓迭代法計算，得表3 不同初始值的迭代計算結(jié)果x001x1-3.00002.5000x2-1.96151.9296x3-1.14721.7079x4-0.00661.6726x5-3.00041.6717x6-1.96181.6717對于迭代初值取x0=0，迭代數(shù)列中的第四項又回到初始點x0 = 0附近，算法將陷入死循環(huán)。圖2 牛頓迭代法初值不收斂示意圖而迭代初值取x0=1，可以使牛頓迭代法得到收斂。三、特殊代數(shù)方程的牛頓迭代法收斂區(qū)域?qū)⑴ｎD迭代法用于求解高階代數(shù)方程時，首先回顧

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

8、區(qū)域色圖問題分析：記f(z) = z3 1，則，所以牛頓迭代公式為由于牛頓迭代法的二階收斂速度，對于一個取定的初值z0，如果z0是一個可以導(dǎo)致迭代收斂的初值，則迭代10次已經(jīng)達(dá)到足夠精度，故可以取迭代次數(shù)為10?？紤]以坐標(biāo)原點為中心的正方形區(qū)域取步長h=0.02，在區(qū)域內(nèi)取離散網(wǎng)格點，( j，k =0，1，200)由此可以構(gòu)造出規(guī)則的復(fù)數(shù)zjk = xj + i yk，( j，k =0，1，200)對于這些點，逐一用牛頓迭代法取初值進(jìn)行迭代實驗，判斷是否收斂？如果收斂，到底以該點為初值的迭代序列收斂到哪方程的一個根？為了記錄實驗結(jié)果，構(gòu)造四個階數(shù)均為201×201矩陣：Z0、Z1、Z

9、2、Z3，開始時這四個矩陣都設(shè)為全零矩陣。如果以zjk為初值的迭代實驗結(jié)果是不收斂，則將Z0的第j行第k列的元素改寫為1；如果以zjk為初值的迭代實驗結(jié)果是收斂到第一個根，則將Z1的第j行第k列的元素改寫為1；如果以zjk為初值的迭代實驗結(jié)果是收斂到第二個根，則將Z2的第j行第k列的元素改寫為1；如果以zjk為初值的迭代實驗結(jié)果是收斂到第三個根，則將Z3的第j行第k列的元素改寫為1。首先分析矩陣Z0的數(shù)據(jù)，由于該矩陣在開始時刻為全零矩陣，而在迭代實驗結(jié)束后，不收斂的點對應(yīng)元素被改寫為“1”。所以，矩陣的元素只可能是“0”或“1”，根據(jù)該矩陣的全部的非零元素所在的位置可以使用MATLAB的圖形繪

10、制命令spy()或pcolor()等顯示出一個特殊的圖形。根據(jù)Z0數(shù)據(jù)繪的圖形如下所示圖4 牛頓迭代法不收斂區(qū)域色圖導(dǎo)致牛頓迭代法不收斂的初始點所形成的平面點集是一個著名的集合，稱為茹莉亞集（為紀(jì)念法國女?dāng)?shù)學(xué)家茹莉亞而命名）。為了得到全局的收斂或不收斂情況，需要對四個矩陣進(jìn)行疊加。如果直接相加將導(dǎo)致一個全“1”矩陣，不可能得出希望的結(jié)果。故，對矩陣做如下組合處理，令Z = Z0 + 2Z1 + 3Z2 + 4Z3則矩陣Z的元素由“1”、“2”、“3”、“4”這四個元素組成。該矩陣的某一位置上數(shù)據(jù)為“1”，說明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法不收斂；位置上數(shù)據(jù)為“2”，說明這一位置上的復(fù)數(shù)做

11、初值導(dǎo)致牛頓迭代法收斂到第一個根；位置上數(shù)據(jù)為“3”，說明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法收斂到第二個根；位置上數(shù)據(jù)為“4”，說明這一位置上的復(fù)數(shù)做初值導(dǎo)致牛頓迭代法收斂到第三個根。所以該矩陣包含了矩陣區(qū)域內(nèi)離散點集合做為牛頓迭代法收斂實驗結(jié)果的全部信息。將這一矩陣用MATLAB作圖命令pcolor()作用，將繪出圖3所示的收斂區(qū)域色圖。導(dǎo)致牛頓迭代法收斂到第一個根的初始點所形成的平面點集，可以根據(jù)Z1數(shù)據(jù)繪圖形四、關(guān)于實驗的注記1MATLAB相關(guān)命令介紹（1）求多項式零點命令roots()該命令用于求多項式P(x) = a1xn + a2 xn-1 + + anx + an+1的全部零點

12、。例如z3 1 = 0的三個零點，只需用命令：roots(1 0 0 -1)，可得ans = -0.5000 + 0.8660i -0.5000 - 0.8660i 1.0000 （2）繪偽彩色圖命令pcolor()該命令主要用于繪制矩陣色圖，根據(jù)矩陣中元素數(shù)據(jù)的大小不同繪不同顏色。常常與命令shading interp結(jié)合使用效果會更好。在MATLAB命令窗口中鍵入help pcolor，可獲得英文幫助信息。2 例題3所用MATLAB程序及注釋：X=roots(1,0,0,-1); %利用MATLAB命令求三次方程的根r1=X(1);r2=X(2);r3=X(3);h=0.02;N=1+4/

13、h; %確定網(wǎng)格步長及網(wǎng)格點規(guī)模z0(N,N)=0;z1=z0;z2=z0;z3=z0; %定義四個大矩陣為全零矩陣t=(-2:h:2)+eps;x,y=meshgrid(t); %確定網(wǎng)格點坐標(biāo)z=x+y*i;for j=1:N for k=1:N p=z(j,k); %提取迭代初始點 for n=1:10 p=p-(p-1/p2)/3; %牛頓迭代操作 end if abs(p-r1)<0.01 z1(j,k)=1; %確定收斂到第一個根的初始點 elseif abs(p-r2)<0.01 z2(j,k)=1; %確定收斂到第二個根的初始點 elseif abs(p-r3)&l

14、t;0.01 z3(j,k)=1; %確定收斂到第三個根的初始點 else z0(j,k)=1; %確定不收斂的初始點 end endendZ=z0+2*z1+3*z2+4*z3;figure(1)pcolor(x,y,Z),shading interp %繪牛頓迭代法收斂域figure(2)pcolor(x,y,z0),shading interp %繪牛頓迭代法不收斂域課程設(shè)計實驗題目1牛頓迭代法解復(fù)方程z n + 1 = 0的收斂域問題。實驗?zāi)康模毫私釴ewton迭代法解復(fù)方程z n + 1 = 0(n3)時收斂域的結(jié)構(gòu)。實驗原理：Newton迭代法可以用于求解復(fù)數(shù)方程z n + 1 =

15、 0，例如對 z6 + 1 = 0，該方程在復(fù)平面上六個根分別是，選擇中心位于坐標(biāo)原點，邊長為4的正方形內(nèi)的任意點作初始值進(jìn)行迭代，將不收斂的初值點歸為第一類，再把收斂到六個根的初值歸為另外六類，分別以不同顏色做圖。對充分多的初始點進(jìn)行實驗，繪出牛頓迭代法對該方程的收斂域彩色圖。2牛頓迭代法計算隱函數(shù)值實驗實驗?zāi)康模毫私怆[函數(shù)存大定理與牛頓迭代法之間的聯(lián)系。實驗原理：隱函數(shù)存在定理敘述為：如果f(x，y)及皆在（x0，y0）附近連續(xù)，而且f(x0，y0) = 0，則在（x0，y0）的附近，方程f(x，y) = 0恰有一個連續(xù)解y =y(x)。隱函數(shù)存在定理具有局部性，這種局部性與牛頓迭代法的局

16、部收斂性有相通之處。在鄰域d(x0，y0) =d(x0)×d(y0)=(x，y) | |x x0| < d，|y y0| < d 內(nèi)計算隱函數(shù)的值。取x1d(x0)=x | |x x0| < d ，存在y1d(y0)=y | |y y0| < d ，使得y1 =y(x1)滿足f(x1，y1) = 0。由此導(dǎo)出關(guān)于函數(shù)值y的一元非線性方程g(y) = f(x1，y) = 0由于f(x，y)及皆在d(x0，y0)連續(xù)，故，且y1y0。應(yīng)用牛頓迭代法，得迭代計算格式y(tǒng) (k+1)= y (k) f(x1，y (k) )/fy(x1，y (k)迭代初值取為：y(0) = y0。由牛頓迭代法的局部收斂性可知，迭代計算可求得隱函數(shù)的高精度函數(shù)值。將這一過程進(jìn)行下去可計算出一系列的函數(shù)值并制做出函數(shù)表。例如對于二元多項式函數(shù)G(x，y) = 3x7 + 2y2 x3 + y 3，方程G(