第4章_方程求根的迭代法

1、數(shù)值計(jì)算方法數(shù)值計(jì)算方法（數(shù)值分析）（數(shù)值分析）第四章：第四章： 方程求根的迭代法方程求根的迭代法本章處理本章處理n二分法和牛頓法在第二節(jié)課已講過。二分法和牛頓法在第二節(jié)課已講過。n加深算法收斂性方面的理解。加深算法收斂性方面的理解。n介紹幾種新方法。介紹幾種新方法。引言 在科學(xué)研究和工程設(shè)計(jì)中在科學(xué)研究和工程設(shè)計(jì)中, 經(jīng)常會(huì)遇到的一大類經(jīng)常會(huì)遇到的一大類問題是非線性方程問題是非線性方程f(x)=0 的求根問題，其中的求根問題，其中f(x)為非線性函數(shù)。為非線性函數(shù)。方程方程f(x)=0的根的根, 亦稱為函數(shù)亦稱為函數(shù)f(x)的零點(diǎn)的零點(diǎn) 如果如果f(x)可以分解成可以分解成 ,其中其中m為正

2、整為正整數(shù)且數(shù)且 ,則稱則稱x*是是f(x)的的m重零點(diǎn)重零點(diǎn),或稱方程或稱方程f(x)=0的的m重根。當(dāng)重根。當(dāng)m=1時(shí)稱時(shí)稱x*為單根。若為單根。若f(x)存在存在m階導(dǎo)數(shù)階導(dǎo)數(shù),則是方程則是方程f(x)的的m重根重根(m1) 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng))()()(*xgxxxfm0)(*xg0)(,0)()()(*)(*)1(*xfxfxfxfmm記筆記記筆記 當(dāng)當(dāng)f(x)不是不是x的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程為非的線性函數(shù)時(shí)，稱對(duì)應(yīng)的函數(shù)方程為非線性方程。如果線性方程。如果f(x)是多項(xiàng)式函數(shù)，則稱為是多項(xiàng)式函數(shù)，則稱為代數(shù)方程代數(shù)方程，否則稱為，否則稱為超越方程超越方程（三角方程，指數(shù)、對(duì)數(shù)

3、方程等（三角方程，指數(shù)、對(duì)數(shù)方程等）。一般稱）。一般稱n次多項(xiàng)式構(gòu)成的方程次多項(xiàng)式構(gòu)成的方程 )0(00111nnnnnaaxaxaxa為為n次代數(shù)方程次代數(shù)方程,當(dāng)當(dāng)n1時(shí)時(shí),方程顯然是非線性的方程顯然是非線性的 一般稍微復(fù)雜的一般稍微復(fù)雜的3次以上的代數(shù)方程或超越方程次以上的代數(shù)方程或超越方程,很很難甚至無法求得精確解。本章將介紹常用的求解非難甚至無法求得精確解。本章將介紹常用的求解非線性方程的近似根的幾種數(shù)值解法線性方程的近似根的幾種數(shù)值解法 數(shù)值解法步驟二分法（略）n復(fù)習(xí)作業(yè)題不動(dòng)點(diǎn)迭代不動(dòng)點(diǎn)迭代 對(duì)于一般的非線性方程對(duì)于一般的非線性方程, ,沒有通常所說的求根沒有通常所說的求根公式求

4、其精確解公式求其精確解, ,需要設(shè)計(jì)近似求解方法需要設(shè)計(jì)近似求解方法, ,即即迭代法迭代法。它是一種逐次逼近的方法。它是一種逐次逼近的方法, ,用某個(gè)用某個(gè)固定公式反復(fù)校固定公式反復(fù)校正正根的近似值根的近似值, ,使之逐步精確化，最后得到滿足精度使之逐步精確化，最后得到滿足精度要求的結(jié)果。要求的結(jié)果。迭代法的迭代法的基本思想基本思想 為求解非線性方程為求解非線性方程f(x)=0f(x)=0的根，先將其寫成便的根，先將其寫成便于迭代的等價(jià)方程于迭代的等價(jià)方程 其中其中 為為x x的連續(xù)函數(shù)的連續(xù)函數(shù))(x)(xx即如果數(shù)即如果數(shù) 使使f(x)=0, 則也有則也有 , 反之反之, 若若 , 則也有

5、則也有 , 稱稱 為迭代函數(shù)為迭代函數(shù) 任取任取一個(gè)初值一個(gè)初值 , 代入式代入式 的右端的右端, 得到得到 *x)(*xx)(*xx0)(*xf)(x0 x)(xx)(01xx再將再將 代入式代入式 的右端的右端, 得到得到 ,依此依此類推類推, 得到一個(gè)數(shù)列得到一個(gè)數(shù)列 ， 其一般表示其一般表示 1x)(xx)(12xx)(23xx), 2 , 1 , 0()(1kxxkk稱為求解非線性方程的簡單迭代法。稱為求解非線性方程的簡單迭代法。 如果由迭代格式如果由迭代格式 產(chǎn)生的序列產(chǎn)生的序列 收斂收斂,即即 nx)(1kkxx*limxxnn則稱則稱迭代法收斂迭代法收斂。 實(shí)際計(jì)算中實(shí)際計(jì)算中

6、當(dāng)然不可能也沒必要無窮多步地做下當(dāng)然不可能也沒必要無窮多步地做下去去, 對(duì)預(yù)先給定的精度要求對(duì)預(yù)先給定的精度要求，只要某個(gè)只要某個(gè)k滿足滿足1kkxx即可結(jié)束計(jì)算并取即可結(jié)束計(jì)算并取 kxx* 當(dāng)然，迭代函數(shù)當(dāng)然，迭代函數(shù) 的構(gòu)造方法是多種多樣的。的構(gòu)造方法是多種多樣的。)( x例例1 用迭代法求方程用迭代法求方程 在在x=1.5附近的一個(gè)根附近的一個(gè)根解解 將方程改寫成如下兩種等價(jià)形式將方程改寫成如下兩種等價(jià)形式 013 xx1)(1)(3231xxxxxx相應(yīng)地可得到兩個(gè)迭代公式相應(yīng)地可得到兩個(gè)迭代公式1)(1)(321311kkkkkkxxxxxx如果取初始值如果取初始值 1.51.5，

7、用上述兩個(gè)迭代公，用上述兩個(gè)迭代公式分別迭代，計(jì)算結(jié)果式分別迭代，計(jì)算結(jié)果0 x30111.51,(0,1,2,). kkxxxk（），kxk012345671.51.357211.330861.325881.324941.324761.324731.32472. ,39.12,375. 2 , 5 . 1, 1 (2) 21031xxxxxkk幾何意義 通常將方程通常將方程f(x)=0化為與它同解的方程化為與它同解的方程的方法不止一種的方法不止一種,有的收斂有的收斂,有的不收斂有的不收斂,這取決于這取決于 的性態(tài)的性態(tài),方程方程 的求根問題在幾何上就是確定曲的求根問題在幾何上就是確定曲線線y

8、= 與直線與直線y=x的交點(diǎn)的交點(diǎn)P*的橫坐標(biāo)的橫坐標(biāo))(xx)(x)(xx)(x y=x y y=)(x y=x 1)(0*x 0)(1*x P0 P2P* Q1 Q2 x1 x0 x2 x* x y x0 x x1 x2 x3 x* y=)(x)(x P* P1 (a)(b)幾何意義 y=x y y=x y=)(x 1)(* x 1)(* x （c） （d） P* x1 x0 x y x0 x x1 x2 x3 x* y=)(x)(x x* x2 P* 對(duì)方程對(duì)方程f(x)=0可以構(gòu)造不同的迭代公式可以構(gòu)造不同的迭代公式, 但迭代但迭代公式公式并非總是收斂。那么并非總是收斂。那么,當(dāng)?shù)?/p>

9、數(shù)當(dāng)?shù)瘮?shù) 滿足什么條件滿足什么條件時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時(shí)，時(shí)，相應(yīng)的迭代公式才收斂呢？即使迭代收斂時(shí)，我們也我們也不可能迭代很多次，而是迭代有限次后就停不可能迭代很多次，而是迭代有限次后就停止止，這就需要估計(jì)迭代值的誤差，以便適時(shí)終止迭，這就需要估計(jì)迭代值的誤差，以便適時(shí)終止迭代代 。),2, 1 ,0()(1kxxkk)(x不動(dòng)點(diǎn)迭代收斂性定理定理1 ，2 設(shè)函數(shù)設(shè)函數(shù) 在在a,b上具有連續(xù)的一階導(dǎo)上具有連續(xù)的一階導(dǎo) 數(shù)數(shù), 且滿足且滿足 （1）對(duì)所有的）對(duì)所有的xa,b 有有 a,b （2）存在存在 0 L 1 ,使所有的使所有的xa,b有有 L則方程則方程 在在a

10、,b上的解上的解 存在且唯一存在且唯一，對(duì)任意的，對(duì)任意的 a ,b ，迭代過程迭代過程均收斂于均收斂于 。并有誤差估計(jì)式。并有誤差估計(jì)式 )(x)(x)(x)(xx*x0 x)(1kkxx*x1*1kkkxxLLxx01*1xxLLxxkk 由連續(xù)函數(shù)介值定理知由連續(xù)函數(shù)介值定理知, 必有必有 a, b, 使使 所以有解存在所以有解存在, 即即假設(shè)有兩個(gè)解假設(shè)有兩個(gè)解 和和 , , a, b，則則 ，由微分中值定理有由微分中值定理有其中其中是介于是介于x*和和 之間的點(diǎn)之間的點(diǎn) 從而有從而有a,b，進(jìn)而進(jìn)而有有 由條件由條件(2)有有 1, 所以所以 - =0，即，即 = ，解唯一。，解唯一

11、。證證: 構(gòu)造函數(shù)構(gòu)造函數(shù) ,由條件（由條件（1）對(duì)任意的）對(duì)任意的xa, b a, b有有xxx)()(0)()(0)()(bbbaaa)(x*x0)()(*xxx*xx*xx)(*xx)(xx)()()(*xxxxxxx0)(1)(*xx)(x*xx*xx按迭代過程按迭代過程 , ,有有 )(1kkxx)()()(1*1*kkkxxxxxx1*1*)(kkkxxLxxxx0*2*21*xxLxxLxxLxxkkkk 由于由于L1,L0），使 )(1kkxx)(xx*xkkxxe*ceepkkk1lim則稱序列 是 p 階收斂的,c稱漸近誤差常數(shù)。特別地,p=1時(shí)稱為線性收斂,p=2時(shí)稱為平

12、方收斂。1 p 0 xn+1X*ayx0Bf(x)0a=x0yx0B=x0f(x)0ayx0Bf(x)0a =x0yx10 x0X*0 x0X*x2 不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離不滿足迭代條件時(shí)，可能導(dǎo)致迭代值遠(yuǎn)離根的情況而找不到根或死循環(huán)的情況根的情況而找不到根或死循環(huán)的情況例例 8 用用求求 x=e-x的根的根,=10-4nxnnnxxnnnxexxxeexxxnnn 1)1 (11取取x0=0.5,逐次計(jì)算得逐次計(jì)算得 x1=0.57102, x2=0.56716， x3=0.56714解：因解：因 f (xk)= x ex 1 , f (x)=ex ( x+1)建立迭代公式建立

13、迭代公式 牛頓下山法牛頓下山法 通常通常, ,牛頓迭代法的收斂性依賴于初始值牛頓迭代法的收斂性依賴于初始值 的選取的選取, ,如果如果 偏離所求的根偏離所求的根 比較遠(yuǎn)比較遠(yuǎn), ,則則牛頓法可能發(fā)散牛頓法可能發(fā)散。為了防止迭代發(fā)散。為了防止迭代發(fā)散, ,我們對(duì)牛頓迭代法的迭代過程再我們對(duì)牛頓迭代法的迭代過程再附加一項(xiàng)要求附加一項(xiàng)要求, ,即具有即具有單調(diào)性單調(diào)性 0 x0 x*x)()(1kkxfxf 將牛頓迭代法與下山法結(jié)合起來使用將牛頓迭代法與下山法結(jié)合起來使用, ,即在下山即在下山法保證函數(shù)值下降的前提下法保證函數(shù)值下降的前提下, ,用牛頓迭代法加快收斂用牛頓迭代法加快收斂速度。把這一算

14、法稱為牛頓下山法。即速度。把這一算法稱為牛頓下山法。即滿足這項(xiàng)要求的算法稱下山法。滿足這項(xiàng)要求的算法稱下山法。)()(1kkkkxfxfxx其中其中(01)(01)為下山因子為下山因子 下山因子的選擇是個(gè)逐步探索的過程，設(shè)下山因子的選擇是個(gè)逐步探索的過程，設(shè)從從=1=1開始反復(fù)將開始反復(fù)將減半進(jìn)行試算減半進(jìn)行試算, , 即逐次取即逐次取為為從中挑選下山因子，直至找到其中某個(gè)從中挑選下山因子，直至找到其中某個(gè)使單調(diào)性使單調(diào)性條件條件成立，則稱成立，則稱“下山成功下山成功”，否則，否則“下山失敗下山失敗”，這時(shí)需另選初值重算。這時(shí)需另選初值重算。,21,21,12)()(1kkxfxf重根情形重根

15、情形. ,)()( )(*)()(,1仍平方收斂可將迭代法改為，牛頓法不是平方收斂重根情形kkkkmxfxfmxxxgxxxfm.0)(*,)(*)()()(*)()( )(*)(/ )()(的單根是故重根，則的是，若還可令xxxgxxxmgxgxxxmxfxxfxfx.(4.14) ,)()()()()( )(21仍平方收斂用牛頓法得對(duì)kkkkkkkxfxfxfxfxfxxx 42 440*2.xxx用上述三種方法求的二重根例例 ；）牛頓法：（kkkkxxxx42 121解解；）（kkkkxxxx22 )13. 4( 221.2)2( (4.14) 3221kkkkkxxxxx）（計(jì)算結(jié)果如

16、下： kxk(1)(2)(3)0123x0 x1x2x31.51.4583333331.4366071431.4254976191.51.4166666671.4142156861.4142135621.51.4117647061.4142114381.414213562 牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但每迭牛頓迭代法雖然具有收斂速度快的優(yōu)點(diǎn)，但每迭代一次都要計(jì)算代一次都要計(jì)算導(dǎo)數(shù)導(dǎo)數(shù) , 當(dāng)當(dāng) 比較復(fù)雜時(shí)比較復(fù)雜時(shí), 不僅不僅每次計(jì)算每次計(jì)算 帶來很多不便，而且還可能十分麻煩帶來很多不便，而且還可能十分麻煩，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只有線性收，如果用不計(jì)算導(dǎo)數(shù)的迭代方法，往往只

17、有線性收斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)斂的速度。本節(jié)介紹的弦截法便是一種不必進(jìn)行導(dǎo)數(shù)運(yùn)算的求根方法。弦截法在迭代過程中不僅用到數(shù)運(yùn)算的求根方法。弦截法在迭代過程中不僅用到前一步前一步 處的函數(shù)值，而且還使用處的函數(shù)值，而且還使用 處的函數(shù)處的函數(shù)值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度值來構(gòu)造迭代函數(shù)，這樣做能提高迭代的收斂速度。)(kxf )(xf)(kxfkx1kx弦截法 弦截法的基本思想弦截法的基本思想 為避免計(jì)算函數(shù)的導(dǎo)數(shù)為避免計(jì)算函數(shù)的導(dǎo)數(shù) ，使用，使用差商差商 替代牛頓公式中的導(dǎo)數(shù)替代牛頓公式中的導(dǎo)數(shù) , ,便得到便得到迭代公式迭代公式 稱為弦截迭代公式，稱為弦截

18、迭代公式， 相應(yīng)的迭代法稱為弦截法相應(yīng)的迭代法稱為弦截法。)()()(11kkkkxxxfxf)(kxf )()()()(111kkkkkkkxxxfxfxfxx),2, 1(k)(kxf 弦截法幾何意義弦截法幾何意義弦截法也稱割線法弦截法也稱割線法,其幾何意義是用過曲線上兩點(diǎn)其幾何意義是用過曲線上兩點(diǎn) 、 的割線來代替曲線的割線來代替曲線,用割線與用割線與x軸軸交點(diǎn)的橫座標(biāo)作為方程的近似根交點(diǎn)的橫座標(biāo)作為方程的近似根 再過再過P1點(diǎn)和點(diǎn)點(diǎn)和點(diǎn) 作割線求出作割線求出 ,再過再過P2點(diǎn)和點(diǎn)點(diǎn)和點(diǎn) 作割線求出作割線求出 ,余此類余此類推，當(dāng)收斂時(shí)可求出推，當(dāng)收斂時(shí)可求出滿足精度要求的滿足精度要求的

19、 P1 y=f(x) x0 x2 x3 x1 x* P3 P0 P2 )(,(000 xfxP)(,(111xfxP2x)(,(222xfxP3x)(,(333xfxP4xkx 可以證明，弦截法具有超線性收斂，收斂可以證明，弦截法具有超線性收斂，收斂的階約為的階約為1.6181.618，它與前面介紹的一般迭代法一，它與前面介紹的一般迭代法一樣都是線性化方法，但也有區(qū)別。即一般迭代樣都是線性化方法，但也有區(qū)別。即一般迭代法在計(jì)算法在計(jì)算 時(shí)只用到前一步的值時(shí)只用到前一步的值 ，故稱之，故稱之為為單點(diǎn)迭代法單點(diǎn)迭代法；而弦截法在求；而弦截法在求 時(shí)要用到前兩時(shí)要用到前兩步的結(jié)果步的結(jié)果 和和 ，使

20、用這種方法必須給出兩，使用這種方法必須給出兩個(gè)初始近似根個(gè)初始近似根 ，這種方法稱為，這種方法稱為多點(diǎn)迭代多點(diǎn)迭代法。法。 1kxkx1kx1kxkx10,xx例例 9 9 用弦截法求方程用弦截法求方程 在在 初始初始 值鄰近的一個(gè)根。要求值鄰近的一個(gè)根。要求解：取解：取 , , , , 令令 利用弦截迭代公式利用弦截迭代公式 計(jì)算結(jié)果，計(jì)算結(jié)果， 易見取近似根易見取近似根 則可滿足精度要求。則可滿足精度要求。xex5 . 00 x0001. 01kkxx5 . 00 x6.01xxexxf)()()()()(1111kkxxkkxkkkxxeexxexxxkkk56714. 04x 弦截法算

21、法實(shí)現(xiàn)弦截法算法實(shí)現(xiàn) ?0)(0 xf ?0)(1xf ?0)()(01xfxf 2010111)()()()(xxxxfxfxfx ?12 xx 輸 入 x0, x1,N 1 k k+ 1 k x1 x0 x2 x1 f(x1)f(x0) f(x2) f(x1) 輸 出 x2 輸 出 迭 代 失 敗 標(biāo) 志 結(jié) 束 n k N ? n n y 輸 出 奇 異 標(biāo) 志 y y x0 x2 x1 x2 n y y n 輸 出 x2 )(, )(,)( )( ,1211221kkkkkkkkkkkkxxxxxxxfxxxxfxfxpxxx，得到插值函數(shù)為插值節(jié)點(diǎn)和以).(,)(4)(2 0)(12

22、112112kkkkkkkkkkkkkkxxxxxfxxfxxxfxfxfxxxp式中，得到兩個(gè)零點(diǎn)：令.,)(4)sgn()(2 211kkkkkkkxxxfxfxfxx.*840. 1xp收斂到拋物線法按階 拋物線法拋物線法 解非線性方程組的解非線性方程組的迭代法迭代法 . 0),(, 0),(, 0),( 21212211nnnnxxxfxxxfxxxf考慮非線性方程組 .)( OXF利用向量記號(hào)寫為. ,*)( ,* .)(為非線性方程組的解則稱使得若存在上向量值函數(shù)是定義在某區(qū)域這里*DRDnXOXFXXF).( XGX 考慮等價(jià)的方程組., ,)()( ),1 , 0( ,: 00壓縮映射壓縮映射定義1定義1上是在則稱使得設(shè)DGDDLL RRDnnYXXYXGYGG00000 7 : (1) (2) , ( ), ,*( *).nnDRRDDDDDGGGG XXGXG X（壓縮映象原理） 設(shè)，且在上是壓縮的，把映入自身 即則 在中有唯一的不動(dòng)點(diǎn)定定理理(0)( ) 8 :* *, ( *