數(shù)值分析方法第三章

1、第二章第二章 非線性方程求根非線性方程求根 /* Solutions of Nonlinear Equations */求求 f (x) = 0 的根的根2022-4-131求根問題包括下面三個問題：求根問題包括下面三個問題： 根的存在性：即根的存在性：即f(x)=0有沒有根？若有，有有沒有根？若有，有 幾個根？幾個根？ 哪兒有根？確定有根區(qū)間哪兒有根？確定有根區(qū)間 根的精確化：已知一個根的近似值后，能否根的精確化：已知一個根的近似值后，能否 將它精確到足夠精度？將它精確到足夠精度？問題的提出方程：y = f (x)方程的根：x = ? y = 0 xy0y = f (x)x = ?y = 3

2、x - 2(x = 2/3)y = x2 - 2x + 1 (x = 1)y = 6.74 10-3 - exp(-5000/x)非線性問題 (x 1000)2022-4-133科學(xué)技術(shù)中常遇到高次代數(shù)方程或超越方程的求根問題?？茖W(xué)技術(shù)中常遇到高次代數(shù)方程或超越方程的求根問題。大于大于4次的代數(shù)方程無求根公式。次的代數(shù)方程無求根公式。因此需要研究函數(shù)方程求根問題的數(shù)值方法。因此需要研究函數(shù)方程求根問題的數(shù)值方法。例如：求解高次方程例如：求解高次方程 7x6-x3+x-1.5=0的根。的根。ex-cos( x)=0求解含有指數(shù)和三角函數(shù)的超越方程的根。求解含有指數(shù)和三角函數(shù)的超越方程的根。Why

3、 數(shù)值計算 ？根：數(shù)值analytical methodnumerical method無解析方法2022-4-135求實根近似值的常用方法求實根近似值的常用方法1、二分法、二分法2、迭代法、迭代法3、牛頓法、牛頓法4、弦截法、弦截法2022-4-136 二分法二分法 /* Bisection Method */原理：原理：若若 f Ca, b，且，且 f (a) f (b) 0，則，則 f 在在 (a, b) 上必有一根。上必有一根。問題求連續(xù)函數(shù) y = f(x) 在區(qū)間a,b上的唯一實根 y = 0 xyy = f(x)ab分析1. “實根”兩側(cè)f(x)反號2. “實根”同側(cè)f(x)同號

4、3. 若: f(x1)f(x2)反號，則“實根”在x1和x2之間方法逐步縮小“有根區(qū)間”2022-4-1372022-4-13 執(zhí)行步驟執(zhí)行步驟1計算計算f (x)在有解區(qū)間在有解區(qū)間a, b端點處的值端點處的值，f (a)，f (b)。2計算計算f (x)在區(qū)間中點處的值在區(qū)間中點處的值f (x0)。3判斷若判斷若f (x0) = 0，則則x0即是根，否則檢驗即是根，否則檢驗：（1）若若f (x0)與與f (a)異號異號，則知解位于區(qū)間則知解位于區(qū)間a, x0， b1=x0, a1=a;（2）若若f (x0)與與f (a)同號同號，則知解位于區(qū)間則知解位于區(qū)間x0, b， a1=x0, b1

5、=b。反復(fù)執(zhí)行步驟反復(fù)執(zhí)行步驟2、3，便可得到一系列有根區(qū)間便可得到一系列有根區(qū)間：(a, b), (a1, b1), , (ak, bk), 的一個正的近似解的一個正的近似解 （精確到（精確到0.1）x2-2x-1=0- +2 3f(2)0 2x13- +2 2.5 3f(2)0 2x12.5- +2 2.25 2.5 3f(2.25)0 2.25x12.5- +2 2.375 2.5 3f(2.375)0 2.375x12.5- +2 2.375 2.4375 3f(2.375)0 2.375x12.4375求方程求方程每個有根區(qū)間的長度都是前一個有根區(qū)間長度的一半abx1x2abWhen

6、 to stop?11xxkk 2)(xf 或或不能保證不能保證 x 的精度的精度x* 2xx*2022-4-1310誤差誤差 分析：分析：02a bx有誤差有誤差02b a|xx*|第第 k 步產(chǎn)生的步產(chǎn)生的 xk 有誤差有誤差12kkba| xx*|對于給定的精度對于給定的精度 ,可估計二分法所需的步數(shù)可估計二分法所需的步數(shù) k ：1lnln12ln2kbabak2022-4-1311第第1步產(chǎn)生的步產(chǎn)生的1x有誤差有誤差14b a|xx*|簡單簡單; 對對f (x) 要求不高要求不高(只要連續(xù)即可只要連續(xù)即可) .無法求復(fù)根及偶重根無法求復(fù)根及偶重根 收斂慢收斂慢 2022-4-1312

7、01)(3xxxf例：求下列方程位于區(qū)間例：求下列方程位于區(qū)間1,1.51,1.5內(nèi)的一個根內(nèi)的一個根kakbkxkf (xk)的符號111.51.25-21.251.51.375+31.251.3751.3125-41.31251.3751.3438+51.31251.34381.3281+61.31251.32811.3203-71.32031.32811.3242-2022-4-1313運用零點定理可以得到如下逐步搜索法：運用零點定理可以得到如下逐步搜索法： 先確定方程先確定方程f(x)=0的所有實根所在的區(qū)間為的所有實根所在的區(qū)間為a,b,從從x0=a 出發(fā)出發(fā), ,以步長以步長 h=

8、(b-a)/n 其中其中n n是正整數(shù)，在是正整數(shù)，在a,b內(nèi)取定節(jié)點：內(nèi)取定節(jié)點： xi=x0ih (i=0,1,2，n) 計算計算f(xi)的值的值, ,依據(jù)函數(shù)值異號及實根的個數(shù)確定隔根依據(jù)函數(shù)值異號及實根的個數(shù)確定隔根區(qū)間區(qū)間, ,通過調(diào)整步長，總可找到所有隔根區(qū)間。通過調(diào)整步長，總可找到所有隔根區(qū)間。 y x a b o 在計算中步長在計算中步長h h要適當(dāng)取小一些要適當(dāng)取小一些, ,若若h h過長則容易丟根過長則容易丟根( (若若在區(qū)間范圍內(nèi)有兩相鄰函數(shù)值符號相同而判定無根在區(qū)間范圍內(nèi)有兩相鄰函數(shù)值符號相同而判定無根) )若間隔若間隔h h值太小值太小, ,則影響計算速度。則影響計

9、算速度。 “數(shù)學(xué)”上是正確的，但作為一種“數(shù)學(xué)方法”，應(yīng)用于實際的“科學(xué)問題”時，不是“放之四海而兼準(zhǔn)”的。 f(x) 在a,b上連續(xù) f(a)f(b)0， f( ) 0嘗試： f(5) 0嘗試： f(10) 0二分法： f(8) = 0 x0y105但是，實際曲線 杜絕教條主義2022-4-1318迭代法迭代法迭代法是數(shù)值計算中一種典型的重要方法，尤其是計算機的普遍使用，使迭代法的應(yīng)用更為廣泛。所謂迭代法就是用某種收斂于所給問題的精確解的極限過程來逐步逼近的一種計算方法，從而可以用有限個步驟算出精確解的具有指定精度的近似解。簡單說迭代法是一種逐步逼近的方法。循環(huán)迭代，用上一輪結(jié)果計算下一輪數(shù)

10、據(jù)。循環(huán)迭代，用上一輪結(jié)果計算下一輪數(shù)據(jù)。 迭代法迭代法 /* Fixed-Point Iteration */思思路路0( )f x 對對于于一一般般形形式式的的方方程程先先將將方方程程化化為為( )xg x0 x再再從從某某一一數(shù)數(shù)出出發(fā)發(fā)，作作序序列列10 1 2(), , ,kkxg xklimkkkxxa若若序序列列有有極極限限，即即0( )( )ag af a則則可可得得即即a亦亦即即 是是方方程程的的根根。0kxx稱稱為為初初始始近近似似值值，稱稱為為k k次次迭迭代代近近似似值值，1( )()kkg xxg x稱稱為為迭迭代代函函數(shù)數(shù)，稱稱為為迭迭代代公公式式。2022-4-1

11、319, 2 , 1 , 0132588. 1133086. 133086. 1135721. 135721. 115 . 11)(5 . 1013132323121301033kxxxxxxxxxxxxxxxxkk重復(fù)步驟，代入，將代入，將代入，將解：改寫方程。用六位有效數(shù)字計算附近的一個根在例：求方程2022-4-132032494. 1432472. 1832588. 1332472. 1733086. 1232473. 1635721. 1132476. 155 . 10kkxkxk311kkxx迭代序列收斂迭代序列收斂2022-4-13213965.1221090252. 64375

12、. 2101.190435 . 109kkxkxk131kkxx迭代序列發(fā)散迭代序列發(fā)散2022-4-1322說明：說明： 迭代函數(shù)不唯一迭代函數(shù)不唯一 迭代序列可能收斂，也可能發(fā)散迭代序列可能收斂，也可能發(fā)散 迭代收斂與否不僅與迭代函數(shù)有關(guān)，還與初迭代收斂與否不僅與迭代函數(shù)有關(guān)，還與初始點有關(guān)。始點有關(guān)。 xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p12022-4-1324問題：問題：(1) |g (x)| 1，迭代法是否一定收斂？，迭代法是否

13、一定收斂？(2) |g (x)| 1，迭代法是否一定發(fā)散？，迭代法是否一定發(fā)散？1111110()()( )kkkkkkkkkkxxg xg xgxxxxxxxx迭代序列收斂性的判斷原始方程：f(x) = 0等價方程：x = g(x)設(shè) f(x) = 0的根在 a, b區(qū)間內(nèi)0y = xyxababy = g(x)發(fā)散迭代方程組: y = x, y = g(x) 要求：(1) y = g(x)也在a, b內(nèi)0y = xyxababy = g(x)D DxD Dg(x)D Dg(x) D Dx(2) |g (x)| L1迭代法收斂的充分條件則有：1、存在唯一的實根*, *( *)xxg x2、迭

14、代收斂，且有誤差估計11*1kkkxxxxL011*xxLLxxkk3、證明證明： g(x) 在在a, b上存在實根？上存在實根？令令( )( )xg xxbxga )( )( )0 ,ag aa( )( )0bg bb)(xf有根有根 實根唯一？實根唯一？反證：若不然，設(shè)還有反證：若不然，設(shè)還有 ，則，則)(xgx xx*),*( )()(*)(xxgxgxg 在在和和之間。之間。 *xx0)(1)( gxx*而而xxg*1| )(| 當(dāng)當(dāng)k 時，時， xk 收斂到收斂到 x* ？ |*|kxx|*| )(| )(*)(|111 kkkxxgxgxg0|*|.|*|01 xxLxxLkk ?

15、|11|*|1kkkxxLxx 111| |( *) ( *)| *| *| | *| *|kkkkkkkkxxxxxxxxxxxxL xx ?|1|*|01xxLLxxkk |.| )(| )()(|011111xxLxxLxxgxgxgxxkkkkkkkkkk ?*lim1xgxxxxkkk *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk 可用可用 來來控制收斂精度控制收斂精度|1kkxx L 越越 收斂越快收斂越快小小 例題 能不能用迭代法求解下列方程？如果不能，試將方程改寫成能用迭代法求解的形式 （1）x=(sinx+cosx)/4 （2）x=4-2x (1,2)

16、( )(cossin )/4|( )| |cossin| /41/21g xxxg xxx( )4 2|( )| | 2 ln2| 2ln2 1xxg xg x ( )ln(4)/ln2111|( )| |14ln22ln2g xxg xx 迭代法的結(jié)束條件迭代法的結(jié)束條件1kkxx例 ：求方程 在0, 0.5內(nèi)的根，精確到10-5。0133 xx2022-4-1331牛頓法牛頓法取 在 x0 做一階Taylor展開將 看成高階小量，則有：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 每一步迭代都有 ，而 且 *limxxkk ，則 的根。1()()kkkkf

17、xxxfx（牛頓公式）20000)(! 2)()()()(xxfxxxfxfxf ， 在 x0 和 x 之間()0kfx2022-4-1332線性線性 /* linear */2022-4-1333牛頓法幾何表示牛頓法幾何表示x*x0 x1x2xyf(x)()()kkkf xxxfx切線切線 /* tangent line */2022-4-13( )yf x( )yf xxx(, ()kkp xf x牛頓公式實際上就是用曲線 在 點處的切線與 軸的交點作為曲線 與 軸交點的近似342022-4-13牛頓法例題牛頓法例題例 用牛頓法求解方程xxe在00.5x 附近的根5(10 )解：將方程xx

18、e轉(zhuǎn)化為等價方程10 xxe 令( )1xf xxe，則牛頓迭代公式為11(1)1kkkxxkkkkkxkkx exexxxexx(0,1,2,)k 352022-4-1300.5x ，迭代結(jié)果如下表取初值kkx012340.50.57102040.56715550.56714330.5671432*0.567143x 可見，牛頓公式的收斂速度是相當(dāng)快的。362022-4-1337牛頓法的收斂性牛頓法的收斂性對方程對方程f (x)=0，若存在區(qū)間，若存在區(qū)間a, b，使，使(1) f (x)在在a, b上連續(xù)；上連續(xù)；(2) f (a) f (b) 0；則；則Newtons Method產(chǎn)生的

19、序列產(chǎn)生的序列 xk 收斂到收斂到f (x)=0 在在a, b上的唯一實根。上的唯一實根。2022-4-1338牛頓法收斂性示意圖牛頓法收斂性示意圖2022-4-1339Newton法的收斂性依賴于x0 的選取。x*x0 x0 x0 Newton - Raphson Method下山法下山法 /* Descent Method */ Newtons Method 局部微調(diào)：局部微調(diào)：初值選擇不當(dāng), 牛頓迭代法發(fā)散, 怎么辦 ?迭代目的: f(x) = 0。因此希望迭代過程中 | f(x) | 越來越小。1()()kkkkf xxxfx牛頓迭代公式但 | f(xk+1) | | f(xk) |原

20、理：原理：若由若由xk 得到的得到的 xk+1 不能使不能使 | f | 減小，則在減小，則在 xk 和和 xk+1 之間找一個更好的點之間找一個更好的點 ，使得，使得 。1 kx)()(1kkxfxf xkxk+1,)1(1kkxx 1, 0 )()()1 ()()(1kkkkkkkkxfxfxxxfxfxx 0 1， 稱為“下山因子” = 1 時就是時就是Newtons Method 公式。公式。 當(dāng)當(dāng) = 1 代入效果不好時，將代入效果不好時，將 減半計算。減半計算。牛頓下山法應(yīng)用舉例計算 f(x) = x3 - x - 1 = 0 在0, 2之間的實根迭代公式131231 kkkkkx

21、xxxxkkkxxx)1(11 取初值 x0 = 0.6，得：9 .171 x絕對值較小新的迭代值f(0.6) = -1.384 f(17.9) = 5716.4 0.5x1 = 9.25f(x1) = 781.20 0.25x1 = 4.925f(x1) = 113.53 0.125x1 = 2.7625f(x1) = 17.319 0.0625x1 = 1.68125f(x1) = 2.0710 0.03125x1 = 1.140625f(x1) = -0.65664 Newton - Raphson Method 求復(fù)根求復(fù)根 /* Finding Complex Roots */ Ne

22、wton 公式中的自變量可以是復(fù)數(shù)公式中的自變量可以是復(fù)數(shù)記記 z = x + i y, z0 為初值，同樣有為初值，同樣有)()(1kkkkzfzfzz kkkkkkDiCzfBiAzf )(,)(設(shè)設(shè)代入公式，令實、虛部對應(yīng)相等代入公式，令實、虛部對應(yīng)相等，可得，可得;221kkkkkkkkDCDBCAxx .221kkkkkkkkDCCBDAyy 2022-4-1344牛頓法優(yōu)缺點牛頓法優(yōu)缺點Newton法具有收斂快，穩(wěn)定性好，精度高等優(yōu)點，是求解非線性方程的有效方法之一。但它每次迭代均需計算函數(shù)值與導(dǎo)數(shù)值，故計算量較大。而且當(dāng)導(dǎo)數(shù)值提供有困難時， Newton法無法進(jìn)行。2022-4-

23、1345弦割法弦割法)(kxf 11)()(kkkkxxxfxf弦割法迭代格式)()()(111kkkkkkkxfxfxxxfxx 在牛頓迭代格式中，將曲線 上點 的切線斜率 ，改為其上兩點連線(弦)的斜率( )yf x(,()kkxf x2022-4-1346弦弦割割法法幾幾何何表表示示x0Xx1 x2 x3YP0P2 P1x11011 ,.,kkkkkxxxxxxx弦 截 法 在 求時 要 用 到 前 面 兩 步 的 結(jié) 果需 兩 個 初 值， 而 牛 頓 切 線 法 在 計 算時 ， 只用 到 前 一 步的 值 。割線割線 /* secant line */x0 x1切線切線 /* ta

24、ngent line */割線割線 /* secant line */收斂比收斂比Newtons Method 慢，且對初值要求同樣高。慢，且對初值要求同樣高。2022-4-1348例題分析例題分析用弦割法求方程10 xxe 在0.5x 附近的根（ ）410解：取010.5,0.6xx由迭代公式求得kkx1kkxx00.510.620.567540.0324630.567150.0003640.567140.00001故*0.56714x ，滿足精度要求迭代過程的收斂速度迭代過程的收斂速度 設(shè)由某方法確定的序列收斂于方程的根，如果存在正實數(shù)p，使得Cxxxxpkkk*1*lim（C為非零常數(shù)）

25、定義：則稱序列 收斂于x*的收斂速度是p階的，或稱該方法具有p 階斂速。2022-4-13492022-4-1350當(dāng)p = 1且0C1時，稱方法為超線性收斂。 當(dāng)p = 2時，稱方法為平方（二次）收斂；定理定理 設(shè)設(shè) x* 為為x = g(x) 的根的根，若，若 ，且，且 ，則，則 xk+1 = g(xk) 在在 附近附近 p 階收斂。階收斂。0*)(.*)()1( xgxgp0*)()( xgp*x證明：證明：( )1( )()()( *)( *)(*).(*)!()*(*)!ppkkkkkppkkgxg xg xg xxxxxpgxxxp*()()*1*()()limlim!ppkkpk

26、kkxxggxppxx簡單迭代的收斂速度簡單迭代的收斂速度*1()()()()kkkkxxg xg xgxx*1*limlim()()kkkkkxxgg xxx( )0g x當(dāng)簡單迭代法是線性收斂 ( ) ,( )0,xxa bx迭 代 過 程 的 收 斂 速 度 依 賴 于 迭 代 函 數(shù) g的 選取 。 如 果 當(dāng)時 g則 該 迭 代 過 程 只可 能 是 線 性 收 斂 。2022-4-1353牛頓法的收斂速度牛頓法的收斂速度 12* ( ) ,( )0,() ()( ) g( ) ( )( )( ) g ( ) ( )( )(kkkkxxa bxfxxxfxfxxxfxfxfxxfxx

27、fxfx迭 代 過 程 的 收 斂 速 度 依 賴 于 迭 代 函 數(shù) g的 選取 。 如 果 當(dāng)時 g則 該 迭 代 過 程 只可 能 是 線 性 收 斂 。 對 牛 頓 公 式其 迭 代 函 數(shù) 為由 于假 定是的 一 個 單 根 ， 即*)0,()0,()0,fxxx則由 上 式 知 g由 上 述 定 理 知 ， 牛 頓 法 在 根的鄰 近 至 少 是 平 方 收 斂 的 。*2* ( )0( 2)( )=()( )( ()0)( )( )g ()lim g ( )lim( )( )( )( )1 g ()1-0( )0mxxxxxf xmf xxxq xq xf x fxxxfxf x

28、fxfxxmf x假定 是的重根，即將，代入上式得 用牛頓迭代法對求重根只具有線性收斂。 設(shè)由某方法確定的序列收斂于方程的根，*1*limkkkxxCxx（0C fzero(fz,-5) ans = -5.1926 fzero(fz,1) ans = 0.19265292x function y=func11_1(x)y=4*cos(x)-x; fzero(func11_1,3)ans = 1.2524 fzero(func11_1,-4)ans = -3.5953 fzero(func11_1,-4,-3)ans = -3.5953在該區(qū)間內(nèi)求解在該區(qū)間內(nèi)求解 fzero(sin(x)-0.

29、1*x,6)ans = 7.0682 fzero(sin(x)-0.1*x,2,6)ans = 2.8523Humps函數(shù) 2211( )6(0.3)0.01(0.9)0.04y xxx在區(qū)間在區(qū)間-0.5,1.5的解的解Humps函數(shù) 2211( )6(0.3)0.01(0.9)0.04y xxx fplot(humps,-0.5,1.5); hold on x1=fzero(humps,-0.5)x1 = -0.1316 x2=fzero(humps,1.5)x2 = 1.2995 plot(x1 x2,0 0,o);hold offroots(p) 多項式p的所有復(fù)根。例 x3+2x2-

30、5的根 roots(1 2 0 -5)ans = -1.6209 + 1.1826i -1.6209 - 1.1826i 1.2419 求解的方法很多，現(xiàn)成的軟件更多，而且會越來越多。為什么還要學(xué)習(xí)求解的方法？“軟件”不能解決所有實際問題，常常需要“自力更生”。關(guān)于方程求根問題的小結(jié) 二分法：f(x)連續(xù)、 f(a) f(b) 0 、一個實根簡單，速度慢 迭代法：|g (x)| -2區(qū)間內(nèi)的實根。困難牛頓法：導(dǎo)數(shù)難以計算；迭代法：難以表達(dá)為x = g(x)。最關(guān)鍵的是函數(shù)性質(zhì)不清楚，函數(shù)連續(xù)性？有多少個根？所以連二分法都難以應(yīng)用。n1n2n3x0 x2a1襯底包層上界面下界面波導(dǎo)層波導(dǎo)與襯底的交界面-下界面，臨界角波導(dǎo)與包層的交界面-上界面，臨界角12c13c2121sincnn3131sincnn23nn假設(shè)：1213cc當(dāng)平面波的入射角1變化時，可產(chǎn)生不同的波型：導(dǎo)模和輻射模導(dǎo)模n1n2n3x0 x2a1襯底包層11213cc當(dāng) 時，即32111cossinnnnn導(dǎo)模：平面波在上下界面都產(chǎn)生全反射上界面下界面波導(dǎo)層TETE模本征方程（模本