复习线性代数：LU分解
参考资料:
清华大学数学科学系-线性代数-马辉
《工程数学 线性代数 第六版》 同济大学数学系 高等教育出版社
Linear Algebra by Gilbert Strang MIT麻省理工线性代数公开视频课
LU分解
回忆消元法的过程：利用初等行变换，方阵$A \longrightarrow$上三角矩阵$U$，使用矩阵语言：$E A=U$，$E$是初等矩阵乘积。
$A=E^{-1} U$，将矩阵$A$分解成一个下三角矩阵（lower triangular matrix）和一个上三角矩阵的乘积（upper triangular matrix），$U$为上三角矩阵，对角元为$A$的主元。$L$为下三角矩阵，对角元为$1$，乘数$l_{ij}$位于对角元下方。有时，可以把$U$写成$DU$的形式$A=LDU$，$D$是对角矩阵。
Gauss消元法的计算量
含乘除法次数：$\frac{n^{3}}{3}+n^{2}-\frac{n}{3} \approx \frac{n^{3}}{3}$
加减法次数：$\frac{n^{3}}{3}+\frac{n^{2}}{2}-\frac{5 n}{6} \approx \frac{n^{3}}{3}$
LU分解的存在性和唯一性
定理：设可逆矩阵$A$的顺序主子阵$A_{k}(k=1, \cdots, n)$均为可逆阵，则$A$有$LU$分解。
定理：设$n$阶可逆阵$A$有$A=LU$，其中$L$为下三角矩阵，$U$为上三角矩阵，且$l{i i}=1, u{i i} \neq 0(1 \leq i \leq n)$，则分解唯一。
证明：设可逆阵$A$有两个$LU$分解：$A=L{1} U{1}=L{2} U{2}$，则
为对角阵。因$L{1}, L{2}$的对角元为$1$，故$L{1}^{-1} L{2}$对角元全为$1$。故$L{1}^{-1} L{2}=U{1} U{2}^{-1}=I$，即$L{1}=L{2}, U{1}=U{2}$。
同理，设可逆矩阵$A=L D U$，则分解唯一。
对称矩阵的$L D L^{T}$分解
设可逆对称矩阵$A$不需换行，只通过消元能化成上三角矩阵$U$，即有$A=L D U$，则$A=A^{T}=U^{T} D L^{T}$。由$A=L D U$分解唯一性知$U=L^{T}$。故$A=L D L^{T}$。
置换矩阵permutation matrix
定义：单位矩阵行重排后得到的矩阵称为置换矩阵
共有$n!$个$n$阶置换阵
置换阵的逆还是置换阵，置换阵的乘积仍是置换阵
置换阵$P$满足$P^{-1}=P^{T}$
$P A=L U$分解
定理：设$A$是一个$n$阶可逆阵，则存在置换阵$P$，使得$P A=L U$。