第七章非线性方程与方程组的数值解法

哈尔滨工程大学数值逼近与数值代数第9章非线性方程与方程组的数值解法方程求根与二分法不动点迭代法及其收敛性迭代收敛的加速方法牛顿法弦解法与抛物线法哈尔滨工程大学数值逼近与数值代数1．根的存在性。方程有没有根？如果有根，有几个根？定理1：设函数f(x)在区间[a,b]上连续，如果f(a)f(b)0，则方程f(x)=0在[a,b]内至少有一实根x*。2．这些根大致在哪里？如何把根隔离开来？3．根的精确化第一节根的搜索哈尔滨工程大学数值逼近与数值代数abx*f(x)0x1．画出f(x)的略图，从而看出曲线与x轴交点的位置。2．从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若0)()(00hxfxf那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。hx09.1.1逐步搜索法哈尔滨工程大学数值逼近与数值代数开始读入a,hax0f(x0)y0x0+hx0f(x0)y00打印结束否是继续扫描哈尔滨工程大学数值逼近与数值代数例1：考察方程01)(3xxxfx00.51.01.5f(x)的符号－－－＋哈尔滨工程大学数值逼近与数值代数abx1x2ab11εxxkk2)(εxf或不能保证x的精度x*2xx*9.1.2二分法哈尔滨工程大学数值逼近与数值代数执行步骤1．计算f(x)在有解区间[a,b]端点处的值，f(a)，f(b)。2．计算f(x)在区间中点处的值f(x1)。3．判断若f(x1)=0，则x1即是根，否则检验：（1）若f(x1)与f(a)异号，则知解位于区间[a,x1]，b1=x1,a1=a;（2）若f(x1)与f(a)同号，则知解位于区间[x1,b]，a1=x1,b1=b。反复执行步骤2、3，便可得到一系列有根区间：(a,b),(a1,b1),…,(ak,bk),…哈尔滨工程大学数值逼近与数值代数4、当11kkab时)(211kkkbax5、则即为根的近似①简单;②对f(x)要求不高(只要连续即可).①无法求复根及偶重根②收敛慢哈尔滨工程大学数值逼近与数值代数定义f(x)f(a)f(b)0f(a)f(b)=0f(a)=0打印b,k打印a,k结束是是是否否否m=(a+b)/2|a-b|f(a)f(b)0打印m,ka=mb=m结束k=K+1是是否否输入,,bak=0哈尔滨工程大学数值逼近与数值代数例2：求方程在[1，1.5]内的实根，要求精确到小数点后两位。01)(3xxxfkakbkxkf(xk)的符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381.3281+51.31251.32811.3203-61.32031.32811.3242-哈尔滨工程大学数值逼近与数值代数§2迭代法1．简单迭代法x1=0.4771x2=0.3939…x6=0.3758x7=0.37582．迭代过程的收敛性f(x)=0x=g(x)等价变换例3：求方程0210)(xxxf的一个根210xx)2lg(xx迭代格式)2lg(1kkxx哈尔滨工程大学数值逼近与数值代数xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1哈尔滨工程大学数值逼近与数值代数定理2：如果满足下列条件（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*。'()1xL(2.1))(x哈尔滨工程大学数值逼近与数值代数))((')()(**1*kkkxxxxxx0*11*2***1*)(')()(xxLxxLxxLxxxxxxkkkkkk证明：设x*是方程的根，即x*=(x*)，由拉格朗日定理其中在x*与xk之间0lim1kkL*10()kxxk*limxxkk因为0L1，由即xk+1=(xk)收敛证完哈尔滨工程大学数值逼近与数值代数3．迭代法的结束条件1111)(')()(kkkkkkkkxxLxxxxxx11kkrrkrkxxLxx1111112112211)(kkpkkkkpkkpkkpkpkpkpkkpkpkpkpkpkkpkxxLLxxLxxLxxLxxxxxxxxxxxxxx*1()1kkkLxxxxpL哈尔滨工程大学数值逼近与数值代数例4：求方程在[0,0.5]内的根，精确到10-5。0133xxx1=(0.25)=0.3385416x2=(x1)=0.3462668x3=(x2)=0.3471725x4=(x3)=0.3472814x5=(x4)=0.3472945x6=(x5)=0.3472961x7=(x6)=0.3472963只要充分小，就可以保证足够小，1kkxx(2.2)1kkxxkxx*因此可以用来进行保证。)()1(313xxx0)('2xx125.05.0)('max2xL满足收敛条件，取初值为0.25，用公式（2.3）算得哈尔滨工程大学数值逼近与数值代数4．迭代过程的收敛速度设由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得Cxxxxpkkk*1*lim（C为非零常数）定义：则称序列{xk}收敛于x*的收敛速度是p阶的，或称该方法具有p阶敛速。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1p2时，称方法为超线性收敛。哈尔滨工程大学数值逼近与数值代数kkkxxxxxx**1*)(')()(0)(')('limlim**1*xxxxxkkkk在上述定理中，若’(x)连续，且’(x*)0，则迭代格式xk+1=(xk)必为线性收敛。因为由如果’(x*)=0，则收敛速度就不止是线性的了。哈尔滨工程大学数值逼近与数值代数§3牛顿法一、牛顿法的迭代公式x*x0x1x2xyf(x)))((')(kkkxxxfxfy其几何意义很明显，点的切线方程为：))(,(kkxfx哈尔滨工程大学数值逼近与数值代数原理：将非线性方程线性化——Taylor展开取x0x*，将f(x)在x0做一阶Taylor展开:20000)(!2)())(()()(xxfxxxfxfxf，在x0和x之间。将(x*x0)2看成高阶小量，则有：)*)(()(*)(0000xxxfxfxf)()(*000xfxfxx只要fC1，每一步迭代都有f'(xk)0，而且，*limxxkk，则x*就是f(x)的根。)()(1kkkkxfxfxx(2.3)哈尔滨工程大学数值逼近与数值代数二、牛顿法的收敛性定理3：设f(x)在[a,b]上满足下列条件：（1）f(a)f(b)0；（2）f'(xk)0；（3）f(x)存在且不变号；（4）取x0[a,b]，使得f(x)f(x0)0则由（2.3）确定的牛顿迭代序列{xk}收敛于f(x)在[a,b]上的唯一根x*。哈尔滨工程大学数值逼近与数值代数哈尔滨工程大学数值逼近与数值代数注：Newton法的收敛性依赖于x0的选取。x*x0x0x0哈尔滨工程大学数值逼近与数值代数1、单点弦截法：牛顿法一步要计算f和f’，相当于2个函数值。现用f的值近似f’:x0x1切线割线切线斜率割线斜率00)()()(xxxfxfxfkkk)()()()(001xxxfxfxfxxkkkkkx2哈尔滨工程大学数值逼近与数值代数2、双点弦截法：切线斜率割线斜率11)()()(kkkkkxxxfxfxf)()())((111kkkkkkkxfxfxxxfxx需要2个初值x0和x1。x0x1x2