线性代数笔记(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$。

 

点赞 1

No Comments

Add your comment