线性代数方程组的直接解法省公共课一等奖全国赛课获奖课件.pptx

3.1引言引言 在工程技术、自然科学和社会科学中，经常在工程技术、自然科学和社会科学中，经常碰到许多问题最终都可归结为解线性方程组，如碰到许多问题最终都可归结为解线性方程组，如电学中网络问题、用最小二乘法求试验数据曲线电学中网络问题、用最小二乘法求试验数据曲线拟合问题，工程中三次样条函数插值问题，经济拟合问题，工程中三次样条函数插值问题，经济运行中投入产出问题以及大地测量、机械与建筑运行中投入产出问题以及大地测量、机械与建筑结构设计计算问题等等，都归结为求解线性方程结构设计计算问题等等，都归结为求解线性方程组或非线性方程组数学问题。所以线性方程组求组或非线性方程组数学问题。所以线性方程组求解对于实际问题是极其主要。解对于实际问题是极其主要。第第3 3章章解线性方程组直接法解线性方程组直接法第1页第第3章章 解线性方程组直接法解线性方程组直接法 常见线性方程组是方程个数和未知量个数常见线性方程组是方程个数和未知量个数相同相同n阶线性方程组，普通形式为阶线性方程组，普通形式为简记为简记为Ax=b，其中，其中(3.1)普通普通b0,当系数矩阵当系数矩阵A非奇异非奇异(即即detA0)时，方程组（时，方程组（3.1）有惟一解。）有惟一解。第2页线性方程组数值解法普通有两类：线性方程组数值解法普通有两类：1.直接法：就是经过有限步算术运算，可求得直接法：就是经过有限步算术运算，可求得方程组准确解方法（若计算过程中没有舍入方程组准确解方法（若计算过程中没有舍入误差），如克莱姆法则就是一个直接法，直误差），如克莱姆法则就是一个直接法，直接法中含有代表性算法是高斯接法中含有代表性算法是高斯(Gauss)消去消去法。法。2.迭代法迭代法:就是用某种极限过程去逐步迫近线就是用某种极限过程去逐步迫近线性方程组准确解方法。也就是性方程组准确解方法。也就是从解某个近似从解某个近似值出发，经过结构一个无穷序列去迫近准确值出发，经过结构一个无穷序列去迫近准确解方法。解方法。(普通有限步内得不到准确解普通有限步内得不到准确解)第3页3.2解线性方程组直接法（高斯消去法）解线性方程组直接法（高斯消去法）3.2.1高斯消去法基本思想高斯消去法基本思想先用一个简单实例来说明先用一个简单实例来说明Gauss法基本思想法基本思想例例3.1 3.1 解线性方程组解线性方程组 解解:该方程组求解过程实际上是将中学学过消元法该方程组求解过程实际上是将中学学过消元法标准化标准化,将一个方程乘或除以某个常数将一个方程乘或除以某个常数,然后将两个然后将两个方程相加减方程相加减,逐步降低方程中未知数逐步降低方程中未知数,最终使每个方最终使每个方程只含有一个未知数程只含有一个未知数,从而得出所求解。整个过程从而得出所求解。整个过程分为消元和回代两个部分。分为消元和回代两个部分。第4页（1）消元过程）消元过程第第1步步:将方程将方程乘上乘上(-2)加到方程加到方程上去上去,将将方程方程乘上乘上 加到方程加到方程上去上去,这么就消去这么就消去了第了第2、3个方程个方程 项项,于是就得到等价方程组于是就得到等价方程组第5页第第2步：将方程步：将方程乘上乘上 加到方程加到方程上去，上去，这么就消去了第这么就消去了第3个方程个方程 项，于是就得到等项，于是就得到等价方程组价方程组这么，消元过程就是把原方程组化为上三角这么，消元过程就是把原方程组化为上三角形方程组，其系数矩阵是上三角矩阵。形方程组，其系数矩阵是上三角矩阵。（2）回代过程）回代过程回代过程是将上述三角形方程组自下而上求回代过程是将上述三角形方程组自下而上求解，从而求得原方程组解：解，从而求得原方程组解：第6页说明：前述消元过程相当于对原方程组说明：前述消元过程相当于对原方程组 增广矩阵进行以下变换增广矩阵进行以下变换(表示增广矩阵第表示增广矩阵第 行）行）一样可得到与原方程一样可得到与原方程组等价方程组组等价方程组第7页 由此看出由此看出,高斯消去法解方程组基本思想是设法高斯消去法解方程组基本思想是设法消去方程组系数矩阵消去方程组系数矩阵A主对角线下元素主对角线下元素,而将而将Ax=b化化为等价上三角形方程组为等价上三角形方程组,然后再经过回代过程便可取然后再经过回代过程便可取得方程组解。换一个说法就是用矩阵行得方程组解。换一个说法就是用矩阵行初等变换初等变换将将原方程组系数矩阵化为上三角形矩阵原方程组系数矩阵化为上三角形矩阵,而以上三角形而以上三角形矩阵为系数方程组求解比较简单矩阵为系数方程组求解比较简单,能够从最终一个方能够从最终一个方程开始程开始,依次向前代入求出未知变量依次向前代入求出未知变量 这种求解上三角方程组方法称为这种求解上三角方程组方法称为回代回代,经过一个方程经过一个方程乘或除以某个常数乘或除以某个常数,以及将两个方程相加减以及将两个方程相加减,逐步降逐步降低方程中变元数低方程中变元数,最终将方程组化成上三角方程组最终将方程组化成上三角方程组,普通将这一过程称为普通将这一过程称为消元消元,然后再回代求解。然后再回代求解。通常把按照先消元通常把按照先消元,后回代两个步骤求解线性后回代两个步骤求解线性方程组方法称为方程组方法称为高斯高斯（Gauss）消去法。消去法。第8页3.2.2高斯消去法算法结构高斯消去法算法结构 我们知道我们知道,线性方程组线性方程组(3.1)用矩阵形式表示用矩阵形式表示为为 (3.3)解线性方程组（解线性方程组（3.1）高斯（）高斯（Gauss）消去法消元过程）消去法消元过程就是对就是对(3.3)增广矩阵进行行初等变换。将例增广矩阵进行行初等变换。将例3.1中解中解三阶线性方程组消去法推广到普通三阶线性方程组消去法推广到普通 阶线性方程阶线性方程组并记组并记则高斯消去法算法结构归纳为：则高斯消去法算法结构归纳为：第9页 消元过程消元过程,高斯消去法消元过程由高斯消去法消元过程由n-1步组成：步组成：第第1 1步步 设设 ,把把(3.3)(3.3)中第一列中元素中第一列中元素 消为零消为零,令令 用用 乘以第乘以第1 1个方程后加到第个方程后加到第 个方程上去个方程上去,消去消去第第2 2n n个方程未知数个方程未知数 ,得到得到 即即其中其中 第10页第第k步步（k=2,3,n-1）继续上述消元过程，设）继续上述消元过程，设第第k-1次消元已经完成，得到与原方程组等价方次消元已经完成，得到与原方程组等价方程组程组记为记为 其中其中第11页只要只要 ,消元过程就能够进行下去消元过程就能够进行下去,直到直到经过经过n-1n-1次消元之后，消元过程结束，得到与次消元之后，消元过程结束，得到与原方程组等价上三角形方程组原方程组等价上三角形方程组,记为记为或者写成或者写成 第12页即即(3.7)（2）回代过程）回代过程就是对上三角方程组（就是对上三角方程组（3.7）自下而上逐步回代解方）自下而上逐步回代解方程组计算，即程组计算，即第13页（3 3）高斯消去法计算步骤：）高斯消去法计算步骤：消元过程消元过程;设设 计算计算 回代过程回代过程 第14页 普通线性方程组使用高斯消去法求解时，普通线性方程组使用高斯消去法求解时，在消元过程中可能会出现在消元过程中可能会出现 情况，这时情况，这时消去法将无法进行；即使消去法将无法进行；即使 ，但它绝对，但它绝对值很小时，用其作除数，会造成其它元素数量值很小时，用其作除数，会造成其它元素数量级严重增加和舍入误差扩散，将严重影响计算级严重增加和舍入误差扩散，将严重影响计算结果精度。实际计算时必须防止这类情况发生。结果精度。实际计算时必须防止这类情况发生。主元素消去法就可填补这一缺点。主元素消去法就可填补这一缺点。第15页v交换标准：经过方程或变量次序交换，交换标准：经过方程或变量次序交换，使在对角线位置上取得绝对值尽可能大使在对角线位置上取得绝对值尽可能大系数作为系数作为akk(k)，称这么，称这么akk(k)为为主元素主元素，并称使用主元素消元法并称使用主元素消元法为主元素法为主元素法v依据主元素选取范围分为：列主元素法、依据主元素选取范围分为：列主元素法、行主元素法、总体选（全）主元素法行主元素法、总体选（全）主元素法记笔记记笔记3.2.4 3.2.4 高斯主元素消去法高斯主元素消去法第16页主元素法意义主元素法意义例例3.2用高斯消去法求以下方程组解用高斯消去法求以下方程组解 解：解：确定乘数确定乘数，再计算系数，再计算系数假设计算在假设计算在4 4位浮点十进值计算机上求解位浮点十进值计算机上求解,则有则有这时方程组实际形式是这时方程组实际形式是 由此回代解出由此回代解出 ,但这个解不满足原但这个解不满足原方程组方程组,解是错误。这是因为所用除数太小使得解是错误。这是因为所用除数太小使得上式在消元过程中上式在消元过程中“吃掉吃掉”了下式，处理这个了下式，处理这个问题方法之一就是采取列选主元高斯消元法。问题方法之一就是采取列选主元高斯消元法。即按列选绝对值大系数作为主元素，则将方程即按列选绝对值大系数作为主元素，则将方程组中两个方程相交换，原方程组变为组中两个方程相交换，原方程组变为得到消元后方程组得到消元后方程组 第17页这时这时 因而方程组实际形式是因而方程组实际形式是 由此回代解出由此回代解出 ,这个结果是正确这个结果是正确 可见用高斯消去法解方程组时可见用高斯消去法解方程组时,小主元可小主元可能造成计算失败能造成计算失败,因为用绝对值很小数作除数因为用绝对值很小数作除数,乘数很大乘数很大,引发约化中间结果数量级严重增加引发约化中间结果数量级严重增加,再舍入就使得计算结果不可靠了再舍入就使得计算结果不可靠了,故防止采取故防止采取绝对值很小主元素。方便降低计算过程中舍入绝对值很小主元素。方便降低计算过程中舍入误差对计算解影响。误差对计算解影响。第18页总体选（全）主元素消去法总体选（全）主元素消去法是经过方程或变量次序交换，使在对角线是经过方程或变量次序交换，使在对角线位置上取得绝对值尽可能大系数作位置上取得绝对值尽可能大系数作 ，称这，称这么么 为主元素。尽管它算法更稳定，但计为主元素。尽管它算法更稳定，但计算量较大，实际应用中大多数使用列主元素消算量较大，实际应用中大多数使用列主元素消去法即可满足需要。去法即可满足需要。第19页vv全主元素法全主元素法不是按列选主元素，而是在全体不是按列选主元素，而是在全体待选系数中选取，则得待选系数中选取，则得全主元素法。全主元素法。v例例3.3 用用全主元素法解以下线组全主元素法解以下线组10 x1-19x2-2x3=3(1)-20 x1+40 x2+x3=4(2)x1+4x2+5x3=5(3)n解：选择全部系数中绝对值最大解：选择全部系数中绝对值最大40作为作为主元主元素，交换第一、二行和交换第一、二列使该素，交换第一、二行和交换第一、二列使该主元素位于对角线第一个位置上，得主元素位于对角线第一个位置上，得40 x2-20 x1+x3=4(4)-19x2+10 x1-2x3=3(5)4x2+x1+5x3=5(6)记笔记记笔记第20页计算计算m21=-19/40=0.475，m31=4/40=0.1(5)-m21(4),(6)-m31(4)消去消去x2 得得 0.5x11.525x3=4.9(7)3x1+4.9x3=4.6(8)选选4.9为主元素为主元素 4.9 x3+3x1=4.6(9)1.525 x3+0.5x1=4.9(10)计算计算m32=-1.525/4.9=-0.31122，(10)-m32(9)消去消去x2得得1.43366x1=6.33161(11)记笔记记笔记第21页保留有主元素方程保留有主元素方程40 x2-20 x1+x3=4(4)4.9x3+3x1=4.6(9)1.43366x1=6.33161(11)进行回代进行回代x1=4.41634 x3=-1.76511x2=2.35230第22页3.2.4.1 列主元素法列主元素法v列主元素法就是在待消元所在列中选取主元，列主元素法就是在待消元所在列中选取主元，经方程行交换，置主元素于对角线位置后进经方程行交换，置主元素于对角线位置后进行消元方法。行消元方法。v例例3.4 用用列主元素法解以下线性方程组列主元素法解以下线性方程组10 x1-19x2-2x3=3(1)-20 x1+40 x2+x3=4(2)x1+4x2+5x3=5(3)n解：选择解：选择-20作为该列作为该列主元素主元素，-20 x1+40 x2+x3=3(4)10 x1-19x2-2x3=4(5)x1+4x2+5x3=5(6)计算计算m21=10/-20=-0.5m31=1/-20=-0.05第23页(5)-m21(4),(6)-m31(4)得得 x21.5x3=5(7)6x2+5.05x3=5.2(8)选选6为主元素为主元素6x2+5.05x3=5.2(9)x21.5x3=5(10)计算计算m32=1/6=0.16667，(10)-m32(9)得得-2.34168x3=4.13332(11)记笔记记笔记第24页保留有主元素方程保留有主元素方程-20 x1+40 x2+x3=4(4)6x2+5.05x3=5.2(9)-2.34168x3=4.13332(11)进行回代进行回代x3=-1.76511x2=2.35230 x1=4.41634记笔记记笔记 列选主元素计算方法与高斯消去法完全一样列选主元素计算方法与高斯消去法完全一样,不一样是在每步消元之前要按列选出主元。不一样是在每步消元之前要按列选出主元。第25页例例3.5 3.5 用矩阵初等行变换求解方程组用矩阵初等行变换求解方程组 解解:用矩阵初等行变换求解用矩阵初等行变换求解,对增广矩阵对增广矩阵 (下面带下划线元素为主元素下面带下划线元素为主元素)第26页第27页3.2.5 3.2.5 高斯高斯-约当（约当（Jordan）消去法）消去法 高斯消去法有消元和回代两个过程，消去高斯消去法有消元和回代两个过程，消去是对角线下方元素。当对消元过程稍加改变便是对角线下方元素。当对消元过程稍加改变便可使方程组可使方程组 化为对角阵化为对角阵（3.83.8）这时求解就不需要回代了这时求解就不需要回代了,这种将主元素化为这种将主元素化为1,1,并用主元将其所在列冗余元素全都消为并用主元将其所在列冗余元素全都消为0,0,即消即消去对角线上方与下方元素去对角线上方与下方元素,这种方法称为这种方法称为高斯高斯-约当消去法约当消去法,这时等号右端即为方程组解这时等号右端即为方程组解第28页例例3.6 3.6 用高斯用高斯-约当约当(Jordan)(Jordan)消去法求方程组解消去法求方程组解 解解 方程组对应增广矩阵方程组对应增广矩阵 列选主元列选主元故得故得 第29页定理定理3.4 3.4 设设A A为非奇异矩阵，方程组为非奇异矩阵，方程组AX=I增增广矩阵为广矩阵为 C=A A I I ，假如对，假如对C应用高斯应用高斯-约约当消去法化为当消去法化为 I I B B，则，则 =B。例例3.7 3.7 用高斯用高斯-约当（约当（JordanJordan）消去法）消去法求求 逆矩阵逆矩阵 第30页解解 C=A A I I =第31页3.3矩阵三角分解法矩阵三角分解法 矩阵三角分解法是高斯消去法解线性方程组一个矩阵三角分解法是高斯消去法解线性方程组一个变形解法变形解法。3.3.1 3.3.1 矩阵三角分解原理矩阵三角分解原理 应用高斯消去法解应用高斯消去法解n阶线性方程组阶线性方程组Ax=b,经过经过n步消元之后步消元之后,得出一个等价上三角型方程组得出一个等价上三角型方程组A(n)x=b(n),对上三角形方程组用逐步回代就能够求对上三角形方程组用逐步回代就能够求出解来。上述过程可经过矩阵分解来实现。出解来。上述过程可经过矩阵分解来实现。将非奇异阵将非奇异阵A分解成一个下三角阵分解成一个下三角阵L和一个上三和一个上三角阵角阵U乘积乘积A=LU称为对称为对矩阵矩阵A A三角分解，又称三角分解，又称LU分解。分解。第32页其中其中第33页方程组方程组Ax=b系数矩阵系数矩阵A经过次序消元逐步化为经过次序消元逐步化为上三角型上三角型A(n),相当于用一系列初等变换左乘相当于用一系列初等变换左乘A结果。实际上，第结果。实际上，第1列消元将列消元将A(1)=A化为化为A(2)，若令：，若令：则依据距阵左乘有则依据距阵左乘有L1A(1)=A(2)第34页第第2列消元将列消元将A(2)化为化为A(3)，若令：，若令：经计算可知经计算可知L2A(2)=A(3),依这类推依这类推,普通有普通有LkA(k)=A(k+1)第35页mi1=a(1)i1/a(1)11i=2,3,n于是矩阵于是矩阵经过消元化为上三角阵经过消元化为上三角阵过程可表示为过程可表示为上述矩阵上述矩阵 是一类初等矩阵是一类初等矩阵,它们都是单位下三角阵，且其逆矩阵也是单位它们都是单位下三角阵，且其逆矩阵也是单位下三角阵下三角阵,只需将只需将 改为改为 ,就得到就得到 。即。即第36页于是有于是有 其中其中 第37页L L为由乘数组成单位下三角阵，为由乘数组成单位下三角阵，U U为上三角阵，由为上三角阵，由此可见，在此可见，在 条件下，高斯条件下，高斯消去法实质上是将方程组系数矩阵消去法实质上是将方程组系数矩阵A A分解为两个分解为两个三角矩阵乘积三角矩阵乘积A=LUA=LU。这种把非奇异矩阵。这种把非奇异矩阵A A分解成分解成一个下三角矩阵一个下三角矩阵L L和一个上三角矩阵和一个上三角矩阵U U乘积称为矩乘积称为矩阵三角分解，又称阵三角分解，又称LULU分解。分解。显然，假如显然，假如 ,由行列式由行列式性质知，方程组系数矩阵性质知，方程组系数矩阵A A前前n-1n-1个次序主子矩阵个次序主子矩阵 非奇异，即次序主子式不等于零，即非奇异，即次序主子式不等于零，即第38页其中其中 （A A主子阵）主子阵）反之反之,可用归纳法证实可用归纳法证实,假如假如A A次序主子式次序主子式 则则 于是得到下述定理：于是得到下述定理：第39页 把把A分解成一个单位上三角阵分解成一个单位上三角阵L和一个下和一个下三角阵三角阵U乘积称为乘积称为杜利特尔（杜利特尔（Doolittle）分分解解。其中其中 第40页若把若把A分解成一个下三角阵分解成一个下三角阵L和一个单位上和一个单位上三角阵三角阵U乘积称为乘积称为克克洛特分解洛特分解Crout）其中其中 第41页3.3.2用三角分解法解方程组用三角分解法解方程组 求求解线性方程组解线性方程组Ax=b时时,先对非奇异矩阵先对非奇异矩阵A进行进行LU分解使分解使A=LU，那么方程组就化为，那么方程组就化为LUx=b从而使问题转化为求解两个简单三角方程组从而使问题转化为求解两个简单三角方程组Ly=b求解求解yUx=y求解求解x这这就就是是求求解解线线性性方方程程组组三三角角分分解解法法基基本本思思想想。下下面面只只介介绍绍杜杜利利特特尔尔（Doolittle）分分解解法法。设设A=LU为为第42页由矩阵乘法规则由矩阵乘法规则由此可得由此可得U第第1行元素和行元素和L第第1列元素列元素第43页 再再确确定定U第第k行行元元素素与与L第第k列列元元素素,对对于于k=2,3,n计算：计算：计算计算U第第k行元素行元素（j=k,k+1,nj=k,k+1,n）计算计算L L第第k k列元素列元素 （i=k,k+1,ni=k,k+1,n）第44页利用上述计算公式便可逐步求出利用上述计算公式便可逐步求出U与与L各元素各元素求解求解 Ly=b,Ly=b,即计算即计算:求解求解 Ux=y,Ux=y,即计算：即计算：第45页显显然然,当当时时,解解Ax=b直直接接三三角角分分解解法法计计算算才才能能完完成成。设设A为为非非奇奇异异矩矩阵阵,当当时时计计算算将将中中止止或或者者当当绝绝对对值值很很小小时时，按按分分解解公公式式计计算算可可能能引引发发舍舍入入误误差差积积累累，所所以以可可采采取取与与列列主主元元消消去去法法类类似似方方法法，对对矩矩阵阵进进行行行行交交换换，则再实现矩阵三角分解。则再实现矩阵三角分解。用直接三角分解法解用直接三角分解法解Ax=b大约需要大约需要 次乘除法。次乘除法。第46页例例3.8用三角分解法解方程组用三角分解法解方程组 求解求解Ly=b得得y=2，2，1T 求解求解Ux=y得得x=-1，0，1T所以方程组解为所以方程组解为第47页本章小结本章小结 本章介绍了解线性方程组直接法。直接法是本章介绍了解线性方程组直接法。直接法是一个计算量小而精度高方法。直接法中含有代表一个计算量小而精度高方法。直接法中含有代表性算法是高斯（性算法是高斯（Gauss）消去法（在第一章提到克）消去法（在第一章提到克莱姆算法也是一个直接法，但该算法用于高阶方莱姆算法也是一个直接法，但该算法用于高阶方程组时计算量太大而不实用），其它算法大都是程组时计算量太大而不实用），其它算法大都是它变型，这类方法是解含有稠密矩阵或非结构矩它变型，这类方法是解含有稠密矩阵或非结构矩阵（零元分布无规律）方程组有效方法。阵（零元分布无规律）方程组有效方法。第48页 选选主主元元算算法法有有很很好好数数值值稳稳定定性性。从从计计算算简简单单出出发发实实际中多项选择取列主元法。际中多项选择取列主元法。第49页 在在实实际际应应用用中中怎怎样样选选择择算算法法是是一一个个主主要要问问题题，往往往从三个方面考虑：往从三个方面考虑：解精度高；解精度高；计算量小；计算量小；所需计算机内存小。所需计算机内存小。但这些条件相互间是矛盾而不能兼顾，所以实但这些条件相互间是矛盾而不能兼顾，所以实际计算时应依据问题特点和要求及所用计算机性能际计算时应依据问题特点和要求及所用计算机性能来选择算法。普通说，系数矩阵为中、小型满矩阵，来选择算法。普通说，系数矩阵为中、小型满矩阵，用直接法很好；当系数矩阵为大型、稀疏矩阵时，用直接法很好；当系数矩阵为大型、稀疏矩阵时，有效解法是下节要讨论迭代法。有效解法是下节要讨论迭代法。第50页