《Chapter对分法和般迭代法》由会员分享，可在线阅读，更多相关《Chapter对分法和般迭代法（33页珍藏版）》请在金锄头文库上搜索。
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)=0的根,4.1 对分区间法 (Bisection Method ),原理：若 f(x) Ca, b，且 f (a) f (b) 0 (1
2、,1.5),12,例2，求方程f(x)= x 3 e-x =0的一个实根。因为 f(0)0。 故f(x)在(0,1)内有根 用二分法解之，(a,b）=（0,1)计算结果如表： k a bk xk f(xk)符号 0 0 1 0.5000 1 0.5000 0.7500 2 0.7500 0.8750 3 0.8750 0.8125 4 0.8125 0.7812 5 0.7812 0.7656 6 0.7656 0.7734 7 0.7734 0.7695 8 0.7695 0.7714 9 0.7714 0.7724 10 0.7724 0.7729 取x10=0.7729，误差为| x*
3、-x10|=1/211 。,Remark1：求奇数个根,Find solutions to the equation,on the intervals 0, 4，Use the bisection method to compute a solution with an accuracy of 107. Determine the numberof 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)
4、.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.2 单个方程的迭代法,f(x)=0化为等价方程x=g(x)的方式是不唯一的,有的收敛,有的发散For example：2x3-x-1=0,xk+1 = g(xk) (3),(1) 如果将原方程化为等价方程,由此可见，这种迭代格式是发散的,取初值,(2)
5、如果将原方程化为等价方程,仍取初值,依此类推,得x3 = 0.9940x4 = 0.9990x5 = 0.9998x6 = 1.0000x7 = 1.0000,已经收敛,故原方程的解为 x = 1.0000,同样的方程 不同的迭代格式有不同的结果,什么形式的迭代法能够收敛呢?,收敛性分析,定义2 若存在常数(0 1),使得对一切x1,x2a,b, 成立不等式 |g(x1)-g(x2)| |x1-x2|， (5) 则称g(x)是a,b上的一个压缩映射， 称为压缩系数,考虑方程 x = g(x), g(x)Ca, b, 若 ( I ) 当 xa, b 时， g(x)a, b； ( II )在a,b
6、上成立不等式：|g(x1)-g(x2)| |x1-x2| 。 则（1）g在a,b上存在惟一不动点x* （2）任取 x0a, b，由 xk+1 = g(xk) 得到的序列 xk（a,b】） 收敛于x* 。 （3）k次迭代所得到的近似不动点xk与精确不动点x*有有误差估计式：,定理4.2.1,3 Fixed-Point Iteration,证明： g(x) 在a, b上存在不动点？, 不动点唯一？, 当k 时， xk 收敛到 x* ？,|x*-x|=|g(x*)-g(x)| |x*-x|. 因0 1，故必有 x=x*,若有xa,b,满足g(x)=x，则,|xk-x*|=|g(xk-1)-g(x*)
7、| |x k-1-x*| 2|xk-2-x*| k|x0-x*|0,令G(x)=g(x)-x, xa,b，由条件知G(a)=g(a)-a0, G(b)=g(b)-b0.,由条件知G(x)在a,b上连续，又由介值定理知 存在x*a,b，使G(x*)=0，即x*=g(x*).,3 Fixed-Point Iteration,可用 来控制收敛精度,越小，收敛越快,(4) |xk-x*|=|g(xk-1)-g(x*)| |x k-1-x*| （|xk-xk-1|+|xk-x*|）, 故有 |xk-x*| /(1-)|xk-xk-1|. 这就证明了估计式(6).,(5) |xk-xk-1| = |g(x
8、k-1)-g(xk-2)| |x k-1-xk-2| k-1|x1-x0|,联系估计式(6)可得 |xk-x*| k-1/(1-)|x1-x0|. 即估计式(7)成立,Remark：,定理条件非必要条件，而且定理4.2.1中的压缩条件不好验证，一般来讲，若知道迭代函数g(x)Ca,b,并且满足|g(x)| 1,对任意的xa,b, 则g（x)是a,b上的压缩映射,例题,已知方程2x-7-lgx0，求方程的含根区间，考查用迭代法解此方程的收敛性。,在这里我们考查在区间3.5,4的迭代法的收敛性,很容易验证：f(3.5)0 将方程变形成等价形式：x(lgx+7)/2,由定理4.2.1知，迭代格式xk
9、+1(lgxk+7)/2 在3.5,4内收敛,局部收敛性定理,定理4.2.2 设x*为g的不动点，g(x)与g(x)在包含x*的某邻域U(x*) (即开区间)内连续，且|g(x*)|0，当x0x* - ，x*+ 时，迭代法(3)产生的序列xk x* - ，x*+ 且收敛于x*.证明略（作为练习）,We dont know x*,how do we estimate the inequality？,举例,用一般迭代法求x3-x-1=0的正实根x*,容易得到：g(x)在包含x*的某邻域U(x*) 内 连续，且|g(x*)|1,例题,用一般迭代法求方程x-lnx2在区间（2，）内的根，要求|xk-x
10、k-1|/|xk|=10-8,解：令f(x)=x-lnx-2,f(2)0,故方程在（2,4）内至少有一个根,将方程化为等价方程：x2lnx,因此， x0（2，），xk+12lnxk产生的序列 xk 收敛于X*,取初值x03.0,计算结果如下：,7 3.146143611 8 3.1461774529 3.146188209 10 3.146191628 11 3.146192714 12 3.146193060 13 3.146193169 14 3.146193204,k xi 0 3.0000000001 3.0986122892 3.1309543623 3.1413378664 3.1
11、446487815 3.1457022096 3.146037143,另一种迭代格式：,0 3.0000000001 3.1479184332 3.1461934413 3.146193221,程序演示,由此可见，对同一个非线性方程的迭代格式，在收敛的情形下，有的收敛快，有的收敛慢。,定义1. :设序列xk收敛于x*，若存在p1和正数c， 使得成立,则称xk为 p 阶收敛的,特别,p = 1，要求c1, 称线性收敛;1p0，当x0 x* - ，x*+ (x0x*)时，由迭代法(3)产生的序列xk以p阶收敛速度收敛于x*.,Proof:,(1)由g(x*)=0必存在0，当x0 x* - ，x*+
12、 U(x)时，由迭代格式(3)产生的序列xk收敛于x*,并有xk x* - ，x*+ (2)由泰勒公式有xk+1=g(xk)=g(x* ）g(x*)(xk- x*)+g (p-1) (x*)(xk-x*) p-1/(p-1)! + g (p)(x*+ (xk-x*)(xk-x*) p /p! ，01. 利用g在x*的各阶导数条件及g(x*)=x*,上式可改写成,(11),(3)由于g在x*处p阶连续可微且g(p)(x*)0，知必存在x*的某邻域(x*)，当xU(x*)时，有g (p) (x)0. 由于x*+ (xk-x*) x* - ，x*+ U(x*)，故 g (p)(x*+ (xk-x*) 0，k=0，1,2,. 可见，当初值x0x*时，由(11)式可推出xkx* 于是由(11)式有,上式令k取极限.,即xk有p阶收敛速度.,
