数值计算方法总复习--课件.ppt

1、计算方法 总复习第1章 绪论 误差及有效数字 误差的传递、函数误差3误差和有效数字称为近似数为准确数，设定义,2.2.1*xxxxxex*)(绝对误差：的）（近似数)0()()(*xxxexexr相对误差：的）（近似数4误差估计差界。的绝对误差界和相对误为近似数和则称满足和若有正数为近似数为精确数，设定义*r*r*|)(|)(|:,2.2.1xxxxxexxxexxrr56有效数字 在工程上，误差的概念就转化为有效数字有效数字。似数。具有五位有效数字的近称则的近似数例如：3.14161021.00000734.0.14159265.31416.3)(1416.3.14159265.3*4*e7

2、位有效数的近似数。的具有为则称的绝对误差满足。如果是整数且和其中有规格化形式设近似数定义nxxxxxexaaniamaaaaxxnmiinm*1321*1021|)(|90,0,.),.,2,1(.0103.2.18，则：的近似数设*2*121,xxxx)()()()(.1*2*1*2*1*2*1*2*1xexedxdxxxdxxe)()(lnln)ln(ln)ln()(.2*2*1*2*1*2*1*2*1*2*1xexexdxdxxdxxdxxerrr9)()()()()()(.3*2*1*1*2*2*1*2*1*2*1*2*1*2*1xexxexxexexxxxexxxxerrrrr)()

3、()(.4*2*1*2*1xexexxerrr2*2*2*1*1*2*2*1)()()()(.5xxexxexxxe101.2.3 函数值的误差估计)()()()()()()()()()()()(),(*xexfxfxfexexfxxxfxdfxfxffexfxxxfyrr或时，则误差为计算函数值则代替用近似数当设函数第二章 非线性方程的数值解法 二分法 一般迭代法 Steffensen加速收敛法 Newton法 弦截法12二分法 用二分法(将区间对平分)求解求解。令 若 ，则 为有根区间，否则 为有根区间 记新的有根区间为 ，则 且)(,1121111bacbbaa0)()(11cfaf,1

4、1ca,11bc,22ba,2211baba)(112122abab13二分法 对 重复上述做法得 且 ,22ba.,.,2211nnbababa)(211ababnnn14 由二分法误差估算式次。至少要二分即误差小于9103966.812lg312lg3)lg(abn2,110)(21|31*baabxxnn，其中152.2一般迭代法2.2.1 迭代法及收敛性 对于对于 有时可以写成有时可以写成 形式形式 如如：0)(xf)(xx33101xxxxxxxxcos0cos31xx或16迭代法及收敛性考察方程 。这种方程是隐式方程，因而不能直接求出它的根。但如果给出根的某个猜测值 ，代入 中的右

5、端得到 ，再以 为一个猜测值，代入 的右端得 反复迭代得)(xx0 x)(xx)(01xx1x)(xx)(12xx,.1,0)(k1kkxx17Steffensen加速收敛法 概述 由上式产生的序列称为Steffensen迭代序列。)2()(2)()()(2xxxxxxx而迭代函数。称为Steffensen18Newton迭代法,.1,0)()(1nxfxfxxnnnn 以此产生的序列以此产生的序列 X Xn n 得到得到f f(x x)=0)=0的近似解，的近似解，称为称为NewtonNewton法法，又叫，又叫切线法切线法。192.4弦截法 Newton迭代法有一个较强的要求是 且存在。因

6、此，用弦的斜率近似的替代 。得弦的方程及则过)(,(P)(,(P111000 xfxxfx0)(xf)(xf,)(10*bxaxxbaxf取，上有唯一零点在设)()()()(101011xxxxxfxfxfy20弦截法 令y=0，解得弦与x轴的交点是坐标x2)()()(1010112xfxfxfxxxx解得0)()()()(1201011xxxxxfxfxf.,320 xxx计算再由,.)2,1()()()(001nxfxfxfxxxxnnnnn.称之为定端点弦截法21弦截法,.)2,1()()()(111nxfxfxfxxxxnnnnnnn以此类推计算若由,321xxx.,又称快速弦截法称之

7、为变端点弦截法第三章 线性方程组的数值解法 消元法求解线性方程组：Gauss消元法 分解法求解线性方程组：LU分解法、Cholesky分解法、追赶法23高斯顺序消去法高斯顺序消去法 设 Ax=b.记A(1)=A b(1)=b。设1、第一次消元。0iiaTnnnnnniiibbbbbaaaaaaaniaalnaa.AA,.,3,2,.,32ii)()2()2(2)1(1)2()1()2()2(2)2(2)2(22)1(1)1(11)1(11)2(1)1(11)1(11)1(11)1(1）（令），行（第第一行24高斯顺序消去法),.,2;,.,2()1(11)1(1)1(1)1()1(11)1()

8、2(njniaaaaalaajiijjiijij),.,2(.)1(1)1(11)1(1)1(1)1(1)1()2(nibaablbbbiiiii25高斯顺序消去法 设第k-1次消元得A(k)x=b(k)其中)()()2(2)1(1)()()()()2(2)2(22)1(1)1(12)1(11)()(.|knkkknnknkkknkkknnkkbbbbaaaaaaaaabA26高斯顺序消去法 则第k次消元:nkjnkialaakkjikkijkij,.,1;,.,1)()()1(，则有，令1,.,2,1,.,1)()(nknkiaalkkkikiknkiblbbkkikkiki,.,1)()(

9、)1(，27高斯顺序消去法 最后)()()2(2)1(1)()()()2(2)2(22)1(1)1(12)1(11)()(.nnkknnnkknkkknnnnbbbbaaaaaaaabA28高斯顺序消去法 也就是对于方程组AX=b系数矩阵做：)1,.,2,1(,.,1,.,1/)()()1()()()1()()(nknkjnkilbbbalaaaalikkkkikikkjikkijkijkkkkikik29高斯顺序消去法)()()2(2)1(1)()()()2(2)2(22)1(1)1(12)1(11)()()n(.)(|AnnkknnnkknkkknnnnbbbbaaaaaaaanAbbx其

10、中得到30高斯顺序消去法)1,.,1(/).(/A)(1)()()()()()(niaxabxabxiiinijjiijiiinnnnnnnbx回代法再解313.1.2 高斯主元素消去法 Gauss列主元消元法 从第一列中选出绝对值最大的元素1111maxiniaannnnniiniinbaaabaaabaaabaaa.21212112221111211交换32高斯列主元消去法顺序消元计算机中实现)3;:;1)2;|;|maxmax|2 1;i ;|max 1)11111TaaaaTdontojforkiathenaifdontokforaijijjjkki33高斯列主元消去法 第 k 步 从

11、 的第 k 列 ，中选取绝对值最大项，记录所在行，即 若 交换第k行与l行的所有对应元素，再进行顺序消元。(k)kka1)(Ak(k)nk.a.(k)kkakkikkkiilaak记|max|)(nik)(kl 34Doolittle分解各元素方法逐行逐列求解用比较等式两边元素的令ULuuuuuulllaaaaaaaaannnnnnnnn,.1.11.222112112121n2n1n222211211135Doolittle分解。得再由；得由时：。得再由；得由时),.,4,3(),.,3,2(12),.,3,2(),.2,1(1:1221212222212121222212121111111

12、1 i1111niuulalululanjulauuulakniualluanjauuakiiiiiijijjjjjiiijjjj36Doolittle分解1111211211,.1,000.10.,.,kttjktkjkjktkjtjktjjjjkkkkkjknkkkknkkjulauuuluuulllakjuuuk）（有步时：计算第37Doolittle分解11111111,.1/)(000.0,1,.,.,ktkktkitikikktkkiktkitkkkikiiknkkknkiuulalululuullakill）（得，于是由由于计算38Doolittle分解nnnnnnkkkttki

13、tikikkttjktkjkjulluuluuunkuulalnkinkjulau.A,.,2,1/)(),.,1;,.,(2122221112111111的各位各元素在计算机内存于即39Doolittle分解。可获解得及再由TniinijjijiiijjijiixxxnniuxuyxniylbyULxyxby),.,(1,.1,/)(,.,2,12111140Cholesky分解的求法332322131211333231222111333231232221131211212221113?.,llllllllllllaaaaaaaaanlllllllLLLAAijnnnnT为例。以如何求令则对

14、称正定设41Cholesky分解的求法。；同理得，得由；，得时：由1131311121211121211111211111lallalllaallak。，得由；，得时：由222131323222322131322212222222221222lllalllllalalllak42Cholesky分解的求法21233333233232231333iilallllak，得时：由njnjilllallalnjjjkjkikijijjkjkjjjj,.,2,1,.,1/)()(,1121112有阶行列式推广到43三对角方程组求解的追赶法yxfyfxfxULA等价于求即则，求，LU，故有其中Tnffff

15、),.,(21nnnffffyyyyppp321321321111),.,2(111niypfyfyiiii解得：44三对角方程组求解的追赶法nnnnnnnyyyyxxxxqcqcqcq121121112211再由)1,.,1(1niqxcyxqyxiiiiinnn解得组的追赶法。以上称为解三对角方程第四章 函数逼近的插值法与曲线拟合法 Lagrange插值法 Newton插值法 离散数据的曲线拟合464701110111()().()().()()()().()().()jjnjjjjjjjjnxxxxxxxxxxlxxxxxxxxxxx)5(0njiiijixxxx48niiinnnxly

16、xlyxlyxlyxP01100)()(.)()()(显然Pn(x)为次数不超过n次的多项式，且满足插值条件。故，Pn(x)为拉格朗日插值问题的解，称为拉格朗日插值多项式。构造函数Pn(x)：4950）式得：式代入（1)2()3(,)(,)()()(10101000 xxxfxxxxxxfxxxfxf,2102210102xxxxfxxxxxfxxxfx，则节点为了提高精度，可增加)4(,)(,210221010 xxxxfxxxxxfxxxf得51,)()(,)(,)()()(210210210101000 xxxxfxxxxxxxxxfxxxxxxfxxxfxf）式得：式代入（3)4(上有

17、一般的，在节点nxxxx,.,21052)()(,.,)().()(,.,).()(.,)(,)()()(10110110110210101000 xRxNxxxxfxxxxxxxxxxxxfxxxxxxxxxfxxxxxxfxxxfxfnnnnnnnn插值公式；上的在节点为Newton)()(0ninxxfxN,.,).()(.,)(,)()()(110110210101000nnnnxxxxfxxxxxxxxxfxxxxxxfxxxfxN其中：,.,)().()()(10110nnnnxxxxfxxxxxxxxxR插值余项。上的在节点为Newton)()(0ninxxfxR 例4.5.3

18、地球温室效应问题 下表统计了近100年内地球大气气温上升的数据.试根据表中数据建立一数学模型即拟和曲线,并根据这一模型,预报地球气温何年会比1860年的平均温度高7oC 解解 为简化数据,从1880年起年份记N,其变换n=(N-1870)/10.将地球气温增加值改记为t=1,2,3,4,6,8,10,13,18,24,32,也就是将原气温增加值扩大100倍,根据新数据绘制图4.5.1(P119)从图4.5.1可以看出,气温t与变换n大致服从指数函数增长过程,因此,可以假设t与n满足指数函数关系 为决定参数,将上式改写成ntelnlntt 记 则有 这是已知数据相应地变为如下表所示ln,ln,y

19、t x n abbxayn1234567891011ln1ln2ln3ln4ln6ln8ln10ln13ln19ln24ln32tyln 由式(4.5.16),取n=1,m=10,并将上表已知数据带入得解方程组得:116521.4509507865506164.2174248abab1.1436951080.307292969aeb所以,307292969.0,134264343.0ba 相应的t 与 n 的指数型拟合曲线关系为 就是所求地球温室效应的指数函数的数学模型,以此进行预报,即已知t值求0.3072929691.143695108teln(/1.143695108)/0.307292

20、9661870 10ntNn第五章 数值积分与数值微分 插值型求积公式，Newton-Cotes求积公式、定步长复化求积公式，复化梯形公式，复化Simpson公式，变步长复化求积公式，Romberg求积公式 数值微分的中点公式，数值微分的Taylor展开法，数值微分的插值法，数值微分的隐式格式的截断误差。为，（其中称系数；是其中积分公式。banbanbannnnjiijnnjdxxfxxxxxxxdxxxxxxfdxxfnfRCotesdtitjnnjCCotesNewton)().()()()(,.,)()()!1(1)()!(!)1(1010)1(00)(常用的几个积分公式 梯形公式(n=

21、1),()(12)()()(2)(21)(21)()(,21 31110bafabfRbfafabbfafabfTfRfTdxxfCCTbaT且。则因为 Simpson公式(n=2),()(2880)()()2(4)(6)(61,64,61)4(5)2(2)2(1)2(0bafabfRbfbafafabfSfRfSdxxfCCCSbaS且所以因为 Newton公式(n=3)。其中且所以，因为3)()2(3)(3)(8)(8183,83,81)3(3)3(2)3(1)3(0abhbfhafhafafabfNfRfNdxxfCCCCbaN Cotes公式(n=4)。其中且所以，因为4)(7)2(3

22、2)2(12)(32)(7(90)(907,90329012,9032,907)4(4)4(3)4(2)4(1)4(0abhbfhafhafhafafabfCfRfCdxxfCCCCCbaC例题756931.075693.0)21351334131(81;4469.0)21231411(61;57.011212169314718.02ln112121ICotesINewtonISimpsonIdxxILeibnizNewtondxxI公式得由公式由公式由）（由梯形公式公式得解：由。计算5.2.1定步长复化求积公式 1.复化梯形求积公式 bbaa2)()2(2)(4)()2(22)2()(22)

23、2()()(2)(bfbafafabbfbafbabafafbahTbfafbahT 一般地将a,b区间n等分，则)()(2),.2,1(,),.2,1,0(,211jjjjjjxfxfhSTnjxxnjjhaxbah公式有使用对每个子区间 2.复化Simpson公式类似于梯形公式：,)()()(4)(6,.2,1,12111hfRSdxxfxfxfxfhSnjxxSnjjbajjjjjj则上有在每个子区间定步长复化Simpson求积公式算法SShSnjjhafhjafSSbfafSnabhhSnban输出计算输入.3;3)3();,.2,1()()21(2)2(;2)()(;)1()(.2;

24、,.1变步长梯形求积公式变步长Simpson求积公式)2(2)2(31)2()(2)(31)21(2)(2)()(31)21(2)(2)()(3)(222111hHhThShHhThjafhjhafbfafhhjafjhafbfafhhSSimpsonnnnnnnjnjnjn所以公式由复化Romberg求积公式5.5.1 Taylor展开式方法展开式方法几种常用的求导公式第六章 常微分方程数值解法 显式Euler法，改进的Euler格式，龙格-库塔法，经典四阶龙格-库塔格式 单步法的稳定性 线性多步法，四阶Adams显式公式、隐式公式6.1 初值问题的Euler方法,.)2,1,0()(,)(

25、0,.),2,1,0()(),(00nyxyyxxyhnnhaxyxyyxfdxdynnnnn即上的近似值在点去获得解值解是指通过某种方法假定为常数。该式的数为步长，一般总记问题设一阶常微分方程初值初值问题的Euler方法。算出出发，逐次公式，它可以从这就是显式的）（的近似值，则有表示以于是该式可离散为：代替散化，并用方法首先将微分算子离为实现这一目标，.,Euler)1(,.2,1,0),()()(,()()(,Euler321010yyyynyxhfyyxyyxyxfhxyhxyxxnnnnnnnnnnn初值问题的Euler方法。才能得到步要解函数方程的不同在于，它每算一方法，它与显式公式

26、或向后这就是隐式的）（的近似值，则有表示以于是该式可离散为：代替如果用11111101)2(EulerEuler)2(,.2,1,0),()()(,()()(,nnnnnnnnnnnnynyxhfyyxyyxyxfhxyhxyxx初值问题的Euler方法)1(11)()1(1)(11)1(1)0(1111,|3,.2,1,0),(),(2),(,.2,1,0),(),(2knnknknknnnnnknnnnnnnnnnnnyyyykyxfyxfhyyyxhfyyynyxfyxfhyy取时当）（）（时常用以下迭代式：计算称为梯形公式。）（平均值的结果，则得如果取以上两式的算术初值问题的Euler

27、方法进行比较。精确解并与法求解法和改进试分别用设初值问题例xyyyxydxdy21,EulerEuler1)0(21.1.6初值问题的Euler方法计算结果如下表所示：法：改进的法：上结果，此时计算解：取,.)2,1,0()1.0(2(1.0)2(1.0)(21Euler,.)2,1,0()2(1.0 1,0,1.011212111nkyxkykyxykkkyynyxyyyEulerxhnnnnnnnnnnnnn6.1.3 数值稳定性分析稳定。值不大，则，则称该算法的舍入误的舍入误差。如果算则称该算法是数值稳定|，得值方法又算，如果结果为计算，则时有一舍入误差假设1111数，也成绝对稳定且通过

28、某种数实际计算nnnnnnnnnnyyyyyRunge-Kutta方法.K-R)21,21(),(,21,1,0)2(1212121方法这是二阶此时算式为可得取kyhxhfkyxhfkkyynnnnnn6.2.3 R-K法的稳定性nnnnyhhhhkyhhhkyhhkyhkyxy)(41)(21)()(41)(21()(21(dd,K-R4324323221有应用于实验方程法为例以经典R-K法的稳定性.,078.2:,1|!4)(!3)(!2)()(1|:|,|4321稳定性必须很小才能保证算法即限制很大步长的绝对值较大时当因此可得稳定性区间为负实数时当于是得稳定性区域为由稳定性要求hhyfh

29、hhhhnn基于数值积分的方法10101)1(211011rr11)1,.,1,0(!)1).(1()1(),(),()()()()(:Newton),(),.,(),(1rrjdsjjsssdsjsbxxfhbxTxTfbhxyxyfxfxfxrjjnrnrrrrjnjjnnnnnnnn其中后插值公式代入得到由个点：取基于数值积分的方法算式时称为四阶显式则），并逐次取式中的代替用Adams3)(720251)()9375955(24)(83)()51623(12)(125)()3(2)(2)(,3210(),()5(513211)4(41211)3(3111 211jjyhxTffffhyyyhxTfffhyyyhxTffhyyyhxThfyyjfxyynnnnnnnnnnnnnnnnnnnnn基于数值积分的方法.Adams)(72019)5199(24:,),(),.,(),(:1)5(521111r1r11算式称为四阶隐式则可同上求得次插值多项式做个点若取yhffffhyyrfxfxfxrnnnnnnnnnnnn