矩阵A的LU分解

本文主要目的是为了通过矩阵乘法实现矩阵A的分解。

1. 矩阵的逆矩阵

1.1 AB的逆矩阵

• 假设A,B矩阵都可逆
  $$A(B{B}^{-1})A^{-1}=I\text{\hspace{1em}(1)}$$
• 可得如下
  $$(AB)(B^{-1}{A}^{-1})=I\text{\hspace{1em}(2)}$$
• 所以当AB矩阵单独可逆下：
  $$(AB{)}^{-1}=B^{-1}{A}^{-1}\text{\hspace{1em}(3)}$$

1.2 转置矩阵

• 由于矩阵A满足如下条件
  $$A{A}^{-1}=I\text{\hspace{1em}(4)}$$
• 对等式两边进行转置如下：
  $$(A^{-1}{)}^T{A}^T=I^T=I\text{\hspace{1em}(5)}$$
• 由此可得如下：
  $$(A^T{)}^{-1}=(A^{-1}{)}^T\text{\hspace{1em}(6)}$$

2. 2X2矩阵A消元

假设矩阵A经过行与行之间的计算，可以得到上三角矩阵U ，可以简化成如下,
$$E_{21}=\left[\begin{array}{cc}1& 0\\ & \\ -4& 1\end{array}\right];A=\left[\begin{array}{cc}2& 1\\ & \\ 8& 7\end{array}\right];U=\left[\begin{array}{cc}2& 1\\ & \\ 0& 3\end{array}\right];\text{\hspace{1em}(7)}$$

$$E_{21}A=U\text{\hspace{1em}(8)}$$
$$\left[\begin{array}{cc}1& 0\\ & \\ -4& 1\end{array}\right]\left[\begin{array}{cc}2& 1\\ & \\ 8& 7\end{array}\right]=\left[\begin{array}{cc}2& 1\\ & \\ 0& 3\end{array}\right]\text{\hspace{1em}(9)}$$

• 可以将上式改成如下
  $$A=(E_{21}{)}^{-1}U=LU\text{\hspace{1em}(10)}$$
• $(E_{21}{)}^{-1}$可得如下：
  $$(E_{21}{)}^{-1}=\left[\begin{array}{cc}1& 0\\ & \\ 4& 1\end{array}\right]\text{\hspace{1em}(11)}$$
• 将U进行分解可得
  $$U=\left[\begin{array}{cc}2& 1\\ & \\ 0& 3\end{array}\right]=\left[\begin{array}{cc}2& 0\\ & \\ 0& 3\end{array}\right]\left[\begin{array}{cc}1& \frac{1}{2}\\ & \\ 0& 1\end{array}\right]\text{\hspace{1em}(12)}$$
• 综上所述可得如下：
  $$A=\left[\begin{array}{cc}2& 1\\ & \\ 8& 7\end{array}\right];L=\left[\begin{array}{cc}1& 0\\ & \\ 4& 1\end{array}\right];D=\left[\begin{array}{cc}2& 0\\ & \\ 0& 3\end{array}\right];U=\left[\begin{array}{cc}1& \frac{1}{2}\\ & \\ 0& 1\end{array}\right]\text{\hspace{1em}(13)}$$
• $A=LDU$
  $$\left[\begin{array}{cc}2& 1\\ & \\ 8& 7\end{array}\right]=\left[\begin{array}{cc}1& 0\\ & \\ 4& 1\end{array}\right]\left[\begin{array}{cc}2& 0\\ & \\ 0& 3\end{array}\right]\left[\begin{array}{cc}1& \frac{1}{2}\\ & \\ 0& 1\end{array}\right]\text{\hspace{1em}(14)}$$

3. 3X3矩阵A消元

• 同理假设有一个3X3矩阵，我们可以经过行变换来消元。
  $$E_{32}{E}_{31}{E}_{21}A=U\text{\hspace{1em}(15)}$$
• 求逆矩阵如下：
  $$L=(E_{21}{)}^{-1}(E_{31}{)}^{-1}(E_{32}{)}^{-1}\text{\hspace{1em}(16)}$$
  $$A=(E_{21}{)}^{-1}(E_{31}{)}^{-1}(E_{32}{)}^{-1}U\text{\hspace{1em}(17)}$$
• 假设如下矩阵：
  $$E_{21}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ -2& 1& 0\\ & & \\ 0& 0& 1\end{array}\right];E_{31}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ 0& 1& 0\\ & & \\ 0& 0& 1\end{array}\right];E_{32}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ 0& 1& 0\\ & & \\ 0& -5& 1\end{array}\right];\text{\hspace{1em}(18)}$$
  $$E_{3221}=E_{32}{E}_{21}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ -2& 1& 0\\ & & \\ 10& -5& 1\end{array}\right]\text{\hspace{1em}(19)}$$
  $$E_{21}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ -2& 1& 0\\ & & \\ 0& 0& 1\end{array}\right];\Rightarrow (E_{21}{)}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ 2& 1& 0\\ & & \\ 0& 0& 1\end{array}\right];\text{\hspace{1em}(20)}$$
  $$E_{32}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ 0& 1& 0\\ & & \\ 0& -5& 1\end{array}\right];\Rightarrow (E_{32}{)}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ 0& 1& 0\\ & & \\ 0& 5& 1\end{array}\right];\text{\hspace{1em}(20)}$$
  $$L=(E_{3221}{)}^{-1}=(E_{21}{)}^{-1}(E_{32}{)}^{-1}=\left[\begin{array}{ccc}1& 0& 0\\ & & \\ 2& 1& 0\\ & & \\ 0& 5& 1\end{array}\right];\text{\hspace{1em}(21)}$$
• 综上所述：
  $$A=LU\text{\hspace{1em}(22)}$$

4. 运算量

• 假设我们矩阵A是100X100的矩阵，那么将矩阵A通过行变换分解成A=LU 一共要进行如下计算步骤：
  $$Count=n^2+(n-1{)}^2+\cdots +2^2+1^2=\frac{1}{3}{n}^3=\frac{1000000}{3}\text{\hspace{1em}(23)}$$

5. 置换矩阵-左行右列

• 左乘置换矩阵-进行行变换XA
• 右乘置换矩阵-进行列变换AX
• 置换矩阵指的是一列中只有一个位置为1，同一列其他位置均为0,用来对矩阵进行位置交换。
• 第一行和第二行位置交换
  $$A=\left[\begin{array}{ccc}1& 2& 3\\ & & \\ 4& 5& 6\\ & & \\ 7& 8& 9\end{array}\right]\text{\hspace{1em}(24)}$$
  $$B=\left[\begin{array}{ccc}4& 5& 6\\ & & \\ 1& 2& 3\\ & & \\ 7& 8& 9\end{array}\right]=\left[\begin{array}{ccc}0& 1& 0\\ & & \\ 1& 0& 0\\ & & \\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}1& 2& 3\\ & & \\ 4& 5& 6\\ & & \\ 7& 8& 9\end{array}\right]\text{\hspace{1em}(25)}$$