计算方法第二章

第2章一元非线性方程的解法2.1初始近似根的确定2.2二分法2.3迭代法的一般知识2.4牛顿迭代法（切线法）2.5弦截法（割线法）2.6埃特金（Aitken）迭代法}引言本章讨论：求一元非线性方程f(x)=0的根的近似值。引言例如e-x-x=0,x8-x3+5x-3=0,x-sinx=0,等等求根的大致步骤：(1)判定根的存在性。(2)确定根的初始近似值(初始近似根)。(3)根的精确化。如果f(x*)=f′(x*)=f″(x*)=……=f(m-1)(x*)=0,但f(m)(x*)≠0,其中m是正整数，则称x*为方程f(x)=0的m重根-------函数f(x)的m重零点。}如果f(x*)=0,则x*是方程f(x)=0的根,也称它是函数f(x)的零点。方程的1重根称为单根，这时f(x*)=0而f′(x*)≠0。定理如果函数f(x)在区间[a,b]上连续，严格单调，且f(a)f(b)0，则在(a,b)内方程有且仅有一个实根。ab0x*yxf(x)假设f(x)在某区间(a,b)内有且仅有一个实根x*,若b–a较小，则可在(a,b)上任取一点x0作为初始近似根。一般情形，也可用逐步扫描法等。2.1初始近似根的确定}}例01)(3xxxf由于f(0)=-10，f(∞)0，故方程至少有一正实根。设从x=0出发，取h=0.5为步长向右扫描，得x00.51.01.5f(x)―――+)5.11(013)(2xxxf所以f(x)在区间[1,1.5]上单调连续，因而在(1,1.5)内有且仅有一个实根，故可在[1,1.5]上任取一点做初始近似根。可见在（1，1.5）内有根。}(1)x0←a;(2)若f(x0)f(x0+h)≤0则结束；否则做下步。(3)x0←x0+h，转(2)（其中h为预选的步长）求初始近似根的逐步扫描法：（设(a,b)内有根）二分法的基本思想和计算过程近似根的误差估计二分法的计算流程二分法的例2.2二分法}二分法的基本思想将含方程根的区间平分为两个小区间，然后判断根在哪个小区间，舍去无根的区间，而把有根的区间再一分为二，再判断根属于哪个更小的区间，如此周而复始，直到求出满足精度要求的近似根。条件：函数f(x)在[a,b]上连续，严格单调，且f(a)f(b)0，这时方程在区间内有且仅有一个实根x*。}二分法的基本思想和计算过程}具体计算过程第1次二分，取中点)(210bax若f(a)f(x0)0，则x*∈(a,x0)，令a1=a,b1=x0；令a1=x0,b1=b。新的有根区间为(a1,b1)，长度是原来的一半。}否则x*∈(x0,b)，xy0)(xfab0x1a1bx*xy0)(xfb1a1ba0xx*第2次二分，取中点)(21111bax若f(a1)f(x1)0，则x*∈(a1,x1)，令a2=a1,b2=x1；否则令a2=x1,b2=b1。新的有根区间为(a2,b2)。}xy0)(xfb1a1ba0x1x2a2b如此反复，有),(),(),(),(),(221100kkbababababa)(21)(2111abababkkkkk）（k0)(21kkkbax∈(ak,bk),k=0,1,2,…..kkkbxa*limlimlimxbxakkkkkk}近似根xk的误差估计x*lm|—————|—————|akxkbk)(21||kkkabxx11kkab)(211abk}由此得二分过程的结束原则：先给定精度要求ε(绝对误差限)，（1）当|bk+1–ak+1|ε时结束二分计算，取x*≈xk；（2）事先由ε估计出二分的最小次数k+1，取x*≈xk1*2kkabxx由2lnln)ln(1abk，得abk12}二分法的计算流程0)(xyf)(afy2/)(baxxbxa,,ba输入ab开始结束x输出TTFF}例求方程01)(3xxxf要求用二分法，取四位小数计算，精确到10-2。解有由,21*kkabxxa=1,b=1.5,,1025.021k21105.02k得k+1=7满足要求，二分7次计算到x6即可。x0=)5.11(21=1.25,f(1)=-10,f(1.5)0.f(1.25)0,f(1)f(1.25)0,得有根区间[1.25,1.5];,375.1)5.125.1(21x1=f(1.375)0,f(1)f(1.375)0,得有根区间[1.25,1.375];在区间(1,1.5)内的根。}如此继续，计算结果见列表：kakbkxkf(xk)的符号011.51.25－11.251.51.375＋21.251.3751.3125－31.31251.3751.3438＋41.31251.34381.3282＋51.31251.32821.3204－61.32041.32821.3243－得x6=1.3243,所以根x*≈1.32}2.3.1迭代法的基本思想及几何意义2.3.2迭代法的收敛条件及误差估计式2.3迭代法的一般知识}}1.迭代法的基本思想2.3.1迭代法的基本思想及几何意义2.迭代法的几何意义方程f(x)=0化为等价形式的方程x=g(x)，若*limxxkk当g(x)(称为迭代函数）连续，，则由1limkkx)(limkkxg得)(**xgx，等价地有f(x*)=0,故x*即为方程的根。实际计算到|xk–xk-1|ε（ε是预定的精度），取x*≈xk。1、迭代法的基本思想：取初始近似根x0,迭代计算x1=g(x0),x2=g(x1),……..得到迭代序列{xk},构造迭代公式xk+1=g(xk),k=0,1,2,……例f(x)=xex-1=0,可化为等价形式x=e–x迭代公式xk+1=e–xk迭代法也称逐次逼近法。}迭代公式收敛（发散）指迭代序列{xk}收敛（发散）。}求方程f(x)=x–10x+2=0的一个根，取4位有效数字计算。问题：迭代公式是否一定收敛？因f(0)=10,f(1)=-70,所以方程在（0，1）中有根。方程改写为两种等价形式：看下例：解对应的迭代公式分别为)2lg()()1(1xxgx210)()2(2xxgx.210)2();2lg()1(11kxkkkxxx10x=x+2x=lg(x+2)})2lg(1kkxx用迭代公式（1）x1=lg3=0.4771,x2=lg(x1+2)=0.3939,….,x6=0.3758,x7=lg(x6+2)=0.3758,…用迭代公式（2）x1=10-2=8,x2=108-2≈108,x3=10108-2≈10108，……x6、x7重合，所以迭代公式（1）是收敛的，x*≈0.3758。迭代公式（2）发散。2101kxkx取x0=1,算得,x0=1,算得2.迭代法的几何意义问题：迭代函数g(x)满足什么条件时，迭代序列才收敛?}x1=g(x0)x2=g(x1)2.3.2迭代法的收敛条件及误差估计式定理2.1设方程x=g(x)在[a,b]上有一阶导数，如果(1)当x∈[a,b]时g(x)∈[a,b];(2)存在正数q1，使对任意x∈[a,b]都有|g′(x)|≤q1则方程x=g(x)在[a,b]上有惟一的根x*；且对于[a,b]上任意初始近似根x0,迭代公式xk+1=g(xk)均收敛于方程的根x*;还有误差估计式011*11xxqqxxqqxxkkkk}证明记f(x)=x-g(x),由条件（1）有a≤g(a)、g(b)≤b,于是f(a)≤0,f(b)≥0，由于f(x)是连续函数，故必存在x*∈[a,b]使f(x*)=0.于是x*为方程x=g(x)的根。先证根的存在性。}其次，证根的惟一性。设y*也是方程的根，则x*=g(x*),y*=g(y*),|x*-y*|=|g(x*)–g(y*)|=|g′(ξ)(x*-y*)|≤q|x*-y*|由已知条件|g′(x)|≤q1故必有x*=y*,所以方程在[a,b]的根是惟一的。微分中值定理,ξ在x*,y*之间再证迭代公式收敛。由x0∈[a,b]知xk∈[a,b]，k=0,1,2,……|xk+1-x*|=|g(xk)–g(x*)|=|g′(ξ)(xk-x*)|≤q|xk-x*|≤q2|xk-1-x*||xk-x*|≤q|xk-1-x*|≤q3|xk-2-x*|≤……≤qk+1|x0-x*|→0（k→∞）所以，对[a,b]上任取的x0,迭代公式xk+1=g(xk)都收敛于x*。0q1,qk+1→0*limxxkk误差公式的证明从略。}|xk-1-x*|≤q|xk-2-x*|}}推论设在区间[a,b]上方程x=g(x)有根x*,且g(x)有连续的一阶导数。如果有正数q1,使得对任意x∈[a,b]都有|g′(x)|≤q1，则存在x*的某个邻域，只要x0属于此邻域，迭代公式xk+1=g(xk)必收敛于x*。（也称迭代公式有局部收敛性）}|g′(x)|≤q1,|x-x*|δ，由中值定理得|g(x)-x*|=|g(x)-g(x*)|=|g′(ξ)(x-x*)|≤q|x-x*|δ，于是g(x)∈(x*-δ,x*+δ)，这说明在该邻域内定理的条件（1）也成立。所以结论成立。证明存在x*的邻域(x*-δ,x*+δ)[a,b],当x∈(x*-δ,x*+δ)时，x*-δx*+δx*ab定理设在区间[a,b]上方程x=g(x)有根x*,且对一切x∈[a,b]都有|g′(x)|≥1，则对于该区间上任意x0(≠x*),迭代公式xk+1=g(xk)一定发散。证明],[baxk时，且*0xx*1*|)(|xxgxxkk0......*0*1xxxxk*xxk不可能收敛于0。}}}迭代法的计算步骤（1）确定方程f(x)=0的一个等价形式x=g(x),要求在某个含根区间[a,b]内满足|g′(x)|≤q1。(2)构造迭代公式xk+1=g(xk)，选取初始近似根x0,进行迭代计算。(3)当|xk+1–xk|ε（ε是预定的精度）时停止计算，取x*≈xk+1。}迭代法的计算框图开始输入x0,xgx10()||xx10xx01输出x1结束FT}例求方程x=e–x在x=0.5附近的一个根，按5位小数计算，结果的精度要求为ε=10–3.解方程等价于f(x)=x–e–x=0.由于f(0.5)0,f(0.6)0,故x*∈(0.5,0.6),令g(x)=e–x,在(0.5,0.6)内,g(x)的一阶导数连续，且有161.0|)(||)(|5.0eeexgxx所以用迭代公式xk+1=e–xk进行计算是收敛的。根据定理2.1的推论}迭代结果:0123450.50.606530.545240.579700.560070.571170.10653－0.061290.03446－0.019630.011106789100.564860.568440.566410.567560.56691－0.006310.00358－0.002030.00115－0.00065kxkxk–xk-1xk–xk-1kxk|x10-x9|=0.00065ε，}故x*≈x10≈0.567xk+1=e–xkx0=0.5,x2=e–x1=0.54524,…….x1=e–x0=0.60653,例方程f(x)=x3-2x-5=0在(1.5,2.5)内有一实根，分别取3152)(xxx)5(21)(32xxx作为迭代函数，试判断对应的迭代公式是否收敛，并用一个收敛的迭代公式求方程的根，精度要求为ε=10-4。解(1),2)5.1(1.....15443.210)5.2(31时，当5.25.1x)(1x，故5.2)(5.11x单调，且321)52(132)(xx614132)5