第7章非線性方程求根

1、1第7章 非線性方程求根第一節(jié) 方程求根與二分法本章主要討論單變量的非線性方程求根問題本章主要討論單變量的非線性方程求根問題2非線性方程根的不同情況 設(shè)非線性方程為： f (x)=0 當(dāng)f (x)為多項(xiàng)式時(shí)，非線性方程是一種特殊形式的方程，即多項(xiàng)式方程，也叫n 次代數(shù)方程 。 若若x*使得使得f (x*)=0，則稱，則稱x*為方程為方程f (x)=0的根的根或函數(shù)或函數(shù) f (x)的零點(diǎn)。的零點(diǎn)。 0)(10 n nn nn na ax xa ax xa aa ax xf f3非線性方程根的不同情況若 f (x)可表示成： Z Zm mx xg gx xx xx xf fm m)()(且且g

2、( x* ) 0當(dāng)當(dāng) m=1 時(shí)，時(shí)，x*稱為稱為f (x)的的單根單根；當(dāng)當(dāng) m1 時(shí)，時(shí)， x*稱為方程稱為方程f (x)的的m重根重根，或函數(shù)，或函數(shù) f (x)的的m重零點(diǎn)重零點(diǎn)。n次的非線性方程在復(fù)數(shù)域內(nèi)有且僅有次的非線性方程在復(fù)數(shù)域內(nèi)有且僅有n個(gè)根。個(gè)根。4求根的方法n對于1次、2次的多項(xiàng)式方程，已經(jīng)有成熟、有效的解法；n對于3次、4次的多項(xiàng)式方程，也有公式可以使用，但形式較為復(fù)雜；n高于4次的多項(xiàng)式方程早在1830年就證明了不可能用公式求解。5求根的方法 根據(jù)前面的討論，可以把次數(shù)高于2次的多項(xiàng)式方程同一般的非線性方程 f (x)=0的求解作為相同的問題進(jìn)行研究。 對這類問題通常

3、采用區(qū)間法或迭代法求解。6非線性方程的有根區(qū)間若 f(x) 滿足條件:(1) 在a,b內(nèi)連續(xù), (2) f(a) f (b)0, f (0)=10, f (3)=- -260可見可見 f(x)僅有兩個(gè)實(shí)根僅有兩個(gè)實(shí)根, 分別位于分別位于(0, 3) , (3,+)9非線性方程的有根區(qū)間又因?yàn)橛忠驗(yàn)?f (4)=10, 所以第二有根區(qū)間可縮小為所以第二有根區(qū)間可縮小為 (3,4)。x(-,0)0 (0,3) 3 (3,4) 4 (4,+) f (x) f (x) - 0+ - 0-+ 有根區(qū)間(0,3)(3,4)10非線性方程的有根區(qū)間逐步搜索法 (增值尋根法) 增值尋根法的基本思想是增值尋根法

4、的基本思想是: : 從初值從初值 開始開始, , 按按規(guī)定的一個(gè)初始步長規(guī)定的一個(gè)初始步長h 來增值。來增值。同時(shí)計(jì)算同時(shí)計(jì)算 。0 x1(0,1,2,)nnxxhn )(1 nxf11非線性方程的有根區(qū)間搜索過程搜索過程, ,可從可從a開始開始, ,也可從也可從b開始開始, ,這時(shí)應(yīng)取步這時(shí)應(yīng)取步長長 h 0。0)()1(1 nxf此時(shí)此時(shí) 即為方程的根即為方程的根1 nx。 x1(2)()()0nnf xf x 說明區(qū)間說明區(qū)間 內(nèi)無根內(nèi)無根 ,1 nnxx可能遇到三種情形：可能遇到三種情形：1(3)()()0nnf xf x ，說明區(qū)間說明區(qū)間 內(nèi)有根內(nèi)有根 ,1 nnxx12求方程的有

5、根區(qū)間.解解根據(jù)有根區(qū)間定義，對方程的根進(jìn)行搜索計(jì)算，結(jié)果如下表：方程的三個(gè)有根區(qū)間為1,2,3,4,5,6.13二分法 應(yīng)用二分法的前提：已經(jīng)確定了非線性方程的有根區(qū)間a,b。 設(shè)方程設(shè)方程 f (x)=0 在區(qū)間在區(qū)間a,b 內(nèi)有且只有一內(nèi)有且只有一個(gè)實(shí)根個(gè)實(shí)根 x* 。 即即 f (x) 滿足條件滿足條件: (1) 在在a,b內(nèi)連續(xù)；內(nèi)連續(xù)；(2) f(a) f(b)0 , (3) f(x) 在在a,b內(nèi)嚴(yán)格單調(diào)。內(nèi)嚴(yán)格單調(diào)。14二分法 二分法的基本思想是：通過等分有根區(qū)間，不斷壓縮有根區(qū)間的大小。在有限步運(yùn)算中，當(dāng)區(qū)間壓縮到一定小的程度時(shí)，用其中點(diǎn)作為原方程的近似解。取有根區(qū)間取有根區(qū)

6、間a,b的中點(diǎn)的中點(diǎn)20b ba ax x 計(jì)算計(jì)算f(x0)，考察考察f(x0)的正負(fù)情況。的正負(fù)情況。15二分法(1)若若 f ( x0 ) = 0, 則則 x0 就是方程的根就是方程的根x*,計(jì)算結(jié)束計(jì)算結(jié)束 ;(2)若若 ，則則 令令 a1= a , b1=x0 ;0)()(0 x xf fa af f),(0*x xa ax x (3)若若 ，則則 令令 a1= x0 , b1= b ;0)()(0 x xf fb bf f),(1*b bx xx x 此時(shí)的有根區(qū)間為此時(shí)的有根區(qū)間為a1,b1，該區(qū)間大小為原區(qū)間的，該區(qū)間大小為原區(qū)間的一半。一半。16二分法對壓縮了的有根區(qū)間a1,

7、b1，實(shí)行同樣的步驟。若每次二分時(shí)所取區(qū)間中點(diǎn)都不是根，則上述過程若每次二分時(shí)所取區(qū)間中點(diǎn)都不是根，則上述過程將無限進(jìn)行下去。將無限進(jìn)行下去。如此反復(fù)進(jìn)行如此反復(fù)進(jìn)行, 可得一系列有根區(qū)間可得一系列有根區(qū)間 ,2211k kk kb ba ab ba ab ba ab ba a17二分法 由于每一區(qū)間都是前一區(qū)間的一半，因此區(qū)間ak, bk的長度為：)(21a ab ba ab bk kk kk k 0)(21lim a ab bk kk k 即當(dāng)即當(dāng) k 時(shí)時(shí), 區(qū)間必將最終收縮為一點(diǎn)區(qū)間必將最終收縮為一點(diǎn)x*, 顯顯然然x* 就是所求的根。就是所求的根。18二分法 小結(jié)：二分法也可以看作一

8、種迭代法，它的迭代過程確定了一個(gè)區(qū)間的序列 I(k) ，使每個(gè)區(qū)間都包含方程的某個(gè)解x*。且區(qū)間長度趨于零。顯然，當(dāng)區(qū)間的長度足夠小時(shí)，此區(qū)間中任何一點(diǎn)與x*的差必小于某一個(gè)值。所以可以用此區(qū)間中任何一點(diǎn)作為x*的近似，且誤差可以容易估計(jì)。19二分法當(dāng)區(qū)間ak, bk的中點(diǎn)作為x*的近似值時(shí)，即：2*k kk ka ab bx x 1*22| k kk kk kk ka ab ba ab bx xx x二分法的二分法的特點(diǎn)特點(diǎn)：計(jì)算簡單，且總是收斂的。但是：計(jì)算簡單，且總是收斂的。但是收斂速度慢。收斂速度慢。二分法適合于尋求一個(gè)較好的近似解，作為其它二分法適合于尋求一個(gè)較好的近似解，作為其它方

9、法求解的初值。方法求解的初值。20二分法 例：用二分法求方程 f(x)=x3-x-1=0在區(qū)間(1,1.5)的實(shí)根,要求誤差不超過0.005。005. 0 k kx xx x解：即要求滿足解：即要求滿足005. 022|1* k kk kk kk ka ab ba ab bx xx x6 . 5 k k取取k =621二分法(1) f (a)0(2) 根據(jù)精 度要求,取到小數(shù)點(diǎn)后四位即可.-+-+ - -1.251.3751.31251.34381.32811.32031.32421.51.51.3751.3751.34381.32811.32811.01.251.251.31251.3125

10、1.31251.32030123456 bk akkkx x)(k kx xf f二分法計(jì)算過程見下表：二分法計(jì)算過程見下表：x* 1.3242 22二分法 例：用二分法求 在1,2 內(nèi)的一個(gè)實(shí)根，且要求滿足精度0104)(23 xxxf31021 k kx xx x23二分法kakbkxkf(xk)01.02.01.52.37511.01.51.25-1.7986721.251.51.3750.1621131.251.3751.3125-0.8483941.31251.3751.34375-0.3509851.343751.3751.359375-0.0964161.3593751.3751

11、.363281250.0323624二分法kakbkxkf(xk)71.3593751.36718751.364257813-0.0321581.363281251.36718751.3647460940.00007291.363281251.3652343751.364257813-0.01605101.3642578131.3652343751.364746094-0.00799x* x10 = 1.36474609431010101021000488281. 02 a ab bx xx x25第七章 非線性方程求根第二節(jié) 迭代法及其收斂性26迭代法的基本思想迭代法是一種重要的逐次逼近法迭

12、代法是一種重要的逐次逼近法, ,其其基本思想基本思想是：是：將方程將方程 f (x)= 0 化為等價(jià)方程化為等價(jià)方程, )(xx 然后在有根區(qū)間內(nèi)取一點(diǎn)然后在有根區(qū)間內(nèi)取一點(diǎn) x0 ，按下式計(jì)算按下式計(jì)算1()(0,1,2,)kkxxk 計(jì)算結(jié)果生成數(shù)列計(jì)算結(jié)果生成數(shù)列,10kxxx如果這個(gè)數(shù)列有極限如果這個(gè)數(shù)列有極限 xxkklim當(dāng)當(dāng) (x) 連續(xù)時(shí)連續(xù)時(shí), ,顯然顯然 就是方程就是方程 x= (x) 的根。的根。 x27這種求根方法稱為這種求根方法稱為迭代法迭代法。 如果迭代序列收斂如果迭代序列收斂, ,則稱則稱迭代格式收斂迭代格式收斂, ,否則稱為否則稱為發(fā)發(fā)散散。于是于是可以從數(shù)列可

13、以從數(shù)列 中求得滿足精度要求的近似根。中求得滿足精度要求的近似根。kx1()(0,1,2,)kkxxk 稱為稱為迭代格式迭代格式, (x) 稱為稱為迭代函數(shù)迭代函數(shù), x0 稱為稱為迭代初值迭代初值,數(shù)列數(shù)列 稱為稱為迭代序列迭代序列。kx迭代法的基本思想28)(0)( x xx xx xf f 所以通常稱所以通常稱 為為 的不動點(diǎn)，求的不動點(diǎn)，求f (x)的零的零點(diǎn)等價(jià)于求點(diǎn)等價(jià)于求 的零點(diǎn)。的零點(diǎn)。*x x)(x x )(x x 因此，又稱因此，又稱 為不動點(diǎn)為不動點(diǎn)迭代法迭代法。1()(0,1,2,)kkxxk 迭代法的基本思想29 03224xxx14)(2 xxx 32)(243 x

14、xxx 4121)23()(xxxx 對方程進(jìn)行如下三種變形：對方程進(jìn)行如下三種變形：用迭代法求方程用迭代法求方程 x4+2x2-x-3=0 在區(qū)間在區(qū)間1, 1.2內(nèi)內(nèi)的的 實(shí)根實(shí)根。解解例例1迭代法的基本思想30分別按以上三種形式建立迭代格式，并取分別按以上三種形式建立迭代格式，并取x0=1進(jìn)行進(jìn)行迭代計(jì)算，結(jié)果如下：迭代計(jì)算，結(jié)果如下：12411()(32)kkkkxxxx 26271.124123xx 12()41kkkxxx 124123. 176 x xx x迭代法的基本思想31第二種格式比第一種格式收斂快得多第二種格式比第一種格式收斂快得多, ,而第三種格而第三種格式不收斂。式不

15、收斂?？梢姷袷讲煌梢姷袷讲煌? , 收斂情況也不同。收斂情況也不同。準(zhǔn)確根準(zhǔn)確根 = 1.124123029 。 x4213()23kkkkxxxx 73496,8.495307 10 xx 迭代法的基本思想32例例2 用迭代法求方程用迭代法求方程0104)(23 xxxf2 , 1在在內(nèi)的一個(gè)近似根，取初始近似值內(nèi)的一個(gè)近似根，取初始近似值5 . 10 x解解原方程的等價(jià)方程可以有以下不同形式原方程的等價(jià)方程可以有以下不同形式x xx xx xx xx xx xx xx xx xx xx x 410)4(1021)3(410)2(104)1(323迭代法的基本思想33對應(yīng)的迭代公式

16、有：對應(yīng)的迭代公式有：nnnnnnnnnnxxxxxxxxxxxn 410)4(1021)3(410)2(104)1(1312311取取,5 . 10 x列表計(jì)算如下列表計(jì)算如下迭代法的基本思想341.365230021.3659167381.365229941.3638870071.3652230581.3678469761.365225591.3600941951.365264751.3751702541.364957011.34545838-469.731.367376371.402540802.99696.73221.348399731.286953770.8165-0.87511.5

17、1.51.51.50(4)(3)(2)(1)n81003. 1 21)65. 8( 迭代法的基本思想35n (1) (2) (3) (4)91.364878221.36523001101.36541006151.36522368201.36523024231.36522998251.36523001接上表接上表迭代法的基本思想36例例2.3 求方程在附近的根.解解 若將方程改寫為,構(gòu)造迭代法由可知，顯然不收斂.構(gòu)造迭代法若將方程改為37計(jì)算結(jié)果如下：從結(jié)果看它是收斂的，且在6位有效數(shù)字時(shí)即為根x*的近似值.38迭代法的幾何意義一般來說從一般來說從,0)( xf構(gòu)造構(gòu)造)(x 不止一種，有的不止

18、一種，有的收斂，有的不收斂，這取決于收斂，有的不收斂，這取決于 的性態(tài)。的性態(tài)。)(x 方程方程 的根，在幾何上就是直線的根，在幾何上就是直線)(xx xy 與曲線與曲線 交點(diǎn)的橫坐標(biāo)交點(diǎn)的橫坐標(biāo))(xy 。 x390()1(1)x迭代法的幾何意義401()0(2)x 迭代法的幾何意義41()1(3)x 迭代法的幾何意義42()1(4)x 迭代法的幾何意義43迭代法的收斂條件定理定理 1 (1) 當(dāng)當(dāng)xa , b時(shí)時(shí)，; ,)(bax (2) 存在正數(shù)存在正數(shù)L1時(shí)稱為時(shí)稱為超線性收斂超線性收斂.顯然顯然,收斂階越大收斂階越大,收斂越快收斂越快.p = 2 時(shí)稱為時(shí)稱為二階二階( (平方平方)

19、 )收斂收斂, , 特別地特別地, ,令令, xxekk若若54則迭代過程在則迭代過程在 的鄰近為的鄰近為 p 階收斂階收斂。 x,1)(0 x (1) 若若為線性收斂為線性收斂；則迭代過程在則迭代過程在 的鄰近的鄰近 x, 0)(,0)()()()() 1( xxxxpp (2) 若若定理定理 3)(xx 的根的根, ,在在 的鄰域的鄰域 U內(nèi)內(nèi))(x 有連續(xù)的有連續(xù)的 p 階導(dǎo)數(shù)，階導(dǎo)數(shù)，則則 設(shè)設(shè) 為為 x x迭代法的收斂速度55將將 處進(jìn)行泰勒展開：處進(jìn)行泰勒展開：*)(x xx xk k在在 p pk kp pk kk kx xx xp px xx xx xx xx x*)(!)(*

20、)*)(*)()()( ,0)(,0)()()()()1( xxxxpp p pk kp pk kx xx xp px xx x*)(!)(*)()()( *)()(1x xx xx xx xk kk k !)()(1p pe ee ep pp pk kk k !)(*)(p px xp p 迭代法的收斂速度56迭代法的加速迭代法的加速無論是解線性方程組的Jacobi迭代法和GS迭代法還是解非線性方程N(yùn)ewton系列迭代法都涉及到收斂速度問題如何加快迭代法的速度呢？也涉及到初值的選取問題如何改善迭代法的適用范圍呢？57GkGkfxBx)()1(bLDUxLDk1)(1)()(bUxxLDkk)

21、()1()(由G-S迭代法的矩陣形式矩陣形式)()1()(kkkxxr加速)()1()(kkkxxr)()()1(kkkxrx加速法主要思想58)()1()(kkkxxr)()()1(kkkrxxbUxLxDxkkk)()1()1(bDUxDLxDxkkk1)(1)1(1)1(bDUxDLxDxxkkkk1)(1)1(1)()(bDUxDLxDxkkk1)(1)1(1)()()1(1)(1)1(1)(bDUxDLxDxkkk-(5)的改變量次迭代時(shí)第xk1前加上因子在)(kr兩邊同時(shí)乘兩邊同時(shí)乘D D59)()1()()1()()1(bUxLxDxDxkkkkbxUDxLDkk)()1()1(

22、)(bLDxUDLDxkk1)(1)1()()1()(-(6)上式為逐次超松弛法(SOR迭代法)的矩陣形式)1()(1UDLDBbLDf1)(令fxBxkk)()1(-(7)法的迭代矩陣為SORB60,1時(shí)當(dāng)SOR法化為bLDUxLDxkk1)(1)1()()(G-SG-S迭代法迭代法G-S法為SOR法的特例, SOR法為G-S法的加速例1.用G-S法和SOR法求下列方程組的解,45. 1取321242124321xxx320要求精度1e-661解:(1)G-S迭代法GBULD1)(13210420040002001205 . 03/10625. 025. 0025. 05 . 00fbLD1

23、)(13210420043203/25 . 0062),0 ,0()0(取初值xx,k=gauss_seidel(a,b,1,1,1,1e-6) 1 1 1 0.7500000 0.3750000 1.5000000 0.5625000 0.5312500 1.5416667 0.6510417 0.5963542 1.6145833 0.7018229 0.6582031 1.6727431. 0.9999933 0.9999923 1.9999926 0.9999943 0.9999935 1.9999937 0.9999952 0.9999944 1.9999946 k = 71x=0.

24、9999950.9999941.999995滿足精度的解迭代次數(shù)為71次63(1)SOR迭代法 1 1 1 0.6375000 0.0121875 1.3199063 0.2004270 0.3717572 1.3122805 0.6550335 0.5340119 1.6922848 0.7058468 0.7733401 1.7771932. 0.9999990 0.9999976 1.9999991 0.9999984 0.9999993 1.9999989 0.9999998 0.9999994 1.9999998 0.9999996 0.9999998 1.9999997 k = 2

25、4x=1.0000001.0000002.000000滿足精度的解迭代次數(shù)為24次bLDxUDLDxkk1)(1)1()()1()(SOR法的收斂速度比G-S法要快得多,選取適當(dāng)?shù)?4SOR法都收斂嗎？1.SOR迭代法收斂的充要條件是對于SOR迭代法(7),有如下結(jié)論1)(B-(8)|1|)(B由于(此結(jié)論的證明較復(fù)雜此結(jié)論的證明較復(fù)雜), 因此有法收斂的必要條件是即SOR20, 1|1| . 2,20,. 3)0(xA對任意初值且為對稱正定矩陣若矩陣法均收斂SOR收斂對任意初值為對稱正定矩陣若矩陣)0(,. 4xSGA另外,松弛因子的選取是很困難的,一般采用試算試算進(jìn)行65二、非線性方程迭代

26、法的加速對于迭代法)(1kkxx1()kkkkxxxx kkkxxr11kkk kxxr)(kkkkxxx)()1(1kkkkkxxx)(kkxx上式的迭代函數(shù))()1()(xxx)()1()(xx0令迭代改變量k加入因子即的加權(quán)平均與)(kkxx求導(dǎo)并令-(9)66)(11x)(11kkx)()1(1kkkkkxxx得因此有松弛迭代法:-(10)從后面的例子可以看出,加速效果是明顯的甚至一些不收斂的迭代法經(jīng)過松弛加速后也能收斂67),(kx要計(jì)算松弛法的每一步迭代都不方便*,)(xxx的精確解為假設(shè)方程0 x初值為)(01xx)(12xx22*xxxx)(*)(12xxx)*)(12xxx中

27、值定理)*()()(101012xxxxxxx差商近似代替導(dǎo)數(shù))*(*101122xxxxxxxx即68得解出 *,x01221222)(*xxxxxxx于是可以得到迭代格式:)(01xx)(12xx其中)()1(kkxx)()1()2(kkxxkkkkkkkxxxxxxx)1()2(2)1()2()2(12)(,2 , 1 ,0k-(11)上組公式稱為Altken公式或Altken加速69將(11)式綜合后可得一個(gè)解析式表示的迭代法:kkkkkkkxxxxxxx)(2)()()()(21-(12)上式稱為Steffensen迭代法Altken公式與Steffensen公式是等價(jià)的加速效果也是

28、很明顯的例2中將比較不同加速方法70例2.對迭代格式3131kkxx進(jìn)行加速解方程組0133 xx6010,5 . 0精確到初值x解:x0 = 0.5x1 = 0.375x2 = 0.3509115x3 = 0.3477369x4 = 0.3473496x5 = 0.3473028x6 = 0.3472971x7 = 0.34729643131kkxx(1)直接使用迭代格式迭代7次,得到滿足精度的解347296. 0 x71(2)對迭代格式進(jìn)行松弛加速211kkx)1(313223kkkxxx31)(3xx2)(xx )()1(1kkkkkxxxx0 = 0.5x1 = 0.3333333x2

29、 = 0.3472222x3 = 0.3472964x4 = 0.3472964迭代4次,得到滿足精度的解347296. 0 x72(3)對迭代格式進(jìn)行Altken加速(11)式313)1(kkxxx0 = 0.5x1 = 0.3451613x2 = 0.3472961x3 = 0.3472964迭代3次,得到滿足精度的解347296. 0 x從以上3種結(jié)果可見,迭代法加速技術(shù)效果比較明顯5 . 1)4(0 x如果將初值改為3131kkxx迭代格式顯然不收斂31)(3)1()2(kkxxkkkkkkkxxxxxxx)1()2(2)1()2()2(12)(73x0 = 1.5x1 = 1.535

30、0706x2 = 1.5321124x3 = 1.5320889x4 = 1.5320889迭代4次,得到滿足精度的解532089. 1x對迭代格式進(jìn)行松弛加速x = 1.5x = 1.5333333x = 1.5320906x = 1.5320889x = 1.5320889迭代4次,得到滿足精度的解532089. 1x對迭代格式進(jìn)行Altken加速可見加速技術(shù)可能將不收斂的迭代法加速為收斂74第七章 非線性方程求根第三節(jié) 牛頓迭代法75牛頓法的基本思想 設(shè)已知方程 f (x) = 0 的近似根為x0，且在 x0附近 f (x) 可用一階泰勒多項(xiàng)式近似，表示為：)()()(000 xxxfx

31、fxf 當(dāng)當(dāng) f (x0) 0 時(shí)時(shí)，方程方程 f (x) = 0 可用線性方程可用線性方程近似代替，即：近似代替，即：0)()(000 xxxfxf76牛頓法的基本思想0)()(000 xxxfxf解線性方程：解線性方程：得：得：)()(000 xfxfxx 取此取此 x 作為原方程的新近似根作為原方程的新近似根 x1，重復(fù)以上步驟重復(fù)以上步驟，得迭代公式：得迭代公式：1()(0,1,)()kkkkf xxxkfx 此式稱為此式稱為牛頓牛頓(Newton)迭代公式迭代公式。77牛頓法的基本思想例 1：用牛頓法求方程用牛頓法求方程0104)(23 xxxf在在 內(nèi)一個(gè)實(shí)根，取初始近似值內(nèi)一個(gè)實(shí)

32、根，取初始近似值。5 . 10 x21 ，解：解：xxxf83)(2 所以迭代公式為：所以迭代公式為：, 2 , 1 , 0)83()104(2231 nxxxxxxnnnnnn列表計(jì)算如下：列表計(jì)算如下：1.365230011.365262011.37333331.5 3 2 10 nnx78牛頓法的幾何意義 方程f (x) = 0 的根就是曲線 y= f (x) 與x 軸交點(diǎn)的橫坐標(biāo)x*，當(dāng)初始值x0 選取后，過(x0 , f (x0 ) 作切線，其切線方程為：)()(000 xxxfxfy )()(0001xfxfxx 它與它與x軸交點(diǎn)的橫坐標(biāo)為：軸交點(diǎn)的橫坐標(biāo)為：79牛頓法的幾何意義

33、設(shè)xk 是x* 的第k 次近似值，過(xk , f (xk )作y= f (x)的切線，其切線與x軸交點(diǎn)的橫坐標(biāo)為：)()(1k kk kk kk kx xf fx xf fx xx x 若過曲線若過曲線 y= f (x)上的點(diǎn)上的點(diǎn) P ( xk , f ( xk )引切線，引切線，該切線與該切線與 x 軸交點(diǎn)的橫坐標(biāo)即為由牛頓迭代公式軸交點(diǎn)的橫坐標(biāo)即為由牛頓迭代公式求求得的得的 xk+1 , 因此牛頓迭代法也稱牛頓切線法。因此牛頓迭代法也稱牛頓切線法。80牛頓法的幾何意義81例5.用Newton迭代法求方程的根:0133xx解:13)(3xxxf設(shè)33)(2xxf由Newton迭代法)()

34、(1kkkkxfxfxx得取初值,5 .00 xx0 =0.5;x1 =0.3333333333x2 =0.3472222222x3 =0.3472963532x4 =0.3472963553331323kkkkxxxx迭代四次精度達(dá)10-8 1kx*x)(xfy kx82牛頓法的幾何意義 用牛頓迭代法求方程用牛頓迭代法求方程 x = e x 在在 x =0.5 附近的根。附近的根。例例2:2:將原方程化為將原方程化為 x e x = 0，則則 f(x)= x e x ， f (x)=1+ e x, 解：解： 牛頓迭代格式為牛頓迭代格式為kkxxkkkeexxx 11取取 x0 =0.5，迭代

35、得迭代得:x1=0.566311, x2=0.5671431, x3=0.567143383牛頓迭代法的收斂速度)()()(xfxfxx 牛頓迭代法的迭代函數(shù)為：牛頓迭代法的迭代函數(shù)為：由于由于f (x*) = 0， 所以當(dāng)所以當(dāng) 時(shí)時(shí), ,0)( xf )()()(0)()()()( xfxfxxfxfxfx 不一定為不一定為 0所以所以f (x)在在x*附近是平方收斂的。附近是平方收斂的。84重根情況當(dāng)x*為m重根時(shí)， f (x)可表為:)()()(xgxxxfm )()()()()()()(1k kk kk kk kk kk kk kk kk kk kx xg gx xx xx xg g

36、m mx xg gx xx xx xx xf fx xf fx xx x )()()()()()(x xg gx xx xx xg gm mx xg gx xx xx xx x 85重根情況令令 xxekk則則)()()(*11kkkkkkkkxgexmgxgeexxe 1()limlim1()()110kkkkkkkkeg xemg xe g xm 86計(jì)算重根的牛頓迭代法對于有重根的情況采用如下迭代格式：1()()kkkkf xxxmfx 用牛頓法求方程的重根時(shí)僅為線性收斂。用牛頓法求方程的重根時(shí)僅為線性收斂。87計(jì)算重根的牛頓迭代法 例：方程 的有二重根，用牛頓迭代法和重根的牛頓迭代法分

37、別求方程的近似根。迭代初值為1.5。04424 x xx x88計(jì)算重根的牛頓迭代法例：用牛頓迭代法求 f (x)=(x-1)sin(x-1)+3x-x3+1=0 在0.95 附近的根。取取 x0 = 0.95 用牛頓迭代法求得的用牛頓迭代法求得的 xk 見下表見下表。k xk01230.950.97442790.98705830.9934878k xk4560.99673280.99835760.999190189計(jì)算重根的牛頓迭代法由重根數(shù)由重根數(shù) m 為為 2 , 用加速法用加速法1()()kkkkf xxxmfx x0=0.95 x1=0.9988559 x2=x3=1收斂速度大大加快

38、于直接用牛頓迭代公式。收斂速度大大加快于直接用牛頓迭代公式。得：得：90)()(1kkkkxfxfxxNewton迭代法需要求每個(gè)迭代點(diǎn)處的導(dǎo)數(shù))(kxf 復(fù)雜！得中的近似替代用,)(0kkxxfx)()(01xfxfxxkkk-(12)-(13)這種格式稱為簡化Newton迭代法精度稍低)(kxf 如果用數(shù)值導(dǎo)數(shù)代替11)()()(kkkkkxxxfxfxf三、Newton迭代法的變形91則Newton迭代法變?yōu)?()()()(111kkkkkkkxxxfxfxfxx-(14)這種格式稱為弦截法收斂階約為1.6181kx11)()(,kkkkABxxxfxfKAB的斜率為如圖11)()(ta

39、nkkkkxxxfxf*x)(xfy 1kxkxAB)()()()(111kkkkkkkxxxfxfxfxx)(cotkkxfx)(cotkxf幾何意義92例6.用簡化Newton法和弦截法解例(5)中方程的根，0133xx解:13)(3xxxf設(shè)33)(2xxf由簡化Newton法)()(01xfxfxxkkk3313203xxxxkkk并和Newton 迭代法比較由弦截法)()()()(111kkkkkkkxxxfxfxfxx93x0=0.5x1= 0.3333333333x2 = 0.3497942387x3 = 0.3468683325x4 = 0.3473702799x5 = 0.3

40、472836048x6 = 0.3472985550 x7 = 0.3472959759x8 = 0.3472964208x9 = 0.3472963440 x10 = 0.3472963572x11 = 0.3472963553x0=0.5;x1=0.4;x2 = 0.3430962343x3 = 0.3473897274x4 = 0.3472965093x5 = 0.3472963553x6 = 0.3472963553簡化Newton法由弦截法要達(dá)到精度10-8 簡化Newton法迭代11次弦截法迭代5次Newton迭代法迭代4次94無論前面哪種迭代法：Newton迭代法簡化Newton

41、法弦截法0)arctan()(xxf0 x精確解為Newton迭代法)1(arctan21kkkkxxxx10 x取初值x0 = 2x1 = -3.54x2 = 13.95x3 = -279.34x4 = 122017是否收斂均與初值的位置有關(guān)如20 x若取初值x0 =1x1 = -0.5708x2 = 0.1169x3 = -0.0011x4 = 7.9631e-010 x5 = 0收斂發(fā)散95|)(|)(|:1kkxfxf入要求如果在構(gòu)造迭代法時(shí)加建立迭代法因此考慮引入一因子 ,)()(1kkkkxfxfxx使得選擇一個(gè)在迭代時(shí),|)(|)(|1kkxfxf-(15)這種方法稱為Newto

42、n下山法，稱為下山因子的選取方式的順序，按322121211成立為止直到|)(|)(|1kkxfxf96例7.99.0,3)(03xxxxf取初值求解方程5110|nnxx解:1.先用Newton迭代法1)(2xxf)()(1kkkkxfxfxx)1(3323kkkkxxxx)1(332003001xxxxx50598.32)1(332113112xxxxx69118.2115689.15x4 = 9.70724 x5 = 6.54091 x6 = 4.46497 x7 = 3.13384 x8 = 2.32607 x9 = 1.90230 x10= 1.75248x11= 1.73240 x

43、12= 1.73205x13= 1.73205)1(332223223xxxxx迭代13次才達(dá)到精度要求972.用Newton下山法,結(jié)果如下k=0 x0 =-0.99 fx0 =0.666567k = 1 x1 =32.505829 f(x) = 11416.4 w =0.5 x1 =15.757915 f(x) = 1288.5 w =0.25 x1 =7.383958 f(x) =126.8 w =0.125 x1 =3.196979 f(x) =7.69 w = 0.0625 x1 =1.103489 f(x)=-0.655k = 2 x2 = 4.115071 f(x) =19.1 w = 0.5 x2 = 2.60928 f(x)=3.31 w =0.25 x2 =1.85638 f(x)=0.27k = 3 x3 =1.74352 f(x)=0.023k = 4 x4 = 1.73216 f(x)=0.00024k = 5 x5 = 1.73205 f(x)=0.00000k = 6 x6 = 1.73205 f(x)=0.000000)(kkxfxk