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

1、1根的存在性。方程有没有根？如果有根，有几个根？根的存在性。方程有没有根？如果有根，有几个根？定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0打打 印印结结 束束否否是是继续扫描继续扫描例例1 1：考察方程：考察方程01)(3xxxfx00.51.01.5f (x) 的符号的符号可见，含根区间为可见，含根区间为 1,1.5abx1x2ab11xxkk 2)(xf 或或不能保证不能保证 x 的精的精度度x* 2xx*执行步骤执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f

2、(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时时)(211kkkbax5、则、则即为根的近似即为根的近似简单简单; 对对f (x)

3、要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 定义定义f (x)f (a) f (b)0f (a) f (b)=0f (a) =0打印打印b, k打印打印a, k结束结束是是是是是是否否否否否否m=(a+b)/2|a-b|0打印打印m, ka=mb=m结束结束k=K+1是是是是否否否否输入输入 ,bak = 0例例2： 求解方程：求解方程：01)(3xxxfkakbkxkf (xk)的符号的符号011.51.25-11.251.51.375+21.251.3751.3125-31.31251.3751.3438+41.31251.34381

4、.3281+51.31251.32811.3203-61.32031.32811.3242-1 1简单迭代法简单迭代法简单迭代法的基本思想简单迭代法的基本思想第一步第一步: :求出与方程求出与方程f(x)=0f(x)=0等价的方程等价的方程x=g(x)x=g(x)第二步第二步: :由迭代格式由迭代格式x0,xx0,xn+1n+1=g(x=g(xn n)n=0,1,2,)n=0,1,2,产生一收敛的数列产生一收敛的数列xxn n 设设X X* *是是xxn n 的极限的极限, ,若若g(x)g(x)是连续的是连续的, ,再由再由第一步可推出第一步可推出X X* *是是f(x)=0f(x)=0的解

5、的解. .x xn+1n+1是是f(x)=0f(x)=0解的第解的第n+1n+1次近似次近似; x; x0 0是解的初始近似是解的初始近似; ;g(x)g(x)是迭代函数是迭代函数; x; xn+1n+1=g(x=g(xn n) )是迭代格式是迭代格式. .例:求方程 的解 013 xx解解: :与原方程等价的方程为与原方程等价的方程为: :31xx0,1,2n131nnxx取取 x0=1.5得迭代格式得迭代格式计算得: x(1)=1.5; for k=2:10 x(k)=(1+x(k-1)(1/3); endXx = 1.5000 1.3572 1.3309 1.3259 1.3249 1.

6、3248 1.3247 1.3247 1.3247 1.324713 xx取 x0=1.5得迭代格式0,1,2n131nnxx计算得: x(1)=1.5; for k=2:4 x(k)=x(k-1)3-1; endXx = 1.0e+003 * 0.0015 0.0024 0.0124 1.9040解法解法2:2:与原方程等价的方程为与原方程等价的方程为: :发散。发散。2.迭代过程的收敛性迭代过程的收敛性简单迭代法的两个基本问题:1.如何选取初值和迭代公式.2.如何停止迭代过程xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(

7、x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p1定理定理2.1：如果：如果 g(x)满足下列条件满足下列条件（1 1）当）当x a, b时，时，g(x) a, b（2 2）当任意）当任意x a, b时时，存在，存在0 L 1，使，使 则方程则方程x = g (x)在在a, b上有唯一的根上有唯一的根x*, ,且对任意初值且对任意初值 x0 a, b时，迭代序列时，迭代序列xk+1=g (xk) (k = 0, 1, )收敛于收敛于x*。1)( Lxg(2.1)设另有f(x1)=0,那么根据微分中值定理有x1- x x* *=g(=g(x1)-g(x-g(x* *

8、)=g()=g(x2)(x1- x x* *) )证:先证解的存在性作辅助函数f (x)=x - g (x),由条件知 f (x)在a, b上连续,且f(a)f(b)0;由连续函数的零点定理,至少存在一x* a, b, 使f (x*)=0.再证解的唯一性即有 (x1- x x* *)(1- g()(1- g(x2)=0根据条件有x1- x x* *=0,=0,即即x1= x x* *最后证迭代数列收敛最后证迭代数列收敛. .首先首先, ,由于由于xn- x x* *=g(=g(xn-1)-g(x x* *)=g()=g(yn-1) (xn-1- x x* *) )LL(xn-1- x x* *

9、)L)L2 2(xn-2- x x* *)L)Ln n(x0- x x* *) )不等式两边取极限得不等式两边取极限得xn x x* *. .定理2.1中的条件要求对任意的xa, b，均有不等式2.1成立.这时对任意的x0a, b,迭代数列收敛.这种迭代格式被称为全局收敛.*x),(*0 xUx 定义2.1设 是方程x=g(x)的解,如果存在 使得迭代对于任意的 均收敛, 则称这种迭代格式为局部收敛局部收敛.定理定理2.2：设：设x x* *是方程是方程x=x= g(x)的解的解, ,如果当如果当x U(x*,) 时，有时，有 则对任意初值则对任意初值x0 U(x*,)，迭代序列，迭代序列xk

10、+1=g (xk) (k = 0, 1, )收敛于收敛于x*。 如果当如果当x U(x*,) 时，有时，有 则对任意初值则对任意初值x0 U(x*,)，迭代序列，迭代序列xk+1=g (xk) (k = 0, 1, )发散。发散。定理证明和例题名见教材定理证明和例题名见教材P23-24, P23-24, 1)( Lxg(2.1)1)( Mxg关于如何停止迭代过程,我们有下面的定理定理定理2.3设x*是x=g(x)的解,如果对于任意的 均有 ,则有误差估计式3迭代法的结束条件迭代法的结束条件),(*xUx1)( Lxg*111nnnxxxxL证明:首先有再由微分中值定理有所以有nnnnxxxxx

11、x11*nnnnxxLxxgxgxgxx*1*)( )()(*111nnnxxxxL欲使绝对误差限为 1,只要就够了.故只要就够至此,我们可以依迭代法编写程序进行计算了.框图和例4参见P26-27*111()1nnnxxxxL11)1 (Lxxnn4 4迭代过程的收敛速度迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，如果存在正实数如果存在正实数p，使得，使得Cxxxxpkkk*1*lim（C C为非零常数）为非零常数）定义：定义：则称序列则称序列xk收敛于收敛于x*的收敛速度是的收敛速度是p阶的，或称该方法阶的，或称该方法具有具有p 阶敛速。

12、当阶敛速。当p = 1时，称该方法为线性（一次）收敛；时，称该方法为线性（一次）收敛；当当p = 2时，称方法为平方（二次）收敛；当时，称方法为平方（二次）收敛；当1 p0; 所以在0,1方程至少有一个解. 又方程的等价形式为 令g(x)=1/5-ex/10,则g(x)=- ex/10 于是, 即解的迭代格式为( )102xf xex1510 xex x0,1, g(x)11010 xee 均有01011510nxnxxe由于所以取极限得根据定义知:此迭代格式为线性收敛.*111()()1010nnxxnnxxeeexx *1*110nnnxxexx *1*1lim10 xnnnxxexxMA

13、TLAB程序: x0=0;k=0;dx=1;while dxepsx=1/5-exp(x0)/10; dx=abs(x-x0); x0=x; k=k+1;end x,k11定理2.4：对于迭代，如果在所求根的邻近连续，并且(*)则该迭代过程在点邻近是P阶收敛的。证明：由于。据定理2.2，可知迭代具有局部收敛性。再将在根处展开，利用条件(*)，则有注意到，由上式得1()kkxg x+=( )( )pgx*x*( 1)*( )( )( ) 0pg xg xgx- =LL()*()0pgx*x( )0g x=1()kkxg x+=()kg x( )*( )()()!pkgg xg xpz=+*()p

14、kxx-1()kkg xx+=*()g xx=( )*1( )()!ppkkgxxxxpz+-=-*x12因此对迭代误差有:。这表明迭代过程确实为P阶收敛，证毕。上述定理告诉我们，迭代过程的收敛速度依赖于迭代函数.如果当时,则该迭代过程只能是线性收敛。( )1( *)!pkpkegxep+1()kkxg x+=,xa b( )0g x3 3 牛顿法牛顿法一、牛顿法的迭代公式一、牛顿法的迭代公式x*x0 x1x2xyf(x)原理：原理：将非线性方程线性化将非线性方程线性化 求求f (x)在在 x0 处的切线方程处的切线方程:)()(0000 xxxfxf0100()()f xxxfx只要只要 f

15、 C1，每一步迭代都有，每一步迭代都有f ( xk ) 0， 而而 且且 ，lim*kkxx=，则，则 x*就是就是 f (x)的根。的根。)()(1kkkkxfxfxx (2.3)000()()()yf xfxxx=+-令令: 求求f (x)在在 x1 处的切线方程处的切线方程:111()()()yf xfxxx=+-1211()()f xxxfx一般地一般地 二、二、牛顿法收敛牛顿法收敛的的充分条件充分条件定理定理2.5： 设设f (x)在在a, b上满足下列条件上满足下列条件：（1）f (a) f (b) 0则由则由（2.3）确定的牛顿迭代序列确定的牛顿迭代序列xk收敛于收敛于f (x)

16、在在a, b上的唯一根上的唯一根x*。Newton法的收敛性依赖于法的收敛性依赖于x0 的选取。的选取。x*x0 x0 x0例6:设C为正实数,导出用牛顿法求 的公式,并证明迭代序列的误差 满足解:设 ,则 于是有由于 所以在 内有一正根.又在 内, 根据定理2.5得牛顿迭代格式为:CCxennnnnxee221Cx Cx 22)( ,2)( ,)(2xfxxfCxxf012) 1(,)0(CCfCf1 , 0C1 , 0C0)( , 0)( xfxf)lim(2, 1n210CxxcxxxCxnnnnn因为 所以注意:由上式可得:即该迭代格式是2阶收敛的.Cxenn11nnnnnnnnxex

17、CxCxcxxe22)(22221Cxeennnnn2121limlim213牛顿法收敛的阶牛顿法收敛的阶定理定理2.6 对于方程对于方程f(x)=0,设设f(x)充分光滑充分光滑.x*是是f(x)=0在在a,b内的根内的根.（1）x*是单根是单根,则牛顿迭代格式是则牛顿迭代格式是2阶收敛的阶收敛的;（2） x*是是m重根重根,则牛顿迭代格式是线性收敛的则牛顿迭代格式是线性收敛的.此定理的证明涉及到定理此定理的证明涉及到定理2.4,请参见请参见P35.例例7 求方程求方程 的解的解01)2(4xex解解:设设 则则 f(0)=1, f(2)= -1 注注:x0=3 or 81)2()(4xex

18、fx44)410(41)( ,)46()( xxexxfexxf在在0,2内内, f(x)0, f(0)f(0)0, 所以迭代格式为所以迭代格式为:MATLAB程序为:x0=0;k=0;dx=1;while dxepsx=x0-(exp(-x0/4)*(2-x0)-1)/(exp(-x0/4)*(x0-6)/4); dx=abs(x-x0); x0=x; k=k+1;end x,k, 2 , 1,)46(1)2(04410nexxexxxnnxnnxnn这应该说是较精确的解如果改写x0=3,又会得到怎样的结果呢?计算结果如上.如果改写x0=6,又会怎样呢?计算结果如上. x(1)=8; for k=2:3x(k)=x(k-1)-(2-x(k-1)*exp(-x(k-1)/4)-1)/(exp(-x(k-1)/4)*(x(k-1)-6)/4);end xx = 8.0000 34.7781 869.1528定理2.5指出:x0的选取是很要紧的.例如此例:选x0=0则完全