http://note.youdao.com/noteshare?id=3da9c65bb3565de02d22c94202b812d5
A的LU分解
两个基础公式
1.假设A、B都是可逆矩阵，那么AB的逆矩阵是什么？
- AB的逆矩阵是
$B^{-1}A^{-1}$，即$(AB)(B^{-1}A^{-1})=I$ - 原因：由于
$AA^{-1} = I = A^{-1}A$和矩阵的结合律,我们可以得到$(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AIA^{-1} = AA^{-1} = I$。同理可得$(B^{-1}A^{-1}) (AB)= B(AA^{-1})B^{-1} = BIB^{-1} = BB^{-1} = I$,所以 AB 的逆矩阵是$B^{-1}A^{-1}$
2. A是可逆矩阵，那么A的转置矩阵$A^{T}$的逆矩阵是什么？
A的转置矩阵
$A^{T}$是A的逆矩阵的转置矩阵$(A^{-1})^{T}$-
什么是转置矩阵？
- 把A的横行写为
$A^{T}$的纵列，把A的纵列写为$A^{T}$的横行，得到的矩阵就是转置矩阵 - 例子：矩阵
$\begin{bmatrix} 1 & 3\\ 2 & 7 \end{bmatrix}$的转置矩阵是$\begin{bmatrix} 1 & 3\\ 2 & 4 \end{bmatrix}$ - 转置矩阵有一个性质：
$(AB)^{T}=B^{T}A^{T}$
- 把A的横行写为
原因：由于
$AA^{-1} = I$，那么将等式两边同时进行转置，得到$(AA^{-1})^{T}= I^{T}$,由于单位矩阵的转置是他本身。那么我们可以得到$(A^{-1})^{T}A^{T}= I$。同理$A^{T}(A^{-1})^{T}= I$。即$(A^{-1})^{T}A^{T}= I = A^{T}(A^{-1})^{T}$，换句话说就是，对于单个矩阵来说，转置和逆运算的顺序可以颠倒
什么是LU分解？
LU分解是一种消元的认知方法。
假设有可逆矩阵A可以进行消元，不需要进行行变换,主元也很好(没有0在主元的位置),最终通过消元得到了一个矩阵U。从A到U，这中间是如何联系起来的？A和U是什么关系？
- 这里我们引出一个矩阵L，它联系着A和U
首先考虑 2 x 2 消元的情形
- 假设矩阵A为
$\begin{bmatrix}2 & 1\\ 8 & 7 \end{bmatrix}$，这里我们应该使用4作为消元系数，最终得到的结果是$\begin{bmatrix}2 & 1\\ 0 & 3 \end{bmatrix}$，即$E_{21}$矩阵是$\begin{bmatrix}1 & 0\\ -4 & 1 \end{bmatrix}$，这里我们得到了一个等式
\begin{bmatrix}1 & 0\\ -4 & 1 \end{bmatrix}
\begin{bmatrix}2 & 1\\ 8 & 7 \end{bmatrix}
=
\begin{bmatrix}2 & 1\\ -4 & 1 \end{bmatrix}
E_{21}A=U
我们最终期望得到的等式是$A = LU$,即
\begin{bmatrix}2 & 1\\ 8 & 7 \end{bmatrix}
=
\begin{bmatrix} & \\ & \end{bmatrix}
\begin{bmatrix}2 & 1\\ 0 & 3 \end{bmatrix}
A = LU
那么，L和E是什么关系呢？
- 从之前的两个基础公式可以看到，它们是逆矩阵的关系，因为
$E_{21}A=U$两边同时乘以$(E_{21})^{-1}$，我们可以得到$(E_{21})^{-1}E_{21}A=(E_{21})^{-1}U$,即$A=(E_{21})^{-1}U$ - 所以，最终得到的L是消元矩阵
$E_{21}$的逆矩阵$\begin{bmatrix}1 & 0\\ 4 & 1 \end{bmatrix}$ - L的含义是什么？
- 在
$A = LU$中，U代表上三角[upper],L代表下三角[lower]
- 在
- 可以看到, L的对角线元素均为1，而U的对角线上均为主元
考虑 3 x 3 矩阵的情况
- 对于3 x 3矩阵A的消元运算，假设我们不需要行变换，一般来说有以下几步
- 在矩阵(2,1)的位置得到0。
$E_{21}A$ - 在矩阵(3,1)的位置得到0。
$E_{31}E_{21}A$ - 在矩阵(3,2)的位置得到0。
$E_{32}E_{31}E_{21}A$
- 在矩阵(2,1)的位置得到0。
最终我们得到了这样的结果：$E_{32}E_{31}E_{21}A = U$，而我们期望的是$A = LU$的形式，那么该如何变换呢？
- 首先消去
$E_{32}$：在等式两边同时乘以$E_{32}$的逆$(E_{32})^{-1}$,得到：$E_{31}E_{21}A =(E_{32})^{-1}U$ - 然后消去
$E_{31}$：同样的步骤得到$E_{21}A=(E_{31})^{-1}(E_{32})^{-1}U$ - 最后消去
$E_{21}$：同样的步骤得到$A=(E_{21})^{-1}(E_{31})^{-1}(E_{32})^{-1}U$
所以L就是$(E_{21})^{-1}(E_{31})^{-1}(E_{32})^{-1}$
问题
一个 N x N 矩阵,在实际的消元过程中需要多少次操作？
- 假设n是一个 100 x 100 矩阵，我们需要运算多少次之后，才能将其转化为上三角矩阵 U 呢？（一次运算的定义：将一行乘一定倍数后加到另一行上消元，这样的过程定义为一次运算）
- 第一列消元运算结束之后，我们得到了下面的矩阵：
\begin{bmatrix}1 & ... & ... & ... & ... \\ 0 & ... & ... & ... & ... \\ 0 & ... & ... & ... & ...\\ 0 & ... & ... & ... & ...\\ 0 & ... & ... & ... & ...\end{bmatrix}
第一列的元素共运算了100次，每行100个元素，于是第一行与第一列的消元结束后，我们共进行了$100^2$次运算。之后我们需要对下面的99x99的矩阵进行相同的消元运算，共 $99^2$次，这样依次进行下去，最终需要进行的运算次数是$100^2 + 99^2 + 98^2 + ... + 3^2 + 2^2 + 1^2 = \sum_{i=1}^{n} n^2$
置换矩阵
- 置换矩阵是一个方形二进制矩阵，它在每行和每列中只有一个1，而在其他地方则为0
- 我们之前接触过行变换所用到的矩阵，即是将单位阵 I 按照对应行变换方式进 行操作之后得到的矩阵。它可以交换矩阵中的两行，代替矩阵行变换
- 例如：在消元过程中，当矩阵主元 位置上面不是 1 时，我们就需要用行变换将主元位置换回 1
- 作用：由单位阵变换而来的矩阵，通过矩阵乘法可以使被乘矩阵行交换
- 列子：3x3的矩阵
$\begin{bmatrix}1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$的置换矩阵共有六个，
\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}
我们取任意两个矩阵相乘，结果仍旧在这六个矩阵中
推广到 n x n 矩阵，n 阶矩阵有 n！个置换矩阵，就是将单位矩阵 I 各行重新排列后所有可能的情况数量。
