计算方法中对分法和一般迭代法

1、数值分析数值分析第二章第二章 非线性方程的数值解法非线性方程的数值解法 简介（Introduction） 我们知道在实际应用中有许多非线性方程的例子，例如 （1）在光的衍射理论（the theory of diffraction of light)中,我们需要求x-tanx=0的根 （2）在行星轨道（ planetary orbits）的计算中,对任意的a和b，我们需要求x-asinx=b的根 （3） 在数学中，需要求n次多项式xn + a1 xn-1+.+an-1 x + an 0的根求求f(x)=0f(x)=0的根的根2.1 对分区间法对分区间法 (Bisection Method )原理

2、：原理：若若 f(x) Ca, b，且且 f (a) f (b) 0，则则f(x) 在在 (a, b) 上必有一根。上必有一根。abx1x2a1b2x*b1a2停机条件（termination condition ）：11xxkk 2)(xf 或或误差误差 分析：分析：第第1步产生的步产生的21bax 有误差有误差21abx*|x 第第 k 步产生的步产生的 xk 有误差有误差kkabx*|x2 对于给定的精度对于给定的精度 ,可估计二分法所需的步可估计二分法所需的步数数 k ： 2lnlnln2abkabk 用二分法求用二分法求 在在(1,2)(1,2)内的根，要求绝对误差不超过内的根，要求

3、绝对误差不超过 ： f(1)=-50 -(1,2)+ f(1.25)0 (1.25,1.375) f(1.313)0 (1.313,1.375) f(1.344)0 (1.344,1.375) f(1.360)0 (1.360,1.368) 010423 xx21021 f(1.5)0 (1,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx12 例2，求方程f(x)= x 3 e-x =0的一个实根。 因为 f(0)0。 故f(x)在(0,1)内有根用二分法解之，(a, b)=(0, 1), 计算结果如

4、表：k ak bk xk f(xk)符号00 1 0.5000 10.5000 0.7500 20.7500 0.8750 3 0.87500.8125 4 0.81250.7812 5 0.7812 0.7656 60.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 90.7714 0.7724 100.7724 0.7729 取x10=0.7729，误差为| x* -x10|=1/211 。 Remark1：求奇数个根 Find solutions to the equationon the intervals 0, 4，Use the bisect

5、ion method to compute a solution with an accuracy of 107. Determine the number of iterations to use. 0,1, 1.5, 2.5 and 3,4，利用前面的公式可计算迭代次数为k=23. Remark2:要区别根与奇异点Consider f(x) = tan(x) on the interval (0,3).Use the 20 iterations of the bisection method and see what happens. Explain the results that yo

6、u obtained.（如下图）Remark3:二分法不能用来求重根f (x) = 0 x = g (x)等价变换等价变换f (x) 的根的根g (x) 的不动点的不动点2 2.2 .2 单个方程的迭代法 f(x)=0 f(x)=0化为等价方程化为等价方程x=g(x)x=g(x)的方式是不唯一的方式是不唯一的的, ,有的收敛有的收敛, ,有的发散有的发散 For example For example：2x2x3 3-x-1=0-x-1=0321xx 如果将原方程化为等价方程如果将原方程化为等价方程由此可见，这种迭代格式是发散的由此可见，这种迭代格式是发散的 取初值取初值00 x310211x

7、x 321213xx 3322155xx 3121kkxx则迭代格式为：321xx 如果将原方程化为等价方程如果将原方程化为等价方程00 x21031 xx3217937.031221xx327937.19644.0仍取初值仍取初值依此类推依此类推, ,得得 x x3 3 = 0.9940 = 0.9940 x x4 4 = 0.9990 = 0.9990 x x5 5 = 0.9998 = 0.9998 x x6 6 = 1.0000 = 1.0000 x x7 7 = 1.0000 = 1.0000已经收敛已经收敛, ,故原方程的解为故原方程的解为 x = 1.0000 x = 1.000

8、0 同样的方程同样的方程不同的迭代格式不同的迭代格式 有不同的结果有不同的结果什么形式的迭代什么形式的迭代法能够收敛呢法能够收敛呢? ?收敛性分析定义定义2 若存在常数若存在常数 (0 1),使得对一使得对一切切x x1 1,x,x2 2a,ba,b, , 成立不等式成立不等式|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| |， 则称则称g(x)g(x)是是a,ba,b上的一个压缩映射上的一个压缩映射， 称为压缩系数称为压缩系数 考虑方程考虑方程 x = g(x), g(x) Ca, b, 若若( I ) 当当 x a, b 时，时， g(x) a

9、, b；( II )在在a,ba,b上成立不等式：上成立不等式：|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| | 。则（则（1）g g在在a,ba,b上存在惟一不动点上存在惟一不动点x x* *（2）任取）任取 x0 a, b，由由 xk+1 = g(xk) 得到的序列得到的序列 x xk k （ a,ba,b】）】） 收敛于收敛于x x* * 。（3）k k次迭代所得到的近似不动点次迭代所得到的近似不动点x xk k与精确不动点与精确不动点x x* *有有有误差估有误差估计式：计式：定理定理2.2.1*11kkkxxxx*101kkxxxx3

10、Fixed-Point Iteration证明：证明： g(x) 在在a, b上存在不动点？上存在不动点？ 不动点唯一？不动点唯一？ 当当k 时，时， xk 收敛到收敛到 x* ？ | |x x* *-x|=|g(x-x|=|g(x* *)-g(x)| )-g(x)| |x |x* *-x|. -x|. 因因0 0 1 1，故必有，故必有 x=xx=x* *若有若有xxa,ba,b, ,满足满足g(x)=xg(x)=x，则则| |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| | |x k-1k-1-x-x* *| | 2 2|x|xk-2k

11、-2-x-x* *| | k k|x|x0 0-x-x* *| |0 0令令G(x)=g(x)-x, xG(x)=g(x)-x, xa a，b b，由条件知由条件知G(a)=g(a)-a0, G(b)=g(b)-b0.G(a)=g(a)-a0, G(b)=g(b)-b0.由条件知由条件知G(x)G(x)在在a,ba,b上连续，又由介值定理知上连续，又由介值定理知存在存在x x* *a,ba,b，使使G(xG(x* *)=0)=0，即即x x* *=g(x=g(x* *).).3 Fixed-Point Iteration 可用可用 来来控制收敛精度控制收敛精度|1kkxx 越小，收敛越快越小，

12、收敛越快(4) |(4) |x xk k-x-x* *|=|g(x|=|g(xk-1k-1)-g(x)-g(x* *)| )| | |x k-1k-1-x-x* *| | （|x|xk k-x-xk-1k-1|+|x|+|xk k-x-x* *| |）, ,故有故有 | |x xk k-x-x* *| | /(1-/(1- ) )|x|xk k-x-xk-1k-1|.|.这就证明了估计式这就证明了估计式. . (5) (5) |x|xk k-x-xk-1k-1| | = |g(x= |g(xk-1k-1)-g(x)-g(xk-2k-2)|)| | |x k-1k-1-x-xk-2k-2| k-

13、1k-1|x|x1 1-x-x0 0| |联系估计式可得联系估计式可得 | |x xk k-x-x* *| | k-1k-1/(1-/(1- ) )|x|x1 1-x-x0 0|.|.即估计式成立即估计式成立定理条件非必要条件，而且定理定理条件非必要条件，而且定理2 .1中中的压缩条件不好验证，一般来讲的压缩条件不好验证，一般来讲， 若知道迭代函数若知道迭代函数g(x)Ca,b,g(x)Ca,b,并且满并且满足足|g(x)| |g(x)| 1,1,对任意的对任意的xxa,ba,b, ,则则g(x)g(x)是是a,ba,b上的压缩映射上的压缩映射例题 已知方程2x-7-lgx0，求

14、方程的含根区间，考查用迭代法解此方程的收敛性。在这里我们考查在区间3.5,4的迭代法的收敛性 很容易验证：f(3.5)0 将方程变形成等价形式：x(lgx+7)/2(lg( )7)11( )2ln10 xg xx1g(x)=23.54max |( )| 0.0631xg x 由定理由定理3.2.1知，迭代格式知，迭代格式x xk+1k+1(lgx(lgxk k+7)/2+7)/2在在3.5,43.5,4内收敛内收敛局部收敛性定理局部收敛性定理定理定理2 .2设设x x* *为为g g的不动点，的不动点，g(x)g(x)与与g(x)g(x)在在包含包含x x* *的某邻域的某邻域U

15、(xU(x* *) () (即开区间即开区间) )内连续，内连续，且且| |g(xg(x* *)|1)| 0 0，当，当x x0 0 x x* * - - ，x x* *+ + 时，迭代法时，迭代法(3)(3)产生的序列产生的序列 x xk k x x* * - - ，x x* *+ + 且收敛于且收敛于x x* *. .证明略（作为练习）证明略（作为练习）We donWe dont know t know x x* *,how do we ,how do we estimate the estimate the inequalityinequality？ 举例用一般迭代法求x3-x-1=0的

16、正实根x*3x= x+1将方程改写成：3x)= x+1则迭代函数为：g(231x)=3x+1 g (（）容易得到：容易得到：g(x)g(x)在包含在包含x x* *的某邻域的某邻域U(xU(x* *) ) 内内连续，且连续，且| |g(xg(x* *)|1)|1*3kx= x +1xk+1因此迭代格式在 附近收敛例题用一般迭代法求方程x-lnx2在区间（2，）内的根，要求|xk-xk-1|/|xk|=10-8解：令f(x)=x-lnx-2f(2)0,故方程在（2,4）内至少有一个根1f (x)=10,2xx又 （ ， ）f (x)=02,2*因此方程 在（ ， ）内仅有一个根x且x（ ， ）将

17、方程化为等价方程：x2lnx1g(x)2lnx (x)|=| 0.51,2 4xx ， |g（ ， ）因此， x0（2，），xk+12lnxk产生的序列 xk 收敛于X*取初值x03.0,计算结果如下：7 3.1461436118 3.146177452 9 333333.146193204k xk0 3.000000000 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6

18、 3.146037143另一种迭代格式： 1(1 ln)1kkkkxxxx 0 3.000000000 1 3.147918433 2 3.146193441 3 3.146193221 由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。 定义定义1. :设设序列序列xk收敛于收敛于x*，若存在若存在p1和正数和正数c，使得成立使得成立则称则称xk为为 p 阶收敛的阶收敛的特别特别, p = 1，要求要求c1, 称线性收敛称线性收敛; 1p 0，当，当x x0 0 x x* * - - ，x x* *+ + (x(x0 0 xx* *) )时，由迭代法时，由迭代法

19、xk+1 = g(xk)产生的序列产生的序列x xk k以以p p阶收敛速度收敛于阶收敛速度收敛于x x* *. .Prove: (1)(1)由由g(g(x x* *)=0)=0必存在必存在 0，当，当x x0 0 x x* * - - ，x x* *+ + U(x)U(x)时，由迭代格式时，由迭代格式(3)(3)产生的序列产生的序列 x xk k 收收敛于敛于x x* *, ,并有并有x xk k x x* * - - ，x x* *+ + (2)(2)由泰勒公式有由泰勒公式有x xk+1k+1=g(x=g(xk k)=)=g(xg(x* * ）g(xg(x* *)(x)(xk k- - x x* *)+)+g +g (p-1)(p-1) (x (x* *)(x)(xk k-x-x* *)