數(shù)值分析第四章學(xué)習(xí)小結(jié)

1、節(jié) 4.1 非線性方程的迭代解法和 4.2 非線性方程組的迭代解法。本章出它的根的近似值，本章將要介紹幾種常用的有效的數(shù)值求根方法，它們都屬于迭代法，因而還要討論這些方法的收斂性和收斂速度。4.1.1 對分法（1）基本思想：確定方程有根的區(qū)間；將區(qū)間逐次分半縮小，得到一個(gè)區(qū)間長度以1/2 的比例減小的 含根區(qū)間序列 ，在給定根的誤差界時(shí)，利用長度趨于零的特點(diǎn)，xk1 的等比2數(shù)列的收斂速度相同。ababk(2)迭代終止條件或者b a x 12 x skk( ) f x2k2kk(3)二分法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：程序簡單，總能求出近似根，對要求不高。f(x)缺點(diǎn)：收斂速度慢，只能求單根和奇數(shù)重根，不能

2、求偶重根，復(fù)根。二分法一般用于對根求近似根。4.1.2 簡單迭代法及其收斂性迭代法的基本思想:f(x)0 x (x)xk1(x ),k 0,1,2,k.之逐步精確化，最后得到滿足精度要求的解。迭代法的基本思想是將隱式方程的求根問題歸結(jié)為計(jì)算( )x x一組顯式公式( )x xk1k 產(chǎn)生的序列 收斂于 ，x x收斂性：若由迭代公式x (x k 1,2,3.k1kk則 是原方程的根。x收斂條件：a非局部收斂性定理：設(shè)函數(shù) (x)Ca,b，在（a，b）內(nèi)可導(dǎo)，且滿足兩個(gè)條件：（1）當(dāng)xa,b(x)a,bxa,b時(shí)， (x) L1，其中L 為一常數(shù)。則有如下結(jié)論：（1）方程在上有唯一的根( ) ,

3、x xa b 產(chǎn)生的序列且x a,b0 x x( )xa b , k1kk收斂于kL（3）成立誤差估計(jì)式或ssx x xx x x1L110Lk1kkk這種形式的收斂定理稱為大范圍收斂性定理，但當(dāng)條件不夠充分時(shí)，預(yù)先指定一個(gè)區(qū)間常常是不可能的。b局部收斂性定理( ),( )設(shè)s s x 在包含s ( ) 1 s存在當(dāng)時(shí)，由簡單迭代法產(chǎn)生的序列0 x s,s0 x (x )k1k 且收斂于s。x s s, k4.1.3 簡單迭代法的收斂速度. 成立，則稱序列 收斂于s 具有當(dāng)（某個(gè)正整數(shù)）時(shí)，ek Kcxk1kerk xr 是 r 的大小反映了序列 收斂xkk的快慢程度，r 越大收斂越快。r=1

4、 時(shí)稱序列線性收斂的，r=2 時(shí)，為平方收斂的。線性收斂的條件：設(shè)函數(shù) (x)Ca,b，且滿足如下條(x)C(a,b)xa,b時(shí)，(x)a,b；（2）當(dāng)xa,b時(shí)， (x) L1，其中L 為一常數(shù)。 則對任取的于方程產(chǎn)生的序列收斂x a,b( )x xxa b , 0k1kk 在內(nèi)的唯一的根時(shí) 是線性收斂x (x) a,bx s0 xk的。m 階收斂的條件： 設(shè)在包含 s 的某個(gè)開區(qū)間內(nèi)連續(xù)( ), ( )s sx(m)（ 如果則存在，當(dāng) ( ) 0( 1,2, , ( ) 0m2s i m( ) s 0(i)m 但產(chǎn)生的序列x s s, x s0 x x( )xa b , 0k1kk以 m

5、階收斂速度收斂于s。4.1.4 迭代的加速過程1.加權(quán)迭代法: x (x k1k1L1或者改進(jìn)： x x xx k1 (x )Lx 1Lk11L1Lk1kkk缺點(diǎn)：L值的確定需要函數(shù)的迭代信息，不便于實(shí)際應(yīng)用。x s L,k2x s L 2Aitken 加速法：設(shè)序列 線性收斂于s，則k1x sxsxkk1kx s x s(x x)2k1k2 x xs2k1kx s x sk2 x x x2k1kk1k2k1k3.Steffensen 迭代法( ),( )y x z y迭代公式： kkkk(y x )2x x ,k kkk12y xk z.kkk無論迭代法是否收斂于s，Steffensen迭代

6、法都能以不低于二階的收斂速度收斂于s。4.1.5 Newton法推導(dǎo)f(x)0 h(x)f(x)0h(s)0( )0 sh(x)f(x)x x(x )fx x ,kf(x )k1k推出迭代公式kk Newton法可求方程的實(shí)數(shù)根和復(fù)數(shù)根，求實(shí)數(shù)根時(shí)有明顯的幾何 上的點(diǎn)(x ,f(x )作該曲線的切線，y f(x)xkkk此曲線與X軸相交的交點(diǎn)的橫坐標(biāo)就是Newton法迭代序列的第k+1個(gè)元素 ，因此Newton法又稱為切線法。xk1局部收斂性定理：設(shè) s 是方程的根，在包含 s 的某個(gè)開區(qū)間內(nèi)連續(xù)且( )x x( )f x，則存在，當(dāng)時(shí)，由Newton法產(chǎn)生的序列f (x) 00 x s,s0

7、 收斂于s；若且，則序列 是平方收斂的。xf (s) 0 x s0 xkk 在區(qū)間 上存在二階連續(xù)導(dǎo)數(shù)，且f(x)a,bf(a)fb)0在區(qū)間 f (x)a,bxa,b時(shí)，。則有Newton法產(chǎn)f (x) 0 x a,b, f (x )f (x ) 0000 生的序列 單調(diào)收斂于方程在 內(nèi)唯一的根s，并且至少( ) , x a b xxk是平方收斂的。4.1.6求方程m重根的Newton法設(shè)s是方程的m重根（m2 在s的某鄰域內(nèi)有mf x( )( )x xf(x)階連續(xù)導(dǎo)數(shù)，這時(shí)(x) xf (s) f(s) fs( ) 0,fs( ) 0(m1)(m)f (x).1( ) ,( ) 1s s

8、 s m（2）變形的Newton 法(x)令 (x) xf (x)道重根的重?cái)?shù)（3）若s 是方程迭代函數(shù)：g(x) x迭代公式：x x 的 m 重根，則s 為u(x)的單根。f(x)f(x)kkk1k2kkkf(x ) f(x )kk1f(x x x )fkkkf(x ) f(x )kkkk1f(s)0 當(dāng)x ,x Ix0k.遠(yuǎn)是割線上的一點(diǎn)。2.迭代公式：x x 00k1k100f(x x x )kkk1kk03.幾何意義：在區(qū)間a,b（1）f(a)fb)0。則由單點(diǎn)割線x ,x a,b010001xkff12n1 1f( )212n2x212nn F(x)0fx x x x x x( ,

9、, n212n12nii1.(x) F(x) 2min (x)min F(x) 24.2.2簡單迭代法R R設(shè)F(x):方程組：nnF(x)0 xG(x)（）Fx(k1)2.收斂性：非局部收斂性定理G(x ),k 0,1,2,G(k)設(shè)在閉區(qū)域把 映入它G:D R RD DDnn00自身，即在 上壓縮映射，即存在常數(shù)，L（0,1）（D DD000使對任意的有則有下列結(jié)論：x,yDG(x)G(y) L x y0 x D( )k（1）對任取的，由迭代公式產(chǎn)生的序列，且收斂于x(0) D00方程內(nèi)的唯一解 ；xk（2）成立誤差估計(jì)式或x x( ) xxk1LLx x x x(k)(k)(k1L實(shí)際計(jì)

10、算時(shí)，可預(yù)先給定精度水平，當(dāng)?shù)蛄袧M足0 x x(k)(k時(shí)停止迭代，取當(dāng)前的 作為方程組的近似解。(k)xx(k)4.2.3 Newton1.基本思想將非線性方程組線性化，構(gòu)造迭代格式。f(x,y)0(x,y)0設(shè)為方程組解的一組初始近似解。(x ,y )1f002fff (x,y) f (x ,y ) (xx ) (y y )11xy110000fff (x,y) f (x ,y )(xx )(y y )22xy220000.x(k1)F x x F(x ) ( ), 0,1,2,k(k)(k) 1(k)3.收斂性：條件：連續(xù)可微，非奇異；F(x)F (x ) 結(jié)論： 超線性收斂于xxk

11、 二次連續(xù)可微，則 平方收斂于k若F(x)xx4.Newton算法x xx(k)x F(x ) F(x )(k)(k(k)(k) 1(k)x(k x x( )( )F x( ) x( ) F x( ) ( )( )kkkkk5.Newton法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：收斂快，一般都能達(dá)到平方收斂；缺點(diǎn)：對初值要求較苛刻，且要求4.2.4 離散Newton 法的各個(gè)偏導(dǎo)數(shù)存在。f (x)i1.基本思想：用差商代替導(dǎo)數(shù)。(x h e ) f (x )f (x ) f(k)(k)(k)(k)ijjh(k)iixjj (f x) ( )f x( )(e f x( ) ( )h e(k)f xh( )(k)(k)

12、kkk111111nnhh(k)(k)1n( ) ( , )F xJ x h(k)(k)(k)(x h e ) f (x )f (x h e ) f (x ) f(k)(k)(k)k( )k( )k( )n11nnnnnhh(k)(k)1n2.迭代公式：3. 的選取x(k1) x J(x ,h ) F(x ),k 0,1,2,(k)(k)(k) 1(k)h(k)(1)保證:h x h e , j ,n(k)(k)(k)jjj(2)Newton-Steffensen 方法，?。?為非零常數(shù)；h c F(x )c(k)(k)jjjj=1,2，n）（3） 也可取與k 無關(guān)的常數(shù)。h(k)j.8.設(shè)

13、s 是方程的根，在 s 的某個(gè)鄰域內(nèi)連續(xù)，并且f(x)0f(x)f (x)4f(x)。令 (x) x為使迭代法f(x) 0h(x2x (x )(k 0,1,)k1f (x)f (x)k能夠至少以三階收斂速度收斂于s，則應(yīng)如何選取函數(shù) ？h(x)解：由定理 4.4 可知，至少三階收斂速度于 s。則，(s) 0(1)f(x)(s)0，(s) 0。令u(x)，于是(x) xu(x)h(x)u(x)2。(2)(3)f (x)通過求導(dǎo)可得：( ) 1 ( ) ( ) ( ) 2 ( ) ( ) ( ) 0; u x h x u x h x u x u x x ( )u (x)h (xu (x)2h(xu

14、(xu(x) x2h(xu(x) 2h(xu(xu (x)0;2 ( ) 0. xf(2)(x)h(x)2f (x)9.試分別用割線法和單點(diǎn)割線法求方程 xsinx1的根，要求。x x / x 6kk1k解：令 f(x) xsinx1， f(0)10, f(1)sin10，所以 f(0)f(1)0。f(x x x )（1）割線法：迭代公式x x ,k 0,1,2,k1kkf(x ) f(x )k1kkk1由于 f(0)f(1)0， f(x) xsinx1在0,1 只有一個(gè)根。f(x )(x x )取x 0,x 1，則x x 0.543044125100(x ) f(x )0 f10101.f(

15、x )(x x )0 0.543044125f(x ) f(x )0.059788703(0.5430441251)0.0597887030.841470984x x 1121100.508092841f(x )(x x )x x 0.508092841221f(x ) f(x)32210.543044125)0.0053952610.0597887030.510985750算到x 0.510973429即可。5（2）單點(diǎn)割線法f(x) xsinx1，f(x)1cos, f(x)sinx，滿足定理4.9的4個(gè)條件：（1）f(0)f(1)0； （2）當(dāng)；x0,1, f (x)0(2)在區(qū)間, f

16、 (x)0且x ,x 0,1f (1)f (1)0, f (1)f (x )0011取x 0,x 1，由單點(diǎn)割線法產(chǎn)生的迭代公式01f(x x x ) 由單點(diǎn)割線法產(chǎn)生的序列 單調(diào)收x x ,k 0,1,2,0 xkkf(x ) f(x )k1kkk0斂于方程在 內(nèi)唯一的根。0,1f(x x x )1x x 10f111f(x ) f(x )f(1) f12110f(x x x )1x x 1f22f(x ) f(x )f f3221結(jié)果為s x 0.51097342882.查閱其他參考書，尋找用牛頓法求解多項(xiàng)式方程根的特殊方法，再找一種加權(quán)法。解: (1)Newton法1.基本思想.將非線性

17、方程組線性化，構(gòu)造迭代格式。f(x,y)0(x,y)0設(shè)為方程組解的一組初始近似解。(x ,y )1f002fff (x,y) f (x ,y ) (xx ) (y y )11xy110000fff (x,y) f (x ,y )(xx )(y y )22xy220000 x(k1)F x x F(x ) ( ), 0,1,2,k(k)(k) 1(k)3.收斂性：條件：連續(xù)可微，非奇異；F(x)F (x ) 結(jié)論： 超線性收斂于xxk 二次連續(xù)可微，則 平方收斂于k若F(x)xx4.Newton算法x xx(k)x F(x ) F(x )(k)(k(k)(k) 1(k)x(k x x( )(

18、)F x( ) x( ) F x( ) ( )( )kkkkk5.Newton法的優(yōu)缺點(diǎn)：優(yōu)點(diǎn)：收斂快，一般都能達(dá)到平方收斂；缺點(diǎn)：對初值要求較苛刻，且要求(2)離散Newton 法的各個(gè)偏導(dǎo)數(shù)存在。f (x)i1.基本思想：用差商代替導(dǎo)數(shù)。(x h e ) f (x )f (x ) f(k)(k)(k)(k)ijjh(k)iixjj (f x) ( )f x( )(e f x( ) ( )h e(k)f xh( )(k)(k)kkk111111nnhh(k)(k)1n( ) ( , )F xJ x h(k)(k)(k)(x h e ) f (x )f (x h e ) f (x ) f(k)

19、(k)(k)k( )k( )k( )n11nnnnnhh(k)(k)1n2.迭代公式：3. 的選取x(k1) x J(x ,h ) F(x ),k 0,1,2,(k)(k)(k) 1(k)h(k).(1)保證:h x h e , j ,njcjjjj=1,2，n）hj簡化牛頓法，也稱平行弦法. 其迭代公式為:k1kk迭代函數(shù):若在根 附近成立 (x) 1 (x) 1，即取0 xf (x)2,則迭 x代法xk1kk1在x，則稱為簡化牛ck1kkf0 x.牛頓法收斂性依賴初值 的選取如果 偏離所求根 較遠(yuǎn)，則x0 x0 x牛頓法可能發(fā)散.為了防止迭代發(fā)散，對迭代過程再附加一項(xiàng)要求，即具有單調(diào)性:

20、f(x ) f(x ). 滿足這項(xiàng)要求的算法稱下山法.k1k將牛頓法與下山法結(jié)合起來使用，即在下山法保證函數(shù)值穩(wěn)定下降的前提下，用牛頓法加快收斂速度.f(x )將牛頓法的計(jì)算結(jié)果與前一步的近似值適當(dāng)加x x k( )f xk1kk權(quán) 平 均 作 為 新 的 改 進(jìn) 值 , x x )x ,其 中k1k1kf(x )(0 1) 稱為下山因子,即稱為牛頓 x x (k k( )f xk1kk下山法.選擇下山因子時(shí)從 1 下降條件成立為止.f(x ) f(x k1k任玉杰習(xí)題 2.81.用拋物線法求方程 f(x)2x 5x10的一個(gè)實(shí)根的近似值x 3k精確到 。6x01,xx在 MATLAB工作窗口

21、輸入x=-2:0.001:2;y=2.*x.3-5.*x-1;plot(x,y);grid,gtext(y=2x3-5x-1)運(yùn)行后得出圖形 1-1，可知區(qū)間內(nèi)有一個(gè)實(shí)根，故取初值(0.5,0).y=2.*x.3-5.*x-1;（3）保存名為paowu.m的M文件(4)在MATLAB工作窗口輸入（5）運(yùn)行后輸出結(jié)果為0.5000 -0.2022 -0.0058提示：根的判別式值為正數(shù).ans=2.0000 0.0478 0.2367 -0.2034提示：根的判別式值為正數(shù).ans=3.0000 0.0012提示：根的判別式值為正數(shù).ans=4.0000 0.0000 0.0000 -0.203

22、4提示：根的判別式值為正數(shù).0.00000.0060 -0.2034 -0.000000ans=5.0000k=50.00000.0000 -0.2034piancha=1.1558e-010 xdpiancha=5.6836e-010 xk=-0.2034yk=0k =5 的根的近似值106值為yk=0，x 的相鄰最小偏差為piancha=1.1558e-010，其相對誤差k為xdpiancha=5.6836e-010.表1-1xdpianchakpianchaxk1.00002.00003.00004.00005.00000.25000.04780.00120.00000.00000.50

23、000.23670.00600.00000.0000-0.2022-0.2034-0.2034-0.2034-0.2034-0.00580.0000-0.000000.9(3,（3）保存名為paowu.m的M文件(4)在MATLAB工作窗口輸入.k,piancha,xdpiancha,xk,yk=paowu(-2,-1,-3,1e-9,1e-9,100)（5）運(yùn)行后輸出結(jié)果為提示：根的判別式值為正數(shù).ans=1.0000提示：根的判別式值為正數(shù).ans=2.0000 0.0871提示：根的判別式值為正數(shù).ans=3.0000 0.0086 0.0045 -1.9042提示：根的判別式值為正數(shù).

24、ans=4.0000 0.0001提示：根的判別式值為正數(shù).ans=5.0000 0.0000 0.0000 -1.9042提示：根的判別式值為正數(shù).1.00000.3333 -1.9129 -0.08650.0455 -1.9042 -0.00070.00000.0000 -1.9042 -0.000000ans=6.0000k=60.00000.0000 -1.9042piancha=4.4409e-016xdpiancha=2.3322e-016xk=-1.9042yk=0k =6 的根的近似值109值為yk=0，x 的相鄰最小偏差為piancha=4.4409e-016，其相對誤差k為xdpiancha=2.3322e-016.表2-1kpianchaxk1.00002.00001.00000.08710.00860.00010.00000.00000.33330.04550.00450.00000.00000.0000-1.9129-1.9042-1.9042-1.9042-1.9042-1.9042-0.0865-0.00070.0000-0.000006.00000 x3.求曲線與曲線之間的最小垂直距離處的 xf (x)