第4章 非線性方程求根

1、第4章 非線性方程求根4.1 實(shí)根的對(duì)分法實(shí)根的對(duì)分法4.2 迭代法迭代法4.3 牛頓牛頓-雷扶生迭代法雷扶生迭代法4.4 弦截法弦截法4.5 非線性方程組的牛頓方法非線性方程組的牛頓方法 本章小結(jié)本章小結(jié) 思考題思考題問題問題的引入的引入 我們知道在我們知道在多項(xiàng)式方程中，求根公式有多項(xiàng)式方程中，求根公式有一、二、三、四次方程，當(dāng)一、二、三、四次方程，當(dāng)n大于大于4已經(jīng)證明沒有計(jì)算公式；在已經(jīng)證明沒有計(jì)算公式；在工程和科學(xué)技術(shù)中許多問題常常歸結(jié)為工程和科學(xué)技術(shù)中許多問題常常歸結(jié)為求解非線性求解非線性方程的方程的問題問題，因此非線性，因此非線性方程的方程的解法需要解法需要給出一給出一種數(shù)值解法

2、，種數(shù)值解法，本章來討論這個(gè)問題。本章來討論這個(gè)問題。 實(shí)根實(shí)根的對(duì)分法的對(duì)分法 所謂對(duì)分法對(duì)我們并不陌生，在所謂對(duì)分法對(duì)我們并不陌生，在VB中學(xué)習(xí)編程時(shí)應(yīng)該學(xué)到。即設(shè)有中學(xué)習(xí)編程時(shí)應(yīng)該學(xué)到。即設(shè)有非線性方程非線性方程 0)(xf0)()(bfaf則函數(shù)在則函數(shù)在a,b 上至少有一個(gè)零點(diǎn)。計(jì)算中通過對(duì)分區(qū)間，逐步縮小有根上至少有一個(gè)零點(diǎn)。計(jì)算中通過對(duì)分區(qū)間，逐步縮小有根區(qū)間，搜索零點(diǎn)的位置。區(qū)間，搜索零點(diǎn)的位置。4.1 實(shí)根的對(duì)分法非線性方程的數(shù)值解法有量大類，對(duì)分法和迭代法。非線性方程的數(shù)值解法有量大類，對(duì)分法和迭代法。為為 a,b 上的連續(xù)函數(shù)，且上的連續(xù)函數(shù)，且第第1步：步：)(2/ )

3、(,111111xfbaxbaba的的函函數(shù)數(shù)值值，計(jì)計(jì)算算區(qū)區(qū)間間中中點(diǎn)點(diǎn)記記如果如果 即即為為所所求求的的根根，則則110)(xxf0)()(11xfaf則根一定在則根一定在區(qū)間區(qū)間 ， ,2211baxa于是我們得到長度縮小一半的含根區(qū)間于是我們得到長度縮小一半的含根區(qū)間,22baab(x1)具體步驟為：具體步驟為：如果如果 ,1xa記記內(nèi)內(nèi)否否則則一一定定在在區(qū)區(qū)間間,2211babx即即 )(21)(21, 0)()(112222abababbfaf 設(shè)已經(jīng)完成了第設(shè)已經(jīng)完成了第1，第，第2，第，第k-1步，得到分半計(jì)算步，得到分半計(jì)算的含的含根區(qū)間根區(qū)間,2211kkbababa且

4、滿足：且滿足： , 0)()(*kkkkbaxbfaf)(21)(211111abababkkkk直至滿足直至滿足 )(211ababkkk為止。為止。 對(duì)分法求根算法對(duì)分法求根算法內(nèi)的一個(gè)實(shí)根內(nèi)的一個(gè)實(shí)根，于區(qū)間于區(qū)間21 01)(6xxxf且要求精度滿足小數(shù)點(diǎn)第三位。即要求且要求精度滿足小數(shù)點(diǎn)第三位。即要求)10213* xxk1、輸入求根區(qū)間和誤差控制量、輸入求根區(qū)間和誤差控制量,ba，定義函數(shù)，定義函數(shù) 。)(xfexitthenbfafif0)()(2、bawhile 例：求方程例：求方程1、輸入求根區(qū)間和誤差控制量、輸入求根區(qū)間和誤差控制量,ba)(xfexitthenbfafif

5、0)()(2、bawhile，定義函數(shù)，定義函數(shù) 。2.1 計(jì)算中點(diǎn)計(jì)算中點(diǎn) 以及函數(shù)值以及函數(shù)值 ；2bax)(xf2.2 分情況處理分情況處理)(xf0)()(xfaf0)()(xfbfendwhile3、輸出近似解、輸出近似解 。x停止計(jì)算轉(zhuǎn)向停止計(jì)算轉(zhuǎn)向3修正區(qū)間修正區(qū)間,baxa修正區(qū)間修正區(qū)間,babx 注意：注意：1、若函數(shù)、若函數(shù) 有幾個(gè)零點(diǎn)，二分法只能算出一個(gè)零點(diǎn)；有幾個(gè)零點(diǎn)，二分法只能算出一個(gè)零點(diǎn)； )(xf注意：注意：2、在實(shí)際操作中，常用、在實(shí)際操作中，常用0)()(bfsignafsign代替代替 ，以避免數(shù)值溢出。，以避免數(shù)值溢出。0)()(bfaf返回本章返回本章

6、4.2 迭代法迭代法 4.2.1 方程的等價(jià)形式方程的等價(jià)形式 4.2.2 迭代法迭代法返回本章返回本章4.2.1 方程的等價(jià)形式方程的等價(jià)形式0)(xf)(xgx 設(shè)非線性方程設(shè)非線性方程，我們總可以，我們總可以將它轉(zhuǎn)化為等價(jià)將它轉(zhuǎn)化為等價(jià)形式形式 。 例例 : 求求方程方程05 . 0sin)(xxxf的等價(jià)的等價(jià)形式。形式。)(5 . 0sin1xgxx解解 ： (a)(b) )()5 . 0arcsin(2xgxx 迭代法是一種逐次逼近法。它是求解代數(shù)方程、超越方程及方迭代法是一種逐次逼近法。它是求解代數(shù)方程、超越方程及方程組的一種基本方程，但存在收斂性及收斂快慢問題。程組的一種基本方

7、程，但存在收斂性及收斂快慢問題。 為了使用迭代法，需要將方程變形成等價(jià)形式。為了使用迭代法，需要將方程變形成等價(jià)形式。 如何使用迭代法求解方程呢？如何使用迭代法求解方程呢？4.2.2 迭代法迭代法定義定義 設(shè)設(shè)方程為方程為 )(xgx （1）選取方程根的一個(gè)初始近似值）選取方程根的一個(gè)初始近似值 ，0 x且按下述逐次代入法，構(gòu)造一近似解序列：且按下述逐次代入法，構(gòu)造一近似解序列：)()()(11201kkxgxxgxxgx這種方法稱為迭代法。這種方法稱為迭代法。)(xg稱為迭代稱為迭代函數(shù)。函數(shù)。 如果迭代收斂，即如果迭代收斂，即)(limlim1kkkkxx，則，則 滿足滿足)(0)(f所以

8、所以 為方程的根。為方程的根。例：例：對(duì)上例中對(duì)上例中的方程，考察用迭代法求根：的方程，考察用迭代法求根：)(5 . 0sin1xgxx)()5 . 0arcsin(2xgxx（a）(b) 0 . 10 x, 2 , 1 , 0),(),(2111kxgxxgxkkkk解解：取初始值取初始值，分別代入迭代公式分別代入迭代公式 計(jì)算結(jié)果計(jì)算結(jié)果如下表。如下表。事實(shí)上，事實(shí)上，1limkkx)(limkkx)lim(kkx)()()(kkxbxak0 1.0 1.01 1.341471 0.5235992 1.473820 0.0236013 1.495301 -0.4965554 1.49715

9、2 -1.4877615 1.4972896 1.4973007 1.497300 kx 由由計(jì)算看出，我們選取的兩個(gè)迭代函數(shù)構(gòu)造的計(jì)算看出，我們選取的兩個(gè)迭代函數(shù)構(gòu)造的序列序列 不一樣，為此不一樣，為此，我們需要解決一個(gè)問題：，我們需要解決一個(gè)問題： ？如何如何選取迭代函數(shù)，使迭代過程收斂選取迭代函數(shù)，使迭代過程收斂。的收斂情況的收斂情況讓讓我們?cè)倏吹覀冊(cè)倏吹匠谭匠?來進(jìn)行分析：來進(jìn)行分析：)(xgx )(xgy xy 發(fā)現(xiàn)，發(fā)現(xiàn)，方程方程 的的根可以看成是曲線根可以看成是曲線與直線與直線的的交交。y=xy=g(x)x*)(xgx 例：例： 我們從圖形上找出作出迭代序列：我們從圖形上

10、找出作出迭代序列：y=xy=g(x)x0 x1x*x2;)(,()(0000QxyxxgxPxgy與與一一點(diǎn)點(diǎn)方方向向前前進(jìn)進(jìn)交交軸軸出出發(fā)發(fā)，沿沿著著平平行行于于上上一一點(diǎn)點(diǎn)從從曲曲線線P0Q0。點(diǎn)點(diǎn)的的橫橫坐坐標(biāo)標(biāo)就就是是顯顯然然，點(diǎn)點(diǎn)，于于軸軸方方向向前前進(jìn)進(jìn)交交點(diǎn)點(diǎn)，沿沿平平行行于于再再從從)()(01110 xgxPPxgyyQ .*xxxkk收收斂斂于于序序列列況況下下，且且從從幾幾何何上上觀觀察察知知情情繼繼續(xù)續(xù)這這個(gè)個(gè)過過程程就就得得到到列列P1P2Oxy 通過圖示觀察，我們發(fā)現(xiàn)迭代收斂與否于迭代函數(shù)的形狀有密通過圖示觀察，我們發(fā)現(xiàn)迭代收斂與否于迭代函數(shù)的形狀有密切的關(guān)系，那么

11、迭代函數(shù)要滿足什么條件能使迭代收斂呢？切的關(guān)系，那么迭代函數(shù)要滿足什么條件能使迭代收斂呢？ 定理：定理： 設(shè)有方程設(shè)有方程 ,若滿足下面三個(gè)條件：若滿足下面三個(gè)條件：)(xgx )(xg1:1:設(shè)迭代函數(shù)設(shè)迭代函數(shù)于于a,b上一階導(dǎo)數(shù)存在；上一階導(dǎo)數(shù)存在；,bax;,)(baxg2:2:當(dāng)當(dāng)時(shí)，有時(shí)，有)(xg1)(Lxg,bax滿足條件滿足條件，當(dāng)，當(dāng)3：則有則有 1：)(xgx ,ba*x迭代方程迭代方程在在上有惟一解上有惟一解 2：對(duì)于任意選取的初始值：對(duì)于任意選取的初始值 ,0bax 迭代方程迭代方程 )(1kkxgx*limxxkk收斂收斂 即即3：), 2 , 1(101*kxxL

12、Lxxkk考察：考察：定理有三個(gè)結(jié)論。定理有三個(gè)結(jié)論。)(xgx ,ba*x1）迭代）迭代方程方程在在上有惟一解上有惟一解分析：我們只需構(gòu)造一個(gè)函數(shù)分析：我們只需構(gòu)造一個(gè)函數(shù))()(xgxx，驗(yàn)證，驗(yàn)證)(x在區(qū)間在區(qū)間,ba上滿足閉區(qū)間連續(xù)函數(shù)的性質(zhì)：上滿足閉區(qū)間連續(xù)函數(shù)的性質(zhì)：0)(, 0)(ba則函數(shù)至少有一個(gè)零點(diǎn)，則函數(shù)至少有一個(gè)零點(diǎn)，*,xx 關(guān)于關(guān)于唯一性證明，不妨設(shè)有兩個(gè)零點(diǎn)唯一性證明，不妨設(shè)有兩個(gè)零點(diǎn))(, 0)()(*xgxxgxx，只需證明，只需證明*xx 可以利用中值定理得到?？梢岳弥兄刀ɡ淼玫?。kkkxxLxx1*112）對(duì)于）對(duì)于任意選取的初始值任意選取的初始值 ,

13、0bax 迭代方程迭代方程 )(1kkxgx*limxxkk收斂收斂 即即只需考察只需考察*1xxk而這是顯然的。而這是顯然的。3）), 2 , 1(101*kxxLLxxkk只需變形不等式：只需變形不等式：由迭代公式由迭代公式)(1kkxgx)()()(111kkkkkkxxcgxgxgxx可以推得可以推得1kkxxL)()(*xgxgk*12xxLk*xxLk)()(*1xgxgLk?0*01 kkxxLL) 1 (), 2 , 1(11LkxxLxxkkkk即即kkxx1于是于是kkxxLxx*即即由（由（1）（）（2）有）有 11*111kkkkkxxLLxxLxx2121kkxxLL

14、011xxLLk至此，定理的分析完畢，證明過程請(qǐng)大家看書。至此，定理的分析完畢，證明過程請(qǐng)大家看書。)(1*kkxxxx1*kkxxxx)2()1 (*kxxL注意注意：對(duì)定理中：對(duì)定理中的假設(shè)條件的假設(shè)條件1)(Lxg等價(jià)形式等價(jià)形式 ，而，而 ，由，由 的連續(xù)性，一定存在一個(gè)鄰域的連續(xù)性，一定存在一個(gè)鄰域在其上有在其上有可能對(duì)于大范圍的含根區(qū)間可能對(duì)于大范圍的含根區(qū)間難于滿足難于滿足，而在根的鄰近是成立的。事實(shí)上，如果而在根的鄰近是成立的。事實(shí)上，如果 是是 的零點(diǎn)，若能構(gòu)造的零點(diǎn)，若能構(gòu)造 *x)(xf)(xx1)(* x)(x),(*xx1)(Lx，這時(shí)若初值，這時(shí)若初值),(*0 x

15、xx，則迭代收斂。，則迭代收斂。整理一下：迭代收斂整理一下：迭代收斂 的兩個(gè)要素為的兩個(gè)要素為1、等價(jià)形式應(yīng)滿足、等價(jià)形式應(yīng)滿足1)(*Lxg2、初始值初始值 必須在根的充分小的鄰域內(nèi)。必須在根的充分小的鄰域內(nèi)。0 x例：求代數(shù)方程例：求代數(shù)方程 在在 附近的實(shí)根。附近的實(shí)根。0523 xx20 x解：解：5 . 2 , 5 . 1 , 1)(,)52(131)(3/2xxxx所以構(gòu)造的迭代收斂。所以構(gòu)造的迭代收斂。3135252) 1xxxxk取取20 x094550. 2094543. 2094494. 2094217. 2,09235. 2,08008. 2654321xxxxxx而準(zhǔn)確

16、解為而準(zhǔn)確解為00945514815. 2x5 . 2 , 5 . 1 , 123)(25)(,25223231xxxxxxxnn2）將迭代格式寫出）將迭代格式寫出所以迭代不能保證收斂。所以迭代不能保證收斂。返回返回本節(jié)本節(jié)4.3 牛頓-雷扶生方法 牛頓牛頓-雷扶生方法是一種將非線性函數(shù)線性化的方法，例如將高次多雷扶生方法是一種將非線性函數(shù)線性化的方法，例如將高次多項(xiàng)式化成一次多項(xiàng)式；牛頓項(xiàng)式化成一次多項(xiàng)式；牛頓-雷扶生方法的優(yōu)點(diǎn)是在單根附近具有較高的雷扶生方法的優(yōu)點(diǎn)是在單根附近具有較高的收斂速度收斂速度；牛頓；牛頓-雷扶生方法可用來計(jì)算方程的實(shí)根，也可計(jì)算代數(shù)方程雷扶生方法可用來計(jì)算方程的實(shí)

17、根，也可計(jì)算代數(shù)方程的復(fù)根的復(fù)根 。我們先來看牛頓法的幾何意義：我們先來看牛頓法的幾何意義： x1x*x0返回本章返回本章x2我們推導(dǎo)牛頓我們推導(dǎo)牛頓-雷復(fù)生迭代公式。雷復(fù)生迭代公式。)(xfy （1）求過曲線）求過曲線 )(xfy 上的點(diǎn)上的點(diǎn)P )(,(00 xfx的切線的切線方程：方程： )()(000 xxxfxfy（2）切線）切線近似代替曲線，切線的零點(diǎn)近似代替曲線，切線的零點(diǎn) 1x近似近似代替代替 的根的根 *x0)(xf0)()(000 xxxfxf解解x得到得到)()(0001xfxfxxx重復(fù)上述的過程，得到牛頓重復(fù)上述的過程，得到牛頓-雷扶生計(jì)算公式雷扶生計(jì)算公式, 2 ,

18、 1 , 0)()(10kxfxfxxxkkkk迭代迭代函數(shù)：函數(shù)： )()()(xfxfxxx牛頓迭代式是否收斂呢？即牛頓迭代式是否收斂呢？即 在根附近是否成立？在根附近是否成立？考察考察說明：牛頓迭代公式還可以通過泰勒公式一階展開得到，并且還可以考察公說明：牛頓迭代公式還可以通過泰勒公式一階展開得到，并且還可以考察公式的誤差問題。式的誤差問題。1)()()()(2 xfxfxfx設(shè)設(shè) ，即，即 是方程是方程 的單根，則的單根，則0)(f0)(xf0)(, 0)(ff則有則有0)(因此只要初值因此只要初值 充分的靠近充分的靠近 ，有，有0 x1)( x所以牛頓迭代法收斂。所以牛頓迭代法收斂。

19、1)( x例：例： 用牛頓法計(jì)算用牛頓法計(jì)算 01)2()(4xexfx的根的根 解：容易看出，解：容易看出，0)2()0( ff，方程方程在在0，2內(nèi)有一根。內(nèi)有一根。4)6()(4xexfx所以牛頓法的計(jì)算公式為所以牛頓法的計(jì)算公式為, 1 , 04/ )6(1)2(4/4/1kxexexxkxkxkkkk10 x80 x（1）取）?。?）?。┤?，兩次計(jì)算的果見下表，兩次計(jì)算的果見下表：kxkkxk0 1 0 81 -1.155999 1 34.7781072 0.189438 2 869.15193 0.714043 4 0.7825425 0.7835956 0.783598收斂收斂發(fā)

20、散發(fā)散例：用牛頓迭代法求方程例：用牛頓迭代法求方程03 .152 .197 . 7)(23xxxxf在在 附近的根?？磿?。附近的根?？磿?。10 x牛頓牛頓迭代法的局限性迭代法的局限性： 1）要求初始值在根的附近；有時(shí)發(fā)生從一個(gè)根附近跳向另一根）要求初始值在根的附近；有時(shí)發(fā)生從一個(gè)根附近跳向另一根附附近，尤其在導(dǎo)數(shù)近，尤其在導(dǎo)數(shù) 數(shù)值很小時(shí)，如下圖。數(shù)值很小時(shí)，如下圖。 2）如果函數(shù)沒有實(shí)根，初始值是實(shí)數(shù)，迭代序列不收斂。）如果函數(shù)沒有實(shí)根，初始值是實(shí)數(shù)，迭代序列不收斂。)(0 xf *x*x0 x牛頓迭代算法：牛頓迭代算法：, 2 , 1 , 0)()()(10kxxfxfxxxkkkkk1、

21、定義函數(shù)及迭代函數(shù)、定義函數(shù)及迭代函數(shù) ，初始值，初始值 ，控制精度，控制精度 。)(),(xxf0 x2、10) 1()01()0(1, 1 , 0 xxelsethenxforxxifxxMAXiforL輸出輸出x1，結(jié)束，結(jié)束3、輸出近似值附近無根。、輸出近似值附近無根。返回本章返回本章為什么？為什么？又由導(dǎo)數(shù)又由導(dǎo)數(shù)的近似計(jì)算公式的近似計(jì)算公式11)()()(kkkkkxxxfxfxf代入牛頓迭代代入牛頓迭代式得到：式得到： )()(1kkkkxfxfxx)()()()(111kkkkkkkxxxfxfxfxx4.4 弦截法想一想：想一想：牛頓迭代法是不斷的用曲線切線的零點(diǎn)逼近曲線的零

22、點(diǎn)，而切線又可以牛頓迭代法是不斷的用曲線切線的零點(diǎn)逼近曲線的零點(diǎn)，而切線又可以用割線來逼近，因此可以對(duì)牛頓法改造，得到另一種迭代公式。用割線來逼近，因此可以對(duì)牛頓法改造，得到另一種迭代公式。已知牛頓迭代公式已知牛頓迭代公式, 2 , 1kX*x0 x1x2給出給出初始值初始值 x0、x1，算出，算出近似值近似值 x2。幾何意義：幾何意義：算法描述：算法描述：根據(jù)牛頓迭代算法，自己分析并寫出。根據(jù)牛頓迭代算法，自己分析并寫出。函數(shù)無近似根函數(shù)無近似根輸出輸出退出退出輸出近似根輸出近似根算出迭代函數(shù)算出迭代函數(shù)初始值初始值）定義函數(shù)）定義函數(shù)弦截法算法：弦截法算法：:)4,)()()()()(,

23、2 , 1)3)(),()2;,),xxxxelsexxfifxxxfxfxfxxMAXiforxfxfxxxf返回本章返回本章設(shè)二階方程組設(shè)二階方程組4.5 非線性方程組的牛頓方法yxXyxfyxfXF,),(),()(21量形式量形式為方便記，將方程組向?yàn)榉奖阌洠瑢⒎匠探M向0),(0),(21yxfyxf為自變量為自變量其中，其中，yx,附近做二元泰勒附近做二元泰勒在點(diǎn)在點(diǎn)將將),(),(),(0021yxyxfyxfyyxfyyxyxfxxyxfyxfyyxfyyxyxfxxyxfyxf),()(),()(),(),(),()(),()(),(),

24、(002000200022001000100011，并取其線性部分，并取其線性部分整理：整理：與非線性方程的迭代一樣，這里與非線性方程的迭代一樣，這里我們也尋求迭代法：我們也尋求迭代法：2211)1(00)0(yxyxXyxX0),()(),()(),(0),()(),()(),(0),(0),(002000200020010001000121yyxfyyxyxfxxyxfyyxfyyxyxfxxyxfyxfyxf令令則有則有令令,00yyyxxx),(),(),(),(),(),(000020020010010012yxfyyyxfxxyxfyxfyyyxfxxyxfyxyfxfyfxfyx

25、J,0),(221100，解出，解出取取，從而可求出，從而可求出 。11yxyyxxyxXyxX0011)1(00)0(得出得出由由類似的，由類似的，由yyyxxx0101,),(),(),(),(),(),(111121121111111112yxfyyyxfxxyxfyxfyyyxfxxyxf解出解出11,yyyxxx得出得出yyxxyxX1122)2(),(),(),(21kkkkkkyxfyxfyxyxJ繼續(xù)做下去，每一次迭代都是解一個(gè)方程組繼續(xù)做下去，每一次迭代都是解一個(gè)方程組為止。為止。一直做到一直做到|,|maxyxyfxfyfxfyxJkk2211),(其中其中kkkkyyyx

26、xx11即即整理一下：整理一下：例：求解線性方程組例：求解線性方程組01),(04),(2221yeyxfyxyxfx7 . 11)0(X解：解：yfxfyfxfyxJ2211),(122xeyx171828. 24 . 32)7 . 1, 1 (J所以有所以有由由01828. 011. 0),(),(,0020010yxfyxfXF方程組為：方程組為：01828. 071828. 211. 04 . 32yxyx解之：解之：029849. 0004256. 0yxX即：即：729849. 1004256. 1029849. 0004256. 07 . 1100)1(XyxX),(),(),(),(),(),(000020020010010012yxfyyyxfxxyxfyxfyyyxfxxyxf又將方程組：又將方程組：)(),(),(),(11200100XFyxfyxfXyxJ寫成矩陣形式：寫成矩陣形式：其中其中)0()1(00110101XXyxyxyyxxyxX)(),(),(),(),(100112001100XFyxJyxfyxfyxJX所以所以繼續(xù)做下去，直至繼續(xù)做下去，直