计算方法第2章f(x)=0求根

第二章非线性方程求根1．根的存在性。方程有没有根？如果有根，有几个根？定理1：设函数f(x)在区间[a,b]上连续，如果f(a)

f(b)<0，

则方程f(x)=0在[a,b]内至少有一实根x*。

2．这些根大致在哪里？如何把根隔离开来？3．根的精确化abx*f(x)1．画出f(x)的略图，从而看出曲线与x轴交点的位置。2．从左端点x=a出发，按某个预先选定的步长h一步一步地向右跨，每跨一步都检验每步起点x0和终点x0+h的函数值，若那么所求的根x*必在x0与x0+h之间，这里可取x0或x0+h作为根的初始近似。

开始读入a,ha

x0f(x0)

y0x0+h

x0f(x0)

y0>0打印结束否是继续扫描

例1：考察方程x00.51.01.5f(x)的符号－－－＋可见，含根区间为

[1,1.5]abx1x2ab或不能保证

x

的精度x*2xx*§1二分法

执行步骤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、当时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是是否否输入k=0例2：求解方程：kakbkxkf(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．简单迭代法简单迭代法的基本思想第一步:求出与方程f(x)=0等价的方程x=g(x)第二步:由迭代格式x0,xn+1=g(xn)n=0,1,2,…产生一收敛的数列{xn}设X*是{xn}的极限,若g(x)是连续的,再由第一步可推出X*是f(x)=0的解.xn+1是f(x)=0解的第n+1次近似;x0是解的初始近似;g(x)是迭代函数;xn+1=g(xn)是迭代格式.例:求方程的解解:与原方程等价的方程为:取x0=1.5得迭代格式计算得:x(1)=1.5;fork=2:10x(k)=(1+x(k-1))^(1/3);endXx=1.50001.35721.33091.32591.32491.32481.32471.32471.32471.3247取x0=1.5得迭代格式计算得:x(1)=1.5;fork=2:4x(k)=x(k-1)^3-1;endXx=1.0e+003*0.00150.00240.01241.9040解法2:与原方程等价的方程为:发散。2.迭代过程的收敛性简单迭代法的两个基本问题:1.如何选取初值和迭代公式.2.如何停止迭代过程xyy=xxyy=xxyy=xxyy=xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0x1p1x0p0x1p1x0p0x1p1x0p0x1p1定理2.1：如果

g(x)满足下列条件 （1）当x[a,b]时，g(x)[a,b] （2）当任意x[a,b]时，存在0<L<1，使

则方程x=g

(x)在[a,b]上有唯一的根x*,且对任意初值

x0[a,b]时，迭代序列xk+1=g

(xk)

(k=0,1,…)收敛于x*。(2.1)设另有f(x1)=0,那么根据微分中值定理有x1-x*=g(x1)-g(x*)=g’(x2)(x1-x*)证:先证解的存在性作辅助函数f(x)=x-g(x),由条件知f(x)在[a,b]上连续,且f(a)f(b)<0;由连续函数的零点定理,至少存在一x*[a,b],使f(x*)=0.再证解的唯一性即有(x1-x*)(1-g’(x2))=0根据条件有x1-x*=0,即x1=x*最后证迭代数列收敛.首先,由于xn-x*=g(xn-1)-g(x*)=g’(yn-1)(xn-1-x*)<L(xn-1-x*)<L2(xn-2-x*)<…<Ln(x0-x*)不等式两边取极限得xn→

x*.定理2.1中的条件要求对任意的x[a,b]，均有不等式2.1成立.这时对任意的x0[a,b],迭代数列收敛.这种迭代格式被称为全局收敛.定义2.1设是方程x=g(x)的解,如果存在使得迭代对于任意的均收敛,则称这种迭代格式为局部收敛.定理2.2：设x*是方程x=

g(x)的解,如果当xU(x*,δ)

时，有

则对任意初值x0U(x*,δ)，迭代序列xk+1=g

(xk)

(k=0,1,…)收敛于x*。如果当xU(x*,δ)

时，有则对任意初值x0U(x*,δ)，迭代序列xk+1=g

(xk)

(k=0,1,…)发散。定理证明和例题名见教材P23--24,(2.1)关于如何停止迭代过程,我们有下面的定理定理2.3设x*是x=g(x)的解,如果对于任意的均有,则有误差估计式3．迭代法的结束条件证明:首先有再由微分中值定理有所以有欲使绝对误差限为1,只要就够了.故只要就够至此,我们可以依迭代法编写程序进行计算了.框图和例4参见P26--27

4．迭代过程的收敛速度

设由某方法确定的序列{xk}收敛于方程的根x*，如果存在正实数p，使得

（C为非零常数）定义：则称序列{xk}收敛于x*的收敛速度是p阶的，或称该方法具有p阶敛速。当p=1时，称该方法为线性（一次）收敛；当p=2时，称方法为平方（二次）收敛；当1<p<2时，称方法为超线性收敛。

例5:写出用迭代法求方程的解的收敛的迭代格式,试问该方法是几阶收敛?解;因为f(0)=-1;f(1)=e+8>0;所以在[0,1]方程至少有一个解.又方程的等价形式为令g(x)=1/5-ex/10,则g’(x)=-ex/10于是,即解的迭代格式为由于所以取极限得根据定义知:此迭代格式为线性收敛.MATLAB程序:x0=0;k=0;dx=1;whiledx>epsx=1/5-exp(x0)/10;dx=abs(x-x0);x0=x;k=k+1;endx,k定理2.4：对于迭代，如果在所求根的邻近连续，并且(*)则该迭代过程在点邻近是P阶收敛的。证明：由于。据定理2.2，可知迭代具有局部收敛性。再将在根处展开，利用条件(*)，则有注意到，由上式得11因此对迭代误差有:。这表明迭代过程确实为P阶收敛，证毕。上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数.如果当时,则该迭代过程只能是线性收敛。12§3牛顿法一、牛顿法的迭代公式x*x0x1x2xyf(x)原理：将非线性方程线性化求f(x)在x0处的切线方程:只要f

C1，每一步迭代都有f’(xk)0，而且，，则

x*就是f(x)的根。(2.3)令:求f(x)在x1处的切线方程:一般地二、牛顿法收敛的充分条件定理2.5：设f(x)在[a,b]上满足下列条件： （1）f(a)

f(b)<0； （2）f’(x)0； （3）f(x)存在且不变号； （4）取x0[a,b]，使得f(x)f(x0)>0则由（2.3）确定的牛顿迭代序列{xk}收敛于f(x)在[a,b]上的唯一根x*。注：Newton法的收敛性依赖于x0的选取。x*x0x0x0例6:设C为正实数,导出用牛顿法求的公式,并证明迭代序列的误差满足解:设,则于是有由于所以在内有一正根.又在内,根据定理2.5得牛顿迭代格式为:因为所以注意:由上式可得:即该迭代格式是2阶收敛的.3．牛顿法收敛的阶定理2.6对于方程f(x)=0,设f(x)充分光滑.x*是f(x)=0在[a,b]内的根.（1）x*是单根,则牛顿迭代格式是2阶收敛的;（2）x*是m重根,则牛顿迭代格式是线性收敛的.此定理的证明涉及到定理2.4,请参见P35.例7求方程的解解:设则f(0)=1,f(2)=-1注:x0=3or8在[0,2]内,f’(x)<0,f’’(x)>0,f(0)f’’(0)>0,所以迭代