数值计算方法第二章.

数值计算方法第二章非线性方程的数值解法计算机与通信工程学院2本章内容安排在实际中许多方程问题无法求出公式解n次代数方程超越方程需要引进能够达到一定精度要求的求方程近似值的方法0tgxx0sin8889.4tg25.0xx计算机与通信工程学院3本章内容安排2.1初始近似值的搜索2.2二分法2.3迭代法2.4牛顿迭代法2.5弦截法计算机与通信工程学院42.1初始近似值的搜索方程的根逐步扫描法计算机与通信工程学院5方程的根代数方程对于一元非线性方程f(x)=0,如果f(x)为代数多项式则称f(x)=0为代数方程超越方程超越方程包括指数方程、对数方程和三角方程等方程的根0111...axaxaxannnn计算机与通信工程学院6方程的根如果存在x*使f(x*)=0，则称x*是方程的解或根，也称x*是函数f(x)的零点或根重根如果函数f(x)可分解为其中m是大于1的正整数，则称x*是方程f(x)=0的m重根重根的判断条件设函数f(x)有m阶连续导数，方程f(x)=0有m重根x*的充要条件是0*)(),(*)()(xgxgxxxfm计算机与通信工程学院7方程的根例2.1.1：求x=0是方程的几重根？解：因此，x=0是的三重根0*)(,0*)(...*)('*)()()1(xfxfxfxfmm0221)(22xxexfx0)0(,221)(22fxxexfx0)0(',422)('2fxexfx0)0('',44)(''2fexfx08)0(''',8)('''2fexfx0221)(22xxexfx计算机与通信工程学院8方程的根方程求根需要解决的问题根的存在性：方程是否有根，如果有根，有几个根？根的隔离：找出有根区间，把有根区间分成较小的子区间，每个子区间有一个根，将有根区间内的任一点都看成该根的一个初始近似值根的精确化：对已知根的初始近似值，逐步精确化求根的步骤判断根是否存在，若存在，确定根的某个初始近似值计算机与通信工程学院9方程的根将初始近似值逐步加工成满足精度要求的结果有根区间如果方程在区间[a,b]内至少有一个根，则称[a,b]为有根区间隔根区间如果方程在区间[a,b]内恰有一个根，则称[a,b]为隔根区间根的隔离寻找隔根区间[a,b]的步骤，叫做根的隔离计算机与通信工程学院10方程的根定理2.1：设函数f(x)在区间[a,b]上连续，如果f(a)f(b)0，则方程f(x)=0在[a,b]内至少有一实根x*定理2.2：设函数f(x)在区间[a,b]上是单调连续函数，并且f(a)f(b)0，则方程f(x)=0在[a,b]上有且仅有一实根x*计算机与通信工程学院11方程的根寻找有根区间（隔根区间）的方法画图法逐步扫描法abx*f(x)0xhx0计算机与通信工程学院12逐步扫描法实现步骤设单值连续函数f(x)在有根区间[a,b]，从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨每跨一步都检验每步起点x0和终点x0+h的函数值如果那么所求的根x*必在x0与x0+h之间0)()(00hxfxf计算机与通信工程学院13逐步扫描法例2.1.2：考察方程利用逐步扫描法确定一个有根区间解：注意到f(0)0,f(+)0，知f(x)至少有一个正的实根设从x=0出发，取h=0.5为步长向右进行根的扫描因此在区间（1,1.5）内必有实根01)(3xxxfx00.51.01.5f(x)的符号－－－＋计算机与通信工程学院142.2二分法二分法的基本思想首先，假定方程f(x)=0在区间[a,b]内有唯一的实根x*就是将方程根所在的区间平分为两个小区间，判断根属于哪个小区间；把有根的小区间再平分为二，再判断根所在的更小的区间，对分；重复这一过程，最后求出所要的近似值二分法的步骤1．计算f(x)在有解区间[a,b]端点处的函数值f(a)，f(b)2．计算f(x)在区间中点处的值f(x0)计算机与通信工程学院152.2二分法3．判断若f(x0)=0，则即是根，否则检验：（1）若f(x0)与f(a)异号，则知根位于区间[a,x0]，以x0代替b；（2）若f(x0)与f(a)同号，则知根位于区间[x0,b]，x0代替a反复执行步骤2、3，便可得到一系列有根区间：[a,b],[a1,b1],…,[ak,bk],…，其中每个区间都是前一个区间的一半，因此区间长度为20bax)(21ababkkk计算机与通信工程学院162.2二分法二分法的误差估计由于只要有根区间[ak+1,bk+1]的长度小于预先给定的误差，那么就可以取作为所求根x*的第k+1次近似值。其误差估计为)(21kkkbax)(211*abxxkk11*)(21kkkkkababxx计算机与通信工程学院172.2二分法例2.2.1：证明1-x-sinx=0在[0,1]内有一个根，使用二分法求误差不大于的根要二分多少次？证：令f(x)=1-x-sinx，f(x)是连续函数f′(x)=-1-cosx,x∈[0,1]f(x)在[0,1]单调减少又f(0)=10，f(1)=-sin10，可知f(x)在[0,1]有且仅有一个根41021计算机与通信工程学院182.2二分法使用二分法时，误差限为：所以总共需要二分14次)(21*1abxxkk411021201k28.132lg4)01lg(k计算机与通信工程学院192.2二分法例2.2.2：求方程在区间[1,1.5]内的实根，要求准确到小数点后第2位。解：预先估计一下二分的次数：按误差估计式01)(3xxxf61021)(212111*kababxxkkkk计算机与通信工程学院202.2二分法kakbkxkbk-ak01.00001.50001.25000.500011.25001.50001.37500.250021.25001.37501.31250.125031.31251.37501.34380.062541.31251.34381.32820.031351.31251.32821.32040.015761.32041.32821.32430.0078因此x*=1.32计算机与通信工程学院2.2二分法也可以事先不估计二分次数，随着二分过程的进行，随时利用公式来作为二分过程结束的判断条件当二分到第六次时，区间长度为0.0078，区间长度的一半小于误差，所以可以在这一步停止二分，而以x6=1.32作为方程根的近似值21计算机与通信工程学院222.3迭代法迭代法原理迭代法的几何意义迭代过程的收敛性全局收敛性局部收敛性迭代过程的收敛速度迭代的加权法加速计算机与通信工程学院23迭代法原理简单迭代法的基本思想将方程f(x)=0化为一个等价的方程从而构成序列如果(x)连续，迭代序列{xk}收敛于x*，则x*就是方程的解。其中(x)称为迭代函数，xk+1=(xk)称为迭代格式。)(xx,2,1,0)(1kxxkk计算机与通信工程学院24迭代法原理例2.3.1：求方程x3-x-1=0在x=1.5附近的一个根解：将所给方程改写成的形式，假设初值x0=1.5是其根，代入后得到求得的x1不等于x0，再将x1代入，求得x2x2与x1不等，再用x2代入，求得x331xx35721.115.113301xx33086.1135721.113312xx32588.1133086.113323xx计算机与通信工程学院25迭代法原理kkx1kkxx0123456781.51.357211.330861.325881.324941.324761.324731.324721.32472——因此x*=1.32472计算机与通信工程学院26迭代法的几何意义迭代法的几何意义可解释成求方程x=φ(x)的根，在几何上就是求直线y=x与曲线y=φ(x)交点A的横坐标x*计算机与通信工程学院27迭代法的几何意义收敛的情形计算机与通信工程学院28迭代法的几何意义发散的情形计算机与通信工程学院29迭代过程的收敛性例2.3.2：求方程的一个根解：因为f(0)=10f(1)=-70，由定理2.1知方程在[0,1]中必有一实根，现将原方程改为同解方程由此得迭代格式取初始值x0=1，可逐次算得x1=0.4771x2=0.3939…0210)(xxxf210xx)2lg(xx)2lg(1kkxx计算机与通信工程学院30迭代过程的收敛性x6=0.3758x7=0.3758因为x6和x7已趋于一致，所以取x7=0.3758为原方程在[0,1]内的一个根的近似值一个方程的迭代格式不唯一，且迭代也不总是收敛的，如上述方程也可改写成得迭代格式经过验证，该迭代公式不收敛210xx2101kxkx计算机与通信工程学院31全局收敛性定义2.1：对任意初值x0∈[a,b]，如果按照迭代格式xk+1=φ(xk)生成的序列{xk}∈[a,b]，则该迭代格式映内。例2.3.3：求方程x=e-x在0.5附近的根解：将方程改写为x=-lnx，而lnx的定义域为（0，＋∞），当取x0=0.5时，进行迭代可得x1=0.693,x2=0.3666,x3=1.0034,x4=-0.0034。可见x4已经超过了lnx的定义域，迭代不能继续，此格式不映内。不仅考虑映内性，为使迭代法有效，还必须保证它的收敛性计算机与通信工程学院32计算机与通信工程学院33全局收敛性定理2.3：设函数φ(x)在[a,b]上具有连续的一阶导数，且满足（1）当x[a,b]时，(x)[a,b]（2）当任意x[a,b]，存在0L1，使则方程x=(x)在[a,b]上有唯一的根x*,且对任意初值x0[a,b]时，迭代序列xk+1=φ(xk)(k=0,1,…)收敛于x*。1)('Lx计算机与通信工程学院34全局收敛性证明：先证明根的唯一性构造连续函数，根据条件(1)可以得到由函数的连续性定理可知，存在x*∈[a,b]，使，也就是存在解，即假设有两个解，则根据中值定理有从而有xxx)()(0)()(aaa0)()(bbb0**)(*)(xxx*)(*xx],[*,baxx)(*),(*xxxx],[),*)((')(*)(*baxxxxxx0)]('1)[*(xx计算机与通信工程学院35全局收敛性根据条件(2)有所以，即，也就是解唯一。设x*是方程的根，即x*=(x*)，由拉格朗日定理因为0L1，由知即xk+1=(xk)收敛))((')()(**1*kkkxxxxxx0*11*2***1*)(')()(xxLxxLxxLxxxxxxkkkkkk0lim1kkL)(01*kxxk1|)('|x0*xxxx*计算机与通信工程学院36全局收敛性定理2.4：设在区间[a,b]方程x=(x)有根x*，并且对有|φ′(x)|≥1，则对于任意x0(≠x*)∈[a,b],迭代过程xk+1=(xk)一定发散。推论2.1：在定理3的条件下，有误差估计式],[bax11*kkkxxLLxx011*xxLLxxkk计算机与通信工程学院37全局收敛性证：即已知L1，因此有只要充分小，就可以保证足够小因此可用条件来控制迭代过程的结束11***kkkkkxxxxLxxLxx)*(1kkkxxxxL1*)1(kkkxxLxxL11*kkkxxL