第二节 迭代法 2

1、数学学院数学学院 信息与计算科学系信息与计算科学系第二节第二节 迭代法迭代法一、迭代法的基本思想一、迭代法的基本思想迭代法是一种重要的逐次逼近法迭代法是一种重要的逐次逼近法, ,其其基本思想基本思想是：是：将方程将方程 f (x)= 0 化为等价方程化为等价方程, )(xx 然后在隔根区间内取一点然后在隔根区间内取一点 x0 ，按下式计算按下式计算1()(0,1,2,)kkxxk 计算结果生成数列计算结果生成数列,10kxxx如果这个数列有极限如果这个数列有极限 xxkklim数学学院数学学院 信息与计算科学系信息与计算科学系这种求根方法称为这种求根方法称为迭代法迭代法。 如果迭代序列收敛如果

2、迭代序列收敛, ,则称则称迭代格式收敛迭代格式收敛, ,否则称为否则称为发发散散。当当 (x) 连续时连续时, ,显然显然 就是方程就是方程 x= (x) 之根。之根。 x于是于是可以从数列可以从数列 中求得满足精度要求的近似根。中求得满足精度要求的近似根。kx1()(0,1,2,)kkxxk 称为称为迭代格式迭代格式, (x) 称为称为迭代函数迭代函数, x0 称为称为迭代初值迭代初值,数列数列 称为称为迭代序列迭代序列。kx数学学院数学学院 信息与计算科学系信息与计算科学系二、二、 迭代法的几何意义迭代法的几何意义一般来说从一般来说从,0)( xf构造构造)(x 不止一种，有的不止一种，有

3、的收敛，有的不收敛，这取决于收敛，有的不收敛，这取决于 的性态。的性态。)(x 方程方程 的根，在几何上就是直线的根，在几何上就是直线)(xx xy 与曲线与曲线 的横坐标的横坐标)(xy 。 x如图如图2-3所示所示数学学院数学学院 信息与计算科学系信息与计算科学系数学学院数学学院 信息与计算科学系信息与计算科学系数学学院数学学院 信息与计算科学系信息与计算科学系 03224xxx14)(2 xxx 32)(243 xxxx 4121)23()(xxxx 对方程进行如下三种变形：对方程进行如下三种变形：用迭代法求方程用迭代法求方程 x4+2x2-x-3=0 在区间在区间1, 1.2内内的的

4、实根实根。解解例例1数学学院数学学院 信息与计算科学系信息与计算科学系分别按以上三种形式建立迭代格式，并取分别按以上三种形式建立迭代格式，并取x0=1进行进行迭代计算，结果如下：迭代计算，结果如下：12411()(32)kkkkxxxx 26271.124123xx12()41kkkxxx 4213()23kkkkxxxx 73496,8.49530710 xx124123. 176 xx数学学院数学学院 信息与计算科学系信息与计算科学系第二种格式比第一种格式收敛快得多第二种格式比第一种格式收敛快得多, ,而第三种格式而第三种格式不收敛。不收敛。可见迭代格式不同可见迭代格式不同, , 收敛情况

5、也不同。收敛情况也不同。准确根准确根 = 1.124123029 。 x数学学院数学学院 信息与计算科学系信息与计算科学系三、迭代法的收敛条件三、迭代法的收敛条件定理定理 1 1 (1) 当当xa , b时时，; ,)(bax (2) 存在正数存在正数L1，使对任意的使对任意的 xa , b,(2) 对任意迭代初值对任意迭代初值 x0a , b,迭代序列迭代序列), 2 , 1 , 0()(1 kxxkk 。1)( Lx (1) 方程方程在在a , b上有唯一根上有唯一根 ;)(xx x)(x 在在a , b上上存在存在, ,且满足条件且满足条件：设设收敛于收敛于 。 x 则则 数学学院数学学

6、院 信息与计算科学系信息与计算科学系(1) 先证方程先证方程)(xx 之解存在且唯一之解存在且唯一.由于由于)(x 在在 a , b上存在上存在, )()(xxxf f (x) 在在a , b上连续。上连续。作函数作函数由条件由条件)(x 连续连续。所以所以证证使使 0)( xf。)( xx 即即则则(1) f (a) 0 , f (b) 0 , 故存在故存在 ,bax 数学学院数学学院 信息与计算科学系信息与计算科学系则由微分中值定理及条件值定理及条件则由微分中值定理及条件值定理及条件(2)(2)有有 xLxxx)()()(此式仅当此式仅当0 x才能成立才能成立，再证迭代格式再证迭代格式)(

7、1kkxx 收敛收敛任取任取 x0 a, b ，由微分中值定理，有由微分中值定理，有。 x 因此因此（2）则由微分中值定理及条件则由微分中值定理及条件(2) 有有设方程设方程)(xx 还有一根还有一根, 数学学院数学学院 信息与计算科学系信息与计算科学系此定理在理论上十分重要此定理在理论上十分重要, , 但是条件但是条件(1)(1)却不容易却不容易判别判别. . 如果仅在根的邻域中考察迭代格式如果仅在根的邻域中考察迭代格式, , 则下述则下述定理可避免条件定理可避免条件(1)(1)的判别。的判别。即迭代过程收敛，即迭代过程收敛， 且且。 xxkklim证毕。证毕。反复用此不等式，并注意反复用此

8、不等式，并注意 0 L 1 ,111)()()( kkkkxxLxxxxxx )(00 kxxLxxkk因此因此数学学院数学学院 信息与计算科学系信息与计算科学系 例例1 1中采用的三种迭代格式中采用的三种迭代格式 , ,在隔根区间在隔根区间(1, 1.2)内有内有187. 0)2 . 1213(25. 02 . 1)23(25. 0)(4324321 xxxx 2 1 41( )(32)xxxx 2( )41xxx 例如例如数学学院数学学院 信息与计算科学系信息与计算科学系423( )23xxxx 844)(33 xxx 11. 051544144)(112 xxx 数学学院数学学院 信息与

9、计算科学系信息与计算科学系且有下列误差估计式且有下列误差估计式 定理定理 2则任取则任取 x0 U , )(1kkxx 迭代格式迭代格式均收敛于均收敛于 , x 若方程若方程)( xx 之根的某邻域之根的某邻域 L 1，使使( )1,xLxU 内内)(x 存在存在, ,且存在正常数且存在正常数 xxxU|11011kkkkkLxxxxLLxxxxL 数学学院数学学院 信息与计算科学系信息与计算科学系( )1x 则迭代必发散。则迭代必发散。提示提示：定理的证明利用定理定理的证明利用定理1 1以及微分中值定理。以及微分中值定理。反之，若在根反之，若在根 的邻域的邻域 U 内内 x数学学院数学学院

10、信息与计算科学系信息与计算科学系例例2 用迭代法求方程用迭代法求方程0104)(23 xxxf2 , 1在在内的一个近似根，取初始近似值内的一个近似根，取初始近似值5 . 10 x解解原方程的等价方程可以有以下不同形式原方程的等价方程可以有以下不同形式xxxxxxxxxxx 410)4(1021)3(410)2(104)1(323数学学院数学学院 信息与计算科学系信息与计算科学系对应的迭代公式有：对应的迭代公式有：nnnnnnnnnnxxxxxxxxxxxn 410)4(1021)3(410)2(104)1(1312311数学学院数学学院 信息与计算科学系信息与计算科学系考察四种迭代法在根附近

11、的收敛情况，取根考察四种迭代法在根附近的收敛情况，取根的近似值为的近似值为。5 . 10 x解解175.17)5 . 1(831)(104)()1(223 xxxxxxx不收敛不收敛1128. 5)5 . 1()410()410(21)(410)()2(221 xxxxxxx不收敛不收敛数学学院数学学院 信息与计算科学系信息与计算科学系1656. 0)5 . 1()10(43)(1021)()3(21323 xxxxx1122.0)5 .1()4(1)410(5)(410)()4(221 xxxxx收敛收敛收敛收敛由定理由定理2知知 值越小，收敛速度就越快值越小，收敛速度就越快)(0 x 数学

12、学院数学学院 信息与计算科学系信息与计算科学系1.365230021.3659167381.365229941.3638870071.3652230581.3678469761.365225591.3600941951.365264751.3751702541.364957011.34545838-469.731.367376371.402540802.99696.73221.348399731.286953770.8165-0.87511.51.51.51.50(4)(3)(2)(1)n81003.1 21)65.8( 取取,5 . 10 x列表计算如下列表计算如下数学学院数学学院 信息与计

13、算科学系信息与计算科学系n (1) (2) (3) (4)91.364878221.36523001101.36541006151.36522368201.36523024231.36522998251.36523001接上图接上图数学学院数学学院 信息与计算科学系信息与计算科学系四、迭代法的收敛速度四、迭代法的收敛速度1(,0)kpkeckce 则称迭代格式则称迭代格式)(1kkxx 是是 p 阶收敛阶收敛的的. . p = 1时称为时称为线性收敛线性收敛, , 1p2时称为时称为超线性收敛超线性收敛.利用微分中值定理及泰勒展式可得下面的定理利用微分中值定理及泰勒展式可得下面的定理3. 3. 显然显然, , 收敛阶越大收敛阶越大, , 收敛越快收敛越快p = 2 时称为时称为二阶二阶( (平方平方) )收敛收敛, , 特别地特别地, ,令令,xxekk若若数学学院数学学院 信息与计算科学系信息与计算科学系则迭代过程在则迭代过程在 的邻近为的邻近为 p 阶收敛阶收敛。 x,1)(0 x (1) 若若为线性收敛为线性收敛；则迭代过程在则迭代过程在 的邻近的邻近 x, 0)(,0)()()()() 1( xxxxpp (2) 若若定理定理 3)(xx 之根之根, ,在在 的邻域的邻域