北京理工大学数值分析总复习2012PPT.ppt

1考试时带计算器考试时带计算器•上机题请在上机题请在11月月30日晚日晚9:30之前交，交打之前交，交打印稿•答疑时间：答疑时间：11月月28，，29, 30（即星期（即星期3, 4，，5）晚上）晚上7:30—9:30，上机作业也在答，上机作业也在答疑时间交疑时间交•答疑地点：中教答疑地点：中教8162第一章第一章 误差误差 绝对（相对）误差绝对（相对）误差 ( 限限 ) 有效数字有效数字3  有效数字有效数字x: 精确值精确值x*: 近似值近似值, 其科学记数法为其科学记数法为若若则称近似值则称近似值 x*具有具有n位有效数字位有效数字.4第二章第二章 解线性方程组的直接方法解线性方程组的直接方法 列主元素法列主元素法 LU分解法分解法 (Doolittle分解法分解法) (追赶法追赶法) 平方根法与改进的平方根法平方根法与改进的平方根法 条件数条件数求求5对对i=2,3,…, n,6先求先求再求再求得得x.  直接三角分解法直接三角分解法或或Doolittle分解法分解法.7 A: 对称正定阵对称正定阵Cholesky分解分解设设 li =L的第的第 i个行向量个行向量, 则则对对 i=2,3,…,n,8先求先求 Ly=b, 再求再求 LTx=y.  平方根法平方根法或或Cholesky分解法分解法.9第三章第三章 解线性方程组的迭代解法解线性方程组的迭代解法 Jacobi迭代法迭代法 Gauss-Seidel迭代法迭代法 迭代法收敛的条件迭代法收敛的条件(充要条件充要条件, 充分条件充分条件)求求10 Jacobi迭代法迭代法(k)(k)(k)(k)(k+1) 11 Gauss-Seidel迭代法迭代法(k)(k)(k+1)(k+1)(k+1) 12  迭代法收敛的充分必要条件迭代法收敛的充分必要条件任意任意收敛收敛  迭代法收敛的充分条件迭代法收敛的充分条件若若A为为严格对角占优或不可约对角占优严格对角占优或不可约对角占优, 则求解则求解Ax=b 的的Jacobi迭代法和迭代法和Gauss-Seidel迭代法均收敛迭代法均收敛.若若A为为对称正定阵对称正定阵, 则则求解求解Ax=b的的Gauss-Seidel迭代迭代法收敛法收敛.13第四章　特征值与特征向量的计算第四章　特征值与特征向量的计算 幂法和反幂法幂法和反幂法14设设A为为n阶实矩阵阶实矩阵, 其特征值为其特征值为 1,  2, …,  n, 相应的相应的特特征向量为征向量为u1, u2, …, un. 且满足条件且满足条件 　　u1, u2, …, un线性无关线性无关.  幂法幂法 幂法幂法: 求求 1及其相应的特征向量及其相应的特征向量.此时此时 1一定是实数一定是实数!   1通常称为通常称为主特征值主特征值.15  幂法的计算公式幂法的计算公式 任取初始向量任取初始向量x(0)=y(0) 0, 对对k=1, 2, …, 构造向量序列构造向量序列 {x(k)}, {y(k)} 当当k充分大时充分大时16反幂法反幂法 用于计算矩阵按模用于计算矩阵按模最小最小的特征值及其特的特征值及其特征向量征向量, 也可用来计算对应于一个给定近似特征值也可用来计算对应于一个给定近似特征值的特征向量的特征向量, 是目前求特征向量最有效的方法是目前求特征向量最有效的方法.  反幂法反幂法17  反幂法迭代公式为反幂法迭代公式为 任取初始向量任取初始向量x(0)=y(0) 0, 构造向量序列构造向量序列 迭代向量迭代向量x(k+1)可以通过解方程组求得可以通过解方程组求得 当当k充分大时充分大时18第五章第五章 插值法插值法 Lagrange插值插值 Newton插值插值 Hermite插值插值19问题问题:求求 Ln(x).(1) 至多至多n次多项式次多项式;(2)20 Lagrange插值插值其中其中 li (x) 为插值为插值基函数基函数(1) n次多项式次多项式  截断误差截断误差(2) 21 差商差商一阶差商一阶差商二阶差商二阶差商 k阶差商阶差商22 Newton插值公式插值公式一般通过差商表进行计算一般通过差商表进行计算  截断误差同截断误差同Lagrange插值公式插值公式. 23 Hermite插值多项式插值多项式求求 H(x).(1) 至多至多(2n+1)次多项式次多项式;(2)24(2n+1)次多项式次多项式其中其中li (x)是是 Lagrange插值基函数插值基函数. 25(2n+1)次多项式次多项式其中其中li (x)是是 Lagrange插值基函数插值基函数. 26  截断误差截断误差  Hermite插值的一般形式插值的一般形式(见课本见课本122页页)27第六章第六章 函数逼近函数逼近 最小二乘一次最小二乘一次 (二次二次)多项式拟合多项式拟合 函数的最佳平方逼近函数的最佳平方逼近28问题问题: 给定给定n个数据点个数据点 (xi , yi) (i=1, 2, …, n)求求 (或或 y=a0+a1x ) 使得使得达到最小达到最小. 最小二乘一次最小二乘一次 (二次二次)多项式拟合多项式拟合29  令令利用多元函数取极值的必要条件得到正则方程组利用多元函数取极值的必要条件得到正则方程组由上式求得由上式求得a0, a1, a2, 得到得到最小二乘拟合二次多项式最小二乘拟合二次多项式.30  最小平方线性多项式逼近最小平方线性多项式逼近§3 函数的最佳平方逼近函数的最佳平方逼近 设设 f (x)是区间是区间[a, b]上的连续函数上的连续函数, 求线性多项求线性多项式函数式函数  (x)=a0+a1x 使得使得, (x)称为函数称为函数 f (x)在区间在区间 [a, b] 上的上的一次最佳平方一次最佳平方逼近多项式逼近多项式.即求即求a0, a1使得使得31  二次最佳平方逼近多项式二次最佳平方逼近多项式设设 f (x)是区间是区间[a, b]上的连续函数上的连续函数, 求二次多项式函求二次多项式函数数  (x)=a0+a1x+ a2x2 使得使得,  (x)称为函数称为函数 f (x)在区间在区间 [a, b] 上的上的二次最佳平二次最佳平方逼近多项式方逼近多项式.32第七章第七章 数值微分与数值积分数值微分与数值积分 复化梯形公式复化梯形公式 复化复化Simpson公式公式 Romberg算法算法 Gauss型求积公式型求积公式 代数精确度代数精确度 截断误差截断误差33 代数精确度代数精确度设有求积公式设有求积公式若它对若它对 f (x)=1, x, x2,…, xm 都能精确成立都能精确成立(即上式等即上式等号成立号成立), 但对但对 f (x)=xm+1 上式等号不成立上式等号不成立, 则称该则称该求积公式具有求积公式具有m次代数精确度次代数精确度. 34 复化梯形公式复化梯形公式其中其中  截断误差截断误差35 复化复化Simpson公式公式区间区间[a, b] n等分等分, n=2m其中其中  截断误差截断误差36 梯形值序列梯形值序列  递推算法递推算法所有新增加节点的函数值之和所有新增加节点的函数值之和.其中其中37 Romberg算法算法38 Gauss型求积公式型求积公式Ak: 求积系数求积系数,{xk}: 求积节点求积节点如果该求积公式具有如果该求积公式具有(2n-1)阶代数精确度阶代数精确度, 则称则称其为其为Gauss型求积公式型求积公式.设有求积公式设有求积公式39  区间区间[-1, 1]上的上的Guass型求积公式型求积公式其中求积节点其中求积节点{xk}为为n阶阶Legendre多项式的多项式的零点零点; Ak, xk 的值可查表得到的值可查表得到.  一般一般[a, b]上的上的Gauss型求积公式可用换元法转型求积公式可用换元法转化成化成[-1, 1]上的上的Gauss型求积公式型求积公式.40第八章第八章 非线性方程解法非线性方程解法 二分法二分法(对分区间法对分区间法)求求 f (x) = 0 的根的根 简单迭代法简单迭代法 (收敛的充分条件收敛的充分条件) 牛顿法牛顿法41  设设[a, b]是是 f (x)=0的有根区间的有根区间, 用二分法迭代用二分法迭代  给定精度给定精度 , 迭代次数迭代次数k 满足下式满足下式, 能保证满足精度能保证满足精度 二分法二分法(对分区间法对分区间法)42 简单迭代法简单迭代法构造递推公式构造递推公式适当选取适当选取.以以 逐次逼近逐次逼近 f (x)=0的根的根.如何构造收敛的迭代法如何构造收敛的迭代法?43定理定理考虑方程考虑方程 x = g(x), g(x) C[a, b], 若若( I ) 当当 x [a, b] 时，时， g(x) [a, b]；；( II )   0   L < 1 使得使得 | g’(x) |   L 对对   x [a, b] 成成立。

立则任取则任取 x0 [a, b]，由，由 xk+1 = g(xk) 得到的序列得到的序列 收敛于收敛于g(x) 在在[a, b]上的唯一不动点并且有误差估上的唯一不动点并且有误差估计式：计式：( k = 1, 2, … )k44 牛顿法牛顿法原理：原理：将非线性方程线性化将非线性方程线性化 ( Taylor 展开展开 )xyx*xnxn+145第九章第九章 常微分方程数值解法常微分方程数值解法 构造常微分方程离散格式的三种方法构造常微分方程离散格式的三种方法 单步法常见格式单步法常见格式 多步法常见格式多步法常见格式 重要概念重要概念: 局部截断误差局部截断误差46  用差商近似导数用差商近似导数  数值积分方法数值积分方法  Taylor多项式近似方法多项式近似方法 构造常微分方程离散格式的三种方法构造常微分方程离散格式的三种方法47  Euler法法  改进改进Euler法法  经典四阶经典四阶RK方法方法 单步法常见格式单步法常见格式48 多步法常见格式多步法常见格式  Simpson公式公式  Adams显隐公式显隐公式  Adams预测预测--校正公式校正公式49  局部截断误差局部截断误差  整体截断误差整体截断误差Taylor展开方法展开方法 几个重要概念几个重要概念  数值方法的阶数数值方法的阶数50数值分析总复习例题数值分析总复习例题51分析分析对称对称其中其中 li为矩阵为矩阵 L的第的第 i个行向量个行向量.一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中52解解:一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中53一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中解解: 54解解: 先解先解 Ly=b, 再解再解 LTx=y, 一一. 用平方根法求线性方程组用平方根法求线性方程组AX=b, 其中其中55二二. 设有方程组设有方程组写出写出Jacobi迭代迭代, Gauss-Seidel迭代迭代的计算公式的计算公式, 两两种迭代法是否收敛种迭代法是否收敛? 为什么为什么?Jacobi迭代法不收敛迭代法不收敛,Gauss-Seidel迭代法迭代法.56三三. 按下表求按下表求 f (x)的四次的四次Hermite插值多项式插值多项式H(x), 并写出截断误差并写出截断误差R (x)=f (x) H(x)的表达式的表达式.0121210 157四四. (1) 求形如求形如的求积公式的求积公式, 使其至少具有两次代数精确度使其至少具有两次代数精确度, 该公式是该公式是否具有三次代数精确度否具有三次代数精确度?解解 (1) 由已知由已知, 当当 f (x)分别为分别为1, x, x2时时, 求积公式等号求积公式等号成立成立. 即即故该公式具有故该公式具有3次代数次代数精确度精确度.58四四. (2) 选用合适的数值积分方法计算选用合适的数值积分方法计算的近似值的近似值, 要求计算结果具有要求计算结果具有3位有效数字位有效数字.解解 设设 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梯形值序列的逐次分半算法梯形值序列的逐次分半算法故故59五五. 设设(1) 用迭代公式用迭代公式 求方程求方程 f (x)=0在在x0=2.0附近的一个根附近的一个根, 试问此迭代法是否收敛试问此迭代法是否收敛? (2) 用合适的方法求用合适的方法求 f (x)=0在在x0=2.0附近的根附近的根, 要要求计算结果具有求计算结果具有4位有效数字位有效数字.解解 (1) 迭代函数为迭代函数为验证验证 g(x)在区间在区间[1.7, 2.0]上满足压缩映像定理上满足压缩映像定理, 故该迭代法收敛故该迭代法收敛.(2) 可用可用Newton迭代法求根迭代法求根, 取取x0=2.0, 写出迭代公写出迭代公式后计算三次得式后计算三次得x1=1.857142857, x2=1.839544514, x3=1.839286811. 故故x3即为所求方程近似根即为所求方程近似根.60六六. 确定求解初值问题确定求解初值问题的二步隐式的二步隐式Adams方法方法中的参数中的参数 , 使该方法成为三阶方法使该方法成为三阶方法, 并写出其局部并写出其局部截断误差主项截断误差主项.可用数值积分方法或可用数值积分方法或Taylor展开方法展开方法61七七. 据资料记载据资料记载, 某地某年间间隔某地某年间间隔30天的日出日落天的日出日落时间如下时间如下5月月1日日 5月月31日日6月月30日日4:514:174:1619:3819:50日出日出日落日落19:04日出日落时间表日出日落时间表请问请问: 这一年中哪一天白天最这一年中哪一天白天最"长长"?解解 用用Newton插值公式较为方便插值公式较为方便, 答案为答案为:这一年中以这一年中以6月月22日的白天最日的白天最"长长".62练习练习1. 第第126页页. 求解线性方求解线性方程组程组 Ax=b, 其中其中A如右图如右图所示所示, 试构造一个与求解试构造一个与求解三对角方程组的追赶法三对角方程组的追赶法类似的直接方法类似的直接方法.其中其中632. 确定如下求积公式中的求积系数确定如下求积公式中的求积系数, 使其具有使其具有尽可能高的代数精确度尽可能高的代数精确度提示提示: 用三次用三次Hermite插值多项式来近似函数插值多项式来近似函数 f (x).64 3. 若干年以前若干年以前, 美国原子能委员会准备将浓缩的放射美国原子能委员会准备将浓缩的放射性废料装入密封的圆桶内沉至海底性废料装入密封的圆桶内沉至海底. 但是但是, 当时一些科当时一些科学家与生态学家都反对这种作法学家与生态学家都反对这种作法. 科学家用实验测定科学家用实验测定出圆桶能够承受的最大撞击速度为出圆桶能够承受的最大撞击速度为v=12.2 m/s, 如果圆如果圆桶到达海底时的速度超过这个速度桶到达海底时的速度超过这个速度, 将会因撞击海底将会因撞击海底而破裂而破裂, 从而引起严重的核污染从而引起严重的核污染. 然而原子能委员会却然而原子能委员会却认为不存在这种可能性认为不存在这种可能性. 根据圆桶的质量根据圆桶的质量, 体积以及海体积以及海水的密度与海底的深度水的密度与海底的深度, 通过建立数学模型得知圆桶通过建立数学模型得知圆桶到达海底时的速度到达海底时的速度v (m/s)满足如下方程满足如下方程:那么圆桶到达海底时的速度究竟会不会超过那么圆桶到达海底时的速度究竟会不会超过12.2 m/s呢呢? 试选用合适的方法求此速度试选用合适的方法求此速度, 要求计算结果具有要求计算结果具有5位有效数字位有效数字.654. 1601年德国天文学家开普勒根据已有的行星观年德国天文学家开普勒根据已有的行星观测数据得出了天文学上著名的开普勒第三定律测数据得出了天文学上著名的开普勒第三定律: 其中其中T 为行星绕太阳运行的周期为行星绕太阳运行的周期(单位天单位天), a为行星椭圆轨道的长半轴长为行星椭圆轨道的长半轴长(单位百万公里单位百万公里), C与与g g均是常数均是常数. 试根据以下数据试根据以下数据, 用最小二乘法用最小二乘法确定上式中的常数确定上式中的常数C与与g gPlanet Mercury Venus Earth Marsa (km 106) 57.59 108.11 149.57 227.84 T(days) 87.99 224.70 365.26 686.98665. 伞兵下降的速度满足如下公式伞兵下降的速度满足如下公式:其中，其中， g是重力加速度是重力加速度 ( 10米米/秒秒2), m是伞兵的质是伞兵的质量量, c是拽拉系数是拽拉系数 ( 14千克千克/秒秒). 经实际测量在下经实际测量在下落落7秒时速度为秒时速度为35米米/秒秒, 试计算出伞兵的质量试计算出伞兵的质量(误差误差不大于不大于0.5千克千克).67完毕完毕68。