对分法及一般迭代法

1、第四章第四章 非线性方程的数值解法非线性方程的数值解法 1根的存在性。方程有没有根？如果有根，有几个根？根的存在性。方程有没有根？如果有根，有几个根？定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0打打 印印结结 束束否否是是继续扫描继续扫描 例例1 1：考察方程：考察方程 的含根区间的含根区间01)(3xxxfx00.51.01.5f (x)符号符号可见，含根区间为可见，含根区间为 1, 1.54.1 对分区间法对分区间法 (Bisection Method )原理：原理：若若 f(x) Ca, b，且且 f (a) f (b) 0f

2、 (a) f (b)=0f (a) =0打印打印b, k打印打印a, k结束结束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m结束结束k=k+1是是是是否否否否输入输入 ,bak = 0 用二分法求用二分法求 在在(1,2)(1,2)内的根，要求绝对误差不超过内的根，要求绝对误差不超过 ： 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

3、,1.5) nx 1.51 x364. 1368. 1360. 1344. 1313. 1375. 125. 18765432 xxxxxxx12 例3，求方程f(x)= x 3 e-x =0的一个实根。 因为 f(0)0。 故f(x)在(0,1)内有根用二分法解之，(a,b）=（0,1)计算结果如表：ka 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.77

4、14 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 bisection 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:

5、要区别根与奇异点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 you obtained.（如下图）Remark3:二分法不能用来求重根f (x) = 0 x = g (x)等价变换等价变换f (x) 的根的根g (x) 的不动点的不动点4 4.2 .2 单个方程的迭代法 f(x)=0 f(x)=0化为等价方程化为等价方程x=g(x)x=g(x)的方式是不唯一的方式是不

6、唯一的的, ,有的收敛有的收敛, ,有的发散有的发散 For example For example：2x2x3 3-x-1=0-x-1=0 xk+1 = g(xk) (3)321xx 如果将原方程化为等价方程如果将原方程化为等价方程由此可见，这种迭代格式是发散的由此可见，这种迭代格式是发散的 取初值取初值00 x310211xx 321213xx 3322155xx 3121kkxx则迭代格式为：321xx 如果将原方程化为等价方程如果将原方程化为等价方程00 x21031 xx3217937.031221xx327937.19644.0仍取初值仍取初值依此类推依此类推, ,得得 x x3

7、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.0000 同样的方程同样的方程不同的迭代格式不同的迭代格式 有不同的结果有不同的结果什么形式的迭代什么形式的迭代法能够收敛呢法能够收敛呢? ?收敛性分析定义定义2 若存在常数若存在常数 (0 1),使得对一使得对一切切x x1 1,x,x2 2a,ba,b, , 成立不等式成

8、立不等式|g(x|g(x1 1)-g(x)-g(x2 2)| )| |x |x1 1-x-x2 2| |， (5) (5)则称则称g(x)g(x)是是a,ba,b上的一个压缩映射上的一个压缩映射， 称为压缩系数称为压缩系数 考虑方程考虑方程 x = g(x), g(x) Ca, b, 若若( I ) 当当 x a, b 时，时， g(x) a, 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）任取）任

9、取 x0 a, b，由由 xk+1 = g(xk) 得到的序列得到的序列 x xk k （ a,ba,b】）】） 收敛于收敛于x x* * 。（3）k k次迭代所得到的近似不动点次迭代所得到的近似不动点x xk k与精确不动点与精确不动点x x* *有误差估计有误差估计式：式：定理定理4.2.1*1(6)1kkkxxxx*10( 7 )1kkxxxx3 Fixed-Point Iteration证明：证明： g(x) 在在a, b上存在不动点？上存在不动点？ 不动点唯一？不动点唯一？ 当当k 时，时， xk 收敛到收敛到 x* ？ | |x x* *-x|=|g(x-x|=|g(x* *)-g

10、(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-2-x-x* *| | k k|x|x0 0-x-x* *| |0 0, ,令令G(x)=g(x)-x, xG(x)=g(x)-x, xa,ba,b，由条件知由条件知G(a)=g(a)-a0, G(b)=g(b)-b0.G(a)=g(a)-a

11、0, 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 越小，收敛越快越小，收敛越快(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*

12、 *| |）, ,故有故有 | |x xk k-x-x* *| | /(1-/(1- ) )|x|xk k-x-xk-1k-1|.|.这就证明了估计式这就证明了估计式(6). (6). (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-1k-1|x|x1 1-x-x0 0| |联系估计式联系估计式(6)(6)可得可得| |x xk k-x-x* *| | k-1k-1/(1-/(1- ) )|x|x1 1-x-x0 0|.|.即估计式即估计式(7)(7)成立成

13、立定理条件非必要条件，而且定理定理条件非必要条件，而且定理4 .1中中的压缩条件不好验证，一般来讲的压缩条件不好验证，一般来讲， 若知道迭代函数若知道迭代函数g(x)Cg(x)C1 1a,ba,b, ,并并且满足且满足|g(x)| |g(x)| 1,1,对任意的对任意的xxa,ba,b, ,则则g g（x)x)是是a,ba,b上的压缩映射上的压缩映射xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1改进、加速收敛改进、加速收敛 /* a

14、ccelerating convergence */ 待定参数法：待定参数法：若若 | g(x) | 1，则将则将 x = g(x) 等价地改造为等价地改造为)()()1()(xxKgxKxKgKxxx 1|)(1|)(| xgKKx 求求K，使得，使得例：例：求求 在在 (1, 2) 的实根。的实根。013)(3 xxxf)()1(313xgxx 如果用如果用 进行迭代，则在进行迭代，则在(1, 2)中有中有1| )(|2 xxg现令现令)1(3)1()()1()(3 xKxKxKgxKx 希望希望1|1| )(|2 KxKx 0122 Kx，即，即在在 (1, 2) 上可取任意上可取任意

15、，例如，例如K = 0.5，则对则对应应 即产生收敛序列。即产生收敛序列。032 K)1(61233 xxx例题 已知方程2x-7-lgx0，求方程的含根区间，考查用迭代法解此方程的收敛性。在这里我们考查在区间3.5,4的迭代法的收敛性 很容易验证：f(3.5)0 将方程变形成等价形式：x(lgx+7)/2(lg( )7)11( )2ln10 xg xx1g(x)=23.54max |( )| 0.0631xg x 由定理由定理4.2.1知，迭代格式知，迭代格式x xk+1k+1(lgx(lgxk k+7)/2+7)/2在在3.5,43.5,4内收敛内收敛局部收敛性定理局部收敛性定理定理定理4

16、 .2 设设x x* *为为g g的不动点，的不动点，g(x)g(x)与与g(x)g(x)在在包含包含x x* *的某邻域的某邻域U(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

17、 do we estimate the estimate the inequalityinequality？ 举例用一般迭代法求x3-x-1=0的正实根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,

18、故方程在（2,4）内至少有一个根1f (x)=10,2xx又 （ ， ）f (x)=02,2*因此方程 在（ ， ）内仅有一个根x且x（ ， ）将方程化为等价方程：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 xi0 3.00000000

19、0 1 3.098612289 2 3.130954362 3 3.141337866 4 3.144648781 5 3.145702209 6 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, 称

20、线性收敛称线性收敛; 1p 0，当，当x x0 0 x x* * - - ，x x* *+ + (x(x0 0 xx* *) )时，由迭代法时，由迭代法(3)(3)产生的序列产生的序列x xk k以以p p阶收敛速度收敛于阶收敛速度收敛于x x* *. .Proof: (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