Linear Algebra-矩阵的 LU 分解-04

概要

这一节首先完善之前讲到的逆矩阵内容，然后使用消元矩阵介绍 A 的 LU 分解，即将矩阵 A 分解为矩阵 L 与上三角矩阵 U，介绍这种运算的普遍规律。最后再一次提起之前介绍的“行交换矩阵”，引入置换矩阵的概念。

逆矩阵性质补充

首先考虑一个问题：如果 A，B 都是可逆矩阵的话，AB 的逆矩阵是什么呢？这个问题并不复杂，想求出逆矩阵，无非就是令 $AB\times(AB)^{-1}=I$ ，而我们不难想到 $ABB^{-1}A^{-1}=I$ ，因此有：

$(AB)^{-1}=B^{-1}A^{-1}$

由于下一章中要涉及到矩阵的转置问题，我们在这里一起讨论矩阵转置和矩阵的逆的关系。

首先介绍一下转置矩阵，转置矩阵就是将原矩阵各行转换为各列所得到的新矩阵，如：

$A=\begin{bmatrix} 1 & 2\\ 3 & 4\\ 4 & 1 \end{bmatrix},A^T=\begin{bmatrix} 1 & 3 & 4\\ 2 & 4 & 1 \end{bmatrix}$

接下来我们看看转置矩阵和逆矩阵有什么联系。说到逆矩阵，最经典的式子无非就是 $AA^{-1}=I$ 。为了找到转置矩阵 $A^T$ 与逆矩阵 $A^{-1}$ 间的关系，我们对 $AA^{-1}=I$ 两边同时进行转置运算，得到：

$(AA^{-1})^T=(A^{-1})^TA^T=I$

为什么 $(A^{-1})^T$ 会变换到 $A^T$ 的前面来呢？我们用非方阵 A 来理解一下这个过程，假设 A 是一个 $3\times 4$ 的矩阵，则A的右逆 $A^{-1}$ 是一个 $4\times 3$ 的矩阵，二者相乘是一个 $3\times 3$ 的单位矩阵。

对其求转置，如果 $A^T$ 在 $(A^{-1})^T$ 前面，则会得到一个 $4\times 4$ 的单位矩阵，矛盾。

再次观察此式： $(A^{-1})^TA^T=I$ ，由于 A 是方阵，则 $A^{T}$ 必然也是方阵，那么我们就能得到 $A^T$ 的逆矩阵，即为 $(A^{-1})^T$ ，也就是说： $(A^T)^{-1}=(A^{-1})^T$

这个结果告诉我们：对于单个矩阵，转置和取逆两个运算顺序可以颠倒。

矩阵的 LU 分解

我们熟悉的消元法都是直接使用行变换得来的，而由于消元矩阵的存在，说明用矩阵乘法也可以达到与之一样的消元效果。所以，现在假设有可逆矩阵 A，如果有： $A-初等行变换->U(上三角矩阵)$ ，就一定有类似于这样的形式： $E\times A=U$ 的等式存在，使 A 相当于进行了初等行变换成为了 U。而我们已经学习了逆矩阵，E 这样的矩阵一定有逆矩阵，因为它本身就是由单位阵变化过来的。所以 $E\times A=U$ 可以写成 $A=E^{-1}\times U$ 。这一形式即为 $A=LU$ 形式，这个过程就是 LU 分解过程。

那么矩阵 L(下三角矩阵)是否有什么特别之处呢？我们可以通过一道例题来探讨下：

【例】现有 $E_{32}E_{31}E_{21}A=U$ ，已知 $E_{32}=\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & -5 & 1\\ \end{bmatrix}$ ， $E_{21}=\begin{bmatrix} 1 & 0 & 0\\ -2 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix}$ ， $E_{31}=I$ ，求 $A=LU$ 分解后的 L。

思路：

逆矩阵化简为 $A=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}U$ ；
后面计算各个矩阵： $E_{21}^{-1}=\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix}$ ， $E_{32}^{-1}=\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 5 & 1\\ \end{bmatrix}$
直接带入计算： $L=E_{21}^{-1}E_{31}^{-1}E_{32}^{-1}=\begin{bmatrix} 1 & 0 & 0\\ 2 & 1 & 0\\ 0 & 5 & 1\\ \end{bmatrix}$

观察发现，L 具有一个非常重要的特点，L 矩阵中各个元素都是 $E_{21}^{-1}$ 与 $E_{32}^{-1}$ 中对应位置的元素。

以上的结论给了我们启示，在使用 $A=LU$ 分解矩阵的时候，我们只需要从 U 入手，反过来考虑：看如何通过行变换可以将上三角矩阵 U 变回 A，然后再将单位阵按此形式变化，就得到了 L 矩阵。这个性质也是 $A=LU$ 形式分解矩阵的最大优点。

LU 分解意义

对于线性方程组 $Ax = b$ ，当矩阵 A 可以进行 LU 分解 $A = LU$ 时，原方程组可转化为 $LUx = b$ 。令 $Ux = y$ ，则先求解 $Ly = b$ （因为 L 是下三角矩阵，求解相对容易，可通过前代法逐步计算），得到 y；再求解 $Ux = y$ （U 是上三角矩阵，可通过回代法求解），从而得到原方程组的解 x。相比于直接求解 $Ax = b$ ，这种方法在计算量上通常更具优势，尤其是对于大型矩阵，可显著减少计算量和计算时间。

运算量

以上，我们已经学会了 A=LU 分解矩阵方法，那么现在有一个额外问题，就是消元的运算量问题，比如现在我们有一个 $100\times 100$ 的大矩阵(无 0 元素)。我们需要运算(将一个数乘系数后加到另一数上消元，每一个这样的过程称为一次运算)多少次后，才能将其化为上三角矩阵呢？

这个问题我们先从列的角度进行考虑，第一列消元运算结束后，矩阵将会变成 $\begin{bmatrix} 1 & ... & ... & ...\\ 0 & ... & ... & ...\\ ... & ... & ... & ...\\ 0 & ... & ... & ...\\ \end{bmatrix}$ 的形式，这一步中，第一列的元素运算了100次，而第一行一共有100个元素，于是仅第一行与第一列的消元结束后，我们就运算了 $100^2$ 次。之后我们要研究的就变成了剩下的 $99\times 99$ 的矩阵。以此类推，最后的运算量为： $\sum_{k=1}^{n}k^2$

这种写法看上去比较难计算，我们可以根据微积分中学到的知识，加入我们计算的不是离散点之和，而是连续区域上函数的黎曼和的话，我们可以通过积分来计算区域面积值的和。我们可以采用积分来估计和，也就是这样估算： $\sum_{k=1}^{n}k^2=\int_{1}^{n}x^2dx$ 。

置换矩阵

我们之前接触过行变换所用到的矩阵，即是将单位阵 I 按照对应行变换方式进行操作之后得到的矩阵。它可以交换矩阵中的两行，代替矩阵行变换。什么时候我们需要使用矩阵行变换呢？一个经典的例子就是：在消元过程中，当矩阵主元位置上面为 0 时，我们就需要用行变换将主元位置换位非 0 数。

这样的由单位阵变换而来的矩阵，通过矩阵乘法可以使被乘矩阵行交换。我们将这样的矩阵称为置换矩阵 P。我们通过一个例子来熟悉一下置换矩阵。

【例】求矩阵 $\begin{bmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 1\\ \end{bmatrix}$ 的所有置换矩阵，并判断其性质。

一共有 6 个置换矩阵：

$\begin{bmatrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\\\end{bmatrix}\begin{bmatrix}0 & 1 & 0\\1 & 0 & 0\\0 & 0 & 1\\\end{bmatrix}\begin{bmatrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\\\end{bmatrix}\begin{bmatrix}0 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\\\end{bmatrix}\begin{bmatrix}0 & 0 & 1\\0 & 1 & 0\\1 & 0 & 0\\\end{bmatrix}\begin{bmatrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\\\end{bmatrix}$

这可以理解为一个群，很明显，我们任取两个矩阵相乘，结果仍在这个群中。