Chapter2_1_线性方程组的直接法.ppt

1、第二章第二章 求解线性方程组的数值解法求解线性方程组的数值解法 (Numerical Solution of Linear Equations)直接法直接法:经过有限步运算后可求得方程组精确解的方法(不计舍入误差!)（2.12.1节）节）迭代法迭代法：从解的某个近似值出发，通过构造一个无穷序列去逼近精确解的方法。分为两类：逐次逼近法(一般有限步内得不到精确解)（2.22.2节）节）共轭斜量法（不考虑计算过程的舍入误差，只用有限步就收敛于方程组的精确解）（2.32.3节）节）解线性方程组的两类方法2.1 解线性方程组的直接法解线性方程组的直接法(Direct Method for Solving

2、 Linear Systems)高斯消去法高斯消去法 (Gaussian Elimination)思思路路首先将首先将A化为上三角阵化为上三角阵 (upper-triangular matrix)，此过程称为此过程称为消去过程消去过程，再求解如，再求解如下形状的方程组，此过程称为下形状的方程组，此过程称为回代求解回代求解 (backward substitution)。=2.1.1求解求解的高斯消去法和选主元高斯消去法的高斯消去法和选主元高斯消去法将增广矩阵将增广矩阵的的第第 i 行行 +li1 第第1 1行行，得到：，得到：消去过程：消去过程：第一步第一步：设设 ，计算因子，计算因子其中其中

3、第第k步：步：设设 ，计算因子，计算因子将增广矩阵将增广矩阵的的第第 i 行行 +lik 第第k k行行，得到：，得到：其中其中定理：定理：若若A的所有的所有顺序主子式顺序主子式 均不为均不为0，则高斯消，则高斯消去法能顺序进行消元，得到唯一解。去法能顺序进行消元，得到唯一解。回代过程：回代过程：共进行共进行 n 1步，得到步，得到 运算量运算量（Amount of Computation）（1 1）用克莱姆用克莱姆（CramerCramer）法则求解法则求解n n阶线性方程组阶线性方程组 每个行列式由每个行列式由n!n!项相加，而每项包含了项相加，而每项包含了n n个因子个因子相乘，乘法运算

4、次数为相乘，乘法运算次数为(n-1)n!n-1)n!次次.仅考虑乘仅考虑乘(除除)法运算法运算,计算解向量包括计算计算解向量包括计算n+1n+1个行列式和个行列式和n n次除法运算次除法运算,乘乘(除除)法运算次数法运算次数N=(n+1)(n-1)n!+n.当当n=8时时,N200，0000（2）高斯消去法高斯消去法:第第1 1个消去步个消去步，计算计算l li1i1(i=2,3(i=2,3，n)n)，有有n-1n-1次次除法运算除法运算.使使a aijij(1)(1)变为变为 a aijij(2)(2)以及使以及使b bi i(1)(1)变为变为b bi i(2)(2)有有n(n-1)n(n

5、-1)次乘法运算次乘法运算.第第k k个消去步个消去步，有，有n-kn-k次除法运算、次除法运算、(n-k+1)(n-k)n-k+1)(n-k)次次乘法运算乘法运算.乘法运算总次数为：乘法运算总次数为：除法运算总次数为除法运算总次数为:(n-1)+1=n(n-1)/2(n-1)+1=n(n-1)/2回代过程的计算回代过程的计算除法运算次数为除法运算次数为n次次.乘法运算的总次数为乘法运算的总次数为 n+(n-1)+1=n(n-1)/2次次 Gauss Gauss消去法消去法 除法运算次数为除法运算次数为:n(n-1)/2+n=n(n+1)/2n(n-1)/2+n=n(n+1)/2，乘法运算次数

6、为乘法运算次数为:n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6 n(n-1)(n+1)/3+n(n-1)/2=n(n-1)(2n+5)/6，通常也说通常也说GaussGauss消去法的运算次数与消去法的运算次数与n n3 3同阶，记为同阶，记为O(nO(n3 3)二、二、选主元消去法选主元消去法在高斯消去法消去过程中可能出现 的情况，这时高斯消去法将无法进行；即使主元素 但很小，其作除数，也会导致其它元素数量级的严重增长和舍入误差的扩散例：例：单精度解方程组单精度解方程组/*精确解为精确解为 和和 */8个个8个个用用Gauss消去法计算：消去法计算：8个个小主元

7、小主元/*Small pivot element*/可能导致计可能导致计算失败。算失败。v列主元消去法列主元消去法在第在第k k 步消元前，在系数矩阵第步消元前，在系数矩阵第k k 列的对角线以列的对角线以下的元素中找出绝对值最大的元。下的元素中找出绝对值最大的元。若若pkpk，交换第交换第k k个与第个与第p p个方程后，再继续消去计算个方程后，再继续消去计算.这种方法称为这种方法称为列主元列主元GaussGauss消去法消去法。列主元列主元GaussGauss消去法保证了消去法保证了l likik1 1(i=k+1,k+2,(i=k+1,k+2,，n).n).为避免这种情况的发生,可通过交

8、换方程的次序，选取绝对值大的元素作主元.基于这种思想导出了“选主元消去法选主元消去法”v 全主元消去法全主元消去法在第在第k k步消去前，步消去前，在系数矩阵右下角的在系数矩阵右下角的n-k+1n-k+1阶主子阵中，阶主子阵中，选绝对值最大的元素作为主元素选绝对值最大的元素作为主元素。(1)If p k then 交换第交换第 k 行与第行与第p行行;If q k then 交换第交换第 k 列与第列与第 q 列列;(2)消元消元注注注注：列交换改变了列交换改变了 x xi i 的顺序，须记录的顺序，须记录交换次序交换次序，解完后再换回来。解完后再换回来。2.1.22.1.2 三角分解法三角分

9、解法 高斯消元法的矩阵形式高斯消元法的矩阵形式 每一步消去过程相当于左乘初等变换矩阵LkA 的的 LU 分解分解(LU factorization)定理定理2.1.1：如果：如果Gauss消去法能顺消去法能顺序进行消去，则序进行消去，则矩阵矩阵A可进行三角分解，即可进行三角分解，即ALU注注注注：（1 1）L 为单位下三角阵而为单位下三角阵而 U 为为一般一般上三角阵的分上三角阵的分解称为解称为Doolittle 分解分解 （2）L 为一般下三角阵而为一般下三角阵而 U 为为单位单位上三角阵的分上三角阵的分解称为解称为Crout 分解分解。Doolittle分解法分解法 ：通过比较法直接导出通

10、过比较法直接导出L 和和 U 的计算公式。的计算公式。思思路路一般计算公式LU 分解求解线性方程组2.1.3 有关定理有关定理定理定理2.1.2：Gauss消去法能顺消去法能顺序进行消去的充要条序进行消去的充要条件是矩阵件是矩阵A的所有的所有顺序主子阵顺序主子阵Ai 非奇异。非奇异。证明参看课本证明参看课本定理定理2.1.4：若若A的所有顺序主子式的所有顺序主子式 均不为均不为0，则，则 A 的的 LU 分解唯一（其中分解唯一（其中 L 为为单位单位下三角阵）。下三角阵）。证明：由证明：由定理定理2.1.12.1.1和定理和定理2.1.22.1.2可知，可知，LU 分解存在。分解存在。下面证明

11、唯一性。下面证明唯一性。若不唯一，则可设若不唯一，则可设 A=L1U1=L2U2，推出推出上三角矩阵上三角矩阵对角线上为对角线上为1 1的的下三角矩阵下三角矩阵2.1.4 2.1.4 求解正定方程组的Cholesky方法回顾：回顾：对称正定阵对称正定阵A的几个重要性质的几个重要性质（1）A 1 亦对称正定，且亦对称正定，且 aii 0（2）A 的顺序主子阵的顺序主子阵 Ak 亦对称正定亦对称正定（3）A 的特征值的特征值 i 0（4）A 的全部顺序主子式的全部顺序主子式 det(Ak)0定理定理2.1.6 设矩阵设矩阵A对称正定，则存在唯一的对角元对称正定，则存在唯一的对角元全为正的下三角阵全为正的下三角阵G 使得使得 AGGT计算格式为计算格式为2.1.5 2.1.5 求解三对角方程组的追赶法求解三对角方程组的追赶法定理：定理：若若 A 为为对角占优对角占优 的三对角阵，且满足的三对角阵，且满足 则方程组有唯一的则方程组有唯一的LU分解。分解。直接比较等式两边的元素，可得到计算公式直接比较等式两边的元素，可得到计算公式（p.66）第二步第二步:追追即解即解 ：第三步第三步:赶赶即解即解 ：第一步第一步:对对 A 作作Crout 分解分解