第4章 非线性方程迭代解法

1、1非线性方程的数值解法非线性方程的数值解法 1 引言引言 2 二分法二分法 3 迭代法迭代法 4 牛顿法牛顿法2引引 言言 代数方程求根问题是一个古老的数学问题，早在16世纪就找到了三次、四次方程的求根公式。但直到19世纪才证明 次的一般代数方程式不能用代数公式求解。因此需要研究用数值方法求得满足一定精度的代数方程式的近似解。 在工程和科学技术中许多问题常常归结为求解非线性方程式问题，例如在控制系统的设计领域，研究人口增长率等。 例例1 关于真实气体的状态方程（Van der waals方程）为 其中，P是气体压力，V是气体体积，T是绝对温度，R是气体常数。 如果已知某气体的温度T及压力P，那

2、么求体积V的方程为： 5nRTbVVaP)(20)()(2RTbVVaPxf(1.1)(1.2)3或 本章将介绍这种类型方程的近似解的数值方法。 设有一非线性方程其中 为实变量 的非线性函数。定义定义 1 （1 1）如果有 使 ，则称 为方程（1.31.3）的根，或 称为函数 的零点零点。 （2 2）当 为多项式时，即方程为 称 为 n 次代数方程代数方程。当 包含指数函数或三 角函数等特殊函数时，称 为超越方程超越方程。 （3 3）如果 ，其中 ，m 为正整 数，则称 为 的 m 重根。重根。当 m=1时称 为 的单根单根。)(2VgbVaPRTV0)(xf)(xfx*x0)(*xf*x)(

3、xf)(xf)0(0)(011nnnnnaaxaxaxf0)(xf)(xf0)(xf)()()(*xgxxxfm0)(*xg*x0)(xf(1.3)(1.3)*x0)(xf4先叙述两个基本定理。定理定理 1 1 （代数基本定理）代数基本定理） 设 为具有复系数的 n 次代数方程，则 于复数域上恰有 n 个根（r 重根计算 r 个）。如果 为实系数代数方程，则复数根成对出现，即当 是 的复根，则 亦是 的根。定理定理2 2 （1 1）设 于 上连续： （2 2）且 ，则存在有 使 即 于 内存在实的零点。 设有非线性，实系数方程问题是：需要求出方程的所有实根（或复根）。),(*bax 0)(xf

4、0)(xf0)(xf)0(i0)(xfi0)(xf)(xf,ba0)()(bfaf0*)(xf)(xf),(ba0)(xf5 2 二二 分分 法法 设有非线性方程 其中， 为 上连续函数且设 （不妨设方程（2.12.1）于 内仅有一个实根。 求方程（2.12.1）实根 的二分法过程，就是将含根区间 逐步分半，检查函数符号的变化，以便确定含根的充分小区间。 0)(xf)(xfba,0)()(bfafba,*xba,0yx)(xfy 1a1x2x*x1b2a2b图图 5-2（2.12.1）6二分法二分法叙述如下；记 （图（图5-2）第一步分半计算（第一步分半计算（k=1k=1）: 将 分半，计算中

5、点 及 ，如果 则根一定在区间 内，否则根一定在区间 内（若 ，则 ）。于是得到长度缩小一半的含根区间 ，即第第k步分半计算：步分半计算：重复上述过程，设已完成第1步， ，第k-1步分半计算得到含根区间且满足；（1） 即 ； （2） ；现在进行第k步分半计算； （3）计算 且有 bbaa11,11,ba2/ )(111bax)(1xf0)()(11xfaf2, 211,baxa2, 211,babx0)(1xf*1xx 2, 2ba)(21, 0)()(112222ababbfaf且kkbababa,2211, 0)()(kkbfafkkbax,*)(211ababkkk2/ )(kkkbax

6、7)(212*ababxxkkkk（2.2)2.2) （4）确定新的含根区间 ，即如果 ，则根一定在 内，否则根一定在区间 且有总之，由上述二分法得到一序列 ，由（2.2），则有 可用二分法求方程 实根 的近似值到任意指定的精度。事实上，设 为给定精度要求，试确定分半次数 k使由 两边取对数，即得 kx*limxxkk1,kknba0)()(kkxfaf kkkkxaba,11 kkkkbxba,11)(2111ababkkkkkabxx2*00)(xf*x)/(2abk8例例3 用二分法求 于 内一个实根，且要求精度到 小数后第3位（即要求 ）。显然 ， 。 解解 由 ，由公式（2. 3）可

7、确定所需分半次数 。计 算结果如下表(表表 5-1)。2ln/ )ln)(ln(eabk（2.32.3）01)(6xxxf2 , 1321*10kxx0)2() 1 ( ff3105 . 011k911.02.01.58.89062521.01.51.251.56469731.01.251.125-0.09771341.1251.251.18750.61665351.1251.18751.156250.23326961.1251.156251.1406250.061577871.1251.1406251.132813-0.019575681.1328131.1406251.1367190.02

8、0619091.1328131.1367191.134766101.1328131.1347661.133789-0.00959799111.1337891.1347661.34277-0.0045915410307. 4kakbkx)(kxfk表表 5-110 二分法优点是简单，且对 只要求连续即可。可用二分法求出 于 内全部实根。但二分法不能求复数及偶数重根。 二分法框图二分法框图（图图5-35-3）：二分法：二分法： 设有方程 ，其中 于 连续，且满足条件 （且设于 内只有一个实根）。 （1）计算 （2）如果 或 则输出 （3）如果 则 否则 其中 表示给定的最大分半次数，当 或 时分半

9、终止， 为一大数。0)()(kkxfaf)(xf0)(xfba,0)(xf)(xfba,0)()(bfafba,0, 2 , 1Nk; 2/ )(),(, 2/ )(0kkkkkabhxfbax1)(kxf2h;),(,kxfxkkkkkkxbaa11,kkkkbbxa11,0N1)(xf2hmaxf11 3 迭迭 代代 法法 迭代法是一种逐次逼近法。它是求解代数方法，超越方程及方程组的一种基本方法，但存在收敛性及收敛快慢问题。 为了用迭代法求非线性方程 的近似值，首先需要将此方程转化为等价的方程 显然，将 转化为等价方程（3.13.1）的方法是很多的。例例4 方程 可用不同方法转化为等价方程

10、 （a） （b）定义定义2 （迭代法）（迭代法）设方程为 （1） 选取方程的一个初始近似 ，且按下述逐次代入法， 构造一近似解序列； 0)(xf)(xgx 0)(xf05 . 0sin)(xxxf)()5 . 0(sin)(5 . 0sin211xgxxxgxx)(xgx 0 x（3.13.1）12)()()(11201kkxgxxgxxgx(3.2)这种方法称为迭代法迭代法（或称为单点迭代法单点迭代法）。 称为迭代函数迭代函数。 （2） 如果由迭代法产生的序列 有极限存在，即 ， 则称 为收敛收敛或称迭代过程（3.2）收敛）收敛。否则称 不不 收敛收敛。 设 为连续函数，且有 ，则有 即 为

11、方程（3.1）的解解（称 为函数的不动点不动点）。 事实上，由迭代过程（3.2）两边取极限，则有)(xg kx*limxxkk kx kx)(xg*limxxkk)(*xgx *x*x)()lim()(limlim*1*xgxgxgxxkkkkkk13显然在由方程 转化为等价的方程 时，选择不同的迭代函数 就会产生不同的序列 （即使初始值 选择一样），且这些序列的收敛情况也不会相同。例例 5 对例4中方程，考查用迭代法求根 （a） （b）)(xg kx0 x0)(xf)(xgx ), 1 , 0(),5 . 0(sin), 1 , 0( , 5 . 0sin111kxxkxxkkkkk01.0

12、1.011.3414710.52359921.4738200.02360131.495301-0.49655541.497152-1.48776151.49728561.49730071.497300 - 3.6710kxa)(kxb)()()(kxfa表表 5-214 由计算看出，选取的两个迭代函数 分别构造序列 收敛情况不一样（初始值都为1.0)，在(a)(a)种情况 收敛且。在(b)(b)种情况出现计算 无定义。因此，对于用迭代法求方程 近似根需要研究下述问题： （1 1）如何选取迭代函数 使迭代过程 收敛。 （2 2）若 收敛较慢时，怎样加速 收敛。迭代法的几何意义：迭代法的几何意义：

13、 从几何上解释，求方程 根的问题，是求曲线 与直线 交点的横坐标 。当迭代函数 的导数 在根 处满足下述几种条件时，从几何上来考查迭代过程 的收敛情况如图图5-45-4。 从曲线 上一点 出发，沿着平行于 x 轴方*x)(),(21xgxg kx kx497300. 1*x)987761. 1arcsin()5 . 0arcsin(4x0)(xf)(xg)(1kkxgx kx kx)(xgx )(xgy xy *x)(xg)(xg)(1kkxgx)(xgx )(,(000 xgxP15)(xgy xy yx00 x1x2x*x(1) 1)(0*xg)(xgy xy yx0(2) 0)(1*xg

14、0 x1x2x*x3xxxyy00(3) (4) 1)(*xg1)(1)(*xgxxg*x*x0 x0 x2x2x1x1x3x)(xgy )(xgy xy xy 0P0P0P0P图图 5-416方向前进交 于一点 ，再从 点沿平行于 y 轴方向前进交 于 点，显然， 的横坐标就是 。继续这过程就得到序列 ，且从几何上观察知在（1）（）（2）情况下 收敛于 ，在（3）（）（4）情况不收敛于 。 由迭代法的几何意义可知，为了保证迭代过程收敛，应该要求迭代函数的导数满足条件 ，当 ，否则方程于 可能有几个根或迭代法不收敛，为此有下述关于迭代法收敛定理。定理定理3 设有方程 （1） 设 于 一阶导数存

15、在； （2） 当 时有 ； （3） 满足条件： 。则 （a） 在 上有唯一解 ； （b） 对任意选取初始值 ，迭代过程 收 敛 ，即 ；1P)(01xgx kx kx*x*x 1xgbax,ba,)(xgx )(xgba,bax,baxg,)()( xg baxLxg, 1当)(xgx ba,*xbax,0)(1kkxgx*limxkxk0Q0Q)(xgy xy 1P17(c);111*kkkxxLxx), 2 , 1(101*kxxLLxxkk 证明证明 只证明(b)，(c)，(d)（见图图5-5）。 证证 (b) 由定理假设条件假设条件(2), 当取 时，则有 。 记误差 ，由中值公式有图

16、图 5-5(d) 误差估计xy )(xgy yx0ba*xab(3.3)(3.4)bax,0baxk,)2 , 1(kkkxxe*182*21*kkkxxLxxLxx)(00*kxxLk当 kkkxxLxxcgxx*1*)2 , 1 , 0(k )(*1*kkkxxcgxgxgxx)(1kkxgx 111kkkkkkxxcgxgxgxxbac,kx*x其中c在 与 之间，即 。 又利用假设条件（3）得到误差的递推关系 (3.5)反复利用(3.5)，得到即证证 (c) 取迭代公式 ，显然有*limxxkk19), 2 , 1( ,1kxxLkk其中 c 在 与 之间，于是即 证证(d) 反复利用

17、(3.6)，可得1*1kkkkxxxxxx1kxkx1*kkxxxxkkkxxLxxLxx*)1 (*11111*kkkkkxxLLxxLxxkkkxxLxx1*11011xxLLK(3.6)20由定理定理3结果结果(3.3)可知，当计算得到的相邻两次迭代满足条件 (3.7)时，则误差所以在电算时可利用 来控制迭代中止，但是要注意，当 时，即使 很小，但误差 还可能较大。当已知 及给定精度要求 时，利用(3.4)可确定使误差达到给定精度要求所需要迭代次数 k 。 事实上，由则 (3.8)kkxx1Lxxk11*kkxx11Lkkxx1kxx *) 1(,10Lxx01*1xxLLxxkkLLx

18、xkln/1lnln0121 定理定理3中的假设条件 。在一般情况下，可能对于大范围的含根区间不满足，而在根的邻近是进成立的，为此有下述迭代过程局部收敛性结果 。定理定理4 （由迭代法局部收敛性局部收敛性）设给定方程 (1) 设 为方 程的解； (2) 设 在 的邻近连续可微且有 （根据 在 邻近连续性，此条件即为存在 的一个邻域 则对任意取初值 ， 迭代过程 收 敛于 （称迭代过程具有局部收敛性局部收敛性）。证明证明 取 ，于是只要验证定理定理3中条件（中条件（2）成立 ，定理4即得证。 事实上，设 ，则 baxLxg, 1当)(xgx *x)(xg*x 1*xg xg*x*x , 1|*L

19、xgxxxS使).时成立当SxSx 0), 2 , 1 , 0)(1kxgxkk*x,*xxbaSx)(xgx *xxcgxgxgxx*xxxxL22其中， 。说明 。例例6 试用迭代法解方程：解解 （1）显然有（见图图5-6） 即知，方程于0，2及-1.9，-1内有根，记为 及 （参 看图图5-6）。 （2）考查取初值 迭代过程 的收敛性 ，其中迭代函数为 。 显然， 及 为增 函数，则有当 。又由ScSx 0)2ln()(xxxf0) 1()9 . 1(0)2()0(ffff*1x*2x2 , 00 x)2ln(1kkxx 2ln1xxg 2386. 14ln2, 06931. 02ln)

20、0(11gg xg1 20201xgx时， 211xxg23*2x*1x210yx12xy )2ln( xy图图 5-624则有于是，由定理定理3可知，当初值 时迭代过程 收敛。如果要求 近似根准确到小数后第6位（即要求 ）。 由表5-3可知所以 2 , 0, 12102111xgxxg当2 , 00 x)2ln(1kkxx*1x621*110kxx21,10|71415Lxx且67141514*1105 . 010211xxLxx714*1108 . 0461931. 1xfx2500.010.6931471820.99071046141.1461931151.1461932表 5-3) 2

21、ln(1kkxxk26（3）为了求 内 方 程 的根，考察迭代过程显然所以，迭代过程（3.9）（初值 ） 不收敛于 。（4）可将方程转化等价方程 且有 所以，当选取 时迭代方程收敛。如取 ，则迭代12次有1, 9 . 1)2ln(1kkxx 1, 9 . 1, 11211xgxxg当*200,1, 9 . 1xxx*2x xgexxexx22, 2或 1, 9 . 1, 1368. 0122xgxg当1, 9 . 10 x), 1 , 0(21kexkxk10 x841405660. 112*2 xx（3.9） xexg227且有 由上例可见，对于方程 ，迭代函数 选取不同，相应由迭代法产生的

22、 收敛情况也不一样。因此，我们应该选取迭代函数，使构造的迭代过程 收敛且收敛较快。迭代法：迭代法：求解方程 （1） 选取解的初始估计 ； （2） 对于 计算 ，其中 为给定的最大迭代次数。当 时（或 或 ，其中 为给定精度要求）迭代终止。812102 . 0)(xf0)(xf)(xg kx)(1kkxgx )(xgx 1x0, 2 , 1Nk)(1kkxgx0Nkkxx1kkkxxx1)(kxf28 4 牛顿牛顿-雷扶生方法雷扶生方法解非线性方程 的牛顿方法是一种将非线性函数线性化的方法。 牛顿方法的最大优点是在方程单根附近具有较高的收敛速度。牛顿方法可用来计算 的实根，还可计算代数方程的复根

23、。 4.1 牛顿法公式及误差分析牛顿法公式及误差分析设有非线性方程其中，设 为 上一阶连续可微，且 又设 是 的 一个零点 的近似值(设 ，现考虑用过曲线 上点 的切线近似代替函数 ，即用线性函数（图图5-8）代替 。且用切线（即线性函数）的零点，记为 ，作为方程（4.1）的根 的近似值，即求解ba,0 x0)(0 xf000 xxxfxfy0)(xf0)(xf0)(xf)(xf; 0)()(bfaf)(xf),(*bax )(xfy )(,(00 xfxP)(xf0)()(000 xxxfxf1x*x(4.1)(xf29)()(0001xfxfxx得到一般，若已求得 ，将（4.2）中 换为

24、，重复上述过程，即求得方程 根的牛顿方法的计算公式 0 xkx), 2 , 1 , 0)()(10kxfxfxxxkkkk（初值）kx0)(xf)(xfy *x0 x1x2xyx0图图 5-8(4.2)(4.3)30 下面利用 的泰勒公式进行误差分析。设已知 根 的第 k 次近似 ，于是 在 点泰勒公式为（设 二次连续可微）：其中c在 与 之间。 如果用线性函数 近似代替 ，其误差为 。且用 根记为 作为 的根 的近似值又得到牛顿公式现在（4.4）中取 ，则有 于是)(xf0)(xf*xkx)(xfkx)(xf2 )(! 2)()()()(kkkkxxcfxxxfxfxf)()(1kkxfxf

25、kkxx*x)()()(kkkxxxfxfxP)(xf0)(xP0)(xf*xx 2*)*(! 2)()*)()()(0kkkkxxcfxxxfxfxf 2*)()(2)()()(kkkkkxxxfcfxfxfxx (4.4)kxx2 )(! 2)(kxxcf1kx31（设 ）。利用牛顿公式(4.3) 即得误差关系式误差公式（4.5）说明 的误差是与 误差的平方成比例的。当初始误差（即 ）是充分小时，以后迭代的误差将非常快的减少。由计算公式（4.3）可知，用牛顿法求方程 根，每计算一步需要计算一次函数值 以及一次导数 。例例7 用牛顿法求 根。解解 显然, 方程于 内有一根.求导 牛顿法计算公

26、式为 0)(kxf2*1*)()(2)(kkkxxxfcfxx (4.5)1kxkx00* xx0)(xf)(kxf)(kxf01)2()(4/xexfx, 0)2()0( ff2 , 0), 2 , 1 , 0( ,4/ )6(1)2(4/4/1kxexexxkxkxkkkk4/ )6()( 4/xexfx3201.01-1.15599920.18943830.71404340.78254250.78359560.78359608.0134.7781072869.15193发散kxkxkk表表 5-4 (1) 取取 0 . 10 x表表 5-5 (2) 取取 0 . 80 x求得近似值 说明

27、当初值 选取靠近根 时牛顿法收敛且收敛较快，当初 值不是选取接近方程根时，牛顿法可能会给出发散的结果。86*108 . 3)(,783596. 0 xfx0 x*x0 x33)(1kkxgx)()()(xfxfxxg0)( xf 4.2 牛顿法的局部收敛性牛顿法的局部收敛性 设有方程 ，显然，牛顿法是一种迭代法，即 其中迭代函数为 （设 )于是，可用迭代法理论来考查牛顿方法的收敛性。定理定理 5 （牛顿法局部收敛性）设有方程 （1）设 在根 邻近具有连续二阶导数； （2） 且设 ，但 ，则存在 的一个邻域 使得对于任意选取初值 ，由牛顿法产生的序列 收敛于 且有 0)(xf0)(xf)(xf*

28、x0)(*xf0)(*xf*xxxxS*Sx 0 kx*x)(2)()(*2*1*limxfxfxxxxkkk （4.6）(4.7)34 证明证明 由于牛顿法是一个迭代法，其迭代函数为计算由假设条件（2），则有 于是由定理定理4，迭代法（4.6）（即牛顿法）为局部收敛。且由 （4.5）取极限即得（4.7）。 牛顿法误差估计：牛顿法误差估计： 设 为 的 根，其中 在 邻近具有连续的一阶导数，且 ， 为由牛顿法得到的近似值，考虑 误差估计。)()()(xfxfxxg222)()()()()()()(1)(xfxfxfxfxfxfxfxg 0)()()()(2* xfxfxfxg0)(* xfkx

29、*x0)(xf)(xf*xkx即（ ） 1*xg35 利用中值公式有其中 在 和 之间。 当 充分接近 时，则有又由牛顿法公式，则 因此，在用牛顿法求 单根 时，一般可用 来估计 的误差，即当 充分接近 时，若)()()()(*xxcfxfxfxfkkkkkckx*xkx*x)()(,)()(*kkkkkxfcfcfxfxxkkkkkxxxfxfxx1*)()(0)(xf*xkkxx1kxkx*xkkxx1(4.8)36意味着 电算时，对于牛顿法可用当 时迭代终止。例例 8 对于例例 3 使用牛顿法计算 内一实根。解解 由牛顿法计算公式有： 方程的真根 ，求得的近似根 具有8位有 效数字。且k

30、xx*kkxx116)(, 1)(56xxfxxxf2 , 0), 1 , 0(1615 . 15610kxxxxxxkkkkk134724138. 1*x6x33433*1068. 41072. 4xxxx3701.511.3004908821.1814804231.1394555941.1347776351.1347241561.13472414表表 5-6)(kxfkxk1kkxx11089. 811054. 211038. 521092. 441050. 581008. 691000. 411000. 211019. 121020. 431068. 451035. 581000. 1c

31、x 0c0)(2cxxf 4.3牛顿法例子及框图牛顿法例子及框图例例9 设 ，试用牛顿法建立计算 的公式。解解 开方问题即为求解方程 。现用牛顿法解此方程， 有（图图 5-9）38图图 5-9xxfcxxf2)(, 0)(2于是即得计算 的公式 易知，上述迭代过程，对任意选取初值 都是收敛的。 00 x), 2 , 1 , 0)(21221kxcxxcxxxkkkkkkcx cxxf2)(0 x1xxy0396110kkxx 试计算 ，要求 时迭代终止。10 x01.015.523.6590909133.1960050843.1624556253.1622776763.16227766kxk表

32、表 5-7所以16227766. 310 40例例 10 用牛顿法求方程 的正实根。解解 方程在 内有一实根，在 内有二重根（图图 5-10）。)54() 3 . 4()(22xxxf046.9984 .46451.356 . 8234xxxx8 , 75 , 4123456780 xy100200100100)(xfy 图图 5-1041 （1） 用牛顿法计算 内单根，要求 。8 , 76110kkxx07.017.04856120.48561227.36041-0.12520537.3485747.3484757.348471kkxxkxk110118. 0310102. 0810758.

33、 0表表 5-834847. 75x即为所要求的近似根。42 （2） 用牛顿法求 内重根。5 , 404.014.1454080.14540824.221380.03895234.260330.03895244.280070.01974054.290010.009939kkx1kkxx 需要迭代19次，则有 ，且 。30000. 419x6181910612. 0 xx表表 5-943 由此例可见，牛顿方法在单根附近具有较快的收敛速度（达到一定的精度所需要的迭代次数较少），而用一般牛顿法求 内二重根时收敛较慢。这种情况牛顿方法可改进如下： 设 为 二重根（即 且 ）。这种情况可定义一个函数显然

34、， 为其单根，于是可用牛顿求法解且计算公式为： 5 , 4*x0)(xf)()()(2*xgxxxf0)(*xg）（）（xfxfxu)(*x0)(xu2221)( ()()(1)( ()()()( ()( ), 1 , 0( ,)( )(xfxfxfxfxfxfxfxukxuxukkkkxx(4.9)4404.014.3081290.30812924.30000134.30000044.300000表表 5-10210812. 0510807. 0910660. 0kkx1kkxx 用(4.9) 公式计算 内方程 二重根，只迭代4 次次就得到满足精度要求 的二重根，但这方法付出的代价是需要计算

35、 。 牛顿法框图图图 5-115 , 40)(xf6110kkxx)(xf45 计算输入计算计算 输出输出stop,00Nx0, 2 , 1Nk)(0 xf)(0 xf0)(0 xf1kx)()(000 xfxfxx0 xxxx 020i10i00ikxfx),(,0iLLL是是否否0Nk 图图 5-1146牛顿法牛顿法：设有方程 ， （1） 选择合适的初值 ； （2） ，计算其中 表最大迭代数，当 时，迭代终止。 表示求得满足给定精度的近似根。 表示 ，计算中断。 表示迭代 次后精度要求仍不满足。0)(xf0 x0, 2 , 1Nk)()(1kkkkxfxfxx0Nkkxx100I20I0N

36、10I0)(0 xf47xxxxfkkkkkffx11/)()()( 5 正正 割割 法法 若函数 比较复杂，求导可能有困难，此时可将牛顿公式中近似用差商来代替，即于是得到计算公式： (5.1)就是正割法公式正割法公式(图图 5-12)。)(xf)(xf), 2 , 1()()()()(,11110kfffxxxxxxxxxkkkkkkk初值(5.1)48x0P图图 5-12 正割法公式（5.1）可从下述想法得到： 设方程 ,且 ，于 连续，如果已知 则可用通过两点 的线性函数 近似代替 ，且求 的根记为 作为 的近似根，其中 为：)(xfy 0 x2x3x4x1xy02P3P*x0)(xf0

37、)()(bfafba,1kkxx)(,(),(,(2111kkkkxfxPxfxP)(xP)(xf0)(xP1kx0)(xf)(xP)()()()()(11kkkkkkxxxxxfxfxfxP49 即为(5.1)，正割法与牛顿法相比，其收敛速度比较慢。例例 11 用正割法求方程 于 内的 根。解解 取初值 ，计算结果见表表5-11。093)(23xxxxf)5 . 1, 2(1, 210 xx0-2-91-162-1.41.7760003-1.4990.3897434-1.526841-0.0263305-1.5250790.0003486-1.5251020.000000kkx)(kxf表表

38、 5-111kx50 6 迭代法的收敛阶和迭代法的收敛阶和Aitken加速方法加速方法 在迭代法定理定理4的条件下，且 ，由中值公式有 (6.1)其中 在 与 之间，且由 ，于是 。又由 (6.1) 式及 的连续性， 的误差 有关系 (6.2)由定理定理5可知，求解方程 的牛顿法产生的 的误差 有关系 一般情况，设有方程 及迭代过程 0)( *xg)*)( )(*)(*1kkkxxcgxgxgxxckx*xSx 0ScSxk,)(xgkxx *)(1limxgxxxxkkkkxx *)(2)(/21)(limxfxfxxxxkkk0)(xfkxkx(6.3)(xgx 51), 2 , 1 ,

39、0(),(10kgxxxkk初值）(6.4)且设 收敛于 。 如果误差有关系 (6.5)其中 为实数且 ， 为正常数，称迭代过程为 阶收敛，当 时（且要求0c1）称迭代过程为线性收敛线性收敛，当 时称迭代过程为超线性收敛超线性收敛，当 时称迭代过程为二次收敛二次收敛（或为平方收敛平方收敛）。 当一迭代过程为 阶收敛时 ，(6.5) 表示当 充分接近根 时有 (6.6)反映了 在接近收敛于 过程中，每迭代一次近似解误差的缩减速度，当 数值不大时，近似解误差下降速度主要取决于(6.6)中的幂次 。 kx*x01limcpkkkxxxxP1PP1P1P2PcPkx*xpkkxxcxx*1*kx*xc

40、P(6.6)52当 越大， 收敛于 速度就越快，于是 可以作为衡量迭代法收敛速度的一种度量。因此， 值的大小是衡量一个迭代过程优劣的标志之一。 于是，一般迭代法 ，当 时迭代过程为线性收敛（ ，(6.2)式）。牛顿法具有二阶收敛（由定理定理5及(6.3)式， ）。牛顿法在接近收敛过程中，近似根 的误差将是平方地下降，因此牛顿法在单根邻近具有 较快的收敛速度。但牛顿法对初值要求比较苛刻。初值选取不好，牛顿法可能发散（图图5-13）。当 为 二重根时，则牛顿法为线性收敛。 对于收敛较慢数列 （例如， 由迭代过程 产生），一个补救的方法是采用加速度公式。 设有P kx*xPP)(1kkxgx0)(*

41、xg1P2Pkx*x0)(xf kxkx)(1kkxgx) 10(,1limlimccxxxxxxkkkkk且53xy*x3x1x0 x2x0)(xfy 图图5-13于是 (6.7)则 能由 用下述方程确定，事实上，由(6.7)有cxxxxkk1*xxxxkkk21,54xxxxxxxxkkkk112*x上式说明，当（6.7）得到较好的满足时，则 是近似值 的很大的改进。于是，由数列 可定义一新的数列 xxk 2 kxkx解出 ， 则得xxxxxxkkkkkkx21221212)(122xkkxxxxxxkkkk（6.8）55定义定义 且序列 可能比 更快的收敛于 。这种由给出的数列 （收敛较

42、慢）来计算新数列 的方法称为Aitken加速方法加速方法。 当迭代过程收敛较慢时，一般可用Aitken方法加速，但有时Aitken方法加速可能失败，如当 起伏很大，初值 和根 有较大的距离时，Aitken加速就可能失败。 将将 Aitken 加速方法用于迭代法：加速方法用于迭代法： 设有方程 ， 为初值。 （1）迭代 （2）加速kx kx*x kx)( xg0 x*x)(xgx 0 x), 2 , 1 , 0(k(6.9)2, 1 ,0( ,12)(122kkkxxxxxxxkkkkkkx)(),(yzxykkkkgg(6.10), 2 , 1 , 0(2)(21kkkxyzxyxxkkkkk(6.11)56例例 12 设有方程 ，试用 Aitken 方法求 内方程根的近 似值。解解 迭代过程 计算到 ， 方程的精确解为 现用法加速（即(6.10)，(6.11)式）。结果如表表5-12。且 加速效果较好。exx6 . 0 , 5 . 0)2, 1 , 0( ,5 . 010kexxkxk567143438. 023x56714329. 0*x1062315. 0 xx10722 . 0 xx5700.50.60653066