求解线方程组的数值解法市公开课一等奖百校联赛特等奖课件.pptx

第三章第三章 求解线性方程组数值解法求解线性方程组数值解法泰山学院信息科学技术系泰山学院信息科学技术系第1页解线性方程组两类方法:直接法:经过有限次运算后可求得方程组准确解方法(不计舍入误差!)迭代法：从解某个近似值出发，经过结构一个无穷序列去迫近准确解方法(普通有限步内得不到准确解)第2页3.1 解线性方程组直接法解线性方程组直接法 一、高斯消去法一、高斯消去法思思绪绪首先将方程组首先将方程组Ax=b 化为上三角方程组化为上三角方程组，此过程称为此过程称为消去过程消去过程，再求解上三角方程，再求解上三角方程组，此过程称为组，此过程称为回代过程回代过程.3.1.1 高斯消去法和选主元高斯消去法高斯消去法和选主元高斯消去法第3页将增广矩阵将增广矩阵第第 i 行行 +li1 第第1 1行行，得到：，得到：消去过程：消去过程：第一步第一步：设设 ，计算因子，计算因子其中其中第4页第第k步：步：设设 ，计算因子，计算因子且计算且计算共进行共进行 n 1步，得到步，得到第5页定理：定理：若若A全部全部次序主子式次序主子式 均不为均不为0，则高斯消去，则高斯消去法能次序进行消元，得到唯一解。法能次序进行消元，得到唯一解。回代过程：回代过程：第6页二、二、选主元消去法选主元消去法为防止这种情况发生,可经过交换方程次序，选取绝对值大元素作主元.基于这种思想导出了主元素法在高斯消去法消去过程中可能出现 情况，这时高斯消去法将无法进行；即使主原因 但很小，其作除数，也会造成其它元素数量级严重增加和舍误差扩散第7页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 次序，须统计次序，须统计交换次序交换次序，解完后再换回来。解完后再换回来。第9页 运算量运算量（Amount of Computation）（1 1）用克莱姆用克莱姆（CramerCramer）法则求解法则求解n n阶线性方程组阶线性方程组 每个行列式由每个行列式由n!n!项相加，而每项包含了项相加，而每项包含了n n个因子个因子相乘，乘法运算次数为相乘，乘法运算次数为(n-1)n!n-1)n!次次.仅考虑乘仅考虑乘(除除)法运算法运算,计算解向量包含计算计算解向量包含计算n+1n+1个行列式和个行列式和n n次除法运算次除法运算,乘乘(除除)法运算次数法运算次数N=(n+1)(n-1)n!+n.第10页（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-1)次乘法运算和次乘法运算和 n(n-1)n(n-1)次加次加(减减)法运算法运算.在第在第k k个消去步，有个消去步，有n-kn-k次除法运算、次除法运算、(n-k+1)(n-k)n-k+1)(n-k)次次乘法运算和相同加乘法运算和相同加(减减)法运算法运算.首先统计乘法运算总次数首先统计乘法运算总次数.将每个消去步乘法运算次将每个消去步乘法运算次数相加，数相加，有有n(n-1)+(n-1)(n-2)+3.2+2.1=n(n-1)(n+1)/3n(n-1)+(n-1)(n-2)+3.2+2.1=n(n-1)(n+1)/3加加(减减)法运算次数总计也为法运算次数总计也为n(n-1)(n+1)/3.n(n-1)(n+1)/3.除法运算总次数为除法运算总次数为n+(n-1)+1=n(n-1)/2n+(n-1)+1=n(n-1)/2第11页回代过程计算回代过程计算除法运算次数为除法运算次数为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，乘法运算次数为乘法运算次数为: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，加加(减减)法运算次数为法运算次数为:n(n-1)(2n+5)/6n(n-1)(2n+5)/6通常也说通常也说GaussGauss消去法运算次数与消去法运算次数与n n3 3同阶，记为同阶，记为O(nO(n3 3)第12页u全主远消去法全主远消去法:比比 高斯消去法多出高斯消去法多出 比较，确保稳定，但费时比较，确保稳定，但费时。u 列主元消去法列主元消去法:比比 高斯消去法只多出高斯消去法只多出 比较，略省时。比较，略省时。第13页2.1.22.1.2 三角分解法三角分解法 高斯消元法矩阵形式高斯消元法矩阵形式 每一步消去过程相当于左乘初等变换矩阵Lk第14页第15页A LU 分解分解(LU factorization)第16页定理定理2.1.4：若若A全部次序主子式全部次序主子式 均不为均不为0，则，则 A LU 分解分解唯一（其中唯一（其中 L 为为单位单位下三角阵）。下三角阵）。证实：由证实：由1中定理可知，中定理可知，LU 分解存在。下面证实唯一性。分解存在。下面证实唯一性。若不唯一，则可设若不唯一，则可设 A=L1U1=L2U2，推出推出上三角矩阵上三角矩阵对角线上为对角线上为1 1下下三角矩阵三角矩阵注注注注：（1 1）L 为单位下三角阵而为单位下三角阵而 U 为为普通普通上三角阵分解上三角阵分解称为称为Doolittle 分解分解（2）L 为普通下三角阵而为普通下三角阵而 U 为为单位单位上三角阵分解称为上三角阵分解称为Crout 分解分解。第17页 Doolittle分解法分解法 ：经过比较法直接导出经过比较法直接导出L 和和 U 计算公式。计算公式。思思绪绪第18页普通计算公式 计算量与 Gauss 消去法同.第19页LU 分解求解线性方程组第20页第21页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第22页定理定理2.1.6 设矩阵设矩阵A对称正定，则存在唯一对角元全对称正定，则存在唯一对角元全为正下三角阵为正下三角阵G 使得使得 AGGT计算格式为计算格式为第23页2.1.5 2.1.5 求解三对角方程组追赶法求解三对角方程组追赶法定理：定理：若若 A 为为对角占优对角占优 三对角阵，且满足三对角阵，且满足 则方程组有唯一则方程组有唯一LU分解。分解。第24页直接比较等式两边元素，可得到计算公式（直接比较等式两边元素，可得到计算公式（p.66）第二步第二步:追追即解即解 ：第三步第三步:赶赶即解即解 ：第一步第一步:对对 A 作作Crout 分解分解第25页