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

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

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

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

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

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

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

解方程组

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

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

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

选取主元的过程中用到列变换,需要记录交换信息.当前第55页\共有59页\编于星期二\12点设，则存在排列矩阵

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

算法:

Ga