数值分析期末复习要点总结课件.ppt

1、1期末复习要点总结数值分析数值分析22第一章第一章 误差误差第一章第一章 误差误差一一.误差的来源误差的来源:1 1.模型误差模型误差2.2.观测误差观测误差3.3.截断误差截断误差4.4.舍入误差舍入误差二二.绝对误差绝对误差、相对误差和有效数字相对误差和有效数字33为准确值为准确值x的一个近似值，称的一个近似值，称*x*)(xxxe*x绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字若若 *)(xxxe*x 的的绝对误差限绝对误差限，简称，简称误差限误差限.通常称通常称为近似值为近似值定义定义2 设设*x)(*xerxxxxxexer*(1-3)记为记为 即即准确值之比为近似值准确

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

3、数字到这一位的所有数并从第一个非零数字到这一位的所有数字均称为字均称为有效数字有效数字.绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字 有效数字有效数字的误差限是的误差限是则称则称*.x 1 4144142136.1*x取前八位数得近似值取前八位数得近似值 例如，例如，.,x 21 414213562 取前四位数得取前四位数得.,3121 4141021.414有有4位有效数字位有效数字.7121 41421361021.4142136有有8位有效数字位有效数字.66*xmnaaax10.021*(1-5),2,1,01iaai 一般地，如果近似值一般地，如果近似值其中其中m为整数，

4、为整数，绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字为为0 0到到9 9之间的整数之间的整数.nmxx1021*如果如果(1-6)则称近似值则称近似值*x有有n位有效数字位有效数字.*.x 11 4140 141410例如例如.3141121 414101022有有4位有效数字位有效数字.故故*.x 1 414的规格化形式为的规格化形式为77绝对误差、相对误差和有效数字绝对误差、相对误差和有效数字若若x的近似值的近似值,10.021*mnaaax111021na至少具有至少具有n位有效数字位有效数字.*xr1110121nra*x)0(1a有有n位有效数字，位有效数字，则则误差限误

5、差限.反之，反之，的相对误差的相对误差定理定理1.11.1为其相对为其相对满足满足若若则则88(1-12)(1-11)(1-13)22121211212121)()()(xexxxxexxxxxexexexxerrr2121211221xexexxexexxexxxerrr1112222211221rrrxxee xe xxxxxeexexx 数值计算中误差的传播数值计算中误差的传播 9例例设近似数设近似数1.557a 31()1 02e a()()re aeaa是某真值是某真值 x 经四舍五入经四舍五入所得所得,试求其绝对误差限和相对误差限试求其绝对误差限和相对误差限.解解由于由于a经四舍五

6、入得到经四舍五入得到,故故311 021.5 7 743.1705771091010411()10,2e x126.1025,80.115xx1212,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 xxe x431180.

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

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

9、 11121(12)(1)xxxxx对对解解(1)要使计算准确要使计算准确,应避免两个相近的数相减应避免两个相近的数相减(2)11xxxx对对1x(2)要使计算准确要使计算准确,应避免两个相近的数相减应避免两个相近的数相减故变换所给公式故变换所给公式故变换所给公式故变换所给公式1111()()1111xxxxxxxxxxxxxxxx211xxxxx1214已知函数已知函数 y=f(x)在在 a,b 上有定义，且已经测得在点上有定义，且已经测得在点 a x0 x1 xn b 处的函数值为处的函数值为 y0=f(x0)，yn=f(xn)如果存在一个如果存在一个简单易算简单易算的函数的函数 P(x)

10、，使得，使得 P(xi)=f(xi)，i=1,2,.,n则称则称 P(x)为为 f(x)的的插值函数插值函数插值区间插值区间插值节点插值节点求插值函数求插值函数 P(x)的方法就称为的方法就称为插值法插值法插值节点插值节点无需递增排无需递增排列列，但必须确保，但必须确保互不互不相同相同！插值条件插值条件15基函数法通过基通过基函数来构造函数来构造插值多项式的方法插值多项式的方法就就称为称为基函数基函数插值插值法法Zn(x)=次数不超过次数不超过 n 的多项式的全体的多项式的全体记记n+1 维线性空间维线性空间设设 z0(x),z1(x),.,zn(x)构成构成 Zn(x)的一组基，则插值多项式

11、的一组基，则插值多项式P(x)=a0z0(x)+a1z1(x)+anzn(x)寻找合适的基函数寻找合适的基函数 确定插值多项式在这组基下的表示系数确定插值多项式在这组基下的表示系数基函数法基本步骤基函数法基本步骤16Lagrange插值基函数设设 lk(x)是是 n 次多项式，在插值节点次多项式，在插值节点 x0,x1,xn 上满足上满足1,()0,kjjklxjk 则称则称 lk(x)为节点为节点 x0,x1,xn 上的上的拉格朗日插值基函数拉格朗日插值基函数17两种特殊情形 n=10110 01 1010110()()()xxxxLxy lxy lxyyxxxx 线性插值多项式（一次插值多

12、项式）线性插值多项式（一次插值多项式）n=2020112012010210122021()()()()()()()()()()()()xxxxxxxxxxxxyyyxxxxxxxxxxxx 抛物线插值多项式（二次插值多项式）抛物线插值多项式（二次插值多项式）2()Lx18例：例：已知函数已知函数 y=lnx 的函数值如下的函数值如下解解：x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试分别用试分别用线性插值线性插值和和抛物线插值抛物线插值计算计算 ln 0.54 的近似值的近似值线性插值线性插值：取取 x0=0.5,x1=0.6 得

13、得将将 x=0.54 代入可得：代入可得：011010110()0.18231.6046xxxxLxyyxxxxx ln 0.54 L1(0.54)=-0.6202为了减小截断误差，通常选取插值点为了减小截断误差，通常选取插值点 x 邻接的插值节点邻接的插值节点19抛物线插值抛物线插值：取取 x0=0.4,x1=0.5,x2=0.6,可得可得ln 0.54 L2(0.54)=-0.6153 ln 0.54 的精确值为：的精确值为：-0.616186可见，抛物线插值的精度比线性插值要高可见，抛物线插值的精度比线性插值要高Lagrange插值多项式简单方便，只要取定节点就可写出基函数，进而插值多项

14、式简单方便，只要取定节点就可写出基函数，进而得到插值多项式，易于计算机实现。得到插值多项式，易于计算机实现。20l0(x),l1(x),ln(x)构成构成 Zn(x)的一组的一组基基性质性质注意注意l0(x),l1(x),ln(x)与插值节点有关，与插值节点有关，但与函数但与函数 f(x)无关无关lk(x)的表达式的表达式0110111,()()()()()()()()()kknkkkknjjjkkknjkkxxxxxlxxxxxxxxxxxxxxxx 由构造法可得由构造法可得21误差估计如何估计误差)()()(xLxfxRnn 插值余项插值余项定理定理设设 f(x)Cna,b(n 阶连续可微

15、阶连续可微)，且，且 f(n+1)(x)在在(a,b)内存在，则对内存在，则对 x a,b，有，有(1)1()()()()()(1)!nxnnnfRxfxLxxn 其中其中 x(a,b)且与且与 x 有关有关,101()()()()nnxxxxxxx 22插值余项l 余项公式只有当余项公式只有当 f(x)的高阶导数存在时才能使用的高阶导数存在时才能使用几点说明 l 计算插值点计算插值点 x 上的近似值时，应选取与上的近似值时，应选取与 x 相近插值节点相近插值节点10()(1)!nnniiMRxxxn 如果如果 ，则，则(1)1()nnfxM l x 与与 x 有关，通常无法确定有关，通常无法

16、确定,实际使用中通常是估计其上界实际使用中通常是估计其上界23插值误差举例例：例：已知函数已知函数 y=lnx 的函数值如下的函数值如下x0.40.50.60.70.8lnx-0.9163-0.6931-0.5108-0.3567-0.2231试估计试估计线性插值线性插值和和抛物线插值抛物线插值计算计算 ln 0.54 的误差的误差解解线性插值线性插值(2)2()4f (2)101()()()()2fRxxxxx 1(0.54)2(0.540.5)(0.540.6)0.0048R x0=0.5,x1=0.6,(0.5,0.6)24Newton 插值为什么 Newton 插值Lagrange 插

17、值简单易用，但若要增加一个节点时，全部基函数插值简单易用，但若要增加一个节点时，全部基函数 lk(x)都需重新都需重新计算，不太方便。计算，不太方便。设计一个可以逐次生成插值多项式的算法，即设计一个可以逐次生成插值多项式的算法，即 n 次插值多项式可以通过次插值多项式可以通过 n-1 次插次插值多项式生成值多项式生成 Newton 插值法插值法解决办法解决办法25什么是差商设函数设函数 f(x)，节点，节点 x0,xn()(),jiijjifxfxf xxxx f(x)关于点关于点 xi,xj 的的一阶差商一阶差商,jkijijkkif xxf xxf xxxxx f(x)关于点关于点 xi,

18、xj,xk 的的二阶差商二阶差商101010,kkkkf xxf xxf xxxxx k 阶差商阶差商差商的一般定义差商的一般定义26差商的性质l k 阶差商与阶差商与 k 阶导数之间的关系：阶导数之间的关系：若若 f(x)在在 a,b 上上 具有具有 k 阶导数，则至少存在一点阶导数，则至少存在一点 (a,b)，使得使得()01(),!kkff xxxk 27如何巧妙地计算差商差商表差商表xi(xi)一阶差商二阶差商三阶差商n 阶差商x0 x1x2x3xn(x0)(x1)(x2)(x3)(xn)x0,x1x1,x2x2,x3xn-1,xnx0,x1,x2x1,x2,x3xn-2,xn-1,x

19、nx0,x1,x2,x3xn-3,xn-2,xn-1,xnx0,x1,xn28差商举例例：例：已知已知 y=(x)的函数值表，的函数值表，试计算其各阶差商试计算其各阶差商i0123xi-2-112f(xi)531721解：解：差商表如下差商表如下xi(xi)一阶差商二阶差商三阶差商-2-112531721-2743-1-129Newton 插值公式 f(x)=Nn(x)+Rn(x)10102011()()()()()nniinaaxxaxxxxaxNxx 001,.,().()()nnnnf x xxxRxxxxxx Nn(x)是是 n 次多项式次多项式Nn(xi)=f(xi)，i=0,1,2

20、,n重要性质重要性质Nn(x)是是 f(x)的的 n 次插值多项式次插值多项式nixxfaxfaii,2,1 ,),(000 其中其中30Newton/LagrangeNewton 插值多项式与 Lagrange 插值多项式f(x)在在 x0,x1,xn 上上的的 n 次插值多项式是唯一的！次插值多项式是唯一的！Nn(x)Ln(x)余项也相同余项也相同(1)000()()()(1)!nnnxniiiiff x,x,.,xxxxxn (1)0()(1)!nxnffx,x,.,xn !)()(0kfx,.,xfkk 将将 x 看作节点看作节点31插值举例例：例：已知函数已知函数 y=lnx 的函数

21、值如下的函数值如下解解：取节点取节点 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)=-0.6931+1.8230(x-0.5)-2.0450(x-0.5)(x-0.6

22、)N2(0.54)=-0.6153ex25.m插值节点无需递增排插值节点无需递增排列，但必须确保互不列，但必须确保互不相同！相同！32()()dbaIffxx l 微积分基本公式：微积分基本公式：baaFbFxxf)()(d)(3)f(x)表达式未知表达式未知，只有通过测量或实验得来的数据表，只有通过测量或实验得来的数据表l 但是在许多实际计算问题中但是在许多实际计算问题中(2)F(x)难求！难求！甚至有时不能用初等函数表示。甚至有时不能用初等函数表示。如如21()sin,xfxxex (1)F(x)表达式较复杂表达式较复杂时，计算较困难。如时，计算较困难。如61()1fxx 33数值积分公式

23、的一般形式数值积分公式的一般形式0()d()nbiiaifxxA fx 求积节点求积节点求积系数求积系数机械求积方法机械求积方法l 将定积分计算转化成被积函数的将定积分计算转化成被积函数的函数值函数值的计算的计算l 无需求原函数无需求原函数l 易于计算机实现易于计算机实现一般地，用一般地，用 f(x)在在 a,b 上的一些离散点上的一些离散点 a x0 x1 xn b 上的函数值的加权平均作为上的函数值的加权平均作为 f()的近似值，可得的近似值，可得34定义定义：如果对于所有次数不超过：如果对于所有次数不超过 m 的多项式的多项式 f(x)，公式，公式精确成立，但对某个次数为精确成立，但对某

24、个次数为 m+1 的多项式不精确成立，则称该求积公式具有的多项式不精确成立，则称该求积公式具有 m 次代数精度次代数精度0()d()nbiiaifxxA fx l 将将 f(x)=1,x,x2,xm 依次代入，公式精确成立依次代入，公式精确成立;l 但对但对 f(x)=xm+1 不精确成立。即：不精确成立。即：22110 d2mmnbmmiiaibaA xxxm (k=0,1,m)代数精度的验证方法代数精度的验证方法110 d1kknbkkiiaibaA xxxk 35例：例：试确定系数试确定系数 Ai，使得下面的求积公式具有尽可能高的代数精度，并求出使得下面的求积公式具有尽可能高的代数精度，

25、并求出此求积公式的代数精度。此求积公式的代数精度。10121()d(1)(0)(1)fxxA fA fA f 解：解：将将 f(x)1,x,x2 代入求积公式，使其精确成立，可得代入求积公式，使其精确成立，可得 1101222023302()/12 ()/20 ()/32/3AAAbaAAbaAAba 解得解得 A0=1/3,A1=4/3,A2=1/3。所以求积公式为。所以求积公式为3)1()0(4)1(d)(11fffxxf 易验证该公式对易验证该公式对 f(x)x3 也精确成立，但对也精确成立，但对 f(x)x4 不精确成立，所以此求不精确成立，所以此求积公式具有积公式具有 3 次代数精度

26、。次代数精度。36设求积节点为：设求积节点为：a x0 x1 xn b 若若 f(xi)已知，则可做已知，则可做 n 次多项式插值：次多项式插值：0()()nniiiLxlxfx 其中其中()dbiiaAlxx 插值型求积公式插值型求积公式00()()d()d d()()bniiannbbiiaaiifxxxfxfxxxAxLl 误差：误差：()()d()dbbnnaaR ffxLxxRxx (1)01()()()()()(1)!nnnfRxxxxxxxn 其中其中abAnkk 037基于等分点的插值型求积公式基于等分点的插值型求积公式l 积分区间：积分区间：a,bl 求积节点：求积节点：xi

27、=a+i h bahn l 求积公式：求积公式：()0()d()()nbniiaifxxbaCfx ()()1()dbnniiaClxxba 00 dnnkkihtktbaik xath 001(1)()d!ninnkkitktnini Cotes 系数系数Newton-Cotes 求积公式求积公式()()nnin iCC(1)(2)()01nniiC3821,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()()6bababafx dxf aff bS

28、 代数精度代数精度=3抛物线公式抛物线公式Simpson公式公式n=4:01234()7()32()12()32()7()90babaf x dxf xf xf xf xf xC 科特斯科特斯(Cotes)公式公式4/)(,abhhiaxi代数精度代数精度=539l 梯形公式梯形公式(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 40q 提高积分计算精度的常用两种方法提高积分计算精度的

29、常用两种方法l 用用 复合公式复合公式l 用用 非等距节点非等距节点l 将积分区间分割成多个小区间将积分区间分割成多个小区间l 在每个小区间上使用低次牛顿科特斯求积公式在每个小区间上使用低次牛顿科特斯求积公式复合求积公式复合求积公式41l 将将 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()12niihR ff 2()12bah f (,)a b 42复合

30、复合 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 公式都是收敛的，也都是稳定公式都是收敛的，也都是稳定的。的。43例例2 分别用复化梯形公式与复化分别用复化梯形公式与复化Simpson公式计算积分公式计算积分10 xIe dx解解 (1)用复化梯形公式用复化梯形

31、公式,截断误差为截断误差为复化求积公式复化求积公式的近似值，为使截断误差的绝对值不超过的近似值，为使截断误差的绝对值不超过411 022(),1 2TbaRfhfa b ,0,1kxfxeex至少应将至少应将0,1的多少等份的多少等份.2211 21 2ThRhfe24210,67.312nen故取故取 n=681121112en4110,244(2)若用复化若用复化Simpson公式，截断误差为公式，截断误差为复化求积公式复化求积公式SRf bafhab,18044 44180SbaRfh f 4421 0,1 8 0en故取故取 n=6410180h e411180en4110,0,124

32、.1688n 12451()()()nbkkakx fx dxA fx例例5 试确定求积公式试确定求积公式 kx)(xGaussGauss型求积公式型求积公式 具有具有 2n+1次代数精确度次代数精确度，Gauss型求积公式型求积公式.公式公式（7-42）称为带权函数称为带权函数为为Gauss点点，则称这组节点则称这组节点定义定义7.2如果一组节点如果一组节点,21baxxxn能使求积公式能使求积公式（7-42）的的代数精确度代数精确度，Gauss型求积公式型求积公式.它是否是它是否是18 4482(2)(0)2(2)3fx dxfff46448dx 解解19由于当由于当 4482(2)(0)

33、2(2)3fx dxfff821283 fx分别取分别取231,x xx有有440 xdx423444112833x dxx82202203 2281282(2)022 33 即求积公式精确成立即求积公式精确成立.而当而当 4fxx44544412048,55x d xx434444104x dxx3382(2)02(2)03 4485122(2)02(2)33 20485因此因此,求积公式的代数精度为求积公式的代数精度为3.它不是它不是Gauss型求积公式型求积公式.p22471计算计算f(x)在有解区间在有解区间a,b端点处的值端点处的值，f(a)，f(b)。2计算计算f(x)在区间中点处

34、的值在区间中点处的值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=b。反复执行步骤反复执行步骤2、3，便可得到一系列有根区间便可得到一系列有根区间：(a,b),(a1,b1),(ak,bk),区间对分法区间对分法（二分法）（二分法）484、当当11kkab时时)(211kkkbax5、则、则即为根的近似即为根的近似),2,1()(211*1kabxxkk先验误

35、差估计：先验误差估计：理论基础：理论基础：定理定理1：设函数设函数 f(x)在区间在区间a,b上连续上连续，如果如果f(a)f(b)0，则方程则方程 f(x)=0 在在a,b内至少有一实根内至少有一实根x*。495310 xx对分区间法对分区间法在在0,0.5内的根内的根,要求误差不超过要求误差不超过例例6 6 试用对分区间法求方程试用对分区间法求方程2110.2解解 令令5()31fxxx则则(0)10,(0.5)0.5310ff 4()530,fxx故在故在0,0.5内内5()310fxxx有唯一实根有唯一实根.为达到要求为达到要求()ln1ln 2ban即即2(0.50)ln11021l

36、n 2n取取6n 计算结果见下表。计算结果见下表。202ln1015.64ln 250-0.2490230.1324158-0.05951970.0360497-0.01182140.012091010.000129230.250.3750.31250.343750.3281250.33593750.332031250.50.50.3750.3750.343750.343750.335937500.250.250.31250.31250.3281250.3281250123456nnanbnx)(nxf对分区间法对分区间法5()31fxxx故故60.33203125x 即为符合精度要求的解即为

37、符合精度要求的解.2151q 基本思想l 构造构造 f(x)=0 的一个等价方程：的一个等价方程：()xx (x)的不动点的不动点f(x)=0 x=(x)等价变换等价变换f(x)的零点的零点52q 具体过程l 任取一个迭代初始值任取一个迭代初始值 x0，计算，计算得到一个迭代序列：得到一个迭代序列：x0，x1，x2，.，xn，.1()kkxx k=0,1,2,.几何含义：几何含义：求曲线求曲线 y=(x)与直线与直线 y=x 的交点的交点53设设 (x)连续，若连续，若 收敛，即收敛，即 ，则，则 1limlim()limkkkkkkxxx lim*kkxx 0kkx *(*)xx (*)0f

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

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

40、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.m58定义定义：设设 x*是是 (x)的不动点，若存的不动点，若存在在 x*的某个的某个 -邻域邻域 U(x*)=x*-,x*+，对任意对任意 x0 U(x*)，不动点迭代，不动点迭代 xk+1=(xk)产生的点列都收敛到产生的点列都收敛到 x*，则称该迭代，则称该迭代局部收敛。局部收敛。定理：定理：设设 x*是是 (x)的不动点，若的不动点，若 (x)在在 x*的某个邻域内连续，且的某个邻域内连续，且|(x*)|0，则称

41、该迭代为，则称该迭代为 p 阶收敛阶收敛。(1)当当 r=1 时称为时称为线性收敛线性收敛，此时，此时 C 1 时称为时称为超线性收敛超线性收敛l 二分法是线性收敛的二分法是线性收敛的l 若若 (x*)0，则，则不动点迭代不动点迭代 xk+1=(xk)线性收敛线性收敛60定理：定理：设设 x*是是 (x)的不动点的不动点，若若 (p)(x)在在 x*的某邻域内连续，的某邻域内连续，且且(1)()(*)(*)(*)0,(*)0ppxxxx 则迭代则迭代 xk+1=(xk)是是 p 阶收敛的。阶收敛的。61例：例：求求 f(x)=x2-3=0 的正根的正根 2()3xxx (1)(*)2311x

42、ex72.m*3x 23()4xxx (2)3(*)10.31412x 13()2xxx (3)(*)0 x 2(*)03x 二次收敛二次收敛局部收敛局部收敛62计算得计算得40 xex00 5.x 例例9 9 用简单迭代法求方程用简单迭代法求方程精确到精确到3位有效数字位有效数字.解解简单迭代法简单迭代法在在0,1内的根内的根()4,xfxex()fx在在0,1内连续内连续,()40,0,1xfxex在在0,1内有唯一内有唯一实根实根.40 xex的等价方程为的等价方程为14xxe1(),4xxe又当又当0,1,()0,1xx故故114nxnxe对对00,1x均收敛均收敛.取取故故()0fx

43、 26(0)10,f(1)40fe1()4xxe14e1,0,1x63故，故，10.4122,x 简单迭代法简单迭代法*0.358x 114nxnxe00 5.x 2770.3575x 60.3571,x 50.3583,x 40.3600,x 30.3675,x 20.3775,x64q 基本思想将非线性方程将非线性方程线性化线性化2()()()()()()2!kkkkff xf xfxxxxx l 设设 xk 是是 f(x)=0 的近似根，将的近似根，将 f(x)在在 xk 处处 Taylor 展开展开令：令：()0P x 1()()kkkkfxxxfx ()P x()()()kkkf x

44、fxxx 条件：条件：f(x)065Newton 法xyx*xkxk+166因为因为32()210200fxxxx2()34100,1,2fxxxx3212210203410nnnnnnnxxxxxxx得牛顿迭代公式为得牛顿迭代公式为例例7用用Newton法求方程法求方程在在(1,2)的根，取初值的根，取初值01x 解解 NewtonNewton法与弦截法法与弦截法1()()nnnnfxxxfx(1)7,(2)16ff 根据根据 Newton迭代迭代故在故在1,2内方程有唯一实根内方程有唯一实根取初值取初值01x 得得226711.411764706,x 代入初值得代入初值得NewtonNew

45、ton法与弦截法法与弦截法31.368808189,x 3212210203410nnnnnnnxxxxxxx01x 故取故取9541102xx*51.368808108xx2351.368808108x 41.368808108,x21.369336471x681()()kkkkfxxxfx k=0,1,2,.l 迭代函数()()()fxxxfx (*)(*)0,(*)2(*)fxxxfx 牛顿法至少二阶牛顿法至少二阶局部收敛局部收敛12*(*)(*)lim(*)2!2(*)kkkxxxfxxxfx 2()()()()f x fxxfx69例：例：用用 Newton 法求法求 f(x)=x2

46、 C=0 的正根的正根,并验证这一方法的二阶收敛性并验证这一方法的二阶收敛性21()1()22kkkkkkkkkfxxCCxxxxfxxx 解：解：211,2kkkxCxCx 2112kkkxCxCx 211kkkkxCxCxCxC 2200kkkkxCxCqxCxC 2221kkkqxCCq 对任意对任意 x00，总有总有|q|1，即即牛顿法收敛牛顿法收敛070112kkkCxxx 2112kkkxCxCx 1212kkkxcxxc12c二阶收敛二阶收敛关于二次收敛性，事实上关于二次收敛性，事实上12kkee12c717273常微分方程数值解法常微分方程数值解法10(,)(0,1,)()nn

47、nnyyhf xynyy a(9-2)公式公式(9-2)(9-2)称为显式欧拉公式称为显式欧拉公式.Euler法的局部截断误差也可表示为法的局部截断误差也可表示为23211()()()2nnRh yxO hO hEuler方法是一阶方法方法是一阶方法.第九章第九章 常微分方程数值解法常微分方程数值解法3074111,2nnnnnnhyyfxyfxy(9-9)这就是求解初值问题式（这就是求解初值问题式（9-1）的）的梯形公式梯形公式.梯形公式（梯形公式（9-9）的局部截断误差为）的局部截断误差为常微分方程数值解法常微分方程数值解法1111()(,()(,()2nnnnnnnhRy xy xfxy

48、 xfxy x3()12hy 1nnxx故梯形公式为二阶方法故梯形公式为二阶方法.3175常微分方程数值解法常微分方程数值解法一般地一般地,RK方法设近似公式为方法设近似公式为11111,(,)(2,3,)pnniiinniininijjjyyhc KKf xyKf xah yhb Kip(9-13),ia,ijb,ic其中其中 都是参数都是参数,确定它们的原则是使近似确定它们的原则是使近似公式在公式在 处的处的Taylor展开式展开式与与 在在 处的处的),(nnyx)(xynxTaylor展开式的前面的项尽可能多地重合展开式的前面的项尽可能多地重合,这样就使近这样就使近似公式有尽可能高的精

49、度似公式有尽可能高的精度。3276常微分方程数值解法常微分方程数值解法121211,)(2hKyhxfKyxfKKKhyynnnnnn这就是改进这就是改进Euler公式公式,它是一种二阶龙格它是一种二阶龙格-库塔公式。库塔公式。3377常微分方程数值解法常微分方程数值解法(9-11)式（式（9-11）称为由）称为由Euler公式和梯形公式得到的公式和梯形公式得到的预测预测校正系统校正系统，也叫，也叫改进改进Euler法法，它是显式单步法。，它是显式单步法。预测预测1(,)nnnnyyhf xy校正校正改进改进Euler法的局部截断误差为法的局部截断误差为),(3hO故它是二阶方法。故它是二阶方

50、法。111(,)(,)2nnnnnnhyyfxyfxy3478例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.000530.060.94890.95030.001440.080.93360.93540.001850.100.91920.923