数值计算方法复习提纲

1、数值计算方法复习提纲第一章 数值计算中的误差分析1了解误差及其主要来源，误差估计；2了解误差(绝对误差、相对误差)和有效数字的概念及其关系；3掌握算法及其稳定性，设计算法遵循的原则。1、 误差的来源模型误差观测误差截断误差舍入误差2误差与有效数字绝对误差 E（x）=x-x 绝对误差限 相对误差 有效数字若，称有n位有效数字。有效数字与误差关系（1） m一定时，有效数字n越多，绝对误差限越小；（2） 有n位有效数字，则相对误差限为。选择算法应遵循的原则1、 选用数值稳定的算法，控制误差传播；例 x2、 简化计算步骤，减少运算次数；3、 避免两个相近数相减，和接近零的数作分母；避免第二章 线性方程

2、组的数值解法1了解Gauss消元法、主元消元法基本思想及算法；2掌握矩阵的三角分解，并利用三角分解求解方程组；（Doolittle分解；Crout分解；Cholesky分解；追赶法） 3掌握迭代法的基本思想，Jacobi迭代法与Gauss-Seidel迭代法；4掌握向量与矩阵的范数及其性质,迭代法的收敛性及其判定 。本章主要解决线性方程组求解问题，假设n行n列线性方程组有唯一解，如何得到其解？ 两类方法，第一是直接解法，得到其精确解；第二是迭代解法，得到其近似解。一、 Gauss消去法1、 顺序auss消去法记方程组为：消元过程：经步消元，化为上三角方程组第步若回代过程：、auss消去法避免回

3、代，消元时上下同时消元、auss列主元消去法例 ：说明直接消元，出现错误由顺序auss消去法，得；auss列主元消去法原理：每步消元前，选列主元，交换方程。算法：将方程组用增广矩阵表示。（1）消元过程：对k=1,2,n-1,选主元，找 如果，则矩阵A奇异，程序结束；否则执行3。如果，则交换第k行与第行对应的元素位置， 消元，对i=k+1, ,n,计算 对j=L+1, ,n+1,计算 （2）回代过程：1若则矩阵A奇异，程序结束；否则执行。2 举例说明。4、消元法应用（1）行列式计算；（2）矩阵求逆。二、利用矩阵三角分解求解线性方程组1、求解原理线性方程组写成矩阵形式为：AX=b若A=LU，则LU

4、X= b，记UX=Y则LY= b若L、U为特殊矩阵，则求解线性方程组变为解两个特殊线性方程组问题。2、 Doolittle分解L为下三角矩阵, U为上三角矩阵,不一定能分解,分解也不一定唯一;设L或U是单位三角矩阵, 若能分解,则可分解唯一.L是单位下三角矩阵,称为Doolittle分解; U是单位上三角矩阵,称为Crout分解；定理: n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0.Doolittle分解算法：由矩阵乘法：得到：算法特点：先计算U的行，再计算L的列，交替进行；存储时可用紧凑格式。矩阵分解后，解两个三角方程组：LY= b，UX=Y3、Crout分解若L为下三角矩阵

5、，U是单位上三角矩阵，则称Crout分解；算法特点：先计算L的列，再计算U的行，交替进行。4、正定对称矩阵的平方根法（Cholesky分解）（1） 正定对称矩阵性质与判定：定义：是n阶对称矩阵，若对任意非零向量，有，则称A为正定对称矩阵； 判定：A为n阶正定对称矩阵充要条件A的各阶顺序主子式大于0。（2） Cholesky分解定理：设A为n阶正定对称矩阵，则存在唯一主对角线元素都是正数的下三角阵L，使得.Cholesky分解算法：5、 追赶法 三对角矩阵的特殊分解三对角方程组的追赶法：追的过程LY=D赶的过程UX=Y§2 线性方程组的迭代解法一、 Jacobi迭代公式例： 其解为 方

6、程变形得到迭代公式 给初值计算，观察解的变化。一般地，对线性方程组若，则可从第i个方程中解出,得到Jacobi迭代公式：简记为：二、 Gauss-Seidel迭代公式三、 SOR迭代公式四、 迭代公式的矩阵表示 §3 迭代公式的收敛性一、 向量与矩阵的范数与性质1、 向量范数定义：向量，对应非负实数，满足三条件：（1）非负性 （2）齐次性 （3）三角不等式 称为向量范数2、 常见向量范数1范数 2范数 范数 3、 矩阵范数定义：方阵，对应非负实数，满足三条件：（1）非负性 （2）齐次性 （3）三角不等式 （4）绝对值不等式 称为矩阵范数；向量范数与矩阵范数相容性：4、常见矩阵范数1范

7、数，列范数 ： 范数，行范数 ： 2范数，谱范数 ：F范数：举例计算二、 迭代公式收敛性的判定1、 向量的极限2、 矩阵的谱半径： 为特征值；3、收敛性的判定收敛的充要条件：迭代公式收敛的充要条件为谱半径。判定定理1：若则迭代公式收敛。判定定理2：若对方程AX=b的系数矩阵A为对角占优，则Jacobi迭代公式，Gauss-Seidel迭代公式收敛；判定定理3：若对方程AX=b的系数矩阵A为对称正定，则Gauss-Seidel迭代公式收敛；Jacobi迭代公式收敛与Gauss-Seidel迭代公式收敛关系举例：第三章 非线性方程的数值解法1了解二分法的原理与算法；2掌握一般迭代法的基本思想及其收

8、敛性判定 ；3掌握Newton切线法、弦截法，并用它们求方程近似根的方法。本章问题：求方程f(x)=0的根§1 二分法一、 根的存在性定理：函数f(x)在区间a，b连续，且f(a).f(b)<0,则方程f(x)=0在区间a，b有根。方程的根存在，不一定唯一，若在区间a，b上有唯一根，称区间a，b为根隔离区间。二、 二分法（区间逐次分半法）原理：通过计算根隔离区间中点，将区间分半，缩小区间，得到方程近似根数列。 取 §2 迭代法一、 迭代原理迭代法是一种逐次逼近法，由提供的递推公式计算，逐次精确，直到满足精度要求。方程f(x)=0变形为，得到递推公式-简单迭代公式称为迭

9、代函数给初值计算，得到数列，若，则称迭代收敛，否则发散。例：求方程写出两个简单迭代公式：（1） （2）观察计算得到数列的收敛性。迭代法的几何解释：二、 迭代收敛性判定收敛性定理：设方程的迭代函数在a，b满足：（1）当时，；（2）在a，b可导，且，则（1）方程在a，b有唯一根； （2）迭代公式收敛，即；（3）误差估计。说明可根据迭代函数的导数判断迭代收敛性。三、 迭代公式的加速§3 Newton 迭代法一、Newton切线公式几何作法迭代公式例：利用解二次方程推导近似计算的公式。由Newton切线公式 三、 Newton弦截公式Newton切线公式的缺点及改进几何作法迭代公式Newto

10、n弦截公式是两步公式。第五章 插值法1. 掌握代数插值问题及其解存在唯一性，Lagrange插值多项式构造及其余项，插值基函数性质；2. 掌握差商的概念及其性质，Newton插值多项式构造，两种插值法之间的区别与联系；3了解差分与等距节点插值多项式公式；4. 掌握Hermite 插值问题及其构造方法。本章问题：函数复杂，或无表达式，构造简单函数来代替。§1 Lagrange插值一、代数插值问题及插值多项式存在唯一条件1、代数插值问题：已知在区间a,b中互异的n+1个点的函数值，求次数n次多项式且满足，（i=0,1,n）.2、插值多项式存在唯一条件：定理：存在唯一条件是n+1个节点互异

11、。二、Lagrange插值构造1、线形插值（n=1）几何解释；利用插值基函数构造：基函数：一次多项式满足 -1次Lagrange插值多项式例1：求过点（4，2），（9，3）的1次Lagrange插值多项式，并计算近似值。2、抛物插值（n=2）几何解释；利用插值基函数构造：基函数：二次多项式满足 -2次Lagrange插值多项式例2：求过点（1，1），（4，2），（9，3）的2次Lagrange插值多项式，并计算近似值。3、一般情形：利用插值基函数构造：基函数：n次多项式满足 -n次Lagrange插值多项式三、插值余项定理：若则插值误差，其中。§2 分段插值一、分段线性插值在区间a，

12、b，分为n个区间,i=0,1,2n-1每个区间由直线代替曲线，形成分段线性插值函数，二、分段抛物插值§3 Newton 插值一、差商及其性质定义：一阶差商：二阶差商：K阶差商：性质：（1）差商可由节点函数值表示；（2）差商值与节点次序无关。二、Newton 插值多项式由差商定义。依次带入- Newton 插值多项式计算时先造差商表；三、余项§4 差分与等距节点插值多项式一、差分及其性质：二、等距节点插值多项式§5 Hermite 插值一、带导数的插值多项式1、问题：求次数不超过3次多项式；2、利用基函数构造二、一般情形1、问题：求次数不超过2n+1次多项式2、利用

13、基函数构造见教材第七章 数值微积分1. 了解数值求积基本思想；2. 掌握Newton-Cotes公式（梯形公式，Simpson公式，Cotes公式）推导及误差；3. 了解Romberg 求积公式原理；4了解数值微分的方法。本章问题：数值积分问题求定积分 不能使用微积分公式情形存在问题：（1）f(x)表达式复杂，原函数更复杂； （2）f(x)表达式不复杂，但原函数复杂；（3）原函数不存在； （3）f(x)无表达式§1 Newton-Cotes公式一、 数值求积基本思想1、 不利用原函数，直接利用函数值积分中值定理：为平均高度；机械求积方法：为求积节点；为求积系数。2、 几个简单求积公式

14、左矩形公式右矩形公式中矩形公式梯形公式二、 Newton-Cotes公式1、公式推导由Lagrange插值多项式代替函数f(x)记则求积系数的计算：-为Cotes系数；- Newton-Cotes求积公式2、Cotes系数性质对称性：权性：3、常用公式n=1梯形公式：n=2Simpson,抛物公式：n=4Cotes公式： 4误差估计：见教材 举例说明。 §2 Romberg 求积公式一、复化梯形公式将积分区间a,b， n等份，步长误差估计：二、梯形公式递推化三、Romberg 求积公式由梯形公式修正，提高精度§3 Gauss型求积公式一、代数精确度定义：若求积公式对任意m次

15、代数多项式精确成立，而对m+1次代数多项式不精确成立，称求积公式具有m次代数精确度。判定：求积公式具有m次代数精确度求积公式对精确成立；而对 不精确成立。例：梯形公式具有1次代数精确度；定理1：n+1个节点的插值型求积公式代数精确度至少为n；定理2；Newton-Cotes公式代数精确度至少为n；当n为偶数时，可达n+1次代数精确度。二、Gauss型求积公式定义：若n+1个节点求积公式具有2n+1次代数精确度，则称为Gauss型求积公式，节点为Gauss点。Gauss点的特性：见教材第八章 常微分方程数值解1. 掌握 Euler方法（Euler公式，梯形公式，Euler预估-校正公式），局部截断误差，公式的阶；2. 了解 Runge-Kutta 方法的基本思想及四阶经典Runge-Kutta 公式；3. 掌握线性多步方法的原理与公式推导。本章问题：一阶常微分方程初值问题 解的存在性定理：解析解的概念数值解的概念§1 Euler方法一、 Euler公式导数离散化由向前差商代替导数得记为 - Euler显式公式由向后差商代替导数得记为 - Euler隐式公式由中心差商代替导数得记为 - Euler两步公式二、 Euler预估-校正公式梯形公式预估：校正：三、 误差估计1 局部截断误差2 公