方程求根的迭代法(19-20)

1、重庆大学数理学院数数 值值 分分 析析第第十讲十讲主讲教师主讲教师： 谭谭 宏宏第四章第四章 非线性方程求根非线性方程求根1 1教学内容：教学内容： 二分法、迭代法的一般原理 、NEWTON迭代法 2 2重点难点：重点难点：重点：重点：牛顿迭代法及局部收敛性难点：难点：迭代法及收敛性定理3 3教学目标：教学目标： 掌握迭代法的一般原理、对给出的方程球根问题，能利用一般迭代法或者牛顿迭代法进行数值求解0tg xx0sin8889. 4tg25. 0 xx 在中学时，我们很熟悉一次、二次代数方程以及某些特殊的高次方程或超越方程的解法。这些方法都是代数解法，也是精确法。但在实际中，有许多方程问题无法

2、求出公式解。例如超越方程 看起来很简单，却不容易求得精确解。至于解三次、四次代数方程，尽管存在着求解公式，却不实用，而对一般的五次或五次以上的代数方程，根本没有求根公式。另一方面，在实际应用中，只要能获得具有预先给定的误差限内的近似值就可以了。因此，需要引进能够达到一定精度要求的求方程近似值的方法。 求方程0)(xf的根也叫求函数)(xf的零点。需要解决的几个问题：1根的存在性。方程有没有根？如果有根，有几个根？根的存在性。方程有没有根？如果有根，有几个根？2这些根大致在哪里？如何把根隔离开来？这些根大致在哪里？如何把根隔离开来？3根的精确化根的精确化定理定理1：设函数设函数 f (x) 在区

3、间在区间a, b上连续上连续，如果如果f (a) f (b) 0， 则方程则方程 f (x) = 0 在在a, b内至少有一实根内至少有一实根x*。 二分法的基本思想是： 逐步将有根区间分半，通过判别函数值的符号，进一步搜索有根区间，将有根区间缩小到充分小，从而求出满足给定精度的根的近似值。 执行步骤执行步骤1计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解

4、位于区间则知解位于区间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) 要求不高要求不高(只要连续即可只要连续即可) .无法求复根及偶重根无法求复根及偶重根 收敛慢收敛慢 Yx0*xab)(xfy 21bax1a1b2xYx0*xab误差估计：)(21|

5、*abxxkk由于：*limxxkk所以，二分法可以求得任意精度的根。对于任意给定的精度要求：0由)(21|*abxxkk得：2lnln)ln(abk即：只要二分K次，就可得到指定精度的根。例： 求方程在 区间1, 1.5内的 实根。要求准确到小数点后第2位。 01)(3xxxf 用二分法，这里a = 1, b = 1.5， 且f (a) 0。取区间a, b的中点x0 = 1.25将区间二等分， 由于f (x0)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

6、是是是是否否否否输入输入 ,bak = 0二分法程序流程图1、迭代法的设计思想 迭代法是一种逐次逼近法，这种方法使用某个固定公式所谓迭代公式反复校正根的近似值，使之逐步精确化，直至满足精度要求的结果。 迭代法的求根过程分成两步，第一步先提供根的某个猜测值，即所谓迭代初值，然后将迭代初值逐步加工成满足精度要求的根。迭代法的设计思想是：f (x) = 0等价变换等价变换)(xx迭代函数把根的某个猜测值0 x=()代入迭代函数得)(01xx0 x1x1x2x2x3x一般地：)(1kkxxkx得到序列的根：收敛就必收敛到则若0)(xfxk)lim()(limlim1kkkkkkxxx)(*xx 迭代过

7、程的几何表示 ) : )(xyxyxx交点即真根。( )yxy xO x* x2 x1 x0 xy0P1Q1P2P*P2Q例：例：求方程求方程0210)(xxxf的一个根的一个根210 xx解：解：)2lg( xx等价变换等价变换迭代格式迭代格式)2lg(1kkxxx1 = 0.4771x2 = 0.3939x6 = 0.3758x7 =0.3758取初始值x0 = 1，可逐次算得 迭代法的设计思想是：f (x) = 0等价变换等价变换)(xx迭代函数)(1kkxx问题：？1、怎样选取迭代函数2、怎样保证迭代收敛3、怎样加速迭代收敛3*0331k ( )10 1.5. 1 1 1(0,1,2)

8、 k 0 1 2 7 8 x 1.51.35721 1.330861.324kkf xxxxxxxxxk 例：求方程 在附近的根解：（ ） 将方程改写为由此建立迭代公式331k721.32472 2 11.k 0 1 2 x1.52.37512.39 kkxxxx迭代收敛。（ ） 若将方程改写为建立迭代公式 迭代不收敛。xyy = xxyy = xxyy = xxyy = xx*x*x*x*y=g(x)y=g(x)y=g(x)y=g(x)x0p0 x1p1 x0p0 x1p1 x0p0 x1p1x0p0 x1p11| )( |x1| )( |x1| )( |x1| )( |x3、压缩映像原理定

9、理定理1：如果：如果 (x)满足下列条件满足下列条件（1 1）当）当x a, b时，时， (x) a, b（2 2）当任意）当任意x a, b，存在，存在0 L 1，使，使 则方程则方程x = (x)在在a, b上有唯一的根上有唯一的根x*, ,且对任意初值且对任意初值 x0 a, b时，迭代序列时，迭代序列xk+1= (xk) (k = 0, 1, )收敛于收敛于x*。1)( Lx(6)kkkxxLxx1*1101*1xxLLxxkk且有下列误差估计且有下列误差估计(7)(8)证：)( )()(*1*kkkxxxxxx其中 在x*与xk之间， 设x*是方程的根，即x*= (x*)，由微分中值

10、定理0*11*2*1*)( )()(xxLxxLxxLxxxxxxkkkkkk由条件（2）得因为0 L 1，由知0lim1kkL)(01*kxxk所以*limxxkk即 xk+1 = (xk)收敛因为：| )1 (|*1*1kkkkkkkxxLxxLxxxxxxxx所以：kkkxxLxx1*11012121111)( )()(xxLxxLxxLxxxxxxkkkkkkkkkkk而：所以：01*11xxLxxk 据（7）式，只要 充分小，就可以保证足够小。因此可用条件 来控制迭代过程的结束。kkxx1kxx *kkxx1例：求方程 在0, 0.5内的根，精确到10-5。0133 xx)() 1(

11、313xxx0)( 2 xx125. 05 . 0)( max2xL解：将方程变形因为，在0, 0.5内 为增函数，所以满足收敛条件，取x0 = 0.25，算得x1 = (0.25) = 0.3385416 x2 = (x1) = 0.3462668x3 = (x2) =0.3471725 x4 = (x3) =0.3472814x5 = (x4) =0.3472945 x6 = (x5) =0.3472961x7 = (x6) =0.3472963因为66710|3472961. 03472963. 0| xx取近似根为x* = 0.34729621112 ( )10 (1.5)0.250,

12、 (2)10 1.5,2 11( ) 1.51.5 1( )2 12111( )3.162212 2.51(2) 1( ) f xxxffxxxxxxxxx 例：用简单迭代法求方程的根。解：因为有根区间。（ ）因且2222011 1.5 1( )1221.5111 ( )1.52.25 1.5,2,xxxx 因且根据定理，任取由这两种等价方程所构造的简单迭代方法都收敛，且第一种所产生的迭代序列收敛较快。4、迭代过程的局部收敛性在实际应用迭代法时，通常首先在根 的邻近考察。*x 称一种迭代过程在根 邻近收敛，如果存在邻域 ，使迭代过程对于任意初值 均收敛，这种在根的邻近所具有的收敛性被称为局部局

13、部收敛性收敛性。*x*: xx0 x 定理定理2 设 在 的根 邻近有连续导数，且 成立 则迭代过程 在 邻近具有局部收 敛性。 x xx*x *1x1kkxx*x5、迭代过程的收敛速度 设由某方法确定的序列设由某方法确定的序列xk收敛于方程的根收敛于方程的根x*，如果存在正实数如果存在正实数p，使得，使得定义：定义：Cxxxxpkkk*1*lim（C C为非零常数）为非零常数）则称序列则称序列xk收敛于收敛于x*的收敛速度是的收敛速度是p阶的，或称该方法阶的，或称该方法具有具有p 阶敛速。当阶敛速。当p = 1时，称该方法为线性（一次）收敛；时，称该方法为线性（一次）收敛；当当p = 2时，

14、称方法为平方（二次）收敛；当时，称方法为平方（二次）收敛；当1 p 2时，时，称方法为超线性收敛。称方法为超线性收敛。对于在根 邻近收敛的迭代公式，由于)( *1*kkxxxx式中 介于 与 之间，故有：kx*x|)( |1*1*kkxxxx所以：)( lim*1*1*xxxxxkkk因此，若 则该迭代过程为线性收敛。)( *x0)( *x若将)(kx在 处泰勒展开有：*x2*2*)(2)( )()(2)( )( )()(xxxxxxxxxxkkkk1kx*x所以，2)( )(2*1xxxxkk故2)( lim*2*1*xxxxxkkk即当0)( *x0)( ,*x迭代过程为平方收敛的。星期三晚 设 是根 的某个近似值，用迭代公式校正一次得kx*x1kkxx假设 在所考察的范围内改变不大，其估计值为L， 则有 x*1kkxxL xx据此可导出如下加速公式： 其一步分为两个