数值分析期末复习要点总结PPT学习教案

1、会计学1数值分析期末复习要点总结数值分析期末复习要点总结22为准确值为准确值x的一个近似值，称的一个近似值，称 *x*)(xxxe*x绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字若若 *)(xxxe*x 的的绝对误差限绝对误差限，简称，简称误差限误差限.通常称通常称为近似值为近似值定义定义2 设设*x)(*xer xxxxxexer*(1-3)记为记为 即即准确值之比为近似值准确值之比为近似值*x为近似值为近似值的的绝对误差绝对误差，简称，简称误差误差.(1-1)称绝对误差与称绝对误差与为准确值为准确值 x 的近似值，的近似值，的相对误差，的相对误差，(1-2)定义定义1 1 设设

2、第2页/共87页3由于在计算过程中准确值由于在计算过程中准确值 x 总是未知的，总是未知的， *xxxxxexer绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字故一般取相对误差为故一般取相对误差为 则称则称 为为 的的相对误差限相对误差限.rrrxxexe*r*x使得使得(1-4)如果存在正数如果存在正数第3页/共87页4如果近似值如果近似值 *xn1021*x准确到小数点后第准确到小数点后第n位位,并从第一个非零数字到并从第一个非零数字到这一位的所有数字均称为这一位的所有数字均称为有效数字有效数字.绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字 有效数字有效数字的误差限是

3、的误差限是则称则称*.x 1 4144142136. 1*x取前八位数得近似值取前八位数得近似值 例如，例如，.,x 21 414213562取前四位数得取前四位数得.,3121 4141021.414有有4位有效数字位有效数字.7121 41421361021.4142136有有8位有效数字位有效数字.第4页/共87页55*xmnaaax10. 021*(1-5), 2 , 1, 01iaai 一般地，如果近似值一般地，如果近似值其中其中m为整数，为整数， 绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字为为0 0到到9 9之间的整数之间的整数. . nmxx1021*如果如果(1-

4、6)则称近似值则称近似值*x有有n位有效数字位有效数字.*.x 11 4140 1414 10例如例如.31 41121 414101022有有4位有效数字位有效数字.故故*.x 1 414的规格化形式为的规格化形式为第5页/共87页66绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字若若x的近似值的近似值,10. 021*mnaaax111021na至少具有至少具有n位有效数字位有效数字.*xr1110121nra*x)0(1a有有n位有效数字，位有效数字， 则则误差限误差限. 反之，反之，的相对误差的相对误差定理定理1.11.1为其相对为其相对满足满足若若则则第6页/共87页77(

5、1-12)(1-11)(1-13) 22121211212121)()()(xexxxxexxxxxexexexxerrr 2121211221xexexxexexxexxxerrr1112222211221rrrxxee xe xxxxxeexexx 数值计算中误差的传播数值计算中误差的传播 第7页/共87页8例例设近似数设近似数1.557a 31( )102e a( )( )re aeaa是某真值是某真值 x 经四舍五入经四舍五入所得所得,试求其绝对误差限和相对误差限试求其绝对误差限和相对误差限.解解由于由于a经四舍五入得到经四舍五入得到,故故311021.57743.170577 108

6、第8页/共87页99411()10 ,2e x126.1025,80.115xx121 2,xxx x例例1:2, 求求数值计算中误差的传播数值计算中误差的传播 1.经四舍五入得经四舍五入得试问它们有几位有效数字？试问它们有几位有效数字？的绝对误差限的绝对误差限.解解故故12,xx分别具有分别具有5位有效数字位有效数字1212()()()e xxe xe x12()()e xe x431110100.0005522321()10 ,2e x1221122112()()()()()e x xx e xx e xxe xx e x431180.115106.102510220.007057第9页/

7、共87页1010数值计算中误差的传播数值计算中误差的传播 例例2:2:要使要使6的近似值的相对误差限小于的近似值的相对误差限小于0.1%,应取应取取几位有效数字取几位有效数字解解: :263,6的首位数是的首位数是2,12a 设近似数设近似数*x有有n位有效数字位有效数字,只须取只须取n使使111100.1%2na 即即11100.1%22n 1100.4%,n 取取n=4,即取即取4位有效数字位有效数字,近似值的相对误差限小于近似值的相对误差限小于0.1%.1010,0.4%n10lg3.39790.4%n 第10页/共87页11数值计算中的一些原则数值计算中的一些原则1.1.避免两个相近的

8、数相减避免两个相近的数相减2.2.避免大数避免大数“吃吃”小数的现象小数的现象3.3.避免除数的绝对值远小于被除数的绝对值避免除数的绝对值远小于被除数的绝对值4.4.要简化计算，减少运算次数，提高效率要简化计算，减少运算次数，提高效率5. 要有数值稳定性要有数值稳定性,即能控制舍入误差的传播即能控制舍入误差的传播例如例如 为提高数值计算精度为提高数值计算精度, 当正数当正数x充分大时充分大时,应将应将2121xx( 2121)( 2121)2121xxxxxx 22121xx 改写为改写为22121xx11第11页/共87页12例例 如何计算下列函数值才比较精确如何计算下列函数值才比较精确(1

9、)11121xx1x 11121(12 )(1)xxxxx对对解解 (1) 要使计算准确要使计算准确, 应避免两个相近的数相减应避免两个相近的数相减(2)11xxxx对对1x (2) 要使计算准确要使计算准确, 应避免两个相近的数相减应避免两个相近的数相减故变换所给公式故变换所给公式故变换所给公式故变换所给公式1111()()1111xxxxxxxxxxxxxxxx211xxxxx12第12页/共87页13已知函数已知函数 y = f(x) 在在 a, b 上有定义，且已经测得在点上有定义，且已经测得在点 a x0 x1 xn b 处的函数值为处的函数值为 y0 = f(x0)， ，yn =

10、f(xn)如果存在一个如果存在一个简单易算简单易算的函数的函数 P(x)，使得，使得 P(xi) = f(xi)，i = 1, 2, . , n则称则称 P(x) 为为 f(x) 的的插值函数插值函数插值区间插值区间插值节点插值节点求插值函数求插值函数 P(x) 的方法就称为的方法就称为插值法插值法插值节点插值节点无需递无需递增排列增排列，但必须，但必须确保确保互不相同互不相同！插值条件插值条件第13页/共87页14基函数法通过基通过基函数来构造函数来构造插值多项式的方法插值多项式的方法就就称为称为基函数基函数插值插值法法Zn(x) = 次数不超过次数不超过 n 的多项式的全体的多项式的全体记

11、记n+1 维线性空间维线性空间设设 z0(x), z1(x), . , zn(x) 构成构成 Zn(x) 的一组基，则插值多项式的一组基，则插值多项式P(x) = a0z0(x) + a1z1(x) + + anzn(x)寻找合适的基函数寻找合适的基函数 确定插值多项式在这组基下的表示系数确定插值多项式在这组基下的表示系数基函数法基本步骤基函数法基本步骤第14页/共87页15Lagrange插值基函数设设 lk(x) 是是 n 次多项式，在插值节点次多项式，在插值节点 x0 , x1 , , xn 上满足上满足1,()0,kjjklxjk 则称则称 lk(x) 为节点为节点 x0 , x1 ,

12、 , xn 上的上的拉格朗日插值基函数拉格朗日插值基函数第15页/共87页16两种特殊情形 n=10110 01 1010110( )( )( )xxxxL xy lxy l xyyxxxx 线性插值多项式（一次插值多项式）线性插值多项式（一次插值多项式）n=2020112012010210122021()()()()()()()()()()()()xxxxxxxxxxxxyyyxxxxxxxxxxxx 抛物线插值多项式（二次插值多项式）抛物线插值多项式（二次插值多项式）2( )Lx第16页/共87页17例：例：已知函数已知函数 y = lnx 的函数值如下的函数值如下解解：x0.40.50.

13、60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试分别用试分别用线性插值线性插值和和抛物线插值抛物线插值计算计算 ln 0.54 的近似值的近似值线性插值线性插值：取取 x0=0.5, x1=0.6 得得将将 x=0.54 代入可得：代入可得：011010110( )0.18231.6046xxxxL xyyxxxxx ln 0.54 L1(0.54) =-0.6202为了减小截断误差，通常选取插值点为了减小截断误差，通常选取插值点 x 邻接的插值节点邻接的插值节点第17页/共87页18抛物线插值抛物线插值：取取 x0=0.4, x1=0.5, x2=

14、0.6, 可得可得ln 0.54 L2(0.54) =-0.6153 ln 0.54 的精确值为：的精确值为：-0.616186可见，抛物线插值的精度比线性插值要高可见，抛物线插值的精度比线性插值要高Lagrange插值多项式简单方便，只要取定节点就可写插值多项式简单方便，只要取定节点就可写出基函数，进而得到插值多项式，易于计算机实现。出基函数，进而得到插值多项式，易于计算机实现。第18页/共87页19l0(x) , l1(x) , , ln(x) 构成构成 Zn(x) 的一组的一组基基性质性质注意注意l0(x) , l1(x) , , ln(x) 与插值节点有关，与插值节点有关，但与函数但与

15、函数 f(x) 无关无关lk(x) 的表达式的表达式0110111,()()( ) ()()()()()()kknkkkknjjj kkknjkkxxxxxlxxxxxxxxxxxxxxxx 由构造法可得由构造法可得第19页/共87页20如何估计误差 )()()(xLxfxRnn 插值余项插值余项定理定理设设 f(x) Cna, b ( n 阶连续可微阶连续可微 )，且，且 f (n+1)(x)在在 (a, b) 内存在，则对内存在，则对 x a,b，有，有(1)1()( )( )( )( )(1)!nxnnnfRxf xLxxn 其中其中 x (a, b) 且与且与 x 有关有关,101(

16、)()()()nnxxxxxxx 第20页/共87页21l 余项公式只有当余项公式只有当 f(x) 的高阶导数存在时才能使用的高阶导数存在时才能使用几点说明 l 计算插值点计算插值点 x 上的近似值时，应选取与上的近似值时，应选取与 x 相近插值节点相近插值节点10( ) (1)!nnniiMRxxxn 如果如果 ，则，则(1)1( )nnfxM l x 与与 x 有关，通常无法确定有关，通常无法确定, 实际使用中通常是估计其上界实际使用中通常是估计其上界第21页/共87页22例：例：已知函数已知函数 y = lnx 的函数值如下的函数值如下x0.40.50.60.70.8lnx-0.9163

17、-0.6931-0.5108-0.3567-0.2231试估计试估计线性插值线性插值和和抛物线插值抛物线插值计算计算 ln 0.54 的误差的误差解解线性插值线性插值 (2)2( )4f (2)101( )( )()()2fR xxxxx 1(0.54)2(0.540.5)(0.540.6)0.0048Rx0=0.5, x1=0.6, (0.5, 0.6)第22页/共87页23为什么 Newton 插值Lagrange 插值简单易用，但若要增加一个节点时，全部基插值简单易用，但若要增加一个节点时，全部基函数函数 lk(x) 都需重新计算，不太方便。都需重新计算，不太方便。设计一个可以逐次生成插

18、值多项式的算法，即设计一个可以逐次生成插值多项式的算法，即 n 次插值多项式次插值多项式可以通过可以通过 n-1 次插值多项式生成次插值多项式生成 Newton 插值法插值法解决办法解决办法第23页/共87页24什么是差商设函数设函数 f(x)，节点，节点 x0 , , xn ()(),jiijjif xf xf x xxx f(x) 关于点关于点 xi , xj 的的一阶差商一阶差商,jkijijkkif xxf x xf x xxxx f(x) 关于点关于点 xi , xj , xk 的的二阶差商二阶差商101010,kkkkf xxf xxf xxxxx k 阶差商阶差商差商的一般定义差

19、商的一般定义第24页/共87页25l k 阶差商与阶差商与 k 阶导数之间的关系：阶导数之间的关系：若若 f (x) 在在 a,b 上上 具有具有 k 阶导数，则至少存在一点阶导数，则至少存在一点 (a, b)，使得使得( )01( ),!kkff xxxk 第25页/共87页26如何巧妙地计算差商差商表差商表xi(xi)一阶差商二阶差商三阶差商n 阶差商x0 x1x2x3xn(x0)(x1)(x2)(x3)(xn)x0, x1x1, x2x2, x3xn-1, xnx0, x1, x2x1, x2, x3xn-2, xn-1, xnx0, x1, x2, x3xn-3, xn-2, xn-1

20、, xnx0, x1, xn第26页/共87页27例：例：已知已知 y = (x) 的函数值表，的函数值表，试计算其各阶差商试计算其各阶差商i0123xi-2-112f(xi)531721解：解：差商表如下差商表如下xi(xi)一阶差商二阶差商三阶差商-2-112531721-2743-1-1第27页/共87页28 f (x) = Nn(x) + Rn(x) 10102011()()()( )()nniinaa xxaxxxxaxNxx 001 , . ,().()( )nnnnf x xxxRxxxxxx Nn(x) 是是 n 次多项式次多项式Nn(xi) = f (xi)，i = 0, 1

21、, 2, , n重要性质重要性质Nn(x) 是是 f (x) 的的 n 次插值多项式次插值多项式nixxfaxfaii, 2 , 1 , ),(000 其中其中第28页/共87页29Newton 插值多项式与 Lagrange 插值多项式f (x) 在在 x0 , x1 , , xn 上上的的 n 次插值多项式是唯一的！次插值多项式是唯一的！Nn(x) Ln(x)余项也相同余项也相同(1)000()()()(1)!nnnxniiiiff x,x , .,xxxxxn (1)0()(1) !nxnff x,x , . ,xn !)()(0kfx,.,xfkk 将将 x 看作节点看作节点第29页/

22、共87页30例：例：已知函数已知函数 y = lnx 的函数值如下的函数值如下解解：取节点取节点 0.5, 0.6, 0.4 作差商表作差商表试分别用试分别用牛顿牛顿线性插值和抛物线插值计算线性插值和抛物线插值计算 ln 0.54 的近似值的近似值x0.40.50.60.70.8lnx-0.9163 -0.6931 -0.5108-0.3567-0.2231xi(xi)一阶差商二阶差商0.50.60.4-0.6931-0.5108-0.91631.82302.0275-2.0450N1(x) = -0.6931 + 1.8230(x-0.5)N1(0.54) = -0.6202N2(x) =

23、-0.6931 + 1.8230(x-0.5) - 2.0450(x-0.5)(x-0.6)N2(0.54) = -0.6153ex25.m插值节点无需递插值节点无需递增排列，但必须增排列，但必须确保互不相同！确保互不相同！第30页/共87页31( )( ) dbaI ff xx l 微积分基本公式：微积分基本公式：baaFbFxxf)()(d)(3) f (x) 表达式未知表达式未知，只有通过测量或实验得来的数据表，只有通过测量或实验得来的数据表l 但是在许多实际计算问题中但是在许多实际计算问题中(2) F(x) 难求！难求！甚至有时不能用初等函数表示。甚至有时不能用初等函数表示。 如如21

24、( )sin , xf xxex (1) F(x) 表达式较复杂表达式较复杂时，计算较困难。如时，计算较困难。如61( )1f xx 第31页/共87页32数值积分公式的一般形式数值积分公式的一般形式0( )d()nbiiaif xxA f x 求积节点求积节点求积系数求积系数机械求积方法机械求积方法l 将定积分计算转化成被积函数的将定积分计算转化成被积函数的函数值函数值的计算的计算l 无需求原函数无需求原函数l 易于计算机实现易于计算机实现一般地，用一般地，用 f(x) 在在 a, b 上的一些离散点上的一些离散点 a x0 x1 xn b 上的函数值的加权平均作为上的函数值的加权平均作为

25、f ( ) 的近似值，可得的近似值，可得第32页/共87页33定义定义：如果对于所有次数不超过：如果对于所有次数不超过 m 的多项式的多项式 f (x) ，公式，公式精确成立，但对某个次数为精确成立，但对某个次数为 m +1 的多项式不精确成立，则称的多项式不精确成立，则称该求积公式具有该求积公式具有 m 次代数精度次代数精度0( )d()nbiiaif xxA f x l 将将 f (x) = 1, x, x2, , xm 依次代入，公式精确成立依次代入，公式精确成立;l 但对但对 f (x) = xm+1 不精确成立。即：不精确成立。即：22110 d2mmnbmmiiaibaA xxxm

26、 ( k = 0, 1, , m )代数精度的验证方法代数精度的验证方法110 d1kknbkkiiaibaA xxxk 第33页/共87页34例：例：试确定系数试确定系数 Ai ，使得下面的求积公式具有尽可能高的使得下面的求积公式具有尽可能高的代数精度，并求出此求积公式的代数精度。代数精度，并求出此求积公式的代数精度。10121( )d ( 1)(0)(1)f xxA fA fA f 解：解：将将 f (x)1, x, x2 代入求积公式，使其精确成立，可得代入求积公式，使其精确成立，可得 1101222023302() /12 () / 20 () / 32/ 3AAAbaAAbaAAba

27、 解得解得 A0 =1/3, A1 =4/3, A2 =1/3。所以求积公式为。所以求积公式为3 )1()0(4)1( d)(11fffxxf 易验证该公式对易验证该公式对 f (x)x3 也精确成立，但对也精确成立，但对 f (x)x4 不精不精确成立，所以此求积公式具有确成立，所以此求积公式具有 3 次代数精度。次代数精度。第34页/共87页35设求积节点为：设求积节点为：a x0 x1 xn b 若若 f (xi) 已知，则可做已知，则可做 n 次多项式插值：次多项式插值：0( ) ()nniiiLxl x f x 其中其中( ) dbiiaAl xx 插值型求积公式插值型求积公式00(

28、 )( ) d( )d d()()bniiannbbiiaaiif xxxf xfxxxAxLl 误差：误差： ( )( ) d( ) dbbnnaaR ff xL xxRxx (1)01( )( )()()()(1)!nnnfRxxxxxxxn 其中其中abAnkk 0第35页/共87页36基于等分点的插值型求积公式基于等分点的插值型求积公式l 积分区间：积分区间：a, bl 求积节点：求积节点： xi = a + i h bahn l 求积公式：求积公式：( )0( ) d()()nbniiaif xxbaCf x ( )( )1( ) dbnniiaClxxba 00 dnnkk iht

29、ktbaik xath 001( 1)() d!n innkk itktn ini Cotes 系数系数Newton-Cotes 求积公式求积公式( )( )nnin iCC(1)(2)( )01nniiC第36页/共87页3721,21)1(1)1(0 CCn = 1:( ) ( )( )2babaf x dxf aTf b 代数精度代数精度 = 1梯形公式梯形公式n = 2:61,32,61)2(2)2(1)2(0 CCC2( ) ( )4 ()( )6ba babaf x dxf aff bS 代数精度代数精度 = 3抛物线公式抛物线公式Simpson公式公式n = 4:01234( )

30、7 ()32 () 12 ()32 ()7 ()90babaf x dxf xf xf xf xf xC 科特斯科特斯 (Cotes) 公式公式4/ )( ,abhhiaxi代数精度代数精度 = 5第37页/共87页38l 梯形公式梯形公式 (n=1) 的余项的余项31 ()( )12R fbaf ( , )a b l Simpson公式公式 (n=2) 的余项的余项4(4)1 ( )1802baR ff ( , )a b l Cotes 公式公式 (n=4) 的余项的余项6(6)8 ( )9454baR ff ( , )a b 第38页/共87页39q 提高积分计算精度的常用两种方法提高积分

31、计算精度的常用两种方法l 用用 复合公式复合公式l 用用 非等距节点非等距节点l 将积分区间分割成多个小区间将积分区间分割成多个小区间l 在每个小区间上使用低次牛顿科特斯求积公式在每个小区间上使用低次牛顿科特斯求积公式复合求积公式复合求积公式第39页/共87页40l 将将 a, b 分成分成 n 等分等分 xi , xi+1 ，其中，其中(i = 0, 1, , n)nabhhiaxi ,复合梯形公式复合梯形公式 111100( ) d( ) d ()()2iinnbxiiaxiihf xxf xxf xf x 11( )2()( )2niinhf af xfTb l 余项余项 310()12

32、niihR ff 2( )12bah f ( , )a b 第40页/共87页41复合复合 Simpson 公式公式 11211100( ) d( ) d ()4 ()()6iinnbxbiiiaxaiihf xxf xxf xf xf x 121101( )4()2()( )6nniiinihf af xf xf bS l 余项余项 51(4)0()2880niihR ff 4(4)( )2880bah f ( , )a b 性质性质：复合梯形公式和复合：复合梯形公式和复合Simpson 公式都是收敛公式都是收敛的，也都是稳定的。的，也都是稳定的。 第41页/共87页42例例2 分别用复化梯

33、形公式与复化分别用复化梯形公式与复化Simpson公式公式计算积分计算积分10 xIe dx解解 (1)用复化梯形公式用复化梯形公式, 截断误差为截断误差为复化求积公式复化求积公式的近似值，为使截断误差的绝对值不超过的近似值，为使截断误差的绝对值不超过411022(),12TbaRfhfa b ,0,1kxfxeex至少应将至少应将0,1的多少等份的多少等份.2211212ThRhfe24210,67.312nen故取故取 n=681121 112en4110 ,2第42页/共87页43(2)若用复化若用复化Simpson公式，截断误差为公式，截断误差为复化求积公式复化求积公式 SRf baf

34、hab,18044 44180SbaRfh f 44210 ,180en故取故取 n=641 0180h e411180en4110 ,0,124.1688n 12第43页/共87页441( ) ( )()nbkkakx f x dxA f x例例5 试确定求积公式试确定求积公式 kx)(xGaussGauss型求积公式型求积公式 具有具有 2n+1次代数精确度次代数精确度，Gauss型求积公式型求积公式.公式公式（7-42）称为带权函数称为带权函数为为Gauss点点，则称这组节点则称这组节点定义定义7.2如果一组节点如果一组节点,21baxxxn能使求积公式能使求积公式（7-42）的的代数精

35、确度代数精确度，Gauss型求积公式型求积公式.它是否是它是否是18 4482 ( 2)(0)2 (2)3f x dxfff第44页/共87页45448dx 解解19由于当由于当 4482 ( 2)(0)2 (2)3f x dxfff82 1283 f x分别取分别取231, ,x xx有有440 xdx423444112833x dxx82202 203 2281282 ( 2)02 2 33 即求积公式精确成立即求积公式精确成立.而当而当 4f xx44544412048,55x dxx434444104x dxx3382 ( 2)02 (2) 03 4485122 ( 2)02 (2)

36、33 20485因此因此,求积公式的代数精度为求积公式的代数精度为3.它不是它不是Gauss型求积公式型求积公式.p22第45页/共87页461计算计算f (x)在有解区间在有解区间a, b端点处的值端点处的值，f (a)，f (b)。2计算计算f (x)在区间中点处的值在区间中点处的值f (x1)。3判断若判断若f (x1) = 0，则则x1即是根，否则检验即是根，否则检验：（1）若若f (x1)与与f (a)异号异号，则知解位于区间则知解位于区间a, x1， b1=x1, a1=a;（2）若若f (x1)与与f (a)同号同号，则知解位于区间则知解位于区间x1, b， a1=x1, b1=

37、b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a, b), (a1, b1), , (ak, bk), 区间对分法区间对分法（二分法）（二分法）第46页/共87页474、当当11kkab时时)(211kkkbax5、则、则即为根的近似即为根的近似), 2 , 1()(211*1kabxxkk先验误差估计：先验误差估计：理论基础：理论基础：定理定理1：设函数设函数 f (x) 在区间在区间a, b上连续上连续，如果如果f (a) f (b) 0， 则方程则方程 f (x) = 0 在在a, b内至少有一实根内至少有一实根x*。 第47页/共87页485310

38、 xx 对分区间法对分区间法在在0, 0.5内的根内的根,要求误差不超过要求误差不超过例例6 6 试用对分区间法求方程试用对分区间法求方程2110 .2解解 令令5( )31f xxx则则(0)10,(0.5)0.5310ff 4( )530,fxx故在故在0,0.5内内5( )310f xxx 有唯一实根有唯一实根.为达到要求为达到要求()ln1ln2ban即即2(0.50)ln11021ln2n取取6n 计算结果见下表。计算结果见下表。202ln1015.64ln2 第48页/共87页49-0.2490230.1324158-0.05951970.0360497-0.01182140.01

39、2091010.000129230.250.3750.31250.343750.3281250.33593750.332031250.50.50.3750.3750.343750.343750.335937500.250.250.31250.31250.3281250.3281250123456nnanbnx)(nxf对分区间法对分区间法5( )31f xxx故故60.33203125x 即为符合精度要求的解即为符合精度要求的解.21第49页/共87页50q 基本思想l 构造构造 f (x) = 0 的一个等价方程：的一个等价方程： ( )xx (x) 的不动点的不动点f (x) = 0 x

40、= (x)等价变换等价变换f (x) 的零点的零点第50页/共87页51q 具体过程l 任取一个迭代初始值任取一个迭代初始值 x0 ，计算，计算得到一个迭代序列：得到一个迭代序列： x0，x1，x2，. . . ，xn，. . . 1()kkxx k = 0, 1, 2, . . 几何含义：几何含义：求曲线求曲线 y = (x) 与直线与直线 y = x 的交点的交点第51页/共87页52设设 (x) 连续，若连续，若 收敛，即收敛，即 ，则，则 1limlim ()limkkkkkkxxx lim*kkxx 0kkx *( *)xx ( *)0f x 即即q 收敛性分析性质：性质：若若 ，则

41、不动点迭代，则不动点迭代收敛收敛，且，且 x* 是是 f(x)=0 的解；否则迭代法的解；否则迭代法发散发散。lim*kkxx 第52页/共87页53定理定理：设设 (x) Ca,b 且满足且满足证明：板书证明：板书(1)对任意的对任意的 x a,b 有有 (x) a,b(2)存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy则则 (x) 在在 a,b 上存在上存在唯一的不动点唯一的不动点 x*解的存在唯一性解的存在唯一性第53页/共87页54定理定理：设设 (x) Ca,b 且满足且满足(1)对任意的对任意的 x a,b 有有 (x) a,b(2

42、)存在常数存在常数 0L1，使得任意的，使得任意的 x, y a,b 有有( )( )xyL xy则对任意初始值则对任意初始值 x0 a,b，不动点迭代，不动点迭代 xk+1= (xk) 收敛，且收敛，且不动点迭代的收敛性不动点迭代的收敛性11011kkkkLLxxxxxxLL 第54页/共87页55不动点迭代的收敛性不动点迭代的收敛性若若 (x) C1a,b 且对任意且对任意 x a,b 有有 | (x)| L1则上述定理中的结论成立。则上述定理中的结论成立。收敛性结论表明：收敛性结论表明：收敛性与初始值的选取无关收敛性与初始值的选取无关全局收敛全局收敛第55页/共87页56例：例：求求 f

43、(x) = x3 x 1=0 在区间在区间 1, 2 中的根中的根 3( )1xx 231( )(1)3xx 31( )0.2513x (1)1( )2x (1,2)x 3( )1xx 2( )3xx ( )1x (2)0( )7x (1,2)x ex71.m第56页/共87页57定义定义：设设 x* 是是 (x) 的不动点，若存的不动点，若存在在 x* 的某个的某个 -邻域邻域 U(x*) =x*- , x* + ，对任意，对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1 = (xk) 产生的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理

44、：设设 x* 是是 (x) 的不动点，若的不动点，若 (x) 在在 x* 的某个邻域的某个邻域内连续，且内连续，且 | (x*)| 0，则称该迭代为，则称该迭代为 p 阶收敛阶收敛。(1)当当 r =1 时称为时称为线性收敛线性收敛，此时，此时 C 1 时称为时称为超线性收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*) 0，则，则不动点迭代不动点迭代 xk+1 = (xk) 线性收敛线性收敛第58页/共87页59定理：定理：设设 x* 是是 (x) 的不动点的不动点，若若 (p)(x) 在在 x* 的的某邻域内连续，且某邻域内连续，且(1)()( *)( *)( *)0

45、,( *)0ppxxxx 则迭代则迭代 xk+1 = (xk) 是是 p 阶收敛的。阶收敛的。第59页/共87页60例：例：求求 f(x) = x2 - 3=0 的正根的正根 2( )3xxx (1)( *)2 311x ex72.m*3x 23( )4xxx (2)3( *)10.31412x 13( )2xxx (3)( *)0 x 2( *)03x 二次收敛二次收敛局部收敛局部收敛第60页/共87页61计算得计算得40 xex00 5 .x 例例9 9 用简单迭代法求方程用简单迭代法求方程精确到精确到3位有效数字位有效数字.解解简单迭代法简单迭代法在在0,1内的根内的根( )4 ,xf

46、xex( )f x在在0,1内连续内连续,( )40,0,1xfxex在在0,1内有唯一内有唯一 实根实根.40 xex的等价方程为的等价方程为14xxe1( ),4xxe又当又当0,1, ( )0,1xx故故114nxnxe对对00,1x均收敛均收敛. .取取故故( )0f x 26(0)10,f (1)40fe1( )4xxe14e1,0,1x第61页/共87页62故，故，10.4122,x 简单迭代法简单迭代法*0.358x 114nxnxe00 5 .x 2770.3575x 60.3571,x 50.3583,x 40.3600,x 30.3675,x 20.3775,x 第62页/

47、共87页63q 基本思想将非线性方程将非线性方程线性化线性化2( )( )()()()()2!kkkkff xf xfxxxxx l 设设 xk 是是 f (x)=0 的近似根，将的近似根，将 f(x) 在在 xk 处处 Taylor 展开展开令：令：( )0P x 1()()kkkkf xxxfx ( )P x()()()kkkf xfxxx 条件：条件： f(x) 0第63页/共87页64xyx*xkxk+1第64页/共87页65因为因为32( )210200f xxxx2( )34100,1,2fxxxx3212210203410nnnnnnnxxxxxxx得牛顿迭代公式为得牛顿迭代公式

48、为例例7用用Newton法求方程法求方程在在(1,2)的根，取初值的根，取初值01x 解解 NewtonNewton法与弦截法法与弦截法1()()nnnnf xxxfx(1)7,(2)16ff 根据根据 Newton迭代迭代故在故在1,2内方程有唯一实根内方程有唯一实根取初值取初值01x 得得22第65页/共87页6611.411764706,x 代入初值得代入初值得NewtonNewton法与弦截法法与弦截法31.368808189,x 3212210203410nnnnnnnxxxxxxx01x 故取故取9541102xx*51.368808108xx2351.368808108x 41.

49、368808108,x 21.369336471x 第66页/共87页671()()kkkkf xxxfx k = 0, 1, 2, . . . l 迭代函数( )( )( )f xxxfx ( *)( *)0,( *)2( *)fxxxfx 牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛12*( *)( *)lim(*)2!2( *)kkkxxxfxxxfx 2( ) ( )( )( )f x fxxfx第67页/共87页68例：例：用用 Newton 法求法求 f(x) = x2 C=0 的正根的正根, 并验证这一并验证这一方法的二阶收敛性方法的二阶收敛性21()1()22kkkkkkkkk

50、f xxCCxxxxfxxx 解：解： 211,2kkkxCxCx 2112kkkxCxCx 211kkkkxCxCxCxC 2200kkkkxCxCqxCxC 2221kkkqxCCq 对任意对任意 x00，总有总有 |q|1，即即牛顿法收敛牛顿法收敛0第68页/共87页69112kkkCxxx 2112kkkxCxCx 1212kkkxcxxc12 c二阶收敛二阶收敛关于二次收敛性，事实上关于二次收敛性，事实上12kkee12 c第69页/共87页70第70页/共87页71第71页/共87页72常微分方程数值解法常微分方程数值解法10( ,)(0,1, )( )nnnnyyhf x yny

51、y a(9-2)公式公式(9-2)(9-2)称为显式欧拉公式称为显式欧拉公式. .Euler法的局部截断误差也可表示为法的局部截断误差也可表示为23211()()()2nnRh y xO hO hEuler方法是一阶方法方法是一阶方法.第九章第九章 常微分方程数值解法常微分方程数值解法30第72页/共87页73111,2nnnnnnhyyf xyf xy(9-9)这就是求解初值问题式（这就是求解初值问题式（9-1）的）的梯形公式梯形公式.梯形公式（梯形公式（9-9）的局部截断误差为）的局部截断误差为常微分方程数值解法常微分方程数值解法1111() (, ()(, ()2nnnnnnnhRy x

52、y xf xy xf xy x3( )12hy 1nnxx故梯形公式为二阶方法故梯形公式为二阶方法. 31第73页/共87页74常微分方程数值解法常微分方程数值解法一般地一般地,RK方法设近似公式为方法设近似公式为11111,(,)(2,3, )pnniiinniininijjjyyhcKKf x yKf xah yhb Kip(9-13),ia,ijb,ic其其中中 都是参数都是参数, , 确定它们的原则是使近似确定它们的原则是使近似公式在公式在 处的处的Taylor展开式展开式与与 在在 处的处的),(nnyx)(xynxTaylor展开式的前面的项尽可能多地重合展开式的前面的项尽可能多地

53、重合, ,这样就使近这样就使近似公式有尽可能高的精度似公式有尽可能高的精度。32第74页/共87页75常微分方程数值解法常微分方程数值解法121211,)(2hKyhxfKyxfKKKhyynnnnnn这就是改进这就是改进Euler公式公式,它是一种二阶龙格它是一种二阶龙格-库塔公式。库塔公式。33第75页/共87页76常微分方程数值解法常微分方程数值解法(9-11)式（式（9-11）称为由）称为由Euler公式和梯形公式得到的公式和梯形公式得到的预测预测校正系统校正系统，也叫，也叫改进改进Euler法法，它是显式单步法。，它是显式单步法。预测预测1(,)nnnnyyhf xy校正校正改进改进

54、Euler法的局部截断误差为法的局部截断误差为 ),(3hO故它是二阶方法。故它是二阶方法。111 (,)(,)2nnnnnnhyyf xyf xy34第76页/共87页77例1用欧拉法求初值问题000.912()10yyxy xx 当h = 0.02时在区间0, 0.10上的数值解。解解 把 yxyxf219 . 0),(代入欧拉法计算公式。就得10.90.01810,1,51212nnnnnnyyhyynxx具体计算结果如下表：nxnyny(xn) n = y(xn) - yn001.00001.0000010.020.98200.98250.000520.040.96500.96600.

55、000530.060.94890.95030.001440.080.93360.93540.001850.100.91920.9230.0021第77页/共87页78常微分方程数值解法常微分方程数值解法例例 用改进的用改进的Euler法求初值问题法求初值问题210.1()nnnnnyyxxy200.3(0) 0yxx yxy 0.1h的数值解的数值解, 取取 .解解 改进的改进的Euler公式为公式为2( , )f x yxxy所以所以2220.1(0.1)(0.1)0.90.1()2nnnnnnnnnyxxyxxyxx1111(,) (,)(,)2nnnnnnnnnnyyhf xyhyyf xyf xy2211110.12nnnnnnnnyyxxyxxy20.051.92.11.90.11nnnnyxxy3520.90.1()nnnyxx第78页/共87页79常微分方程数值解法常微分方程数值解法