第二章 数值分析

第二章方程求根教学内容：1．二分法2．基本迭代法3．牛顿法4．弦位法5．埃特金法和斯基芬森法6．重根的情况教学重点：各种算法的思路及迭代公式的构造教学难点：各种算法的收敛性、收敛速度及误差估计计划学时：5-6学时授课提纲：方程求根就是求函数f(x)的零点x*，即求解方程f(x)二0这里，f(x)=0可以是代数方程，也可以不是，如超越方程。方程的根既可以是实数，也可以是复数；既可能是单根，也可能是重根；即可能要求求出给定范围内的某个根，也可能要求求出方程全部的根。本章介绍的方法对两类方程都适用，但大部分都是要求知道根在什么范围内，且在此范围内只有一个单根。若有a使得f(a)二0,f'Q)丰0，则称a是方程f(x)二0的单根；若有a使得f(a)=f'(a)= =f(m-1)(a)二0,f(m)(a)丰0，则称a是方程f(x)二0的m重根。设f(x)在区间［a,b］连续，若f(a)f(b)<0，则f(x)在区间(a,b)内至少有一个实根，若再有f'(x)不变号，则有根区间(a,b)内仅有一个实根。除特别声明，本章介绍的算法都是求单实根。2.1二分法二分法又称区间对分法，是最直观、最简单的一种方法。2.1.1二分法原理若f(x)在［a,b］内单调连续，且f(a)f(b)v0,则f在(a,b)内必有惟一的实根。

2.1.2二分法思想区间对分，去同存异2.1.3二分法计算步骤步1：令x二(a+b)/2，计算f(x)；00步2：若f(x)二0，令x*=x，计算结束；00步3：若f(x)*f(a)>0,令a二x；否则令b=x；000步4：若Ib-al<e，令x*二(a+b)/2,计算结束；否则转步1。2.1.4二分法误差分析和收敛性记第k次区间中点为x，则有k…,x*一x<（b一a）/2k+1k得x*一x<（b一a）/2,x*…,x*一x<（b一a）/2k+1k得01故当kT2时，xTx*。k为使|x*-x|<8，解不等式（b一a）/2k+i<8,kk>[ln（b一a）一In8]/ln2一12.1.5二分法的优缺点•算法简单直观，易编程计算；•只需f(x)连续即可；•区间收缩速率相同，收敛速度慢；•无法求复根和偶重根。 例2-1p15例12.2迭代法迭代法原理f(x)二0 Of(x)的根迭代法思路任取初值xe[a,b]，令x=申(x)，x=9(x)，反复迭代，即得01021x=9(x),(k=0,1,2,…)k+1 k直到满足精度要求的x来近似x*。称x=9(x)为迭代公式，9(x)为迭代函数,k｛x｝为迭代序列。x=x*，当9（x）连续时kkT8x=x*，当9（x）连续时kkT8=limx=lim9（x）=9（lim）=9（x*）k+1 kkT8 kT8 kT8亦即f(x*)=0。若｛x｝不收敛，称迭代公式是发散的。k

2.2.3迭代法的计算步骤步1：选取初值x及精度8，置k=0；0步2：计算x二申(x)；k+1 k步3：若|x-x|<8，令x*二x，计算结束；令*=*+1,转第2步。k+1 k k+1迭代法的几何意义及收敛性条件迭代法的几何意义是求曲线y=x和y二申(x)交点的横坐标x*。可以看出，若申(x)的变化幅度小于x的变化幅度时，迭代公式收敛，否则，迭代公式不收敛。迭代序列的收敛性依赖于构造的迭代函数(不唯一)。例2-2求方程f(x)=x5-2x-1在(1,2)内的根。分别构造迭代函数申(x)二5；2x+1 申(x)二(x5-1)122定理2-1迭代收敛基本定理设迭代函数申(x)在［a,b］内连续，在(a,b)内可导，且满足映内性：当xg［a,b］时，有申(x)g［a,b］；压缩性：30<L<1，Vxg［a,b］，有b'(x)|<L；

函数申(x)在[a,b]内存在惟一的不动点x*；Vxe[a,b]，迭代公式x (x)产生的序列｛x e[a,b]，且0 k+1 k kk=1imx=x*ksk有如下误差估计1-Lk+1x1-Lk+1x*一xk(k=1,2,…)(k=1,2,…)；limx—xk+1x*一x=9'(x*)说明：(i)常用|x—xI来控制是收敛精度，L越小，收敛越快。k+1k(ii)条件30<L<1， Vxe[a,b]，有'(x)|<L太强，但是好验证，可以改为较弱的条件：Vx,xe[a,b],9(x)—9(x)|<Llx—xI,其中L是与x,x无关的常数12121 2丨 12(Lipschitz常数)，且0<L<1。(iii)定理的条件是迭代公式收敛的充分条件，非充要条件。p19例3。定义2-1如果存在x*的某个邻域N(x*,6)，使迭代过程x =9(x)对任意k+1 k的初值xeN(x*,6)均收敛，则称该迭代过程在根x*邻近具有局部收敛性。0定理2-2局部收敛性定理设x*是x=9(x)的不动点，9‘(x)在x*的某个邻域N(x*,6)内连续且9'(x)<L<1，则迭代公式x=9(x)对任意的初值k+1 kxeN(x*,6)局部收敛。0定理2-3设x*是x=9(x)的不动点，9‘(x)在x*附近连续，若存在x*的某个邻域N(x*,6)，VxeN(x*,6)，都有”'(x)|>1，则迭代公式不对任意的初值xeN(x*,6)收敛，称为发散。见p19定理3。0定理2-4对于迭代公式x=9(x)，如果9(p)(x)在x*附近连续，且有k+1 k9‘(x*)=9“(x*)=…=9(p—1)(x*)=0,9(p)(x*)乂0则该迭代公式在x*附近是p阶收敛的。见p20定理4。

证明：由9'(x*)=0证明：由9'(x*)=0及定理2-2知，迭代过程x =9(x)在x*的附近具有k+1 k局部收敛性。再将9(x)在x*处做泰勒展开，则有k9(x)=9(x*)+9"")(g)(x—x*)pk p! kp!(g介于x和x*之间)k注意到x=9(x)及x*=9(x*)，从而有xk+1 k—x=9(p)(g)(x—x*)pk+1 k p! kx-x*k+19(x*)，迭代公式在x*附近是p阶收敛的。故limek+i=limksepk迭代法的收敛阶是对迭代法收敛速度的一种度量p!例4(见p20)例设a,x>0，证明迭代公式x=xk(汽+3a)是计算^万的3阶方法,0 k+1 3x2+ak并计算lima_x^+^。k*(Ja—x)3k证明显然当a,x>0，x>0(k=1,2,…)，0k令9(x)令9(x)=x(x2+3a)3x2+a则9'(x)=…3(x2—a)2(3x2+a)2则Vx>0，可使9'(x)|<1，即迭代收敛。设xTx*，则有kx*=三0 +3a)，解之得x*=0,pa，—fa，取x*=、：'a。贝U3x*2+ax3+3axTOC\o"1-5"\h\zk k_a—x 3x2+a (、；a—x)3 十1lim k^=lim k=lim.. k =limk*G--'a—x)3k*(応a—x)3 k*G-'a—x)3(3x2+a)k*3x2+a4ak k k k k故迭代是3阶收敛。例已知迭代公式例已知迭代公式xk+1皐二局部收敛于方程x=的根x*=1，证k明该迭代公式平方收敛。证法一：迭代函数9(x)x2—3 x2—证法一：迭代函数9(x)= ，经计算9(x)= ，9(x*)=0，2x—4 2(x—2)29"(x)=丄，而9©*)丰0，有定理2-4知，迭代公式平方收敛。

证法二：由于limx=证法二：由于limx=x*=1，则e二x—1。于是

kT8k k kx2—3 (x—1)2 e2e=x—1=k—1=k= k—k+1 k+1 2x—4 2x—4 2x—4k k k1 1门=丰0。2x—4 2k从而2.2.4迭代法的特点•算法逻辑结构简单；•在计算时，中间结果若有扰动，仍不会影响计算结果；•不同的迭代公式在收敛性、收敛速度上有差别。2.3牛顿(Newton)法牛顿法原理牛顿法是把非线性方程f(x)=0线性化的一种近似方法。把f(x)在x点附近展开成泰勒(Taylor)级数011f(x)=f(x)+f'(x)(x—x)+—f〃(x)(x—x)2+…+-Jf(n)(x)(x—x)n+…取2! n!其线性部分，当f(x)鼻0时，得到第1次迭代结果，0x=x—f(x)/f(x)1若广(x)丰0,在x点作线性近似，得到第2次迭代结果11x=x—f(x)/f(x)2111这样，得到牛顿法的一个迭代序列x=x—f(x)/f(x)TOC\o"1-5"\h\zk+1 k k k牛顿法的几何意义f(x)过点(x,f(x))的切线方程为y—f(x)=广(x)(x—x)，kk n n n该切线与x轴的交点是x—f(x)/f'(x)，把它记作x作为下一次迭代点。故k k k k+1牛顿法也叫做切线法。

2.3.3牛顿法的计算步骤步1：选取初值x及精度;0步2：计算f(x)，广(x)，令x=x-f(x)/f'(x)；001000若卜］x一x若卜］x一x—1 0x1<£,令x*二x,计算结束；否则，令1=xi，转第2步。例5p23,参［1］p20例2-8,2-9,2-10牛顿法的收敛性及收敛速度定理2-5牛顿迭代法平方局部收敛定理设x*是方程f(x)二0的单根，且f(x)在x*的某邻域有二阶连续导数，则牛顿法在x*附近局部收敛，且至少是二阶收敛，有ex*-x f"(x*)(参⑹p61)limk+1—lim k+1—kT2e2kkT8x*—x22f'(x*)k问题与思考：1．牛顿法的收敛性与初值x的选取是否有关系？ 有02．当有重根即f(x*)=0时，牛顿法仍收敛吗？ 是3.当x*是方程f(x)=0的m重根时，是否仍平方收敛？x-x*m一1线性收敛，且lim = k*x-x*mk4．收敛速度与得光滑性有关系吗？ 有例6p23定理2-6收敛充分条件若f(x)在区间［a,b］上满足:1)f(a)•f(b)<0;有根2)广(x)丰0;唯一根3)f"(x)不变号；{x}单调有界k4)选取初值xe[a,b]，使f(x)f(x)>0,000自身映射则牛顿法产生的迭代序列单调收敛于方程f(x)二0在该区间上的惟一解。例用牛顿迭代法推导求’万(a>0)的迭代公式，并求收敛的阶。

解方法一：设f(x)二x2-a，则有x=1(x+—)。k+1 2kxka a 1此时，申'(x)=(1—),申"(x)= ,Q(\.：a)二0,申)=丰0,x2 4x3 4ja故该迭代公式为二阶收敛迭代公式。方法二：设f(x)=1——，则有x=1x(3—乂)。x2 k+12ka由于3x2 3x , 由于此时，申'(x)=— ，申"(x)=— ，0(i：a)=0，申"(pa)=TOC\o"1-5"\h\z2a af"(x)=—6a，故取xe(0小万)时，迭代公式二阶收敛。x4 0方法三：设心=(x2-a)2，则有xk+1=4xk+汙，此时ka 1申"(x)=— ，由于申G-'a)=\：a，而0<9"(\a)= <1，4x2 2故该迭代公式仅为线性收敛迭代公式。牛顿法的特点及牛顿下山法牛顿法有以下特点：•收敛速度快，达到平方收敛；•计算量较大，对函数f(x)解析性质要求较高。•具有局部收敛性，即当初值x与x*太远时，收敛速度很慢，甚至不收0敛，仅在x*附近可达到平方收敛；将牛顿迭代公式修改为以下形式7f(x)x=x一九 kk+1 k f'(x)k111其中参数九e(0,1)称为下山因子。用试算的方法选取九(1,1,丄,丄，)，使得22223If(x)|<f(x)k+1 k称满足上述要求的算法为牛顿下山法。2.4弦位法2.4.1弦位法的思想弦位法又称弦截法或割线法。是用差商代替牛顿公式中的微商f(x)；或k者说是用f(x)在点(x,f(x))和(x,f(x))处的割线的零点作为新的迭代点k—1 k—1 k kx=x- k(x-x)k+1 kf(x)-f(x)k k-1k k-12.4.2弦位法的几何意义略2.4.3弦位法的计算步骤略2.4.4弦位法的收敛性及收敛速度定理2-7设x*是方程f(x)=0的单根，且f(x)在x*的某邻域有二阶连续导数，则Vx,xeN(x*,5)，弦位法在x*附近局部收敛，且按阶1.618收敛到x*。012.4.4弦位法的特点•收敛速度夹较快，但比牛顿法慢；•超线性收敛，收敛阶为1.618；无需计算导数，每步只需计算一次函数值；属于多点迭代，而牛顿法和一般迭代法属于单点迭代。2.5迭代法的改善与加速2.5.1一般的加速算法加速算法思想是先求x=9(x)，然后选取合适的数m和n令TOC\o"1-5"\h\zk+1 kx=mx+nxk+1 k+1 k作为下一次迭代点。为选取合适的线性组合系数m,n。由于9(x)连续，且x*=9(x*)，从而x*—x=9(x*)-9(x)=9'(E)(x*—x)k+1 k k用a近似代替上式中的9'点)，立即有x*-xua(x*-x)k+1 k整理得1 _ax*u x-x1+ak+1 1+ak从而得到加速迭代公式\o"CurrentDocument"1 ax= 9(x)-xk+1 1+ak1+ak2.5.2埃特金(Aithen)加速算法埃特金算法的思想是将一般迭代法和弦位法相结合来实现加速迭代算法的收敛速度的。为构造埃特金法加速迭代公式，设x是x二申(x)的一个近似解，首先令kx二p(x)，X二p(x)TOC\o"1-5"\h\zk+l k_k+1 k然后在曲线y二p(x)上，过点P(x,x)和P(x,x)做连线，该直线的两点kk+1 k+1k+1式方程为\o"CurrentDocument"x-x y-x—k+1k+1= k+1\o"CurrentDocument"x-x x-xk+1k k最后考虑到方程x二p(x)的解是曲线y二p(x)和直线y=x的交点P*的横坐标，可用弦PP与直线y=x的交点P代替P*,即用点P的横坐标作为x二p(x)的k+1 k+1一个近似解，其值可通过将上式中的y用x代替并解出x得到xx-x2x二 kk+1 k+1—x-2x+xk k+1k+1用上式进一步可以构造出两种具有加速收敛的迭代公式xx-2x2入(x-x)2TOC\o"1-5"\h\zxu——kk+1 k+——x— k+1 ——k+1 x-2x+x k+1 x-2x +xk k+1 k+1 k k+1 k+1称上式为埃特金算法的迭代公式；xx-2x2 (x-x)2xUkk+1 片1—x— k+1 k入k+1x-2x+xkx-2x+xk k+1 k+1 k k+1 k+1称上式为Steffensen(斯姬芬森)外推迭代公式。实质上，若令屮(x)—x- ，则x—屮(x)k—0,1,2,称为Steffensen迭代公式。p(p(x))-2p(x)+x k+1 k埃特金算法的几何意义略p25图2-7埃特金算法的计算步骤略例8p25，原本发散的迭代公式x—x3-1用埃特金算法是收敛的。k+1 k2.5.4加速算法的收敛性设x*是x—p(x)的精确解，由迭代法收敛性定理知：若p'(x*)在x*的某个邻域上连续，若0<p'(x*)<1，则迭代算法x —p(x)局部收敛;若|p'(x*)—1，k+1 k 1 1则迭代算法可能收敛，也可能不收敛；若|p'(x*)|>1，则迭代算法肯定不收敛。但经过改进后的Aitken算法超线性收敛，Steffensen(斯基芬森)外推算法若p气x)在x*处连续，且p'(x*)丰1，则算法至少有二次收敛性。定理2-8Steffensen迭代法收敛定理设函数屮(x)按上式定义的迭代函数：

⑴若x*是申(x)的不动点，申'(x)在x*处连续，且申'(x)丰1,则x*也是屮(x)的不动点，反之，若x*是屮(x)的不动点，则x*也是申(x)的不动点。(2)若x*是申(x)的不动点，申《x)在x*处连续，且申，(x)丰1,贝USteffensen迭代公式至少是平方收敛。(证明见6p60)2.6代数方程求根当f(x)是多项式时，方程f(x)=0称作代数方程。在牛顿迭代法中，要求f(x),fXx)，设00f(x)=axn+axn-i+•…+ax+aTOC\o"1-5"\h\z0 1 n-1 n=(—((ax+a)x+a)xd—a)x+a0 1 2 n-1 n令b=a,b=adxb(i=1,2,—,n), 则f(x)=b。0 0ii0i-1 0n为求f'(x)，考查f(x)求导，即0f'(x)=[…((ax+a)x+a)xd—a]x+(…((ax+a)x+a)xd—a)0 1 2 n-1 0 1 2 n-1=([…((ax+a)x+a)xd—a]'x+(…((ax+a)x+a)xd—a))x0 1 2 n-2 0 1 2 n-1+(…((ax+a)x+a)xd—a)0 1 2 n-1=(…(ax+a)xd—(…((ax+a)x+a)xd—a)x+0 1 0 1 2 n-2(…((ax+a)x+a)xd—a))x+(…((ax+a)x+a)xd—a)0 1 2 n-1 0 1 2 n-1则f'(x)=(…(ax+a)xd—(…((ax+a)x+a)xd—a)x+0 00 1 0 00 10 20n-2 0(…((ax+a )x +a )xd—a ))x+(…((ax +a)x +a)xd—a )00 10 20 n-1 0 00 10 20 n-1=(…((bx+b)x+b)xd—b)x+b00 10 20 n-20 n-1上述结果用于代数方程f(x)=0的牛顿迭代公式x=x-f(x)/f'(x)kd1 k k k中，f(x),f'(x)的计算公式如下：kkc=b00c=b00<c=b+xc1<i<n-1iiki-1

f'(x)=c

k n-100<b=a+xb1<i<niiki-1f(x)=bkn2.7求方程的m重根设x*是方程f(x)=0的m(>2)重根，贝Vf(x)=