解非线性方程迭代法

1、解非线性方程迭代法 1 1 方程求根与二分法方程求根与二分法 第第7 7章章 解非线性方程的迭代法解非线性方程的迭代法 一、引言一、引言 . ,)(, (1.1) 0)( baCxfRx xf 的求根问题，其中 考虑单变量非线性方程 非线性方程的分两类： . 01 : )., 1 , 0(R, 0 , 0 , . 1 3 0 1 1 10 xxniaa axaxaxa i nn nn 如其中 代数方程 . 0 : , . 2 x ex如超越方程 解非线性方程迭代法 .)(* . ,|*)(|0 ),(*)()( )( 重零点的为则称为正整数其中 可以分解为如果 mxfxmxg xgxxxf x

2、f m . 0*)(, 0*)(*)(*)( )() 1( xfxfxfxf mm 此时 , 0)()(,)(bfafbaCxf若 则可用搜索法求有根区间. .0 的有根区间求方程 x ex例1例1 x 1 0 1 2 f(x)的符号 + + 求根问题的三个方面：存在性，分布，精确化。 解非线性方程迭代法 二、二分法二、二分法 二分法简述. ., ;,)()( ., )()( . 2/ )(, 0)()( 011 1010 0 00 xbaa bbxaxfaf x xfxfbaxbfaf 否则 同号，则与若 假若不然，停止那么输出 的零点，是假如取设 , 11 kk bababa故 *,2/

3、)(xbax kkk (1.3) .2/ )(2/ )(|*| 1 k kkk ababxx 解非线性方程迭代法 .2 5 . 1 , 0 . 1 01 3 位小数点后 内的一个实根，准确到在求 xx 例2例2 k ak bk xkf(xk)符号 0 1 2 3 4 5 6 1.0 1.25 1.3125 1.3203 1.5 1.375 1.3438 1.3281 1.25 1.375 1.3125 1.3438 1.3281 1.3203 1.3242 + + + 二分法优、缺点； 用途。 解非线性方程迭代法 2 2 迭代法迭代法 一、不动点迭代一、不动点迭代 (2.1) ).( 0)(

4、xx xf 化为等价形式将非线性方程 .)(* ; ) *(*0*)( 不不动动点点的一个为函数称xx xxxf ).(, 010 xxx可以得到给定初始近似值 .)( (2.2) ., 2 , 1 , 0 ),( 1 为迭代函数称 式如此反复，构造迭代公 x kxx kk 解非线性方程迭代法 .)2 . 2( )(*)(*(2.2) *,lim )2 . 2(, 0 不不动动点点迭迭代代法法为故称 的不动点，是收敛，且则称迭代公式 有极限得到的序列由如果对任何初值 xxx xx xbax k k k .几何意义 是一种逐次逼近法；隐式化为显式，迭代法 ：说明说明 解非线性方程迭代法 .*5

5、. 101 3 xxx附近的根在求 例例3 3 )., 2 , 1 , 0( , 15 . 11 3 10 kxxx kk ，）解：（ kxk 0 1 2 3 4 5 6 7 1.5 1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 . ,39.12,375. 2 , 5 . 1, 1 (2) 210 3 1 xxxxx kk 解非线性方程迭代法 .*,)( 2.4 |;| )()(| , , 10 (2) ,)( , (1) , ,)( xbax yxLyx bayxL baxbax baCx 上存在唯一的不动点在那么 ）（ 都有

6、使得常数 都有 并且如果迭代函数 定定理理1 1 二、不动点的存在性与迭代法的收敛性二、不动点的存在性与迭代法的收敛性 *,)(2.2) ,1 0 xx bax 的不动点均收敛于 迭代序列对任意初值的条件下在定理 定定理理2 2 并有误差估计 (2.5) . | 1 |*| 01 xx L L xx k k . | 1 1 |*| 1kkk xx L xx 还有 解非线性方程迭代法 . | 1 1 |*| 4) |,| 1 |*| 3) *,(2.2) , 2) *,0)( 1) ; 1| )(|, , 10 (2) ,)( , (1) , ,)( 1 01 0 1 kkk k k xx L

7、xx xx L L xx xbax xbaxf LxbaxL baxbax baCx 均收敛于迭代序列对任意初值 上有唯一的根在方程 那么 都有使得 都有 并且如果迭代函数 推论推论 . 12 ; 11 1,2 3 1 3 1 kkkk xxxx）内考查：在 解非线性方程迭代法 三、局部收敛性与收敛阶三、局部收敛性与收敛阶 . * , 局部收敛性附近考察收敛性，称为 点。应用上经常只在不动不容易由定理作出判断 局收敛性；上的收敛性通常称为全在迭代序列 x baxk . *),(* (2.2)*,( ),*,( 0 则称迭代序列局部收敛均收敛于 迭代序列使得如果 xx xUxxU 定义1定义1

8、.)2 . 2( , 1|*)(| , *)(,)(* 是局部收敛的则迭代法且内有连续导数 的某邻域在的不动点为迭代函数若 x xxxx 定理3定理3 解非线性方程迭代法 . 3*03 2 xx的根求方程只用四则运算不用开方例例4 4 ; 1132*)(12)(31 2 1 xxxxxx kkk ，）（ ; 1*)( 3 )( 3 2 2 1 x x x x x k k ，）（ ;134. 0 2 3 1*)( 2 1)() 3( 4 1 3 2 1 x x xxxx kkk ，）（ . 0*)() 3 1 ( 2 1 )() 3 ( 2 1 4 2 1 x x x x xx k kk ，）（

9、 kxk迭代法(1) 迭代法(2) 迭代法(3)迭代法(4) 0 1 2 3 ? x0 x1 x2 x3 ? 2 3 9 87 ? 2 1.5 2 1.5 ? 2 1.75 1.73475 1.732631 ? 2 1.75 1.732143 1.732051 ? 解非线性方程迭代法 .2 11 . , ,lim *,*,)( 1 1 时为平方收敛超线性收敛；当 时为当时迭代法为线性收敛；特别地，当收敛 阶则称迭代过程为是不等于零的常数若 误差收敛于设迭代过程 p pp pCC e e xxexxx p k k k kkkk 定定义义2 2 .* , 0*)(0*)(*)(*)( , *)()

10、( )() 1( 阶收敛的附近是那么迭代过程在 ， 并且连续导数 阶邻近具有的根在如果迭代函数 px xxxx pxxxx pp 定定理理4 4 . ,0*)( , 0*)( ; ,1|*)(|0 平方收敛时当 迭代法线性收敛时特别地，当 xx x 作业作业: P290, 2,4. 解非线性方程迭代法 3 3 迭代收敛的加速方法迭代收敛的加速方法 一、埃特金加速收敛方法一、埃特金加速收敛方法 ),( 01 xx 由迭代公式校正一次得对于收敛的迭代过程， ).( 12 xx再校正一次得 则变化不大如果 ,)( ,)(Lxx (3.1) *).-(*)()(* *),-(*)()(* 112 00

11、1 xxLxxxx xxLxxxx * * * * 1 0 2 1 xx xx xx xx 解非线性方程迭代法 ,*2 2 0202 2 1 2 1 xxxxxxxxxxx . 2 )( 2 2 2 * 012 2 01 0 012 2 102 2 01002 0 012 2 102 xxx xx x xxx xxxxxxxx x xxx xxx x )( )( :Aitken)( 12 1 2 kk kk xx xx 加速迭代方法于是得到埃特金 * * * * 1 0 2 1 xx xx xx xx kkk kk kk xxx xx xx 12 2 1 1 2 )( (3.2) ./)( 2

12、2 kkk xxx 解非线性方程迭代法 二、斯蒂芬森迭代法二、斯蒂芬森迭代法 迭代法 蒂芬森加速技巧结合，得到斯把不动点迭代与埃特金 )(Steffensen (3.3) ), 2 , 1 , 0( 2 )( ),( ),( 2 1 k xyz xy xx yzxy kkk kk kk kkkk (3.4) ), 2 , 1 , 0( )( 1 其中 代法改写为另一种不动点迭 kxx kk (3.5) . )(2)( )( )( 2 xxx xx xx 解非线性方程迭代法 .2)3 . 3( )(*1) *( ,)()(* .)(*,)(* 阶收敛的是迭代法的不动点，且斯蒂芬森 为，则存在的不

13、动点，设为 反之，的不动点为则的不动点为若 xxxxxx xxxx 定定理理5 5 . 1 01 3 1 3 kk xxxx的迭代将斯蒂芬森法用于解 例5例5 .,)3 . 3( .13 3 1 有收敛结果计算现用发散指出：例 kk xx解解 kxkykzk 0 1 2 3 4 5 1.5 1.41629 1.35565 1.32985 1.32480 1.32472 2.37500 1.84092 1.49140 1.34710 1.32518 12.3965 5.23888 2.31728 1.44435 1.32714 说明说明: (2.2)不收敛,(3.3)可能收敛; (2.2)线性收

14、敛,(3.3)平方收敛! 解非线性方程迭代法 .4 , 303 2 中的解在求方程 x ex 例例6 6 ln3ln2 构造迭代法，)(3lnln2： 1 kk xx xgxx取对数得解解 .2 ,4 , 3)(,4 , 3 , 1 3 2 )(max , 2 )( 43 迭代收敛由定理 当 xxx x x x .73307. 3 , 5 . 3 160 xx 则进行加速若用,)3 . 3( kxkykzk 0 1 2 3.5 3.73444 3.73307 3.60414 3.73381 3.66202 3.73347 解非线性方程迭代法 4 4 牛顿法牛顿法 一、牛顿法及其收敛性一、牛顿法

15、及其收敛性 .牛顿迭代公式的推导:线性化 展开做并假定近似根 的设已知方程 Taylorxfx xf kk , 0)(, 0)( ),)()()( kkk xxxfxfxf (4.1) , 0)()( 0)( kkk xxxfxf xf近似表示为于是 . 4.2 . )( )( ,其根为 1 1 牛牛顿顿迭迭代代法法这就是 ）（ 则有计算公式记 k k kk k xf xf xx x 解非线性方程迭代法 .义牛顿迭代公式的几何意 .性牛顿迭代法的局部收敛 , )( )( )( xf xf xx , )( )()( )( )()()( 1)( 22 2 xf xfxf xf xfxfxf x ,

16、 *)( *)( *)( 0*)(*)(0*)(*)( *)( 4 2 xf xf xf xfxfxfxf x ）（4.3 . *)(2 *)( *)( * lim 2 1 xf xf xx xx k k k 解非线性方程迭代法 二、牛顿法应用举例二、牛顿法应用举例 .0 的根用牛顿法求方程 x ex例例7 7 . 5 . 0 ), 2 , 1 , 0( 1 0 1 x k x ex xx k x k kk k 取初值 解：牛顿迭代公式为 kxk 0 1 2 3 0.5 0.57102 0.56716 0.56714 ，应用牛顿法解二次方程对于给定正数0 , 2 CxC例例8 8 ;115并求

17、 .0 0 迭代公式皆平方收敛证明x (4.5) ). ( 2 1 2 2 1 k k k k kk x C x x Cx xx 解： . 01 ,115 0 xC初值取 kxk 0 1 2 3 4 10 10.750000 10.723837 10.723805 10.723805 解非线性方程迭代法 三、简化牛顿法与牛顿下山法三、简化牛顿法与牛顿下山法 ., 2 , 1 , 0, 0 )( 1 kCxCfxx kkk 构造迭代公式 .,2)(0 1, )(1)(公式局部收敛时即当xfCxfCxg (4.7) . )( )( 0 1 xf xf xx k kk 简化牛顿法： )( 1 0 x

18、f C kkk xxx)1 ( 11 (4.12) , 2 , 1 , 0, )( )( 1 k xf xf xx k k kk 牛顿下山法： . )()( 1, 1kk xfxf 逐次折半直到满足其中下山因子 解非线性方程迭代法 .*5 . 101 3 3 xxx附近的根在再求、 例例 ，计算结果如下：，折半 ，简化牛顿法，：依次用牛顿法 32/11 6 . 06 . 05 . 1 000 xxx解解 kxkxkxk f(xk) 0 1 2 3 4 1.5 1.34783 1.32520 1.32472 0.6 17.9 发散 0.6 -1.384 1.140625 -0.656643 1.

19、36181 0.1866 1.32628 0.00667 1.32472 0.0000086 . 1 )( 2 的根山法求讨论用牛顿法和牛顿下： x x xf 思思考考 .，11, 1,0 )1 ( 1 )1 ( 2)1 ( )( 000 22 2 22 2 xxx x x x xxx xf注： 解非线性方程迭代法 四、重根情形四、重根情形 . (4.13) , )( )( )(*)()(, 1 仍平方收敛 可将迭代法改为 ，牛顿法不是平方收敛重根情形 k k kk m xf xf mxx xgxxxfm .0)(* , )(*)()( )(*)( )( )(*)(/ )()( 的单根是故 重

20、根，则的是，若还可令 xx xgxxxmg xgxx x mxfxxfxfx 解非线性方程迭代法 . (4.14) , )()()( )()( )( 2 1 仍平方收敛 用牛顿法得对 kkk kk kk xfxfxf xfxf xx x . 2*044 9 24 xxx的二重根用上述三种方法求 例例 ；）牛顿法：（ k k kk x x xx 4 2 1 2 1 解解 ；）（ k k kk x x xx 2 2 )13. 4( 2 2 1 . 2 )2( (4.14) 3 2 2 1 k kk kk x xx xx）（计算结果如下： 解非线性方程迭代法 kxk(1)(2)(3) 0 1 2 3

21、 x0 x1 x2 x3 1.5 1.458333333 1.436607143 1.425497619 1.5 1.416666667 1.414215686 1.414213562 1.5 1.411764706 1.414211438 1.414213562 作业作业: P291, 12,15. 解非线性方程迭代法 5 5 弦截法弦截法 的迭代法。下面介绍避免求要计算 外还每步除计算程用牛顿法求解非线性方 )( ).( )(, 0)( kk k xfxf xfxf 单点弦截法 . 1 ).( )()( )( )(, )( )( 0 0 01 0 k k k k kkk k xx xx x

22、fxf xf xxxxfxfxp xx ，得到线性插值函数为插值节点和以 . )( )()( )( 0)( 0 0 1 1 称为单点弦截法 ， ，得到令 xx xfxf xf xx xp k k k kk 解非线性方程迭代法 )( )()( 0 0 ，同样得代替导数在牛顿法中用差商 k k k xf xx xfxf ).( )()( )( 0 0 1 xx xfxf xf xx k k k kk .几何意义 .线性收敛的可以证明单点弦截法是这是因为， , *)( 1 0)*( )(*)( 0)(*)(*)( 1*)( 0 0 * )(*)( 0 2 0 0 xx xfxf xf xx xfxf

23、 xfxfxf x . 1*)( 0 x 解非线性方程迭代法 两点弦截法 . 2 )( )()( )( )( 1 1 1 1 k kk kk k kk xx xx xfxf xfxp xx ，得到线性插值函数为插值节点和以 . )( )()( )( 0)( 1 1 1 1 称为两点弦截法 ， ，得到令 kk kk k kk xx xfxf xf xx xp . )()( )( 1 1 而得到或在牛顿法中取 kk kk k xx xfxf xf .几何意义 解非线性方程迭代法 .线性收敛可以证明两点弦截法超 .* 618. 1 , , 0)( |*:|*)( 6 2 51 10 x p xxxfx xxxxf 收敛到 按阶充分小时，两点弦截法那么当 又初值有连续导数，且对任意 内具有二阶的邻域在根假设 定定理理 .01)( 的根用两点弦截法求方程 x xexf 例10例10 kxk 0 1 2 3 4 0.5 0.6 0.56532 0.56709 0.56714 解非线性方程迭代法 抛物线法 . 3 )(, )(,)( )( , 121 12 21 kkkkk kkkk kkk xxxxxxxf xxxxfxfxp xxx，得到插值函数为插值节点和以 ).(, ,)(4 )(2 0)( 1211 21