数值分析总复习2012z)

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

2、有效数字位有效数字.5第二章第二章 解线性方程组的直接方法解线性方程组的直接方法 列主元素法列主元素法 LU分解法分解法 (Doolittle分解法分解法) (追赶法追赶法) 平方根法与改进的平方根法平方根法与改进的平方根法 条件数条件数bAx 求求611u1 kiliiu1 jiu1 1 iil1klkil1ilijuiiuju1iu121l12u22uju11kliju), 2 , 1(nj ), 3 , 2(nk ), 1,(niij kil), 1(nik 对对i=2,3, n,ja1 111uak )(112211jiiijijiijululula iiiikiikikkiuulul

3、ula)(112211 7,LUA bLUxbAx , bLy 先求先求再求再求yUx 得得x. 直接三角分解法直接三角分解法或或Doolittle分解法分解法.y8 A: 对称正定阵对称正定阵Cholesky分解分解TLLA 21l11l22l1nl2nl2il1iliilnilnnlTL)(),(jillajiij 设设 li =L的第的第 i个行向量个行向量, 则则,1111al )2(1111 klalkk对对 i=2,3,n,)(2121 iiiiiiillaliiiikiikikkikilllllllal)(112211 )., 1(nik 9bxLLbAxT 先求先求 Ly=b,

4、 再求再求 LTx=y. 平方根法平方根法或或Cholesky分解法分解法.y10第三章第三章 解线性方程组的迭代解法解线性方程组的迭代解法 Jacobi迭代法迭代法 Gauss-Seidel迭代法迭代法 迭代法收敛的条件迭代法收敛的条件(充要条件充要条件, 充分条件充分条件)bAx 求求11 Jacobi迭代法迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k)(k)(k+1), 2 , 1(ni T

5、knkkkxxxx)()(2)(1)(, 12 Gauss-Seidel迭代法迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k+1)(k+1)(k+1), 2 , 1(ni 13 迭代法收敛的充分必要条件迭代法收敛的充分必要条件 )0()()1(,xgMxxkk任意任意收敛收敛. 1)( M 迭代法收敛的充分条件迭代法收敛的充分条件若若A为为严格对角占优或不可约对角占优严格对角占优或不可约对角占优,

6、则求解则求解Ax=b 的的Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.若若A为为对称正定阵对称正定阵, 则则求解求解Ax=b的的Gauss-Seidel迭代迭代法收敛法收敛.14第四章特征值与特征向量的计算第四章特征值与特征向量的计算 幂法和反幂法幂法和反幂法15设设A为为n阶实矩阵阶实矩阵, 其特征值为其特征值为 1, 2, , n, 相应的相应的特特征向量为征向量为u1, u2, , un. 且满足条件且满足条件 n 32 u1, u2, , un线性无关线性无关. 幂法幂法 幂法幂法: 求求 1及其相应的特征向量及其相应的特征向量.此时此时 1一定是实数

7、一定是实数! 1通常称为通常称为主特征值主特征值. 1 16 幂法的计算公式幂法的计算公式 kkkkkkkxyxAyx )()()()1()(max 任取初始向量任取初始向量x(0)=y(0) 0, 对对k=1, 2, , 构造向量序列构造向量序列 x(k), y(k)1 k)max(11)(uuyk 当当k充分大时充分大时17反幂法反幂法 用于计算矩阵按模用于计算矩阵按模最小最小的特征值及其特的特征值及其特征向量征向量, 也可用来计算对应于一个给定近似特征值也可用来计算对应于一个给定近似特征值的特征向量的特征向量, 是目前求特征向量最有效的方法是目前求特征向量最有效的方法. 反幂法反幂法18

8、 反幂法迭代公式为反幂法迭代公式为 任取初始向量任取初始向量x(0)=y(0) 0, 构造向量序列构造向量序列)., 2 , 1 , 0()max()1()1()1()(1)1( kxxyyAxkkkkk 迭代向量迭代向量x(k+1)可以通过解方程组求得可以通过解方程组求得)()1(kkyAx nkx 1)max( )max()(nnkuuy 当当k充分大时充分大时19第五章第五章 插值法插值法 Lagrange插值插值 Newton插值插值 Hermite插值插值20问题问题:ix2x1xnx)(iixfy 1y2yny0 x0y求求 Ln(x).(1) 至多至多n次多项式次多项式;).,

9、1 , 0()()(niyxfxLiiin (2)21 Lagrange插值插值)()()()()(1100 xlyxlyxlyxlyxLnniin 其中其中 li (x) 为插值为插值基函数基函数(1) n次多项式次多项式);, 1 , 0( , 0)(, 1)(ijnjxlxljiii ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni 截断误差截断误差)()()(xLxfxRnn . )()!1()(0)1( niinxxnf (2) 22 差商差商一阶差商一阶差商jijijixxxfxfxxf )()(,二阶差商二阶差商kikjjikjixxxxfxxfxxxf ,

10、 k阶差商阶差商kkkkxxxxxfxxxfxxxf 02111010,23 Newton插值公式插值公式)(,)()(0100 xxxxfxfxNn )(,10210 xxxxxxxf)()(,11010 nnxxxxxxxxxf一般通过差商表进行计算一般通过差商表进行计算).()(xNxLnn 截断误差同截断误差同Lagrange插值公式插值公式. 24 Hermite插值多项式插值多项式ix2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y求求 H(x).(1) 至多至多(2n+1)次多项式次多项式;)., 1 , 0(, )( ,)(niyxHyxHi

11、iii (2)25)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xhiixixnx0 x1(2n+1)次多项式次多项式 ),()( 21)(2xlxxxlxhiiii 其中其中li (x)是是 Lagrange插值基函数插值基函数. 26)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xHiixixnx0 x1(2n+1)次多项式次多项式),()()(2xlxxxHiii 其中其中li (x)是是 Lagrange插值基函数插值基函数. 27 截断误差截断误差)()()(xHxfx

12、R .)()()()!22()(22120)22(nnxxxxxxnf Hermite插值的一般形式插值的一般形式(见课本见课本122页页)28第六章第六章 函数逼近函数逼近 最小二乘一次最小二乘一次 (二次二次)多项式拟合多项式拟合 函数的最佳平方逼近函数的最佳平方逼近29问题问题: 给定给定n个数据点个数据点 (xi , yi) (i=1, 2, , n)ix2x1xnxiy1y2yny求求,2210 xaxaay (或或 y=a0+a1x ) 使得使得 212210)( niiiixaxaay达到最小达到最小. 最小二乘一次最小二乘一次 (二次二次)多项式拟合多项式拟合30 212210

13、210)(),( niiiixaxaayaaaF 令令利用多元函数取极值的必要条件得到正则方程组利用多元函数取极值的必要条件得到正则方程组n niix1 niix12 niiy1 niix1 niix12 niix12 niix13 niix14 niix13 niiiyx1 niiiyx120a1a2a由上式求得由上式求得a0, a1, a2, 得到得到最小二乘拟合二次多项式最小二乘拟合二次多项式.31 最小平方线性多项式逼近最小平方线性多项式逼近3 函数的最佳平方逼近函数的最佳平方逼近 设设 f (x)是区间是区间a, b上的连续函数上的连续函数, 求线性多项式求线性多项式函数函数 (x)

14、=a0+a1x 使得使得, .2)()(2)()(10 babadxxaaxfdxxxf为最小为最小 (x)称为函数称为函数 f (x)在区间在区间 a, b 上的上的一次最佳平方逼一次最佳平方逼近多项式近多项式.即求即求a0, a1使得使得 .2)()(min2)()()(10 baxgbadxxgxfdxxaaxf线性多项式线性多项式32 二次最佳平方逼近多项式二次最佳平方逼近多项式设设 f (x)是区间是区间a, b上的连续函数上的连续函数, 求二次多项式函求二次多项式函数数 (x)=a0+a1x+ a2x2 使得使得, (x)称为函数称为函数 f (x)在区间在区间 a, b 上的上的

15、二次最佳平方二次最佳平方逼近多项式逼近多项式. .2)()(min2)()()(2210 baxgbadxxgxfdxxaxaaxf二次多项式二次多项式33第七章第七章 数值微分与数值积分数值微分与数值积分 复化梯形公式复化梯形公式 复化复化Simpson公式公式 Romberg算法算法 Gauss型求积公式型求积公式 代数精确度代数精确度 截断误差截断误差34 代数精确度代数精确度设有求积公式设有求积公式 nkkkbaxfAdxxf0)()(若它对若它对 f (x)=1, x, x2, xm 都能精确成立都能精确成立(即上式等即上式等号成立号成立), 但对但对 f (x)=xm+1 上式等号

16、不成立上式等号不成立, 则称该求则称该求积公式具有积公式具有m次代数精确度次代数精确度. 35 复化梯形公式复化梯形公式 bannfffffhdxxf)(22)(1210其中其中,nabh .),(ihaxxffiii 截断误差截断误差nbaTTdxxffR )()(.:nT ).,(),( 122bafhab 36 复化复化Simpson公式公式 .:)(2)(43)(2242123120nmbammSffffffffhdxxf 区间区间a, b n等分等分, n=2m其中其中.nabh 截断误差截断误差).,(),(180)()()4(4bafhabSdxxffRnbaS 37 梯形值序列

17、梯形值序列 mT2 递推算法递推算法 mhTTmm2122所有新增加节点的函数值之和所有新增加节点的函数值之和.其中其中.2mmabh 38 Romberg算法算法1T32T16T8T4T2T2S4S8S16S32S4C8C16C32C8D16D32D8S3448TT 16C1516816SS 636481616CCD 39 Gauss型求积公式型求积公式)()(1knkkbaxfAdxxf Ak: 求积系数求积系数,xk: 求积节点求积节点如果该求积公式具有如果该求积公式具有(2n-1)阶代数精确度阶代数精确度, 则称则称其为其为Gauss型求积公式型求积公式.设有求积公式设有求积公式40

18、区间区间-1, 1上的上的Guass型求积公式型求积公式 nkkkxfAdxxf111)()(其中求积节点其中求积节点xk为为n阶阶Legendre多项式的多项式的零点零点; Ak, xk 的值可查表得到的值可查表得到. 一般一般a, b上的上的Gauss型求积公式可用换元法型求积公式可用换元法转化成转化成-1, 1上的上的Gauss型求积公式型求积公式.222)(11dtabtabbafdxxfba 41第八章第八章 非线性方程解法非线性方程解法 二分法二分法(对分区间法对分区间法)求求 f (x) = 0 的根的根 简单迭代法简单迭代法 (收敛的充分条件收敛的充分条件) 牛顿法牛顿法421

19、2 kkabx*|x . 12lnlnln abk 设设a, b是是 f (x)=0的有根区间的有根区间, 用二分法迭代用二分法迭代 给定精度给定精度 , 迭代次数迭代次数k 满足下式满足下式, 能保证满足精度能保证满足精度 二分法二分法(对分区间法对分区间法)43 简单迭代法简单迭代法)(0)(xgxxf 构造递推公式构造递推公式 01),(xxgxnn适当选取适当选取.以以 逐次逼近逐次逼近 f (x)=0的根的根. nx如何构造收敛的迭代法如何构造收敛的迭代法?44定理定理考虑方程考虑方程 x = g(x), g(x) Ca, b, 若若( I ) 当当 x a, b 时，时， g(x)

20、 a, b；( II ) 0 L 1 使得使得 | g(x) | L 对对 x a, b 成立。成立。则任取则任取 x0 a, b，由，由 xk+1 = g(xk) 得到的序列得到的序列 收敛于收敛于g(x) 在在a, b上的唯一不动点。并且有误差估上的唯一不动点。并且有误差估计式：计式： 0kkx|11|*|1kkkxxLxx ( k = 1, 2, )|1|*|01xxLLxxk k45 牛顿法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 ( Taylor 展开展开 ), 1 ,0()()(1 nxfxfxxnnnnxyx*xnxn+146第九章第九章 常微分方程数值解法常微分方

21、程数值解法 构造常微分方程离散格式的三种方法构造常微分方程离散格式的三种方法 单步法常见格式单步法常见格式 多步法常见格式多步法常见格式 重要概念重要概念: 局部截断误差局部截断误差47 用差商近似导数用差商近似导数 数值积分方法数值积分方法 Taylor多项式近似方法多项式近似方法 构造常微分方程离散格式的三种方法构造常微分方程离散格式的三种方法48 Euler法法 改进改进Euler法法 经典四阶经典四阶RK方法方法 单步法常见格式单步法常见格式49 多步法常见格式多步法常见格式 Simpson公式公式 Adams显隐公式显隐公式 Adams预测预测-校正公式校正公式50 局部截断误差局部

22、截断误差 整体截断误差整体截断误差Taylor展开方法展开方法 几个重要概念几个重要概念 数值方法的阶数数值方法的阶数51数值分析总复习例题数值分析总复习例题52分析分析 333231222111aaaaaaA对称对称TLL 333231222111llllll0 333222312111llllll0),(jiijlla 其中其中 li为矩阵为矩阵 L的第的第 i个行向量个行向量.,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b,

23、其中其中,22484548416 A,321 xxxX.1034 b53, 4161111 al, 144112121 lal, 2113131 lal解解:,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中,22484548416 A,321 xxxX.1034 b54一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中, 2152212222 lal, 3)(2221313232 lllal, 323

24、22313333 llal解解: 332021004LybxLLT , 4161111 al, 144112121 lal, 2113131 lal,22484548416 A,321 xxxX.1034 b55解解: 先解先解 Ly=b, 再解再解 LTx=y, 1034332021004321yyy,621 y 621300320214321xxx.2449 x 332021004LybxLLT 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中,22484548416 A,321 xxxX.1034 b56二二. 设有方程组设有方程组写出写出Jacobi迭代迭代,

25、Gauss-Seidel迭代迭代的计算公式的计算公式, 两两种迭代法是否收敛种迭代法是否收敛? 为什么为什么? ,251084,118104,134410321321321xxxxxxxxxJacobi迭代法不收敛迭代法不收敛,Gauss-Seidel迭代法迭代法.57三三. 按下表求按下表求 f (x)的四次的四次Hermite插值多项式插值多项式H(x), 并写出截断误差并写出截断误差R (x)=f (x) H(x)的表达式的表达式.ix)(ixf)( ixf0121210 1.212231)(432xxxxxH 58四四. (1) 求形如求形如 )10()()(21)(212110 xx

26、xfxfdxxf的求积公式的求积公式, 使其至少具有两次代数精确度使其至少具有两次代数精确度, 该公式是该公式是否具有三次代数精确度否具有三次代数精确度?解解 (1) 由已知由已知, 当当 f (x)分别为分别为1, x, x2时时, 求积公式等号求积公式等号成立成立. 即即1110 dx)11(21 2110 dxx)(2121xx 31102 dxx)(212221xx .32121,3212121xx41103 dxx)(213231xx 故该公式具有故该公式具有3次代数次代数精确度精确度.59四四. (2) 选用合适的数值积分方法计算选用合适的数值积分方法计算的近似值的近似值, 要求计

27、算结果具有要求计算结果具有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梯形值序列梯形值序列T1=0.770151152T2=0.869531786T4=0.895758895T8=0.902332842Simpson值序列值序列S2=0.9026586

28、64S4=0.904501264S8=0.904524157梯形值序列的逐次分半算法梯形值序列的逐次分半算法故故904524157. 0)cos(102 dxx60五五. 设设(1) 用迭代公式用迭代公式 求方程求方程 f (x)=0在在x0=2.0附近的一个根附近的一个根, 试问此迭代法是否收敛试问此迭代法是否收敛? (2) 用合适的方法求用合适的方法求 f (x)=0在在x0=2.0附近的根附近的根, 要求要求计算结果具有计算结果具有4位有效数字位有效数字., 1)(23 xxxxf21111kkkxxx 解解 (1) 迭代函数为迭代函数为,111)(2xxxg 验证验证 g(x)在区间在

29、区间1.7, 2.0上满足压缩映像定理上满足压缩映像定理, 故故该迭代法收敛该迭代法收敛.(2) 可用可用Newton迭代法求根迭代法求根, 取取x0=2.0, 写出迭代公写出迭代公式后计算三次得式后计算三次得x1=1.857142857, x2=1.839544514, x3=1.839286811. 故故x3即为所求方程近似根即为所求方程近似根.61六六. 确定求解初值问题确定求解初值问题 .)(,),(0yaybxayxfy的二步隐式的二步隐式Adams方法方法)5(12111 nnnnnfffhyy 中的参数中的参数 , 使该方法成为三阶方法使该方法成为三阶方法, 并写出其局部并写出其

30、局部截断误差主项截断误差主项.).()(241, 85)4(41hOxyhRnn 可用数值积分方法或可用数值积分方法或Taylor展开方法展开方法62七七. 据资料记载据资料记载, 某地某年间间隔某地某年间间隔30天的日出日落天的日出日落时间如下时间如下5月月1日日 5月月31日日6月月30日日4:514:174:1619:3819:50日出日出日落日落19:04日出日落时间表日出日落时间表请问请问: 这一年中哪一天白天最这一年中哪一天白天最长长?解解 用用Newton插值公式较为方便插值公式较为方便, 答案为答案为:这一年中以这一年中以6月月22日的白天最日的白天最长长.63练习练习1. 第

31、第126页页. 求解线性方求解线性方程组程组 Ax=b, 其中其中A如右图如右图所示所示, 试构造一个与求解试构造一个与求解三对角方程组的追赶法三对角方程组的追赶法类似的直接方法类似的直接方法. 2222112211nnnn . 0, 0, 1 iiii 其中其中642. 确定如下求积公式中的求积系数确定如下求积公式中的求积系数, 使其具有使其具有尽可能高的代数精确度尽可能高的代数精确度).( )( )()()(1010bfBafBbfAafAdxxfba 提示提示: 用三次用三次Hermite插值多项式来近似函数插值多项式来近似函数 f (x).65 3. 若干年以前若干年以前, 美国原子能委员会准备将浓缩的放射美国原子能委员会准备将浓缩的放