求解线性方程组精.ppt
求解线性方程组第1页，本讲稿共40页1 1 引言与预备知识引言与预备知识第七章第七章 解线性代数方程组的直接法解线性代数方程组的直接法一、引言一、引言线性方程组的来源线性方程组的分类线性方程组的两类解法：1、直接法2、迭代法二、向量和矩阵二、向量和矩阵(略略)第2页，本讲稿共40页三、特殊矩阵三、特殊矩阵1)对角矩阵2)三对角矩阵3)上三角矩阵4)Hessenberg阵5)对称矩阵6)埃尔米特矩阵7)对称正定矩阵8)正交矩阵9)酉矩阵10)初等置换阵11)置换阵第3页，本讲稿共40页定理定理1 设ARnn,A非奇异?定理定理2 若ARnn对称正定矩阵，则?定理定理3 若ARnn对称矩阵，则对称正定矩阵=?定理定理4(若当标准型)其中其中对角化的条件：1）；2）.第4页，本讲稿共40页求解求解1 高斯消去法高斯消去法 高斯消去法：高斯消去法：思思路路首先将首先将A 化为上三角阵，化为上三角阵，再回代求解再回代求解 。=第5页，本讲稿共40页记记Step 1：设设 ，计算因子，计算因子将增广矩阵将增广矩阵第第 i 行行 mi1 第第1 1行行，得到，得到其中其中Step k：设设 ，计算因子，计算因子且计算且计算共进行共进行？步步n 1主元主元第6页，本讲稿共40页定理定理 若若A的所有的所有顺序主子式顺序主子式 均不为均不为0，则高斯消元无需换行即，则高斯消元无需换行即可进行到底，得到唯一解。可进行到底，得到唯一解。注注注注：事实上，只要事实上，只要 A 非奇异，即非奇异，即 A 1 存在，则可通过逐次存在，则可通过逐次消元及行交换，将方程组化为三角形方程组，求出唯消元及行交换，将方程组化为三角形方程组，求出唯一解。一解。第7页，本讲稿共40页2 2 高斯消去法高斯消去法一、高斯消去法一、高斯消去法设有线性方程组：AXAX=b b一般地,顺序高斯消去法:第8页，本讲稿共40页（1）消元过程其中第一步：若用乘第一行加到第i行中，得到第二步：若用.第9页，本讲稿共40页第k步：若用乘第k行加到第i行中，得到其中第10页，本讲稿共40页第n-1步：（2）回代过程若则第11页，本讲稿共40页说明说明:若线性方程组的系数矩阵非奇异，则它总可以通若线性方程组的系数矩阵非奇异，则它总可以通过带行交换的高斯消去法进行求解。过带行交换的高斯消去法进行求解。定理定理7.17.1可以通过高斯消去法求解.(2)系数矩阵非奇异，总可以通过带行交换的高斯消去 法进行求解。列主元高斯消去法的必要性,简例简例:(1)第12页，本讲稿共40页算法算法.第13页，本讲稿共40页第14页，本讲稿共40页二、矩阵的三角分解二、矩阵的三角分解下面建立高斯消去法与矩阵的因式分解的关系.第15页，本讲稿共40页第16页，本讲稿共40页第17页，本讲稿共40页第18页，本讲稿共40页第19页，本讲稿共40页课堂练习第20页，本讲稿共40页3 3 高斯主元素消去法高斯主元素消去法例例33采用3位十进制，用消元法求解 解法解法1：第21页，本讲稿共40页解法解法2：全主元消去法;列主元消去法.第22页，本讲稿共40页一、全主元消去法一、全主元消去法第23页，本讲稿共40页首先选取系数矩阵中绝对值最大的元素作为主元素首先选取系数矩阵中绝对值最大的元素作为主元素重复上述过程，设已完成第重复上述过程，设已完成第k-1k-1步的选主元素，步的选主元素，交换两行及两列，消元计算得交换两行及两列，消元计算得：第24页，本讲稿共40页第第k k步选主元素，交换行列，消元计算；步选主元素，交换行列，消元计算；最后将原方程化为最后将原方程化为回代求解回代求解选主元计算量选主元计算量太大太大第25页，本讲稿共40页二、列主元消去法二、列主元消去法设有线性方程组：AX=b第一步:先在A的第一列选取绝对值最大的元素作主元素,然后交换第1行和第i1行(当i11时),再进行第1次消元.第26页，本讲稿共40页 第k步选主元素,然后交换第k行和第ik行(当ikk时),再进行第k次消元.第n-1步第27页，本讲稿共40页回代求解算法算法(列主元消去法列主元消去法).第28页，本讲稿共40页下面用矩阵描述列主元消去法见课后习题见课后习题8第29页，本讲稿共40页说明说明:L,U,Ip的存贮.第30页，本讲稿共40页二、高斯二、高斯若当消去法若当消去法第31页，本讲稿共40页算法算法(高斯高斯若当消元法若当消元法).第32页，本讲稿共40页第33页，本讲稿共40页例例4 4 采用高斯若当消去法求矩阵的逆A-1.第34页，本讲稿共40页 选主元消去法选主元消去法例：例：单精度解方程组单精度解方程组/*精确解为精确解为 和和 */8个个8个个用用高斯消元法高斯消元法计算：计算：8个个小主元小主元 可能导致计算可能导致计算失败。失败。第35页，本讲稿共40页 全主元消去法全主元消去法每一步选绝对值最大的元素为主元素，保证每一步选绝对值最大的元素为主元素，保证 。Step k:选取选取 If ik k then 交换第交换第 k 行与第行与第 ik 行行;If jk k then 交换第交换第 k 列与第列与第 jk 列列;消元消元注注注注：列交换改变了列交换改变了 xi 的顺序，须记录的顺序，须记录交换次序交换次序，解完后再，解完后再换回来。换回来。列主元消去法列主元消去法省去换列的步骤，每次仅选一列中最大的元。省去换列的步骤，每次仅选一列中最大的元。第36页，本讲稿共40页例：例：注注注注：列主元法没有全主元法稳定。列主元法没有全主元法稳定。例：例：注意：这两个方程组在注意：这两个方程组在数学上数学上严格等价严格等价。标度化列主元消去法标度化列主元消去法对每一行计算对每一行计算 。为省时间，。为省时间，si 只在初始时计算只在初始时计算一次。以后每一步考虑子列一次。以后每一步考虑子列 中中 最大的最大的 aik 为主元为主元.注注注注：稳定性介于列主元法和全主元法之间。稳定性介于列主元法和全主元法之间。第37页，本讲稿共40页 高斯高斯-若当若当消去法消去法与与高斯消元法高斯消元法的主要区别：的主要区别：每步不计算每步不计算 mik，而是先将当前主元，而是先将当前主元 akk(k)变为变为 1;把把 akk(k)所在列的上、下元素全消为所在列的上、下元素全消为0;不需要回代。不需要回代。第38页，本讲稿共40页 运算量运算量由于计算机中乘除由于计算机中乘除 运算的时间远远超过加减运算的时间远远超过加减 运算的时间，运算的时间，故估计某种算法的运算量时，往往只估计故估计某种算法的运算量时，往往只估计乘除的次数乘除的次数，而且通，而且通常以乘除次数常以乘除次数的的最高次幂最高次幂为运算量的为运算量的数量级数量级。高斯消元法高斯消元法:Step k：设设 ，计算因子，计算因子且计算且计算共进行共进行n 1步步(n k)次次(n k)2 次次(n k)次次(n k)(n k+2)次次消元乘除次数：消元乘除次数：1 次次(n i+1)次次回代乘除次数：回代乘除次数：高斯消元法高斯消元法的总乘除次数为的总乘除次数为 ，运算量为，运算量为 级。级。第39页，本讲稿共40页全主元消去法全主元消去法:比比高斯消元法高斯消元法多出多出 比较，保证稳定，但费时。比较，保证稳定，但费时。列主元消去法列主元消去法:比比高斯消元法高斯消元法只多出只多出 比较，略省时，但不保证稳比较，略省时，但不保证稳定。定。标度化列主元消去法标度化列主元消去法:比比高斯消元法高斯消元法多出多出 除法和除法和 比较比较,比列主元法稳比列主元法稳定。但若逐次计算定。但若逐次计算 si(k)，则比全主元法还慢。，则比全主元法还慢。高斯高斯-若当若当消去法消去法 :运算量约为运算量约为 。故通常只用于求逆矩阵。故通常只用于求逆矩阵,而不用于解方而不用于解方程组。求逆矩阵即程组。求逆矩阵即 。第40页，本讲稿共40页
