数值分析3.1.二分法、迭代法及收敛性

1、第第3章章 非线性方程的数值解法非线性方程的数值解法 3.1 方程求根与二分法方程求根与二分法 3.2 迭代法及其收敛性迭代法及其收敛性 3.3 迭代收敛的加速方法迭代收敛的加速方法 3.4 牛顿法牛顿法 3.5 弦截法与抛物线法弦截法与抛物线法3.1.1 3.1.1 引言引言本章主要讨论本章主要讨论单变量非线性方程单变量非线性方程f(x)=0 (1.1)的求根问题，这里的求根问题，这里xR, f(x)Ca, b. 在科学与工程在科学与工程计算中有大量方程求根问题，其中一类特殊的问题计算中有大量方程求根问题，其中一类特殊的问题是多项式方程是多项式方程)2 . 1(),0()(01110 aax

2、axaxaxfnnnn其中系数其中系数ai(i=0,1,n)为实数为实数.3.1 方程求根与二分法方程求根与二分法n=1,2时方程的根是大家熟悉的，时方程的根是大家熟悉的，n=3,4时虽有求时虽有求根公式但比较复杂，可在数学手册中查到，但已不适根公式但比较复杂，可在数学手册中查到，但已不适合数值计算，而合数值计算，而n5时就不能用公式表示方程的根时就不能用公式表示方程的根.因因此，通常对此，通常对n3的多项式方程求根与一般连续函数方的多项式方程求根与一般连续函数方程程(1.1)一样都可采用迭代法求根一样都可采用迭代法求根.方程方程f(x)=0的的根根 x*，又称为函数又称为函数f(x)的的零点

3、零点，它使得，它使得f(x*)=0，若，若f(x)可分解为可分解为f(x)=(x- -x*)mg(x)，其中其中m为正整数，且为正整数，且g(x*)0. 当当m=1时，则称时，则称x*为为单单根根，若，若m1称称x*为为(1.1)的的m重根重根，或，或x*为函数为函数f(x)的的m重零点重零点. 若若x*是是f(x)的的m重零点重零点，则，则. 0)(, 0)()()()()1( xfxfxfxfmm注：注：3.1.2 3.1.2 二分法二分法如果如果 f(x) 在区间在区间a, b上连续上连续, f(a)f(b)0, 则在则在a, b 内有方程的根内有方程的根. （ Bisection Me

4、thod ）二分法原理二分法原理二分法的实施过程二分法的实施过程取取a, b的中点的中点 将区间一分为二将区间一分为二. 若若 f (x0)=0, 则则x0就是方程的根就是方程的根, 否则判别根否则判别根 x*在在 x0 的的左侧左侧还是还是右侧右侧., )(210bax 若若f(a) f(x0)0, 则则x*(a, x0), 令令 a1= a, b1=x0;若若f(x0) f(b)0, 则则x*(x0 , b), 令令 a1=x0, b1=b. . 不论出现哪种情况不论出现哪种情况, (a1, b1)均为新的有根区间均为新的有根区间, 它它的的长度只有原有根区间长度的一半长度只有原有根区间长

5、度的一半, 达到了达到了压缩有根压缩有根区间的目的区间的目的.如此反复进行如此反复进行, 即可的一系列即可的一系列有根区间套有根区间套 ,11nnbababa 由于每一区间都是前一区间的一半，因此区间由于每一区间都是前一区间的一半，因此区间an , bn的长度为的长度为)(ababnnn 21若每次二分时所取区间中点都不是根，则上述过程将若每次二分时所取区间中点都不是根，则上述过程将无限进行下去无限进行下去. 当当 n 时，区间必将最终收缩为一时，区间必将最终收缩为一点点x* ，显然，显然 x* 就是所求的就是所求的根根. 若取区间若取区间an , bn的中点的中点)(nnnbax 21作为作

6、为x*的近似值，则有下述的近似值，则有下述111*()()22nnnnxxbaba 只要只要 n 足够大足够大, (即区间二分次数足够多即区间二分次数足够多)，误差就可，误差就可足够小足够小.),(,*11 nnnbaxx二分法的误差估计二分法的误差估计例例1 用二分法求方程用二分法求方程 f(x)=x3- -x- -1=0在在(1, 1.5)的实根的实根,要求误差不超过要求误差不超过0.005. 解解 由题设条件，即：由题设条件，即：则要则要005. 021)15 . 1(21)(21211 nnnab|x*- -xn|0.005由此解得由此解得 取取 n=6, 按二分法计算过程见按二分法计

7、算过程见下表下表, x6 = 1.3242 为所求之近似根为所求之近似根., 6 . 512lg2 nn an bn xn f(xn)说明说明01234561.01.251.251.31251.31251.31251.32031.51.51.3751.3751.34381.32811.32811.251.3751.31251.34381.32811.32031.3242- -+ +- -+ + +- - -(1) f(a)0(2) 根据精根据精 度要求，度要求，取到小数取到小数点后四位点后四位 即可即可. 二分法的二分法的优点优点是算法简单，且总是收敛的，是算法简单，且总是收敛的，缺缺点点是收

8、敛的太慢，故一般不单独将其用于求根，只是收敛的太慢，故一般不单独将其用于求根，只是用其为根求得一个较好的近似值是用其为根求得一个较好的近似值.二分法的计算步骤二分法的计算步骤: :步骤步骤1 准备准备 计算函数计算函数f(x)在区间在区间a, b端点处的值端点处的值f(a), f(b). 若若f(a)f(a+b)/2)0, 则以则以(a+b)/2代替代替b ，否则以，否则以(a+b)/2代替代替a.步骤步骤2 二分二分 计算函数计算函数f(x)在区间中点在区间中点(a+b)/2处的处的值值f(a+b)/2).步骤步骤3 判断判断 若若f(a+b)/2)=0，则，则(a+b)/2即是根，即是根，

9、计算过程结束，否则检验计算过程结束，否则检验. 反复执行步骤反复执行步骤2和步骤和步骤3，直到区间，直到区间a, b长度小于长度小于允许误差允许误差，此时中点，此时中点(a+b)/2即为所求近似根即为所求近似根.3.2 迭代法及其收敛性迭代法及其收敛性3.2.1 3.2.1 不动点迭代法不动点迭代法 将方程将方程 f(x)=0 改写为等价方程形式改写为等价方程形式 x= (x). (2.1)若要求若要求 x* 满足满足 f(x*)=0，则，则 x*= (x*)；反之亦然，称；反之亦然，称 x*为函数为函数 (x)的一个的一个. 求求 f(x) 的的就等于求就等于求 (x)的的，选择一个初始近似

10、值，选择一个初始近似值 x0，将它代入，将它代入(2.1)右右端，即可求得端，即可求得 x1= (x0). .lim xxkk可以如此反复迭代计算可以如此反复迭代计算 xk+1= (xk) (k=0,1,2,). (2.2) (x)称为迭代函数称为迭代函数. 如果对任何如果对任何x0a, b，由，由(2.2)得得到的序列到的序列xk有极限有极限则称迭代方程则称迭代方程(2.2)收敛收敛. 且且x*= (x*)为为 (x)的的不动点不动点，故称故称(2.2)为为不动点迭代法不动点迭代法.当当 (x)连续时，连续时，显然显然x*就是方程就是方程 x= (x)之之根根(不动点不动点). 于是可以从数

11、列于是可以从数列xk中求得满足精度要求的近似根中求得满足精度要求的近似根. 这种求根方法称为这种求根方法称为不动点迭代法不动点迭代法, 1()(0,1,2,)kkxxk 称为称为迭代格式迭代格式, (x)称为称为迭代函数迭代函数, x0 称为称为迭代初值迭代初值,数列数列xk称为称为迭代序列迭代序列. 如果迭代序列收敛如果迭代序列收敛, 则称迭则称迭代格式代格式收敛收敛,否则称为否则称为发散发散. 1()(0,1,2,)kkxxk .lim xxkk 03224xxx分别按以上三种形式建立迭代公式，并取分别按以上三种形式建立迭代公式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：

12、14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 解解 对方程进行如下三种变形：对方程进行如下三种变形：例例2 用迭代法求方程用迭代法求方程x4+2x2- -x- -3=0 在区间在区间1, 1.2内内的实根的实根.准确根准确根 x* = 1.124123029, 可见可见迭代公式不同迭代公式不同, 收敛情收敛情况也不同况也不同. 第二种公式比第一种公式收敛快得多第二种公式比第一种公式收敛快得多, 而而第三种公式第三种公式不收敛不收敛.73496,8.495307 10 xx 12()41kkkxxx 4213()23kkkkxxxx 12411()(32)kkkkx

13、xxx 26271.124123xx 671.124123xx xyoy= (x)y=x解解x= (x)求求 y=x 与与y= (x)的的交点的横坐标交点的横坐标x*x0(x0 , x1)(x1 , x2)(x1 , x1)x1x2迭代法的几何意义迭代法的几何意义xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1注：迭代法的研究涉及四个问题：注：迭代法的研究涉及四个问题：(1)(1)迭代公式的选取；迭代公式的选取；(2)(2)迭代公式收敛性的判定；迭

14、代公式收敛性的判定；(3)(3)在收敛情况下，如何比较收敛速度；在收敛情况下，如何比较收敛速度；(4)(4)迭代停止的条件。迭代停止的条件。3.2.2 3.2.2 不动点的存在性与迭代法的收敛性不动点的存在性与迭代法的收敛性 首先考察首先考察 (x)在在a, b上不动点的存在唯一性上不动点的存在唯一性. 设设 (x)Ca, b满足以下两个条件：满足以下两个条件：1 对任意对任意xa, b有有a (x)b. .)4 . 2(.)()(yxLyx 2 存在正数存在正数La及及 (b)0, f(b)= (b)- -b0, 由连续函数性质可知存在由连续函数性质可知存在 x*(a, b) 使使 f(x*

15、)=0，即，即x*= (x*)，x*即为即为 (x)的不动点的不动点. 再证不动点的再证不动点的. 设设x1*, x2*a, b都是都是 (x)的不动点，则由的不动点，则由(2.4)得得.)()(21212121 xxxxLxxxx 引出矛盾，故引出矛盾，故 (x)的不动点只能是唯一的的不动点只能是唯一的. . 设设 (x)Ca, b满足定理满足定理1中的两个条件，中的两个条件，则对任意则对任意x0a, b，由，由(2.2)得到的迭代序列得到的迭代序列xk收敛收敛到不动点到不动点x*，并有，并有)6 . 2(.1)5 . 2(.1101kkkkkxxLLxxxxLLxx 证明证明 设设x*a,

16、 b是是 (x)在在a, b上的唯一不动点上的唯一不动点, ,由条件由条件1，可知，可知xka, b，再由，再由(2.4)得得.)()(011xxLxxLxxxxkkkk 因因0L1时称时称超线性收敛超线性收敛，p=2 时称时称平方收敛平方收敛. 对于迭代过程对于迭代过程 xk+1= (xk)，如果，如果 ( (p) )(x)在在所求根所求根 x* 的邻近连续（的邻近连续（ p 1），并且），并且)8 . 2(. 0)(, 0)()()()()1( xxxxpp 则该迭代过程在则该迭代过程在 x* 的邻近是的邻近是 p 阶收敛的阶收敛的. 由于由于(x*)=0，根据定理，根据定理3立即可以断定

17、迭立即可以断定迭代过程代过程xk+1= (xk)具有局部收敛性具有局部收敛性. 再将再将 (xk)在根在根x*处做泰勒展开处做泰勒展开, 利用条件利用条件(2.8), 则有则有.,)(!)()()()(之间之间与与在在 xxxxpxxkpkpk 注意到注意到 (xk)=xk+1， (x*)= x*，由上式得，由上式得,)(!)()(1pkpkxxpxx 因此对迭代误差，令因此对迭代误差，令k时有时有这表明迭代过程这表明迭代过程xk+1= (xk)确实为确实为 p 阶收敛阶收敛. 证毕证毕. ( )1|()|.!pkpkexep上述定理告诉我们，迭代过程的收敛速度依赖于上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数迭代函数 (x)的选取的选取. 如果如果xa, b但但 (x)0 时，则时，则该迭代过程只可能是线性收敛该迭代过程只可能是线性收敛.)0( aa的三阶方法的三阶方法. 假设假设 x0 充分靠近充分靠近 x*, 求求13|lim|() |kkkaxax 提示：提示： 设设 (x) =x(x2+3a)/(3x2+