1、 三角分解法也是直接法，基本思想是：三角分解法也是直接法，基本思想是：将系数矩阵将系数矩阵A分解为两个三角形矩阵分解为两个三角形矩阵L和和U的的乘积乘积A=LU，将方程组，将方程组AX=b的求解问题归结为的求解问题归结为两个三角形方程组两个三角形方程组 LY=b与与UX=Y的求解问题。的求解问题。即：先由即：先由LY=b求出求出Y，然后由，然后由UX=Y求出求出X，从而获得从而获得AX=b的解。的解。2 直接三角分解法直接三角分解法 (1)A为一般稠密（零元素占很小比例）矩阵为一般稠密（零元素占很小比例）矩阵的的杜利特尔杜利特尔(Doolittlr)和克劳特和克劳特(Crout)分解法；分解法
2、；(2)A为三对角的追赶法。为三对角的追赶法。把一个把一个n阶矩阵阶矩阵A分解成两个三角形矩阵相分解成两个三角形矩阵相乘的形式称为矩阵的三角分解。乘的形式称为矩阵的三角分解。1 Doolittle分解法和分解法和Crout 分解法分解法A=LU，其中，其中L为下三角阵，为下三角阵，U为上三角阵。为上三角阵。若若U为单位上三角阵为单位上三角阵(对角元都是对角元都是1 1的上三角阵的上三角阵),L L为单位下三角阵为单位下三角阵,则称为则称为克劳特克劳特(Crout)分解分解。矩阵三角分解的常见形式是：矩阵三角分解的常见形式是：作为特例，若作为特例，若L为单位下三角阵为单位下三角阵(对角元都是对角
3、元都是1 1的下三角阵的下三角阵),U为上三角阵，则称为为上三角阵，则称为杜利特尔杜利特尔(Doolittle)分解分解；下面分析实现矩阵杜利特尔下面分析实现矩阵杜利特尔(Doolittle)分解和克分解和克劳特劳特(Crout)分解的条件分解的条件,讨论这些分解的唯一性。讨论这些分解的唯一性。定理定理2 (2 (矩阵三角分解基本定矩阵三角分解基本定 理理)n nAR则存在唯一的杜利特尔分解则存在唯一的杜利特尔分解A=LU，其中，其中L 为单位下三角阵，为单位下三角阵，U 为非奇异上三角阵。为非奇异上三角阵。det()0kA(1,2,)kn设设 。若。若A的顺序的顺序主子式主子式 还可以证明存
4、在唯一的克劳特还可以证明存在唯一的克劳特Crout分解分解ALU这里这里L为非奇异下三角阵，为非奇异下三角阵，U为单位上三角阵。为单位上三角阵。如果如果A是一般非奇异阵，由列主消元法，是一般非奇异阵，由列主消元法，A适适当行交换后，可使当行交换后，可使A的各阶顺序主子式的各阶顺序主子式 ，从而实现杜利特尔从而实现杜利特尔Doolittle或克劳特或克劳特Crout分解。分解。det()0kA设方程组设方程组AX=b的系数矩阵的各阶顺序主子式的系数矩阵的各阶顺序主子式det()0kA(1,2,)kn，则存在唯一杜利特尔分解，则存在唯一杜利特尔分解ALU，其中，其中2131321231111nnn
5、lLlllll 11121222nnnnuuuuuUu 杜利特尔杜利特尔Doolittle分解法分解法下面介绍直接根据下面介绍直接根据A的元素计算的元素计算L、U元素的分解方法元素的分解方法由矩阵乘法规则与相等条件由矩阵乘法规则与相等条件,ijaijliju第一步第一步求求U的第一行元素和的第一行元素和L的第一列元素的第一列元素第二步第二步求求U的第二行元素和的第二行元素和L的第二列元素的第二列元素.对那些明确是对那些明确是1或是或是0的元素不再求。的元素不再求。导出计算导出计算 或或 的公式。的公式。利用利用 在上述计算过程中，在上述计算过程中，第一步第一步计算由计算由 得得11iiau11
6、iiua(1,2,)in11 11iial u1111/iilau(2,3,)in第二步第二步计算计算由由 得得221 12iiial uu2221 1iiiual u(2,3,)in21 122 22iiial ul u221 1222()/iiilal uu(3,4,)in（1）由由 得得由由 得得（2）例如例如第第k步计算步计算U的第的第k行行L的第的第k列元素的公式为：列元素的公式为：11(,1,)kkikikjjijual uik kn11()/(1,;)kikikijjkkkjlal uuikn kn 在我们利用杜利特尔矩阵分解解线性方程在我们利用杜利特尔矩阵分解解线性方程组组AX
7、=b时时,只要实现矩阵分解只要实现矩阵分解A=LU,依次解三角依次解三角形方程组形方程组LY=b与与UX=Y即可。即可。（3）（4）1111(2,3,)kkkkjjjybybl ykn1/()/(1,2,1)nnnnnkkkj jkkj kxy uxyu x uk nn （6）（5）计算公式：计算公式：杜利特尔矩阵分解杜利特尔矩阵分解求解线性方程组的求解线性方程组的过程为过程为:10 实现实现A=LU分解，即分解，即(a)按计算公式按计算公式(1),(2)依次计算依次计算U的第的第1行元素行元素 与与L的第的第1列元素列元素1(1,2,)iuin1(2,3,)ilin(,1,)kiui k k
8、n(1,;)iklikn kn (b)对对k+2,3,n 按计算公式按计算公式(3),(4)依次依次计算计算U的第的第k行元素行元素 与与L的第的第k列元素列元素20 求解三角形方程组求解三角形方程组LY=b，即按计算公即按计算公式式(5)依次计算依次计算12,ny yy30 求解三角形方程组求解三角形方程组UX=Y，即按计算公即按计算公式式(6)依次计算依次计算11,nnx xx为便于记忆，我们给出为便于记忆，我们给出L、U分解紧凑格式分解紧凑格式:在解方程组时在解方程组时,对于右端项对于右端项b也可不必经也可不必经过中间过程而按紧凑格式的方法直接得出过中间过程而按紧凑格式的方法直接得出y，
9、因为因为Ly=b，所以，所以1111(2,3,)kkkkqqqybybl ykn 它与公式（它与公式（3）相似。若将）相似。若将b作为增广矩阵的最作为增广矩阵的最后一列元素后一列元素,那么对增广矩阵作那么对增广矩阵作LU分解分解,b也作相应也作相应运算运算,仍在最后一列仍在最后一列,则分解后的最后一列即为则分解后的最后一列即为y。于是于是11(,1,1)kkjkikjjijual uik kn n 例例3：将方程组：将方程组1231231231233151831526xxxxxxxxx解：增广矩阵为解：增广矩阵为1233 151831151216的系数矩阵作的系数矩阵作LU分解，并求方程组的解
10、。分解，并求方程组的解。LU分解的紧凑格式为分解的紧凑格式为1233153371522221716161263所以系数矩阵所以系数矩阵的三角分解为的三角分解为100123333710022217161001263A 等价的三角方程组为等价的三角方程组为123123315371522216163xxx用回代法解得用回代法解得 3213,2,1xxx11112222211111nnnnnnnnnbcxfabcxfabcxfabxf 4 追赶法求解三对角线性方程组追赶法求解三对角线性方程组 在样条函数的计算、微分方程数值求在样条函数的计算、微分方程数值求解中常遇到如下形式的线性代数方程组：解中常遇到
11、如下形式的线性代数方程组：其中方程组其中方程组AX=f 的系数矩阵的系数矩阵A的元素满足条件：的元素满足条件：1100iiinnbcbacba 且且0iiac(2,3,1)in（1）根据系数矩阵根据系数矩阵A的特点，设的特点，设112221111111nnnnnALU 其中其中 为待定系数。比较为待定系数。比较A与与LU对应对应的元素，有的元素，有,iii 111111,(2,3,)(2,3,)(2,3,1)iiiiiiiiibcainbincin （2）由（由（1）和（）和（2）可以看出）可以看出1110abc因此有因此有 1111/01ca且由由 22212212220abababac有有
12、 2222/01ca且一般地，用归纳法可以证明一般地，用归纳法可以证明0iiac01i（即）(1,2,1)in因此我们从关系式（因此我们从关系式（2）解出待定系数为）解出待定系数为111111(2,3,)/(2,3,)iiiiiiiiibaincbain（3）由以上推导过程知，方程组由以上推导过程知，方程组AX=f 有唯一解有唯一解由（由（3）式可得计算）式可得计算 的递推公式的递推公式i1111/()(2,3,1)iiiiicbcbainiii,iia bi（4）只要计算出只要计算出 ，其它待定系数，其它待定系数 与与 均可均可通过已知数通过已知数 与与 表示。表示。上述解方程组上述解方程组
13、 AX=f 的过程归纳为：的过程归纳为：10 实现实现A=LU分解分解,按递推公式按递推公式(4)计算计算121,n 20 求解方程组求解方程组 LY=f ,相应的递推公式是相应的递推公式是11111/()/()(2,3,)iiiiiiiyf byfaybain（5）30 求解方程组求解方程组 UX=Y ,相应的递推公式是相应的递推公式是1(1,2,2,1)nniiiixyxyxinn （6）计算计算 及及 的过程的过程121n12nyyy称为追的过程，计算方程组的解称为追的过程，计算方程组的解 的过程称为赶的过程，因此上述方法称为追赶法。的过程称为赶的过程，因此上述方法称为追赶法。11nnx
14、xx例例4：用追赶法解方程组：用追赶法解方程组12342100111220220110022200012xxxx 解：按递推公式（解：按递推公式（4）计算）计算 得得123,123127,2726按递推公式（按递推公式（5）计算）计算(1,2,3,4)iy i 得得12341111,4145290yyyy 按递推公式（按递推公式（6）计算）计算 得得(4,3,2,1)ix i 432111713,90459045xxxx 用追赶法解方程组用追赶法解方程组 AX=f 仅需仅需 5n-4 次乘除次乘除法运算法运算,计算过程稳定。计算过程稳定。练习：练习：1、利用、利用LU分解求解四元线性方程组分解求解四元线性方程组AX=b，其中其中0174,3231532223522121bA2、用追赶法求方程组的解、用追赶法求方程组的解344341001410014100144321xxxx
