《2020年整理数值计算方法复习提纲.doc》由会员分享,可在线阅读,更多相关《2020年整理数值计算方法复习提纲.doc(20页珍藏版)》请在金锄头文库上搜索。
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=Y2 线性方程组的迭代解法一、 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掌握一般迭代法的基本思想及其收敛性判定 ;3掌握New
8、ton切线法、弦截法,并用它们求方程近似根的方法。本章问题:求方程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切线公式的缺点及改进几何作法迭代公式Newton弦截公式是两步公式。第五章 插值法1. 掌握代数插值问题及其解存在
10、唯一性,Lagrange插值多项式构造及其余项,插值基函数性质;2. 掌握差商的概念及其性质,Newton插值多项式构造,两种插值法之间的区别与联系;3了解差分与等距节点插值多项式公式;4. 掌握Hermite 插值问题及其构造方法。本章问题:函数复杂,或无表达式,构造简单函数来代替。1 Lagrange插值一、代数插值问题及插值多项式存在唯一条件1、代数插值问题:已知在区间a,b中互异的n+1个点的函数值,求次数n次多项式且满足,(i=0,1,n).2、插值多项式存在唯一条件:定理:存在唯一条件是n+1个节点互异。二、Lagrange插值构造1、线形插值(n=1)几何解释;利用插值基函数构造
11、:基函数:一次多项式满足 -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,b,分为n个区间,i=0,1,2n-1每个区间由直线代替曲线,形成分段线性插值函数,二、分段
12、抛物插值3 Newton 插值一、差商及其性质定义:一阶差商:二阶差商:K阶差商:性质:(1)差商可由节点函数值表示;(2)差商值与节点次序无关。二、Newton 插值多项式由差商定义。依次带入- Newton 插值多项式计算时先造差商表;三、余项4 差分与等距节点插值多项式一、差分及其性质:二、等距节点插值多项式5 Hermite 插值一、带导数的插值多项式1、问题:求次数不超过3次多项式;2、利用基函数构造二、一般情形1、问题:求次数不超过2n+1次多项式2、利用基函数构造见教材第七章 数值微积分1. 了解数值求积基本思想;2. 掌握Newton-Cotes公式(梯形公式,Simpson公
13、式,Cotes公式)推导及误差;3. 了解Romberg 求积公式原理;4了解数值微分的方法。本章问题:数值积分问题求定积分 不能使用微积分公式情形存在问题:(1)f(x)表达式复杂,原函数更复杂; (2)f(x)表达式不复杂,但原函数复杂;(3)原函数不存在; (3)f(x)无表达式1 Newton-Cotes公式一、 数值求积基本思想1、 不利用原函数,直接利用函数值积分中值定理:为平均高度;机械求积方法:为求积节点;为求积系数。2、 几个简单求积公式左矩形公式右矩形公式中矩形公式梯形公式二、 Newton-Cotes公式1、公式推导由Lagrange插值多项式代替函数f(x)记则求积系数的计算:-为Cotes系数;- Newton