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

1第一章线性方程组的直接解法Dr.Zhang南昌大学理学院数学系E-mail:[e-mail]§1.1三角形方程组和三角分解上页下页返回结束2如何利用电子计算机来快速、有效地求解线性方程组的问题是数值线性代数研究的核心问题，而且也是目前仍在继续研究的重大课题之一。这是因为各种各样的科学与工程问题往往最终都要归结为一个线性方程组的求解问题。例如结构分析、网络分析、大地测量、数据分析、最优化及非线性方程组和微分方程组数值解等，都常遇到线性方程组的求解问题。线性方程组的求解问题是一个古老的数学问题。早在中国古代的《九章算术》中，就已详细地描述了解线性方程组的消元法。到了19世纪初，西方也有了Gauss消去法，然后求解未知数多的大型线性方程组则是在20世纪中叶电子计算机问世后才成为可能。上页下页返回结束3求解线性方程组的数值方法大体上可分为直接法和迭代法两大类。直接法是指没有舍入误差的情况下经过有限次运算可求得方程组的精确解的方法。因此，直接法又称为精确法。迭代法则是采取逐次逼近的方法，亦即从一个初始向量出发，按照一定的计算格式，构造一个向量的无穷序列，其极限才是方程组的精确解，只经过有限次运算得不到精确解。上页下页返回结束4这一章，我们将主要介绍解线性方程组的一类最基本的直接法—Gauss消去法,其特点是（1）求解中小规模线性方程组（即阶数不要太高，例如不超过1000）最常用的方法；（2）一般用于系数矩阵稠密（即矩阵的绝大多数元素都是非零的）而又没有任何特殊结构的线性方程组。如若系数矩阵具有某种特殊形式，则为了尽可能地减少计算量与存储量，需采用其他专门的方法来求解。51.1.1三角形方程组的解法1.1.3三角分解的计算1.1.2Gauss变换§1.1三角形方程组和三角分解由于三角形方程组简单易于求解，而且它又是用分解方法解一般线性方程组的基础，所以我们首先考虑这种特殊类型的线性方程组的解法。上页下页返回结束61.1.1三角形方程组的解法(1.1.1)下三角形方程组形如Lyb这里是已知的，是未知的，而是已知的非奇异下三角阵，即1(,,)TnnbbbR1(,,)TnnyyyRnnijLlR112122313233123nnnnnlllLlllllll,其中0,1,2,...,.iilin上页下页返回结束7我们容易得到方程组（1.1.1）的解的分量表达式11,1,2,,.iiiijjiijyblylin这种解方程组（1.1.1）的方法称之为前代法.如果在实际计算时将得到的就存放在所用的存储单元内，并适当调整一下运算顺序，可得如下算法：ibiy上页下页返回结束8算法1.1.1（解下三角形方程组：前代法）1:1()()/(,)(1:)(1:)()(1:,)()()/(,)forjnbjbjLjjbjnbjnbjLjnjendbnbnLnn该算法所需要的加、减、乘、除运算的次数为：21(1)(21)22ninninn即该算法的运算量为。2n上页下页返回结束9注意：针对方程（1.1.1）使用消元法，我们能够得到另外一种程序。算法分析如下：第一步：对增广矩阵实施行初等变换，使之成为其中：显然地，上式右端是与原方程组同解的一个方程组的增广矩阵。(1)(1)(1)111111/,,2,...,.iiibblbbblin上页下页返回结束10第k步：消元工作如下上页下页返回结束11经n-1步变换之后，我们将得到原方程组的如下同解方程：其中：()(1)()(1)(),,/,,1,,.kkkkkkkkkiikikbblbbblikn(1)1(1)1(1),11nnnnnnbblb上页下页返回结束12最后，对第n个方程做行初等变换，令我们便得到原方程组的一个最简形式的同解方程组：()(1),/,nnnnnnbbl,xb其中：(1)(2)()12(,,,).nTnbbbb综合上述，我们得到如下算法程序：1:1()()/(,);1:()()()*(,);()()/(,)forinbibiliiforjinbjbjbiljiendendbnbnlnn上页下页返回结束13(1.1.2)再考虑如下上三角形方程组:Uxy其中是非奇异上三角阵。,nnijUuR这一方程组可以用所谓的回代法解之，即从方程组的最后一个方程出发依次求出，其计算公式为11,,,nnxxx1,,1,,1;niiijjiijixyuxuinn上页下页返回结束14显然该算法的运算量也为。2n算法1.1.2（解上三角形方程组：回代法）:1:2()()/(,)(1:1)(1:1)()*(1:1,)(1)(1)/(1,1)forjnyjyjUjjyjyjyjUjjendyyU上页下页返回结束15对于一般的线性方程组（1.1.3）Axb其中和是已知的，是未知的，如果我们能够将A分解为：，即一个下三角阵L与一个上三角阵U的乘积，那么原方程组的解x便可由下面两步得到：nnARnbRnxRALU(1)用前代法解得y；Lyb(2)用回代法解得x.Uxy所以对于求解一般的线性方程组来说，关键是如何将A分解为一个下三角阵L与一个上三角阵U的乘积，这正是我们本节的中心任务。返回161.1.2Gauss变换引理1设是两个单位下三角矩阵，则仍是单位下三角矩阵。12,nnLLR12LLL引理2设是两个上三角矩阵，则仍是上三角矩阵。12,nnUUR12UUU定义1设，那么以下的变换称为初等行（列）变换：mnAR第一种初等变换又称对换。互换的两行（列）；第二种初等变换又称倍乘。用中一个非零的数乘的某行（列）；第三种初等变换又称倍加。用中的一个数乘的某行（列）加到另外一行（列）。上页下页返回结束17引理3设是一个初等矩阵，则方程组与方程组同解。nnPRPAxPbAxb欲把一个给定的矩阵A分解为一个下三角阵L与一个上三角阵U的乘积，最自然的做法是通过一系列的初等变换，逐步将A约化为一个上三角阵，而又能保证这些变换的乘积是一个下三角矩阵。这可归结为：对于一个任意给定的向量找一个尽可能简单的下三角矩阵，使经这一矩阵作用之后的第k+1至第n分量均为零。能够完成这一任务的最简单的下三角矩阵便是Gauss变换阵。nxR上页下页返回结束18定义3如下形式的初等下三角阵,TknkkLIle其中即1,(0,,0,,,),Tkkknklll这种类型的初等单位下三角矩阵称作Gauss变换，而称向量为Gauss向量。kl1,,1111kkknkLll上页下页返回结束19命题1对于一个给定的向量若，取其中：12(,,,),TnnxxxxR0kx1,(0,,0,,,),Tkkknklll,1,,.iikkxliknx则Gauss变换：使TknkkLIle1(,,,0,,0).TkkLxxx证明：由于111,(,,,,,),TkkkkkknknkLxxxxxlxxl将代入，即得出结论。iikkxlx上页下页返回结束20命题2Gauss变换的逆变换为kL1TknkkLIle命题3当时，则pq(1),TTpqppqqLLIlele11(2).TTpqppqqLLIlele上页下页返回结束21命题4设，则对A施以指标为k的Gauss变换，A的前k行保持不变。nnAR则,TkkeAa111,()()kTTkkkkkkkkknnkkaaLAIleAAleAalaala从而[证明]将A按行分块，记为121,(,...,),1,2,...,.kkknnaaAaaakna返回221.1.3三角分解的计算1.1.3.1算法的理论分析假定，三角分解是指分解，其中为下三角矩阵，为上三角矩阵。基于分解式的这种表达方式，有时亦称三角分解为LU分解。nnARALUnnLRnnUR下面我们来讨论怎样利用Gauss变换来实现A的三角分解。先来考察一个简单的例子。设1472583610A上页下页返回结束23我们首先计算一个Gauss变换使得的第1列的后两个元素为0。由命题1和4容易得出1L1LA且1100210301L11470360611LA然后再计算Gauss变换使得的第2列的最后一个元素为0，再由命题1和4得2L21()LLA上页下页返回结束242100010021L且21147()036001LLA由命题211121121,01,301021LL令1211147()21,036321001LLLU上页下页返回结束25则有.ALU对于一般的n阶矩阵A，在一定条件下，我们也可以计算n-1个Gauss变换，使得为上三角矩阵。11,,nLL11nLLA(1)(1)(1)1112121(1)22,0kkkkkkAAALLLAA事实上，记，并假定已求出k-1个Gauss变换使得11,,()nnkLLRkn(0)AA其中是k-1阶上三角阵，为(1)11kA(1)22kA(1)(1)(1)22(1)(1)kkkkknkkknknnaaAaa上页下页返回结束26如果，则我们就又可以确定一个Gauss变换，使得中第k列的最后n-k个元素为0。由前面所介绍的Gauss变换可知，这样的应为(1)0kkkakL(1)kkLAkLTknkkLIle其中(1)1,(1)(0,,0,,,),,1,,.kTikkkknkikkkkallllikna因为，故是唯一确定的。对于这样确定的，我们有(1)0kkkakLkL上页下页返回结束27其中是k阶上三角阵。从k=1出发，如此进行n-1步，最终所得矩阵即为我们所要求的上三角矩阵，则我们就已经实现了A的上三角形约化。若令()11kA(1)nA则.ALU注意到对ji有,从而0Tjiel上页下页返回结束28由此可见，L不仅是一个单位下三角矩阵，而且是非常容易得到的。即L具有形式21121313212311[,,...,,0]11nnnnlLIllllllll通常称Gauss消去过程中的为主元。显然，当且仅当均不为零时，算法1.1.3才能进行到底。那么自然要问：给定的矩阵A满足什么，才能保证所有主元均不为零？这一问题可由下面定理回答。(1)kkka(1)(1,...,1)kkkakn上页下页返回结束29定理1.1.1主元均不为零的充分与必要条件是A的i阶顺序主子阵都是非奇异的。(1)(1,...,)iiiaik(1,...,)iAik证明:对k用归纳法.当k=1时，，定理显然成立。假定定理直至k-1成立,下面只需证明“若非奇异,则非奇异的充要条件是”即可.由归纳法假定知.因此，Gauss消去过程至少可进行k-1步，即可得到k-1个Gauss变换，使得(0)111Aa11,,kAAkA(1)0kkka(1)0(11)iiiaik11,,kLL（1.1.4）(1)(1)(1)1112121(1)220kkkkkkAAALLLAA其中是对角元为的上