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

在没有在没有舍入误差舍入误差情况下，经过有限次情况下，经过有限次运算能够得到方程组运算能够得到方程组准确解准确解方法。方法。第三章第三章 线性方程组直接解法线性方程组直接解法/*Direct Method for Solving Linear Systems*/求解求解Cramer法则法则:所需乘除法运算量大约为所需乘除法运算量大约为(n+1)!+)!+nn=20时，每秒时，每秒1亿亿次运算速度计算机要算次运算速度计算机要算30多万年！多万年！直接法直接法第1页3.1 三角形方程组和三角分解三角形方程组和三角分解一、一、三角形方程组解法三角形方程组解法 考虑考虑下下三角形方程组三角形方程组第2页计算公式为计算公式为：算法算法3.1.1 下三角形方程组下三角形方程组前代前代法：法：forend第3页 考虑考虑上上三角形方程组三角形方程组计算公式为计算公式为：第4页算法算法3.1.2 上三角形方程组上三角形方程组回代回代法：法：forend两种算法工作量两种算法工作量(加减乘除运算次数之和加减乘除运算次数之和)均为均为第5页 三角分解法基本思想三角分解法基本思想:记记方程组可化为下面两个方程组可化为下面两个易求解易求解三角三角方程组方程组设已知方程组系数矩阵三角分解为设已知方程组系数矩阵三角分解为其中其中,为为下下三角矩阵三角矩阵,为为上上三角矩阵三角矩阵.第6页二、二、高斯高斯(Gauss)变换变换取下三角形矩阵取下三角形矩阵则则 可表示为可表示为其中为其中为 单位矩阵单位矩阵,称下三角形阵称下三角形阵 为为高斯高斯(Gauss)变换变换,为高斯向量为高斯向量.Gauss变换定义变换定义第7页 高斯高斯(Gauss)变换性质变换性质性质性质1 设向量设向量 且且则存在唯一则存在唯一下三角阵下三角阵 ,满足满足证实：证实：寻找满足条件寻找满足条件初等初等下三角阵下三角阵记记第8页写成份量形式：写成份量形式：唯一唯一确定确定性质性质2 第9页性质性质3第10页性质性质4若记若记 ,则有则有第11页即即单位单位下三角阵下三角阵能够分解为一系列能够分解为一系列初等初等下三角阵乘积下三角阵乘积第12页三、三、三角分解计算三角分解计算 Gauss消去法消去法设给定矩阵设给定矩阵取取Gauss变换变换矩阵矩阵则有则有第13页再取再取Gauss变换变换矩阵矩阵其中其中第14页设给定设给定 阶矩阵阶矩阵记记 Gauss消去法矩阵表示消去法矩阵表示令令Step 1：假如假如高斯变换高斯变换第15页取取其中其中记记第16页类似地，对类似地，对 中中 部分部分重复重复以上做法以上做法第17页Step k：第第k步步消元消元过程计算公式过程计算公式整个整个消元消元过程矩阵表示过程矩阵表示 上三角上三角矩阵矩阵计算计算第18页第19页经过经过n-1次消元，并将次消元，并将 存放在矩阵零元素位置存放在矩阵零元素位置第20页forforforGauss消去法消元过程算法消去法消元过程算法Gauss消去法工作量为消去法工作量为第21页三角分解计算过程三角分解计算过程:Step1Step2Step3Step4Step5Step6Step2n-1Step2(n-1)先计算先计算 行行再计算再计算 列列依次依次交替交替进行进行对方程组求解对方程组求解,只要得到了系数矩阵三角分解形式只要得到了系数矩阵三角分解形式,再再利用利用前代前代算法和算法和回代回代算法解两个三角方程组即得算法解两个三角方程组即得.第22页例例1 1：用用Gauss消去消去法求解以下方程组法求解以下方程组解：解：系数矩阵系数矩阵第23页第24页（Gauss消去法实现条件）消去法实现条件）全不为全不为零零充要条件是充要条件是各阶各阶次序主子式次序主子式都不等于都不等于零零，即，即证实：证实：归纳法证实归纳法证实(对对k归纳归纳)第25页设直到设直到k-1成立成立,只要证实只要证实非非零零时，时，非非零零充要条件是充要条件是 即可。即可。在归纳假设下，在归纳假设下，Gauss消去法可进行到第消去法可进行到第k-1步步其中其中 是对角元为是对角元为 上三角矩阵上三角矩阵矩阵矩阵 k阶阶主子式主子式 是是上三角上三角第26页均为单位均为单位下三角下三角矩阵矩阵其中其中所以，若矩阵各阶所以，若矩阵各阶次序主子式次序主子式均不为均不为零零，能够采取能够采取Gauss消元法进行三角分解。消元法进行三角分解。结论得证结论得证第27页若若 次序主子式次序主子式 均非奇异均非奇异,则存在唯一则存在唯一单位下三角单位下三角阵阵 和上和上三角阵三角阵 ,满足满足（矩阵三角分解一个充分条件矩阵三角分解一个充分条件)证实可参考定理证实可参考定理3.1.1.3.1.1.第28页给定矩阵给定矩阵 ，假如满足：，假如满足：且且时，时，则称则称 为上半带宽为为上半带宽为 ，下半带宽为，下半带宽为 带状带状矩阵，矩阵，称为称为带状带状方程组；方程组；假如假如 ，则称，则称 为为半带宽半带宽，并称之为并称之为等带宽等带宽方程组；方程组；为为 总带宽总带宽。四、四、其它其它三角分解三角分解假如矩阵假如矩阵 能够分解为一个能够分解为一个单位下三角阵单位下三角阵 和和一个上三一个上三角阵角阵 乘积，即乘积，即 ，则称，则称此分解为此分解为Doolittle分解分解;假如矩阵假如矩阵 能够分解一个下三角阵能够分解一个下三角阵 和单位上三角阵和单位上三角阵 乘积乘积,则称此分解为则称此分解为Crout分解分解.第29页比如比如上半带宽为上半带宽为2，下半带宽为，下半带宽为1总带宽为总带宽为3第30页半带宽半带宽为为t等等带状带状矩阵矩阵普通形式普通形式:第31页（保带状保带状结构定理）结构定理）设设 为上半带宽为为上半带宽为 ，下半带宽为，下半带宽为 带状带状矩阵，矩阵，且其且其次序主子式次序主子式 ，则，则 有唯一三角分解有唯一三角分解 ，其中其中 是是下半带宽下半带宽为为 单位下三角阵，单位下三角阵，是是上半带宽上半带宽为为 上三角阵。上三角阵。证实证实可依据前面讲过可依据前面讲过三角分解三角分解公式公式保带状保带状结构定理说明：矩阵三角分解中，结构定理说明：矩阵三角分解中，和和带外带外元素为元素为零零，所以无须计算，且无须参加，所以无须计算，且无须参加求和求和运算运算第32页 三对角三对角线性方程组三对角算法（线性方程组三对角算法（追赶法追赶法）三对角三对角线性方程组线性方程组其中其中第33页依据依据保带状保带状结构定理，系数矩阵可作以下三角分解：结构定理，系数矩阵可作以下三角分解：第34页 三对角三对角矩阵矩阵 分解计算公式：分解计算公式：第35页 方程组求解计算公式：方程组求解计算公式：解方程组解方程组 解方程组解方程组“追追”过程过程“赶赶”过程过程第36页 追赶法追赶法实现一个实现一个充分充分条件条件(补充补充)设设 为前述为前述三对角三对角矩阵，且满足以下条件：矩阵，且满足以下条件：则则 非奇异非奇异，且，且特殊情况：假如特殊情况：假如三对角三对角矩阵矩阵 为为严格对严格对角占优角占优矩阵，则能够采取矩阵，则能够采取追赶法追赶法求解。求解。第37页例例2 2：用用追赶法追赶法求解三对角求解三对角方程组方程组 ,其中其中:解：解：注意到本例并注意到本例并不满足不满足定理定理3.1.3条件条件,但依然能够但依然能够利用利用追赶法追赶法来求解来求解.所以所以,定理定理3.1.3条件仅是条件仅是充充分分条件条件.第38页第39页求解方程组求解方程组求解方程组求解方程组第40页3.2 选主元三角分解选主元三角分解 选选主元主元三角分解思想三角分解思想三角三角分解过程中存在问题分解过程中存在问题Gauss消元法消元法完成条件是矩阵各阶完成条件是矩阵各阶次序主子式次序主子式(n=1,2,n-1)均不为零均不为零.三角分解过程中除法运算要求分母不三角分解过程中除法运算要求分母不 能太小能太小,不然不然将可能产生将可能产生不稳定不稳定情况情况.选主元目标就是为了完成消元且防止不稳定情况发生选主元目标就是为了完成消元且防止不稳定情况发生第41页例例3 3：在在8位制计算机上解方程组位制计算机上解方程组要求用要求用三角分解三角分解方法方法计算。计算。8个个解：解：小主元小主元 可能造可能造成计算失败成计算失败第42页交换方程组两行交换方程组两行8个个第43页 Gauss全主元全主元三角分解法三角分解法交换交换单位单位矩阵矩阵 第第 列列(行行)和第和第 列列(行行)得到矩得到矩(初等初等置换置换矩阵矩阵)阵阵 ,称之为初等置换矩阵称之为初等置换矩阵.列列列列第44页Step 1(k=1)：第第1步选择步选择主元主元寻求寻求 和和 满足满足然后交换矩阵然后交换矩阵 第第 行和行和 行，第行，第 列和列和 列列设给定设给定 阶矩阵阶矩阵记记然后按照前面讨论方法进行三角分解然后按照前面讨论方法进行三角分解.用矩阵表示用矩阵表示:其中其中,为初等置换矩为初等置换矩阵阵.第45页第46页第47页其中其中第48页第第1步选步选主元主元完成后计算公式完成后计算公式:第第1步选步选主元主元完成后实际编程计算公式完成后实际编程计算公式:对对 中右下角中右下角 矩阵矩阵重复重复以上做法即可以上做法即可.Step k：第第k(k=1,2,n-1)步选择步选择主元主元寻求寻求 和和 满足满足第49页再按照前面讨论方法进行三角分解再按照前面讨论方法进行三角分解.用矩阵表示整个过程用矩阵表示整个过程:第第k步选步选主元主元完成后计算公式完成后计算公式:然后交换矩阵然后交换矩阵 第第 行和行和 行，第行，第 列和列和 列列第50页设上述过程能够进行到第设上述过程能够进行到第r步终止步终止,则有则有令令则有结论则有结论:其中其中 为上三角阵为上三角阵,为为单位下三角单位下三角阵阵,且它第且它第 列列对角线以下元素是由组成对角线以下元素是由组成 Gauss向量向量 做对应做对应排列得到排列得到,故故 全部元素之模均不会超出全部元素之模均不会超出1.结论含有什么结论含有什么意义意义?第51页令令证实：证实：则有则有下面利用归纳法证实下面利用归纳法证实 含有以下形含有以下形式式:其中其中 是全部元素模均小于是全部元素模均小于1 阶单位下三角阵阶单位下三角阵,是全部是全部元素模均小于元素模均小于1 阶矩阵阶矩阵,表示表示 阶单位矩阵阶单位矩阵.第52页k=1时结论显然成立时结论显然成立.现假设对现假设对k-1上述结论成立上述结论成立,则则其中其中 是由是由 交换了第交换了第1行和行和 行得到行得到,且且第53页 Gauss全主元全主元三角分解法求解方程组三角分解法求解方程组设已经得到三角分解式设已经得到三角分解式则原方程组等价于则原方程组等价于令令则则注意到注意到 计算可在三角分解过程中来完成计算可在三角分解过程中来完成 Gauss全主元全主元三角分解法存在问题三角分解法存在问题 选取主元方法中选取主元方法中计算量计算量太大太大;选取主元过程中用到选取主元过程中用到列列变换变换,需要统计需要统计交换信息交换信息.第54页设设 ，则存在，则存在排列矩阵排列矩阵 ,以及单位下三角阵以及单位下三角阵 和上三角阵和上三角阵 ,使得使得而且而且 全部元素均满足全部元素均满足 ,非零对角元非零对角元个数恰好等于矩阵个数恰好等于矩阵 秩秩.(排列矩阵排列矩阵)有限个初等置换矩阵有限个初等置换矩阵乘积乘积称之为排列矩阵称之为排列矩阵.全主元全主元Gauss消去法算法见教材消去法算法见教材:算法算法3.2.1第55页 Gauss列主元列主元三角分解法三角分解法Gauss列主元列主元三角分解法与三角分解法与全主元全主元三角分解法区分三角分解法区分就是在消元过程中只作就是在消元过程中只作行变换行变换,这么即能够降低选择这么即能够降低选择主元时主元时逻辑计算量逻辑计算量,又能够防止统计又能够防止统计交换信息交换信息.Step k：第第k(k=1,2,n-1)步选择步选择主元主元寻求寻求 满足满足用矩阵表示整个过程用矩阵表示整个过程:则有结论则有结论:第56页 Gauss列主元列主元三角分解法求解方程组三角分解法求解方程组设已经得到三角分解式设已经得到三角分解式则原方程组等价于则原方程组等价于令令则则注意到注意到 计算仍在三角分解过程中来完成计算仍在三角分解过程中来完成教材中教材中算法算法3.2.2为为列主元列主元Gauss消去法算法消去法算法第57页 算法算法:Gauss列主元列主元消去算法消去算法求方程组求方程组Ax=b 解解.输入输入:增广矩阵增广矩阵An(n+1)=（A|b）.输出输出:近似解近似解 xk=ak,n+1(k=1,2,n)或失败信息或失败信息.消元消元过程过程 for k=1,2,n-1 do Step 1-Step 4 Step 1 寻找行号寻找行号 ik,使得使得Step 2 假如假如 ，则交换第，则交换第k行和行和ik行；行；不然转不然转Step 7 第58页 算法算法:Gauss列主元列主元消去算法（续）消去算法（续）Step 3 for i=k+1,n 计算计算 Step 4 for j=k+1,n+1 计算计算回代回代过程过程Step 5Step 6 for i=n-1,1 计算计算 Step 7 Output(系数矩阵奇异系数矩阵奇异);/*不成功不成功*/STOP.编程时此处调编程时此处调用用回代回代算法算法第59页例例4 4：用用Gauss列主元列主元消去法求解以下方程组消去法求解以下方程组解：解：首先写出首先写出增广矩阵增广矩阵第60页Step 1第61页消消 元元Step 2第62页消消 元元所求方程组解为所求方程组解为第63页