计算方法非线性方程(组)的数值解法ch07ar

1第七章非线性方程(组)的数值解法计算方法——方程求根与二分法——不动点迭代及其加速2本章内容非线性方程求解二分法不动点迭代法及其加速牛顿法、弦截法、抛物线法求根问题的敏感性与多项式的零点非线性方程组的数值求解3本讲内容迭代格式加速算法收敛性非线性方程求解介绍二分法及其收敛性不动点迭代及其加速4非线性方程数值解法考虑方程若f(x)是一次多项式，则称为线性方程；否则称为非线性方程f(x)=0若f(x)=a0+a1x+...+anxn，则称为代数方程,()[,]xRfxCabn=1,2,3,4时有相应的求根公式，n5时不存在求根公式非线性方程可能有(无穷)多个解，求解时必须强调求解区间非线性方程一般没有直接解法，通常都使用迭代算法求解5非线性方程数值解法几个基本概念实根与复根根的重数f(x)=(x–x*)m·g(x)且g(x*)0,则x*为f(x)=0的m重根有根区间：[a,b]上存在f(x)=0的一个实根研究内容：在有根的前提下求出方程的近似根6二分法（对分法）基本思想将有根区间进行对分，找出根所在的小区间，然后再对该小区间对分，依次类推，直到有根区间的长度满足给定的精度为止数学原理：介值定理设f(x)在[a,b]上连续，且f(a)f(b)0，则由介值定理可得，在(a,b)内至少存在一点使得f()=0适用范围求有根区间内的单重实根或奇重实根，即f(a)f(b)0用二分法求根，通常先给出f(x)草图以确定有根区间7二分法算法：(二分法)(1)计算f(a)，f(b)，若f(a)f(b)0，则停止计算(2)对k=1,2,...,maxit2abx计算f(x)，其中若|f(x)|或b-a，停止计算，输出近似解x若f(a)·f(x)0，则令b=x;否则令a=x优点：简单易用，总是收敛缺点：收敛速度慢，不能求复根和偶数重根总结：一般用来计算解的一个粗糙估计8误差分析记a1=a,b1=b,第k步的有根区间为[ak,bk]11224kkkkkkkbababaxxx112kba20()kkakbxx结论：二分法总是收敛的9不动点迭代基本思想构造f(x)=0的一个等价方程：()xx(x)的不动点f(x)=0x=(x)等价变换f(x)的零点10不动点迭代具体过程任取一个迭代初始值x0，计算得到一个迭代序列：x0，x1，x2，...，xn，...1()kkxxk=0,1,2,......几何含义：求曲线y=(x)与直线y=x的交点11xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=(x)y=(x)y=(x)y=(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1x212连续性分析设(x)连续，若收敛，即，则1limlim()limkkkkkkxxxlim*kkxx0kkx*(*)xx(*)0fx即收敛性分析性质：若，则不动点迭代收敛，且x*是f(x)=0的解；否则迭代法发散。lim*kkxx13解的存在唯一性定理：设(x)C[a,b]且满足证明：自学(1)对任意的x[a,b]有(x)[a,b](2)存在常数0L1，使得任意的x,y[a,b]有()()xyLxy则(x)在[a,b]上存在唯一的不动点x*解的存在唯一性14收敛性分析定理：设(x)C[a,b]且满足证明：自学(1)对任意的x[a,b]有(x)[a,b](2)存在常数0L1，使得任意的x,y[a,b]有()()xyLxy则对任意初始值x0[a,b]，不动点迭代xk+1=(xk)收敛，且不动点迭代的收敛性11011kkkkLLxxxxxxLL15收敛性分析不动点迭代的收敛性若(x)C1[a,b]且对任意x[a,b]有|’(x)|L1则上述定理中的结论成立。收敛性结论表明：收敛性与初始值的选取无关全局收敛16举例例：求f(x)=x3–x–1=0在区间[1,2]中的根3()1xx231'()(1)3xx31'()0.2513x(1)1()2x([1,2])x3()1xx2'()3xx'()1x(2)0()7x([1,2])xex71.m17局部收敛定义：设x*是(x)的不动点，若存在x*的某个-邻域U(x*)=[x*-,x*+]，对任意x0U(x*)，不动点迭代xk+1=(xk)产生的点列都收敛到x*，则称该迭代局部收敛。定理：设x*是(x)的不动点，若’(x)在x*的某个邻域内连续，且|’(x*)|1则不动点迭代xk+1=(xk)局部收敛证明：自学局部收敛18收敛速度定义：设迭代xk+1=(xk)收敛到(x)的不动点x*，记ek=xkx*，若1||lim||kpkkeCe其中常数C0，则称该迭代为p阶收敛。(1)当p=1时称为线性收敛，此时C1(2)当p=2时称为二次收敛，或平方收敛(3)当p1时称为超线性收敛二分法是线性收敛的若’(x*)0，则不动点迭代xk+1=(xk)线性收敛19收敛速度定理：设x*是(x)的不动点，若(p)(x)在x*的某邻域内连续，且(1)()'(*)''(*)(*)0,(*)0ppxxxx则迭代xk+1=(xk)是p阶收敛的。证明：自学20举例例：求f(x)=x2-3=0的正根2()3xxx(1)'(*)2311xex72.m*3x23()4xxx(2)3'(*)10.31412x13()2xxx(3)'(*)0x2''(*)03x21Aitken加速Aitken加速10()xx1010*()(*)'()(*)xxxxxx21()xx2121*()(*)'()(*)xxxxxx若’(x)变化不大，则可得：12'()'()0121****xxxxxxxx2100210()*2xxxxxxx1y22Aitken加速01234...xxxxx123...yyy21121()2kkkkkkkxxyxxxx收敛性：1*lim0*kkkyxxx超线性收敛23Steffenson加速21()(),(),2kkkkkkkkkkkyxyxzyxxzyxSteffenson加速将Aitken加速技巧与不动点迭代相结合k=0,1,2,...迭代函数：21(())(),()()2()kkxxxxxxxxx24Steffenson加速定理：若x*是(x)的不动点，则x*是(x)的不动点。反之，若x*是(x)的不动点，且”(x)存在，’(x*)1，则x*是(x)的不动点，且Steffenson加速迭代是二阶收敛的。若原迭代是p阶收敛的，则Steffenson加速后p+1阶收敛原来不收敛的迭代，Steffenson加速可能收敛25举例例：用Steffenson加速法求f(x)=3x2–ex=0在区间[3,4]中的根（取(x)=2ln(x)+ln3）例：用Steffenson加速法求f(x)=x3–x–1=0在区间[1,2]中的根（取(x)=x3–1）ex73.mex74.m26作业教材238页，习题2，4，6