第一节：三角形方程组和三角分解

1、1第一章第一章 线性方程组的直接解法线性方程组的直接解法Dr. Zhang南昌大学理学院数学系E-mail: 1.1 三角形方程组和三角分解三角形方程组和三角分解上页上页 下页下页 返回返回 结束结束 2 如何利用电子计算机来快速、有效地求解线如何利用电子计算机来快速、有效地求解线性方程组的问题是数值线性代数研究的核心问题，性方程组的问题是数值线性代数研究的核心问题，而且也是目前仍在继续研究的重大课题之一。这而且也是目前仍在继续研究的重大课题之一。这是因为各种各样的科学与工程问题往往最终都要是因为各种各样的科学与工程问题往往最终都要归结为一个线性方程组的求解问题。例如结构分归结为一个线性方程组

2、的求解问题。例如结构分析、网络分析、大地测量、数据分析、最优化及析、网络分析、大地测量、数据分析、最优化及非线性方程组和微分方程组数值解等，都常遇到非线性方程组和微分方程组数值解等，都常遇到线性方程组的求解问题。线性方程组的求解问题。 线性方程组的求解问题是一个古老的数学问线性方程组的求解问题是一个古老的数学问题。早在中国古代的题。早在中国古代的九章算术九章算术中，就已详细中，就已详细地描述了解线性方程组的消元法。到了地描述了解线性方程组的消元法。到了19世纪初，世纪初，西方也有了西方也有了Gauss消去法，然后求解未知数多的消去法，然后求解未知数多的大型线性方程组则是在大型线性方程组则是在2

3、0世纪中叶电子计算机问世纪中叶电子计算机问世后才成为可能。世后才成为可能。上页上页 下页下页 返回返回 结束结束 3 求解线性方程组的数值方法大体上可分为求解线性方程组的数值方法大体上可分为直直接法接法和和迭代法迭代法两大类。两大类。 直接法直接法是指没有舍入误差的情况下经过有限是指没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法。因此，次运算可求得方程组的精确解的方法。因此，直接法又称为精确法。直接法又称为精确法。 迭代法迭代法则是采取逐次逼近的方法，亦即从一则是采取逐次逼近的方法，亦即从一个初始向量出发，按照一定的计算格式，构造个初始向量出发，按照一定的计算格式，构造一个向量的

4、无穷序列，其极限才是方程组的精一个向量的无穷序列，其极限才是方程组的精确解，只经过有限次运算得不到精确解。确解，只经过有限次运算得不到精确解。上页上页 下页下页 返回返回 结束结束 4 这一章，我们将主要介绍解线性方程组的一类这一章，我们将主要介绍解线性方程组的一类最基本的直接法最基本的直接法GaussGauss消去法消去法, , 其特点是其特点是 （1 1）求解）求解中小规模线性方程组中小规模线性方程组（即阶数不要（即阶数不要太高，例如不超过太高，例如不超过10001000）最常用的方法；）最常用的方法； （2 2）一般用于系数矩阵稠密（即矩阵的绝大）一般用于系数矩阵稠密（即矩阵的绝大多数元

5、素都是非零的）而又没有任何特殊结构多数元素都是非零的）而又没有任何特殊结构的线性方程组。的线性方程组。 如若系数矩阵具有某种特殊形式，则为了尽可如若系数矩阵具有某种特殊形式，则为了尽可能地减少计算量与存储量，需采用其他专门的能地减少计算量与存储量，需采用其他专门的方法来求解。方法来求解。51.1.1 三角形方程组的解法三角形方程组的解法1.1.3 三角分解的计算三角分解的计算1.1.2 Gauss变换变换1.1 三角形方程组和三角分解三角形方程组和三角分解 由于三角形方程组简单易于求解，而且它又是用分解方法解一般线性方程组的基础，所以我们首先考虑这种特殊类型的线性方程组的解法。上页上页 下页下

6、页 返回返回 结束结束 61.1.11.1.1三角形方程组的解法三角形方程组的解法 (1.1.1)下三角形方程组形如Lyb这里 是已知的， 是未知的，而 是已知的非奇异下三角阵，即1( ,)TnnbbbR1(,)TnnyyyRn nijLlR 112122313233123nnnnnlllLlllllll,其中其中 0,1,2,., .iilin上页上页 下页下页 返回返回 结束结束 7 我们容易得到方程组（我们容易得到方程组（1.1.11.1.1）的解）的解的分量表达式的分量表达式11,1,2, .iiiijjiijybl ylin 这种解方程组（1.1.1）的方法称之为前代法前代法.如果在

7、实际计算时将得到的 就存放在 所用的存储单元内，并适当调整一下运算顺序，可得如下算法：ibiy上页上页 下页下页 返回返回 结束结束 8算法算法1.1.11.1.1（解下三角形方程组：前代法）（解下三角形方程组：前代法）1:1( )( )/ ( , )(1: )(1: )( ) (1: , )( )( )/ ( , )for jnb jb jL j jb jnb jnb j L jn jendb nb nL n n 该算法所需要的加、减、乘、除运算的次数为：21(1)(21)22nin ninn即该算法的运算量为 。2n上页上页 下页下页 返回返回 结束结束 9注意：针对方程（注意：针对方程（

8、1.1.11.1.1）使用消元法，我们）使用消元法，我们能够得到另外一种程序。能够得到另外一种程序。算法分析如下：算法分析如下：第一步：对增广矩阵实施行初等变换，使之成为其中：其中： 显然地，上式右端是显然地，上式右端是与原方程组同解的一个方程组的增广矩阵。与原方程组同解的一个方程组的增广矩阵。(1)(1)(1)111111/,2,., .iiibblbbb lin上页上页 下页下页 返回返回 结束结束 10第第k步：消元工作如下步：消元工作如下上页上页 下页下页 返回返回 结束结束 11经经n-1步变换之后，我们将得到原方程组的如下同解步变换之后，我们将得到原方程组的如下同解方程：方程：其中

9、：其中： ( )(1)( )(1)( ),/,1, .kkkkkkkk kiiki kbblbbblikn(1)1(1)1(1),11nnnn nnbblb上页上页 下页下页 返回返回 结束结束 12最后，对第最后，对第n个方程做行初等变换，令个方程做行初等变换，令 我们便得到原方程组的一个最简形式的同解方程组：我们便得到原方程组的一个最简形式的同解方程组：( )(1),/,nnnnn nbbl,xb其中：其中： (1)(2)( )12(,) .nTnbbbb综合上述，我们得到如下算法程序：综合上述，我们得到如下算法程序：1:1( )( )/ ( , );1:( )( )( )* ( , );

10、( )( )/ ( , )for inb ib il i ifor jinb jb jb il j iendendb nb nl n n 上页上页 下页下页 返回返回 结束结束 13 (1.1.2)再考虑如下上三角形方程组再考虑如下上三角形方程组: Uxy其中其中 是非奇异上三角阵。是非奇异上三角阵。 ,n ni jUuR这一方程组可以用所谓的回代法解之，即从方程组这一方程组可以用所谓的回代法解之，即从方程组的最后一个方程出发依次求出的最后一个方程出发依次求出 ，其计，其计算公式为算公式为11,nnxxx1,1,1;niiijjiij ixyu xuin n 上页上页 下页下页 返回返回 结束

11、结束 14显然该算法的运算量也为 。2n算法算法1.1.21.1.2（解上三角形方程组：回代法）（解上三角形方程组：回代法）: 1:2( )( )/( , )(1:1)(1:1)( )*(1:1, )(1)(1)/(1,1)for jny jy jU j jyjyjy jUjjendyyU 上页上页 下页下页 返回返回 结束结束 15对于一般的线性方程组对于一般的线性方程组 （1.1.3）Axb其中其中 和和 是已知的，是已知的， 是未知的，如果是未知的，如果我们能够将我们能够将A分解为：分解为： ，即一个下三角阵，即一个下三角阵L与一与一个上三角阵个上三角阵U的乘积，那么原方程组的解的乘积，

12、那么原方程组的解x便可由下便可由下面两步得到：面两步得到：n nARnbRnxRALU(1) 用前代法解用前代法解 得得y； Lyb(2) 用回代法解用回代法解 得得x.Uxy所以对于求解一般的线性方程组来说，关键是如何所以对于求解一般的线性方程组来说，关键是如何将将A分解为一个下三角阵分解为一个下三角阵L与一个上三角阵与一个上三角阵U的乘积，的乘积，这正是我们本节的中心任务。这正是我们本节的中心任务。 返回161.1.2 Gauss变换变换 引理引理1 设 是两个单位下三角矩阵，则 仍是单位下三角矩阵。12,n nL LR12LL L 引理引理2 设 是两个上三角矩阵，则 仍是上三角矩阵 。

13、12,n nU UR12UU U定义定义1 设 ，那么以下的变换称为初等行（列）变换：m nAR第一种初等变换又称对换。互换的两行（列）；第二种初等变换又称倍乘。用中一个非零的数乘的某行（列）；第三种初等变换又称倍加。用中的一个数乘的某行（列）加到另外一行（列）。上页上页 下页下页 返回返回 结束结束 17引理引理3 设设 是一个初等矩阵，则方程组是一个初等矩阵，则方程组与方程组与方程组 同解。同解。n nPRPAxPbAxb 欲把一个给定的矩阵欲把一个给定的矩阵A分解为一个下三角阵分解为一个下三角阵L与一个上三角与一个上三角阵阵U的乘积，最自然的做法是通过一系列的初等变换，逐步将的乘积，最自

14、然的做法是通过一系列的初等变换，逐步将A约化为一个上三角阵，而又能保证这些变换的乘积是一个下约化为一个上三角阵，而又能保证这些变换的乘积是一个下三角矩阵。这可归结为：对于一个任意给定的向量三角矩阵。这可归结为：对于一个任意给定的向量 找一找一个尽可能简单的下三角矩阵，使经这一矩阵作用之后的第个尽可能简单的下三角矩阵，使经这一矩阵作用之后的第k+1至第至第n分量均为零。能够完成这一任务的最简单的下三角矩阵分量均为零。能够完成这一任务的最简单的下三角矩阵便是便是Gauss变换阵。变换阵。nxR上页上页 下页下页 返回返回 结束结束 18定义定义3 如下形式的初等下三角阵如下形式的初等下三角阵,Tk

15、nkkLIl e其中其中 即即1,(0,0,) ,Tkkknklll这种类型的初等单位下三角矩阵称作这种类型的初等单位下三角矩阵称作 Gauss 变换变换，而称向量而称向量 为为 Gauss 向量向量。kl1,1111kkkn kLll上页上页 下页下页 返回返回 结束结束 19命题命题1 对于一个给定的向量对于一个给定的向量 若若 ，取，取其中：其中：12( ,),Tnnxx xxR0kx 1,(0,0,) ,Tkkknklll,1, .iikkxliknx 则则Gauss变换：变换： 使使TknkkLIl e1( ,0,0) .TkkL xxx证明：由于证明：由于111,( ,) ,Tkk

16、kk kknk nkL xxxxx lxx l将将 代入，即得出结论。代入，即得出结论。iikkxlx上页上页 下页下页 返回返回 结束结束 20命题命题2 Gauss变换变换 的逆变换为的逆变换为kL1TknkkLIl e命题命题3 当当 时，则时，则pq(1),TTpqppqqL LIl el e11(2).TTpqppqqL LIl el e上页上页 下页下页 返回返回 结束结束 21 命题命题4 设设 ，则对，则对A施以指标为施以指标为k的的Gauss变换，变换，A 的前的前k行保持不变。行保持不变。n nAR则则,Tkke Aa111,()()kTTkkkkkkkkknnkkaaL

17、AIl eAAle Aalaal a从而从而证明证明 将将A按行分块，记为按行分块，记为121,(,.,),1,2,., .kkknnaaAaaakna 返回221.1.3 三角分解的计算三角分解的计算1.1.3.1 算法的理论分析算法的理论分析假定 ，三角分解是指分解 ，其中 为下三角矩阵， 为上三角矩阵。基于分解式的这种表达方式，有时亦称三角分解为LU分解。n nARALUn nLRn nUR下面我们来讨论怎样利用下面我们来讨论怎样利用Gauss变换来实现变换来实现A的三的三角分解。先来考察一个简单的例子。设角分解。先来考察一个简单的例子。设1472583610A上页上页 下页下页 返回返

18、回 结束结束 23 我们首先计算一个Gauss变换 使得 的第1列的后两个元素为0。由命题1和4容易得出1L1L A且1100210301L 11470360611L A然后再计算Gauss变换 使得 的第2列的最后一个元素为0，再由命题1和4得2L21()L L A上页上页 下页下页 返回返回 结束结束 242100010021L且且21147()036001L L A由命题由命题211121121,01,301021LL令令1211147()21,036321001LL LU上页上页 下页下页 返回返回 结束结束 25则有则有.ALU对于一般的对于一般的n阶矩阵阶矩阵A，在一定条件下在一定

19、条件下，我们也可以，我们也可以计算计算n-1个个Gauss变换变换 ，使得，使得 为为上三角矩阵上三角矩阵。11,nLL11nLL A(1)(1)(1)1112121(1)22,0kkkkkkAAALLL AA事实上，记事实上，记 ，并假定已求出，并假定已求出k-1个个Gauss变变换换 使得使得11,()n nkLLRkn(0)AA其中其中 是是k-1阶上三角阵，阶上三角阵， 为为 (1)11kA(1)22kA(1)(1)(1)22(1)(1)kkkkknkkknknnaaAaa上页上页 下页下页 返回返回 结束结束 26如果如果 ，则我们就又可以确定一个，则我们就又可以确定一个Gauss变

20、换变换 ，使，使得得 中第中第k列的最后列的最后n-k个元素为个元素为0。由前面所介绍的。由前面所介绍的Gauss变换可知，这样的变换可知，这样的 应为应为(1)0kkkakL(1)kkL AkLTknkkLIl e其中其中(1)1,(1)(0,0,) ,1, .kTikkkknkikkkkallllikna因为因为 ，故，故 是唯一确定的。对于这样确定的是唯一确定的。对于这样确定的 ，我们有我们有(1)0kkkakLkL上页上页 下页下页 返回返回 结束结束 27 其中其中 是是k阶上三角阵。从阶上三角阵。从k=1出发，如此进行出发，如此进行n-1步，步，最终所得矩阵最终所得矩阵 即为我们所

21、要求的上三角矩阵，则我们就即为我们所要求的上三角矩阵，则我们就已经实现了已经实现了A的上三角形约化。的上三角形约化。 若令若令( )11kA(1)nA则则.ALU注意到对注意到对 j i有有 , 从而从而0Tj ie l 上页上页 下页下页 返回返回 结束结束 28 由此可见，由此可见，L不仅是一个单位下三角矩阵，而且是非常不仅是一个单位下三角矩阵，而且是非常容易得到的。容易得到的。 即即L具有形式具有形式21121313212311 , ,.,011nnnnlLIl lllllll 通常称通常称Gauss消去过程中的消去过程中的 为主元。显然，当且仅当为主元。显然，当且仅当 均不为零时，算法

22、均不为零时，算法1.1.3才能进行到底。那才能进行到底。那么自然要问：给定的矩阵么自然要问：给定的矩阵A满足什么，才能保证所有主元均不满足什么，才能保证所有主元均不为零？这一问题可由下面定理回答。为零？这一问题可由下面定理回答。(1)kkka(1)(1,.,1)kkkakn上页上页 下页下页 返回返回 结束结束 29 定理定理1.1.1 主元主元 均不为零的充分与必要均不为零的充分与必要条件是条件是A的的i阶顺序主子阵阶顺序主子阵 都是非奇异的。都是非奇异的。(1)(1,., )iiiaik(1,., )iA ik 证明证明: 对对k用归纳法用归纳法. 当当k=1时，时， ，定理显然成立。，定

23、理显然成立。假定定理直至假定定理直至k-1成立成立, 下面只需证明下面只需证明“若若 非奇非奇异异, 则则 非奇异的充要条件是非奇异的充要条件是 ”即可即可. 由归纳法由归纳法假定知假定知 . 因此，因此，Gauss消去过程至少可消去过程至少可进行进行k-1步，即可得到步，即可得到k-1个个Gauss变换变换 ，使得，使得(0)111Aa11,kAAkA(1)0kkka(1)0(11)iiiaik 11,kLL（1.1.4） (1)(1)(1)1112121(1)220kkkkkkAAALLL AA其中其中 是对角元为是对角元为 的上三角阵。的上三角阵。 (1)11kA(1)(1,.,1)ii

24、iaik上页上页 下页下页 返回返回 结束结束 30由此可知由此可知 的的k阶顺序主子阵有如下形式阶顺序主子阵有如下形式(1)kA(1)11(1)*kkkkAa若将若将 的的k阶顺序主子阵分别记为阶顺序主子阵分别记为 ，则由（则由（1.1.4）及下三角阵的性质可知）及下三角阵的性质可知11,kLL11() ,()kkkLL(1)11121(1)*() ()()kkkkkkkkkkALLLAa注意到注意到 是单位下三角阵，由此立即得到是单位下三角阵，由此立即得到iL(1)(1)11detdet,kkkkkAaA从而有从而有 非奇异当且仅当非奇异当且仅当 。kA(1)0kkka上页上页 下页下页

25、返回返回 结束结束 31定理定理1.1.2 若若 的顺序主子阵的顺序主子阵 均非奇异，则存在唯一的单位下三角阵均非奇异，则存在唯一的单位下三角阵 和上三角和上三角阵阵 使得使得 。n nAR(1,.,1)k kkARknn nLRn nURALU上页上页 下页下页 返回返回 结束结束 321.1.3.2 算法的编程算法的编程 这种计算三角分解的方法称作Gauss消去法消去法。实际编程计实际编程计算时，我们还需要弄清的是：当算时，我们还需要弄清的是：当 作用于作用于 后，后， 的哪的哪些元素作了改变？以及作了怎样的改变？此外，些元素作了改变？以及作了怎样的改变？此外， 及及 的的元素又是怎样存储起来的？元素又是怎样存储起来的？因为kL(1)kA(1)kAkL( )kA( )(1)(1)(1)(1)(),kkTkkTkkkkkkAL AIl eAAl e A并注意到 是 的第k行