第7章-非线性方程求根1

1、1第第7 7章章 非线性方程求根非线性方程求根 7.1 7.1 方程求根与二分法方程求根与二分法 7.1.1 7.1.1 引言引言0)(xf（1.1） 本章主要讨论单变量非线性方程 的求根问题，这里 .,)(,RbaCxfx 一类特殊的问题是多项式方程 ),0()(01110aaxaxaxaxfnnnn（1.2）的求根问题，其中系数 为实数. ), 1 ,0(niai2 方程 的根 ，又称为函数 的零点，它使 ，若 可分解为 0)(xf*x)(xf0*)(xf)(xf),(*)()(xgxxxfm其中 为正整数，且 m.0*)(xg 当 时，称 为单根，若 称 为（1.1）的 重根，或 为 的

2、 重零点. 1m*x1m*xm*x)(xfm 若 是 的 重零点，且 充分光滑，则 *x)(xfm)(xg.0*)(,0*)(*)(*)()()1(xfxfxfxfmm 当 为代数多项式（1.2）时，根据代数基本定理可知， 次方程在复数域有且只有 个根（含复根， 重根为 个根）. )(xfmmnn 时方程的根是大家熟悉的， 时虽有求2, 1n4,3n3根公式但比较复杂，可在数学手册中查到，但已不适合于数值计算，而 时就不能用公式表示方程的根. 5n 通常对 的多项式方程求根与一般连续函数方程（1.1）一样都可采用迭代法. 3n 迭代法要求先给出根 的一个近似，若 且 ，根据连续函数性质可知 在

3、 内至少有一个实根，这时称 为方程（1.1）的有根区间.通常可通过逐次搜索法求得方程（1.1）的有根区间.*x,)(baCxf0)()(bfaf0)(xf),(ba,ba 例例1 1 求方程 的有根区间.077.418.381.11)(23xxxxf 解 根据有根区间定义，对 的根进行搜索计算，结果如下： 0)(xf4的符号)(6543210 xfx由此可知方程的有根区间为 .6,5,4,3,2,15 7.1.2 7.1.2 二分法二分法 考察有根区间 ，取中点 将它分为两半，假设中点 不是 的零点，然后进行根的搜索.,ba2/)(0bax0 x)( xf 检查 与 是否同号，如果确系同号，说

4、明所求的根 在 的右侧, 这时令 ；否则 必在 的左侧，这时令 . 见图7-1.)(0 xf)(af*x0 xbbxa101,*x0 x011,xbaa图7-16 不管出现哪一种情况，新的有根区间 的长度仅为 的一半. ,11ba,ba 对压缩了的有根区间 又可施行同样的手续，即用中点 将区间 再分为两半，然后通过根的搜索判定所求的根在 的哪一侧，从而又确定一个新的有根区间 ，其长度是 的一半.1x,11ba2/)(111bax,11ba,22ba,11ba 如此反复二分下去，即可得出一系列有根区间 ,2211kkbabababa其中每个区间都是前一个区间的一半，因此 的长度 ,kkbakkk

5、abab2/)(当 时趋于零，就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点 ，该点显然就是所求的根.k*x7 每次二分后，设取有根区间 的中点 ,kkba2/)(kkkbax作为根的近似值，则在二分过程中可以获得一个近似根的序列 ,210kxxxx该序列必以根 为极限.*x 由于 ,2/)(2/)(*1kkkkababxx（1.3）只要二分足够多次（即 充分大），便有 k,*kxx这里 为预定的精度.8 例例2 2 求方程 01)(3xxxf在区间 内的一个实根，要求准确到小数点后第2位.5.1 ,0.1 解解 这里 ，而 5.1,0.1ba0)(,0)(bfaf 取 的中点

6、，将区间二等分，由于 ，即 与 同号，故所求的根 必在 右侧，这时应令 ，而得到新的有根区间,ba25.10 x0)(0 xf)(0 xf)(af*x0 x5.1,25.1101bbxa.,11ba 如此反复二分下去, 按误差估计（1.3）式, 欲使,005.021212/)(2/)(*11kkkkkababxx9只需 ，即只要二分6次，便能达到预定的精度. 6k 计算结果如表7-1. 3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15 .10 .10)(17符号表kkkkxfxbak1

7、0 二分法是计算机上的一种常用算法，计算步骤为： 步骤步骤1 1 准备准备 计算 在有根区间 端点处的值 )(xf).(),(bfaf,ba 步骤步骤2 2 二分二分 计算 在区间中点 处的值 )(xf2ba ).2(baf 步骤步骤3 3 判断判断 若 ，则 即是根，计算过程结束，否则检验. 0)2( baf2ba 若 ，则以 代替 ，否则以 代替 . 0)()2(afbaf2ba b2ba a 反复执行步骤2和步骤3，直到区间 长度小于,ba11允许误差 ，此时中点 即为所求近似根. 2ba 12 7.2 7.2 迭代法及其收敛性迭代法及其收敛性 7.2.1 7.2.1 不动点迭代法不动点

8、迭代法 将方程（1.1）改写成等价的形式 ).(xx（2.1）若要求 满足 ，则 ；反之亦然，称 为函数 的一个不动点. *x0*)(xf*)(*xx*x)(x 求 的零点就等价于求 的不动点，选择一个初始近似值 ，将它代入(2.1)右端，即可求得 )(xf)(x0 x).(01xx如此反复迭代计算 )., 1 ,0()(1kxxkk（2.2）13 称为迭代函数.如果对任何 ，由（2.2）得到的序列 有极限 )(x,0baxkx.*limxxkk则称迭代方程(2.2)收敛，且 为 的不动点，故称（2.2）为不动点迭代法不动点迭代法. *)(*xx)(x 上述迭代法是一种逐次逼近法，其基本思想是

9、将隐式方程（2.1）归结为一组显式的计算公式（2.2），就是说，迭代过程实质上是一个逐步显示化的过程. 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 )(xxxy)(xyxy .*P 对于 的某个近似值 ，在曲线 上可确定一点 ，它以 为横坐标，而纵坐标则等于 *x0 x)( xy0P0 x.)(10 xx14过 引平行 轴的直线，设此直线交直线 于点 ，然后过 再作平行于 轴的直线，它与曲线 的交点记作 ，则点 的横坐标为 ，纵坐标则等于0Pxxy 1Q1Qy)(xy1P1P1x)(1x.2x图7-215 例例3 3 求方程 01)(3xxxf（2.3）在 附近的根 5.10 x

10、.*x 解解 设将方程（2.3）改写成下列形式 .13xx 按图7-2中箭头所示的路径继续做下去，在曲线 上得到点列 ，其横坐标分别为依公式 求得的迭代值)(xy21, PP)(1kkxx.,21xx 如果点列 趋向于点 ，则相应的迭代值 收敛到所求的根 kP*Pkx.*x据此建立迭代公式 1632494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1027kkxkxk表).,2,1 ,0(131kxxkk各步迭代的结果见表7-2. 如果仅取6位数字，那么结果 与 完全相同，这时可以认为 实际上已满足方程(2.3)，即

11、为所求的根.7x8x7x17但若采用方程（2.3）的另一种等价形式13 xx建立迭代公式 .131kkxx仍取迭代初值 ，则有 5.10 x.39.12,375.221xx结果会越来越大，不可能趋于某个极限. 这种不收敛的迭代过程称作是发散发散的. 一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.18 7.2.2 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察 在 上不动点的存在唯一性. ,ba)(x 定理定理1 1 设 满足以下两个条件：,)(baCx 1 对任意 有 ,bax bxa)( 2 存在正常数 ，使对任意 都有 1L,bayx.

12、)()(yxLyx（2.4）则 在 上存在唯一的不动点 )( x,ba.*x 证明证明 先证不动点存在性. 若 或 ，显然 在 上存在不动点. aa)(bb)()( x,ba 因 ，以下设 及 ，定bxa)(aa)(bb)(19义函数.)()(xxxf显然 ，且满足 ，由连续函数性质可知存在 使 ，即 即为 的不动点.,)(baCxf)(,0)()(bfaaaf0)( bb),(*bax0*)(xf*),(*xxx)( x 再证唯一性. 设 都是 的不动点，则由(2.4)得 ,21baxx)( x.)()(21212121xxxxLxxxx引出矛盾. 故 的不动点只能是唯一的. 证毕.)( x

13、20 定理定理2 2 设 满足定理1中的两个条件，则对任意 ，由（2.2）得到的迭代序列 收敛到 的不动点 ，并有误差估计 ,)(baCx ,0baxkx)( x*x.1*01xxLLxxkk（2.5） 证明证明 设 是 在 上的唯一不动点，由条件1，可知 ，再由（2.4）得 ,ba,*bax)( x,baxk.*)()(*011xxLxxLxxxxkkkk因 ，故当 时序列 收敛到 .10 Lkkx*x 再证明估计式（2.5），由（2.4）有 .)()(111kkkkkkxxLxxxx（2.6）21反复递推得 .011xxLxxkkk于是对任意正整数 有p.1)(0101211211xxLL

14、xxLLLxxxxxxxxkkpkpkkkpkpkpkpkkpk在上式令 ，注意到 即得式（2.5）. 证毕.p*limxxpkp 迭代过程是个极限过程. 在用迭代法实际计算时，必须按精度要求控制迭代次数.22 误差估计式（2.5）原则上可用于确定迭代次数，但它由于含有信息 而不便于实际应用. L 根据式（2.6），对任意正整数 有 p.11)1(1121kkkkppkpkxxLxxLLxx在上式中令 知 p.11*1kkkxxLxx 由此可见，只要相邻两次计算结果的偏差 足够小即可保证近似值 具有足够精度.kkxx1kx 对定理1和定理2中的条件2，在使用时如果 且对任意 有 )( x,1b

15、aC,bax 23,1)(Lx（2.7）则由中值定理可知对 有 ,bayx).,(,)()()(bayxLyxyx表明定理中的条件2可用（2.7）代替. 例3中，当 时， ,在区间 中， ，故（2.7）成立. 31)(xx3/2)1(31)(xx2, 114131)(3/1 x又因 ，故定理1中条件1也成立.所以迭代法是收敛的. 23)(2133x而当 时， 在区间 中 不满足定理条件.1)(3 xx23)(xx2, 11)( x24 7.2.3 7.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 上面给出了迭代序列 在区间 上的收敛性，通常称为全局收敛性. 定理的条件有时不易检验，实际应用时通

16、常只在不动点 的邻近考察其收敛性，即局部收敛性.kx,ba*x 定义定义1 1 设 有不动点 ，如果存在 的某个邻域 ，对任意 ，迭代（2.2）产生的序列 ，且收敛到 ，则称迭代法（2.2）局部收敛局部收敛.)( x*x*x*:xxRRx0Rxk*x 定理定理3 3 设 为 的不动点， 在 的某个邻域连续，且 ，则迭代法（2.2）局部收敛.*x)( x)( x*x1*)( x 证明证明 由连续函数的性质，存在 的某个邻域 ，使对于任意 成立 *x*:xxRRx .1)(Lx25此外，对于任意 ，总有 ，这是因为 Rx Rx )(.*)()(*)(xxxxLxxxx于是依据定理2可以断定迭代过程

17、 对于任意初值 均收敛. 证毕.)(1kkxxRx 0 讨论迭代序列的收敛速度. 例例4 4 用不同方法求方程 的根 032x.3* x 解解 这里 ，可改写为各种不同的等价形式 ，其不动点为 由此构造不同的迭代法：3)(2 xxf)( xx.3* x.1132)3(*)(,12)(,3)(,3)1(221xxxxxxxxxkkk26.1134.0231*)(,211)(),3(41)(),3(41)3(221xxxxxxxxxkkk.0)3(*)(),31(21)(),3(21)(),3(21)4(21xxxxxxxxxkkk取 ，对上述4种迭代法，计算三步所得的结果如下表. 20 x.1*

18、)(,3)(,3)(,3)2(21xxxxxxxkk27732051.1732361.15.1873732143.173475.129275.175.15.13122220)4()3()2()1(373210 xxxxxkk迭代法迭代法迭代法迭代法计算结果表 注意 ，从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件，迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 . 7320508.13 0*)( x28 定义定义2 2 设迭代过程 收敛于方程 的根 ，如果迭代误差 当 时成立下列渐近关系式 )(1kkxx)(xx*x*

19、xxekkk),0(1CCeepkk常数则称该迭代过程是 阶收敛阶收敛的. 特别地, 时称线性收线性收敛敛， 时称超线性收敛超线性收敛， 时称平方收敛平方收敛. p1p1p2p 定理定理4 4 对于迭代过程 ，如果 在所求根 的邻近连续，并且 )(1kkxx)()(xp*x,0*)(,0*)(*)(*)()1( xxxxpp（2.8）则该迭代过程在点 邻近是 阶收敛的. *xp29 证明证明 由于 ，据定理3立即可以断定迭代过程 具有局部收敛性. 0*)( x)(1kkxx 再将 在根 处做泰勒展开，利用条件（2.8），则有 )(kx*x.*,*)(!)(*)()()(之间与在xxxxpxxk

20、pkpk注意到 ，由上式得 *)(,)(1xxxxkk,*)(!)(*)(1pkpkxxpxx因此对迭代误差，当 时有 k.!*)()(1pxeeppkk（2.9）这表明迭代过程 确实为 阶收敛. 证毕. )(1kkxxp30 上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取. 如果当 时 ，则该迭代过程只可能是线性收敛. )( x,bax 0)( x 在例4中，迭代法（3）的 ，故它只是线性收敛，而迭代法（4）的 ，而 由定理4知 ，即该迭代过程为2阶收敛. 0*)( x0*)( x,6)(3xx .032*)( x2p31 7.3 7.3 迭代收敛的加速方法迭代收敛的加速方法 7.3

21、.1 7.3.1 埃特金加速收敛方法埃特金加速收敛方法 设 是根 的某个近似值，用迭代公式校正一次得 0 x*x)(01xx由微分中值定理，有 *),)(*)()(*001xxxxxx其中 介于 与 之间.0 x*x 假定 改变不大，近似地取某个近似值 ，则有 )( xL*).(*01xxLxx（3.1）若将校正值 再校正一次，又得 )(01xx32),(12xx由于 *),(*12xxLxx将它与（3.1）式联立，消去未知的 ，有 L.*1021xxxxxxxx由此推知 .2)(2*01220100122120 xxxxxxxxxxxxx在计算了 及 之后，可用上式右端作为 的新近似，记作

22、. 1x2x*x1x33 一般情形是由 计算 ，记 kx21,kkxx)., 1 ,0(/)(2)(2212211kxxxxxxxxxxkkkkkkkkkk（3.2）(3.2)称为埃特金（Aitken）加速方法. 可以证明 .0*lim1xxxxkkk它表明序列 的收敛速度比 的收敛速度快.kxkx34 7.3.2 7.3.2 斯蒂芬森迭代法斯蒂芬森迭代法 埃特金方法不管原序列 是怎样产生的，对 进行加速计算，得到序列 . kxkxkx 如果把埃特金加速技巧与不动点迭代结合，则可得到如下的迭代法： )., 1 ,0(2)(),(),(21kxyzxyxxyzxykkkkkkkkKkk（3.3）

23、称为斯蒂芬森(Steffensen)迭代法. 它的理解为，要求 的根 ，令 ， ，已知 的近似值 及 ，其误差分别为 )(xx*xxxx)()(0*)(*)(xxx*xkxky35x 过 及 两点做线性插值函数，它与 轴交点就是（3.3）中的 ，即方程 )(,(kkxx)(,(kkyy1kx0)()()()(kkkkkkxxxyxyx的解 .2)()()()()(12kkkkkkkkkkkkkxxyzxyxxyxyxxx 实际上（3.3）是将不动点迭代法（2.2）计算两步合并成一步得到的，可将它写成另一种不动点迭代 ), 1 ,0()(1kxxkk（3.4）.)()(,)()(kkkkkkkkkkyzyyyxyxxx36其中 .)(2)()()(2xxxxxxx（3.5） 定理定理