现代数值分析 第2章线性方程组的直接法.ppt

第二章 解线性方程组的直接方法 列主元消去法 在第k步消元前，在系数矩阵第k列的对角线以下的元素中找出绝对值最大的元。 ? 运算量 （Amount of Computation） （1）用克莱姆（Cramer）法则求解n阶线性方程组 （2） 高斯消去法: 在第1个消去步, 计算 li1(i=2,3,…,n), 有n-1次除法运算. 使aij(1)变为 aij(2) 以及使bi(1)变为bi(2)有n(n-1)次乘法运算 和 n(n-1)次加(减)法运算. 回代过程的计算 除法运算次数为n次. 乘法运算和加法运算的总次数 都为n+(n-1)+…+1= n(n-1)/2次 §2.2 三角分解法 一般计算公式 LU 分解求解线性方程组 ? 求解正定方程组的Cholesky方法(平方根法) 回顾：对称正定阵A的几个重要性质 （1）A?1 亦对称正定，且 aii 0 （2）A 的顺序主子阵 Ak 亦对称正定 （3）A 的特征值 ?i 0 （4）A 的全部顺序主子式 det ( Ak ) 0 定理2.2.2: 设矩阵A对称正定，则存在唯一的对角元全为正的下三角阵G 使得 A＝GGT ? 解三对角方程组的追赶法 定理2.2.3：若 A 为对角占优 的三对角阵，且满足 则方程组有唯一的LU分解。 第一步 : 对 A 作Doolittle 分解 追赶法公式的推导：（以四阶为例） 该过程称为“追”的过程。 该过程称为“赶”的过程。 一般情形的三对角方程组计算公式： 计算次序为： 最 好 牢记 直接比较等式两边的元素，可得到计算公式： 第一步: 对 A 作Crout 分解： 注: 也可通过对 A 作Crout 分解进行求解 * 高斯(Gauss)消元法 矩阵的三角分解法 矩阵的条件数与方程组的性态 解线性方程组的两类方法: 直接法: 经过有限次运算后可求得方程组精确解的方法(不计舍入误差!) 迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法(一般有限步内得不到精确解) 一、高斯消去法 思路 首先将方程组Ax=b 化为上三角方程组，此过程称为消去过程，再求解上三角方程组，此过程称为回代过程. §2.1 高斯消去法和选主元高斯消去法 将增广矩阵的第 i 行 + li1 ? 第1行，得到： 消去过程： 第一步：设 ，计算因子 其中 第k步：设 ，计算因子 且计算 共进行 n ? 1步，得到 定理2.1：若A的所有顺序主子式 均不为0，则高斯消去法能顺序进行消元，得到唯一解。 回代过程： 例2.1.1 高斯消元法 x1 = -13 x2 = 8 x3 = 2 二、选主元消去法 为避免这种情况的发生, 可通过交换方程的次序，选取绝对值大的元素作主元. 基于这种思想导出了主元素法 在高斯消去法消去过程中可能出现 的情况， 这时高斯消去法将无法进行；即使主元素 但很小，其作除数 ，也会导致其它元素数量级的严 重增长和舍入误差的扩散 若p≠k, 交换第k个与第p个方程后, 再继续消去计算. 这种方法称为列主元Gauss消去法。 列主元Gauss消去法保证了｜lik｜≤1 ( i = k +1, k +2,…，n ). 例2.1.2 列主元法 第一列中绝对值最大是10，取10为主元 n阶方程组第k 轮消元时，选第k 列的后( n – k + 1 )个元素中绝对值最大作主元。 x3=6.2/6.2=1 x2=(2.5-5x3)/2.5= -1 x1=(7+7x2-0x3)/10=0 x1=0 x2= -1 x3=1 第二列的后两个数中选出主元 2.5 全主元消去法 在第k 步消去前， 在系数矩阵右下角的n- k+1阶主子阵中，选绝对值最大的元素作为主元素。 (1) If p ? k then 交换第 k 行与第p 行; If q ? k then 交换第 k 列与第 q 列; (2) 消元 注：列交换改变了xi 的顺序，须记录交换次序，解完后再换回来。 例2.1.3 全主元解方程组: 每个行列式由n!项相加, 而每项包含了n个因子相乘,乘法运算次数为(n-1) n!次. 仅考虑乘(除)法运算, 计算解向量包括计算n+1个行列式和n次除法运算, 乘(除)法运算次数 N=(n+1)(n-1)n!+n. 在第k个消去步, 有n-k次除法运算, (n-k+1)(n-k)次乘法运算和相同的加(减)法运算. 首先统计乘法运算总次数. 将每个消去步的乘法运算次数相加,有