数值分析方法第三章

1、第二章第二章 非线性方程求根非线性方程求根 /* Solutions of Nonlinear Equations */求求 f (x) = 0 的根的根2022-4-131求根问题包括下面三个问题：求根问题包括下面三个问题： 根的存在性：即根的存在性：即f(x)=0有没有根？若有，有有没有根？若有，有 几个根？几个根？ 哪儿有根？确定有根区间哪儿有根？确定有根区间 根的精确化：已知一个根的近似值后，能否根的精确化：已知一个根的近似值后，能否 将它精确到足够精度？将它精确到足够精度？问题的提出方程：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科学技术中常遇到高次代数方程或超越方程的求根问题。科学技术中常遇到高次代数方程或超越方程的求根问题。大于大于4次的代数方程无求根公式。次的代数方程无求根公式。因此需要研究函数方程求根问题的数值方法。因此需要研究函数方程求根问题的数值方法。例如：求解高次方程例如：求解高次方程 7x6-x3+x-1.5=0的根。的根。ex-cos( x)=0求解含有指数和三角函数的超越方程的根。求解含有指数和三角函数的超越方程的根。Why

3、 数值计算 ？根：数值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) 上必有一根。上必有一根。问题求连续函数 y = f(x) 在区间a,b上的唯一实根 y = 0 xyy = f(x)ab分析1. “实根”两侧f(x)反号2. “实根”同侧f(x)同号

4、3. 若: f(x1)f(x2)反号，则“实根”在x1和x2之间方法逐步缩小“有根区间”2022-4-1372022-4-13 执行步骤执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x0)。3判断若判断若f (x0) = 0，则则x0即是根，否则检验即是根，否则检验：（1）若若f (x0)与与f (a)异号异号，则知解位于区间则知解位于区间a, x0， b1=x0, a1=a;（2）若若f (x0)与与f (a)同号同号，则知解位于区间则知解位于区间x0, b， a1=x0, b1

5、=b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(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求方程求方程每个有根区间的长度都是前一个有根区间长度的一半abx1x2abWhen

6、 to stop?11xxkk 2)(xf 或或不能保证不能保证 x 的精度的精度x* 2xx*2022-4-1310误差误差 分析：分析：02a bx有误差有误差02b a|xx*|第第 k 步产生的步产生的 xk 有误差有误差12kkba| xx*|对于给定的精度对于给定的精度 ,可估计二分法所需的步数可估计二分法所需的步数 k ：1lnln12ln2kbabak2022-4-1311第第1步产生的步产生的1x有误差有误差14b a|xx*|简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 2022-4-1312

7、01)(3xxxf例：求下列方程位于区间例：求下列方程位于区间1,1.51,1.5内的一个根内的一个根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的所有实根所在的区间为的所有实根所在的区间为a,b,从从x0=a 出发出发, ,以步长以步长 h=

8、(b-a)/n 其中其中n n是正整数，在是正整数，在a,b内取定节点：内取定节点： xi=x0ih (i=0,1,2，n) 计算计算f(xi)的值的值, ,依据函数值异号及实根的个数确定隔根依据函数值异号及实根的个数确定隔根区间区间, ,通过调整步长，总可找到所有隔根区间。通过调整步长，总可找到所有隔根区间。 y x a b o 在计算中步长在计算中步长h h要适当取小一些要适当取小一些, ,若若h h过长则容易丢根过长则容易丢根( (若若在区间范围内有两相邻函数值符号相同而判定无根在区间范围内有两相邻函数值符号相同而判定无根) )若间隔若间隔h h值太小值太小, ,则影响计算速度。则影响计

9、算速度。 “数学”上是正确的，但作为一种“数学方法”，应用于实际的“科学问题”时，不是“放之四海而兼准”的。 f(x) 在a,b上连续 f(a)f(b)0， f( ) 0尝试： f(5) 0尝试： f(10) 0二分法： f(8) = 0 x0y105但是，实际曲线 杜绝教条主义2022-4-1318迭代法迭代法迭代法是数值计算中一种典型的重要方法，尤其是计算机的普遍使用，使迭代法的应用更为广泛。所谓迭代法就是用某种收敛于所给问题的精确解的极限过程来逐步逼近的一种计算方法，从而可以用有限个步骤算出精确解的具有指定精度的近似解。简单说迭代法是一种逐步逼近的方法。循环迭代，用上一轮结果计算下一轮数

10、据。循环迭代，用上一轮结果计算下一轮数据。 迭代法迭代法 /* Fixed-Point Iteration */思思路路0( )f x 对对于于一一般般形形式式的的方方程程先先将将方方程程化化为为( )xg x0 x再再从从某某一一数数出出发发，作作序序列列10 1 2(), , ,kkxg xklimkkkxxa若若序序列列有有极极限限，即即0( )( )ag af a则则可可得得即即a亦亦即即 是是方方程程的的根根。0kxx称称为为初初始始近近似似值值，称称为为k k次次迭迭代代近近似似值值，1( )()kkg xxg x称称为为迭迭代代函函数数，称称为为迭迭代代公公式式。2022-4-1

11、319, 2 , 1 , 0132588. 1133086. 133086. 1135721. 135721. 115 . 11)(5 . 1013132323121301033kxxxxxxxxxxxxxxxxkk重复步骤，代入，将代入，将代入，将解：改写方程。用六位有效数字计算附近的一个根在例：求方程2022-4-132032494. 1432472. 1832588. 1332472. 1733086. 1232473. 1635721. 1132476. 155 . 10kkxkxk311kkxx迭代序列收敛迭代序列收敛2022-4-13213965.1221090252. 64375

12、. 2101.190435 . 109kkxkxk131kkxx迭代序列发散迭代序列发散2022-4-1322说明：说明： 迭代函数不唯一迭代函数不唯一 迭代序列可能收敛，也可能发散迭代序列可能收敛，也可能发散 迭代收敛与否不仅与迭代函数有关，还与初迭代收敛与否不仅与迭代函数有关，还与初始点有关。始点有关。 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，迭代法是否一定发散？，迭代法是否一定发散？1111110()()( )kkkkkkkkkkxxg xg xgxxxxxxxx迭代序列收敛性的判断原始方程：f(x) = 0等价方程：x = g(x)设 f(x) = 0的根在 a, b区间内0y = xyxababy = g(x)发散迭代方程组: y = x, y = g(x) 要求：(1) y = g(x)也在a, b内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有根有根 实根唯一？实根唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则)(xgx xx*),*( )()(*)(xxgxgxg 在在和和之间。之间。 *xx0)(1)( gxx*而而xxg*1| )(| 当当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 迭代法的结束条件迭代法的结束条件1kkxx例 ：求方程 在0, 0.5内的根，精确到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转化为等价方程10 xxe 令( )1xf xxe，则牛顿迭代公式为11(1)1kkkxxkkkkkxkkx exexxxexx(0,1,2,)k 352022-4-1300.5x ，迭代结果如下表取初值kkx012340.50.57102040.56715550.56714330.5671432*0.567143x 可见，牛顿公式的收敛速度是相当快的。362022-4-1337牛顿法的收敛性牛顿法的收敛性对方程对方程f (x)=0，若存在区间，若存在区间a, b，使，使(1) f (x)在在a, b上连续；上连续；(2) f (a) f (b) 0；则；则Newtons Method产生的

19、序列产生的序列 xk 收敛到收敛到f (x)=0 在在a, b上的唯一实根。上的唯一实根。2022-4-1338牛顿法收敛性示意图牛顿法收敛性示意图2022-4-1339Newton法的收敛性依赖于x0 的选取。x*x0 x0 x0 Newton - Raphson Method下山法下山法 /* Descent Method */ Newtons Method 局部微调：局部微调：初值选择不当, 牛顿迭代法发散, 怎么办 ?迭代目的: 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 公式。公式。 当当 = 1 代入效果不好时，将代入效果不好时，将 减半计算。减半计算。牛顿下山法应用举例计算 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 求复根求复根 /* Finding Complex Roots */ Ne

22、wton 公式中的自变量可以是复数公式中的自变量可以是复数记记 z = x + i y, z0 为初值，同样有为初值，同样有)()(1kkkkzfzfzz kkkkkkDiCzfBiAzf )(,)(设设代入公式，令实、虚部对应相等代入公式，令实、虚部对应相等，可得，可得;221kkkkkkkkDCDBCAxx .221kkkkkkkkDCCBDAyy 2022-4-1344牛顿法优缺点牛顿法优缺点Newton法具有收敛快，稳定性好，精度高等优点，是求解非线性方程的有效方法之一。但它每次迭代均需计算函数值与导数值，故计算量较大。而且当导数值提供有困难时， Newton法无法进行。2022-4-

23、1345弦割法弦割法)(kxf 11)()(kkkkxxxfxf弦割法迭代格式)()()(111kkkkkkkxfxfxxxfxx 在牛顿迭代格式中，将曲线 上点 的切线斜率 ，改为其上两点连线(弦)的斜率( )yf x(,()kkxf x2022-4-1346弦弦割割法法几几何何表表示示x0Xx1 x2 x3YP0P2 P1x11011 ,.,kkkkkxxxxxxx弦 截 法 在 求时 要 用 到 前 面 两 步 的 结 果需 两 个 初 值， 而 牛 顿 切 线 法 在 计 算时 ， 只用 到 前 一 步的 值 。割线割线 /* 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 ，满足精度要求迭代过程的收敛速度迭代过程的收敛速度 设由某方法确定的序列收敛于方程的根，如果存在正实数p，使得Cxxxxpkkk*1*lim（C为非零常数）

25、定义：则称序列 收敛于x*的收敛速度是p阶的，或称该方法具有p 阶敛速。2022-4-13492022-4-1350当p = 1且0C1时，称方法为超线性收敛。 当p = 2时，称方法为平方（二次）收敛；定理定理 设设 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当简单迭代法是线性收敛 ( ) ,( )0,xxa bx迭 代 过 程 的 收 敛 速 度 依 赖 于 迭 代 函 数 g的 选取 。 如 果 当时 g则 该 迭 代 过 程 只可 能 是 线 性 收 敛 。2022-4-1353牛顿法的收敛速度牛顿法的收敛速度 12* ( ) ,( )0,() ()( ) g( ) ( )( )( ) g ( ) ( )( )(kkkkxxa bxfxxxfxfxxxfxfxfxxfxx

27、fxfx迭 代 过 程 的 收 敛 速 度 依 赖 于 迭 代 函 数 g的 选取 。 如 果 当时 g则 该 迭 代 过 程 只可 能 是 线 性 收 敛 。 对 牛 顿 公 式其 迭 代 函 数 为由 于假 定是的 一 个 单 根 ， 即*)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假定 是的重根，即将，代入上式得 用牛顿迭代法对求重根只具有线性收敛。 设由某方法确定的序列收敛于方程的根，*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在该区间内求解在该区间内求解 fzero(sin(x)-0.

29、1*x,6)ans = 7.0682 fzero(sin(x)-0.1*x,2,6)ans = 2.8523Humps函数 2211( )6(0.3)0.01(0.9)0.04y xxx在区间在区间-0.5,1.5的解的解Humps函数 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的所有复根。例 x3+2x2-

30、5的根 roots(1 2 0 -5)ans = -1.6209 + 1.1826i -1.6209 - 1.1826i 1.2419 求解的方法很多，现成的软件更多，而且会越来越多。为什么还要学习求解的方法？“软件”不能解决所有实际问题，常常需要“自力更生”。关于方程求根问题的小结 二分法：f(x)连续、 f(a) f(b) 0 、一个实根简单，速度慢 迭代法：|g (x)| -2区间内的实根。困难牛顿法：导数难以计算；迭代法：难以表达为x = g(x)。最关键的是函数性质不清楚，函数连续性？有多少个根？所以连二分法都难以应用。n1n2n3x0 x2a1衬底包层上界面下界面波导层波导与衬底的交界面-下界面，临界角波导与包层的交界面-上界面，临界角12c13c2121sincnn3131sincnn23nn假设：1213cc当平面波的入射角1变化时，可产生不同的波型：导模和辐射模导模n1n2n3x0 x2a1衬底包层11213cc当 时，即32111cossinnnnn导模：平面波在上下界面都产生全反射上界面下界面波导层TETE模本征方程（模本