1、17.1 7.1 方程求根與二分法方程求根與二分法設非線性方程為設非線性方程為 f (x)=0 (7-1) 方程方程(2-1)的解的解 稱為稱為方程的根方程的根或或函數函數 f (x)的零點。的零點。 x )()(xgxxxfm 其中其中m為大于為大于1 1的整數的整數, ,且且g(x) 0,稱稱 為方程為方程(7-1)的的m重根重根, ,或或函數函數 f (x) 的的m重零點重零點. . x若若 f (x) 為為n 次多項式次多項式, ,則稱則稱 f (x)=0為為n 次代數方程次代數方程 . 若若 f (x) 為超越函數為超越函數, ,則稱則稱f (x)=0 為為超越方程超越方程 。 若若

2、 f (x) 可表示為可表示為第第7章章 非線性方程求根非線性方程求根2一、求有根區間的一般方法一、求有根區間的一般方法若若 f(x) 滿足條件滿足條件: (1) 在在a,b內連續內連續, , (2) f(a) f(b)0, f (0)=10, f (3)=- -260f (x) 在此三區間的符號分別為在此三區間的符號分別為“- -”、“- - ”、“+”由由 f (x)= 4 x2(x- -3)=0 得駐點得駐點 x1=0, x2=3。6以上分析可用下表表示以上分析可用下表表示x(-,0)0 (0,3) 3 (3,4) 4(4,+) f (x) f (x) - - 0 + - - 0 - -

3、+ + 隔根區間隔根區間(0,3)(3,4)可見可見 f (x) 僅有兩個實根僅有兩個實根, , 分別位于分別位于(0, 3) , (3,+), 又又 f (4)=10, 所以第二根的隔根區間可縮小為所以第二根的隔根區間可縮小為 (3,4)。72. 逐步搜索法逐步搜索法 (增值尋根法增值尋根法)搜索過程搜索過程, ,可從可從a 開始開始, ,也可從也可從 b 開始開始,這時應取步長這時應取步長 h 0。 增值尋根法的基本思想是增值尋根法的基本思想是: 從初值從初值 開始開始, 按規按規定的一個初始步長定的一個初始步長h 來增值。來增值。 同時計算同時計算 . 可能遇到三可能遇到三種情形：種情形

4、：0 x1(0,1,2,)nnxxhn )(1 nxf1(3)()()0nnf xf x ，0)()1(1 nxf此時此時 即為方程的根即為方程的根1 nx。 x1(2)()()0nnf xf x 說明區間說明區間 內無根內無根 ,1 nnxx說明區間說明區間 內有根內有根 ,1 nnxx8圖圖2-1圖圖2-29三、三、 二分法二分法設設方程方程f(x)=0 在區間在區間a,b 內有且只有一個實根內有且只有一個實根x* 。即即 f(x) 滿足條件滿足條件: (1) 在在a,b內連續內連續, , (2) f(a) f(b)0 , (3) f(x) 在在a,b內嚴格單調。內嚴格單調。10 二分法的

5、步驟：二分法的步驟：(2)若若 則則 令令 a2= a , b2=x1 ;1( )()0 ,f af x1( ,),xa x (3)若若 則則 , 令令 a2= x1 , b2=b。 1()( )0 ,f xf b1(, )xx b 11(),2xab記記a, b = a1, b1, 中點中點 計算計算f(x1),(1)若若 f ( x1 ) = 0, 則則 x1 就是方程的根就是方程的根x*,計算結束計算結束 ;對壓縮了的有根區間對壓縮了的有根區間 a2, b2, , 實行同樣的步驟實行同樣的步驟. .若每次二分時所取區間中點都不是根，則上述過程若每次二分時所取區間中點都不是根，則上述過程將

6、無限進行下去。將無限進行下去。111122,nna ba ba b 如此反復進行如此反復進行, , 可得一系列有根區間套可得一系列有根區間套由于每一區間都是前一區間的一半，因此區間由于每一區間都是前一區間的一半，因此區間 an , bn 的長度為的長度為11()2nnnbaba 當當 n 時時, 區間必將最終收縮為一點區間必將最終收縮為一點x*, 顯然顯然x* 就就是所求的根是所求的根。12)(nnnbax 21只要只要n 足夠大足夠大, 即區間二分次數足夠多即區間二分次數足夠多, 誤差就可足誤差就可足夠小。夠小。),(,11 nnnbaxx若取區間若取區間 的中點的中點,nnba作為作為 的

7、近似值，則有下述誤差估計式的近似值，則有下述誤差估計式 x11()()22nnnnxxbaba 13 由于在偶重根附近曲線由于在偶重根附近曲線 y=f(x) 為上凹或下凸為上凹或下凸, ,即即 f(a) 與與 f(b) 的符號相同的符號相同, ,因此不能用二分法求偶重根因此不能用二分法求偶重根. .005. 0 nxx解解 可知可知 要想滿足題意，即要想滿足題意，即：)5 . 1 , 1 ( x例例 2 用二分法求方程用二分法求方程 f(x)=x3-x-1=0在在 上的上的實實根根, ,要求誤差不超過要求誤差不超過0.005。)5 . 1 , 1(14為所求之近似根。即為所求之近似根。即 x*

8、 1.3242 (1) f (a)0 (2) 根據精根據精 度要求度要求, 取到小數取到小數 點后四位點后四位 即可即可.- + - + + - -1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.32421.5 1.5 1.375 1.375 1.3438 1.3281 1.32811.0 1.25 1.25 1.3125 1.3125 1.3125 1.32031 2 3 4 5 6 7 annnbnx)(nxf15例例 3用二分法求用二分法求 在在 內的一個實根，且要求滿足精度內的一個實根，且要求滿足精度0104)(23 xxxf2 , 131021 nx

9、x解解用二分法計算結果如表用二分法計算結果如表2-1：160.0000721.3647460941.36718751.363281259-0.032151.3642578131.36718751.35937580.032361.363281251.3751.3593757-0.096411.3593751.3751.343756-0.350981.343751.3751.31255-0.848391.31251.3751.2540.162111.3751.51.253-1.798671.251.51.022.3751.52.01.01n17-0.007991.3647460941.365234

10、3751.36425781311-0.016051.3642578131.3652343751.3632812510nnanbnx)(nxf接上圖接上圖迭代迭代11 次，次，近似根近似根364746094. 111 x即為所求，即為所求，其誤差其誤差311111021000488281. 02 abxxn187.2 不動點迭代法及其收斂性不動點迭代法及其收斂性一、迭代法的基本思想一、迭代法的基本思想 迭代法是一種重要的逐次逼近法迭代法是一種重要的逐次逼近法, ,其其基本思想基本思想是：是：將方程將方程 f (x)= 0 化為等價方程化為等價方程, )(xx 然后在隔根區間內取一點然后在隔根區間

11、內取一點 x0 ，按下式計算按下式計算1()(0,1,2,)kkxxk 計算結果生成數列計算結果生成數列,10kxxx如果這個數列有極限如果這個數列有極限 xxkklim19這種求根方法稱為這種求根方法稱為不動點迭代法不動點迭代法。 如果迭代序列收斂如果迭代序列收斂, ,則稱則稱迭代格式收斂迭代格式收斂, ,否則稱為否則稱為發發散散。當當 (x) 連續時連續時, ,顯然顯然 就是方程就是方程 x= (x) 之根。之根。 x于是于是可以從數列可以從數列 中求得滿足精度要求的近似根。中求得滿足精度要求的近似根。kx1()(0,1,2,)kkxxk 稱為稱為迭代格式迭代格式, (x) 稱為稱為迭代函

12、數迭代函數, x0 稱為稱為迭代初值迭代初值,數列數列 稱為稱為迭代序列迭代序列。kx20 03224xxx14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 對方程進行如下三種變形：對方程進行如下三種變形：用迭代法求方程用迭代法求方程 x4+2x2-x-3=0 在區間在區間1, 1.2內內的的 實根實根。解解例例121分別按以上三種形式建立迭代格式，并取分別按以上三種形式建立迭代格式，并取x0=1進行進行迭代計算，結果如下：迭代計算，結果如下：12411()(32)kkkkxxxx 26271.124123xx12()41kkkxxx 4213()23kkkkxxxx

13、 73496,8.49530710 xx22第二種格式比第一種格式收斂快得多第二種格式比第一種格式收斂快得多, ,而第三種格式而第三種格式不收斂。不收斂。可見迭代格式不同可見迭代格式不同, , 收斂情況也不同。收斂情況也不同。準確根準確根 = 1.124123029 。 x23例例2 用迭代法求方程用迭代法求方程0104)(23 xxxf2 , 1在在內的一個近似根，取初始近似值內的一個近似根，取初始近似值5 . 10 x解解原方程的等價方程可以有以下不同形式原方程的等價方程可以有以下不同形式xxxxxxxxxxx 410)4(1021)3(410)2(104)1(32324對應的迭代公式有：

14、對應的迭代公式有：nnnnnnnnnnxxxxxxxxxxxn 410)4(1021)3(410)2(104)1(1312311取取,5 . 10 x列表計算如下列表計算如下251.365230021.3659167381.365229941.3638870071.3652230581.3678469761.365225591.3600941951.365264751.3751702541.364957011.34545838-469.731.367376371.402540802.99696.73221.348399731.286953770.8165-0.87511.51.51.51.50

15、(4)(3)(2)(1)n表表2-226二、二、 迭代法的幾何意義迭代法的幾何意義一般來說從一般來說從,0)( xf構造構造)(x 不止一種，有的不止一種，有的收斂，有的不收斂，這收斂，有的不收斂，這取決于取決于 的性態的性態。)(x 方程方程 的根，在幾何上就是直線的根，在幾何上就是直線)(xx xy 與曲線與曲線 交點的橫坐標交點的橫坐標)(xy 。 x如圖如圖2-3所示所示27)1(1)(0 x 281()0(2)x 29()1(3)x ()1(4)x 30三、不動點的存在性與迭代法的收斂性三、不動點的存在性與迭代法的收斂性定理定理 1 (1) 當當xa , b時時，; ,)(bax (

16、2) 存在正數存在正數L1，使對任意的使對任意的 xa , b,。1)( Lx 方程方程在在a , b存在唯一根存在唯一根)(xx x, ,且滿足條件且滿足條件：設設 則則 ,)(baCx 31 證方程證方程)(xx 之解存在且唯一之解存在且唯一.由于由于)(x 在在 a , b上存在上存在, )()(xxxf f (x) 在在a , b上連續。上連續。作函數作函數由條件由條件)(x 連續連續。所以所以證證使使 0)( xf。)( xx 即即則則(1) f (a) 0 , f (b) 0 , 故存在故存在 ,bax 32則由微分中值定理及條件值定理及條件則由微分中值定理及條件值定理及條件(2)

17、(2)有有 xLxxx)()()(此式僅當此式僅當0 x才能成立才能成立，。 x 因此因此則由微分中值定理及條件則由微分中值定理及條件(2) 有有設方程設方程)(xx 還有一不動點還有一不動點, 33定理定理 2 (1) 當當xa , b時時，; ,)(bax (2) 存在正數存在正數L1，使對任意的使對任意的 xa , b,對任意迭代初值對任意迭代初值 x0a , b,迭代序列迭代序列), 2 , 1 , 0()(1 kxxkk 。1)( Lx , ,且滿足條件且滿足條件：設設收斂于收斂于 。 x 則則 ,)(baCx 11011kkkkkLxxxxLLxxxxL 且有下列誤差估計式且有下列

18、誤差估計式 34即迭代過程收斂，即迭代過程收斂， 且且。 xxkklim反復用此不等式，并注意反復用此不等式，并注意 0 L 1 ,111)()()( kkkkxxLxxxxxx )(00 kxxLxxkk因此因此先證迭代格式先證迭代格式)(1kkxx 收斂收斂任取任取 x0 a, b ，由微分中值定理，有由微分中值定理，有35提示提示：定理的證明利用定理定理的證明利用定理1 1以及微分中值定理。以及微分中值定理。3637則任取則任取 x0 U , )(1kkxx 迭代格式迭代格式均收斂于均收斂于 , x定理定理 3 若方程若方程)( xx 之根的某鄰域之根的某鄰域 L 1時稱為時稱為超線性收

19、斂超線性收斂.利用微分中值定理及泰勒展式可得下面的定理利用微分中值定理及泰勒展式可得下面的定理3. 顯然顯然,收斂階越大收斂階越大,收斂越快收斂越快.p = 2 時稱為時稱為二階二階( (平方平方) )收斂收斂, , 特別地特別地, ,令令, xxekk若若44則迭代過程在則迭代過程在 的鄰近為的鄰近為 p 階收斂階收斂。 x,1)(0 x (1) 若若為線性收斂為線性收斂；則迭代過程在則迭代過程在 的鄰近的鄰近 x, 0)(,0)()()()() 1( xxxxpp (2) 若若定理定理 4)(xx 之根之根, ,在在 的鄰域的鄰域 U內內)(x 有連續的有連續的 p 階導數，階導數，則則

20、設設 為為 x x454631)(limkkkxaxa 由泰勒展式可得由泰勒展式可得113311limlim()()3!4()kkkkkkaxeaeaax 解解)0( aa的三階方法。假設的三階方法。假設 x0 充分靠近充分靠近 , 求求證明迭代公式證明迭代公式 xk+1=xk(xk2+3a)/(3xk2+a) ，試求試求 x例例 247加速迭代法加速迭代法松弛法迭代公式：松弛法迭代公式：)()1()(111nnnnnnnxwxwxxw ), 2 , 1 , 0( nnw為松弛因子為松弛因子7.3 7.3 迭代收斂的加速方迭代收斂的加速方法法48稱為稱為斯蒂芬森斯蒂芬森 ( Steffense

21、n ) 加速法加速法. .則埃特金法為則埃特金法為平方收斂平方收斂；(1)1(2)(1)11(2)(1)2(2)1111(2)(1)11()()()2kkkkkkkkkkkxxxxxxxxxxx 若若)(1kkxx 為為 p ( p 1)階收斂階收斂，)(x 導數連續導數連續,的的 p 階階可以證明可以證明: :)(1kkxx 若若為線性收斂為線性收斂, ,則埃特金法為則埃特金法為 2p 1 階收斂階收斂。迭代格式迭代格式49 求方程求方程 x = e x 在在 x = 0.5 附近的根附近的根. .x25 = x26 = 0.5671433 若對此格式用若對此格式用斯蒂芬森斯蒂芬森法法, 則

22、則 取取 x0 = 0.5, 迭代格式迭代格式kxkex 1 得得解解例例3kxkex )1(1)1(1)2(2 kxkexkkkkkkkxxxxxxx )1(1)2(12)1(1)2(1)2(112)(50仍取仍取 x0 = 0.5 , 得得5671433. 05671433. 05671433. 05671433. 05672979. 05668708. 05676279. 05452392. 06065307. 03)2(3)1(32)2(2)1(21)2(1)1(1 xxxxxxxxx由此可見由此可見,斯蒂芬森斯蒂芬森法加速收斂效果是相當顯著法加速收斂效果是相當顯著的的. .51例例4

23、分別用松弛法、分別用松弛法、斯蒂芬森斯蒂芬森法求方程法求方程 在初值在初值 附近的一個根，取迭代格式附近的一個根，取迭代格式010423 xx5 . 10 x21410 xx解解 用松弛法計算，取用松弛法計算，取21410)( xx 234210)( xx 52因此松弛法的迭代公式為因此松弛法的迭代公式為 )(1421011123nnnnnnxwxwxxw , 2 , 1 , 0 n 列表計算如下：列表計算如下：1.3652300131.3652300121.3649539161.50.8871308690.8871308690.890803686 3 2 1 0nnwnx53用用斯蒂芬森斯蒂

24、芬森方法計算，迭代格式為：方法計算，迭代格式為：nnnnnnnnnnnxxxxxxxxxxx )1(1)2(12)1(1)2(1)2(1121)1(1)2(121)1(12)(410410, 2 , 1 , 0 n 54列表計算如下：列表計算如下：1.3652305831.3673763721.3652255341.3483997251.3652300131.3652652241.5 2 1 0 nnx)1(1 nx)2(1 nx557.4 7.4 牛頓法牛頓法一、牛頓法的基本思想一、牛頓法的基本思想 設已知方程設已知方程 f (x) = 0 的近似根的近似根 x0，且在且在 x0附近附近 可

25、用一階泰勒多項式近似，表示為可用一階泰勒多項式近似，表示為)(xf)()()(000 xxxfxfxf 方程方程 f (x) = 0 可用線性方程近似代替，即可用線性方程近似代替，即0)()(000 xxxfxf56解此線性方程得解此線性方程得)()(000 xfxfxx 取此取此 x 作為原方程的新近似根作為原方程的新近似根 x1，重復以上步驟重復以上步驟，得迭代公式得迭代公式1()(0,1,)()kkkkf xxxkfx 此式稱為此式稱為牛頓牛頓(Newton)迭代公式迭代公式。0)()(000 xxxfxf57例例 1 用牛頓法求方程用牛頓法求方程0104)(23 xxxf在在 內一個實

26、根，取初始近似值內一個實根，取初始近似值。5 . 10 x21 ，解解xxxf83)(2 所以迭代公式為：所以迭代公式為：, 2 , 1 , 0)83()104(2231 nxxxxxxnnnnnn列表計算如下：列表計算如下：1.365230011.365262011.37333331.5 3 2 10nnx58二、牛頓法的幾何意義二、牛頓法的幾何意義)()(000 xxxfxfy 0 x方程方程 的根就是曲線的根就是曲線 與與 軸交軸交點的橫坐標點的橫坐標 ，當初始值，當初始值 選取后，過選取后，過 作切線，其切線方程為：作切線，其切線方程為：0)( xf)(xfy x x)(,(00 xf

27、x)()(0001xfxfxx 它與它與x軸交點的橫坐標為：軸交點的橫坐標為：59一般地，設一般地，設 是是 的第的第n 次近似值，過次近似值，過 作作 的切線，其切線與的切線，其切線與x 軸交點的橫坐標為：軸交點的橫坐標為：nx x)(,(nnxfx)(xfy )()(1nnnnxfxfxx 即用切線與即用切線與 x 軸交點的橫坐標近似代替曲線軸交點的橫坐標近似代替曲線 與與x 軸交點的橫坐標，如圖軸交點的橫坐標，如圖2-4。60若過曲線若過曲線 y= f (x)上的點上的點 P ( xk , f ( xk )引切線，引切線，該切線與該切線與 x 軸交點的橫坐標即為由牛頓迭代公式軸交點的橫坐

28、標即為由牛頓迭代公式求得的求得的 xk+1 , 因此因此牛頓迭代法也稱牛頓切線法牛頓迭代法也稱牛頓切線法。圖圖2-461將原方程化為將原方程化為 x e x = 0，則則牛頓迭代格式為牛頓迭代格式為kkxxkkkeexxx 11取取 x0 =0.5，迭代得迭代得x1=0.566311, x2=0.5671431, x3=0.5671433 f(x)= x e x ， f (x)=1+ e x, 用牛頓迭代法求方程用牛頓迭代法求方程 x = e x 在在 x =0.5 附近的根。附近的根。例例4 4 解解 62三、牛頓迭代法的收斂速度三、牛頓迭代法的收斂速度)()()(xfxfxx 牛頓迭代法的

29、迭代函數為牛頓迭代法的迭代函數為 )()()(0)()()()( xfxfxxfxfxfx 不為不為 0由于由于 ,0)( xf所以當所以當 時時, ,0)( xf63只是收斂速度將大大減慢只是收斂速度將大大減慢。1、當當 為單根時，牛頓迭代法在為單根時，牛頓迭代法在根根 的附近的附近 是二階收斂的是二階收斂的； x x2、當當 為重根時，設為為重根時，設為m重根，則重根，則 f (x)可表為可表為 x)()()(xgxxxfm 其中其中 此時用牛頓迭代法求此時用牛頓迭代法求 仍然收斂仍然收斂，,0)( xg x64)()()()()()()(1kkkkkkkkkkxgxxxgmxgxxxxf

30、xfxx 事實上，因為事實上，因為令令 xxekk則則)()()(*11kkkkkkkkxgexmgxgeexxe 1()limlim1()()110kkkkkkkkeg xemg xe g xm 65可見用牛頓法求方程的重根時僅為線性收斂。可見用牛頓法求方程的重根時僅為線性收斂。1()limlim1()()110kkkkkkkkeg xemg xe g xm 663、計算重根的牛頓迭代法計算重根的牛頓迭代法有兩種方法可以提高求重根的收斂速度：有兩種方法可以提高求重根的收斂速度：1()()kkkkf xxxmfx 1）采用如下迭代格式采用如下迭代格式672）將求重根問題化為求單根問題，注意函數

31、將求重根問題化為求單根問題，注意函數)01)()()()()()( mxQxQxxxfxfxu所以化為求所以化為求 u(x)=0的單根是平方收斂的。的單根是平方收斂的。 12()()()()()()()kkkkkkkkkku xf xfxxxxu xfxf xfx 格式為格式為68 用牛頓迭代法求用牛頓迭代法求 f (x)=(x-1)sin(x-1)+3x-x3+1=0 在在0.95 附近之根附近之根。 取取 x0 = 0.95 用牛頓迭代用牛頓迭代法求得的法求得的 xk 見右表見右表。解解例例 5k xk k m0 1 2 3 4 5 60.95 0.9744279 0.9870583 0.

32、9934878 0.9967328 0.9983576 0.99919010.5090 0.5047 0.5007 0.51252.0369 2.0190 2.0028 2.0511可見可見 xk 收斂很慢。收斂很慢。69由重根數由重根數 m 為為 2 , 用加速法用加速法 x0=0.95 x1=0.9988559 x2=x3=1收斂速度大大加快于直接用牛頓迭代公式收斂速度大大加快于直接用牛頓迭代公式. .1()()kkkkf xxxmfx 求得求得704、簡化牛頓迭代法簡化牛頓迭代法1()(0,1,)kkkf xxxkM 此式稱為此式稱為簡化牛頓迭代公式簡化牛頓迭代公式。只要只要 M 選擇得

33、當選擇得當，上式總是線性收斂的。上式總是線性收斂的。在牛頓迭代公式中用一常數在牛頓迭代公式中用一常數 M 代替代替 得得, )(kxf 7172牛頓下山法牛頓下山法73用常數用常數 M 來代替來代替 f ( xk )雖然簡單，但沒充分雖然簡單，但沒充分利用利用 f (x)本身的特性本身的特性，因此收斂較慢。因此收斂較慢。若在牛頓迭代公式中改用差商若在牛頓迭代公式中改用差商11)()( kkkkxxxfxf代替導數代替導數 f (xk) ，得迭代公式得迭代公式1、割線（弦截）法割線（弦截）法7.5 7.5 弦截法與拋物線法弦截法與拋物線法74111()()()()kkkkkkkf xxxxxf xf x 每步只用一新點，此格式為每步只用一新點，此格式為弦截法（雙點割線法）弦截法（雙點割線法）。可以證明它的收斂階為可以證明它的收斂階為1(15)1.6182p 。確實比式確實比式1()kkkf xxxM 收斂快。收斂快。7576將式將式)()()()(0001xxxfxfxfxxkkkk 每步只用一新點，此格式為每步只用一新點，此格式為單點割線法。單點割線法。中的中的 xk-1 改為改為 x0，即即111()()()()kkkkkkkf xxxxxf xf x 773、割線法的幾何意義、割線法的幾何意義雙點割線法是用過點雙點割線法是用過點 和和 兩兩點的割線與點的割線與 x 軸交