[科普中国]-三角分解法

基本介绍

若能通过正交变换，将系数矩阵A分解为A=LU，其中L是单位下三角矩阵(主对角线元素为1的下三角矩阵)，而U是上三角矩阵，则线性方程组Ax=b变为LUx=b，若令Ux=y，则线性方程组Ax=b的求解分为两个三角方程组的求解：

(1)求解Ly=b，得y；

(2)再求解Ux=y，即得方程组的解x；

因此三角分解法的关键问题在于系数矩阵A的LU分解。2

矩阵能LU分解的充分条件一般地，任给一个矩阵不一定有LU分解，下面给出一个矩阵能LU分解的充分条件。

定理1 对任意矩阵 ，若A的各阶顺序主子式均不为零，则A有唯一的Doolittle分解(或Crout分解)。

定理2 若矩阵 非奇异，且其LU分解存在，则A的LU分解是唯一的。2

矩阵A的Doolittle分解定义1 设 ，称A=LU，其中

为矩阵A的Doolittle分解(Doolittle factorization或Doolittle decomposition)。2

矩阵的Doolittle分解可以通过Gauss消去法或直接利用矩阵的乘法得到。

假设A的各阶顺序主子式均不为零，从Gauss消去法的消元过程可以看出，第一次消元时执行了n一1次初等行变换，若用矩阵的语言解释，相当于

其中

第二次消元时，相当于

其中

重复上述过程，经过n一1次消元，最后得到等价方程组：

其中

综上所述，得

而 为上三角矩阵，记 且

于是有

注上述过程中，若不假设A的各阶顺序主子式均不为零，只假设A非奇异，则Gauss消元过程未必能完全实施，一般需要选主元，然后进行初等行或列变换，以保证消元过程的进行．若用矩阵的语言解释，相当于对A左乘或右乘一个置换矩阵。

定理3 若A非奇异，则一定存在置换矩阵(permutation matrix)P，使得PA有三角分解PA=LU，其中L是单位下三角矩阵(主对角线元素为1的下三角矩阵)，而U是上三角矩阵。

由定理1知，存在矩阵P使得线性方程组PAx=Pb化为LUx=Pb，进而由

求得原方程组的解x。

若直接利用矩阵乘法，可设

由矩阵相等的定义，得L与U的递推计算公式如下：

(1) U的第一行、L的第一列的元素分别为

(2) 对 (依次：U的第二行，L的第二列，U的第三行，L的第三列……)，有

由上述两种方法得到矩阵A的LU分解后，求解Ly=b与Ux=y的计算公式为