线性代数方程组的解法详解演示文稿

线性代数方程组的解法详解演示文稿现在是1页\一共有59页\编辑于星期三（优选）线性代数方程组的解法现在是2页\一共有59页\编辑于星期三考虑上三角形方程组的计算公式为：现在是3页\一共有59页\编辑于星期三两种算法的工作量(加减乘除运算次数之和)均为现在是4页\一共有59页\编辑于星期三三角分解法的基本思想:记方程组可化为下面两个易求解的三角方程组设已知方程组系数矩阵的三角分解为其中,为下三角矩阵,为上三角矩阵.现在是5页\一共有59页\编辑于星期三二、高斯消去法设给定矩阵现在是6页\一共有59页\编辑于星期三forforforGauss消去法的消元过程算法endendend现在是7页\一共有59页\编辑于星期三LU分解求A的LU分解（L是下三角矩阵，U是上三角矩阵）现在是8页\一共有59页\编辑于星期三LU分解性质1

设向量且则存在唯一的下三角阵,满足证明：寻找满足条件的初等下三角阵记现在是9页\一共有59页\编辑于星期三写成分量形式：唯一确定性质2

现在是10页\一共有59页\编辑于星期三性质3现在是11页\一共有59页\编辑于星期三性质4若记,则有现在是12页\一共有59页\编辑于星期三即单位下三角阵可以分解为一系列初等下三角阵的乘积现在是13页\一共有59页\编辑于星期三三、三角分解的计算Gauss消去法设给定矩阵取Gauss变换矩阵则有现在是14页\一共有59页\编辑于星期三再取Gauss变换矩阵其中现在是15页\一共有59页\编辑于星期三设给定阶矩阵记Gauss消去法的矩阵表示令Step1：如果高斯变换现在是16页\一共有59页\编辑于星期三取其中记现在是17页\一共有59页\编辑于星期三类似地，对中的部分重复以上做法现在是18页\一共有59页\编辑于星期三Stepk：第k步消元过程的计算公式整个消元过程的矩阵表示上三角矩阵计算现在是19页\一共有59页\编辑于星期三现在是20页\一共有59页\编辑于星期三forforforGauss消去法的消元过程算法endendend现在是21页\一共有59页\编辑于星期三经过n-1次消元，并将存放在矩阵零元素位置现在是22页\一共有59页\编辑于星期三LU分解的计算过程:Step1Step2Step3Step4Step5Step6Step2n-1Step2(n-1)先计算的行再计算的列依次交替进行对方程组求解,只要得到了系数矩阵的三角分解形式,再利用前代算法和回代算法解两个三角方程组即得.现在是23页\一共有59页\编辑于星期三例1：用Gauss消去法求解下列方程组解：系数矩阵现在是24页\一共有59页\编辑于星期三现在是25页\一共有59页\编辑于星期三（Gauss消去法的实现条件）全不为零的充要条件是的各阶顺序主子式都不等于零，即证明：归纳法证明(对k归纳)现在是26页\一共有59页\编辑于星期三设直到k-1成立,只要证明非零时，非零的充要条件是即可。在归纳假设下，Gauss消去法可进行到第k-1步其中是对角元为的上三角矩阵矩阵的k阶主子式是上三角的现在是27页\一共有59页\编辑于星期三均为单位下三角矩阵其中因此，若矩阵的各阶顺序主子式均不为零，可以采用Gauss消元法进行三角分解。结论得证现在是28页\一共有59页\编辑于星期三若的顺序主子式

均非奇异,则存在唯一的单位下三角阵和上三角阵,满足（矩阵三角分解的一个充分条件)证明可参照定理3.1.1.现在是29页\一共有59页\编辑于星期三给定矩阵，如果满足：且时，则称为上半带宽为，下半带宽为的带状矩阵，称为带状方程组；如果，则称为的半带宽，并称之为等带宽方程组；为的总带宽。四、其他的三角分解如果矩阵可以分解为一个单位下三角阵和一个上三角阵的乘积，即，则称此分解为Doolittle分解;如果矩阵可以分解一个下三角阵和单位上三角阵

的乘积,则称此分解为Crout分解.现在是30页\一共有59页\编辑于星期三例如上半带宽为2，下半带宽为1总带宽为3现在是31页\一共有59页\编辑于星期三半带宽为t的等带状矩阵的一般形式:现在是32页\一共有59页\编辑于星期三（保带状结构定理）设为上半带宽为，下半带宽为的带状矩阵，且其顺序主子式，则

有唯一的三角分解，其中是下半带宽为的单位下三角阵，是上半带宽为的上三角阵。证明可根据前面讲过的三角分解公式保带状结构定理说明：矩阵的三角分解中，和带外元素为零，因此不必计算，且不必参加求和运算现在是33页\一共有59页\编辑于星期三三对角线性方程组的三对角算法（追赶法）三对角线性方程组其中现在是34页\一共有59页\编辑于星期三根据保带状结构定理，系数矩阵可作如下三角分解：现在是35页\一共有59页\编辑于星期三三对角矩阵分解的计算公式：现在是36页\一共有59页\编辑于星期三方程组求解的计算公式：

解方程组

解方程组“追”的过程“赶”的过程现在是37页\一共有59页\编辑于星期三追赶法实现的一个充分条件(补充)设为前述三对角矩阵，且满足下列条件：

则非奇异，且特殊情况：如果三对角矩阵为严格对角占优矩阵，则可以采用追赶法求解。现在是38页\一共有59页\编辑于星期三例2：用追赶法求解三对角方程组,其中:解：注意到本例并不满足定理’的条件,但仍然可以利用追赶法来求解.因此,定理’的条件仅是充分条件.现在是39页\一共有59页\编辑于星期三现在是40页\一共有59页\编辑于星期三求解方程组求解方程组现在是41页\一共有59页\编辑于星期三§3.2选主元三角分解选主元三角分解的思想三角分解过程中存在的问题Gauss消元法完成的条件是矩阵的各阶顺序主子式(n=1,2,…,n-1)均不为零.三角分解过程中的除法运算要求分母不能太小,否则将可能产生不稳定情况.选主元的目的就是为了完成消元且避免不稳定情况的发生现在是42页\一共有59页\编辑于星期三例3：在8位制计算机上解方程组要求用三角分解方法计算。8个解：小主元可能导致计算失败现在是43页\一共有59页\编辑于星期三交换方程组的两行8个现在是44页\一共有59页\编辑于星期三Gauss全主元三角分解法交换单位矩阵的第列(行)和第列(行)得到的矩(初等置换矩阵)阵,称之为初等置换矩阵.列列现在是45页\一共有59页\编辑于星期三Step1(k=1)：第1步选择主元寻求和满足然后交换矩阵的第行和行，第列和列设给定阶矩阵记然后按照前面讨论的方法进行三角分解.用矩阵表示:其中,为初等置换矩阵.现在是46页\一共有59页\编辑于星期三现在是47页\一共有59页\编辑于星期三现在是48页\一共有59页\编辑于星期三其中现在是49页\一共有59页\编辑于星期三第1步选主元完成后的计算公式:第1步选主元完成后的实际编程计算公式:对中右下角的矩阵重复以上做法即可.Stepk：第k(k=1,2,…,n-1)步选择主元寻求和满足现在是50页\一共有59页\编辑于星期三再按照前面讨论的方法进行三角分解.用矩阵表示整个过程:第k步选主元完成后的计算公式:然后交换矩阵的第行和行，第列和列现在是51页\一共有59页\编辑于星期三设上述过程可以进行到第r步终止,则有令则有结论:其中为上三角阵,为单位下三角阵,且它的第列对角线以下的元素是由构成的Gauss向量做相应的排列得到的,故的所有元素之模均不会超过1.结论具有什么意义?现在是52页\一共有59页\编辑于星期三令证明：则有下面利用归纳法证明具有如下形式:其中是所有元素模均小于1的阶单位下三角阵,是所有元素模均小于1的阶矩阵,表示阶单位矩阵.现在是53页\一共有59页\编辑于星期三k=1时结论显然成立.现假设对k-1上述结论成立,则其中是由交换了第1行和行得到的,且现在是54页\一共有59页\编辑于星期三Gauss全主元三角分解法求解方程组设已经得到三角分解式则原方程组等价于令则注意到的计算可在三角分解的过程中来完成Gauss全主元三角分解法存在的问题

选取主元的方法中计算量太大;

选取主元的过程中用到列变换,需要记录交换信息.现在是55页\一共有59页\编辑于星期三设，则存在排列矩阵

,以及单位下三角阵和上三角阵,使得而且的所有元素均满足,的非零对角元的个数正好等于矩阵的秩.(排列矩阵)有限个初等置换矩阵的乘积称之为排列矩阵.全主元Gauss消去法的算法见教材:算法3.2.1现在是56页\一共有59页\编辑于星期三Gauss列主元三角分解法Gauss列主元三角分解法与全主元三角分解法的区别就是在消元过程中只作行变换,这样即可以减少选择主元时的逻辑计算量,又可以避免记录交换信息.Stepk：第k(k=1,2,…,n-1)步选择主元寻求满足用矩阵表示整个过程:则有结论:现在是57页\一共有59页\编辑于星期三Gauss列主元三角分解法求解方程组设已经得到三角分解式则原方程组等价于令则注意到的计算仍在三角分解的过程中来完成教材中算法3.2.2为列主元Gauss消去法的算法现在是58页\一共有59页\编辑于星期三

算法:

Gauss