数值分析第二章2)

1、数 值 分 析1 1 误差来源与种类误差来源与种类上节知识要点回顾上节知识要点回顾: (1) 模型误差模型误差(2) 参数误差参数误差(3) 截断误差截断误差(4) 舍入误差舍入误差2 绝对误差和相对误差绝对误差和相对误差定义定义设某量的准确值为设某量的准确值为x, 是是x的近似值，的近似值，x 如果如果 称称 为为 的的绝对误差限绝对误差限.,exx x 显然显然,xxx常记为常记为.xx exx为为 的的绝对误差绝对误差，简称误差，简称误差.x 称称定义定义 设某量的准确值为设某量的准确值为x, 是是x的近似值，的近似值，x 如果如果 称称 为为 的的相对误差限相对误差限.,rre r x

2、 为为 的的相对误差相对误差，记做，记做 .x 称称ex re 3 有效数字有效数字定义定义: 设设x为准确值，为准确值， 是是x的近似值，且的近似值，且x 12(0.) 10 ,mnxa aa 其中其中m为整数，为整数，110,naaa 为为0,1,9中一个数字中一个数字. 如果如果x 误差满足误差满足 即即 误差不超过误差不超过1|10,2m nxxx 某位的半个单位某位的半个单位. 称该位到称该位到 的第一位非零数的第一位非零数字为字为 的有效数字，即的有效数字，即 有有n位有效数字位有效数字.x x x 注注 当当 是是x的的 按四舍五入原则得到的近似按四舍五入原则得到的近似x 1na

3、 数，则数，则 具有具有n位有效数字位有效数字 .x 4.有效数字和相对误差之间的关系有效数字和相对误差之间的关系:定理定理1设设x的近似数为的近似数为120.10 ,mnxa aa 如果如果 具有具有n位有效数字位有效数字,则则 的相对误差限为的相对误差限为x x (1)11|102nrxxexa 其中其中 ；反之，；反之， 10a (1)11|102(1)nrxxexa 如果如果 的相对误差满足的相对误差满足x 则则 至少具有至少具有n位有效数字位有效数字.x 5. 5. 条件数与病态问题条件数与病态问题定义定义 对于前向误差和后向误差，其相对误差对于前向误差和后向误差，其相对误差之比的绝

4、对值称为计算函数之比的绝对值称为计算函数f(x)的的条件数条件数( ( )( *)( *)*(*)*pyf xf xf xyCxxxxx 近似计算公式为近似计算公式为*( *)( *)pxfxCf x 当条件数较大时，可能会出现前向误差当条件数较大时，可能会出现前向误差很大的情况，通常称这类问题为很大的情况，通常称这类问题为病态问题病态问题.6. 6. 数值计算中需要注意的问题数值计算中需要注意的问题(1) 避免两个相近的数相减避免两个相近的数相减(2) 防止大数防止大数“吃掉吃掉”小数小数(3) 简化计算步骤，减少运算次数简化计算步骤，减少运算次数(4) 避免误差的积累与传播避免误差的积累与

5、传播误差呈递增形式误差呈递增形式,称这类算法是称这类算法是不稳定的不稳定的;误差逐步递减，这样的算法称为误差逐步递减，这样的算法称为稳定的算法稳定的算法7. 二分法二分法令令 取区间中点取区间中点00,aa bb0002abx 若若00() ()0f af x 则则1010,;aa bx若若00() ()0f bf x 则则1010,;ax bb若若00() ()0f af x 则已得到方程的根则已得到方程的根.问题：问题：( )0f x 为一非线性方程，为一非线性方程， , a b* , . . ( *)0.xa b s t f x为有根区间，求为有根区间，求 基本思想：基本思想： 如此下去

6、如此下去,不断缩小有根区间不断缩小有根区间,直到达到给定直到达到给定精度精度.因此有因此有0011,kka ba bab()/2kkkxab那么令那么令即即*limkkxx 并且序列并且序列 的收敛性与初始区间无关的收敛性与初始区间无关.kx所以所以二分法是大范围收敛二分法是大范围收敛的的.1|*| ()/2()/2kkkkxxbaba 则则预先给定误差精度预先给定误差精度 当当12kba 时时, 停止计算停止计算算法步骤算法步骤(1) 取初始有根区间取初始有根区间a,b,和精度要求和精度要求 ； (2) 若若 则停止计算；则停止计算；,2ba (3) 取取 ，若，若2bax ( ) ( )0

7、,f a f x 则则 b=x；否则否则a=x；(4) 转转(2).例例 用二分法计算方程用二分法计算方程 在在0, 0.5内具有内具有5位有效数字的根，它的绝对误差限位有效数字的根，它的绝对误差限是多少？至少需要对分多少次才能达到精度？是多少？至少需要对分多少次才能达到精度？4310 xx解解 由有效数字定义可知，绝对误差限是由有效数字定义可知，绝对误差限是5110 .2 要使要使5111022kba 52111022k 16k例例 用二分法计算方程用二分法计算方程 在在1, 2内内具有具有4位有效数字的根，它的绝对误差限是位有效数字的根，它的绝对误差限是多少？至少需要对分多少次才能达到精度

8、？多少？至少需要对分多少次才能达到精度？310 xx解解 由有效数字定义可知，绝对误差限是由有效数字定义可知，绝对误差限是3110 .2 要使要使3111022kba 31102k 10k二分法的优缺点二分法的优缺点(1) 简单易用，大范围收敛简单易用，大范围收敛优点：优点：(2) 对对 f (x) 要求不高，只要连续即可要求不高，只要连续即可缺点：缺点：(1) 无法求复根及重根无法求复根及重根(2) 收敛速度太慢收敛速度太慢 第二章第二章 解非线性方程的数值方法解非线性方程的数值方法一、一、 二分法二分法二、二、 迭代法迭代法三、三、 Newton法法 将给定方程将给定方程f(x)=0转化成

9、等价方程转化成等价方程 ( ) ( 1 2. )xx 二、二、 迭代法迭代法1 迭代法的基本思想迭代法的基本思想:若若x*是是f(x)的根的根, 即即 ,则有则有*()0f x *()xx 称称x*为函数为函数 的一个的一个不动点不动点.( )x 设设x0是一个近似解，可以构造序列是一个近似解，可以构造序列1 0,1,2 ( (2.2 ) ) kkkxx 迭代法迭代法(2.2)称为简单迭代法或单点迭代法称为简单迭代法或单点迭代法.称函数称函数 为为迭代函数迭代函数.( )x 简单迭代法简单迭代法(2.2), 若迭代序列若迭代序列xk保持有界保持有界,全在全在 定义域内定义域内;且有且有( )x

10、 *limkkxx 称迭代法是称迭代法是收敛的收敛的. 此时此时, ,由由 的连续性可得的连续性可得即即 x* = (x*)，即即x*是是 的不动点，也就是的不动点，也就是f (x)的零点。的零点。 1limlim(lim)kkkkkkxxx ，建立迭代格式 解：改写方程为解：改写方程为 求方程x3-2x-3=0在1,2内的根.例例 332 xx3123kkxx取初值x0=1.9 ,计算得：kxkkxk0123451.91.894536471.893521141.893332331.893297221.893290696789101.893289471.893289251.893289211.

11、893289201.89328920 由计算结果有|x10 x9|10-8, 因此可取 x* x10 1.89328920 。 方程也可改写成x=(x3-3)/2, 建立迭代格式 xk+1=(xk3-3)/2 , k=0,1,2, 仍取初值x0=1.9, 则有 x1=1.9295, x2=2.0917, x3=3.0760, x4=13.0529xk, 此迭代格式是发散的。30111.51,(0,1,2,). kkxxxk （），kxk012345671.51.357211.330861.325881.324941.324761.324731.3247231012(2) 1,1.5, 2.37

12、5,12.39, .kkxxxxx 例例 求求x3-x-1=0在在1.5附近的根附近的根x*解解xyy = xxyy = xxyy = xxyy = xx*x*x*x*y= (x)y= (x)y= (x)y= (x)x0p0 x1p1x0p0 x1p1 x0p0 x1p1x0p0 x1p1x2 不动点迭代法的几何解释不动点迭代法的几何解释2 收敛定理和误差估计收敛定理和误差估计定理定理1 设设 在在a, b上有连续的一阶导数上有连续的一阶导数,且且( )x (1) 有有 , ,xa b ( );axb (2)|( ) |1,xL , ;xa b 则有则有(1) 函数函数 在在a ,b上存在唯一

13、的不动点上存在唯一的不动点x*( )x 由迭代公式由迭代公式(2.2)得到的序列得到的序列(2)0 , ,xa bkx都收敛到方程的根都收敛到方程的根x*10|1kkLxxxxL (3)*11|1kkkxxxxL (4)证明证明:(1) 先证明存在性先证明存在性, 令令( )( )h xxx 由条件由条件(1)可知可知( )( )0, ( )( )0h aaah bbb由连续函数根的存在定理由连续函数根的存在定理,必必* , . .xa b s th(x*)=0，即即*()xx 再证明唯一性再证明唯一性,设设 也是一个解也是一个解,即即( )xx x 那么那么*| | ()( ) | |( )

14、() |xxxxxxL xx 因为因为L1, 所以有所以有*xx (2) 由条件由条件(2)和和Lagrange中值定理得中值定理得*1| | ()()| kkxxxx 因为因为L1, 所以当所以当 时时, 有有 k 0.kL (3)和和(4) 利用利用(2)的方法的方法*1|( )()| kxx *1|kL xx 2*2| kLxx *0|kLxx1121| | | kpkkpkpkpkpkkxxxxxxxx 10|1kkpkLxxxxL 2111210| |kkkkkkkxxL xxLxxLxx1211(1)|1|1ppkkkkLLLxxxxL 令令 即分别得即分别得,p *11|1kkk

15、xxxxL *10|1kkLxxxxL 定理定理1的几点说明的几点说明(i) 通常将条件通常将条件(1)称为映内性；称为映内性；(ii) 条件条件(2)也可以改为：存在常数也可以改为：存在常数L且且0L1使得使得| ( )( ) |, , xyL xyx ya b结论仍然成立结论仍然成立, 这个条件通常称为压缩性；这个条件通常称为压缩性；(iii) 结论结论(3)说明说明 的误差大概是常数的误差大概是常数*|kxx 乘上乘上Lk, 但是一般但是一般L未知未知;(iv) 结论结论(4)说明说明 与与 有关有关*|kxx 1|kkxx 因此得到迭代法的终止条件因此得到迭代法的终止条件1|kkxx

16、3 一般迭代法的算法一般迭代法的算法算法：算法：(1) 取初始点取初始点x0,最大迭代次数最大迭代次数N和精度要求和精度要求, 并置并置k=0；(2) 计算计算1();kkxx (3) 若若 则停止计算；则停止计算；1|,kkxx (4) 若若k=N, 则停止计算；否则则停止计算；否则k=k+1, 转转(2). 求方程xex-1=0在0.5附近的根,精度要求=10-3。解解 可以验证方程xex-1=0在区间0.5,0.61内仅有一个根。例例 改写方程为x=e-x ,建立迭代格式, 2 , 1 , 0,1kexkxk由于(x)=e-x ,在0.5,0.61上有|(x)|e-0.50.6 1，且(

17、x)0.5,0.61，所以迭代法收敛。 取x0=0.5,得kxk|xk-xk-1|kxk|xk-xk-1|0123450.50.606530.545240.579700.560060.571170.106530.061290.034460.019640.011116789100.564860.568440.566410.567560.566910.006310.003580.002030.001150.00065 所以,取近似根x*x10=0.56691满足精度要求。 如果精度要求为=10-5, 则由LxxLkln)1 (ln0195.196 . 0ln10653. 0104 . 0ln5可知

18、,需要迭代20次。 实际上,方程在0.55,0.6上有唯一根，而此时|(x)|e-0.550.581. 若取L=0.58，则有 注意：这里迭代次数20是充分的但不是必要的。LxxLkln)1 (ln0150.42 10lnln0.5818.60.10653可知, 只需迭代19次。4 局部收敛定理局部收敛定理迭代序列迭代序列xk在区间在区间a,b上的收敛性通常称为上的收敛性通常称为全局收敛性全局收敛性. 实际应用只在不动点实际应用只在不动点x*的邻近考的邻近考察收敛性，称为察收敛性，称为局部收敛性局部收敛性.定义定义 设设 有不动点有不动点x*,如果存在如果存在x*的某个邻域的某个邻域( )x

19、*:|,Rxx 对任意的对任意的 迭代迭代(2.2)产生的产生的0 xR 序列序列 且收敛到且收敛到x*,则称则称(2.2)局部收敛局部收敛.kxR 证明证明 由连续函数的性质由连续函数的性质,存在存在x*的某个邻域的某个邻域*:|,Rxx 对任意的对任意的 有有xR |( ) |1xL 而而*| ( )| | ( )() | |xxxxL xxxx根据定理根据定理1可以断定迭代过程可以断定迭代过程(2.2)对任意初对任意初值值 均收敛均收敛.0 xR 定理定理2 若若x*为迭代函数为迭代函数 的不动点的不动点, 在在x*( )x ( )x 的某个邻域内有连续导数的某个邻域内有连续导数,且且

20、则则*|() | 1,x 迭代法迭代法(2.2)局部收敛局部收敛.21(1) 3( *)2 311; kkkxxxx ，13(2) ( *)1; kkxxx ，2113(3) (3)( *)10.134; 42kkkxxxx ，113(4) ()( *)0.2kkkxxxx ，例例 只用四则运算不用开方求方程只用四则运算不用开方求方程x2-3=0的根的根*3x 解解kxk迭代法迭代法(1) 迭代法迭代法(2) 迭代法迭代法(3)迭代法迭代法(4)0123 ? x0 x1 x2 x3 ?23987?21.521.5?21.751.734751.732631?21.751.7321431.7320

21、51?(1)和和(2)发散，发散， (3)和和(4)收敛收敛.例例 设设2( )(5),xxa x 试讨论试讨论a的取值范围的取值范围使迭代公式使迭代公式(2.2)局部收敛到局部收敛到*5x 解解 因为因为2( )(5)xxa x 所以所以 由定理由定理2可知只需可知只需( )12,xax *|() | 1x 即即|12 5 | 1a105a 所以当所以当 时时,迭代公式收敛迭代公式收敛.105a5 迭代收敛的阶迭代收敛的阶则称该迭代为则称该迭代为p 阶收敛阶收敛. . ( (C为常数为常数) )(1) (1) 当当p =1时称为时称为线性收敛线性收敛，此时，此时00C 1和和p =1且且C=

22、0时称为时称为超线性收敛超线性收敛. .定义定义 设迭代设迭代 收敛到收敛到 的不动的不动点点x*. 记记ek = xk x*，若若1|lim0|kpkkeCe 1()kkxx ( )x 例例: (1) 二分法线性收敛二分法线性收敛;(2)不动点迭代中，若不动点迭代中，若 则则线性收敛线性收敛*()0 x 解解: (2) 不动点迭代中第不动点迭代中第k+1步的误差为：步的误差为：*11| |*| |()()|kkkexxxx*1lim| lim()()1kkkkkexe *|()|(,)kkkkxxxx *|()|(,)kkkkexx *(1)*()*(1) (),(2) ()()()0,(3

23、) ()0ppxxxxxx ()*11lim()!pkpkkexep 则则定理定理3 设迭代设迭代 若若 在在x*的某的某1(),kkxx ()( )px 邻域内连续并满足邻域内连续并满足即该迭代法是即该迭代法是p阶收敛的。阶收敛的。*1()*()()()()() .()!kkkppkkxxxxxxxxp 证明：证明： 根据泰勒展开有根据泰勒展开有( )*1()()!ppkkkxxxxp ()*11lim()!pkpkkexep 6 迭代加速迭代加速若若 则迭代公式则迭代公式(2.2)只是线性收敛。只是线性收敛。*()0,x 迭代加速方法可对线性收敛的简单迭代迭代加速方法可对线性收敛的简单迭代

24、法起到加速作用。法起到加速作用。取初始点取初始点x0,令令 那么那么00()yx *00*0*0()()( )()()yxxxxxL xx *00000111()1LxyxLLLyyxL 由此得加速迭代公式由此得加速迭代公式1()1kkkkLxyyxL 此加速法的优点：此加速法的优点：迭代速度快；迭代速度快；此加速法的缺点：此加速法的缺点：迭代公式中有待定的迭代公式中有待定的L,使用不方便。使用不方便。令令 得到得到0000(),()yxzy*0000(),()yxL xxzxL yx*00*00yxxxzxyx2*000000()2yxxxzyx Steffensen迭代加速法迭代加速法*2

25、*000()()()yxzxxx由此得由此得Steffensen加速法加速法21(),()()2kkkkkkkkkkkyxzyyxxxzyx 0,1,k Steffensen加速法是平方收敛的加速法是平方收敛的.注注：果第：果第k步发生步发生zk-2yk+xk=0, 就终止计算就终止计算, 取取x* xk 。 分别用简单迭代法和Steffensen加速算法例例求方程 在 附近的根。1.60.99cosxx2 *(1.585471802)x 解：解：简单迭代法迭代公式简单迭代法迭代公式11.6 0.99coskkxx Steffensen迭代公式：迭代公式：21(),()()2kkkkkkkkk

26、kkyxzyyxxxzyx k简单迭代法简单迭代法kSteffensen迭代法迭代法xk|xk-xk-1|xk|xk-xk-1|012341.570801.61.571091.599711.571380.02920.028910.028620.028330121.57079631.585472581.585471800.014676280.00000078取取x0= /2, 计算结果如下计算结果如下: Newton迭代法是求方程根的重要方法迭代法是求方程根的重要方法之一之一,其最大优点是在方程的单根附近具有其最大优点是在方程的单根附近具有平方收敛平方收敛,而且而且Newton迭代法还可用来求方

27、迭代法还可用来求方程的重根、复根及非线性方程组。程的重根、复根及非线性方程组。三、三、 Newton法法1 Newton法基本思想法基本思想2( )( )()()()()2!kkkkff xf xfxxxxx 设设xk是是f (x)=0的近似根的近似根, ,将将f (x)在在xk一阶一阶Taylor 展开展开: :( ( 在在xk和和x之间之间) )*0()f x *()()()kkkf xfxxx *()()kkkf xxxfx 当当 f (x) 0时时, , , ,于是于是 即为即为Newton迭代公式迭代公式.1()()kkkkf xxxfx xyx*xkxk+1Newton法的几何意义

28、法的几何意义()()()kkkyf xfxxx Newton法的本质就是不断用切线来近似曲法的本质就是不断用切线来近似曲线，因此线，因此Newton法也成为法也成为切线法切线法.1()0()kkkkf xyxxfx 2 Newton法的算法法的算法(1) 取初始点取初始点x0,最大迭代次数最大迭代次数N和精度要求和精度要求置置k=0;(2) 计算计算1();()kkkkf xxxfx (3) 若若 则停止计算则停止计算;1|kkxx (4) 若若k=N则停止计算则停止计算;否则置否则置k=k+1,转转(2).Newton 法可以看作下面的不动点迭代：法可以看作下面的不动点迭代：1()kkxx

29、其中其中( )( )( )f xxxfx 2( ) ( )( )( )f x fxxfx (x*) = 0 (若若f(x*)=0,f(x*)0，即，即x*是单根）是单根）Newton 法至少法至少二阶局部收敛二阶局部收敛3 Newton法收敛性法收敛性定理定理4 设设f(x)在其零点在其零点x*的某个邻域内二阶连的某个邻域内二阶连续可导且续可导且f(x) 0，则存在，则存在x*的的某个某个 邻域邻域N(x*) =x*- , x* + , 使得对使得对 x0 N(x*)，Newton法产生的序列以法产生的序列以不低于不低于二阶的收敛速度收敛二阶的收敛速度收敛到到 x* . .证明证明 (略略)N

30、ewton 法也可以看作一类特殊的加速迭代法也可以看作一类特殊的加速迭代1()1()1()1()kkkkkkxxxxxx （ (x) = x - -f (x)）取x0=0.5,计算结果如下:例例4 用Newton迭代法求方程xex-1=0在0.5附近的根,精度要求=10-5. 解解 Newton迭代格式为11,0,1,2,1kkkkxkkkxxkxkkkx exxex exexkx kxk(xk)|xk-xk-1|012340.50.571020440.567155570.567143290.56714329-0.175639360.010747510.000033930.0000000003

31、0.00000000030.071020440.003864870.000012280.00000000 从结果可见从结果可见 ,Newton迭代法迭代迭代法迭代3次已获得次已获得精确到小数点后五位的近似解精确到小数点后五位的近似解,迭代迭代4次已获得次已获得精确到小数点后八位的近似解精确到小数点后八位的近似解.与一般迭代法比与一般迭代法比较可见较可见Newton迭代法收敛的确实快迭代法收敛的确实快.例 设计一个二阶收敛算法计算设计一个二阶收敛算法计算 (a 0).a解：转化为求解：转化为求 x2-a = 0 的正根的正根Newton 迭代：迭代：221()()22kkkkkkkkkf xxa

32、xaxxxfxxx 212kkkxaxaax 22222kkkkkxaxaxaxx 1212kkkxaxxa 12 a二阶收敛二阶收敛取取x0=1.7，计算得：，计算得：2133222kkkkkkxxxxxx 所以取x3=1.732050808 3kxk|xk-xk-1|01231.71.7323529411.7320508341.7320508080.0323529410.0003021070.000000026例例 用Newton迭代法求解解 对方程x2-3=0应用Newton迭代法： 的近似值,要求=10-7。3设设x*是是f(x)的的m(m 2)重根重根, Newton法是否收敛？法是

33、否收敛？*(1)*()*()()()0, ()0mmf xfxfxfx Taylor 展式展式()*11( )()()!mmf xfxxm ()*121( )()()(1)!mmfxfxxm ()*231( )()()(2)!mmfxfxxm 4 重根情况重根情况*()*()*2132()*1211()()()()!(2)!lim1()()(1)!mmmmxxmmfxxfxxmmfxxm 所以所以Newton 迭代：迭代：( )( )( )f xxxfx *2*( ) ( )()lim( )lim( )xxxxf x fxxxfx 111m 线性收敛线性收敛, 且重数且重数m越高越高, 收敛越

34、慢收敛越慢.提高收敛速度提高收敛速度但但m通常无法预先知道！通常无法预先知道！法一：取法一：取 ( )( )(2)( )f xxxmmfx *()0 x 二阶收敛二阶收敛注注: 推导过程与前面类似推导过程与前面类似.法二：将求法二：将求f(x)的重根转化为求另一个函数的重根转化为求另一个函数 的单根的单根. . 构造针对构造针对 (x) 的具有二阶收敛的的具有二阶收敛的Newton迭代：迭代： 2( )( ) ( )( )( )( )( ) ( )xf x fxxxxxfxf x fx 令令 ，则，则x*是是 (x)的单重根的单重根. . ( )( )( )f xxfx 例例 取初始点取初始点x0=1.5, 分别用分别用Newton法和求重根法和求重根的两种方法计算的两种方法计算 f(x)=(x+ +1)(x- -1)2=0解解 (1) Newton法迭代公式法迭代公式1(1)(1)31kkkkkxxxxx k012345xk1.51.2727 1.1441 1.0744 1.0378