第五章 非线性方程的数值解法

《第五章 非线性方程的数值解法》由会员分享，可在线阅读，更多相关《第五章 非线性方程的数值解法（37页珍藏版）》请在文档大全上搜索。

1、 计算方法非线性方程的数值解法5 1、二分法 2、不动点迭代的构造及其收敛性判定 3、Newton迭代 4、割线法 5、非线性方程组的迭代解法主要知识点主要知识点2008年10月6日12时7分沈阳航空工业学院飞机设计教研室第2页，共45页第第4 4章章 数值积分数值积分 计算方法5.1 引言2008年10月6日12时7分沈阳航空工业学院飞机设计教研室第3页，共48页历史背景 代数方程的求根问题是一个古老的数学问题。理论上， 次代数方程在复数域内一定有 个根(考虑重数)。早在16世纪就找到了三次、四次方程的求根公式，但直到19世纪才证明大于等于5次的一般代数方程式不能用代数公式求解，而对于超越方

2、程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。 nn求方程 几何意义0( )f x 基本定理1Th 如果函数 在 上连续，且则至少有一个数 使得 ，若同时 的一阶导数 在 内存在且保持定号，即 (或 )则这样的 在 内唯一。 ( )f x , a b( ) ( )0f a f b ( )0f ( )fx ( )0fx , a b( )f x , a b0( )fx abx*( )yf x oxy1 二分法 /* Bisection Method */原理：若 f Ca, b，且 f (a) f

3、(b) 0，则 f 在 (a, b) 上至少有一实根。基本思想：逐步将区间分半，通过判别区间端点函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求 出满足给定精度的根 的近似值。x )(xfy aboxy x 21bax 1b 2112xba 2a 3a 1a32xba 2b3b11,a b22,a b33,a b以此类推终止法则？abx1x2abWhen to stop?11xxkk 2()kf x 或不能保证 x 的精度x*2xx* 二分法算法给定区间a,b ，求f(x)=0 在该区间上的根x.输入: a和b; 容许误差 TOL; 最大对分次数 Nmax.输出: 近似根 x.

4、Step 1 Set k = 1;Step 2 Compute x=f(a+b)/2);Step 3 While ( k Nmax) do steps 4-6 Step 4 If |x| TOL , STOP; Output the solution x. Step 5 If x*f(a)0 , Set b=x; Else Set a=x; Step 6 Set k=k+1; Compute x=f(a+b)/2);Go To Step 3 ;Step 7 Output the solution of equation: x; STOP. 11111 222, ,kkkkkabxxxbak 且

5、3、 12lnlnlnbak 由二分法的过程可知：4、对分次数的计算公式： 11,kka ba bab 0,kkkkf af bxab 1、 111122kkkkkbababa 2、 1112kkxxba 令误差 分析2Th解：211 510 ,.;ab，12ln()lnlnban 21 5 11012ln( .)lnln 4.645n例1：用二分法求方程 在区间 上的根，误差限为 ，问至少需对分多少次？310 xx 1 1 5 , . 210 简单; 对f (x) 要求不高(只要连续即可) .无法求复根及偶重根收敛慢 用二分法求根，最好先给出 f (x) 草图以确定根的大概位置。或用搜索程序

6、，将a, b分为若干小区间，对每一个满足 f (ak)f (bk) 0 的区间调用二分法程序，可找出区间a, b内的多个根，且不必要求 f (a)f (b) 0 。优点缺点2 迭代法的理论 /* Theory of Iteration Method*/f (x) = 0 x = g (x)（迭代函数）等价变换思路从一个初值 x0 出发，计算 x1 = g(x0), x2 = g(x1), , xk+1 = g(xk), 若 收敛，即存在 x* 使得 ，且 g 连续，则由 可知 x* = g(x* )，即x* 是 g 的不动点，也就是f 的根。 0kkx*limxxkk kkkkxgx liml

7、im1看起来很简单，令人有点不相信，那么问题是什么呢？如何判定这种方法是收敛的呢？f (x) 的根x g (x) 的不动点x 10 1 2(), , ,(*)kkxg xk 一、不动点迭代 /*Fixed-Point Iteration*/xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1x0p0 x1p1x0p0 x1p1x0p0 x1p1几何意义例2： 已知方程 在 上有一个根（正根）324100 xx1 2 , 下面选取5种迭代格式：1、32410 xxxx 即32410( )g xxxx 2、234

8、10 xx 1321102xx 1321102g xx即3、即2104xxx 12104xxx 12104g xxx4、即12104xx 12104g xx 5、即xxxxxx83104223( )( )( )f xg xxfx 取01 5 .x 计算结果如下：123840875673246972010275 10.xxxx 法11234451113484013673813649613652613751713652251365230013.xxxxxxx 法412123081650299691865086.( .)xxx 法31234451129128695140254134546137517

9、13751713751713651378211365230013.xxxxxxxx 法2123413733313652613652300141365230013.xxxx 法5Lipschitz(利普希茨)条件成立的充分条件3Th 考虑方程 x = g(x), 若( I ) 当 xa, b 时， g(x)a, b；( II ) 0 L 0 , r0 使得使得axxxxrnnn|*|*|lim1则称数列则称数列xn r 阶收敛阶收敛.特别特别: (1) 收敛阶收敛阶r=1时时,称为线性收敛称为线性收敛; (2) 收敛阶收敛阶r1时时,称为超线性收敛称为超线性收敛; (3) 收敛阶收敛阶r=2 时

10、时,称为平方收敛称为平方收敛序列的收敛阶数越高序列的收敛阶数越高, ,收敛速度越快收敛速度越快例例 方程方程 x3+10 x-20=0,取取 x0 = 1.5, 证明迭代证明迭代法法)10/(2021 nnxx是线性收敛是线性收敛)10/(20)(2 xx 22)10/(40)( xxx 证证:令令 f (x) = x3 + 10 x 20, 绘出绘出 y = f(x) 图形可知图形可知方程的根方程的根 x*1.5, 令令求导数求导数, 得得-6-4-20246-300-200-1000100200300 xx3+ 10 x-20|*|)(|*)()(|*|1xxxxxxnnnn |*)(|

11、)(|lim|*|*|lim1xxxxxnnnnn 利用利用Lagrange中值定理中值定理, 有有其中其中, 介于介于xn和和x*之间之间. 所以所以n由此可知由此可知,这一序列的收敛阶数为这一序列的收敛阶数为1,即迭代法即迭代法是线性收敛是线性收敛.显然显然,在在x*附近附近1| )(| x 0)( x 定理定理 设设x*是是 的不动点的不动点,且且)(x0*)(*)(*)()1( xxxp 而而 则则 p阶收阶收敛敛0*)()(xp)(1nnxx| )(|!|*|*)()(|*|)(1nppnnnpxxxxxx 由由Taylor公式公式其中其中, 介于介于xn和和x*之间之间.所以所以n

12、|*)(| )(|lim|*|*|lim)()(1xxxxxpnpnpnnn 故迭代法故迭代法p阶收敛阶收敛.0()()f xg xx4 牛顿法 /* Newton - Raphson Method */一、牛顿迭代公式的推导1、待定参数法不动点迭代的关键是构造满足收敛条件的迭代函数 ( )g x一种自然的选择是令0( )( )()g xxcf xc为了加速不动点迭代的收敛过程，应尽可能使迭代函数 在 处有更多阶导数等于零（定理5）。 ( )g xxx 1()cfx 1()()g xcfx 令0 遗 憾！ 110()() ()()()()()g xh xf xh xfxh xfx 10()()

13、()h xfxfx 现设( )( ) ( )g xxh x f x10( )( )( )h xfxfx 取0()g x 满足因此，选取迭代函数( )( )( )f xg xxfx Newton Raphson迭代格式10 1 2(), , ,()kkkkf xxxkfx 称之为牛顿拉夫森方法，简称牛顿法原理：将非线性方程线性化取 x0 x*，将 f (x)在 x0 做一阶Taylor展开:20000)(! 2)()()()(xxfxxxfxfxf ， 在 x0 和 x 之间2、Taylor展开法/* Taylors expansion Method */将 (x* x0)2 看成高阶小量，则有

14、：)*)()(*)(0000 xxxfxfxf )()(*000 xfxfxx 线性 /* linear */xyx*x010 1 2(), , ,()kkkkf xxxkfx 只要 f C1，每一步迭代都有 而且 ，则 x*就是 f 的根。limkkxx 0()kf x 1x000()()()yf xfxxx 与x轴交点的横坐标1x2x无开方运算，又无除法运算。例1：写出求 的Newton迭代格式； 写出求 的Newton迭代格式,要求公式中既0()a a 10()aa 解：等价于求方程 的正根200( )()f xxaa2110 1 222()(), , ,()kkkkkkkkkf xxa

15、axxxxkfxxx 2( )fxx 解法一：等价于求方程 的正根2100( )()()f xxaa12( )()fxxa 21112()()()()kkkkkkkxf xaxxxfxxa 110 1 22(), , ,kxka 32( )fxx 解法二：等价于求方程 的正根2100( )()f xaax21312()()kkkkkkkaf xxxxxfxx 2130 1 22(), , ,kkxaxk Th7 （局部收敛性） 设 x* 为方程 f (x) =0的根，在包含x*的某个开区间内 连续， 且 ，则存在 x* 的邻 ，使得任取初值 ，由Newtons Method产生的序列 以不低于

16、二阶的收敛速度收敛于x*，且( *),Bxxx *)(0 xBx ( )fx 0( )fx kx122*( *)lim(*)( *)kkkxxfxxxfx 122*( *)lim(*)( *)kkkxxfxxxfx 221( )( )( )( )( )fxf x fxgxfx 证明：Newtons Method 事实上是一种特殊的不动点迭代 其中 ，则)()()(xfxfxxg 10*)(*)(*)(*)(2xfxfxfxg收敛由 Taylor 展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 k

17、x122*()( *)()kkkkxxfxxfx 在单根 /*simple root */ 附近收敛快只要 ，则令 可得结论。 k0()fx Th2.5有根根唯一产生的序列单调有界保证收敛证明：因为f C2a, b，由（1）和（2）知f (x) 在a, b内有唯一根x 下面由条件（1）、（2）分4种情况讨论：000( ),( ); , ,( )f af bxa bfx 000( ),( ); , ,( )f af bxa bfx 000( ),( ); , ,( )f af bxa bfx 000( ),( ); , ,( )f af bxa bfx 仅证明第一种情况，其它情况类似讨论Th8

18、（收敛的充分条件）设f (x) =0 且f C2a, b，若(1) f (a) f (b) 0；(2) 在整个a, b上 不变号且 ；(3) 选取 x0 a, b 使得 ；则Newtons Method产生的序列 xk 收敛于方程的根 ,f 0( )fx 000()()f xfx x 且122*( *)lim(*)( *)kkkxxfxxxfx 由中值定理， 使得 , a b 0( )( )( )f bf afba 因此0( ) , fxxa b 即 在 上单调递增( )f x , a b由0000 , ,()()xa bf xfx 00()f x0 xx 01000()()f xxxxfx

19、另一方面，由Taylor展开得2000012( )()()()( )()!f xf xfxxxfxx 介于 、 之间 x0 x20000102()()()()( )()!f xf xfxxxfxx 20000012()( )()()()f xfxxxxfxfx 210012( )()()fxxxfx 1xx 0 x 重复以上过程，可得（归纳法）1kkxxx （自己证）因此，数列 单调下降且有下界 kxx 令limkkxl 1()( )limlim()( )kkkkkkf xf lxxllfxfl 0( )f llx 由Taylor展开得212( )()()()()()!kkkkkf xf xf

20、xxxfxx 2102()()()()()()!kkkkkf xf xfxxxfxx 212()()()()!()kkkkkkf xfxxxxfxfx 2112()()!()kkkkfxxxxfx 122*( *)lim(*)( *)kkkxxfxxxfx Newtons Method 收敛性依赖于x0 的选取。x*x0 x0 x0Th9 （收敛的另一充分条件）设 在a, b上连续， (1) f (a) f (b) 0；(2) 在整个a, b上 且 ；(3) ，则对 ，Newtons Method产生的序列 xk 收敛于方程 在a, b内的唯一实根 。( )fx 0( )fx x 且0( )f

21、x ( )( )f abaf a ( )( )f bbaf b 0 , xa b 0( )f x ab( )( )()yf afaxa ( )( )f axafa ( )( )f afa ( )( )f bxbfb ( )yf x ( )( )f bfb x ( )( )()yf bfbxb Th9中条件（3）的几何意义保证数列 单调递增且有上界 kxx 证明仿照Th2.9改进与推广（补充） /* improvement and generalization */ 重根 /* multiple root */ 加速收敛法：Q1: 若 ，Newtons Method 是否仍收敛？0*)( xf设

22、 x* 是 f 的 n 重根，则： 且 。( )()( )nf xxxq x ()0q x 因为 Newtons Method 事实上是一种特殊的不动点迭代，其中 ，则)()()(xfxfxxg 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nA1: 有局部收敛性，但重数 n 越高，收敛越慢。Q2: 如何加速重根的收敛？A2: 将求 f 的重根转化为求另一函数的单根。令，则 f 的重根 = 的单根。)()()(xfxfx 求复根 /* Finding Complex Roots */ Newton 公式中的自变量可以是复数记 z = x + i y, z0 为初值，同样有

23、)()(1kkkkzfzfzz kkkkkkDiCzfBiAzf )(,)(设代入公式，令实、虚部对应相等，可得;221kkkkkkkkDCDBCAxx .221kkkkkkkkDCCBDAyy 收敛比Newtons Method 慢，且对初值要求同样高。5 割线法 /* Secant Method */x0 x1切线 /* tangent line */割线 /* secant line */切线斜率割线斜率11()()()kkkkkf xf xfxxx 111()()()()kkkkkkkf xxxxxf xf x 需要2个初值 x0 和 x1。Newtons Method 每一步要计算 f 和 ，为了避免计算导数值，现用 f 的值近似 ，从而得到割线法（弦割法）。f f x2