数值分析第7章非线性方程与方程组的数值解法课件.ppt

1、第第7 7章章 非线性方程与方程组的数值解法非线性方程与方程组的数值解法7.1 方程求根与二分法 7.2 不动点迭代法及其收敛性 7.3 迭代收敛的加速方法 7.4 牛顿法 7.5 弦截法与抛物线法 7.6 求根问题的敏感性与多项式的零点7.7 非线性方程组的数值解法7.1 方程求根与二分法方程求根与二分法 7.1.1 引言引言0)(xf（1.1）本章主要讨论求解单变量非线性方程 其中 也可以是无穷区间.,)(,RbabaCxfx 如果实数 满足 ，则称 是方程(1.1)的根根，或称 是 的零点零点.*x)(xf0*)(xf*x*x若 可分解为)(xf),(*)()(xgxxxfm其中 为正整

2、数，且 则称 为方程(1.1)的 重根重根，或 为 的 重零点重零点，时为单根单根.m.0*)(xg1m*xm 若 是 的 重零点，且 充分光滑，则*x)(xfm)(xg,0*)(*)(*)()1(xfxfxfm.0*)()(xfm*x)(xfm 如果函数 是多项式函数，即),0()(01110aaxaxaxaxfnnnn（1.2）其中 为实数，则称方程(1.1)为 次代数方程次代数方程.),1,0(,00niaai)(xfn它在整个 轴上有无穷多个解，若 取值范围不同，解也不同，因此讨论非线性方程(1.1)的求解必须强调 的定义域，即 的求解区间5n 时的求根公式是熟知的，时的求根公式可在数

3、学手册中查到，但比较复杂不适合数值计算，当 时就不能用公式表示方程的根，所以 时求根仍用一般的数值方法2,1n4,3n 根据代数基本定理可知,次方程在复数域有且只有 个根（含重根，重根为 个根）.,010sine10/xxmmnn3nx 另一类是超越方程，例如xxx.,ba 迭代法要求先给出根 的一个近似，若 且 ，根据连续函数性质可知 在 内至少有一个实根，这时称 为方程(1.1)的有根区间.非线性问题一般不存在直接的求解公式，故没有直接方法求解，都要使用迭代法.*x,)(baCxf0)()(bfaf0)(xf),(ba,ba 通常可通过逐次搜索法求得方程 的有根区间.0)(xf 例例1 1

4、 求方程 的有根区间.解解 根据有根区间定义，对 的根进行搜索计算，结果如下：0)(xf077.418.381.11)(23xxxxf的符号)(6543210 1-7表xfx计算结果由此可知方程的有根区间为.6,5,4,3,2,1 检查 与 是否同号，如果同号，说明所求的根 在 的右侧,这时令否则 必在 的左侧，这时令见图7-1.*x0 x 考察有根区间 ，取中点 将它分为两半，,ba2/)(0bax 7.1.2 二分法二分法假设中点 不是 的零点，然后进行根的搜索.0 x)(xf)(0 xf)(af*x0 x,01xa;1bb,1aa.01xb 图7-1 不管出现哪一种情况，新的有根区间 的

5、长度仅为 的一半.,11ba,ba 对压缩了的有根区间 又可施行同样的手续，即用中点 将区间 再分为两半，然后通过根的搜索判定所求的根在 的哪一侧，从而又确定一个新的有根区间 ，其长度是 的一半.2/)(111bax,11ba,11ba1x,22ba,11ba 如此反复二分下去，即可得出一系列有根区间,2211kkbabababa其中每个区间都是前一个区间的一半，因此 的长度 ,kkbakkkabab2/)(当 时趋于零.k 就是说，如果二分过程无限地继续下去，这些区间最终必收缩于一点 ，该点显然就是所求的根.*x作为根的近似，则在二分过程中可以获得一个近似根的序列 ,210kxxxx该序列必

6、以根 为极限.*x 每次二分后，设取有根区间 的中点,kkba2/)(kkkbax 由于 2/)(*kkkabxx只要二分足够多次（即 充分大），便有 k,*kxx这里 为预定的精度.（1.3）,2/)(1kab 例例2 2 求方程 01)(3xxxf在区间 内的一个实根，要求准确到小数点后第2位.5.1,0.1 解解 这里 ，而5.1,0.1ba 取 的中点 ，将区间二等分，由于 ，即 与 同号，故所求的根 必在 右侧，这时应令 ，而得到新的有根区间,ba25.10 x0)(0 xf)(0 xf)(af*x0 x5.1,25.1101bbxa 如此反复二分下去,按误差估计（1.3）式,欲使0

7、)(,0)(bfaf.,11ba（1.3）,2/)(*1kkabxx只需 ，即只要二分6次，便能达到预定的精度.6k2/)(*kkkabxx12/)(kab,005.021211k 计算结果如表7-2.3242.13203.063203.13281.153281.13438.143438.13125.133125.1375.12375.125.1125.15.10.10符号)(27kkkkxfxbak表 二分法是计算机上的一种常用算法，计算步骤为：步骤步骤1 1 准备准备 计算 在有根区间 端点处的值)(xf).(),(bfaf,ba 步骤步骤2 2 二分二分 计算 在区间中点 处的值 )(x

8、f2ba).2(baf 步骤步骤3 3 判断判断 若 ，则 即是根，计算过程结束，否则检验.0)2(baf2ba 若 ，则以 代替 ，否则以0)()2(afbaf2ba b代替 .2ba a此时中点 即为所求近似根.2ba 误差 ，反复执行步骤2和步骤3，直到区间 长度小于允许,ba7.2 不动点迭代法及其收敛性不动点迭代法及其收敛性 7.2.1 不动点与不动点迭代法不动点与不动点迭代法 将方程（1.1）改写成等价的形式).(xx（2.1）若 满足 ，则 ；反之亦然，称为函数 的一个不动点不动点.*x0*)(xf*)(*xx*x)(x 求 的零点就等价于求 的不动点.)(xf)(x 选择一个初

9、始近似值 ，将它代入(2.1)右端，即可求得0 x).(01xx0)(xf（1.1）如此反复迭代计算).,1,0()(1kxxkk（2.2）称为迭代函数.)(x 如果对任何 ，由（2.2）得到的序列 有极限,0bax kx.*limxxkk则称迭代方程(2.2)收敛，且 为 的不动点，故称（2.2）为不动点迭代法不动点迭代法.*)(*xx)(x 方程 的求根问题在 平面上就是要确定曲线 与直线 的交点)(xxxy)(xyxy.*P 对于 的某个近似值 ，在曲线 上可确定一点 ，它以 为横坐标，而纵坐标则等于*x0 x)(xy0P0 x.)(10 xx 就是说，迭代过程实质上是一个逐步显示化的过

10、程.过 引平行 轴的直线，设此直线交直线 于点 ，0Pxxy 1Q然后过 再作平行于 轴的直线，1Qy与曲线 的交点)(xy 上述迭代法是一种逐次逼近法，其基本思想是将隐式方程 归结为一组显式的计算公式 .)(xx)(1kkxx则点 的横坐标为 ，1P1x图7-21P记作 ，.)(21xx纵坐标则等于 按图7-2中箭头所示的路径继续做下去.在曲线 上得到点列，)(xy21,PP其横坐标分别为 例例3 3 求方程 01)(3xxxf（2.3）在 附近的根 5.10 x.*x 解解 设将方程（2.3）改写成下列形式 .13xx依公式 求得的迭代值)(1kkxx.,21xx 如果点列 趋向于点 ，则

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

12、种不收敛的迭代过程称作是发散发散的.如图7-3.一个发散的迭代过程，纵使进行了千百次迭代，其结果也是毫无价值的.图7-3 7.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察 在 上不动点的存在唯一性.,ba)(x 定理定理1 1 设 满足以下两个条件：,)(baCx 1.对任意 有 ,bax bxa)(2.存在正常数 ，使对任意 都有 1L,bayx.)()(yxLyx（2.4）则 在 上存在唯一的不动点)(x,ba.*x 因 ，bxa)(以下设 及 ，aa)(bb)(若 或 ，则不动点为 或 ，aa)(bb)(ab存在性得证.定义函数.)()(xxxf显然 ，

13、,)(baCxf,0)()(aaaf由连续函数性质可知存在 ,),(*bax*),(*xx且满足,0)()(bbbf使 ,0*)(xf即即为 的不动点.)(x*x 证明证明 先证不动点存在性.再证唯一性.设 都是 的不动点，,21baxx)(x)()(2121xxxx引出矛盾.故 的不动点只能是唯一的.)(x则由(2.4)得.2121xxxxL.)()(yxLyx（2.4）.1*01xxLLxxkk（2.5）定理定理2 2 设 满足定理1中的两个条件，则对任意 ，由（2.2）得到的迭代序列 收敛到 的不动点 ，并有误差估计 ,)(baCx,0baxkx)(x*x 证明证明 设 是 在 上的唯一

14、不动点，由条件，可知 ，再由（2.4）得,ba,*bax)(x,baxk*)()(*1xxxxkk因 ，故当 时序列 收敛到 .10 Lkkx*x*1xxLk.*0 xxLk.)()(yxLyx（2.4）).,1,0()(1kxxkk（2.2）再证明估计式（2.5），)()(11kkkkxxxx由（2.4）有（2.6）.1kkxxL反复递推得.011xxLxxkkk于是对任意正整数 有pkkpkpkpkpkkpkxxxxxxxx12110121)(xxLLLkpkpk.101xxLLk.1*01xxLLxxkk（2.5）.)()(yxLyx（2.4）在上式令 ，注意到 即得式（2.5）.p*l

15、imxxpkp 迭代过程是个极限过程.在用迭代法实际计算时，必须按精度要求控制迭代次数.原则上可以用误差估计式（2.5）确定迭代次数，但由于它含有信息 而不便于实际应用.L 根据式（2.6），对任意正整数 有 pkkppkpkxxLLxx121)1(.111kkxxL在上式中令 知 p)()(11kkkkxxxx（2.6）.1kkxxL.1*01xxLLxxkk（2.5）.11*1kkkxxLxx 由此可见，只要相邻两次计算结果的偏差 kkxx1足够小即可保证近似值 具有足够精度.kx 对定理1和定理2中的条件2，如果且对任意 有,bax,1)(Lx（2.7）则由中值定理可知对 有,bayx)

16、()()(yxyx表明定理中的条件2可用（2.7）代替.,)(1baCx).,(,bayxL 例3中，当 时，,在区间 中，故（2.7）成立.31)(xx3/2)1(31)(xx2,114131)(3/1 x 又因 ，故定理1中条件1也成立.所以迭代法是收敛的.23)(2133x 而当 时，在区间 中 不满足定理条件.1)(3 xx23)(xx2,11)(x,1)(Lx（2.7）7.2.3 局部收敛性与收敛阶局部收敛性与收敛阶 上面给出了迭代序列 在区间 上的收敛性，kx,ba 定理的条件有时不易检验，实际应用时通常只在不动点 的邻近考察其收敛性，即局部收敛性.*x 定义定义1 1 设 有不动

17、点 ，如果存在 的某个邻域 对任意 ，迭代（2.2）产生的序列 且收敛到 ，则称迭代法（2.2）局部收敛局部收敛.)(x*x,*:xxRRx 0,Rxk通常称为全局收敛性.*x*x).,1,0()(1kxxkk（2.2）证明证明 由连续函数的性质，存在 的某个邻域 使对于任意 成立*x,*:xxRRx.1)(Lx 定理定理3 3 设 为 的不动点，在 的某个邻域连续，且 ，则迭代法（2.2）局部收敛.*x)(x)(x*x1*)(x此外，对于任意 ，Rx 总有 ，Rx)(*)()(*)(xxxx于是依据定理2可以断定迭代过程 对于任意初值 均收敛.)(1kkxxRx 0这是因为*xxL.*xx)

18、.,1,0()(1kxxkk（2.2）讨论迭代序列的收敛速度.例例4 4 用不同方法求方程 的根 032x.3*x 解解 这里 ，可改写为各种不同的等价形式 其不动点为 由此构造不同的迭代法：3)(2 xxf),(xx,3)1(21kkkxxx.3*x,12)(xx.1132)3(*)(x,3)(2xxx,3)2(1kkxx,3)(xx,3)(2xx.1*)(x),3(41)3(21kkkxxx),3(41)(2xxx),3(21)4(1kkkxxx取 ，对上述4种迭代法，计算三步所得的结果如下表.20 x,211)(xx.1134.0231*)(x),3(21)(xxx),31(21)(2x

19、x.0)3(*)(x732051.1732361.15.1873732143.173475.129275.175.15.13122220迭代法迭代法迭代法迭代法计算结果4表73210 xxxxxkk(4)(3)(2)(1)从计算结果看到迭代法（1）及（2）均不收敛，且它们均不满足定理3中的局部收敛条件.注意 .7320508.13 0*)(x 迭代法（3）和（4）均满足局部收敛条件，且迭代法（4）比（3）收敛快，因在迭代法（4）中 .定义定义2 2 设迭代过程 收敛于方程的根 ，如果迭代误差 当 时成立下列渐近关系式),0常数(1CCeepkk则称该迭代过程是 阶收敛阶收敛的.p 特别地,时称

20、线性收敛线性收敛，)1(1Cp)(1kkxx)(xx*x*xxekkk1p时称超线性收敛超线性收敛，2p时称平方收敛平方收敛.定理定理4 4 对于迭代过程 ，如果 在所求根 的邻近连续，并且 )(1kkxx)()(xp*x,0*)(*)(*)()1(xxxp则该迭代过程在点 邻近是 阶收敛的.*xp（2.8）,0*)(xp 证明证明 由于 ，据定理3立即可以断定迭代过程 具有局部收敛性.0*)(x)(1kkxx 再将 在根 处做泰勒展开，利用条件（2.8），)(kx*x.之 间*与在,*)(!)(*)()()(xxxxpxxkpkpk则有 注意到 ，*)(,)(1xxxxkk,*)(!)(*)

21、(1pkpkxxpxx因此对迭代误差，当 时有 k.!*)()(1pxeeppkk（2.9）这表明迭代过程 确实为 阶收敛.)(1kkxxp由上式得 上述定理说明，迭代过程的收敛速度依赖于迭代函数 的选取.)(x 如果当 时 ，则该迭代过程只可能是线性收敛.,bax 0)(x 在例4中，迭代法（3）的 ，故它只是线性收敛.0*)(x 而迭代法（4）的 ，而 由定理4知 ，该迭代过程为2阶收敛.0*)(x.032*)(x2p,6)(3xx 7.3 迭代收敛的加速方法迭代收敛的加速方法 7.3.1 埃特金加速收敛方法埃特金加速收敛方法 设 是根 的某个近似值，用迭代公式迭代一次得 0 x*x)(0

22、1xx由微分中值定理，有*)()(*01xxxx其中 介于 与 之间.0 x*x 假定 改变不大，近似地取某个近似值 ，)(xL*).(*01xxLxx（3.1）*),)(0 xx 则有),(12xx由于*),(*12xxLxx将它与（3.1）式联立，消去未知的 ，L.*1021xxxxxxxx由此推知 01221202*xxxxxxx 在计算了 及 之后，可用上式右端作为 的新近似，记作 .1x2x*x1x若将校正值 再迭代一次，又得)(01xx有.2)(0122010 xxxxxx*).(*01xxLxx（3.1）一般情形是由 计算 ，kx21,kkxxkkkkkkkxxxxxxx1221

23、12)(3.2)称为埃特金（Aitken）加速方法.可以证明.0*lim1xxxxkkk它表明序列 的收敛速度比 的收敛速度快.kxkx（3.2）).,1,0(/)(22kxxxkkk记 2 7.3.2 斯蒂芬森迭代法斯蒂芬森迭代法 埃特金方法不管原序列 是怎样产生的，对 进行加速计算，得到序列 .kxkxkx 如果把埃特金加速技巧与不动点迭代结合，则可得到如下的迭代法：),(kkxy称为斯蒂芬森(Steffensen)迭代法.),(kKyz（3.3）).,1,0(2)(21kxyzxyxxkkkkkkk 它的理解为，要求 的根 ，)(xx*x,)()(xxx,0*)(*)(xxx已知 的近似

24、值 及 ，其误差分别为*xkxky,)()(kkkkkxyxxx.)()(kkkkkyzyyy 过 及 两点做线性插值函数.)(,(kkxx)(,(kkyy它与 轴交点就是（3.3）中的 ，即方程 x1kx0)()()()(kkkkkkxxxyxyx的解 令（3.3）).,1,0(2)(21kxyzxyxxkkkkkkk),(kkxy),(kKyz)()()()(kkkkkkxyxyxxx 实际上（3.3）是将不动点迭代法（2.2）计算两步合并成一步得到的，可将它写成另一种不动点迭代),1,0()(1kxxkk（3.4）kkkkkkxyzxyx2)(2.1kx其中.)(2)()()(2xxxx

25、xxx（3.5）).,1,0()(1kxxkk（2.2）（3.3）).,1,0(2)(21kxyzxyxxkkkkkkk),(kkxy),(kKyz 定理定理5 5 若 为（3.5）定义的迭代函数 的不动点，则 为 的不动点.反之，若 为 的不动点，设 存在，则 是 的不动点，且斯蒂芬森迭代法（3.3）是2阶收敛的.*x)(x*x)(x*x)(x)(x 1*)(x*x)(x 解解 例3中已指出,下列迭代 131kkxx是发散的，现用(3.3)计算，取 .1)(3 xx 例例5 5 用斯蒂芬森迭代法求解方程 .01)(3xxxf计算结果如下表.)(2)()()(2xxxxxxx（3.5）（3.3

26、）).,1,0(2)(21kxyzxyxxkkkkkkk),(kkxy),(kKyz 至于原来已收敛的迭代法（2.2），由定理5可知它可达到2阶收敛.32474.1532714.132518.132480.1444435.134710.132895.1331728.249140.135565.1223888.584092.141629.113965.1237500.25.10计算结果5表7kkkzyxk 计算表明它是收敛的，这说明即使迭代法（2.2）不收敛，用斯蒂芬森迭代法（3.3）仍可能收敛.更进一步还可知若（2.2）为 阶收敛，则（3.3）为p1p阶收敛.例例6 6 求方程 在 中的解.0

27、e3)(2xxxf4,3 解解 由方程得等价形式 ，取对数得 23exx).(3lnln23ln2xxxx由此构造迭代法,3lnln21kkxx且当 时，4,3x4,3)(x由于 ,2)(xx 132)(max43xx根据定理2此迭代法是收敛的.).,1,0()(1kxxkk（2.2）（3.3）).,1,0(2)(21kxyzxyxxkkkkkkk),(kkxy),(kKyz 若取 迭代16次得 ，有六位有效数字.5.30 x73307.316x 若用（3.3）进行加速，计算结果如下：73307.3273347.373381.373444.3166202.360414.35.30kkkzyxk

28、 这里计算2步（相当于（2.2）迭代4步）结果与 相同，16x说明用迭代法（3.3）的收敛速度比迭代法（2.2）快得多.7.4 牛顿法牛顿法 7.4.1 牛顿法及其收敛性牛顿法及其收敛性 设已知方程 有近似根 （假定 )，kx0)(xf0)(kxf将函数 在点 展开，有)(xfkx),)()()(kkkxxxfxfxf于是方程 可近似地表示为 0)(xf.0)()(kkkxxxfxf（4.1）牛顿法是一种线性化方法，其基本思想是将非线性方程 逐步归结为某种线性方程来求解.0)(xf这是个线性方程，记其根为 ，1kx则 的计算公式为 1kx),1,0()()(1kxfxfxxkkkk（4.2）这

29、就是牛顿牛顿(Newton)法法.牛顿法的几何解释.方程 的根 可解释为0)(xf*x曲线 与 轴的交点的横坐标)(xfy x图7-4（图7-4).设 是根 的某个近似值，过曲线 上横坐标为 的点 引切线，并将该切线与 轴的交点的横坐标 作为 的新的近似值.kx*x)(xfy kxkPx1kx*x 注意到切线方程为).)()(kkkxxxfxfy这样求得的值 必满足（4.1），从而就是牛顿公式（4.2）的计算结果.1kx 由于这种几何背景，牛顿法亦称切线法切线法.由定理4，可以直接得到牛顿法的收敛性，),1,0()()(1kxfxfxxkkkk（4.2）.0)()(kkkxxxfxf（4.1）

30、,)()()(xfxfxx由于.)()()()(2xfxfxfx 假定 是 的一个单根，即 ，则由上式知 于是依据定理4可以断定，牛顿法在根 的邻近是平方收敛的.)(xf*x0*)(,0*)(xfxf0*)(x(4.2)的迭代函数为*x 又因,*)(*)(*)(xfxfx ),1,0()()(1kxfxfxxkkkk（4.2）故由（2.9）可得.*)(2*)(*)(*lim21xfxfxxxxkkk（4.3）例例7 7 用牛顿法解方程 .01exx（4.4）解解 这里牛顿公式为 ,1e1kxkkkxxxxk取迭代初值 ，迭代结果列于表7-6中.5.00 x 所给方程（4.4）实际上是方程 的等

31、价形式.xx e.!*)()(1pxeeppkk（2.9）56714.0356716.0257102.015.00计算结果7表7kxk 牛顿法的计算步骤：步骤步骤1 1 准备准备 选定初始近似值 ，计算 0 x).(00 xff 步骤步骤2 2 迭代迭代 按公式 0001/ffxx迭代一次，得新的近似值 ，1x).(),(1111xffxff 若用不动点迭代到同一精度 可见牛顿法的收敛速度是很快的.要迭代17次.),(00 xff计算 1x 此处 是允许误差，而 21,，；时当时当1101101CxxxxCxxx其中 是取绝对误差或相对误差的控制常数，C1C 步骤步骤4 4 修改修改 如果迭代

32、次数达到预先指定的次数 ，N 步骤步骤3 3 控制控制 如果 满足 或 ，则终止迭代，以 作为所求的根；否则转步骤4.1x121f一般可取或者 ，则方法失败；01f 否则以 代替 转步骤2继续迭代.),(111ffx),(000ffx 7.4.2 牛顿法应用举例牛顿法应用举例 对于给定的正数 ，应用牛顿法解二次方程 C,02 Cx可导出求开方值 的计算程序 C).(211kkkxCxx（4.5）这种迭代公式对于任意初值 都是收敛的.00 x 事实上，对（4.5）式施行配方手续，易知;)(2121CxxCxkkk以上两式相除得.211CxCxCxCxkkkk据此反复递推有.20011kCxCxC

33、xCxkk（4.6）记,00CxCxq.)(2121CxxCxkkk 解解 取初值 ，对 按(4.5)式迭代3次便得到精度为 的结果（见表7-8).1222kkqqCCxk 对任意 ，总有 ，故由上式推知，当时 ，即迭代过程恒收敛.00 x1qCxk723805.104723805.103723837.102750000.101100计算结果87表kxk100 x115C610 例例8 8 求 .115整理（4.6）式，得 k.20011kCxCxCxCxkk（4.6）).(211kkkxCxx（4.5）由于公式（4.5）对任意初值 均收敛，并且收敛的速度很快，因此可取确定的初值如 编成通用程

34、序.00 x10 x).(211kkkxCxx（4.5）7.4.3 简化牛顿法与牛顿下山法简化牛顿法与牛顿下山法 牛顿法的优点是收敛快，缺点一是每步迭代要计算 及 ，计算量较大且有时 计算较困难，)(kxf)(kxf)(kxf 为克服这两个缺点，通常可用下述方法.（1 1）简化牛顿法，简化牛顿法，也称平行弦法.其迭代公式为 .,1,00)(1kCxCfxxkkk（4.7）迭代函数).()(xCfxx 二是初始近似 只在根 附近才能保证收敛，如0 x*x0 x给的不合适可能不收敛.若在根 附近成立 ，即取*x1)(1)(xfCx,2)(0 xfC则迭代法（4.7）局部收敛.在（4.7）中取 ，则

35、称为简化牛顿法简化牛顿法，)(10 xfC这类方法计算量省，但只有线性收敛，其几何意义是用平行弦与 轴交点作为 的近似.x*x 如图7-5所示.图7-5即)()(01xfxfxxkkk （2 2）牛顿下山法牛顿下山法.牛顿法收敛性依赖初值 的选取.0 x 如果 偏离所求根 较远，则牛顿法可能发散.0 x*x 例如，用牛顿法求方程.013 xx（4.8）在 附近的一个根 .5.1x*x 设取迭代初值 ，用牛顿法公式 5.10 x131231kkkkkxxxxx（4.9）计算得.32472.1,32520.1,34783.1321xxx迭代3次得到的结果 有6位有效数字.3x 但如果改用 作为迭代

36、初值，则依牛顿法公式（4.9）迭代一次得 6.00 x.9.171x这个结果反而比 更偏离了所求的根 .6.00 x32472.0*x 为了防止迭代发散，对迭代过程再附加一项要求，即具有单调性：.)()(1kkxfxf（4.10）满足这项要求的算法称下山法下山法.131231kkkkkxxxxx（4.9）将牛顿法与下山法结合起来使用，即在下山法保证函数值稳定下降的前提下，用牛顿法加快收敛速度.将牛顿法的计算结果)()(1kkkkxfxfxx与前一步的近似值 适当加权平均作为新的改进值 kx,)1(11kkkxxx（4.11）其中 称为下山因子，)0(),1,0()()(1kxfxfxxkkkk

37、（4.12）(4.12)称为牛顿下山法牛顿下山法.（4.11）即为 选择下山因子时从 开始，逐次将 减半进行试算，1 若用此法解方程（4.8），当 时由（4.9）求得6.00 x直到能使下降条件（4.10）成立为止.，它不满足条件（4.10）.9.171x 通过 逐次取半进行试算，当 时可求得32/1,140625.11x此时有 ，656643.0)(1xf显然 .)()(01xfxf384.1)(0 xf而 由 计算 时 ,均能使条件（4.10）成立.计算结果如下：1x,32xx1.)()(1kkxfxf（4.10）131231kkkkkxxxxx（4.9）.013 xx（4.8）;1866

38、.0)(,36181.122xfx 即为 的近似.一般情况只要能使条件（4.10）成立，则可得到 ，从而使 收敛.4x*x0)(limkkxfkx;00667.0)(,32628.133xfx.0000086.0)(,32472.144xfx.)()(1kkxfxf（4.10）7.4.4 重根情形重根情形 设 ，整数 ，则 为方程 的 重根，此时有 )(*)()(xgxxxfm0*)(,2xgm*x0)(xfm.0*)(,0*)(*)(*)()1(xfxfxfxfmm只要 仍可用牛顿法（4.2）计算，此时迭代函数 0)(kxf)()()(xfxfxx的导数为 011*)(mx且 ，所以牛顿法求

39、重根只是线性收敛.1*)(x),1,0()()(1kxfxfxxkkkk（4.2）,)()()(xfxfmxx则 .0*)(x),1,0()()(1kxfxfmxxkkkk（4.13）求 重根，则具有2阶收敛，但要知道 的重数 .mm*x 构造求重根的迭代法，还可令 ，)(/)()(xfxfx若 是 的 重根，则*x0)(xfm,)(*)()()(*)()(xgxxxmgxgxxx若取 用迭代法)()()(xxxx从而可构造迭代法),1,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk（4.14）它是二阶收敛的.故 是 的单根.*x0)(x对它用牛顿法，其迭代函数为.)(

40、)()()()(2xfxfxfxfxfx 例例9 9 方程 的根 是二重根，用上述三种方法求根.04424xx2*x 解解 （1）牛顿法.42844423241kkkkkkkkkxxxxxxxxx先求出三种方法的迭代公式：（2）用（4.13）式.22,221kkkkxxxxm （3）用（4.14）式.2)2(221kkkkkxxxxx取初值 ，计算结果如表7-9.5.10 x),1,0()()(1kxfxfmxxkkkk（4.13）),1,0()()()()()(21 kxfxfxfxfxfxxkkkkkkk,44)(24xxxf414213562.1414213562.1425497619.

41、13414211438.1414215686.1436607143.12411764706.1416666667.1458333333.11)3()2()1(9321xxxxkk方法方法方法三种方法数值结果表7 从结果看出，经过三步计算，方法（2）及（3）均达到10位有效数字，而由于牛顿法只有线性收敛，所以要达到同样精度需迭代30次.7.5 弦截法与抛物线法弦截法与抛物线法 当函数 比较复杂时，计算 往往较困难，)(xf)(xf 值 的计算.)(kxf 为此可以利用已求函数值 来回避导数),(),(1kkxfxf还要算 .)(kxf 用牛顿法求方程 的根，每步除计算 外，)(kxf0)(xf

42、7.5.1 弦截法弦截法 设 是 的近似根，1,kkxx0)(xf利用 )(),(1kkxfxf构造一次插值多项式 ，并用 的根作为新的近似根 .)(1xp0)(1xp1kx).()()()(111kkkkkkxxxxxfxfxfxp（5.1）由于 因此有).()()()(111kkkkkkkxxxfxfxfxx（5.2）（5.2）可以看做将牛顿公式)()(1kkkkxfxfxx中的导数 用差商 取代的结果.)(kxf 11)(kkkkxxxfxf 接着讨论几何意义.曲线 上横坐标为 的点分别记为 ，)(xfy 1,kkxx1,kkPP则弦线 的斜率等于差商值 ,1kkPP11)(kkkkxx

43、xfxf).()()()(111kkkkkkkxxxfxfxfxx（5.2）).()()(11kkkkkkxxxxxfxfxfy按（5.2)式求得的 实际上是弦线 与 轴交点的横坐标.1kx1kkPPx表7-6这种算法因此而称为弦截法弦截法.其方程为).()()()(111kkkkkkkxxxfxfxfxx（5.2）而弦截法（5.2），在求 时要用到前面两步的结果 ，1kx1,kkxx 弦截法与切线法（牛顿法）都是线性化方法，但两者有本质的区别.切线法在计算 时只用到前一步的值 .kx1kx因此使用这种方法必须先给出两个开始值 .01,xx 例例10 10 用弦截法解方程 .01e)(xxxf

44、 解解 设取 作为开始值，用弦截法求得的结果见表7-10，56714.0456709.0356532.026.015.00计算结果107表kxk6.0,5.010 xx).()()()(111kkkkkkkxxxfxfxfxx（5.2）实际上，弦截法具有超线性的收敛性.比较例7牛顿法的计算结果可以看出，弦截法的收敛速度也是相当快的.定理定理6 6 假设 在根 的邻域 内具有二阶连续导数，且对任意 有 ，又初值 那么当邻域充分小时，弦截法（5.2）将按 阶收敛到根 .这里 是方程 的正根.618.1251p012)(xf*x*:xxx0)(xf,10 xx*xp).()()()(111kkkkk

45、kkxxxfxfxfxx（5.2）7.5.2 抛物线法抛物线法 设已知方程 的三个近似根 ，21,kkkxxx0)(xf 几何上，这种方法的基本思想是用抛物线与 轴的交点 作为所求根 的近似位置（图7-7).1kxx*x图7-7以这三点为节点构造二次插值多项式 ，)(2xp 的一个零点 作为新的近似根，)(2xp1kx并适当选取 这样确定的迭代过程称为抛抛物线法物线法，亦称密勒（密勒（Mller）法）法.插值多项式).)(,)(,)()(12112kkkkkkkkkxxxxxxxfxxxxfxfxp有两个零点：,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）式中).(,121

46、1kkkkkkkxxxxxfxxf 问题是该如何确定 .1kx 假定在 三个近似根中，更接近所求的根 .21,kkkxxxkx*x 为了保证精度，选（5.3）中较接近 的一个值作为新的近似根 .kx1kx 为此，只要取根式前的符号与 的符号相同.例例11 11 用抛物线法求解方程 .01e)(xxxf 解解 设用表7-10的前三个值 56532.0,6.0,5.0210 xxx作为开始值，计算得,093271.0)(,175639.0)(10 xfxf,005031.0)(2xf,68910.2,01xxf,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）56714.04567

47、09.0356532.026.015.00计算结果107表kxk故.75694.2)(,1201212xxxxxfxxf代入（5.3）式求得.56714.0,)(4)(201222223xxxfxfxfxx,83373.2,12xxf.21418.2,012xxxf 以上计算表明，抛物线法比弦截法收敛得更快.在一定条件下可以证明，对于抛物线法，迭代误差有下列渐近关系式.*)(6*)(42.01840.1xfxfeekk ,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）可见抛物线法也是超线性收敛的，其收敛的阶 ,840.1p 从（5.3）看到，即使 均为实数，也可以是复数，所以

48、抛物线法适用于求多项式的实根和复根.21,kkkxxx1kx收敛速度比弦截法更接近于牛顿法.,)(4)(22121kkkkkkkxxxfxfxfxx（5.3）7.6 求根问题的敏感性与多项式的零点求根问题的敏感性与多项式的零点 7.6.1 求根问题的敏感性与病态代数方程求根问题的敏感性与病态代数方程 方程求根的敏感性与函数求值是相反的，若 ，则由 求 的病态性与由 求 的病态性相反，光滑函数 在根 附近函数绝对误差与自变量误差之比若 ，则求根为反问题，即输入 满足若找到一个 使 ,则解的误差 与 之比为 ，即 误差将达到 ，如果 非常小，这个值就非常大，直观的可用图7-8表示.yxf)(yxx

49、yf*x,*)(xfxy0*)(xf*x,0*)(xfyx)(xf*xxx*)()(xfxfy*)(1xfyxx*)(xf*)(xf 图7-8 对多项式方程若系数有微小扰动其根变化很大，这种根对系数变化的敏感性成为病态的代数方程.若多项式 的系数有微小变化，可表示为其中 是一个多项式，次数不大于 的零点表示为 ，令 为 的零点，即 ，将（6.2）对 求导，可得,0,0)(01110aaxaxaxaxpnnnn（6.1）)(xp,0)()()(xqxpxp（6.2）0)(xq)(.xpn)(,),(),(21nxxx)0(,),0(),0(21nxxx)(xp),2,1)(0(nixxii于是当

50、 时有当 充分小时，利用 在 处的泰勒展开得它表明系数有微小变化 时引起根变化的情况.当 很大时代数方程（6.1）就是病态的.,0dd)()(dd)(xxqxqxxp.)()()(ddxqxpxqx0.)0()0(d)0(dxpxqx)(kx0,2,1,)()()(nkxpxqxxkkkkiixx)(（6.3）（6.4）例例1212 多项式 解解 取 的根由（6.4）可得56732228)7()2)(1()(xxxxxxxp.5040130681313267691960234xxxx)(,002.0,)(6xpxxq).7,2,1(kkxk,)(,)()(6kxqjkxpkkjk.)!7()!