线性代数笔记（6）——LU 分解

线性代数笔记（6）——LU 分解

$LU$ 分解

分析

方阵 $A$ 需要可逆。（必要条件）

方阵$A \stackrel{初等行变换}{\longrightarrow}$ 上三角矩阵 $U$。

即 $EA = U$，$E$ 是一系列初等矩阵的乘积。

设只做“上面行的倍数加到下面行”的操作，$A$ 经 Gauss 消元法变为上三角阵。

则三阶下就是 $E \equiv E_{32} E_{31} E_{21}$。

消去矩阵为下三角矩阵，消去矩阵的逆、乘积均为下三角。

$L \equiv E^{-1}$ 容易计算，$E \equiv E_{32} E_{31} E_{21}$ 不易计算。

$L$ 是这样得到的：将消元的系数写在相应位置。

$$\begin{pmatrix} \mathbf{a_1} \\ \mathbf{a_2} \\ \mathbf{a_3} \end{pmatrix} = A = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix} U = \begin{pmatrix} 1 & 0 & 0 \\ l_{21} & 1 & 0 \\ l_{31} & l_{32} & 1 \end{pmatrix} \begin{pmatrix} \mathbf{u_1} \\ \mathbf{u_2} \\ \mathbf{u_3} \end{pmatrix} \Rightarrow \left\{ \begin{array}{l} \mathbf{a_1} = \mathbf{u_1} \\ \mathbf{a_2} = l_{21} \mathbf{u_1} + \mathbf{u_2} \\ \mathbf{a_3} = l_{31} \mathbf{u_1} + l_{32} \mathbf{u_2} + \mathbf{u_3} \end{array} \right.$$

定义

设 $A_{n \times n} = LU$，$A_{n \times n}$ 可逆，其中 $L$ 是对角元是 $1$ 的下三角阵，$U$ 是上三角阵。

$LDU$ 分解

$A = LU = LDU$，其中 $D$ 是一个对角阵，$U$ 是对角元是 $1$ 的上三角阵。

$$DU = \begin{pmatrix} d_1 & & \\ & \ddots & \\ & & d_n \end{pmatrix} \begin{pmatrix} 1 & * & * \\ & \ddots & * \\ & & 1 \end{pmatrix}$$
$D = \rm{diag}(d_1, d_2, \cdots, d_n)$ 。

用 $LU$ 分解解线性方程组

先解出 $L(U \mathbf{x}) = \mathbf{b}$（$L \mathbf{c} = \mathbf{b}$），再解出 $U \mathbf{x} = \mathbf{c}$。

两次解方程较为容易，只需要回代即可。

$LU$ 分解的存在性和唯一性

并非每个矩阵 $A$ 都有 $LU$ 分解，即使 $A$ 可逆。

比如：

$$\begin{pmatrix} 0 & 1 \\ 2 & 0 \end{pmatrix}$$
设 $A_k$ 是 $A$ 的左上角的 $k \times k$ 子矩阵，称为 $A$ 的 $k$ 阶顺序主子阵。

定理：设可逆矩阵 $A = (a_{ij})_{n\times n}$ 的顺序主子阵 $A_k = (a_{ij})_{k \times k}(k=1,\cdots,n)$ 均为可逆阵，则 $A$ 有 $LU$ 分解。

定理：设 $n$ 阶可逆阵 $A$ 有 $A = LU$，其中 $L$ 为下三角矩阵，$U$ 为上三角矩阵，且 $l_{ii} = 1,u_{ii} \not = 0(1 \le i \le n)$，则分解唯一。

同理，$A = LDU$ 的分解也唯一。

对称矩阵的 $LDL^T$ 分解

设 $A$ 是对称矩阵。

$LDU = A = A^T = (LDU)^T = U^T D L^T$，由 $LDU$ 分解唯一性知 $U = L^T$。

故 $A = LDL^T$。

置换矩阵

定义

一个 $n$ 元置换是 $1,2,\cdots,n$ 的一个排列，这诱导了 $n$ 阶单位矩阵“行”的一个重排，单位阵行重排后得到的矩阵称为置换阵。

性质

共有 $n!$ 个 $n$ 阶置换阵。

置换阵的逆还是置换阵，置换阵的乘积仍是置换阵。

置换阵 $P$ 满足 $P^{-1} = P^T$。

$PA = LU$ 分解

定理：设 $A$ 是一个 $n$ 阶可逆阵，则存在置换阵 $P$，使得 $PA = LU$。

 笔记 线性代数