数值分析方法课件.ppt

1、2.2 2.2 迭代法迭代法2.2.1 2.2.1 迭代原理迭代原理2.2.2 2.2.2 迭代的收敛性迭代的收敛性2.2.3 2.2.3 迭代的收敛速度迭代的收敛速度2.2.4 2.2.4 迭代的加速迭代的加速预备定理预备定理介介 值值 定定 理理 函函 数数 f(x)在在 a,b上上 单单 调调 连连 续续，且且f(a)f(b)0，则则 方方 程程 f(x)=0 在在 区区 间间 a,b上上 有有 且且 仅仅 有有 一一 个个实实 根根 x*。微 分 中 值 定 理 如 果 函 数()fx在,a b连 续，在a,b（)可 微，则 在a,b（)内 至 少 有 一 点存 在，使 ()()()(

2、)fbfafba ab 迭代法是一种逐次逼近的方法，用某种固定格式反复校正根的近似值，使之逐步精确，最后达到满意的效果。例 求310 xx在01.5x 附近的根。解 将上式写成等价方程31xx，当用根x代入时，有 31xx 设01.5x 是其根，代入时，有 331011.511.35721xx 再设11.35721x 是其根，代入时，有 32111.33086xx，33211.32588xx 依次可得 41.32494,x 561.32476,1.32473xx781.32472,1.32472xx 2.2.1 迭代原理迭代原理k kx 1kkxx 0 1 2 3 4 5 6 7 8 1.5

3、1.35721 1.33086 1.32588 1.32494 1.32476 1.32473 1.32472 1.32472 计算结果见下表计算结果见下表 方程方程f(x)=0化为等价形式的方程化为等价形式的方程 x=(x)，构造迭代公式构造迭代公式 xk+1=(xk),k=0,1,2,取初始近似根取初始近似根x0,进行迭代计算进行迭代计算 x1=(x0),x2=(x1),.则有则有x1,x2,.,xk,.,得到迭代序列得到迭代序列xk.如果这个如果这个序列有极限，则迭代公式是收敛的。这时序列有极限，则迭代公式是收敛的。这时 则则 ，x*为不动点，等价地有为不动点，等价地有 f(x*)=0,

4、x*即为即为方程的根。连续函数方程的根。连续函数(x)称为迭代函数。称为迭代函数。实际计算到实际计算到|xk xk-1|（是预定的精度），取是预定的精度），取x*xk。*limxxkk *()xx 迭代公式收敛迭代公式收敛指迭代序列指迭代序列xk 收敛，收敛，迭代公式发散迭代公式发散指迭代指迭代序列序列xk 不收敛，即发散。迭代公式不一定总是收敛。不收敛，即发散。迭代公式不一定总是收敛。例如求方程例如求方程 f(x)=x3-x-1=0的一个根的一个根。对应的迭代公式为对应的迭代公式为01.5x 311kkxx取初值取初值1232.375,12.39648,1904.00277xxx迭代序列迭代

5、序列xk 发散发散.简单迭代法的几何意义：把求方程()0f x 的根的问题，转化为求()yxyx两曲线的交点问题，交点的横坐标就是方程的根*x。x1=(x0)x2=(x1)迭代法收敛与发散的图示迭代法收敛与发散的图示迭代法的收敛与发散迭代法的收敛与发散 收敛的情形 发散的情形2.2.2 迭代的收敛性迭代的收敛性 迭代法的收敛条件及误差估计式迭代法的收敛条件及误差估计式定理（充分性条件）定理（充分性条件）设函数设函数 (x)在在a,b上连续，且上连续，且 (1)对对 xa,b,有有 (x)a,b (2)存在存在0 L 1，使对任意，使对任意 x a,b有有|(x)|L 1则方程则方程x=(x)在

6、在 a,b上的根上的根x*存在且唯一；对初值存在且唯一；对初值 x0 a,b,迭代过程迭代过程 xk+1=(xk)均收敛于方程的根均收敛于方程的根x*。定理中的定理中的(1)对对 xa,b,有有 (x)a,b，称为适定性（映内，称为适定性（映内性）。性）。证明证明 先证根的存在性。先证根的存在性。作连续函数作连续函数(x)=x-(x),由条件（由条件（1）xa,b,(x)a,b，即即a (x)、xb,于是于是 (a)=a-(a)0 (b)=b-(b)0 由于由于(x)是连续函数，故必存在是连续函数，故必存在 x*a,b 使使(x*)=0.即即(x*)=x*-(x*)=0.于是于是 x*=(x*

7、)即即x*为方程为方程 x=(x)的根。的根。其次，证根的唯一性其次，证根的唯一性。设设y*也是方程的根，则也是方程的根，则x*=(x*),y*=(y*),x*-y*=(x*)(y*)=()(x*-y*)x*-y*()(x*-y*)=0，（x*-y*）1-()=0由条件（由条件（2）|(x)|L 1，故有故有x*-y*=0，即即x*=y*所以方程在所以方程在a,b的根唯一的根唯一。再证迭代的收敛性再证迭代的收敛性。由由xk=(xk-1),x*=(x*),有有|xk -x*|=|()(xk-1-x*)|L|x k-1-x*|L2|xk-2-x*|L3|xk-3-x*|Lk|x0-x*|0（k）所

8、以，对所以，对a,b上任取的上任取的x0,迭代公式迭代公式xk+1=(xk)都收都收敛于敛于x*。L越小收敛得越快。越小收敛得越快。*limxxkk 定理是充分性条件定理是充分性条件xk -x*=(xk-1)(x*)=()(xk-1-x*)推论：在定理的条件下，有误差估计式推论：在定理的条件下，有误差估计式 验后误差估计式验后误差估计式 验前误差估计式验前误差估计式证明：证明：|xk -x*|L|x k-1-x*|=L|x k-1-x k+x k-x*|L（|x k-x*|+|x k-1-x k|）（1-L)|x k-x*|L|x k-1-x k|迭代法的终点判断：只要相邻两次迭代值的偏迭代法

9、的终点判断：只要相邻两次迭代值的偏差充分小，就能保证迭代值足够准确，因而用差充分小，就能保证迭代值足够准确，因而用|x k-x k-1|控制迭代过程的结束。控制迭代过程的结束。*11kkkLxxxxL*11kkkLxxxxL*101kkLxxxxL 定理定理 设在区间设在区间a,b上方程上方程 x=(x)有根有根x*,且对一切且对一切xa,b 都有都有|(x)|1，则对于该区间上任意，则对于该区间上任意x0(x*),迭代公式迭代公式xk+1=(xk)一定发散一定发散。证明证明,baxk 时，时，且且*0 xx *1|()|kkxxxx 0.*0*1 xxxxk*xxk 不可能收敛于不可能收敛于

10、0。例 用迭代法求方程3250 xx 的最小正根。解解 试凑正根所在的区间 x 0 1 2 3 4 200 20000 f(x)-5-6-1 16 51 +取正根区间2,3，迭代格式3115)2kkxx（，迭代函数导数2233(),()13.5 12maxxxxx，不满足收敛定理。将原方程改写成 3(25)xx,2332()25,()(25),3xxxx()0.94 123maxxx，迭代格式3125kkxx 收敛。,取初值02.5x。进行迭代，结果如下所示。k kx 1kkxx 0 1 2 3 4 5 6 2.5 2.1544 2.1036 2.0959 2.0948 2.0946 2.09

11、46 计算结果见下表计算结果见下表取方程的根取方程的根 2.0946。例 对方程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 由于：22321.6()0.5174113(11.4)x，(1.4,1.6)x，因而迭代收敛。且

12、第二种迭代格式比第一种迭代格式收敛得更快。取初值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 由于 ，故取 54981310102xx*91.4656xx定定义义 如果存在*x的某个邻域：*xx，使迭代过程1()kkxx对 于 任

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

14、根，按附近的一个根，按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 9 10 0.564 86 0.568 44 0.566 41 0.567 56 0.566 91 0.

15、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，15211c，有051c。迭代的计算步骤迭代的计算步骤（1）确定()0f x 的等价形式()xx，选初值0 x，判断收敛性01x（）。（2）由公式10

16、()xx计算1x。（3）如 果10 xx则 停 止 计 算，取*1xx；否则令01xx，重复步骤 2 和 3，直到计算停止。迭代法计算框图的说明迭代法计算框图的说明0 x，N,k 10 xx 已知)(xx在a,b上只有一个实根，而且当,bax 时，1|)(|Lx（L为常数），问如何将)(xx化为适合于迭代的形式？解解 由已知)(xx在a,b上只有一个实根，故其反函数)(xx存在，又)(1)(xx，当,bax 时，1|)(|Lx（L为常数），所以有1)(1)(xx，因此)(xx收敛。给定函数f(x)，设迭代过程)(1kkkxfxx，选取值，使在0)(xf的单根附近收敛。解解)(1kkkxfxx，

17、)()(xfxx，1)(1)(xfx时，迭代过程收敛。解之1)(11xf，0)(2xf，2)(0 xf 在0)(xf的单根附近，0)(xf且)(xf连续，取)(max*xfMxx，得M20 2.2.3 迭代过程的收敛速度迭代过程的收敛速度定定 义义 设设 迭迭 代代 过过 程程1()kkxx收收 敛敛 于于()xx的的根根*x，迭迭代代误误差差*kkexx，如如果果存存在在常常数数p（1p）和和不不等等于于零零的的常常数数c使使 1limkpkkece 则则称称序序列列kx是是p阶阶收收敛敛的的。c称称渐渐进进误误差差常常数数。特特别别地地，1p 称称为为线线性性收收敛敛，2p 称称为为平平方

18、方收收敛敛，1p 时时称称为为超超线线性性收收敛敛。迭代函数的导数和收敛阶。定理 对迭代过程1()kkxx，若()()px在所求根*x邻近连续，且*(1)*()()()0pxxx()*()0px 则迭代格式1()kkxx在*x邻近是p阶收敛的。证明*()0 x，迭代过程1()kkxx有局部收敛性。*21()()()()()()2kkkxxxxxxxx(1)*(1)()11()()()()(1)!ppppkkxxxxxpp*()11()()!ppkkxxxxp，得证。例：迭代过程)5(21kkkxcxx，至少平方收敛到5时，确定c的值。解：2()(5)xxc x，()12xcx，当()0 x时，

19、至少平方收敛，所以取1250c，12 5c 例 设方程0cos2312xx的迭代法kkxxcos3241，证明 对 Rx 0，均有*limxxkk，其中*x为方程的根；取40 x，求此迭代法的近似根，使误差不超过 10-3 ；证明此迭代法的收敛阶。证证 kkxxcos3241，迭代函数xxcos324)(是连续函数 324cos324324x,22()4,4(,)33x 2max()sin1,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.3

20、483 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，由中值定理 1()()()()kkkxxxxxx 其中,kxx，假定()变化不大，设()c，有 1()kkxxc xx，1kkxcxxcx 1111kkLxxxcc，取11111kkkLxxxcc，即 11(1kkkxxcxc 2.2.4 迭代的加速埃

21、埃特特金金加加速速法法：设 kx是根x的某近似值，取 11(),()kkkkxxxx 和加权法同理有1()kkxxc xx，和1()kkxxc xx 将上二式联立，有111kkkkxxxxxxxx，211111()2kkkkkkxxxxxxx 取 2111111()2kkkkkkkxxxxxxx 2 埃特金加速与斯蒂芬森迭代法 埃特金迭代埃特金迭代1112111111(),()()2kkkkkkkkkkkxxxxxxxxxxx将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法将不动点迭代法与埃特金加速结合即得斯蒂芬森迭代法21(),()()2kkkkkkkkkkkyxzyyxxxzyx用不动点迭

22、代法求函数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 位有效数字。斯蒂芬森迭代法加速 2lnkkxy，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 位有效数字。