数值分析V4提要.doc

数值分析提要第一章: 绪论 关键词：误差、绝对误差、相对误差、有效数字、稳定性1科学计算的重要性：当今世界，科学与工程计算是高科技，它已经成为衡量一个国家的实力的指标之一；它在科学、工程、社会经济活动中的作用日益重要，成为继理论研究、科学实验之后，三大科学技术研究手段之一，是不可缺少的重要技术；2误差的来源：模型误差、观测误差、截断误差（方法误差）、舍入误差（计算误差）；误差分类：绝对误差、相对误差；强近似、弱近似、误差限、相对误差限；3 精度的定义：有效数字N（精确到第N位）；4 衡量算法的指标：稳定性、计算精度、计算速度；5 四则运算的误差估计；有效数字与相对误差的关系；6 减少误差的一些基本原则：避免大数除小数、避免相近数相减、避免大数与小数的加减、简化运算步骤减少运算次数。一、定理 设的近似值有位有效数字，则其相对误差限，反之，若其相对误差限满足：，则有位有效数字。二、误差限的运算： 三、误差的传播四、稳定 第二章 代数插值关键词：拉氏插值、艾氏插值、样条插值、等距插值、分片插值、线性插值、二次插值1设是区间上的连续函数，已知它在上个互异点，若代数多项式在点处满足则称为函数的插值多项式，为插值节点。 满足上述条件的次数不超过的多项式是存在且惟一的。 常用的代数插值公式有：拉格朗日型 和牛顿型公式 插值余项为 其中。2埃尔米特插值公式为 其中 的表达式同拉格朗日型公式中的基函数。插值余项为 3三次样条插值多项式，详见参考文献1，2，5等。第三章 函数逼近关键词：最佳一致逼近、最佳平方逼近、最小二乘逼近、数据拟合、多项式逼近、权函数、正交多项式、勒让得多项式、切比雪夫多项式1、函数逼近的概念。设中一组线性无关的函数，在某种范数意义下距离最近，即，则称为在函数类意义下的最佳逼近函数。特别当范数为时，分别为最佳平方逼近和最佳一致逼近。 常用的函数类次多项集合。次最佳平方逼近多项式和最佳一致逼近多项式都是存在惟一的。 次最佳平方逼近多项式的系数满足正规方程组 逼近误差，这里内积定义为。 2、正交多项式的引入，可能简化最佳平方逼近多项式的正规方程组的求解。 常用的正交多项式有：切比雪夫多项式、勒让德多项式、拉盖尔多项式以及埃尔米特多项式。 3、对数据进行曲线拟合，常用最小二乘法（最佳平方逼近）。其拟合曲线及误差的表达式同连续函数的情形完全一样。只需把内积理解为 即可。第四章 数值积分和数值微分关键词：求积代数精度、机械积分公式、高斯点积分公式、牛顿-柯特斯求积公式、矩形公式、梯形公式、辛普森公式、复化求积公式、差分、向前差分、向后差分、一阶差分、二阶差分、高阶差分、外推法数值积分是求定积分的近似算法。1、 牛顿-柯特斯求积分式牛顿-柯特斯求积公式是节点等距的插值型求积公式。将等分，其节点为则牛顿-柯特斯求积公式为 其中为柯特斯系数。 时，求积公式为梯形公式： 时，求积公式为辛普森公式： 2、 复化求积公式复化梯形公式：3、求积公式的代数精确度概念一个求积公式的多项式都能精确地成立，但对于次多项式不能精确成立，则称该求积公式具有次代数精确度。形如的求积公式至少具有次代数精确度的充要条件是，该求积公式为插值型的。牛顿-柯特斯公式是插值型公式。4、 高斯型求积公式以为节点作插值多项式所得到的插值型求积公式，可使该求积公式的代数精确度提高到次。这样的节点称为高斯点，相应的求积公式称为高斯型求积公式，其一般表达式为其中系数、节点可查表，余项 常用的高斯型求积公式有：高斯-勒让德求积公式、高斯-切比雪夫求积公式、高斯-拉盖尔求积公式及高斯-埃尔米特求积公式。5、 数值微分数值微分的求法，总的来说有两大类方法：泰勒展开方法和用插值函数求微分方法。第五章 解线性代数方程组的直接法关键词：高斯消去法、LU分解、Cholesky分解、追赶法、范数、向量范数、1范数、2范数、P范数、无穷范数、矩阵范数、列范数、行范数、F范数、谱半径、条件数、误差估计设线性方程组为Ax=b，其中A为n阶非奇异矩阵，x,b为n维列向量。1 高斯消去法、高斯-若当消去法和主元素消去法见参考文献1。2 矩阵三角分解法。高斯消元过程实现了A的一个三角因子分解A=LU，其中L为单位下三角阵，U为上三角阵，此分解称为A的Doolittle分解。A有唯一Doolittle分解的充要条件是A的前n-1个顺序主子式均不为零。 如果A对称正定，则有唯一分解A=，这里为下三角阵,此分解称为平方根分解或Cholesky分解.当A对称正定时也可以进行如下分解A=,其中L为单位下三角阵,D为对角阵.解方程Ax=b等价于解两个三角方程组 这种解方程组的方法称为直接三角分解法.3.三对角方程组的追赶法求解见参考文献1,4.4.向量、 矩阵的范数及方程组的性态.向量与矩阵范数的定义见参考文献1.常用的向量范数是p-范数:, (正整数)当p为1,2,时分别为:1范数: 2范数: -范数 与上述向量范数相容的矩阵范数分别是:1范数: 2范数: -范数 其中为的最大特征值.设| . |a为非奇异矩阵A的某种算子范数,当A的条件数时,方程组Ax=b是”病态”的,此时求解比较困难.条件数越大,则病态越严重,从而越难求解,如果系数矩阵的条件数不是很大,则方程是”良态”的.第六章 解线性代数方程组的迭代法关键词：迭代法、雅可比迭代、高斯塞得尔迭代、（弱、超）松弛（SOR）迭代法、收敛性判别法 设有方程组Ax=b，其中为n阶非奇异阵，x,b为n维列向量。1 简单迭代法将Ax=b等价变形为x=Bx+g，其中B为n阶矩阵，g为n维常向量。任取迭代格式 k=（0，1，2，。）称为简单迭代法，B称为迭代矩阵。特别地，若则有所谓的雅可比迭代法 2 高斯赛德尔迭代法把简单迭代法中的迭代矩阵B=写成B=L+D+U其中D=diag（bii），L和U分别是由B的对角线以下和以上的部分的元素组成的严格下、上三角阵，则高斯赛德尔迭代格式为： 其分量形式为： 3逐次超松弛（SOR）迭代法 逐次超松弛迭代法为： 其中L和U分别是雅可比迭代矩阵的对角线以下和以上元素组成的严格下、上三角阵， 称为松弛因子。4 。迭代法的收敛性判定（1）对任意初始向量和右端项g简单迭代法都收敛的充要条件是（2）若迭代矩阵B满足|B|1=，则简单迭代法和相应的高斯赛德法都收敛。（3）若迭代矩阵B满足|B|=，则简单迭代法和相应的高斯赛德法都收敛。（4）若系数矩阵A对称正定，则求解Ax=b的与Jacobi迭代法对应的高斯赛德法都收敛。（5）若系数矩阵A严格对角占优或 不可约弱对角占优，则求解Ax=b的与Jacobi迭代法对应的高斯赛德法都收敛。（6）逐次超松弛法收敛的必要条件是02。若系数矩阵对称正定，则02也是充分条件。第七章 方程求根关键词：二分法、简单迭代法、不动点原理、（方程组）牛顿迭代法、收敛阶、弦割法、抛物法、加速法、ARTEN加速法一、内容提要本章内容主要讨论非线性方程f（x）=0的数值求解，其他内容未列入本书。 常用的方法有：1 二分法（参阅参考文献1。2）2 简单迭代法将f（x）=0变为另一种等价形式：，选取根x*的近似值则递推关系式k=（0，1，2。），可产生迭代序列xk，这种迭代方法称为简单迭代法。简单迭代法有如下收敛性定理： 设函数在有限的区间a,b上满足（1） ，当； （2）则在a，b上存在唯一的解x*，且对由k=0，1，2。产生的迭代序列xk收敛于x*，并有误差估计式 3 牛顿迭代法 迭代公式为，设f（x）在包含其零点x*的某个闭区间a，b内有二阶连续导数，且则只要取x0充分接近于x*，牛顿迭代法产生的序列xk收敛于x*，且有： 4 弦割法、抛物线法5 迭代收敛阶的概念 设迭代过程收敛于的根x*，如果迭代误差满足下列关系式： （c为常数且不为0）则称该迭代过程是p阶收敛的，p=1，0c1称超线性收敛。 前述的简单迭代法是线性收敛的，牛顿法是平方收敛的，双点弦割法的收敛阶为1.618，抛物线法的收敛阶是1.839。 收敛阶的判别原理：对于迭代过程如果在所求的根x*的邻近连续，且则称该迭代过程在点x*邻近是p 阶收敛的。第八章 矩阵的特征值与特征向量的计算关键词：圆盘定理、幂法、反幂法、原点平移法、瑞利商加速法、雅可比法、QR分解、H变换、HESSENNERG矩阵、正交变换法1 圆盘定理（Gerschgorin定理）矩阵的任何的一个特征值至少位于复平面上的几个圆盘 2、乘幂法与反幂法 乘幂法是求一个实矩阵的按模最大的特征值和对应的特征向量的方法。它是一个迭代法。设为A的特征值，xi为对应的特征向量，并且有： （i=1，2，。，n）线性无关，则对任一非零向量，乘幂法的计算公式为 中绝对值最大的一个分量。迭代结果的各种情况讨论见参考文献1，3。特别当反幂法和两方法的加速法见参考文献1，2。2 实对称阵的雅可比方法 雅可比方法是求一个实对称矩阵的全部特征值与特征向量的方法。起基本思想是通过正交相似变换，把实对称矩阵化为对角阵，该对角阵的对角元就是原对称矩阵的特征值。 记A0=A，施行一系列正交相似变换 其中的选取必须满足4、QR方法、Householder变换、对称三对角阵的二分法等见参考文献1，2。第九章 常微分方程初值问题数值解法关键词：欧拉法、后退欧拉法、梯形法、显式法、隐式法、（2、3、4阶）龙格库塔法、单步法、线性多步法、ADAMS法、预测-校正法、相容性、收敛性、稳定性（判别法）、收敛阶、局部截断误差、全局截断误差、刚性方程本章讨论形如：的初值问题的数值解法，其中f（x,y）是已知连续函数，为给定的初值，假设该初值问题的解存在唯一。（一） 单步法1 欧拉（Euler）法及其改进形式（1） 向前欧拉公式（欧拉折线法或欧拉显格式） 其中h为步长，该方法的局部截断误差阶为O（h2），是一阶方法。（2） 向后欧拉公式（后退欧拉公式） （3） 梯形公式（欧拉公式的改进） 这也是一个隐格式，是二阶方法。实用中常按下述爹带进行求解： 该方法是二阶方法；如果关于k仅迭代一步，并换则称该方法为欧拉预估校正方法。2 显式龙格-库塔方法（Runge-Kutta）方法一般形式为： 其中Ci为待定权因子，满足为所使用的f值的个数，a1=0，ai（i1），bij均是待定参数，随着m取不同的正整数值，便可以得到各阶显式龙格-库塔格式，特别当m=4时，可以得到四阶、经典的龙格-库塔格式： 3 单步法的收敛性与稳定性4 单步法的收敛性与稳定性的概念非常重要，有关定义和结论可见参考2，6，10。（二） 线性多步法1 一般公式 其中 为和