4.1 矩阵的三角分解

高等工程数学 讲义 2021

---

---

内容回顾

• 方阵的两个重要分解：
  
  1. 相似对角化 $\boldsymbol{A}=\boldsymbol{P} \operatorname{diag}\left\{\lambda_{1}, \lambda_{2}, \cdots, \lambda_{n}\right\} \boldsymbol{P}^{-1}$
  2. Jordan 标准型 $\boldsymbol{A}=\boldsymbol{P} \operatorname{diag}\left\{\boldsymbol{J}_{1}, \boldsymbol{J}_{2}, \cdots, \boldsymbol{J}_{s}\right\} \boldsymbol{P}^{-1}$
• 手段：把矩阵分解为形式或性质比较简单的若干个矩阵的乘积
• 目的：
  
  1. 更加清晰地刻画原矩阵的某些特征
  2. 为进一步的理论分析和数值计算奠定基础

---

三角矩阵

• 上三角阵 $\left[\begin{array}{ccc}{a_{11}} & {\cdots} & {a_{1 n}} \\ {} & {\ddots} & {\vdots} \\ {} & {} & {a_{n n}}\end{array}\right]$
• 单位上三角阵 $\left[\begin{array}{llll}{1} & {*} & {\cdots} & {*} \\ {} & {\ddots} & {\ddots} & {\vdots} \\ {} & {} & {\ddots} & {*} \\ {} & {} & {} & {1}\end{array}\right]$

---

上(下)三角阵的性质

1. 上(下)三角阵的和、差、乘积、逆仍是上(下)三角阵

2. 单位上(下)三角阵的乘积、逆仍为单位上(下)三角阵

   • 系数矩阵 $\boldsymbol{A}$ 为三角阵时，非齐次线性方程组 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ 比较容易求解

---

4.1.1 三角分解

若方阵 $\boldsymbol{A}$ 可写为

$$\boldsymbol{A}=\boldsymbol{LR},$$

其中 $\boldsymbol{L}$ 是单位下三角阵， $\boldsymbol{R}$ 是上三角阵，则称 $\boldsymbol{A}$ 可 三角分解（或 LR分解， Doolittle分解，LU分解）

---

LR分解的应用

若方阵 $\boldsymbol{A}$ 有三角分解 $\boldsymbol{A}=\boldsymbol{LR}$， 令

$$\boldsymbol{R}\boldsymbol{x}=\boldsymbol{y},$$

则可考虑非齐次线性方程组 $\boldsymbol{Ax}=\boldsymbol{b}$ 可分解为两个非齐次线性方程组

1. 前推方程组： $\boldsymbol{L}\boldsymbol{y}=\boldsymbol{b}$

2. 后退方程组： $\boldsymbol{R}\boldsymbol{x}=\boldsymbol{y}$

   • 利用三角矩阵的特性可以大大减少原方程组求解的计算量

---

前推方程组

$$\boldsymbol{L}\boldsymbol{y}=\boldsymbol{b}$$

即

$$\left[\begin{array}{cccc}{1} & {} & {} & {} \\ {l_{21}} & {1} & {} & {} \\ {\vdots} & {\ddots} & {\ddots} & {} \\ {l_{n 1}} & {\cdots} & {l_{n, n-1}} & {1}\end{array}\right]\left[\begin{array}{c}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{n}}\end{array}\right]=\left[\begin{array}{c}{b_{1}} \\ {b_{2}} \\ {\vdots} \\ {b_{n}}\end{array}\right]$$

按照 $y_{1} \Rightarrow y_{2} \Rightarrow \cdots \Rightarrow y_{n}$ 的次序进行求解

---

后退方程组

$$\boldsymbol{R}\boldsymbol{x}=\boldsymbol{y}$$

即

$$\left[\begin{array}{cccc}{r_{11}} & {r_{12}} & {\cdots} & {r_{1 n}} \\ {} & {r_{22}} & {\ddots} & {r_{2 n}} \\ {} & {} & {\ddots} & {\vdots} \\ {} & {} & {} & {r_{n n}}\end{array}\right]\left[\begin{array}{c}{x_{1}} \\ {x_{2}} \\ {\vdots} \\ {x_{n}}\end{array}\right]=\left[\begin{array}{c}{y_{1}} \\ {y_{2}} \\ {\vdots} \\ {y_{n}}\end{array}\right]$$

按照 $x_{n} \Rightarrow x_{n-1} \Rightarrow \cdots \Rightarrow x_{1}$ 的次序进行求解

---

LR 分解的存在性

• 例 讨论方阵 $\boldsymbol{A}=\left[\begin{array}{ll}{0} & {1} \\ {1} & {0}\end{array}\right]$ 的 LR 分解.
• 分析：设 $\boldsymbol{A}=\left[\begin{array}{c}1& \\ l_{21} & 1\end{array}\right]\left[\begin{array}{c} r_{11} & r_{12} \\ & r_{22}\end{array}\right]$
• 容易求得：$r_{11}=0,r_{12}=1$
• 注意到 $l_{21}r_{11}=1$
• 因为 $r_{11}=0$，故 $l_{21}$ 无解！
• 不是任何方阵都有 LR 分解！

---

定理 $n$ 阶可逆方阵 $\boldsymbol{A}$ 有唯一的 LR 分解，当且仅当 $\boldsymbol{A}$ 的前 $n-1$ 阶顺序主子式

$$\Delta_k\ne0\quad (k=1,2,\ldots,n-1).$$

• 注：$\Delta_k=\left|\begin{array}{c}a_{11} & a_{12} & \ldots & a_{1k}\\ a_{21} & a_{22} & \dots & a_{2k}\\ \vdots & \vdots & \ddots & \vdots \\ a_{k1} & a_{k2} & \ldots & a_{kk}\end{array}\right|$

---

证明充分性： 设 $\boldsymbol{A}$ 的顺序主子式 $\Delta_k\ne0\;(k=1,2,\ldots,n-1)$ .

• 设 $\boldsymbol{A}=\left[a_{ij}\right]_{n\times n}$ ，对 $[\boldsymbol{A}\;\;\boldsymbol{I}]$ 进行不包含行交换的初等行变换，将其中的 $\boldsymbol{A}$ 化为上三角阵.

• 因为 $\Delta_1=a_{11}\ne0$ ，所以有

  • $[A\;|\; I]=\left[\begin{array}{cccccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} & {|} & 1 \\ {a_{21}} & {a_{22}} & {\cdots} & {a_{2 n}} & {|} & & {1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {|} & & & {\ddots} \\ {a_{n 1}} & {a_{n 2}} & {\cdots} & {a_{n n}} & {|} & && &{1}\end{array}\right]$
  • $\to\left[\begin{array}{cccccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} & {|} & {1} \\ {0} & {a_{22}^{(1)}} & {\cdots} & {a_{2 n}^{(1)}} & {|} &{-\frac{a_{21}}{a_{11}}} & {1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {|} & \vdots & & {\ddots} \\ {0} & {a_{n 2}^{(1)}} & {\cdots} & {a_{n n}^{(1)}} & {|} & {-\frac{a_{n 1}}{a_{11}}} & & &{1}\end{array}\right]$

---

• 因为 $\Delta_{2}=a_{11} a_{22}-a_{12} a_{21} \neq 0$，
• 所以 $a_{22}^{(1)}=a_{22}-a_{12} \times \frac{a_{21}}{a_{11}} \neq 0$.
• 进而由 $\left[\begin{array}{cccccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} & {|} & {1} \\ {0} & {a_{22}^{(1)}} & {\cdots} & {a_{2 n}^{(1)}} & {|} &{-\frac{a_{21}}{a_{11}}} & {1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {|} & \vdots & & {\ddots} \\ {0} & {a_{n 2}^{(1)}} & {\cdots} & {a_{n n}^{(1)}} & {|} & {-\frac{a_{n 1}}{a_{11}}} & & &{1}\end{array}\right]$
• 可得 $\left[\begin{array}{cccccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} & {|} & {1} \\ {0} & {a_{22}^{(1)}} & {\cdots} & {a_{2 n}^{(1)}} & {|} &{-\frac{a_{21}}{a_{11}}} & {1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {|} & \vdots & \vdots & {\ddots} \\ {0} & 0 & {\cdots} & {a_{n n}^{(2)}} & {|} & * & {-\frac{a_{n 2}^{(1)}}{a_{22}^{(1)}}} & \ldots &{1}\end{array}\right]$

---

• 依此类推，
• 由 $\left[\begin{array}{cccccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} & {|} & {1} \\ {0} & {a_{22}^{(1)}} & {\cdots} & {a_{2 n}^{(1)}} & {|} &{-\frac{a_{21}}{a_{11}}} & {1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {|} & \vdots & \vdots & {\ddots} \\ {0} & 0 & {\cdots} & {a_{n n}^{(2)}} & {|} & * & {-\frac{a_{n 2}^{(1)}}{a_{22}^{(1)}}} & \ldots &{1}\end{array}\right]$,
• 最终可得 $\left[\begin{array}{ccccccc}{a_{11}} & {a_{12}} & {\cdots} & {a_{1 n}} & {|} & {} 1\\ {0} & {a_{22}^{(1)}} & {\cdots} & {a_{2 n}^{(1)}} & {|} & * &{1} \\ {\vdots} & {\vdots} & {\ddots} & {\vdots} & {|} & \vdots &{\vdots} & {\ddots} \\ {0} & {0} & {\cdots} & {a_{n n}^{(n-1)}} & {|} &{*} & {*} & {\cdots} & {1}\end{array}\right] \triangleq\left[\boldsymbol{R}\;\; \boldsymbol{L}^{-1}\right]$.
• 其中：$\boldsymbol{L}^{-1}$ 是单位下三角阵， $\boldsymbol{R}$ 是上三角阵.
• 由单位下三角阵的性质知， $\boldsymbol{L}$ 也是单位下三角阵.

---

• 以上的行变换，可综合表示为 $\boldsymbol{L}^{-1}[\boldsymbol{A} \;\; \boldsymbol{I}]=[\boldsymbol{R} \;\; \boldsymbol{L}^{-1}]$，
• 由此即知 $\boldsymbol{A}=\boldsymbol{L R}$.
• 以下证明唯一性
• 假设同时存在两个 LR 分解： $\boldsymbol{A}=\boldsymbol{L R}=\tilde{\boldsymbol{L}} \tilde{\boldsymbol{R}}$.
• 因为 $\boldsymbol{A}$ 可逆，故 $\boldsymbol{L}$，$\tilde{\boldsymbol{R}}$ 均可逆.
• 由前式可得 $\boldsymbol{L}^{-1} \tilde{\boldsymbol{L}}=\boldsymbol{R} \tilde{\boldsymbol{R}}^{-1}$.
• 这说明 $\boldsymbol{L}^{-1} \tilde{\boldsymbol{L}}$ 既是单位下三角阵，又是上三角阵.
• 故 $\boldsymbol{L}^{-1} \tilde{\boldsymbol{L}}$ 是单位阵.
• 进而可知 $\boldsymbol{L}=\tilde{\boldsymbol{L}}, \boldsymbol{R}=\tilde{\boldsymbol{R}}$.

---

证明必要性： 设可逆矩阵 $\boldsymbol{A}$ 存在 LR 分解： $\boldsymbol{A}=\boldsymbol{LR}$

• 对任意的 $k=1,2,...n$，可将 $\boldsymbol{A}=\boldsymbol{LR}$ 写成分块矩阵的形式
• $\boldsymbol{A}=\left[\begin{array}{c}{\boldsymbol{A}_{k}} & {\boldsymbol{B}_{k}} \\ {\boldsymbol{C}_{k}} & {\boldsymbol{D}_{k}}\end{array}\right]=\left[\begin{array}{c}{\boldsymbol{L}_{k}} & \\ {\boldsymbol{M}_{k}} & {\boldsymbol{N}_{k}}\end{array}\right]\left[\begin{array}{c}{\boldsymbol{R}_{k}} & {\boldsymbol{V}_{k}} \\ & {\boldsymbol{W}_{k}}\end{array}\right]$
• 其中: $\boldsymbol{A}_k,\boldsymbol{L}_k,\boldsymbol{R}_k$ 分别是 $\boldsymbol{A},\boldsymbol{L},\boldsymbol{R}$ 的 $k$ 阶顺序主子阵,
• 显然 $\boldsymbol{A}_{k}=\boldsymbol{L}_{k} \boldsymbol{R}_{k}$.
• 因为 $\boldsymbol{A}$ 可逆，所以 $\boldsymbol{L},\boldsymbol{R}$ 可逆.
• 进而可知 $\left|{\boldsymbol{L}}_{k}\right| \neq {0}, \quad\left|{\boldsymbol{R}}_{k}\right| \neq {0}$.
• 于是 $\Delta_k=\left|\boldsymbol{A}_{k}\right|=\left|\boldsymbol{L}_{k}\right| \cdot\left|{\boldsymbol{R}}_{k}\right| \neq 0$.

---

4.1.2 三角分解的求解

• 方法一：Gauss 消元法求三角分解
• 方法二：待定系数法求三角分解

---

Gauss 消元法求三角分解

例 求 $\boldsymbol{A}=\left[\begin{array}{ccc}{2} & {1} & {4} \\ {4} & {3} & {13} \\ {2} & {2} & {20}\end{array}\right]$ 的 LR 分解.

• 提示： $\Delta_{1}=2 \neq 0, \quad \Delta_{2}=6-4 \neq 0$.
• $\boldsymbol{A}$ 有唯一的 LR 分解.

---

• $[\boldsymbol{A}\;\; \boldsymbol{I}]=\left[\begin{array}{cccc}{2} & {1} & {4} & { | } & 1\\ {4} & {3} & {13} & { | } && {1} \\ {2} & {2} & {20} & { | } &&& {1}\end{array}\right]$.
  
  • $\to\left[\begin{array}{cccrrr}{2} & {1} & {4} & { | } & 1 \\ {0} & {1} & {5} & { | } & -2 & {1} \\ {0} & {1} & {16} & { | } & -1 & {0} & {1}\end{array}\right]$
  • $\to\left[\begin{array}{cccrrr}{2} & {1} & {4} & { | } & {1} & {} \\ {0} & {1} & {5} & { | } & {-2} & {1} \\ {0} & {0} & {11} & { | } & {1} & {-1} & {1}\end{array}\right]$
  • $=\left[\boldsymbol{R}\;\;\boldsymbol{L}^{-1}\right]$.

---

• $\boldsymbol{L}=\left[\begin{array}{lll}{1} & {} \\ {2} & {1} \\ {1} & {1} & {1}\end{array}\right]$
• $\boldsymbol{A}=\left[\begin{array}{ccc}{2} & {1} & {4} \\ {4} & {3} & {13} \\ {2} & {2} & {20}\end{array}\right]=\boldsymbol{L R}=\left[\begin{array}{ccc}{1} & {} & {} \\ {2} & {1} & {} \\ {1} & {1} & {1}\end{array}\right]\left[\begin{array}{ccc}{2} & {1} & {4} \\ {} & {1} & {5} \\ {} & {} & {11}\end{array}\right]$

---

例 $\boldsymbol{A}=\left[\begin{array}{cccc}{0} & {1} & {-1} & {2} \\ {1} & {0} & {0} & {1} \\ {2} & {-1} & {0} & {1} \\ {1} & {3} & {0} & {1}\end{array}\right]$ 是否存在 LR 分解？

• 分析： $\Delta_1=0$ ，故 $\boldsymbol{A}$ 没有 LR 分解.
• 但因为 $\boldsymbol{A}$ 可逆，故 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ 的解唯一.
• 将 $\boldsymbol{A}$ 的前两行互换，可得 $\tilde{\boldsymbol{A}}=\left[\begin{array}{cccc}{1} & {0} & {0} & {1} \\ {0} & {1} & {-1} & {2} \\ {2} & {-1} & {0} & {1} \\ {1} & {3} & {0} & {1}\end{array}\right]$
• 可以验证 $\tilde{\boldsymbol{A}}$ 有 LR 分解，且方程组 $\boldsymbol{A}\boldsymbol{x}=\boldsymbol{b}$ 与 $\tilde{\boldsymbol{A}} \boldsymbol{x}=\tilde{\boldsymbol{b}}$ 同解.
• 记 $\boldsymbol{P} \boldsymbol{A}=\tilde{\boldsymbol{A}}$ ， $\boldsymbol{P}$ 称为 置换矩阵 (Permutation Matrix).

---

带行交换的 LR 分解

定理 若 $\boldsymbol{A}$ 是可逆方阵，则存在置换矩阵 $\boldsymbol{P}$ ，使得 $\boldsymbol{PA}$ 有唯一的三角分解，即

$$\boldsymbol{P A}=\boldsymbol{L R}$$

称以上 LR 分解为 $\boldsymbol{A}$ 的 带行交换的 LR 分解

---

例 求 $\boldsymbol{A}=\left[\begin{array}{cccc}{0} & {1} & {-1} & {2} \\ {1} & {0} & {0} & {1} \\ {2} & {-1} & {0} & {1} \\ {1} & {3} & {0} & {1}\end{array}\right]$ 的带行交换的 LR 分解.

• 提示： $A$ 是可逆阵，但 $\Delta_1=0$，故无法进行 LR 分解.
• 取 $\boldsymbol{P}=\left[\begin{array}{llll}{0} & {1} & {0} & {0} \\ {1} & {0} & {0} & {0} \\ {0} & {0} & {1} & {0} \\ {0} & {0} & {0} & {1}\end{array}\right]$, 则 $\boldsymbol{P A}=\left[\begin{array}{cccc}{1} & {0} & {0} & {1} \\ {0} & {1} & {-1} & {2} \\ {2} & {-1} & {0} & {1} \\ {1} & {3} & {0} & {1}\end{array}\right]$.
• 变换后 $\Delta_{1}=1 \neq 0, \quad \Delta_{2}=1 \neq 0, \quad \Delta_{3}=-1 \neq 0$，故 $\boldsymbol{PA}$ 有唯一的 LR 分解.

---

• $[\boldsymbol{P A}\;\; \boldsymbol{I}]=\left[\begin{array}{rrrrrrrrr}{1} & {0} & {0} & {1} & { | } & {1} & {0} & {0} & {0} \\ {0} & {1} & {-1} & {2} & { | } & {0} & {1} & {0} & {0} \\ {2} & {-1} & {0} & {1} & { | } & {0} & {0} & {1} & {0} \\ {1} & {3} & {0} & {1} & { | } & {0} & {0} & {0} & {1}\end{array}\right]$
  
  • $\to \left[\begin{array}{rrrrrrrrr} {1} & {0} & {0} & {1} & { | } & {1} & {0} & {0} & {0} \\ {0} & {1} & {-1} & {2} & { | } & {0} & {1} & {0} & {0} \\ {0} & {-1} & {0} & {-1} & { | } & {-2} & {0} & {1} & {0} \\ {0} & {3} & {0} & {0} & { | } & {-1} & {0} & {0} & {1} \end{array}\right]$
  • $\to\left[\begin{array}{rrrrrrrrr} {1} & {0} & {0} & {1} & { | } & {1} & {0} & {0} & {0} \\ {0} & {1} & {-1} & {2} & { | } & {0} & {1} & {0} & {0} \\ {0} & {0} & {-1} & {1} & { | } & {-2} & {1} & {1} & {0} \\ {0} & {0} & {3} & {-6} & { | } & {-1} & {-3} & {0} & {1} \end{array}\right]$
  • $\to\left[\begin{array}{rrrrrrrrr} {1} & {0} & {0} & {1} & { | } & {1} & {0} & {0} & {0} \\ {0} & {1} & {-1} & {2} & { | } & {0} & {1} & {0} & {0} \\ {0} & {0} & {-1} & {1} & { | } & {-2} & {1} & {1} & {0} \\ {0} & {0} & {0} & {-3} & { | } & {-7} & {0} & {3} & {1} \end{array}\right]=[\boldsymbol{R}\;\;\boldsymbol{L}^{-1}]$

---

于是 $\boldsymbol{R}=\left[\begin{array}{rrrr}{1} & {0} & {0} & {1} \\ & {1} & {-1} & {2} \\ & & {-1} & {1} \\ & & & {-3}\end{array}\right], \boldsymbol{L}^{-1}=\left[\begin{array}{rrrr}{1} & & & \\ {0} & {1} & & \\ {-2} & {1} & {1} & \\ {-7} & {0} & {3} & {1}\end{array}\right]$.

• 进而 $\boldsymbol{L}=\left[\begin{array}{rrrr}{1} & & & \\ {0} & {1} & & \\ {2} & {-1} & {1} & \\ {1} & {3} & {-3} & {1}\end{array}\right]$.
• $\boldsymbol{P A}=\boldsymbol{L R}=\left[\begin{array}{rrrr}{1} & & & \\ {0} & {1} & & \\ {2} & {-1} & {1} & \\ {1} & {3} & {-3} & {1}\end{array}\right]\left[\begin{array}{rrrr}{1} & {0} & {0} & {1} \\ & {1} & {-1} & {2} \\ & & {-1} & {1} \\ & & & {-3}\end{array}\right]$.

---

例 设 $\left[\begin{array}{cc} 4 & 3\\ 6 & 3 \end{array}\right]=\left[\begin{array}{cc} 1 & \\ l_{21} & 1 \end{array}\right]\left[\begin{array}{cc} r_{11} & r_{12} \\ & r_{22} \end{array}\right]$

• 也即 $\left\{\begin{aligned} 4 & = r_{11}\\ 3 & = r_{12}\\ 6 & = l_{21}r_{11}\\ 3 & = l_{21}r_{12}+r_{22} \end{aligned} \right.$
• 依次可解得
  
  • $r_{11}=4,\;r_{12}=3$
  • $l_{21}=1.5$
  • $r_{22}=-1.5$

---

待定系数法求三角分解

考虑 $n$ 阶可逆方阵 $\boldsymbol{A}=[a_{ij}]_{n\times n}$ 有三角分解 $\boldsymbol{A}=\boldsymbol{LR}$，其中

$$\boldsymbol{L}=\left[\begin{array}{cccc}{1} \\ {l_{21}} & {1} \\ {\vdots} & {\vdots} & {\ddots} & {} \\ {l_{n 1}} & {l_{n 2}} & {\cdots} & {1}\end{array}\right], \quad \boldsymbol{R}=\left[\begin{array}{cccc}{r_{11}} & {r_{12}} & {\cdots} & {r_{1 n}} \\ & {r_{22}} & {\cdots} & {r_{2 n}} \\ & & {\ddots} & {\vdots} \\ & & & {r_{n n}}\end{array}\right].$$

利用行列式的乘法可得到一系列等式关系，进而可由其解出 $\boldsymbol{L},\boldsymbol{R}$ 中所有的待定数值.

---

求解公式

1. $r_{11}=a_{11}, \quad r_{12}=a_{12}, \quad \cdots, \quad r_{1 n}=a_{1 n}$
2. $l_{21}=\frac{a_{21}}{r_{11}}, \quad l_{31}=\frac{a_{31}}{r_{11}}, \cdots, \quad l_{n 1}=\frac{a_{n 1}}{r_{11}}$
3. $r_{22}=a_{22}-l_{21} r_{12}, \quad r_{23}=a_{23}-l_{21} r_{13},$
   
   • $\cdots,\; r_{2 n}=a_{2 n}-l_{21} r_{1 n}$
4. $l_{i 2}=\frac{1}{r_{22}}\left(a_{i 2}-l_{i 1} r_{12}\right), \quad i=3,4, \cdots, n$
5. ......

---

Doolittle 紧凑计算格式

• For $k=1$ to $n$
  
  • For $j=k$ to $n$
    
    • $r_{k j}=a_{k j}-\sum\limits_{i=1}^{k-1} l_{k i} r_{i j}$
  • $y_k=b_k-\sum\limits_{i=1}^{k-1} l_{k i} y_i$
  • For $i=k+1$ to $n$
    
    • $l_{i k}=\frac{1}{r_{k k}}\left(a_{i k}-\sum\limits_{m=1}^{k-1} l_{i m} r_{m k}\right),$
• For $k=n$ to $1$
  
  • $x_k=\frac{1}{r_{kk}}\left(y_k-\sum\limits_{j=k+1}^n\frac{r_{kj}}{r_{jj}}x_j\right)$

---

例 用 LR 分解法求解线性方程组

$$\left[\begin{array}{cccc}{2} & {10} & {0} & {-3} \\ {-3} & {-4} & {-12} & {13} \\ {1} & {2} & {3} & {-4} \\ {4} & {14} & {9} & {-13}\end{array}\right]\left[\begin{array}{l}{x_{1}} \\ {x_{2}} \\ {x_{3}} \\ {x_{4}}\end{array}\right]=\left[\begin{array}{c}{10} \\ {5} \\ {-2} \\ {7}\end{array}\right]$$

• $r_{1j}=a_{1j},\;j=1,2,3,4$
  
  • $(r_{11},r_{12},r_{13},r_{14})=(2,10,0,-3)$
• $l_{i1}=\frac{a_{i1}}{r_{11}},\;i=2,3,4$
  
  • $(1,l_{21},l_{31},l_{41})=(1,-1.5,0.5,2)$

---

• $r_{2j}=a_{2j}-l_{21}r_{1j},\;j=2,3,4$
  
  • $(0,r_{22},r_{23},r_{24})=(0,11,-12,17/2)$
• $l_{i2}=\frac1{r_{22}}\left(a_{i2}-l_{i1}r_{12}\right),\;i=3,4$
  
  • $(0,1,l_{32},l_{42})=(0,1,-3/11,-6/11)$
• $r_{3j}=a_{3j}-l_{31}r_{1j}-l_{32}r_{2j},\;j=3,4$
  
  • $(0,0,r_{33},r_{34})=(0,0,-3/11,-2/11)$
• $l_{43}=\frac1{r_{33}}\left(a_{43}-l_{41}r_{13}-l_{42}r_{23}\right)$
  
  • $(0,0,1,l_{43})=(0,0,1,-9)$
• $r_{44}=a_{44}-l_{41}r_{14}-l_{42}r_{24}-l_{43}r_{34}$
  
  • $(0,0,0,r_{44})=(0,0,0,-4)$

---

• $\boldsymbol{L}=\left[\begin{array}{cccc}1 & \\ -3/2 & 1 \\ 1/2 & -3/11 & 1 \\ 2 & -6/11 & -9 & 1\end{array}\right]$,
• 解 $\boldsymbol{L}\boldsymbol{y}=\boldsymbol{b}$，得 $\boldsymbol{y}=[10\;\;20\;-17/11\;\;-16]^{\mathrm{T}}$.
• $\boldsymbol{R}=\left[\begin{array}{cccc}2 & 10 & 0 & -3 \\ & 11 & -12 & 17/2 \\ & & -3/11 & -2/11 \\ &&& -4\end{array}\right]$,
• 解 $\boldsymbol{R}\boldsymbol{x}=\boldsymbol{y}$， 得 $\boldsymbol{x}=[1\;2\;3\;4]^{\mathrm{T}}$.

---

迭代过程

$\left[\begin{array}{rrrr:r} 2 & 10 & 0 & -3 & 10\\ -3 & -4 & -12 & 13 & 5 \\ 1 & 2 & 3 & -4 & -2 \\ 4 & 14 & 9 & -13 & 7 \end{array}\right]\to\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & -4 & -12 & 13 & 5 \\ \bbox[lightgreen]{\frac{1}{2}} & 2 & 3 & -4 & -2 \\ \bbox[lightgreen]{2} & 14 & 9 & -13 & 7 \end{array}\right]$

• $\bbox[yellow]{r_{1j}}=a_{1j},\; j=1,2,3,4$
• $\bbox[lightblue]{y_1}=b_1$
• $\bbox[lightgreen]{l_{i1}}=\frac{a_{i1}}{\bbox[yellow]{r_{11}}},\;i=2,3,4$

---

$\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & -4 & -12 & 13 & 5 \\ \bbox[lightgreen]{\frac{1}{2}} & 2 & 3 & -4 & -2 \\ \bbox[lightgreen]{2} & 14 & 9 & -13 & 7 \end{array}\right]\to\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & \bbox[yellow]{11} & \bbox[yellow]{-12} & \bbox[yellow]{\frac{17}{2}} & \bbox[lightblue]{20} \\ \bbox[lightgreen]{\frac{1}{2}} & \bbox[lightgreen]{-\frac{3}{1}} & 3 & -4 & -2 \\ \bbox[lightgreen]{2} & \bbox[lightgreen]{-\frac{6}{11}} & 9 & -13 & 7 \end{array}\right]$

• $\bbox[yellow]{r_{2j}}=a_{2j}-\bbox[lightgreen]{l_{21}}\bbox[yellow]{r_{1j}},\; j=2,3,4$
• $\bbox[lightblue]{y_2}=b_2-\bbox[lightgreen]{l_{21}}\bbox[lightblue]{y_{1}}$
• $\bbox[lightgreen]{l_{i2}}=\frac{1}{\bbox[yellow]{r_{22}}}(a_{i2}-\bbox[lightgreen]{l_{i1}}\bbox[yellow]{r_{12}}),\;i=3,4$

---

$\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & \bbox[yellow]{11} & \bbox[yellow]{-12} & \bbox[yellow]{\frac{17}{2}} & \bbox[lightblue]{20} \\ \bbox[lightgreen]{\frac{1}{2}} & \bbox[lightgreen]{-\frac{3}{1}} & 3 & -4 & -2 \\ \bbox[lightgreen]{2} & \bbox[lightgreen]{-\frac{6}{11}} & 9 & -13 & 7 \end{array}\right]\to \left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & \bbox[yellow]{11} & \bbox[yellow]{-12} & \bbox[yellow]{\frac{17}{2}} & \bbox[lightblue]{20} \\ \bbox[lightgreen]{\frac{1}{2}} & \bbox[lightgreen]{-\frac{3}{1}} & \bbox[yellow]{-\frac{3}{11}} & \bbox[yellow]{-\frac{2}{11}} & \bbox[lightblue]{-\frac{17}{11}} \\ \bbox[lightgreen]{2} & \bbox[lightgreen]{-\frac{6}{11}} & \bbox[lightgreen]{-9} & -13 & 7 \end{array}\right]$

• $\bbox[yellow]{r_{3j}}=a_{3j}-\bbox[lightgreen]{l_{31}}\bbox[yellow]{r_{1j}}-\bbox[lightgreen]{l_{32}}\bbox[yellow]{r_{2j}},\; j=3,4$
• $\bbox[lightblue]{y_3}=b_3-\bbox[lightgreen]{l_{31}}\bbox[lightblue]{y_{1}}-\bbox[lightgreen]{l_{32}}\bbox[lightblue]{y_{2}}$
• $\bbox[lightgreen]{l_{43}}=\frac{1}{\bbox[yellow]{r_{33}}}(a_{43}-\bbox[lightgreen]{l_{41}}\bbox[yellow]{r_{13}}-\bbox[lightgreen]{l_{42}}\bbox[yellow]{r_{23})}$

---

$\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & \bbox[yellow]{11} & \bbox[yellow]{-12} & \bbox[yellow]{\frac{17}{2}} & \bbox[lightblue]{20} \\ \bbox[lightgreen]{\frac{1}{2}} & \bbox[lightgreen]{-\frac{3}{1}} & \bbox[yellow]{-\frac{3}{11}} & \bbox[yellow]{-\frac{2}{11}} & \bbox[lightblue]{-\frac{17}{11}} \\ \bbox[lightgreen]{2} & \bbox[lightgreen]{-\frac{6}{11}} & \bbox[lightgreen]{-9} & -13 & 7 \end{array}\right]\to \left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ \bbox[lightgreen]{-\frac{3}{2}} & \bbox[yellow]{11} & \bbox[yellow]{-12} & \bbox[yellow]{\frac{17}{2}} & \bbox[lightblue]{20} \\ \bbox[lightgreen]{\frac{1}{2}} & \bbox[lightgreen]{-\frac{3}{1}} & \bbox[yellow]{-\frac{3}{11}} & \bbox[yellow]{-\frac{2}{11}} & \bbox[lightblue]{-\frac{17}{11}} \\ \bbox[lightgreen]{2} & \bbox[lightgreen]{-\frac{6}{11}} & \bbox[lightgreen]{-9} & \bbox[yellow]{-4} & \bbox[lightblue]{-16} \end{array}\right]$

• $\bbox[yellow]{r_{44}}=a_{44}-\bbox[lightgreen]{l_{41}}\bbox[yellow]{r_{14}}-\bbox[lightgreen]{l_{42}}\bbox[yellow]{r_{24}}-\bbox[lightgreen]{l_{43}}\bbox[yellow]{r_{34}}$
• $\bbox[lightblue]{y_4}=b_4-\bbox[lightgreen]{l_{41}}\bbox[lightblue]{y_1}-\bbox[lightgreen]{l_{42}}\bbox[lightblue]{y_2}-\bbox[lightgreen]{l_{43}}\bbox[lightblue]{y_3}$

---

$\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & \bbox[yellow]{-3} & \bbox[lightblue]{10}\\ & \bbox[yellow]{11} & \bbox[yellow]{-12} & \bbox[yellow]{\frac{17}{2}} & \bbox[lightblue]{20} \\ & & \bbox[yellow]{-\frac{3}{11}} & \bbox[yellow]{-\frac{2}{11}} & \bbox[lightblue]{-\frac{17}{11}} \\ & & & \bbox[yellow]{-4} & \bbox[lightblue]{-16} \end{array}\right]\to \left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & \bbox[yellow]{0} & 0 & \bbox[lightgreen]{22}\\ & \bbox[yellow]{11} & \bbox[yellow]{-12} & 0 & \bbox[lightgreen]{-14} \\ & & \bbox[yellow]{-\frac{3}{11}} & 0 & \bbox[lightgreen]{-\frac{9}{11}} \\ & & & 1 & 4 \end{array}\right]$

$\to\left[\begin{array}{rrrr:r} \bbox[yellow]{2} & \bbox[yellow]{10} & 0 & 0 & \bbox[lightgreen]{22}\\ & \bbox[yellow]{11} & 0 & 0 & \bbox[lightgreen]{22} \\ & & 1 & 0 & 3 \\ & & & 1 & 4 \end{array}\right]\to \left[\begin{array}{rrrr:r} 1 & 0 & 0 & 0 & 1 \\ & 1 & 0 & 0 & 2 \\ & & 1 & 0 & 3 \\ & & & 1 & 4 \end{array}\right]$

---

4.1.3 LDR 分解

若方阵 $\boldsymbol{A}$ 是可逆的，则有三角分解

$$\boldsymbol{A}=\boldsymbol{L} \tilde{\boldsymbol{R}}$$

其中 $\boldsymbol{L}$ 是单位下三角阵， $\tilde{\boldsymbol{R}}$ 是上三角阵.

• 分析： 因为 $\boldsymbol{A}$ 可逆，所以 $\tilde{\boldsymbol{R}}$ 可逆，故 $\tilde{\boldsymbol{R}}$ 的对角元不为零.

---

• 令 $\tilde{\boldsymbol{R}}=\left[\begin{array}{c}d_1 \\ & d_2\\ && \ddots\\ &&& d_n\end{array}\right]\left[\begin{array}{c}1 & r_{12} & \ldots & r_{1n}\\ & 1 & \ddots & \vdots \\ && \ddots & r_{n-1,n} \\ &&& 1\end{array} \right] \triangleq \boldsymbol{D R},$ 则 $\boldsymbol{A}=\boldsymbol{LDR}$.
  
  • 其中：$\boldsymbol{L}$ 是单位下三角阵;
  • $\boldsymbol{D}$ 是对角阵;
  • $\boldsymbol{R}$ 是单位上三角阵.
• 称 $\boldsymbol{A}=\boldsymbol{LDR}$ 是 $\boldsymbol{A}$ 的 LDR分解（或 LDU分解）.

---

例 求 $\boldsymbol{A}=\left[\begin{array}{ccc}{1} & {2} & {1} \\ {0} & {2} & {3} \\ {0} & {-6} & {0}\end{array}\right]$ 的LDR分解.

• 提示：先求 $\boldsymbol{A}$ 的 LR 分解
• $\boldsymbol{A}=\left[\begin{array}{ccc}{1} & {2} & {1} \\ {0} & {2} & {3} \\ {0} & {-6} & {0}\end{array}\right]=\boldsymbol{L} \tilde{\boldsymbol{R}}=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {-3} & {1}\end{array}\right]\left[\begin{array}{ccc}{1} & {2} & {1} \\ {0} & {2} & {3} \\ {0} & {0} & {9}\end{array}\right]$.
• 进而可知 $\boldsymbol{A}$ 的 LDR 分解为 $\boldsymbol{A}=\boldsymbol{L D R}=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {-3} & {1}\end{array}\right]\left[\begin{array}{ccc}1 \\ & 2 \\ && 9\end{array}\right]\left[\begin{array}{ccc}1&2&1\\ &1&3/2\\ &&1\end{array}\right]$.

---

4.1.3 正定矩阵的平方根分解

• 设方阵 $\boldsymbol{A}$ 正定，则 $\boldsymbol{A}$ 的顺序主子式均大于零.
• 于是 $\boldsymbol{A}$ 必有 LDR 分解，设 $\boldsymbol{A}=\boldsymbol{LDR}$，其中：$\boldsymbol{D}=\operatorname{diag}\left\{d_{1}, d_{2}, \cdots, d_{n}\right\}$.
• 记 $\boldsymbol{D}_k$ 为 $\boldsymbol{D}$ 的 $k$ 级顺序主子式，则 $|\boldsymbol{A}_k|=|\boldsymbol{D}_k|=\prod_{i=1}^{k}d_i>0,\;k=1,2,\ldots,n$.
• 由此可知 $d_i>0,\;i=1,2,\ldots,n$.
• 令 $\boldsymbol{D}^{\frac{1}{2}}=\mathrm{diag}\{\sqrt{d_1},\ldots,\sqrt{d_n}\}$，则 $\boldsymbol{D}=\boldsymbol{D}^{\frac{1}{2}}\left(\boldsymbol{D}^{\frac{1}{2}}\right)^{\mathrm{T}}$.

---

• 因为 $\boldsymbol{A}^{\mathrm{T}}=\boldsymbol{A}$ ，故 $\boldsymbol{LDR}=\boldsymbol{R}^{\mathrm{T}}\boldsymbol{DL}^{\mathrm{T}}$.
• 由于 $LDR$ 分解是唯一的，故由上式可知 $\boldsymbol{L}^{\mathrm{T}}=\boldsymbol{R}$.
• 进而 $\boldsymbol{A}=\boldsymbol{L D R}=\boldsymbol{L D}^{\frac{1}{2}} \boldsymbol{D}^{\frac{1}{2}} \boldsymbol{L}^{{T}}=\left(\boldsymbol{L D}^{\frac{1}{2}}\right)\left(\boldsymbol{L D}^{\frac{1}{2}}\right)^{\mathrm{T}}$.
• 令 $\boldsymbol{G}=\boldsymbol{L D}^{\frac{1}{2}}$，显然 $\boldsymbol{G}$ 是对角元大于 $0$ 的下三角阵，且 $\boldsymbol{A}=\boldsymbol{GG}^T$.
• 以上的分解称为正定矩阵 $\boldsymbol{A}$ 的平方根分解 (或 Cholesky分解).

---

例 求 $\boldsymbol{A}=\left[\begin{array}{ccc}{5} & {-2} & {0} \\ {-2} & {3} & {-1} \\ {0} & {-1} & {1}\end{array}\right]$ 的平方根分解.

---

方法一：Gauss消元法

• 设 $\boldsymbol{A}=\boldsymbol{LDR}$，则 $\boldsymbol{G}=\boldsymbol{L} \boldsymbol{D}^{1 / 2}=\boldsymbol{R}^{\mathrm{T}} \boldsymbol{D}^{1 / 2}$.
• $\boldsymbol{A}=\left[\begin{array}{rrr}{5} & {-2} & {0} \\ {-2} & {3} & {-1} \\ {0} & {-1} & {1}\end{array}\right]\to \left[\begin{array}{rrr}{5} & {-2} & {0} \\ {0} & {11 / 5} & {-1} \\ {0} & {-1} & {1}\end{array}\right] \to \left[\begin{array}{cccc}{5} & {-2} & {0} \\ {0} & {11 / 5} & {-1} \\ {0} & {0} & {6 / 11}\end{array}\right]$
  
  • $=\left[\begin{array}{ccc}{5} & {0} & {0} \\ {0} & {11 / 5} & {0} \\ {0} & {0} & {6 / 11}\end{array}\right]\left[\begin{array}{ccc}{1} & {-2 / 5} & {0} \\ {0} & {1} & {-5 / 11} \\ {0} & {0} & {1}\end{array}\right]=\boldsymbol{D}^{\frac{1}{2}}\boldsymbol{R}$.
• $\boldsymbol{A}=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {-2 / 5} & {1} & {0} \\ {0} & {-5 / 11} & {1}\end{array}\right]\left[\begin{array}{cccc}{5} & {0} & {0} \\ {0} & {11 / 5} & {0} \\ {0} & {0} & {6 / 11}\end{array}\right]\left[\begin{array}{ccc}{1} & {-2 / 5} & {0} \\ {0} & {1} & {-5 / 11} \\ {0} & {0} & {1}\end{array}\right].$

---

• 令 $\boldsymbol{G}=\left[\begin{array}{ccc}{1} & {0} & {0} \\ {-2 / 5} & {1} & {0} \\ {0} & {-5 / 11} & {1}\end{array}\right]\left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {0} & {\sqrt{11 / 5}} & {0} \\ {0} & {0} & {\sqrt{6 / 11}}\end{array}\right]$
  
  • $=\left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {-2 / \sqrt{5}} & {\sqrt{11 / 5}} & {0} \\ {0} & {-\sqrt{5 / 11}} & {\sqrt{6 / 11}}\end{array}\right]$.
• $\boldsymbol{A}=\boldsymbol{G G}^{\mathrm{T}}=\left[\begin{array}{ccc}{\sqrt{5}} & {0} & {0} \\ {-2 / \sqrt{5}} & {\sqrt{11 / 5}} & {0} \\ {0} & {-\sqrt{5 / 11}} & {\sqrt{6 / 11}}\end{array}\right]\left[\begin{array}{ccc}{\sqrt{5}} & {-2 / \sqrt{5}} & {0} \\ {0} & {\sqrt{11 / 5}} & {-\sqrt{5 / 11}} \\ {0} & {0} & {\sqrt{6 / 11}}\end{array}\right].$

---

方法二：待定系数法

设 $\boldsymbol{A}=\left[\begin{array}{ccc}{5} & {-2} & {0} \\ {-2} & {3} & {-1} \\ {0} & {-1} & {1}\end{array}\right]=\boldsymbol{GG}^{\mathrm{T}}=\left[\begin{array}{lll}{g_{11}} & {} & {} \\ {g_{21}} & {g_{22}} & {} \\ {g_{31}} & {g_{32}} & {g_{33}}\end{array}\right]\left[\begin{array}{ccc}{g_{11}} & {g_{21}} & {g_{31}} \\ {} & {g_{22}} & {g_{32}} \\ {} & {} & {g_{33}}\end{array}\right]$.

• $g_{11}=\sqrt{5},\quad g_{11} g_{21}=-2 \quad\Rightarrow\quad g_{21}=-\frac{2}{\sqrt{5}}$.
• $g_{11} g_{31}=0 \quad\Rightarrow\quad g_{31}=0$.
• $g_{21}^{2}+g_{22}^{2}=3 \quad\Rightarrow\quad g_{22}=\sqrt{\frac{11}{5}}$.
• $g_{31} g_{21}+g_{32} g_{22}=-1 \quad\Rightarrow\quad g_{32}=-\sqrt{\frac{5}{11}}$.
• $g_{31}^{2}+g_{32}^{2}+g_{33}^{2}=1 \quad\Rightarrow\quad g_{33}=\sqrt{\frac{6}{11}}$.

---

Crout 分解

• 如果 $\boldsymbol{A}$ 存在 LR 分解，则 $\boldsymbol{A}$ 一定也存在所谓的 Crout 分解, 即：$\boldsymbol{A}=\tilde{\boldsymbol{L}}\tilde{\boldsymbol{R}}$
  
  • 其中: $\tilde{\boldsymbol{L}}$ 为下三角阵，$\tilde{\boldsymbol{R}}$ 为单位上三角阵.
• 如果 $\boldsymbol{A}$ 为正定的 Hermite 矩阵，则存在下三角矩阵 $\boldsymbol{G}$，使得 $\boldsymbol{A}=\boldsymbol{GG}^{\mathrm{H}}$.

---

小结

• LR 分解
  
  1. Gauss 分解法
  2. 待定系数法
• LDR 分解
  
  • 正定矩阵的平方根分解