第四讲：$A$ 的 $LU$ 分解

$AB$的逆矩阵：

$$\begin{array}{rl}A\cdot A^{-1}=I& =A^{-1}\cdot A\\ (AB)\cdot (B^{-1}{A}^{-1})& =I\\ \text{则}AB\text{的逆矩阵为}& B^{-1}{A}^{-1}\end{array}$$

$A^T$的逆矩阵：

$$\begin{array}{rl}(A\cdot A^{-1}{)}^T& =I^T\\ (A^{-1}{)}^T\cdot A^T& =I\\ \text{则}{A}^T\text{的逆矩阵为}& (A^{-1}{)}^T\end{array}$$

将一个 $n$ 阶方阵 $A$ 变换为 $LU$ 需要的计算量估计：

1. 第一步，将$a_{11}$作为主元，需要的运算量约为$n^2$

$$\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ a_{21}& a_{22}& \cdots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{n1}& a_{n2}& \cdots & a_{nn}\end{array}\right]\underrightarrow{\mathrm{消}\mathrm{元}}\left[\begin{array}{cccc}{a}_{11}& a_{12}& \cdots & a_{1n}\\ 0& a_{22}& \cdots & a_{2n}\\ 0& ⋮& \ddots & ⋮\\ 0& a_{n2}& \cdots & a_{nn}\end{array}\right]$$

2. 以此类推，接下来每一步计算量约为$(n-1{)}^2、(n-2{)}^2、\cdots 、2^2、1^2$。

3. 则将 $A$ 变换为 $LU$ 的总运算量应为$O(n^2+(n-1{)}^2+\cdots +2^2+1^2)$，即$O(\frac{n^3}{3})$。

置换矩阵(Permutation Matrix)：

3阶方阵的置换矩阵有6个：

$$\left[\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}0& 1& 0\\ 1& 0& 0\\ 0& 0& 1\end{array}\right]\left[\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\right]\left[\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 1& 0& 0\end{array}\right]\left[\begin{array}{ccc}0& 0& 1\\ 1& 0& 0\\ 0& 1& 0\end{array}\right]$$

$n$阶方阵的置换矩阵有$(\genfrac{}{}{0ex}{}{n}{1})=n!$个。