数值计算方法第2章

第 2章 非线性方程与方程组的数值 解法 本章重点介绍求解非线性方程 的几种常见和有 效的数值方法 ,同时也对非线性方程组 求解 ,简单介绍一些最基本的解法 .无论在理论上 ,还是在 实际应用中 ,这些数值解法都是对经典的解析方法的突 破性开拓和补充 ,许多问题的求解 ,在解析方法无能为力 时 ,数值方法则可以借助于计算机出色完成 . 0)( xf ),2,1(0),( 21 nixxxf ni 例 2.1.将一半径为 r,密度为 0是给定的步长，取 ， 若 则扫描成功；否则令 ，继续上述方法，直到成 功。如果 则扫描失败。再将 h 缩小， 继续以上步骤。 haxax 10 , 0)()( 10 xfxf hxxxx 0110 , bx 1 等步长扫描算法 算法：（求方程 的有根区间） (1) 输入 ； (2) ； (3) ，若 输出失败信息， 停机。 (4)若 。输出 ，已算出方程的一个根，停 机。 0)( xf hba , )(0 aff )(, 1 xffhax bx 01 f x (5) 若 。输出 为有根区间， 停机 (6) ，转 3） 注：如果对足够小的步长 h扫描失败。 说明： 在 内无根 在 内有偶重根 010 ff , xaxa xa , ba , ba 例题 例 1 设方程 解：取 h=0.1,扫描得： 又 即 在 有唯一根。 2,1,1)( 3 baxxxf 0344.0)4.1( 061.0)3.1( f f .4.1,3.1方程的有根区间为 4.1,3.1,013)( 2 xxxf 0)( xf 4.1,3.1 a a+ a+2 a+3 a+4 h 0 0 0 -0.61 0.344 h/2 0 +0.009375 h/4 0 +0.0012 h/8 0 -0.0505 +0.0012 h/16 0 -0.0775 h=0.1,a=1,a=1.3,b=1.4,a=1.3,b=1.35.a=1.3,b=1.325, a=1.3,b=1.3125,a=1.3125,b=1.325 2.2一般迭代法 2.2.1 迭代法及收敛性 对于 有时可以写成 形式 如： 0)( xf )( xx 3 33 1 101 xx xxxx xxxx cos0cos 迭代法及收敛性 考察方程 。这种方程是隐式方 程，因而不能直接求出它的根，但如果 给出根的某个猜测值 ， 代入 中 的右端得到 ，再以 为一个猜 测值，代入 的右端得 反复迭代得 )( xx 0 x )( xx )( 01 xx 1x )( xx )( 12 xx ,.1,0)( k1k kxx 迭代法及收敛性 若 收敛，即 则得 是 的一个根 kx xxk klim x )( xx )()lim()(limlim 1n xxxxx nnnnn 例题 例 2 设方程 xx xx xxx baxxxf 83 104 )( : 10 2,1,104)( 2 23 4 24 令 。不超过 上的根，使得误差在 k xk 0 1 2 3 4 1.5 1.37333333 1.365262015 1.365230014 1.365230013 该方法比二分法快 ! 迭代法的几何意义 交点的横坐标 *x )()( xy xyxx y=x 2x 0 x1x 简单迭代法 将 变为另一种等价形式 。 选取 的某一近似值 ，则按递推 关系 产生的迭代序列 。这种方法算为简单迭代法。 0)( xf )( xx x , 0 bax ,.1,0)( k1k kxx kx 例题 例 2.2.1 试用迭代法求方程 在区间 (1， 2)内的实根。 解：由 建立迭代关系 k=10,1,2,3 . 计算结果如下 : 3 1 xx 01)( 3 xxxf 31 1 kk xx 例题 精确到小数点后五位 510213 24 7 2.1 x 例题 但如果由 建立迭代公式 仍取 ，则有 ， 显然结果越来越大， 是发散序列 1x 3 x ,. .2,1131 kxx kk 5.10 x 2 .3 7 51 x 1 2 .3 92 x kx 迭代法的收敛性 定理 2.2.1（压缩映像原理） 设迭代函数 在闭区间 上满足 （ 1） （ 2） 满足 Lipschitz条件 即 有 且 。 )(x , ba ,)(, baxbax )(x , 21 baxx )()( 2121 xxLxx 10 L 压缩映像原理 则 在 上存在 唯一解 ， 且对 ，由 产生 的序列 收敛于 。 并且有误差估计式 : )( xx ,0 bax )( k1k xx . 1kx x , ba x 1 01 * xx L Lxx k k 压缩映像原理 证明：不失一般性 ,不妨设 否则 为方程的根。 首先证明根的存在性 令 bbaa )(,)( ba或 xxx )()( 压缩映像原理 则 ， 即 由条件 2） 是 上的连续函数 是 上的连续函数。 故由零点定理 在 上至少有一根 0)()( aaa 0)( b 0)()( ba )(x , ba )( x所以 , ba0)( x , ba ),( bax 压缩映像原理 再证根的唯一性 设有 均为方程的根 则 因为 0L1 ，所以只可能 ， 即根是唯一的。 , 21 baxx |)()(| 212121 xxLxxxx 21 xx 压缩映像原理 最后证迭代序列的收敛性 与 n 无关，而 0L1 即 |)()(| 1 xxxx nn 由于 | 1 xxL n | 0 xxL n . xx , 0因为 0lim|lim 0 nnnn Lxxxx所以 xx nnlim 压缩映像原理 误差估计 若 满足定理 2.2.1条件，则 这是事后估计，也就是停机标准。 L越小，收敛速度越快。 这是事前估计。选取 n，预先估计迭代次数。 )( xx |L1 L| 1nn xxxx n |L1 L| 01 n xxxx n 例题 例 2.2.2 证明函数 在区间 1， 2上满足迭代收敛条件。 证明： 3 1)x( x 上严格单调增函数。是区间所以 因为 ,)( 2,10)1( 3 1 )x( 3 2 bax xx 例题 2,1143 1|)1(31|)(| 33 2 xLxx又 23)2(12)1( 33 ，而 ）。满足条件（，所以即 1)(2,1)2(),1( x ）。满足条件（所以 2)( x 满足压缩映像原理。在故 2,11)x( 3 x 例题 若取迭代函数 ， 不满足压缩映像原理，故不能肯定 收敛到方程的根。 1)x( 3 x 2,13|3|)(| 2 xxx因为 ,. .1,0)(1 nxx nn 简单迭代收敛情况的几何解释 压缩映像原理推论 推论 设迭代函数 在闭区间 上满足 )(x ,1 baC * 10 |)(|, xx L Lxbax k 收敛于则 定理 2.2.2 设迭代函数 在 上连续可微 )(x 证明（略） 就收敛于充分接近于则只要 *0 * *, 1|)(| xxxx x k 的邻域*x 2.2.2 Steffensen加速收敛法 迭代法收敛的阶 定义 2.2.1 设序列 收敛到 ，若有实 数 和非零常数 C， 使得 其中， ，则称该序列是 p 阶收敛的， C 称为渐进误差常数。 0nx *x 1p Cee p n n n 1lim *xxe nn 迭代法收敛的阶 当 p=1时，称为线性收敛 (0c1时，称为超线性收敛； 当 p=2时，称为平方收敛或二次收敛。 迭代法收敛的阶 定理 2.2.2 设 是方程 的不动 点， 若为足够小的正数 。 如果 且 ，则从任意 出发，由 产生的序列 收 敛到 ，当 时敛速是线性的。 *x )( xx , * xx Cx)( 1|)(| * x 0 x )(1 kk xx 0 nx *x 0)( x 迭代法收敛的阶 证明： 满足压缩映像原理 知，及由 Cxx )(1|)(| * 足够小时，有 )(1|)(| xLx |)(|)()(|)(| * xxxxxxxx x 有因此，对于 迭代法收敛的阶 敛速是线性的 线性收敛到 。 0)()()(limlim * * 1 n xxx xxee n n nn n 因为 。收敛到故 *0 xx n 满足压缩映像原理，所以即 )(,)( xx 0 nx所以 *x Steffensen迭代格式 由线性收敛知 当 n充分大时有 即 0limlim 1 1 2 n Ce e e e n n nn n n n n n e e e e 1 1 2 * * 1 * 1 * 2 xx xx xx xx n n n n Steffensen迭代格式 展开有： nnn nn n xxx xxxx 12 2 1* 2 )( 2*12 1*2 )(2)( xxxxxxxx nnnn 2*12 12*2*2 )(2)( xxxxxxxxxxx nnnnnn *12 1*2*2 2 xxxxxxxxx nnnnnn 2 1212* )2( nnnnnn xxxxxxx Steffensen迭代格式 已知 ，则 ， 改成 nx )(1 nn xx )(2 nn xx nnn nn nn nn nn xyz xy xx yz xy 2 )( )( )( 2 1 n=0， 1， 2， Steffensen迭代格式 也可以改写成 其中迭代函数 ,.)1,0()(1 nxx nn xxx xxxx )(2)( )()( 2 Steffensen迭代法收敛的充要条件 定理 2.2.3 ,)( *1 xxCx ，设函数 。件是的不动点的充分必要条是 )()( * xxxxx ，则为足够小的正数，且 1)( * x Steffensen迭代法收敛的充要条件 证明：必要性 的不动点，是因为 )(* xxx )(2)()()( 2 xxxxxxx 由于 ，所以 0)(lim * xxxx ，故有 0)(lim * xxxx )( * xx 即 的不动点。是所以 )(* xxx Steffensen迭代法收敛的充要条件 充分性 的不动点有是由 )(* xxx xxx xxxx xxxx )(2)( )(lim)(lim 2 * 1)(2)()( 1)()(2lim * xxx xxx xx o o 型 01)( 1)()(2lim 2* * * x xxx xx 的不动点。是所以 )(* xxx Steffensen算法的收敛速度 ! )( )( lim )(0)( 0)(.)()( , ),1()(,)(4.2.2 *)( * * 1 * 0 10 *)( *)1(* * * p x xx xx xpx xxxx xxx xx pCxxxx p p n n n n kk p p p ，且阶收敛速度收敛到，以列 产生的序，由，则而 如果为足够小的正数 的不动点是设定理 Steffensen算法的收敛速度 定理 2.2.5 在定理 2.2.3假设下，若 产生的序列 至少平方收敛到 。 ,. .2,1,0 2 )( )( )( 2 1 n xyz xy xx yz xy S t e f f e n s e n nnn nn nn nn nn 迭代格式则由 2C)( x 0 nx *x *x Steffensen算法的收敛速度 的不动点，是证明： )(* xxx 。即 )( * xx 1)( 1 1)( lim )( lim * * * x x xx xx xx o o xx 型 又因为 Steffensen算法的收敛速度 * )(2)(lim * xx xxx xx 及 )1)(2)()(lim * xxx xx o o 型 1)(2)()( * xxx 2* 1)( x Steffensen算法的收敛速度 * * * )()(lim)( * xx xxx xx 于是有 * * 2 )(2)( )( lim * xx x xxx xx x xx * 2 * )(2)( )( lim1 * xx xxx xx xx xx 01)( 1)(1 2* 2* xx Steffensen算法的收敛速度 由定理 2.2.4知 至少以平方速度 收敛到 。 也就是说：简单迭代法是线性收敛； Steffensen迭代至少平方以上收敛（加速 收敛）。 0 nx *x 例题 例 2.2.3试用 Steffensen算法求解方程 解法一、取 ，由 013 xx 3 1)( xx nnn nn nn nn nn xyz xy xx yz xy 2 )( )( )( 2 1 n = 0， 1， 2， 例题 取初值 ，计算结果如下： 5.1 0 x N Xn Yn Zn 0 1.5 1.357208808 1.330860959 1 1.324899181 1.324752379 1.324724496 2 1.324717957 1.324717957 1.324717957 例题 解法二、取 ，由 对于该迭代函数在一般迭代法中是发散的， 而 Steffensen格式却是收敛的。 1)( 3 xx nnn nn nn nn nn xyz xy xx yz xy 2 )( )( )( 2 1 n=0， 1， 2， 例题 取初值 ，计算结果如下： N Xn Yn Zn 0 1.5 2.375 1.239648437 1 1.416292975 1.840921915 5.238872769 2 1.355650442 1.491398279 2.317270699 3 1.328948777 1.347062883 1.444351224 4 1.324804489 1.325173544 1.327117281 5 1.324717944 1.324718152 1.324718980 6 1.324717957 5.10 x Steffensen迭代格式几何解释 Steffensen迭代算法 1 10 0 2 001 20 0 100 210 :)3( ; )4 );2/()()3 ;3|2|)2 );();()1 |)(|w h i l e)2( ;,)1( x e ndw hi l e xx xyzxyxx t he nxyzif yzxy xx x 输出 步做第 做 输入 Steffensen迭代算法 2.2.2 Steffensen加速收敛法 迭代法收敛的阶 定义 2.2.1 设序列 收敛到 ，若有实 数 和非零常数 C， 使得 其中， ，则称该序列是 p 阶收敛的， C 称为渐进误差常数。 0nx *x 1p Cee p n n n 1lim *xxe nn 迭代法收敛的阶 当 p=1时，称为线性收敛 (0c1时，称为超线性收敛； 当 p=2时，称为平方收敛或二次收敛。 2.3 Newton迭代法 设 x * 是方程 f (x ) = 0的根，又 x0 为 x * 附近的一个值 ，将 f (x ) 在 x0附近做泰勒 展式 令 ，则 之间和在其中 0 2 0000 )()(2 1)()()()( xx fxxxfxxxfxf *xx )()(21)()()()(0 20*00*0* fxxxfxxxfxf Newton迭代法 去掉 的二次项，有： 即 以 x1代替 x0重复以上的过程，继续下去得： 0* xx 0)()()( 000*0 xfxxfxxf )( )( 0 0 01 * xf xfxxx Newton迭代法 ,. . .1,0 )( )( )( )( )( )( 1 n xf xf xxx xf xf xx n n nnn 令 以此产生的序列 Xn得到 f(x)=0的近似 解，称为 Newton法，又叫切线法。 Newton迭代法几何解释 几何意义 Newton迭代法收敛性 定理 2.3.1 设函数 ，且满足 若初值 时，由 Newton法产生的序列收 敛到 在 上的唯一根 ,并且收敛阶至 少为 2, 。 2)( Cxf ;0)()2 ;0)()1 af af 0 x 0)( xf 20)( 时，收敛阶为af 证明迭代序列的收敛性 )( )()( * * 1 k n nn xf xfxfxxxx 由于 )(2 )( )( )( 2 )( )()()( 2* 2* * * n n n nnkk n xf xxf xf xx f xxxfxfxf xx . xx nnlim 。故收敛阶至少为 2 |)(2| |)(| |)(2| |)(| lim | | lim * * 2* * 1 xf xf xf f xx xx x n n n n n n n 例题 例 2.3.1 用 Newton法求 的 近似解。 解：由零点定理。 0c o s)( xxxf 内有根。在 )2,0(0c os xx 迭代公式得及 由 N e w t o n xxxf ) 2 ,0(0s i n1)( ,.1,0s i n1 c os1 nx xxxx n nn nn 08 51 3373 9.0 73 90 85 13 3.073 90 85 13 3.0 73 90 85 17 8.0;73 93 61 33.0 4 4 * 43 21 0 xx xx xx x 故取 得取 例 2.3.2 用 Newton法计算 。 解： 20)( 2 aaxxf 其中 迭代公式得及 由 N e w t o n x x xxxxf 2 2 )(,2)( 2 ,.1,0)2(212 2 2 1 nxxx xxx n n n n nn 。有十位有效数的近似值 是已的精确值相比，。与 ，则取 33 210 2414213562.1 414215686.11 . 4 1 6 6 6 6 6 75.1 xx xxx 例 2.3.3 用 Newton法求 的近似解。 解：由零点定理。 01s in9)( 2 xxxf 内有根。在 ) 2 ,0(0)( xf 迭代公式得及 由 N e w t o n xxxf )4.0,4.0(0c o s18x)( ,.1,0c os1 1s i n 2 1 nx xxxx n nn nn N Xn n xn 0 1 2 0.4 0.39194423490290 0.39184808256798 3 4 5 0.39184690717420 0.39184690700265 0.39184690700265 N=4时小数点后 14位无变化 ,x4为近似解 Newton迭代法算法框图 Newton迭代法算法 。输出 ）转（ 做 输入 1 10 1001 0 0100 0 :)4( ; ;2)3 ;)2 ;/)1 |w h i l e( 3) );();()2( ;,)1( x e ndw hi l e xx ffxx f xffxff x Newton迭代法收敛性 定理 2.3.2 设函数 ，且满足 若初值 满足 时，由 Newton 法产生的序列收敛到 在 a,b上的唯一根。 ,)( 2 baCxf 上恒正或恒负。在 ,)()3 );,(,0)()2 ;0)()()1 baxf baxxf bfaf ,0 bax 0)()( 00 xfxf 0)( xf Newton迭代法收敛性 证明： 根的存在性 根的唯一性 内至少有一个根。 在知）及由条件（ ),( 0)(,)(1 ba xfbaCxf 。记此根为内有唯一根在 上严格单调函数，因此是故 保号，知及由 *,),( 0)(,)( )(,bC a ,)(,0)( xba xfbaxf xfxfxf Newton迭代法收敛性 收敛性 )()(0 )( )( 0)(,0)( ,0)(,0)()( 2 .3 .4( 0)(,0)(,0)(,0)( 0100 0 0 0 01 00 0 * 000 xxxfxf x xf xf xx xfxf xfbxxxfxf xfxfbfaf 即有 ，所以 知，由 ），其他情形见图 不妨设 Newton迭代法收敛性 继续上述推理有代替。再以因此有 两式相减 展式由另一方面 0101 * 2 0 * 0 1 * 2 0 * 0 * 00 * 0)( )( )( 2 1 )( 2 1 )()()(0 T a y l or, xxxxx xx xf f xx xxfxxxfxfxf Newton迭代法收敛性 。，由根的唯一性知可得时当 由 。故必有极限，记 。是单调减有下界的序列故序列 * 1 0 011 * 0)(, ,.2,1 )( )( lim . xaafn n xf xf xx ax x xxxxx n n nn n n n nn Newton迭代法收敛性 推论 在定理 2.3.1条件下， Newton迭代 法具有平方收敛速度。 故结论成立。 之间，则与介于其中， 证明，一般有类似定理证明 0 )( )( 2 1 lim )( )( )( 2 1 1.3.2 * * 2 1 * 2* 1n * xf xf e e xx xx xf f xx n n n nn n n n 简化 Newton迭代法 ,. . . .1,0 )( )( )( )( )( )( 0 1 0 n xf xf xxx xf xf xx n nnn 令 用 x0点的导数替换 x点的导数 ,以此产生的序列 Xn得到 f(x)=0的近似解，称为简化 Newton法。 简化 Newton迭代法 X2 x1 x0 简化 Newton迭代法 ,. .1,0 )( )( )( )( 1 n c xf xxx c xf xx n nnn 令 用常数 c替换 x点的导数 ,以此产生的序列 Xn得到 f(x)=0的近似解，称为推广简 化 Newton法。 简化 Newton迭代法 收敛时， 令 n x c xf L c xf x c xf xx 2 )( 0 1| )( 1)(| )( )( 下山 Newton迭代法 称 为为 下山因子 n xf xf xxx xf xf xx n n nnnn 10 ,.1,0 )( )( )( )( )( )( 1 令 ,. 2 1, 2 1,1 2n 称为下山 Newton法，通常选 。 直到 n nn xfxf * 1 |)(|)(| 记 下山 Newton迭代法 例 2.3.3 用下山 Newton法，求 1 3 1)(, 3 )( 0 3 2 3 1 2 3 3 n n n nnn x x x xx xxfx x x解：f 的根。x x n 0 -0.99 0.666567 1 1 0.5 0.25 32.50598 15.75799 7.38400 1146.5 1288.55 126.816 0.125 0.0625 3.19700 1.10350 7.69495 -0.65559 2 1 4.41181 19.10899 0.5 2.60916 3.31162 0.125 0.27594 5 1 1.73205 0.00000 nx )( nxfn 弦割法 Newton迭代法有一个较强的要求是 且存在。因此，用弦的斜率 近似的替代 。 0)( xf )(xf )( )()( )( )(,(P)(,(P ,)( 1 01 01 1 111000 10 * xx xx xfxf xfy xfxxfx bxaxxbaxf 得弦的方程及则过 ，取上有唯一零点在设 弦割法 令 y=0,解得弦与 x轴的交点是坐标 x2 . ,.)2,1()( )()( ., )( )()( 0)( )()( )( 0 0 1 320 1 01 01 12 12 01 01 1 法称之为定端点弦 计算再由 解得 割 nxf xfxf xx xx xxx xf xfxf xx xx xx xx xfxf xf n n n nn 弦割法 ., ,.)2,1()( )()( , 1 1 1 321 法又称快速弦法称之为变端点弦 以此类推计算若由 割割 nxf xfxf xx xx xxx n nn nn nn 弦截法的几何解释 定理 2.3.3 设函数 ，且满足 则存在 ,当 时， ,)( *2 xxCxf 。0)()2 ;0)()()1 * * xf xfxf 0 , 0*0*10 xx，xx 。的敛速收敛到以确定的序列 由 线性收敛到确定的序列 由 * 0 1 1 * 0 0 1 2 15 ,. .2,1)( )()( )2( ; ,. .2,1)( )()( )1( xpx nxf xfxf xx xx xx nxf xfxf xx xx n n n nn nn n n n n nn 定理 2.3.4 设函数 ，且满足 若初值 , 满足 时，由 弦割法 法产生的序列收敛到 在 a,b上的唯一根。 ,)( 2 baCxf 上恒正或恒负。在 ,)()3 );,(,0)()2 ;0)()()1 baxf baxxf bfaf , 10 baxx 0100 ,0)()( xxxfxf 0)( xf 例题 例 2.4.4 用 弦割法 求方程 在区间（ 1， 2）内的实根。 解：取 x0=1,x1=2,代入公式 2.4.2计算结果 ,如 表 2.4.1所示。 01)( 3 xxxf k xk f(xk) 0 1 -1 1 2 5 2 1.166666667 -0.57870369 3 1.253112023 -0.28536302 4 1.337206444 0.053880579 5 1.323850096 -0.0036981168 6 1.324707936 -4.273521*10E-5 7 1.324717965 3.79*10E-8 例 2.3.5 用 Newton法求 的近似解。 解：由零点定理。 01s in9)( 2 xxxf 内有根。在 ) 2 ,0(0)( xf 迭代公式得及 由 N e w t o n xxxf )4.0,4.0(0c o s18x)( ,.1,0c os1 1s i n 2 1 nx xxxx n nn nn N Xn n xn 0 1 2 3 4 0.4 0.39194423490290 0.39184808256798 0.39184692120360 0.39184690717420 5 6 7 8 0.39184690700472 0.39184690700267 0.39184690700265 其中 ,x1由 Newton法算出 ,N=7时小数点后 14位无变化 ,x4为近似解 求解方程 f(x)=0的 弦割法 。输出 停止计算输出失败信息 时做 输入 Lx NL ffffxxxx LLxfff ff xx xx f xffxffL Nxx ,)4( ;e n dw h i l e ,t h e nif)3 ;)2 ;1);(;)1 |w h i l e)3( );(),(,0)2( ;,:)1( 2 2110210 221 01 01 12 1 1100 10