第2章迭代法

1、第2章 方程求根1 二分法二分法2 简单迭代法简单迭代法3 切线法切线法(牛顿法牛顿法)4 弦截法弦截法 图 2.3 二分法适合单二分法适合单根，不能求复根，不能求复根和偶数重根，根和偶数重根，且收敛速度慢，且收敛速度慢，可以为其他方可以为其他方法提供一个初法提供一个初值，用其他方值，用其他方法精确化。法精确化。预备定理预备定理介值定理介值定理 函数函数 f(x)f(x)在在 a,ba,b 上单调连续，且上单调连续，且f(a)f(b)f(a)f(b)00，则方程，则方程f(x)=0f(x)=0在区间在区间 a,ba,b 上有且仅有上有且仅有一个实根一个实根x x* *。 微分中值定理 如果函数

2、( )f x在 , a b连续，在a,b（)可微，则在a,b（)内至少有一点存在，使 ( )( )( )()f bf afba ab 2 迭代法迭代法 迭代法的基本思想是:首先将方程(2.1)改写成某种等价形式,由等价形式构造相应的迭代公式,然后选取方程的某个初始近似根x0,代入迭代公式反复校正根的近似值,直到满足精度要求为止。迭代法是一种数值计算中重要的逐次逼近方法。 迭代法是一种逐次逼近的方法，用某种固定格式反复校正根的近似值，使之逐步精确，最后达到满意的效果。 例 求310 xx 在01.5x 附近的根。 解 将上式写成等价方程31xx，当用根x代入时，有 3*1xx 设01.5x 是其

3、根，代入时，有 35721. 115 . 113301xx 再设11.35721x 是其根，代入时，有 33086. 1135721. 113312xx， 依次可得 41.32494,x 561.32476,1.32473xx781.32472,1.32472xx k kx 1kkxx 0 1 2 3 4 5 6 7 8 1. 5 1. 35721 1. 33086 1. 32588 1. 32494 1. 32476 1. 32473 1. 32472 1. 32472 计算结果见下表计算结果见下表 对于一般形式的方程(2.1),首先我们设法将其化为下列等价形式 x=g(x) (2.7) 然

4、后按(2.7)构造迭代公式 (2.8) 从给定的初始近似根x0出发,按迭代公式(2.8)可以得到一个数列 x0,x1,x2,xk, 若这个数列xk有极限,则迭代公式(2.8)是收敛的。此时数列的极限1(),0,1,2,kkxg xklimkkxx 就是原方程(2.1)的根。 虽然迭代法的基本思想很简单,但效果并不总是令人满意的。对于上例,若按方程写成另一种等价形式 x=x3-1 (2.9) 建立迭代公式 xk+1=x3k-1, k=0,1,2, 仍取初始值x0=1.5, 则迭代结果为 x1=2.375 x2=12.3976 迭代法的几何意义:把方程(2.1)求根的问题改写成(2.7)变为求数列

5、xn的极限,实际上是把求根问题转化为求( )yxyg x 图 2.4 迭代过程(2.8)就是在x轴取初始近似值x0,过x0作y轴的平行线交曲线y=g(x)于p0,p0的横坐标为x0,纵坐标为g(x0)(g(x0)=x1),也即 p0(x0,x1) 再在x轴上取x1作为新的近似值,过x1作y轴的平行线交曲线y=g(x)于p1,p1的横坐标为x1,纵坐标为 g(x1)(g(x1)=x2),也即 p1(x1,x2) 而这相当于过p0引平行于x轴的直线交y=x于 Q1(x1,x2) 再过Q1引平行于y轴的直线交曲线y=g(x)于 p1(x1,x2) 仿此可得到点列 p0(x0,x1),p1(x1,x2

6、),p2(x2,x3), 若limlimkkkkppxx 则迭代法收敛,见图2.4(a);否则迭代法发散,见图2.4(b)。 必须说明两点: 若g(x)可微,可用充分条件( )1g xq这里q1是非常重要的条件,否则不能保证迭代收敛。 对于收敛的迭代过程,误差估计式(2.11)说明迭代值的偏差xk-xk-1相当小,就能保证迭代误差x-xk足够小。因此在具体计算时常常用条件 xk-x k-1 (2.15) 来控制迭代过程结束。 迭代法的突出优点是算法的逻辑结构简单,且在计算时,中间结果若有扰动,仍不会影响计算结果。其计算步骤为: (1)确定方程f(x)=0的等价形式x=g(x),为确保迭代过程的

7、收敛,要求g(x)满足g(x)q1 (2)选取初始值x0,按公式 x k+1=g(xk), k=0,1,2, 进行迭代; (3)若x k+1-xk,则停止计算,xx k+1。 例2 求方程 x= e-x 在x=0.5附近的一个根。按五位小数计算,计算结果 的精度要求为=10-3。 解 过x=0.5以步长h=0.1计算 f(x)=x-e-x 由于 f(0.5)0,f(0.6)0 故所求的根在区间(0.5,0.6)内,且在x=0.5附近 (2)()0.61xe 5488. 0606. 06 . 05 . 06 . 05 . 0eex 图 2.5 表表 23 因此用迭代公式 由表可见10 xxxxe

8、为方程 kkxex1例 对方程0123 xx在区间1.4，1.6建立两种收敛的迭代格式，并用其中一种求解，精确到 5 位有效数字。 方法1： 取方程等价形式211xx ， 对应迭代格式1211kkxx ，0,1,k 。其中21( )1xx ， 则32( )xx 。 由于3322( )0.72911.4xx，(1.4,1.6)x，因而迭代收敛。 方法 2：取等价形式321xx ，故收敛格式2311kkxx，0,1,k 。其中32( )1xx，则2232( )(1)3xxx 由于：2232 1.6( )0.5174113 (1 1.4 )x，(1.4,1.6)x，因而迭代收敛。且第二种迭代格式比第

9、一种迭代格式收敛得更快。 取初值01.5x ，用第二种迭代格式计算过程如下表所示。 k kx 1kkxx 0 1. 50000 1 1. 14812 1. 50000 2 1. 47271 0. 35188 3 1. 46882 0. 32458 4 1. 46709 0. 00389 5 1. 46624 0. 00177 6 1. 46588 0. 00081 7 1. 46571 0. 00037 8 1. 46563 0. 00008 9 1. 46560 0. 00003 由于 ，故取x x9=1.46560 54981310102xx定义定义 如果存在*x的某个邻域：*xx，使迭代

10、过程1()kkxx对 于 任 意 初 值0 x 均 收 敛 ， 则 称 迭 代 过 程1()kkxx在根*x附近具有局部收敛性。 定理定理 设( )x在( )xx的根*x附近连续，且有 ()1x 则迭代格式1()kkxx在根*x附近具有局部收敛性。 迭代法的迭代法的局部收敛性局部收敛性由于在实际应用中根由于在实际应用中根 x* 事先不知道，故条件事先不知道，故条件 | (x* )| 1无法验证。但已知根的初值无法验证。但已知根的初值x0在根在根 x*邻域，又根据邻域，又根据 (x)的连续性，则的连续性，则可采用可采用 | (x0 )| 1 来代替来代替| (x* )| 1，判断迭代的收敛性。，

11、判断迭代的收敛性。 例例求方程求方程 x=e x在在x=0.5附近的一个根，按附近的一个根，按5位小数计算，位小数计算，结果的精度要求为结果的精度要求为=10 3.解解迭代公式迭代公式 xk+1=e xk ，取取 (x)=e x,0.50.5|(0.5)| |(e) | e0.61 1迭代公式迭代公式 xk+1=e xk 收敛。收敛。迭代结果迭代结果: 0 1 2 3 4 5 0. 5 0. 606 53 0. 545 24 0. 579 70 0. 560 07 0. 571 17 0. 106 53 0. 061 29 0. 034 46 0. 019 63 0. 011 10 6 7 8

12、 9 10 0. 564 86 0. 568 44 0. 566 41 0. 567 56 0. 566 91 0. 006 31 0. 003 58 0. 002 03 0. 001 15 0. 000 65kxkxk xk-1xk xk-1k xk|x10 - x9 |=0.00065，故故 x*x10 0.567x0=0.5, x2=e x1=0.54524,.x1=e x0=0.60653,xk+1=e xk例： 迭代过程)5(21kkkxcxx， 当局部收敛到5时，确定c的值。 解：迭代函数 )5()(2xcxx，cxx21)(，当 局 部 收 敛 到5时 ，1521)5(c，152

13、11c，有051c。 迭代的计算步骤迭代的计算步骤 （1）确定( )0f x 的等价形式( )xx，选初值0 x，判断收敛性01x（ ）。 （2）由公式10()xx计算1x。 （3）如果10 xx则停止计算，取*1xx；否则令01xx，重复步骤 2 和 3，直到计算停止。 迭代法计算框图的说明迭代法计算框图的说明0 x，N, k 10 xx 2.2.3 迭代过程的收敛速度迭代过程的收敛速度定义定义 设迭代过程设迭代过程1()kkxx收敛于收敛于( )xx的根的根*x，迭代误差，迭代误差*kkexx，如果，如果存在常数存在常数p（1p ）和不等于零的常数）和不等于零的常数c使使 1limkpkk

14、ece 则则称序列称序列kx是是p阶收敛的。阶收敛的。c称渐进误差常数。称渐进误差常数。特别地，特别地，1p 称为线性收敛，称为线性收敛，2p 称为平方称为平方收敛，收敛，1p 时称为超线性收敛。时称为超线性收敛。 迭代函数的导数和收敛阶。 定理 对迭代过程1()kkxx，若()( )px在所求根*x邻近连续，且 *(1)*()()()0pxxx()*()0px 则迭代格式1()kkxx在*x邻近是p阶收敛的。 证明 *()0 x，迭代过程1()kkxx有局部收敛性。 *21()()()()()()2kkkxxxxxxxx (1)*(1)()11()()( )()(1)!ppppkkxxxxx

15、pp *()11( )()!ppkkxxxxp，得证。 例：迭代过程)5(21kkkxcxx，至少平方收敛到5时，确定c的值。 解： 2( )(5)xxc x，( )12xcx ， 当()0 x时，至少平方收敛，所以取1250c，12 5c 例 设方程0cos2312xx的迭代法kkxxcos3241，证明 对 Rx 0，均有*limxxkk，其中*x为方程的根；取40 x，求此迭代法的近似根，使误差不超过 10-3 ；证明此迭代法的收敛阶。 证证 kkxxcos3241，迭代函数xxcos324)(是连续函数 324cos324324x,22( )4,4(,)33x 2max( )sin1,

16、lim*3kkx Rxxxx 已知初值40 x，计算结果如下表所示。 k kx 1kkxx 0 4 1 3. 5642 0. 4358 2 3. 3920 0. 1722 3 3. 3541 0. 0379 4 3. 3483 0. 0058 5 3. 3475 0. 0008 6 3. 3474 0. 0001 7 3. 3474 0. 0000 取近似根*x3474. 37x。 取3474. 3*x，则3.34742( *)|sin(3.3474)0.1362403x ,所以迭代法 1 阶收敛（线性收敛） 。 1 1 加加权权法法：设 kx是根x的某近似值，取1(),()kkxxxx，由中

17、值定理 1()()( )()kkkxxxxxx 其中,kxx，假定( ) 变化不大，设( )c ，有 1()kkxxc xx，1kkxcxxcx 1111kkLxxxcc，取11111kkkLxxxcc，即 11 (1kkkxxcxc 2.2.4 迭代的加速埃特金加速法：埃特金加速法：设 kx是根x的某近似值，取 )(1kkxx )(12kkxx 和加权法同理有)(*1*kkxxcxx)(1*2*kkxxcxx， 将上二式联立，有 1*2*1*kkkkxxxxxxxx kkkkkkxxxxxxx1221*2)( 2 埃特金加速法21(),()()2kkkkkkkkkkkyxzyyxxxzyx用

18、不动点迭代法求函数2ln)(xxxf在区间（2，+）内的零点，并用艾特肯森迭代法加速。 解解 设, 02ln)(xxxf有等价方程, 2lnxx，取迭代函数( )ln2xx，此时2111( ), max( )12xxxxx 所以迭代过程2ln1kkxx局部收敛，取初值30 x，计算结果如下表所示。 k kx 1kkxx 0 3 1 3. 098612289 2 3. 130954363 3 3. 141337866 4 3. 144648781 5 3. 145702209 6 3. 146037143 不动点迭代法不加速时，取146. 36x，有 4 位有效数字。 斯蒂芬森迭代法加速 2ln

19、kkxy， 2lnkkyz ， 21()2kkkkkkkyxxxzyx。 计算结果如下表所示。 k kx ky kz 0 3 3. 098612289 3. 130954363 1 3. 146738373 3. 146366479 3. 146248288 2 3. 146193227 3. 146193223 3. 146293221 3 3. 146193227 用斯蒂芬森迭代法加速后，146193227. 33x，有 10 位有效数字。 3 切线法切线法(牛顿法牛顿法) 切线法是求解方程(2.1)的一种重要迭代方法。如图2.6,曲线y=f(x)与x轴的交点x就是方程(2.1)的根。 图图 2.6 与x轴的交点为x k+1,其方程为1()()()0()()()kkkkkkkyf xfxxxf xfxxx 点xk+1满足该切线方程,即可得到切线迭代公式(或牛顿迭代公式)1(),0,1,2,()kkkkf xxxkfx(2.20) 切线法是非线性方程线性化的方法。其计算步骤为: 给出初始近似根x0及精度。 计算 若x1-x0,则转向;否则x1 x0,转向。 输出满足精度的根x1,结束。 切线法的计算