计算方法复习提纲.docVIP

数值计算方法复习提纲 第一章 数值计算中的误差分析 1．了解误差及其主要来源，误差估计； 2．了解误差(绝对误差、相对误差)和有效数字的概念及其关系； 3．掌握算法及其稳定性，设计算法遵循的原则。 误差的来源 模型误差 观测误差 截断误差 舍入误差 2误差与有效数字 绝对误差 E（x）=x-x 绝对误差限 相对误差 有效数字 若，称有n位有效数字。 有效数字与误差关系 m一定时，有效数字n越多，绝对误差限越小； 有n位有效数字，则相对误差限为。 选择算法应遵循的原则 选用数值稳定的算法，控制误差传播； 例 △△x 简化计算步骤，减少运算次数； 避免两个相近数相减，和接近零的数作分母； 避免 第二章 线性方程组的数值解法 1．了解Gauss消元法、主元消元法基本思想及算法； 2．掌握矩阵的三角分解，并利用三角分解求解方程组； （Doolittle分解；Crout分解；Cholesky分解；追赶法） 3．掌握迭代法的基本思想，Jacobi迭代法与Gauss-Seidel迭代法； 4．掌握向量与矩阵的范数及其性质,迭代法的收敛性及其判定 。 本章主要解决线性方程组求解问题，假设n行n列线性方程组有唯一解，如何得到其解？ 两类方法，第一是直接解法，得到其精确解； 第二是迭代解法，得到其近似解。 Gauss消去法 顺序Ｇauss消去法 记方程组为： 　　　 消元过程： 经ｎ－１步消元，化为上三角方程组 第ｋ步　 若 　　 回代过程： ２、Ｇauss—Ｊｏｒｄａｎ消去法 避免回代，消元时上下同时消元 ３、Ｇ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，则LUX= b， 记UX=Y 则LY= b 若L、U为特殊矩阵，则求解线性方程组变为解两个特殊线性方程组问题。 Doolittle分解 L为下三角矩阵, U为上三角矩阵,不一定能分解,分解也不一定唯一; 设L或U是单位三角矩阵, 若能分解,则可分解唯一. L是单位下三角矩阵,称为Doolittle分解; U是单位上三角矩阵,称为Crout分解； 定理: n阶矩阵A有唯一分解的充要条件为A的前n-1阶主子式都不为0. Doolittle分解算法： 由矩阵乘法： 得到： 算法特点：先计算U的行，再计算L的列，交替进行；存储时可用紧凑格式。 矩阵分解后，解两个三角方程组： LY= b，UX=Y 3、Crout分解 若L为下三角矩阵，U是单位上三角矩阵，则称Crout分解； 算法特点：先计算L的列，再计算U的行，交替进行。 4、正定对称矩阵的平方根法（Cholesky分解） 正定对称矩阵性质与判定： 定义：是n阶对称矩阵，若对任意非零向量，有，则称A为正定对称矩阵； 判定：A为n阶正定对称矩阵充要条件A的各阶顺序主子式大于0。 Cholesky分解 定理：设A为n阶正定对称矩阵，则存在唯一主对角线元素都是正数的下三角阵L，使得. Cholesky分解算法： 追赶法 三对角矩阵的特殊分解 三对角方程组的追赶法： 追的过程 LY=D 赶的过程 UX=Y §2 线性方程组的迭代解法 Jacobi迭代公式 例： 其解为 方程变形得到迭代公式 给初值计算，观察解的变化。 一般地，对线性方程组 若，则可从第i个方程中解出,得到Jacobi迭代公式： 简记为： Gauss--Seidel迭代公式 SOR迭代公式 迭代公式的矩阵表示 §3 迭代公式的收敛性 向量与矩阵的范数与性质 向量范数 定义：向量，对应非负实数，满足三条件： （1）非负性 （2）齐次性 （3）三角不等式 称为向量范数 常见向量范数 1范数 2范数 ∞范数 矩阵范数 定义：方阵，对应非负实数，满足三条件： （1）非负性 （2）齐次性 （3）三角不等式 （4）绝对值不等式 称为矩阵范数； 向量范数与矩阵范数相容性： 4、常见矩阵范数 1范数，列范数 ： ∞范数，行范数 ： 2范