《非线性方程求根》ppt课件

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

2、是 的 重零点，且 充分光滑，那么 *x)(xfm)(xg.0*)(,0*)(*)(*)()()1(xfxfxfxfmm 当 为代数多项式1.2时，根据代数根本定理可知， 次方程在复数域有且只需 个根含复根， 重根为 个根. )(xfmmnn 时方程的根是大家熟习的， 时虽有求2, 1n4,3n根公式但比较复杂，可在数学手册中查到，但已不适宜于数值计算，而 时就不能用公式表示方程的根. 5n 通常对 的多项式方程求根与普通延续函数方程1.1一样都可采用迭代法. 3n 迭代法要求先给出根 的一个近似，假设 且 ，根据延续函数性质可知 在 内至少有一个实根，这时称 为方程1.1的有根区间.通常可经

3、过逐次搜索法求得方程1.1的有根区间.*x,)(baCxf0)()(bfaf0)(xf),(ba,ba 例1 求方程 的有根区间.077.418.381.11)(23xxxxf 解 根据有根区间定义，对 的根进展搜索计算，结果如下： 0)(xf的符号)(6543210 xfx由此可知方程的有根区间为 .6,5,4,3,2,1 7.1.2 7.1.2 二分法二分法 调查有根区间 ，取中点 将它分为两半，假设中点 不是 的零点，然后进展根的搜索.,ba2/)(0bax0 x)( xf 检查 与 能否同号，假设确系同号，阐明所求的根 在 的右侧, 这时令 ；否那么 必在 的左侧，这时令 . 见图7-

4、1.)(0 xf)(af*x0 xbbxa101,*x0 x011,xbaa图7-1 不论出现哪一种情况，新的有根区间 的长度仅为 的一半. ,11ba,ba 对紧缩了的有根区间 又可施行同样的手续，即用中点 将区间 再分为两半，然后通过根的搜索断定所求的根在 的哪一侧，从而又确定一个新的有根区间 ，其长度是 的一半.1x,11ba2/)(111bax,11ba,22ba,11ba 如此反复二分下去，即可得出一系列有根区间 ,2211kkbabababa其中每个区间都是前一个区间的一半，因此 的长度 ,kkbakkkabab2/)(当 时趋于零，就是说，假设二分过程无限地继续下去，这些区间最终

5、必收缩于一点 ，该点显然就是所求的根.k*x 每次二分后，设取有根区间 的中点 ,kkba2/)(kkkbax作为根的近似值，那么在二分过程中可以获得一个近似根的序列 ,210kxxxx该序列必以根 为极限.*x 由于 ,2/)(2/)(*1kkkkababxx1.3只需二分足够多次即 充分大，便有 k,*kxx这里 为预定的精度. 例2 求方程 01)(3xxxf在区间 内的一个实根，要求准确到小数点后第2位.5.1 ,0.1 解 这里 ，而 5.1,0.1ba0)(,0)(bfaf 取 的中点 ，将区间二等分，由于 ，即 与 同号，故所求的根 必在 右侧，这时应令 ，而得到新的有根区间,b

6、a25.10 x0)(0 xf)(0 xf)(af*x0 x5.1,25.1101bbxa.,11ba 如此反复二分下去, 按误差估计1.3式, 欲使,005.021212/)(2/)(*11kkkkkababxx只需 ，即只需二分6次，便能到达预定的精度. 6k 计算结果如表7-1. 3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15 .10 .10)(17符号表kkkkxfxbak 二分法是计算机上的一种常用算法，计算步骤为： 步骤1 预备 计算 在有根区间 端点处的值 )(xf).

7、(),(bfaf,ba 步骤2 二分 计算 在区间中点 处的值 )(xf2ba ).2(baf 步骤3 判别 假设 ，那么 即是根，计算过程终了，否那么检验. 0)2( baf2ba 假设 ，那么以 替代 ，否那么以 替代 . 0)()2(afbaf2ba b2ba a 反复执行步骤2和步骤3，直到区间 长度小于,ba允许误差 ，此时中点 即为所求近似根. 2ba 7.2 7.2 迭代法及其收敛性迭代法及其收敛性 7.2.1 不动点迭代法 将方程1.1改写成等价的方式 ).(xx2.1假设要求 满足 ，那么 ；反之亦然，称 为函数 的一个不动点. *x0*)(xf*)(*xx*x)(x 求 的

8、零点就等价于求 的不动点，选择一个初始近似值 ，将它代入(2.1)右端，即可求得 )(xf)(x0 x).(01xx如此反复迭代计算 )., 1 ,0()(1kxxkk2.2 称为迭代函数.假设对任何 ，由2.2得到的序列 有极限 )(x,0baxkx.*limxxkk那么称迭代方程(2.2)收敛，且 为 的不动点，故称2.2为不动点迭代法. *)(*xx)(x 上述迭代法是一种逐次逼近法，其根本思想是将隐式方程2.1归结为一组显式的计算公式2.2，就是说，迭代过程本质上是一个逐渐显示化的过程. 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点 )(xxxy)(xyxy .*P 对于

9、的某个近似值 ，在曲线 上可确定一点 ，它以 为横坐标，而纵坐标那么等于 *x0 x)( xy0P0 x.)(10 xx过 引平行 轴的直线，设此直线交直线 于点 ，然后过 再作平行于 轴的直线，它与曲线 的交点记作 ，那么点 的横坐标为 ，纵坐标那么等于0Pxxy 1Q1Qy)(xy1P1P1x)(1x.2x图7-2 例3 求方程 01)(3xxxf2.3在 附近的根 5.10 x.*x 解 设将方程2.3改写成以下方式 .13xx 按图7-2中箭头所示的途径继续做下去，在曲线 上得到点列 ，其横坐标分别为依公式 求得的迭代值)(xy21, PP)(1kkxx.,21xx 假设点列 趋向于点

10、 ，那么相应的迭代值 收敛到所求的根 kP*Pkx.*x据此建立迭代公式 32494.1432472.1832588.1332472.1733086.1232473.1635721.1132476.155.1027kkxkxk表).,2, 1 ,0(131kxxkk各步迭代的结果见表7-2. 假设仅取6位数字，那么结果 与 完全一样，这时可以以为 实践上已满足方程(2.3)，即为所求的根.7x8x7x但假设采用方程2.3的另一种等价方式13 xx建立迭代公式 .131kkxx仍取迭代初值 ，那么有 5.10 x.39.12,375.221xx结果会越来越大，不能够趋于某个极限. 这种不收敛的迭

11、代过程称作是发散的. 一个发散的迭代过程，纵使进展了千百次迭代，其结果也是毫无价值的. 7.2.2 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先调查 在 上不动点的存在独一性. ,ba)(x 定理1 设 满足以下两个条件：,)(baCx 1 对恣意 有 ,bax bxa)( 2 存在正常数 ，使对恣意 都有 1L,bayx.)()(yxLyx2.4那么 在 上存在独一的不动点 )( x,ba.*x 证明 先证不动点存在性. 假设 或 ，显然 在 上存在不动点. aa)(bb)()( x,ba 因 ，以下设 及 ，定bxa)(aa)(bb)(义函数.)()(xx

12、xf显然 ，且满足 ，由延续函数性质可知存在 使 ，即 即为 的不动点.,)(baCxf)(,0)()(bfaaaf0)( bb),(*bax0*)(xf*),(*xxx)( x 再证独一性. 设 都是 的不动点，那么由(2.4)得 ,21baxx)( x.)()(21212121xxxxLxxxx引出矛盾. 故 的不动点只能是独一的. 证毕.)( x 定理2 设 满足定理1中的两个条件，那么对恣意 ，由2.2得到的迭代序列 收敛到 的不动点 ，并有误差估计 ,)(baCx ,0baxkx)( x*x.1*01xxLLxxkk2.5 证明 设 是 在 上的独一不动点，由条件1，可知 ，再由2.

13、4得 ,ba,*bax)( x,baxk.*)()(*011xxLxxLxxxxkkkk因 ，故当 时序列 收敛到 .10 Lkkx*x 再证明估计式2.5，由2.4有 .)()(111kkkkkkxxLxxxx2.6反复递推得 .011xxLxxkkk于是对恣意正整数 有p.1)(0101211211xxLLxxLLLxxxxxxxxkkpkpkkkpkpkpkpkkpk在上式令 ，留意到 即得式2.5. 证毕.p*limxxpkp 迭代过程是个极限过程. 在用迭代法实践计算时，必须按精度要求控制迭代次数. 误差估计式2.5原那么上可用于确定迭代次数，但它由于含有信息 而不便于实践运用. L

14、 根据式2.6，对恣意正整数 有 p.11)1(1121kkkkppkpkxxLxxLLxx在上式中令 知 p.11*1kkkxxLxx 由此可见，只需相邻两次计算结果的偏向 足够小即可保证近似值 具有足够精度.kkxx1kx 对定理1和定理2中的条件2，在运用时假设 且对恣意 有 )( x,1baC,bax ,1)(Lx2.7那么由中值定理可知对 有 ,bayx).,(,)()()(bayxLyxyx阐明定理中的条件2可用2.7替代. 例3中，当 时， ,在区间 中， ，故2.7成立. 31)(xx3/2)1(31)(xx2, 114131)(3/1 x又因 ，故定理1中条件1也成立.所以迭

15、代法是收敛的. 23)(2133x而当 时， 在区间 中 不满足定理条件.1)(3 xx23)(xx2, 11)( x 7.2.3 7.2.3 部分收敛性与收敛阶部分收敛性与收敛阶 上面给出了迭代序列 在区间 上的收敛性，通常称为全局收敛性. 定理的条件有时不易检验，实践应用时通常只在不动点 的临近调查其收敛性，即部分收敛性.kx,ba*x 定义1 设 有不动点 ，假设存在 的某个邻域 ，对恣意 ，迭代2.2产生的序列 ，且收敛到 ，那么称迭代法2.2部分收敛.)( x*x*x*:xxRRx0Rxk*x 定理3 设 为 的不动点， 在 的某个邻域延续，且 ，那么迭代法2.2部分收敛.*x)(

16、x)( x*x1*)( x 证明 由延续函数的性质，存在 的某个邻域 ，使对于恣意 成立 *x*:xxRRx .1)(Lx此外，对于恣意 ，总有 ，这是由于 Rx Rx )(.*)()(*)(xxxxLxxxx于是根据定理2可以断定迭代过程 对于恣意初值 均收敛. 证毕.)(1kkxxRx 0 讨论迭代序列的收敛速度. 例4 用不同方法求方程 的根 032x.3* x 解 这里 ，可改写为各种不同的等价形式 ，其不动点为 由此构造不同的迭代法：3)(2 xxf)( xx.3* x.1132)3(*)(,12)(,3)(,3)1(221xxxxxxxxxkkk.1134.0231*)(,211)

17、(),3(41)(),3(41)3(221xxxxxxxxxkkk.0)3(*)(),31(21)(),3(21)(),3(21)4(21xxxxxxxxxkkk取 ，对上述4种迭代法，计算三步所得的结果如下表. 20 x.1*)(,3)(,3)(,3)2(21xxxxxxxkk732051.1732361.15.1873732143.173475.129275.175.15.13122220)4()3()2()1(373210 xxxxxkk迭代法迭代法迭代法迭代法计算结果表 留意 ，从计算结果看到迭代法1及2均不收敛，且它们均不满足定理3中的部分收敛条件，迭代法3和4均满足部分收敛条件，且

18、迭代法4比3收敛快，因在迭代法4中 . 7320508.13 0*)( x 定义2 设迭代过程 收敛于方程 的根 ，假设迭代误差 当 时成立以下渐近关系式 )(1kkxx)(xx*x*xxekkk),0(1CCeepkk常数那么称该迭代过程是 阶收敛的. 特别地, 时称线性收敛， 时称超线性收敛， 时称平方收敛. p1p1p2p 定理4 对于迭代过程 ，假设 在所求根 的临近延续，并且 )(1kkxx)()(xp*x,0*)(,0*)(*)(*)()1( xxxxpp2.8那么该迭代过程在点 临近是 阶收敛的. *xp 证明 由于 ，据定理3立刻可以断定迭代过程 具有部分收敛性. 0*)( x

19、)(1kkxx 再将 在根 处做泰勒展开，利用条件2.8，那么有 )(kx*x.*,*)(!)(*)()()(之间与在xxxxpxxkpkpk留意到 ，由上式得 *)(,)(1xxxxkk,*)(!)(*)(1pkpkxxpxx因此对迭代误差，当 时有 k.!*)()(1pxeeppkk2.9这阐明迭代过程 确实为 阶收敛. 证毕. )(1kkxxp 上述定理阐明，迭代过程的收敛速度依赖于迭代函数 的选取. 假设当 时 ，那么该迭代过程只能够是线性收敛. )( x,bax 0)( x 在例4中，迭代法3的 ，故它只是线性收敛，而迭代法4的 ，而 由定理4知 ，即该迭代过程为2阶收敛. 0*)(

20、 x0*)( x,6)(3xx .032*)( x2p 7.3 7.3 迭代收敛的加速方法迭代收敛的加速方法 7.3.1 埃特金加速收敛方法 设 是根 的某个近似值，用迭代公式校正一次得 0 x*x)(01xx由微分中值定理，有 *),)(*)()(*001xxxxxx其中 介于 与 之间.0 x*x 假定 改动不大，近似地取某个近似值 ，那么有 )( xL*).(*01xxLxx3.1假设将校正值 再校正一次，又得 )(01xx),(12xx由于 *),(*12xxLxx将它与3.1式联立，消去未知的 ，有 L.*1021xxxxxxxx由此推知 .2)(2*01220100122120 x

21、xxxxxxxxxxxx在计算了 及 之后，可用上式右端作为 的新近似，记作 . 1x2x*x1x 普通情形是由 计算 ，记 kx21,kkxx)., 1 ,0(/)(2)(2212211kxxxxxxxxxxkkkkkkkkkk3.2(3.2)称为埃特金Aitken加速方法. 可以证明 .0*lim1xxxxkkk它阐明序列 的收敛速度比 的收敛速度快.kxkx 7.3.2 7.3.2 斯蒂芬森迭代法斯蒂芬森迭代法 埃特金方法不论原序列 是怎样产生的，对 进行加速计算，得到序列 . kxkxkx 假设把埃特金加速技巧与不动点迭代结合，那么可得到如下的迭代法： )., 1 ,0(2)(),()

22、,(21kxyzxyxxyzxykkkkkkkkKkk3.3称为斯蒂芬森(Steffensen)迭代法. 它的了解为，要求 的根 ，令 ， ，知 的近似值 及 ，其误差分别为 )(xx*xxxx)()(0*)(*)(xxx*xkxkyx 过 及 两点做线性插值函数，它与 轴交点就是3.3中的 ，即方程 )(,(kkxx)(,(kkyy1kx0)()()()(kkkkkkxxxyxyx的解 .2)()()()()(12kkkkkkkkkkkkkxxyzxyxxyxyxxx 实践上3.3是将不动点迭代法2.2计算两步合并成一步得到的，可将它写成另一种不动点迭代 ), 1 ,0()(1kxxkk3.4.)()(,)()(kkkkkkkkkkyzyyyxyxxx其中 .)(2)()()(2xxxxxxx3.5 定理5