线性代数之——A 的 LU 分解

2018-11-14 本文已影响19人 seniusen

1. A = LU

之前在消元的过程中，我们看到可以将矩阵 $A$ 变成一个上三角矩阵 $U$ ， $U$ 的对角线上就是主元。下面我们将这个过程反过来，通一个下三角矩阵 $L$ 我们可以从 $U$ 得到 $A$ ， $L$ 中的元素也就是乘数 $l_{ij}$ 。

如果有一个 3*3 的矩阵，假设不需要进行行交换，那我们需要三个消元矩阵 $E_{21}, E_{31}, E_{32}$ 来分别使矩阵 $A$ 的 (2, 1)、(3, 1) 和 (3, 2) 位置为零，然后我们就有

乘数 $l_{ij}$ 正好就是 $L$ 中 $(i, j)$ 处的元素。因为当我们计算 $U$ 的第三行的时候，实际上是用 $A$ 的第三行减去 $U$ 的前两行的一些倍数。

因此有

下面看一个特殊的例子

如果 $A$ 的某一行以 0 开始，说明该位置不需要进行消元，也即 $L$ 中对应位置的元素为 0。

如果 $A$ 的某一列以 0 开始，该位置元素在消元过程始终不会改变，也即 $U$ 中对应位置的元素为 0。

由于 $L$ 的对角线上都是 1，而 $U$ 的对角线上为主元，因此，这是不对称的。我们可以进一步将 $U$ 进行分解，使得 $U$ 的对角线上元素也都为 1。

这时候， $A$ 的分解就变成了 $A = LU = LDU$ ，其中 $D$ 是一个对角矩阵， $L$ 是一个下三角矩阵， $U$ 是一个上三角矩阵。

当我们从左边的 $A$ 得到 $L$ 和 $U$ 后，我们就对右边的 $b$ 进行同样的消元过程得到 $Lc = b$ ，然后再通过回带 $Ux=c$ 求出方程组的解。

2. 消元过程的计算复杂度

假设我们有一个 $n*n$ 的矩阵，首先我们要将第一列主元以下的元素都变成 $0$ 。这时候，每一个元素变成 $0$ 我们都需要 $n$ 次乘法和 $n$ 次减法，总共有 $n-1$ 个元素需要变成 $0$ ，总的乘法次数为 $n(n-1)$ ，近似为 $n^2$ 。然后，我们要依次将后面列的主元下面的元素变成 $0$ ，需要的总的乘法次数为 $n^2+(n-1)^2+\cdots + 2 + 1 \approx \frac{1}{3}n^3$ 。

也就是说对左边的 $A$ 消元要进行 $\frac{1}{3}n^3$ 次的乘法操作和 $\frac{1}{3}n^3$ 次的加法操作。

再来看右边对 $b$ 进行消元，首先我们需要将 $b_2, b_3 \cdots b_n$ 都减去 $b_1$ ，需要 $n-1$ 次操作，往后我们依次需要 $n-2, n-3 \cdots 1$ 次操作。回带的时候，求解最后一个方程的时候，我们只需要进行 1 次操作，依次往上我们需要 $2, 3 \cdots n$ 次操作。因此，求解的过程总共需要 $n^2$ 次的乘法操作和 $n^2$ 次的加法操作