第六章 线性方程组的数值解法.ppt

第六章 线性方程组的数值解法 第一节 引言 设线性方程组 第二节 高斯消去法 举例 用消元法解方程组 第一步：-2 x（1）+(3)得 第二步：1 x（2）+（4） 回代得：x=[1,2,3]T 三、高斯消元法的计算量 （1）消元过程乘除法的计算量 ●除法计算量：第k步消元的除法计算量为n-k，其中k=1,2,3,…,n-1 所以：除法计算量为： ●乘法计算量：第k步消元法的计算量为： 该步每行从k＋1个数开始到n＋1个数都需乘一个数（lik）共有：n+1-k次乘法； 该步共有n-k行。 所以乘法计算量为： ●所以高斯消元过程乘除法的计算量为： （2）消元过程加减法的运算量 ●可以从第k步消元计算过程得到： 第k步消元时候，从第k+1行开始到第n行为止；每行的第k+1个数开始到第n+1个数止进行加法运算。 所以该步的加减法次数为：(n-k)×(n+1-k) ●消元过程总的加减法运算次数为： （3）回代过程的计算量 ●乘除法的计算量为： ●加减法的计算量为： （4）高斯消元法总过程的计算量 ●乘除法的计算量为： ●加减法的计算量为： 解： 回代解得 =0.5， =0，显然严重失真。 造成这种结果的原因，就是小主元的出现。用它做除数产生大乘数，出现大数吃小数产生舍入误差，从而 有误差。代回第一个方程 时，因10-6x1+2x2=1， 10-6 +2 =1 该两个式相减得到： 例求解方程组 （1）用顺序高斯消去法 （2）用列主元消去法 第三节 向量范数和矩阵范数 向量范数和矩阵范数是研究迭代法及其收敛性、估计方程组近似解的误差的一种有力工具，本节简要介绍其相关概念。 一、向量范数 1、向量范数的定义 （1）绝对值 范数的最简单的例子，是绝对值函数： 并且有三个熟知的性质： ①x ? 0 ? ? x ? 0 ? x ? = 0当且仅当x = 0 ② ?ax? = ? a ? ? ? x ? a为常数 ③ ? x+ y ?≤ ? x ? + ? y ? （2）范数的另一个简单例子是二维欧氏空间的长度 欧氏范数也满足三个条件： 设x = (x1, x2) ① x ? 0 ? ?? x ?? 0 ② ?? ax ?? = ? a ? ? ?? x ?? a为常数 ③ ?? x+ y ??≤ ?? x ?? + ?? y ?? 前两个条件显然，第三个条件在几何上解释为三角形一边的长度不大于其它两边长度之和。因此，称之三角不等式。 （3）下面我们给出n维空间中向量范数的概念： 设X = (x1, x2, …, xn)T，记为X ? R n 定义1：设X ? R n，??Ｘ?? 表示定义在Rn上的一个实值函数，称之为X的范数，它具有下列性质： ①非负性：即对一切X ? R n，X ? 0, ??Ｘ?? 0 ②齐次性：即为任何实数a ? R，X ? R n， ③三角不等式：即对任意两个向量X、Y? R n，恒有 2、常用的范数 设X = (x1, x2,…, xn)T，则有： （1）向量的1范数 （2）向量的2范数 （3）向量的无穷范数 不难验证，上述三种范数都满足定义的条件。 3、举例 例1：求向量范数 解： 例2：P128 设下x=[1 2 3]T，求x的1范数，2范数和无穷范数 解：根据定义可以得到： 二、矩阵范数 1、定义 对于任意n阶方阵A，按一定的规则由一实数与之对应，记为 ，若 满足： ① ② ③ 则称 为矩阵A的范数。 2、矩阵范数与向量范数的相容性 对于任意的n维向量x，都有： 这一性质称为矩阵范数与向量范数的相容性。 3、常用的矩阵范数 （1）矩阵的1范数 （2）矩阵的无穷范数 （3）矩阵的2范数 矩阵的谱半径： 矩阵B的诸特征值为： 则特征值的最大绝对值称为B的谱半径，记为： 则： 矩阵的2范数其实为ATA的谱半径的1/2次方。 4、矩阵的收敛性 5、举例 例1：求矩阵A的 各常用范数 解： 先求ATA的特征值： 特征方程为： 解之可得ATA特征值： 可得： 所以： 对各个常用范数比较： 第四节 解线性方程组的迭代法 　　迭代法也是解线性代数方程组的一类重要方法。这类方 法主要适用于大型稀疏线性方程组的求解。其基本思想是通 过构造迭代格式产生迭代序列，由迭代序列来逼近原方程组 的解。 　　因此，要解决的基本问题是：