直接三角分解法-数值计算方法

高斯消去法消元的一步等价于用一个单位下三角矩阵左乘前一步约化得到的矩阵。 先说明在消元过程中，系数矩阵A＝A（1）是如何经矩阵运算约化为上三角矩阵A（n）的。 设

施行第一步消元，得到

施行第二步消元，得到

如此下去，施行第n－1 步消元，得到

由此可见，在顺序高斯消去法的过程中，系数矩阵A ＝A（1）经过一系列单位下三角矩阵的左乘运算约化为上三角矩阵A（n），即

其中

记　

容易验证

则由式（7.11）知　

其中，L，U 分别为单位下三角矩阵和上三角矩阵。

总结上述讨论，得到下述重要定理。

定理7.2　（矩阵的LU 分解）　

设A∈Rn×n，如果A 的顺序主子式det（Ai）≠0，（i＝1，2，…，n－1），则A 可分解为一个单位下三角阵L 与一个上三角阵U 的乘积，即A＝LU，且分解是唯一的。

证　根据以上对高斯消去法的矩阵分析，A ＝LU 的存在性已经得到证明。 下面证明唯一性。(www.xing528.com)

对于A 为奇异矩阵的情形请读者自己证明。

称矩阵的三角分解A＝LU 为杜利特尔（Doolittle）分解。 杜利特尔分解算法如下：

对于i＝1，2，…，n，

①计算U 的第i 行k 列元素，即对于k ＝i，i＋1，…，n，计算

②计算L 的第i 列k 行元素，即对于k ＝i＋1，…，n，计算

在上述算法中，对于固定的i，当uik算出时，aik在计算中不再出现，因此把uik存贮在aik的位置；当计算出lki后，aki也不再需要了，将lki存贮在aki的位置。 因此实现LU 分解后，矩阵A的元素分别换成了L 或U 的元素，即

所以矩阵的三角分解过程无须增加新的存贮。

注：①在定理7.2 条件下，同样可有三角分解A＝LU，其中L，U 分别为下三角矩阵和单位上三角矩阵。 称矩阵的这种分解为克劳特（Crout）分解。

③采用列主元素消去法时，只需进行行交换就可将消元法进行到底。 这样，在矩阵的三角分解中可以去掉定理7.2 中关于顺序主子式非奇异的限制。 我们可以证明下面的定理7.3。

定理7.3　设矩阵A∈Rn×n非奇异，则存在置换矩阵P，使得PA 被分解为一个单位下三角阵L 与一个上三角阵U 的乘积，即PA＝LU。

例7.4　利用三角分解方法解方程组

解　进行三角分解A＝LU