北理工数值分析总复习2008

1、12 上机题请在上机题请在12月月24日之前交，强烈建议日之前交，强烈建议交打印稿。若通过电子邮件交，文件名交打印稿。若通过电子邮件交，文件名为：为：学号姓名学号姓名.rar, 压缩文件中若压缩文件中若有有word文档存成文档存成.doc文件文件. 答疑时间：答疑时间：12月月15，16，17，22，23，24（即下星期和下下星期（即下星期和下下星期1，2，3）晚上）晚上7:309:30，上机作业也在答疑时间交。，上机作业也在答疑时间交。 答疑地点：中教答疑地点：中教816。3第一章第一章 误差误差 绝对（相对）误差绝对（相对）误差 ( 限限 ) 有效数字有效数字4 有效数字有效数字x: 精确

2、值精确值x*: 近似值近似值, 其科学记数法为其科学记数法为),0(10. 0*121 aaaaxmn若若nmxx 1021|*|则称近似值则称近似值 x*具有具有n位有效数字位有效数字.5第二章第二章 解线性方程组的直接方法解线性方程组的直接方法 列主元素法列主元素法 LU分解法分解法 (Doolittle分解法分解法) (追赶法追赶法) 平方根法与改进的平方根法平方根法与改进的平方根法 条件数条件数bAx 求求611u1 kiliiu1 jiu1 1 iil1klkil1ilijuiiuju1iu121l12u22uju11kliju), 2 , 1(nj ), 3 , 2(nk ), 1

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

4、3,n,)(2121 iiiiiiillaliiiikiikikkikilllllllal)(112211 )., 1(nik 9bxLLbAxT 先求先求 Ly=b, 再求再求 LTx=y. 平方根法平方根法或或Cholesky分解法分解法.y10第三章第三章 解线性方程组的迭代解法解线性方程组的迭代解法 Jacobi迭代法迭代法 Gauss-Seidel迭代法迭代法 迭代法收敛的条件迭代法收敛的条件(充要条件充要条件, 充分条件充分条件)bAx 求求11 Jacobi迭代法迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibx

5、axaxaxaxa ,111111iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k)(k)(k+1), 2 , 1(ni Tknkkkxxxx)()(2)(1)(, 12 Gauss-Seidel迭代法迭代法,111111ininiiiiiiiiiibxaxaxaxaxa ,111111ininiiiiiiiiiibxaxaxaxaxa ,111111iiiniiiniiiiiiiiiiiiiiabxaaxaaxaaxaax (k)(k)(k+1)(k+1)(k+1), 2 , 1(ni 13 迭代法收敛的充分必要条件迭代法收敛的充分必要条件 )0(

6、)()1(,xgMxxkk任意任意收敛收敛. 1)( M 迭代法收敛的充分条件迭代法收敛的充分条件若若A为为严格对角占优或不可约对角占优严格对角占优或不可约对角占优, 则求解则求解Ax=b 的的Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.若若A为为对称正定阵对称正定阵, 则当则当0 2时时, 求解求解Ax=b的松弛的松弛法收敛法收敛, 特别地特别地Gauss-Seidel迭代法收敛迭代法收敛.14第四章特征值与特征向量的计算第四章特征值与特征向量的计算 幂法和反幂法幂法和反幂法15设设A为为n阶实矩阵阶实矩阵, 其特征值为其特征值为 1, 2, , n, 相应

7、的相应的特特征向量为征向量为u1, u2, , un. 且满足条件且满足条件 n 32 u1, u2, , un线性无关线性无关. 幂法幂法 幂法幂法: 求求 1及其相应的特征向量及其相应的特征向量.此时此时 1一定是实数一定是实数! 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反幂法反幂法 用于计算矩阵按模用于计算矩阵按模最

8、小最小的特征值及其特的特征值及其特征向量征向量, 也可用来计算对应于一个给定近似特征值也可用来计算对应于一个给定近似特征值的特征向量的特征向量, 是目前求特征向量最有效的方法是目前求特征向量最有效的方法. 反幂法反幂法18 反幂法迭代公式为反幂法迭代公式为 任取初始向量任取初始向量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第五章

9、第五章 插值法插值法 Lagrange插值插值 Newton插值插值 Hermite插值插值20问题问题:ix2x1xnx)(iixfy 1y2yny0 x0y求求 Ln(x).(1) 至多至多n次多项式次多项式;)., 1 , 0()()(niyxfxLiiin (2)21 Lagrange插值插值)()()()()(1100 xlyxlyxlyxlyxLnniin 其中其中 li (x) 为插值为插值基函数基函数(1) n次多项式次多项式);, 1 , 0( , 0)(, 1)(ijnjxlxljiii ,)()()(0 nijjjijixxxxxl)., 1 , 0(ni 截断误差截断误

10、差)()()(xLxfxRnn . )()!1()(0)1( niinxxnf (2) 22 差商差商一阶差商一阶差商jijijixxxfxfxxf )()(,二阶差商二阶差商kikjjikjixxxxfxxfxxxf , k阶差商阶差商kkkkxxxxxfxxxfxxxf 02111010,23 Newton插值公式插值公式)(,)()(0100 xxxxfxfxNn )(,10210 xxxxxxxf)()(,11010 nnxxxxxxxxxf一般通过差商表进行计算一般通过差商表进行计算).()(xNxLnn 截断误差同截断误差同Lagrange插值公式插值公式. 24 Hermite插

11、值多项式插值多项式ix2x1xnx)(iixfy 1y2yny0 x0y)( iixfy 1y2yny0y求求 H(x).(1) 至多至多(2n+1)次多项式次多项式;)., 1 , 0(, )( ,)(niyxHyxHiiii (2)25)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHyxHyxHynn )(xhiixixnx0 x1(2n+1)次多项式次多项式 ),()( 21)(2xlxxxlxhiiii 其中其中li (x)是是 Lagrange插值基函数插值基函数. 26)()()()(1100 xhyxhyxhyxHnn )()()(1100 xHy

12、xHyxHynn )(xHiixixnx0 x1(2n+1)次多项式次多项式),()()(2xlxxxHiii 其中其中li (x)是是 Lagrange插值基函数插值基函数. 27 截断误差截断误差)()()(xHxfxR .)()()()!22()(22120)22(nnxxxxxxnf Hermite插值的一般形式插值的一般形式(见课本见课本122页页)28第六章第六章 函数逼近函数逼近 最小二乘一次最小二乘一次 (二次二次)多项式拟合多项式拟合 Legendre正交多项式正交多项式29问题问题: 给定给定n个数据点个数据点 (xi , yi) (i=1, 2, , n)ix2x1xnx

13、iy1y2yny求求,2210 xaxaay (或或 y=a0+a1x ) 使得使得 212210)( niiiixaxaay达到最小达到最小. 最小二乘一次最小二乘一次 (二次二次)多项式拟合多项式拟合30 212210210)(),( niiiixaxaayaaaF 令令利用多元函数取极值的必要条件得到正则方程组利用多元函数取极值的必要条件得到正则方程组n niix1 niix12 niiy1 niix1 niix12 niix12 niix13 niix14 niix13 niiiyx121niiix y0a1a2a由上式求得由上式求得a0, a1, a2, 得到得到最小二乘拟合二次多项

14、式最小二乘拟合二次多项式.31第七章第七章 数值微分与数值积分数值微分与数值积分 复化梯形公式复化梯形公式 复化复化Simpson公式公式 Romberg算法算法 Gauss型求积公式型求积公式 代数精确度代数精确度 截断误差截断误差32 代数精确度代数精确度设有求积公式设有求积公式 nkkkbaxfAdxxf0)()(若它对若它对 f (x)=1, x, x2, xm 都能精确成立都能精确成立(即上式等即上式等号成立号成立), 但对但对 f (x)=xm+1 上式等号不成立上式等号不成立, 则称该求则称该求积公式具有积公式具有m次代数精确度次代数精确度. 33 复化梯形公式复化梯形公式 ba

15、nnfffffhdxxf)(22)(1210其中其中,nabh .),(ihaxxffiii 截断误差截断误差nbaTTdxxffR )()(.:nT ).,(),( 122bafhab 34 复化复化Simpson公式公式 .:)(2)(43)(2242123120nmbammSffffffffhdxxf 区间区间a, b n等分等分, n=2m其中其中.nabh 截断误差截断误差).,(),(180)()()4(4bafhabSdxxffRnbaS 35 梯形值序列梯形值序列 mT2 递推算法递推算法 mhTTmm2122所有新增加节点的函数值之和所有新增加节点的函数值之和.其中其中.2m

16、mabh 36 Romberg算法算法1T32T16T8T4T2T2S4S8S16S32S4C8C16C32C8D16D32D8S3448TT 16C1516816SS 636481616CCD 37 Gauss型求积公式型求积公式)()(1knkkbaxfAdxxf Ak: 求积系数求积系数,xk: 求积节点求积节点如果该求积公式具有如果该求积公式具有(2n-1)阶代数精确度阶代数精确度, 则称则称其为其为Gauss型求积公式型求积公式.设有求积公式设有求积公式38 区间区间-1, 1上的上的Guass型求积公式型求积公式 nkkkxfAdxxf111)()(其中求积节点其中求积节点xk为为

17、n阶阶Legendre多项式的多项式的零点零点; Ak, xk 的值可查表得到的值可查表得到. 一般一般a, b上的上的Gauss型求积公式可用换元型求积公式可用换元法转化成法转化成-1, 1上的上的Gauss型求积公式型求积公式.222)(11dtabtabbafdxxfba 39第八章第八章 非线性方程解法非线性方程解法 二分法二分法(对分区间法对分区间法)求求 f (x) = 0 的根的根 简单迭代法简单迭代法 (收敛的充分条件收敛的充分条件) 牛顿法牛顿法 割线法割线法4012 kkabx*|x . 12lnlnln abk 设设a, b是是 f (x)=0的有根区间的有根区间, 用二

18、分法迭代用二分法迭代 给定精度给定精度 , 迭代次数迭代次数k 满足下式满足下式, 能保证满足精度能保证满足精度 二分法二分法(对分区间法对分区间法)41 简单迭代法简单迭代法)(0)(xgxxf 构造递推公式构造递推公式 01),(xxgxnn适当选取适当选取.以以 逐次逼近逐次逼近 f (x)=0的根的根. nx如何构造收敛的迭代法如何构造收敛的迭代法?42定理定理考虑方程考虑方程 x = g(x), g(x) Ca, b, 若若( I ) 当当 x a, b 时，时， g(x) a, b；( II ) 0 L 1 使得使得 | g(x) | L 对对 x a, b 成立。成立。则任取则任

19、取 x0 a, b，由，由 xk+1 = g(xk) 得到的序列得到的序列 收敛于收敛于g(x) 在在a, b上的唯一不动点。并且有误差估上的唯一不动点。并且有误差估计式：计式： 0kkx|11|*|1kkkxxLxx ( k = 1, 2, )|1|*|01xxLLxxk k43 牛顿法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 ( Taylor 展开展开 ), 1 ,0()()(1 nxfxfxxnnnnxyx*xnxn+144第九章第九章 常微分方程数值解法常微分方程数值解法 构造常微分方程离散格式的三种方法构造常微分方程离散格式的三种方法 单步法常见格式单步法常见格式 多步

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

21、的阶数49数值分析总复习例题数值分析总复习例题50分析分析 333231222111aaaaaaA对称对称TLL 333231222111llllll0 333222312111llllll0),(jiijlla 其中其中 li为矩阵为矩阵 L的第的第 i个行向量个行向量.,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中,22484548416 A,321 xxxX.1034 b51, 4161111 al, 144112

22、121 lal, 2113131 lal解解:,1111al ,112121lal ,113131lal ,2212222lal ,2231213232lllal .2322313333llal 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中,22484548416 A,321 xxxX.1034 b52一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中, 2152212222 lal, 3)(2221313232 lllal, 32322313333 llal解解: 332021004LybxLLT , 4161111 al, 14411212

23、1 lal, 2113131 lal,22484548416 A,321 xxxX.1034 b53解解: 先解先解 Ly=b, 再解再解 LTx=y, 1034332021004321yyy,621 y 621300320214321xxx.2449 x 332021004LybxLLT 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中,22484548416 A,321 xxxX.1034 b54二二. 设有方程组设有方程组写出写出Jacobi迭代迭代, Gauss-Seidel迭代迭代的计算公式的计算公式, 两两种迭代法是否收敛种迭代法是否收敛? 为什么为什么?

24、,251084,118104,134410321321321xxxxxxxxxJacobi迭代法不收敛迭代法不收敛,Gauss-Seidel迭代法迭代法, =1.2的的SOR迭代法收敛迭代法收敛.55三三. 按下表求按下表求 f (x)的四次的四次Hermite插值多项式插值多项式H(x), 并写出截断误差并写出截断误差R (x)=f (x) H(x)的表达式的表达式.ix)(ixf)( ixf0121210 1.212231)(432xxxxxH 56四四. (1) 求形如求形如 )10()()(21)(212110 xxxfxfdxxf的求积公式的求积公式, 使其至少具有两次代数精确度使其

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

26、s(解解 设设 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.902658664S4=0.904501264S8=0.904524157梯形值序列

27、的逐次分半算法梯形值序列的逐次分半算法故故904524157. 0)cos(102 dxx58五五. 设设(1) 用迭代公式用迭代公式 求方程求方程 f (x)=0在在x0=2.0附近的一个根附近的一个根, 试问此迭代法是否收敛试问此迭代法是否收敛? (2) 用合适的方法求用合适的方法求 f (x)=0在在x0=2.0附近的根附近的根, 要求要求计算结果具有计算结果具有4位有效数字位有效数字., 1)(23 xxxxf21111kkkxxx 解解 (1) 迭代函数为迭代函数为,111)(2xxxg 验证验证 g(x)在区间在区间1.7, 2.0上满足压缩映像定理上满足压缩映像定理, 故故该迭代

28、法收敛该迭代法收敛.(2) 可用可用Newton迭代法求根迭代法求根, 取取x0=2.0, 写出迭代公写出迭代公式后计算三次得式后计算三次得x1=1.857142857, x2=1.839544514, x3=1.839286811. 故故x3即为所求方程近似根即为所求方程近似根.59六六. 确定求解初值问题确定求解初值问题 .)(,),(0yaybxayxfy的二步隐式的二步隐式Adams方法方法)5(12111 nnnnnfffhyy 中的参数中的参数 , 使该方法成为三阶方法使该方法成为三阶方法, 并写出其局部并写出其局部截断误差主项截断误差主项.).()(241, 85)4(41hOx

29、yhRnn 可用数值积分方法或可用数值积分方法或Taylor展开方法展开方法60七七. 据资料记载据资料记载, 某地某年间间隔某地某年间间隔30天的日出日落天的日出日落时间如下时间如下5月月1日日 5月月31日日6月月30日日4:514:174:1619:3819:50日出日出日落日落19:04日出日落时间表日出日落时间表请问请问: 这一年中哪一天白天最这一年中哪一天白天最长长?解解 用用Newton插值公式较为方便插值公式较为方便, 答案为答案为:这一年中以这一年中以6月月22日的白天最日的白天最长长.61练习练习1. 第第126页页. 求解线性方求解线性方程组程组 Ax=b, 其中其中A如

30、右图如右图所示所示, 试构造一个与求解试构造一个与求解三对角方程组的追赶法三对角方程组的追赶法类似的直接方法类似的直接方法. 2222112211nnnn . 0, 0, 1 iiii 其中其中622. 已知方程组已知方程组Ax=b, 其中其中 11,212321bxxxA若有迭代公式若有迭代公式),()()()1(bAxaxxkkk 试确定使该公式收敛的实数试确定使该公式收敛的实数a的最大取值范围的最大取值范围.633. 方程方程 f (x)=x3+10 x 20=0是矩阵是矩阵 01020100010A的特征方程的特征方程, 试用带原点移位的反幂法求试用带原点移位的反幂法求 f (x)=0

31、在在x0=1.5附近的根附近的根. 取初始迭代向量为取初始迭代向量为 x(0)=(0.4, 0.6, 1)T.(用求解矩阵特征值的方法来求多项式的根用求解矩阵特征值的方法来求多项式的根)用计算器迭代一次用计算器迭代一次, 或用计算机求具六位有效数字的或用计算机求具六位有效数字的近似值近似值.644. 设设x0, x1, , xn 为为 n+1个互异节点个互异节点, lj (x) (j=0, 1, , n)为这组节点上的为这组节点上的n次次Lagrange插值基函数插值基函数, 证明证明. )()(0011 njjnjjnjnxxxlxx655. 已知函数已知函数 y=f (x)=x3+10 x

32、 20的函数表如下的函数表如下xi 1.5 1.6 1.7yi 1.625 0.096 1.913由于由于 f (x)为为x 的严格单调增加函数的严格单调增加函数, 故可确定出反函故可确定出反函数数 x=x(y), 试用上表求试用上表求x(因变量因变量)关于关于y(自变量自变量)的二的二次插值多项式在次插值多项式在 y=0点的值点的值, 以此值作为方程以此值作为方程 f (x)=0的近似根的近似根. (反插值求根反插值求根)666. 已知函数表已知函数表 xj 0.10 0.20 0.40 0.50yj 21.00 11.00 7.00 6.00试用函数试用函数 作最小二乘曲线拟合作最小二乘曲线拟合, 确确定参数定参数C1和和C2, 结果取结果取3位有效数字位有效数字.xCxCy21 677. 确定如下求积公式中的求积系数确定如下求积公式中的求积系数, 使其具有使其具有尽可能高的代数精确度尽可能高的代数精确度).( )( )()()(1010bfBafBbfAafAdxxfba 提示提示: 用三次用三次Hermite插值多项式来近似函数插值多项式来近似函数 f (x).688. 从地面发射一枚火箭从地面发射一枚火箭, 在最初在