计算方法总结.doc

第0章 绪论一、三大空间的概念：距离空间，赋范线性空间，内积空间。二、掌握定义距离，范数，内积的几条公理并会验证；常用距离空间、赋范线性空间及内积空间的例子。三、会用范数定义内积，用内积定义范数。四、了解内积空间的正交概念及正交投影定理。五、了解完备的内积空间Hilbert空间中的正交系及规范正交系的概念。l 距离空间举例：中距离： ； n维实向量空间中的距离：，等；中距离。l 赋范线性空间：设E是线性空间，又在E上定义了范数，则称E为赋范线性空间，记作。l 距离与范数的关系：在赋范线性空间中，由范数可以导出距离：，因此赋范线性空间由范数导出的距离也构成了距离空间；反之满足一定条件可以。如，中范数，由此定义的距离： 中范数，定义距离l 矩阵的算子范数 给出一种向量范数 ，相应定义一个矩阵非负函数，称为矩阵的算子范数。常用矩阵的算子范数（1）行范数；（2）列范数；（3）2-范数。谱半径：设的特征值为，称为A的谱半径.谱半径的性质：设，则；为对称矩阵，则.l 内积空间的例子：中；中内积可诱导范数 举例：书上P27，20题 （2）设，问按定义是内积吗？为什么？答：按定义构成内积验证：（1）正定性 ， 而（2）共轭性 由于而， 所以 . （3）第一变元线性性质 综上，按定义构成内积第1章 插值法一、插值法的基本概念。二、会用待定系数法、Lagrange插值法构造插值多项式l 已知函数在区间上n+1个互异的插值节点处的函数值，则次Lagrange插值多项式为 （1.2.5） 其中为插值节点处的次Lagrange插值基函数, 且满足：。 例1.2.2 已知的一组数据见下表，用二次插值多项式计算的近似值，并估计误差。 xi1 2 3yi0.3679 0.1353 0.0183解：记，则。由插值公式得 。误差函数 故 。第2章 最佳逼近和最小二乘法一、内积空间的最佳逼近思想、度量标准（利用范数）及求解方法。二、掌握中的最佳平方逼近的构造方法。三、能写出勒让德多项式和切比雪夫多项式，及正交性等。四、离散数据的最小二乘逼近方法。n 中的最佳平方逼近：设在空间中定义内积和范数， 若是中的个线性无关函数，线性子空间。对于，存在，使得 （2.2.1）称是在空间中关于权函数的最佳平方逼近函数。且满足法方程 l 均方误差 例2.2.1 求区间上函数在中的最佳平方逼近多项式及均方误差。解: 记，计算得 ， ， ， 。 解法方程为 解得。的最佳平方逼近为。 均方误差 。n 勒让德（Legendre）多项式 区间上定义的多项式序列 （2.3.1）性质 ，递推关系： 由递推公式可依次得到次Legendre多项式的简单表达形式：， ， 例2.3.1 求上函数的三次最佳平方逼近多项式。解 由于是区间上的连续函数，故取Legendre正交多项式作为基函数，。因为 又 ， ，。则 。的三次最佳平方逼近多项式为。n 切比雪夫（Tchebichef）多项式 在区间上，取权函数，则由线性无关的多项式序列，通过Gram-Schmidt正交化得到的序列，称为切比雪夫（Tchebichef）多项式，它可以表示为。性质：正交性 （2.3.2） 递推关系 ； 例2.3.3 确定参数，使得取得最小值，并计算最小值。解 问题等价于求在上关于权函数的二次最佳平方逼近多项式。故选取切比雪夫基函数。 的二次最佳平方逼近多项式为由此得到参数。而最小值即是平方均方误差 第3章 数值积分与数值微分一、插值型求积分的基本思想，代数精度的概念及判断。二、Lagrange插值多项式的构造方法；等距节点的牛顿-柯特斯公式及余项估计（梯形求积公式，辛普森求积公式）。三、会用复化梯形法，复化辛普森求法及龙贝格方法求解定积分的近似值并能估计误差。四、Gauss型求积思想及代数精度，会确定Gauss点。五、了解数值微分的思想及在节点处的数值微分计算。n 数值积分法 （3.1.1）又称为机械求积法。称为求积余项或误差。n 插值型求积公式是的Lagrange插值多项式，余项若，得求积公式 （3.1.3）其中。该公式称为插值型求积公式。积分余项 n 求积公式的代数精度的定义及验证例3.1.1 试确定求积公式中的待定参数，使其代数精度尽量高，并指出所构造出的求积公式的代数精度。解 将分别代入公式使其准确成立，则有 解得，故求积公式 验证知：代入准确成立，代入不准确成立。因而该公式具有3次代数精度。n 节点均匀分布的牛顿柯特斯（NewtonCotes）公式设是有限区间, 个等间距节点，其中，步长，则Lagrange插值基函数为求积分系数为 其中 称为NC系数从而求积公式 - NC公式l n=1时，梯形公式： 余项：, (3.2.5)具有1阶代数精度。l n=2时, 辛普森（Simpson）公式 余项：，. 具有3阶代数精度。n 复合梯形公式：将分成n个区间，步长, 节点，则 其中： （3.3.1）称为复合梯形公式 余项 n 复合simpson公式 设. 将2n+1个节点分成n个小区间：, 则 （3.3.2）称为复合simpson公式 余项 。例3.3.1 应用复合梯形公式计算积分，要求误差不超过，试确定所需的步长和节点个数. 解 令，则 ，可知在上为单调函数，因此 由于复化梯形公式的误差为：，因此 。要，只要 ，即，因此. 故取步长. 又，得，取节点数为1001.例3.3.2 对函数，给出的函数表(见表3-3-1)，试用复化梯形公式(3.3.1)及复化辛普森公式(3.3.2)计算积分，并估计误差.解 将积分区间划分为8等分，应用复化梯形法， 表 3-3-1011/80.99739781/40.98961583/80.97672671/20.95885105/80.93615563/40.90885167/80.877192510.8414709求得 ；而如果将分为4等分，应用复化辛普森法求得 .为了利用余项公式估计误差，要求出的高阶导数，由于所以有 于是 .故复化梯形公式误差； 而复化辛普森公式误差； n 龙贝格算法基本思想：在逐次半分梯形序列的基础上，利用序列的某种线性组合构造一个新的序列，使其精度更高，收敛速度更快，这种方法又称为加速法。所用公式如下：将积分区间逐次半分为个区间（是半分次数）的梯形法有如下递推公式： （3.4.2）由此得到一个梯形值序列，可以作为积分的近似值。第一次加速公式：，得到Simpson序列第二次加速公式： ，得到Cotes序列第三次加速公式： ，得到龙贝格(Romberg)序列Romberg算法计算过程中的数值如下： 例3.4.1 用Romberg算法计算积分. 解 令，计算，利用上述各公式计算得Romberg的计算结果见下表(代表二分次数)：k00.920735510.93979330.946145920.94451530.94608690.946083030.94569090.94608330.94608310.9460831n 高斯求积公式定义 若在区间中适当选取求积节点，使得插值型求积公式（3.5.1）具有次代数精度，则称该求积公式为Gauss型求积公式，相应的节点为Gauss点。l 定理3.5.1给出了求高斯点的一种方法；也可以通过勒让德多项式求出权为1的高斯点。第4章 线性方程组的数值解法一、 了解方程组的数值解法分两类: 直接法和迭代法二、 了解线性方程组受扰动影响的性态（病态/良态），条件数的作用及计算。三、 会用高斯消元法、选主元的法解方程组。四、 知道矩阵能够进行直接三角分解的条件；掌握用法，法，法以及追赶法求解相应的线性方程组。五、 了解迭代法的思想；掌握求解方程组的Jacobi和Gauss-seidel迭代法，及收敛性的判别方法；了解SOR迭代法及判别定理。 n 条件数: 设A为非奇异矩阵, 称为矩阵A的条件数. 记作, 即。常用的条件数：；n 矩阵的三角分解的存在唯一性：若阶矩阵的各阶顺序主子式(), 则可唯一分解为一个单位下三角矩阵和一个上三角矩阵的乘积，即，称为矩阵的三角分解或分解n Doolittle（杜利特尔）直接分解法： 矩阵L U分解的紧凑格式 Wang wei-wei, Xidian University Page 28 of 35 2/10/2020 2:33:46 下午 例4.3.1 已知线性方程组 写出系数矩阵的紧凑格式，并由LU分解方法解方程组解 由于 存放L、U的紧凑格式 解方程，得，解方程 ，得。n 对称矩阵的三角分解：设为阶对称矩阵, 且的所有顺序主子式均不为零, 则可唯一分解为，其中为单位下三角矩阵, 为对角阵.n 对称正定矩阵Cholesky分解 若为阶对称正定矩阵, 则存在惟一的主对角线元素都是正数的下三角矩阵, 使得。因而求解方程组求解下列两个三角形线性方程组, 又称此方法为平方根法。例4.3.2 用平方根法求解下面对称正定方程组 。解： 分解，解方程组得， 解方程组得n 改进的平方根法：求解方程组等价于解。n 三对角矩阵的分解 设为阶三对角阵, 且的元素满足: 1. 2. , 3. 则可唯一分解为一个单位下二对角阵和一个上二对角阵的乘积n 雅可比（Jacobi）迭代法，高斯赛德尔（Gauss-seidel）迭代法n 迭代法的收敛条件 考虑一般迭代法l 迭代收敛的充分非必要条件：若, 则迭代法对任意初始向量和都收敛于方程组的解。l 迭代收敛的充分必要条件：一般的迭代法对任意的初始向量及都收敛的充要条件是例4.4.2 设有线性方程组 =。试讨论用雅可比迭代法和高斯赛德尔迭代法解此线性方程组的收敛性.解（1）雅可比迭代法的迭代矩阵为因为,所以,故雅可比迭代法收敛.（2）高斯赛德尔迭代法的迭代矩阵为因为,所以, ,从而, 故高斯赛德尔迭代法不收敛.n 对角占优阵 若的元素满足，即矩阵A的每一行对角元素的绝对值都严格大于非对角元素绝对值之和, 则称A为行严格对角占优矩阵.l 定理4.4.3 如果为按行严格对角占优矩阵, 则A为非奇异矩阵.l 特例1（定理 4.4.4）若线性方程组的系数矩阵A为按行严格对角占优矩阵, 解此方程的J迭代法和GS迭代法都收敛.l 特例2（定理4.4.5）若线性方程组的系数矩阵A为对称正定矩阵, 则解此线性方程组的高斯赛德尔迭代法收敛.l 超松弛迭代公式： （4.5.4）时, 即高斯-赛德尔法；时, 称为低松弛法；时,称为超松弛法.n 超松弛迭代法的收敛性l SOR法收敛的充分必要条件：；SOR法收敛的充分条件: 定理4.5.1设则SOR法收敛的必要条件是。l 特例（定理4.5.2）若线性方程组的系数矩阵为对