數(shù)值分析論文(14).doc

Newton迭代法及其應(yīng)用摘要：本文研究應(yīng)用泰勒展開(kāi)式構(gòu)造出Newton迭代法，論證了它的局部收斂性和收斂階。分別討論了單根情形和重根情形，給出了實(shí)例應(yīng)用。最后給出了離散Newton法(割線法) 的具體做法。關(guān)鍵詞：泰勒展開(kāi)式，Newton迭代法及其收斂性，重根，離散Newton法(割線法)。Newton迭代法 1.Newton法及其收斂性求方程f（x）=0的根，如果已知它的一個(gè)近似,可利用Taylor展開(kāi)式求出f(x)在附近的線性近似，即，在x與之間忽略余項(xiàng)，則得方程的近似右端為x的線性方程，若，則解,記作,它可作為的解的新近似，即(2.4.1)稱為解方程的Newton法.在幾何上求方程的解，即求曲線y=f(x)與x軸交點(diǎn).若已知的一個(gè)近似,通過(guò)點(diǎn)(，f()作曲線y=f(x)的切線，它與x軸交點(diǎn)為,作為的新近似，如圖1所示關(guān)于Newton法收斂性有以下的局部收斂定理.定理1 設(shè)是f(x)=0的一個(gè)根，f(x)在附近二階導(dǎo)數(shù)連續(xù)，且，則Newton法(2.4.1)具有二階收斂，且 (2.4.2) 證明 由式(2.4.1)知迭代函數(shù),，,而，由定理可知，Newton迭代(2.4.1)具有二階收斂，由式可得到式(2.4.2).證畢.定理表明Newton法收斂很快，但在附近時(shí)才能保證迭代序列收斂.有關(guān)Newton法半局部收斂性與全局收斂定理.此處不再討論.例1用Newton法求方程的根.解,Newton迭代為 取即為根的近似，它表明Newton法收斂很快.例2設(shè)0，求平方根的過(guò)程可化為解方程.若用Newton法求解，由式(2.4.1)得(2.4.3)這是在計(jì)算機(jī)上作開(kāi)方運(yùn)算的一個(gè)實(shí)際有效的方法，它每步迭代只做一次除法和一次加法再做一次移位即可，計(jì)算量少，又收斂很快，對(duì)Newton法我們已證明了它的局部收斂性，對(duì)式(2.4.3)可證明對(duì)任何迭代法都是收斂的，因?yàn)楫?dāng)時(shí)有即,而對(duì)任意，也可驗(yàn)證,即從k=1開(kāi)始，且 所以從k=1起是一個(gè)單調(diào)遞減有下界的序列，有極限.在式(2.4.3)中令k可得，這就說(shuō)明了只要，迭代(2.4.3)總收斂到,且是二階收斂.在例2.4的迭代法(3)中，用式(2.4.3)求只迭代3次就得到=1.732 051,具有7位有效數(shù)字. 求非線性方程f(x)=0的根x*,幾何上就是求曲線y=f(x)與x軸交點(diǎn)x*，若已知曲線上一點(diǎn)過(guò)此點(diǎn)作它的切線。方程為此切線與x軸交點(diǎn)記作，它就是(2,4,1)給出的Newtor迭代法，由圖2-3看到Newton法求根就是用切線近似曲線，切線與x軸交點(diǎn)xk+1作為方程f(x)=0根x*的新近似。根據(jù)定理2.3可以證明Newton法是二階收斂的，這就是定理4.1給出的結(jié)果，Newton法由于收斂快，它是方程求根最常用和最重要的方法，在計(jì)算機(jī)上用Newton法解方程的計(jì)算步驟：算法如下：（Newton法）步0：給初始近似,計(jì)算精度 最大迭代步數(shù)N,0k.步1：計(jì)算f(x)f,若 ，轉(zhuǎn)步4，否則做步2：計(jì)算 ，若y=0,轉(zhuǎn)步4，否則步3：若，步4，否則，若，轉(zhuǎn)步4，否則轉(zhuǎn)步1步4：打印x,f,y,k計(jì)算停止。此算法給出了4個(gè)停止準(zhǔn)則，保證計(jì)算在有限步結(jié)束，其中y=0及均屬非正常結(jié)束，說(shuō)明用Newton法求根得不到結(jié)果，步2中y=0實(shí)際使用時(shí)可改為（可?。?。計(jì)算例子見(jiàn)例2.6及例2.7，例2.7得到的計(jì)算的Newton法程序（2.4.3）是計(jì)算機(jī)中計(jì)算開(kāi)方的最有效算法，它對(duì)任意初值都能使序列收斂于，且為平方收斂，一般只要迭代35次就可達(dá)到79位有效數(shù)字，因此計(jì)算量很省。2.重根情形當(dāng),則為方程(2.1.1)的重根，此時(shí),Newton法的迭代函數(shù),，故Newton法仍收斂，但只是線性收斂.若迭代函數(shù)改為，則，故迭代法(2.4.5)具有二階收斂.對(duì)重根還可構(gòu)造另一種迭代法，令若是的m重根，則所以是的單根，對(duì)它用Newton法，迭代函數(shù)為 從而可構(gòu)造迭代法(2.4.6) 它也是二階收斂的.例3方程的根是二重根，試用Newton法及(2.4.5)、(2.4.6)三種迭代法各計(jì)算3步.解 方法(1)：Newton迭代，方法(2)：迭代法(2.4.5)，方法(3)：迭代法(2.4.6)，三種方法均取=1.5計(jì)算結(jié)果如下： 方法（1）方法（2）方法（3）1.458 333 3331.436 607 1431.425 497 619 1.416 666 6671.414 215 686 1.414 213 562 1.411 764 7061.414 211 4381.414 213 562 方法(2)與方法(3)均達(dá)到精確度，而方法(1)只有線性收斂，要達(dá)到相同精度需迭代30次。當(dāng)x*是f(x)=0的重根時(shí)，用Newton法計(jì)算，只有線性收斂，如果已知x*是m重根則使用迭代法（2.4.5），否則可使用（2.4.6），見(jiàn)例43.離散Newton法(割線法)求解方程的Newton法(2.4.1)要計(jì)算,如果導(dǎo)數(shù)計(jì)算不方便，通?？捎糜?jì)算函數(shù)差商近似，即 將它代入式(2.4.1)則得離散Newton法：(2.4.7)這種迭代法與式(2.2.2)不同，它要給出兩個(gè)初始近似，才能逐次計(jì)算出.因此稱為多點(diǎn)(兩點(diǎn))迭代，迭代(2.4.7)稱為割線法，其幾何意義是，用曲線上兩點(diǎn)的割線與x軸交點(diǎn)作為=0根的新近似，即的根x，記作，它就是方程(2.1.1)根的新近似，如圖2所示.圖2由于割線法與單點(diǎn)迭代法(2.2.2)不同，其收斂性要復(fù)雜一些.但可以證明割線法(2.4.7)是超線性收斂的，且收斂階,故割線法收斂也是很快的.用Newton法時(shí)，若f(x)不好計(jì)算，可改用離散Newton法（2.4.7），它也稱為弦截法或割線法，它的幾何意義是用兩點(diǎn)與的連線近似曲線，以直線方程的根近似的根x*，得到的迭代公式（2.4.7）與前面討論的迭代法不同，必須給出兩個(gè)初始近似才能逐次計(jì)算出這種迭代法稱為兩點(diǎn)迭代，它具有超線性收斂，其收斂階p=1.618例4割線法求方程的根，設(shè)取由（2.4.7）計(jì)算結(jié)果為與例2.6用Newton法計(jì)算3步得到的結(jié)果相當(dāng)，說(shuō)明此方法收斂也是很快的小結(jié)1用迭代法求方程f(x)=0的根，首先要能正確使用二分法，不動(dòng)點(diǎn)迭代法和Newton法求出方程的根，并避免計(jì)算錯(cuò)誤。作為迭代法選取合適的初始近似或有根區(qū)間是很重要的。二分法既是求方程實(shí)根x*的一種簡(jiǎn)單迭代法，又是求方程一個(gè)足夠好近似根的有效算法。當(dāng)為有限區(qū)間，每次二分迭代可使有根區(qū)間縮減一半且n次迭代Xn的誤差因收斂較慢，故它常作為提供迭代法初值的算法。2.重點(diǎn)是構(gòu)造收斂的迭代法及牛頓法，首先必須掌握判斷不動(dòng)點(diǎn)迭代法收斂性的條件，只有收斂的迭代法才能用于球方程的根。判斷收斂性要分清是在區(qū)間，上整體收斂還是已知方程的根x，只證明它的局部收斂性。對(duì)于前者主要根據(jù)收斂定理，證明，且在上 ，則xk收斂于根x*。對(duì)于局部收斂性只需用定理證明 即可。3.對(duì)收斂的迭代序列xk，還要知道收斂快慢，首先要掌握收斂的定義，并能熟練應(yīng)用定理，確定或證明迭代序列xk的收斂階p，其中計(jì)算 往往要用Hopital 法則求極限。P越大則xk收斂越快，在p=1則由判斷收斂快慢，a越小則序列收斂越快。4對(duì)收斂慢或不收斂的迭代序列要通過(guò)Steffensen迭代法，加速其收斂。5Newton迭代法是求方程f(x)=0最重要的迭代法。（1）用牛頓法求根公式求方程的根，要了解用此方法必須，且方法是局部收斂，一般要求初始近似x0與跟x*靠近，如x0選擇不合適，可用Newton下山法求根。（2）Newton迭代法是2階收斂的，當(dāng)x0選擇合適時(shí)計(jì)算幾步即可達(dá)到精度要求，對(duì)Newton迭代由可以證明具體迭代序列的收斂性。（3）重根情形下，f（x*）=0，但f （xk） 0仍然可用Newton法求根，但它只是線性收斂，為提高收斂速度應(yīng)使用具有2階收斂的迭代法（2.4.5）及（2.4.6）求重根。例如：設(shè)a0，x0，證明迭代公式xk+1=xk(x2k+3a)/(3x2k+a)是計(jì)算 的3階方法，并求這題目主要用到收斂階的概念，它可以直接利用定義，也可以利用定理的結(jié)論證明。下面先證明迭代序列的收斂性。證明：顯然，當(dāng)a0，x0時(shí)，x0(k=1，2。)令則對(duì)，即迭代收斂，設(shè)xk的極限是a，則有a=a(a+3a)/(3a+a),解得a=0,a=,取，下面只要求故迭代序列是3階收斂的上面是由定義直接得到的結(jié)果，如用定理由于1用迭代法求方程f(x)=0的根，首先要能正確使用二分法，不動(dòng)點(diǎn)迭代法和Newton法求出方程的根，并避免計(jì)算錯(cuò)誤。作為迭代法選取合適的初始近似或有根區(qū)間是很重要的。二分法既是求方程實(shí)根x*的一種簡(jiǎn)單迭代法，又是求方程一個(gè)足夠好近似根的有效算法。當(dāng)為有限區(qū)間，每次二分迭代可使有根區(qū)間縮減一半且n次迭代Xn的誤差因收斂較慢，故它常作為提供迭代法初值的算法。2.重點(diǎn)是構(gòu)造收斂的迭代法及牛頓法，首先必須掌握判斷不動(dòng)點(diǎn)迭代法收斂性的條件，只有收斂的迭代法才能用于球方程的根。判斷收斂性要分清是在區(qū)間，上整體收斂還是已知方程的根x，只證明它的局部收斂性。對(duì)于前者主要根據(jù)收斂定理，證明，且在上 ，則xk收斂于根x*。對(duì)于局部收斂性只需用定理證明 即可。3.對(duì)收斂的迭代序列xk，還要知道收斂快慢，首先要掌握收斂的定義，并能熟練應(yīng)用定理，確定或證明迭代序列xk的收斂階p，其中計(jì)算 往往要用Hopital 法則求極限。P越大則xk收斂越快，在p=1則由判斷收斂快慢，a越小則序列收斂越快。4對(duì)收斂慢或不收斂的迭代序列要通過(guò)Steffensen迭代法，加速其收斂。5Newton迭代法是求方程f(x)=0最重要的迭代法。（1）用牛頓法求根公式求方程的根，要了解用此方法必須，且方法是局部收斂，一般要求初始近似x0與跟x*靠近，如x0選擇不合適，可用Newton下山法求根。（2）Newton迭代法是2階收斂的，當(dāng)x0選擇合適時(shí)計(jì)算幾步即可達(dá)到精度要求，對(duì)Newton迭代由可以證明具體迭代序列的收斂性。（3）重根情形下，f（x*）=0，但f （xk） 0仍然可用Newton法求根，但它只是線性收斂，為提高收斂速度應(yīng)使用具有2階收斂的迭代法（2.4.5）及（2.4.6）求重根。例如：設(shè)a0，x0，證明迭代公式xk+1=xk(x2k+3a)/(3x2k+a)是計(jì)算 的3階方法，并求這題目主要用到收斂階的概念，它可以直接利用定義，也可以利用定理的結(jié)論證明。下面先證明迭代序列的收斂性。證明：顯然，當(dāng)a0，x0時(shí)，x0(k=1，2。)令則對(duì)，即迭代收斂，設(shè)xk的極限是a，則有a=a(a+3a)/(3a+a),解得a=0,a=,取，下面只要求故迭代序列是3階收斂的上面是由定義直接得到的結(jié)果，如用定理由于由定理可知迭代序列是3階收斂的。且這與前面直接用定義證明是一致的。又如證明求的Newton迭代法對(duì)且xk是單調(diào)遞減序列證明： 因，故xk 0(k=1,2)對(duì)即對(duì)一切k1，xk，從而故xk+1xk 即x是單調(diào)遞減序列，它是整體收斂的。參考文獻(xiàn)： 1陳紀(jì)修 ,於崇華 ,金路 .數(shù)學(xué)分析 (上冊(cè) )M.北京 :高等教育出版社 ,2004:193-194. 2施吉林 ,劉淑珍 ,陳桂芝