北京理工大学数值分析总复习实用教案

1、1考试(kosh)时带计算器 上机题请在11月30日晚9:30之前交，交打印稿。 答疑时间：11月28，29, 30（即星期3, 4，5）晚上(wn shang)7:309:30，上机作业也在答疑时间交。 答疑地点：中教816。第1页/共68页第一页，共69页。2第一章 误差(wch) 绝对（相对(xingdu)）误差 ( 限 ) 有效数字(yu xio sh z)第2页/共68页第二页，共69页。3 有效数字(yu xio sh z)x: 精确(jngqu)值x*: 近似值, 其科学(kxu)记数法为),0(10. 0*121 aaaaxmn若nmxx 1021|*|则称近似值 x*具有n位

2、有效数字.第3页/共68页第三页，共69页。4第二章 解线性方程组的直接(zhji)方法 列主元素(yun s)法 LU分解(fnji)法 (Doolittle分解(fnji)法) (追赶法) 平方根法与改进的平方根法 条件数bAx 求第4页/共68页第四页，共69页。511u1 kiliiu1 jiu1 1 iil1klkil1ilijuiiuju1iu121l12u22uju11kliju), 2 , 1(nj ), 3 , 2(nk ), 1,(niij kil), 1(nik 对i=2,3, n,ja1 111uak )(112211jiiijijiijululula iiiikiik

3、ikkiuululula)(112211 第5页/共68页第五页，共69页。6,LUA bLUxbAx , bLy 先求再求yUx 得x. 直接三角(snjio)分解法或Doolittle分解法.y第6页/共68页第六页，共69页。7 A: 对称(duchn)正定阵Cholesky分解(fnji)TLLA 21l11l22l1nl2nl2il1iliilnilnnlTL)(),(jillajiij 设 li =L的第 i个行向量, 则,1111al )2(1111 klalkk对 i=2,3,n,)(2121 iiiiiiillaliiiikiikikkikilllllllal)(112211

4、 )., 1(nik 第7页/共68页第七页，共69页。8bxLLbAxT 先求 Ly=b, 再求 LTx=y. 平方根法或Cholesky分解(fnji)法.y第8页/共68页第八页，共69页。9第三章 解线性方程组的迭代(di di)解法 Jacobi迭代法 Gauss-Seidel迭代法 迭代法收敛的条件(tiojin)(充要条件(tiojin), 充分条件(tiojin)bAx 求第9页/共68页第九页，共69页。10 Jacobi迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ii

5、iniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k)(k)(k+1), 2 , 1(ni Tknkkkxxxx)()(2)(1)(, 第10页/共68页第十页，共69页。11 Gauss-Seidel迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k+1)(k+1)(k+1), 2 , 1(ni 第11页/共68页第十一页，共69页。12 迭代法收敛(shulin)

6、的充分必要条件 )0()()1(,xgMxxkk任意(rny)收敛(shulin). 1)( M 迭代法收敛的充分条件若A为严格对角占优或不可约对角占优, 则求解Ax=b 的Jacobi迭代法和Gauss-Seidel迭代法均收敛.若A为对称正定阵, 则求解Ax=b的Gauss-Seidel迭代法收敛.第12页/共68页第十二页，共69页。13第四章特征值与特征向量的计算第四章特征值与特征向量的计算(j sun) 幂法和反幂法第13页/共68页第十三页，共69页。14设A为n阶实矩阵, 其特征值为1, 2, , n, 相应(xingyng)的特征向量为u1, u2, , un. 且满足条件 n

7、 32 u1, u2, , un线性无关(wgun). 幂法 幂法: 求1及其相应(xingyng)的特征向量.此时1一定是实数! 1通常称为主特征值. 1 第14页/共68页第十四页，共69页。15 幂法的计算公式 kkkkkkkxyxAyx )()()()1()(max 任取初始(ch sh)向量x(0)=y(0)0, 对k=1, 2, , 构造向量序列 x(k), y(k)1 k)max(11)(uuyk 当k充分(chngfn)大时第15页/共68页第十五页，共69页。16反幂法 用于计算矩阵按模最小的特征值及其特征向量, 也可用来计算对应于一个(y )给定近似特征值的特征向量, 是目

8、前求特征向量最有效的方法. 反幂法第16页/共68页第十六页，共69页。17 反幂法迭代(di di)公式为 任取初始向量(xingling)x(0)=y(0)0, 构造向量(xingling)序列)., 2 , 1 , 0()max()1()1()1()(1)1( kxxyyAxkkkkk 迭代向量(xingling)x(k+1)可以通过解方程组求得)()1(kkyAx nkx 1)max( )max()(nnkuuy 当k充分大时第17页/共68页第十七页，共69页。18第五章 插值法 Lagrange插值 Newton插值 Hermite插值第18页/共68页第十八页，共69页。19问题

9、(wnt):ix2x1xnx)(iixfy 1y2yny0 x0y求 Ln(x).(1) 至多n次多项式;)., 1 , 0()()(niyxfxLiiin (2)第19页/共68页第十九页，共69页。20 Lagrange插值)()()()()(1100 xlyxlyxlyxlyxLnniin 其中(qzhng) li (x) 为插值基函数(1) n次多项式);, 1 , 0( , 0)(, 1)(ijnjxlxljiii ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni 截断误差)()()(xLxfxRnn . )()!1()(0)1( niinxxnf (2)第20

10、页/共68页第二十页，共69页。21 差商一阶差商jijijixxxfxfxxf )()(,二阶差商kikjjikjixxxxfxxfxxxf , k阶差商kkkkxxxxxfxxxfxxxf 02111010,第21页/共68页第二十一页，共69页。22 Newton插值公式(gngsh)(,)()(0100 xxxxfxfxNn )(,10210 xxxxxxxf)()(,11010 nnxxxxxxxxxf一般通过差商表进行(jnxng)计算).()(xNxLnn 截断误差同Lagrange插值公式(gngsh).第22页/共68页第二十二页，共69页。23 Hermite插值多项式ix

11、2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y求 H(x).(1) 至多(zhdu)(2n+1)次多项式;)., 1 , 0(, )( ,)(niyxHyxHiiii (2)第23页/共68页第二十三页，共69页。24)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xhiixixnx0 x1(2n+1)次多项式 ),()( 21)(2xlxxxlxhiiii 其中(qzhng)li (x)是 Lagrange插值基函数.第24页/共68页第二十四页，共69页。25)()()()(1100 xhyxhy

12、xhyxHnn )()()(1100 xHyxHyxHynn )(xHiixixnx0 x1(2n+1)次多项式),()()(2xlxxxHiii 其中(qzhng)li (x)是 Lagrange插值基函数.第25页/共68页第二十五页，共69页。26 截断误差)()()(xHxfxR .)()()()!22()(22120)22(nnxxxxxxnf Hermite插值的一般形式(xngsh)(见课本122页)第26页/共68页第二十六页，共69页。27第六章 函数(hnsh)逼近 最小二乘一次 (二次)多项式拟合(n h) 函数(hnsh)的最佳平方逼近第27页/共68页第二十七页，共6

13、9页。28问题(wnt): 给定n个数据点 (xi , yi) (i=1, 2, , n)ix2x1xnxiy1y2yny求,2210 xaxaay (或 y=a0+a1x ) 使得(sh de) 212210)( niiiixaxaay达到(d do)最小. 最小二乘一次 (二次)多项式拟合第28页/共68页第二十八页，共69页。29 212210210)(),( niiiixaxaayaaaF 令利用多元(du yun)函数取极值的必要条件得到正则方程组n niix1 niix12 niiy1 niix1 niix12 niix12 niix13 niix14 niix13 niiiyx1

14、 niiiyx120a1a2a由上式求得a0, a1, a2, 得到(d do)最小二乘拟合二次多项式.第29页/共68页第二十九页，共69页。30 最小平方(pngfng)线性多项式逼近3 函数的最佳(zu ji)平方逼近 设 f (x)是区间a, b上的连续函数(hnsh), 求线性多项式函数(hnsh) (x)=a0+a1x 使得, .2)()(2)()(10 babadxxaaxfdxxxf为最小为最小 (x)称为函数 f (x)在区间 a, b 上的一次最佳平方逼近多项式.即求a0, a1使得 .2)()(min2)()()(10 baxgbadxxgxfdxxaaxf线性多项式线性

15、多项式第30页/共68页第三十页，共69页。31 二次最佳平方(pngfng)逼近多项式设 f (x)是区间a, b上的连续函数(hnsh), 求二次多项式函数(hnsh) (x)=a0+a1x+ a2x2 使得, (x)称为函数 f (x)在区间 a, b 上的二次最佳(zu ji)平方逼近多项式. .2)()(min2)()()(2210 baxgbadxxgxfdxxaxaaxf二次多项式二次多项式第31页/共68页第三十一页，共69页。32第七章 数值(shz)微分与数值(shz)积分 复化梯形(txng)公式 复化Simpson公式(gngsh) Romberg算法 Gauss型求积

16、公式 代数精确度 截断误差第32页/共68页第三十二页，共69页。33 代数(dish)精确度设有求积公式(gngsh) nkkkbaxfAdxxf0)()(若它对 f (x)=1, x, x2, xm 都能精确成立(即上式等号成立), 但对 f (x)=xm+1 上式等号不成立, 则称该求积公式具有(jyu)m次代数精确度. 第33页/共68页第三十三页，共69页。34 复化梯形(txng)公式 bannfffffhdxxf)(22)(1210其中(qzhng),nabh .),(ihaxxffiii 截断误差nbaTTdxxffR )()(.:nT ).,(),( 122bafhab 第3

17、4页/共68页第三十四页，共69页。35 复化Simpson公式(gngsh) .:)(2)(43)(2242123120nmbammSffffffffhdxxf 区间(q jin)a, b n等分, n=2m其中(qzhng).nabh 截断误差).,(),(180)()()4(4bafhabSdxxffRnbaS 第35页/共68页第三十五页，共69页。36 梯形(txng)值序列 mT2 递推算法(sun f) mhTTmm2122所有新增加(zngji)节点的函数值之和.其中.2mmabh 第36页/共68页第三十六页，共69页。37 Romberg算法(sun f)1T32T16T8

18、T4T2T2S4S8S16S32S4C8C16C32C8D16D32D8S3448TT 16C1516816SS 636481616CCD 第37页/共68页第三十七页，共69页。38 Gauss型求积公式(gngsh)()(1knkkbaxfAdxxf Ak: 求积系数(xsh),xk: 求积节点(ji din)如果该求积公式具有(2n-1)阶代数精确度, 则称其为Gauss型求积公式.设有求积公式第38页/共68页第三十八页，共69页。39 区间(q jin)-1, 1上的Guass型求积公式 nkkkxfAdxxf111)()(其中求积节点(ji din)xk为n阶Legendre多项式

19、的零点; Ak, xk 的值可查表得到. 一般(ybn)a, b上的Gauss型求积公式可用换元法转化成-1, 1上的Gauss型求积公式.222)(11dtabtabbafdxxfba 第39页/共68页第三十九页，共69页。40第八章 非线性方程(fngchng)解法 二分法(对分区间(q jin)法)求 f (x) = 0 的根 简单(jindn)迭代法 (收敛的充分条件) 牛顿法第40页/共68页第四十页，共69页。4112 kkabx*|x . 12lnlnln abk 设a, b是 f (x)=0的有根区间(q jin), 用二分法迭代 给定精度(jn d), 迭代次数k 满足下式

20、, 能保证满足精度(jn d) 二分法(对分区间(q jin)法)第41页/共68页第四十一页，共69页。42 简单(jindn)迭代法)(0)(xgxxf 构造(guzo)递推公式 01),(xxgxnn适当(shdng)选取.以 逐次逼近 f (x)=0的根. nx如何构造收敛的迭代法?第42页/共68页第四十二页，共69页。43定理(dngl)考虑(kol)方程 x = g(x), g(x)Ca, b, 若( I ) 当 xa, b 时， g(x)a, b；( II ) 0 L 1 使得 | g(x) | L 对 xa, b 成立(chngl)。则任取 x0a, b，由 xk+1 = g

21、(xk) 得到的序列 收敛于g(x) 在a, b上的唯一不动点。并且有误差估计式： 0kkx|11|*|1kkkxxLxx ( k = 1, 2, )|1|*|01xxLLxxk k第43页/共68页第四十三页，共69页。44 牛顿(ni dn)法原理(yunl)：将非线性方程线性化 ( Taylor 展开 ), 1 ,0()()(1 nxfxfxxnnnnxyx*xnxn+1第44页/共68页第四十四页，共69页。45第九章 常微分方程(wi fn fn chn)数值解法 构造常微分方程离散格式的三种(sn zhn)方法 单步法常见(chn jin)格式 多步法常见格式 重要概念: 局部截断

22、误差第45页/共68页第四十五页，共69页。46 用差商近似(jn s)导数 数值积分方法(fngf) Taylor多项式近似(jn s)方法 构造常微分方程离散格式的三种方法第46页/共68页第四十六页，共69页。47 Euler法 改进(gijn)Euler法 经典(jngdin)四阶RK方法 单步法常见(chn jin)格式第47页/共68页第四十七页，共69页。48 多步法常见(chn jin)格式 Simpson公式(gngsh) Adams显隐(xin yn)公式 Adams预测-校正公式第48页/共68页第四十八页，共69页。49 局部(jb)截断误差 整体(zhngt)截断误差

23、Taylor展开(zhn ki)方法 几个重要概念 数值方法的阶数第49页/共68页第四十九页，共69页。50数值(shz)分析总复习例题第50页/共68页第五十页，共69页。51分析(fnx) 333231222111aaaaaaA对称TLL 333231222111llllll0 333222312111llllll0),(jiijlla 其中(qzhng) li为矩阵 L的第 i个行向量.,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一. 用平方根法求线性方程组AX=b, 其中(qzh

24、ng),22484548416 A,321 xxxX.1034 b第51页/共68页第五十一页，共69页。52, 4161111 al, 144112121 lal, 2113131 lal解:,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一. 用平方根法求线性方程组AX=b, 其中(qzhng),22484548416 A,321 xxxX.1034 b第52页/共68页第五十二页，共69页。53一. 用平方根法求线性方程组AX=b, 其中(qzhng), 2152212222 lal,

25、3)(2221313232 lllal, 32322313333 llal解: 332021004LybxLLT , 4161111 al, 144112121 lal, 2113131 lal,22484548416 A,321 xxxX.1034 b第53页/共68页第五十三页，共69页。54解:先解 Ly=b, 再解 LTx=y, 1034332021004321yyy,621 y 621300320214321xxx.2449 x 332021004LybxLLT 一. 用平方根法求线性方程组AX=b, 其中(qzhng),22484548416 A,321 xxxX.1034 b第5

26、4页/共68页第五十四页，共69页。55二. 设有方程组写出Jacobi迭代, Gauss-Seidel迭代的计算公式, 两种迭代法是否(sh fu)收敛? 为什么? ,251084,118104,134410321321321xxxxxxxxxJacobi迭代法不收敛(shulin),Gauss-Seidel迭代法.第55页/共68页第五十五页，共69页。56三. 按下表求 f (x)的四次Hermite插值多项式H(x), 并写出截断误差R (x)=f (x)H(x)的表达式.ix)(ixf)( ixf01212101.212231)(432xxxxxH 第56页/共68页第五十六页，共6

27、9页。57四. (1) 求形如 )10()()(21)(212110 xxxfxfdxxf的求积公式, 使其至少(zhsho)具有两次代数精确度, 该公式是否具有三次代数精确度?解(1) 由已知, 当 f (x)分别(fnbi)为1, x, x2时, 求积公式等号成立. 即1110 dx)11(21 2110 dxx)(2121xx 31102 dxx)(212221xx .32121,3212121xx41103 dxx)(213231xx 故该公式(gngsh)具有3次代数精确度.第57页/共68页第五十七页，共69页。58四. (2) 选用合适的数值积分方法计算的近似值, 要求(yoqi

28、)计算结果具有3位有效数字.dxx 102)cos(解设 f (x)=cos(x2), xk=k/8 (k=0, 1, , 8), fk=f (xk), 则f0=1f1=0.999877932f2=0.998047511f3=0.990128588f4=0.968912422f5=0.924671261f6=0.845924499f7=0.720949381f8=0.540302306梯形(txng)值序列T1=0.770151152T2=0.869531786T4=0.895758895T8=0.902332842Simpson值序列(xli)S2=0.902658664S4=0.90450

29、1264S8=0.904524157梯形值序列的逐次分半算法故904524157. 0)cos(102 dxx第58页/共68页第五十八页，共69页。59五. 设(1) 用迭代公式 求方程 f (x)=0在x0=2.0附近的一个根, 试问(shwn)此迭代法是否收敛? (2) 用合适的方法求 f (x)=0在x0=2.0附近的根, 要求计算结果具有4位有效数字., 1)(23 xxxxf21111kkkxxx 解 (1) 迭代(di di)函数为,111)(2xxxg 验证(ynzhng) g(x)在区间1.7, 2.0上满足压缩映像定理, 故该迭代法收敛.(2) 可用Newton迭代法求根,

30、 取x0=2.0, 写出迭代公式后计算三次得x1=1.857142857, x2=1.839544514, x3=1.839286811. 故x3即为所求方程近似根.第59页/共68页第五十九页，共69页。60六. 确定(qudng)求解初值问题 .)(,),(0yaybxayxfy的二步隐式Adams方法(fngf)5(12111 nnnnnfffhyy 中的参数(cnsh), 使该方法成为三阶方法, 并写出其局部截断误差主项.).()(241, 85)4(41hOxyhRnn 可用数值积分方法或Taylor展开方法第60页/共68页第六十页，共69页。61七. 据资料记载(jzi), 某地

31、某年间间隔30天的日出日落时间如下5月1日5月31日6月30日4:514:174:1619:3819:50日出(r ch)日落(r lu)19:04日出日落时间表请问: 这一年中哪一天白天最长?解 用Newton插值公式较为方便, 答案为:这一年中以6月22日的白天最长.第61页/共68页第六十一页，共69页。62练习(linx)1. 第126页. 求解线性方程组 Ax=b, 其中A如右图所示, 试构造一个与求解三对角方程组的追赶法类似(li s)的直接方法. 2222112211nnnn . 0, 0, 1 iiii 其中(qzhng)第62页/共68页第六十二页，共69页。632. 确定如下(rxi)求积公式中的求积系数, 使其具有尽可能高的代数精确度).( )( )()()(1010bfBafBbfAafAdxxfba 提示: 用三次(sn c)Hermite插值多项式来近似函数 f (x).第63页/共68页第六十三页，共69页。64 3. 若干年以前, 美国原子能委员会准备将浓缩的放