非线性方程的数值解法

1、第二章第二章 非线性方程的数值解法非线性方程的数值解法 /* Numerical Solutions of Nonlinear Equations*/本章主要内容：本章主要内容：1 1、二分法、二分法2 2、不动点迭代的构造及其收敛性判定、不动点迭代的构造及其收敛性判定（重点）（重点）3 3、Newton和和Steffensen迭代迭代（重点）（重点）4 4、割线法、割线法5 5、非线性方程组的迭代解法、非线性方程组的迭代解法历史背景历史背景 代数方程的求根问题是一个古老的数学问题。理论上，代数方程的求根问题是一个古老的数学问题。理论上， 次代数方程在复数域内一定有次代数方程在复数域内一定有

2、个根个根( (考虑重数考虑重数) )。早在。早在1616世纪世纪就找到了三次、四次方程的求根公式，但直到就找到了三次、四次方程的求根公式，但直到1919世纪才证明大世纪才证明大于等于于等于5 5次的一般代数方程式不能用代数公式求解，而对于超次的一般代数方程式不能用代数公式求解，而对于超越方程就复杂的多，如果有解，其解可能是一个或几个，也可越方程就复杂的多，如果有解，其解可能是一个或几个，也可能是无穷多个。一般也不存在根的解析表达式。因此需要研究能是无穷多个。一般也不存在根的解析表达式。因此需要研究数值方法求得满足一定精度要求的根的近似解。数值方法求得满足一定精度要求的根的近似解。 nn求方程求

3、方程 几何意义几何意义0( )f x 基本定理基本定理2 1 .Th 如果函数如果函数 在在 上连续，且上连续，且则至少有一个数则至少有一个数 使得使得 ，若同时，若同时 的一阶的一阶导数导数 在在 内存在且保持定号，即内存在且保持定号，即 ( (或或 ) )则这样的则这样的 在在 内唯一。内唯一。 ( )f x , a b( ) ( )0f a f b ( )0f ( )fx ( )0fx , a b( )f x , a b0( )fx abx*( )yf x oxy1 1 二分法二分法 /* Bisection Method */原理：原理：若若 f Ca, b，且，且 f (a) f (

4、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 或或不能

5、保证不能保证 x 的精的精度度x* 2xx* 二分法算法二分法算法给定区间给定区间a,b ，求，求f(x)=0 在该区间上的根在该区间上的根x. .输入输入: : a和和b; ; 容许误差容许误差 TOL; ; 最大对分次数最大对分次数 Nmax.输出输出: 近似根近似根 x.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; Els

6、e 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 且3、 12lnlnlnbak 由二分法的过程可知：由二分法的过程可知：4、对分次数的计算公式：对分次数的计算公式： 11,kka ba bab 0,kkkkf af bxab 1、 111122kkkkkbababa 2、 1112kkxxba 令令误差误差 分析分析2 2 .Th解解：211 510 ,.;ab，12l

7、n()lnlnban 21 5 11012ln( .)lnln 4.645n例例1 1：用二分法求方程用二分法求方程 在区间在区间 上的上的根，误差限为根，误差限为 ，问至少需对分多少次？，问至少需对分多少次？310 xx 1 1 5 , . 210 简单简单; 对对f (x) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及无法求复根及偶重根偶重根收敛慢收敛慢 用二分法求根，最好先给出用二分法求根，最好先给出 f (x) 草图以确定根的大草图以确定根的大概位置。或用搜索程序，将概位置。或用搜索程序，将a, b分为若干小区间，对每一分为若干小区间，对每一个满足个满足 f (ak)f

8、 (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*

9、)，即，即x* 是是 g 的不动点，也就是的不动点，也就是f 的根。的根。 0kkx*limxxkk kkkkxgx limlim1看起来很简单，令人看起来很简单，令人有点不相信，那么问有点不相信，那么问题是什么呢？题是什么呢？如何判定这种方法如何判定这种方法是收敛的呢？是收敛的呢？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 x

10、1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1几何意义几何意义例例2： 已知方程已知方程 在在 上有一个根（正根）上有一个根（正根）324100 xx 1 2 , 下面选取下面选取5 5种迭代格式：种迭代格式：1 1、32410 xxxx即即32410( )g xxxx 2 2、23410 xx 1321102xx 1321102g xx即即3 3、即即2104xxx12104xxx 12104g xxx 4 4、即即12104xx 12104g xx 5 5、即即xxxxxx83104223( )( )( )f xg xxfx 取取01 5 .x 计算结果如下：计算结果如下

11、：123840875673246972010275 10.xxxx 法法1 11234451113484013673813649613652613751713652251365230013.xxxxxxx 法法4 412123081650299691865086.( .)xxx 法法3 3123445112912869514025413454613751713751713751713651378211365230013.xxxxxxxx 法法2 2123413733313652613652300141365230013.xxxx 法法5 5Lipschitz条件成条件成立的充分条件立的充分条件

12、2 3 .Th 考虑方程考虑方程 x = g(x), 若若( I ) 当当 x a, b 时，时， g(x) a, b；( II ) 0 L 1 使得使得 对对 x a, b 成立。成立。则任取则任取 x0 a, b，由，由 xk+1 = g(xk) 得到的序列得到的序列 收敛收敛于于g(x) 在在a, b上的唯一不动点。并且有误差估计式：上的唯一不动点。并且有误差估计式： 0kkx|11|*|1kkkxxLxx 101|*|kkLxxxxL ( k = 1, 2, )且存在极限且存在极限 *lim1xgxxxxkkk 1( )g xL ( )g x 连续时连续时证明：证明： g(x) 在在a

13、, b上存在不动点？上存在不动点？令令xxgxf )()(bxga )(,0)()( aagaf0)()( bbgbf)(xf有根有根 不动点唯一？不动点唯一？反证：若不然，设还有反证：若不然，设还有 ，则，则)(xgx ),*( )()(*)(xxgxgxg xx*在在和和之间。之间。 *xx0)(1)( gxx*而而xxg*1| )(| 当当k 时，时， xk 收敛到收敛到 x* ？ |*|kxx|*| )(| )(*)(|111 kkkxxgxgxg0|*|.|*|01 xxLxxLkk L 越越 收敛越快收敛越快可用可用 来来控制收敛精度控制收敛精度|1kkxx ?|11|*|1kkk

14、xxLxx |*|*|*|*|11kkkkkkxxLxxxxxxxx ?|1|*|01xxLLxxkk |.| )(| )()(|011111xxLxxLxxgxgxgxxkkkkkkkkkk 1lim()?kkkxxg xxx *)(*)*)(lim*lim1xgxxxxgxxxxkkkkkkk 小小条件条件 ( II ) 可改为可改为 在在a, b 满足满足Lipschitz条件条件,定理结论仍然成立定理结论仍然成立(定理定理2.3)。 算法算法: : 不动点迭代不动点迭代给定初始近似值给定初始近似值 x0 ，求，求x = g(x) 的解的解. .输入输入: : 初始近似值初始近似值 x0

15、; ; 容许误差容许误差 TOL; ; 最大迭代次数最大迭代次数 Nmax.输出输出: 近似解近似解 x 或失败信息或失败信息.Step 1 Set i = 1;Step 2 While ( i Nmax) do steps 3-6Step 3 Set x = g(x0); /* 计算计算 xi */Step 4 If | x x0 | 1)(1)阶收敛的方法，阶收敛的方法，改用改用Stefensen迭代方法优点不多。迭代方法优点不多。取取01 5.x 计算结果如下：计算结果如下：12341361886136522813652301365230.xxxx 法法2 2原原迭迭代代次次数数2912

16、34513368751363130136522013652301365230.xxxxx 法法3 3原原来来不不收收敛敛12345670934944100503310754631145492121343712757711325977.xxxxxxx 法法1 18910111355744136458213652271365230.xxxx 原原来来不不收收敛敛0()()f xg xx 4 牛顿法牛顿法 /* Newton - Raphson Method */一、牛顿迭代公式的推导一、牛顿迭代公式的推导1、待定参数法待定参数法不动点迭代的不动点迭代的关键关键是构造满足是构造满足收敛条件收敛条件的

17、的迭代函数迭代函数 ( )g x一种一种自然的选择自然的选择是令是令0( )( )()g xxcf xc 为了加速不动点迭代的收敛过程，应尽可能使迭代函数为了加速不动点迭代的收敛过程，应尽可能使迭代函数 在在 处有处有更多阶导数等于零更多阶导数等于零（定理（定理2.52.5）。）。 ( )g xxx 1()cfx 1()()g xcfx 令令0 110()() ()()()()()g xh xf xh xfxh xfx 10()()()h xfxfx 现设现设( )( ) ( )g xxh x f x 10( )( )( )h xfxfx 取取0()g x 满足满足因此，选取迭代函数因此，选取

18、迭代函数( )( )( )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 看成看成高阶小量高阶小量，则有：，则有：)*)()(*)

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

20、的正根的正根200( )()f xxaa2110 1 222()(), , ,()kkkkkkkkkf xxaaxxxxkfxxx 2( )fxx 解法一：解法一：等价于求方程等价于求方程 的正根的正根2100( )()()f xxaa 12( )()fxxa 21112()()()()kkkkkkkxf xaxxxfxxa 110 1 22(), , ,kxka 32( )fxx 解法二：解法二：等价于求方程等价于求方程 的正根的正根2100( )()f xaax 21312()()kkkkkkkaf xxxxxfxx 2130 1 22(), , ,kkxaxk Th2.7 （局部收敛性局

21、部收敛性） 设设 x* 为方程为方程 f (x) =0的根，在包含的根，在包含x*的某个开区间内的某个开区间内 连续，连续， 且且 ，则存在，则存在 x* 的邻域的邻域 ，使得任取初值使得任取初值 ，由，由Newtons Method产生的序列产生的序列 以不低于以不低于二阶二阶的收敛速度收敛于的收敛速度收敛于x*，且，且( *),Bxxx *)(0 xBx ( )fx 0( )fx kx122*( *)lim(*)( *)kkkxxfxxxfx 122*( *)lim(*)( *)kkkxxfxxxfx 221( )( )( )( )( )fxf x fxgxfx 证明：证明：Newtons

22、 Method 事实上是一种事实上是一种特殊的不动点迭代特殊的不动点迭代 其中其中 ，则，则)()()(xfxfxxg fxf xgxfx2( *)( *)( *)0( *) 收敛收敛由由 Taylor 展开：展开：2)*(!2)()*)()(*)(0kkkkkxxfxxxfxfxf 2)*()(! 2)()()(*kkkkkkxxxffxfxfxx 1 kx122*()( *)()kkkkxxfxxfx 在在单根单根 /*simple root */ 附近收敛快附近收敛快 只要只要 ，则令，则令 可得结论。可得结论。 k0()fx Th2.5有根有根根唯一根唯一产生的序列产生的序列单调有单调

23、有界界保证收敛保证收敛证明：证明：因为因为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 仅证明仅证明第一种第一种情况，其它情况类似讨论情况，其它情况类似讨论Th2.8 （收敛的充分条件收敛的充分条件）设设f (x) =0 且

24、且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(

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

26、( )kkkkkkf xf lxxllfxfl 0( )f llx 由由Taylor展开得展开得212( )()()()()()!kkkkkf xf xfxxxfxx 2102()()()()()()!kkkkkf xf xfxxxfxx 212()()()()!()kkkkkkf xfxxxxfxfx 2112()()!()kkkkfxxxxfx 122*( *)lim(*)( *)kkkxxfxxxfx Newtons Method 收敛性依赖于收敛性依赖于x0 的选取。的选取。x*x0 x0 x0Th2.9 （收敛的另一充分条件收敛的另一充分条件）设设 在在a, b上连续，上连续， (1

27、) f (a) f (b) 0；(2) 在整个在整个a, b上上 且且 ；(3) ，则对则对 ，Newtons Method产生的序列产生的序列 xk 收敛于方收敛于方程程 在在a, b内内的唯一实根的唯一实根 。( )fx 0( )fx x 且且0( )fx ( )( )f abaf a ( )( )f bbafb 0 , xa b 0( )f x ab( )( )()yf afaxa ( )( )f axafa ( )( )f afa ( )( )f bxbfb ( )yf x ( )( )f bfb x ( )( )()yf bfbxb Th2.9中条件中条件（3）的的几何意义几何意义保

28、证数列保证数列 单调递增且有上界单调递增且有上界 kxx 证明仿证明仿照照Th2.9改进与推广（改进与推广（补充补充） /* improvement and generalization */ 重根重根 /* multiple root */ 加速收敛法：加速收敛法：Q1: 若若 ，Newtons Method 是否仍收敛？是否仍收敛？0*)( xf设设 x* 是是 f 的的 n 重根，则：重根，则： 且且 。()()()nf xxxq x ()0q x 因为因为 Newtons Method 事实上是一种特殊的不动点迭代，事实上是一种特殊的不动点迭代，其中其中 ，则，则)()()(xfxfx

29、xg 22*)(*)(*)(*)(1|*)(|xfxfxfxfxg111 nA1: 有局部收敛性，但重数有局部收敛性，但重数 n 越高越高，收敛，收敛越慢越慢。Q2: 如何如何加速加速重根情况时的收敛速度？重根情况时的收敛速度？A2: 将求将求 f 的的重根转化重根转化为求另一函数的为求另一函数的单根单根。令，则令，则 f 的重根的重根 = = 的单根。的单根。)()()(xfxfx 求复根求复根 /* Finding Complex Roots */ Newton 公式中的自变量可以是公式中的自变量可以是复数复数记记 z = x + i y, z0 为初值，同样有为初值，同样有)()(1kk

30、kkzfzfzz kkkkkkDiCzfBiAzf )(,)(设设代入公式，令代入公式，令实、虚部对应相等实、虚部对应相等，可得，可得;221kkkkkkkkDCDBCAxx .221kkkkkkkkDCCBDAyy 5 弦割法与抛物线法弦割法与抛物线法 /* Secant Method and Parabola Method */x0 x1割线割线 /* secant line */切线斜率切线斜率 割线斜率割线斜率11()()()kkkkkf xf xfxxx 111()()()()kkkkkkkf xxxxxf xf x 需要需要2个初值个初值 x0 和和 x1。Newtons Meth

31、od 每一步要计算每一步要计算 f 和和 ，为了避免计算导，为了避免计算导数值，现用数值，现用 f 的值近似的值近似 ，从而得到，从而得到弦割法弦割法（割线法割线法）。）。f f x2一、弦割法一、弦割法Th2.10 局部收敛性局部收敛性 设设 表示区间表示区间 ， x*为方程为方程 f (x) =0的根，的根， 函数函数f (x)在在 中有中有足够阶连续导数足够阶连续导数， 且且 满足满足 ,xxI0 I则对则对 ，由割线法产生的序列，由割线法产生的序列 都收敛于都收敛于x*，且，且(i) (ii) (iii) 0( );fxxI 2( ),;( )fMIf 1dM 01,xxI kx其中其

32、中11limkqqkkeKe 2*(),()fxKfx 1151 6182().q 收敛速度介于收敛速度介于Newton and Bisection 之间之间 Corollary(推论推论) 设设 x* 为方程为方程 f (x) =0的一个根，的一个根， ， 且且 在在 x* 的附近连续，则的附近连续，则 使得使得 由由Secant Method产生的序列产生的序列 都收敛于都收敛于x*。01,x xxx ( )fx 0()fx kx0, 例例1 证明方程证明方程 在区间在区间 内有内有唯一唯一根根 ，且，且使得对任意的初始值使得对任意的初始值 ，由，由割线法割线法产生的序产生的序列列 都收敛

33、于都收敛于 。 cosxx 02, x 0 01,xxxx kxx 证明：证明：令令( )cosf xxx0022( )()ff 1002( )sin, ,fxxx 方程方程存在存在根根方程存在方程存在唯一唯一根根0()fx 且且( )cosfxx 在在 附近连续附近连续x 由由推论推论知，由知，由割线法割线法产生的序列产生的序列 都收敛于都收敛于 。 x kx xk-2Muller方法的思想来源于方法的思想来源于弦割法弦割法: :利用利用3个已知点构造一条抛物个已知点构造一条抛物线线, ,取其与取其与x轴的交点构造下一次迭代值轴的交点构造下一次迭代值. .x*二、抛物线法二、抛物线法(Mul

34、ler)几何图示几何图示xkxk-1xk+1( )f x2( )px Muller方法的具体实现方法的具体实现: :设已知三个点设已知三个点22(,(),kkxf x 11(,(),kkxf x (,().kkxf x则过上述三个点的则过上述三个点的抛物线方程抛物线方程为为: :12221212121()()()()( )()()()()()()kkkkkkkkkkkkkkxxxxxxxxp xf xf xxxxxxxxx 2121()()()()()kkkkkkkxxxxf xxxxx 取该抛物线与取该抛物线与x轴的交点作为下一次迭代值轴的交点作为下一次迭代值, ,即即210()kpx 然后取新的相邻的三次迭代值重复上述过程然后取新的相邻的三次迭代值重复上述过程, ,即为即为Muller方法方法. Muller方法中抛物线根的计算方法