2.2 直接三角分解

对应教材 2.2.1–2.2.5、定理 2.3–2.5、例 2–3、习题 4–8；对应老师第 4 讲 §二–§四。 主线：把“消元”写成“分解” $A=LU$，一次分解、反复使用；三对角结构再把 $O(n^3)$ 降到 $O(n)$。

2.2.1 Doolittle 分解与 Crout 分解

设 $A$ 非奇异，且前 $n-1$ 个顺序主子式不为零。Doolittle 分解是

$$A=LU,$$

其中 $L$ 是单位下三角（对角元为 1），$U$ 是上三角。逐圈公式（教材式 2.12）：

$$u_{kj}=a_{kj}-\sum_{s=1}^{k-1}l_{ks}u_{sj}\quad(j=k,\dots,n), \qquad l_{ik}=\frac{a_{ik}-\sum_{s=1}^{k-1}l_{is}u_{sk}}{u_{kk}}\quad(i=k+1,\dots,n).$$

解方程组分两步：先解 $L\boldsymbol y=\boldsymbol b$（前代），再解 $U\boldsymbol x=\boldsymbol y$（回代）。

定理 2.3：$n\ge2$ 阶矩阵 $A$ 有唯一 Doolittle 分解的充要条件是前 $n-1$ 个顺序主子式 $D_k\ne0\ (k=1,\dots,n-1)$。

证明要点：充分性由定理 2.1 的顺序消去得到 $P_{n-1}\cdots P_1A=U$，取 $L=P_1^{-1}\cdots P_{n-1}^{-1}$；必要性由 $A_k=L_kU_k$ 得 $D_k=u_{11}\cdots u_{kk}$，若某个 $u_{kk}=0$ 则分解不唯一。$\blacksquare$

Crout 分解：$A=LU$，其中 $L$ 是下三角（对角元不一定是 1），$U$ 是单位上三角。教材给出推论：与 Doolittle 分解存在唯一性等价；两者只差一个对角缩放。

例 2（教材 2.2.1，四位十进制）：方程组 $$\begin{cases} 8.1x_1+2.3x_2-1.5x_3=6.1,\ 0.5x_1-6.23x_2+0.87x_3=2.3,\ 2.5x_1+1.5x_2+10.2x_3=1.8. \end{cases}$$ Doolittle 分解后前代得 $y_1=6.1,\ y_2\approx1.923,\ y_3\approx0.1560$，再回代得 $x$。这个例子说明：分解本身不神秘，逐圈公式的顺序不能乱——每一步只让一个新未知数出现。

2.2.2 选主元的 Doolittle 分解

若某个 $u_{kk}=0$ 或相对很小，分解不能继续或误差会被放大。与列主元 Gauss 消去类似，在分解过程中选主元：第 $k$ 步在当前列的剩余行中选绝对值最大者，交换行，再继续分解。

定理 2.4：若 $A$ 非奇异，则存在置换矩阵 $Q$，使 $QA=LU$，其中 $L$ 单位下三角、$U$ 上三角。

证明要点：由定理 2.2，列主元消去可把 $A$ 化为上三角；把行交换矩阵 $Q_k$ 与消元矩阵 $P_k$ 合并，得到 $Q A=L U$。$\blacksquare$

实际实现时通常把 $Q$ 记录为一个排列向量，不显式构造矩阵；解方程组时对右端做同样的行交换。

2.2.3 带状矩阵的保带状分解

若 $a_{ij}=0$ 当 $i-j\gt r$ 或 $j-i\gt s$，称 $A$ 为上半带宽 $s$、下半带宽 $r$ 的带状矩阵。

定理 2.5（保带状结构三角分解）：设 $A$ 是上半带宽 $s$、下半带宽 $r$ 的带状矩阵，且前 $n-1$ 个顺序主子式不为零；则 $A$ 有唯一 Doolittle 分解 $A=LU$，其中 $L$ 是下半带宽 $r$ 的单位下三角，$U$ 是上半带宽 $s$ 的上三角。

证明要点：由定理 2.3 有唯一分解；当 $i-j\gt r$ 时，$a_{ik}=0\ (k\le j)$，由逐圈公式推出 $l_{ij}=0$；同理 $j-i\gt s$ 时 $u_{ij}=0$。$\blacksquare$

推论：同样条件下，$A$ 有唯一 Crout 分解，且保带宽。计算量：只需存 $(r+s+1)n$ 个带内元素，分解与求解都是 $O(n)$。

2.2.4 追赶法（三对角方程组）

三对角方程组 $$a_i x_{i-1}+b_i x_i+c_i x_{i+1}=d_i,\qquad i=1,\dots,n$$ （$a_1=c_n=0$）是 $r=s=1$ 的带状矩阵。用 Crout 分解可写成“追”和“赶”两步：

追（前代）： $$c'_1=\frac{c_1}{b_1},\quad d'_1=\frac{d_1}{b_1}; \qquad den_i=b_i-a_i c'_{i-1},\quad c'_i=\frac{c_i}{den_i},\quad d'_i=\frac{d_i-a_i d'_{i-1}}{den_i}.$$

赶（回代）： $$x_n=d'_n,\qquad x_i=d'_i-c'_i x_{i+1}\quad(i=n-1,\dots,1).$$

计算量约 $3n$ 次乘除法，即 $O(n)$；不需要选主元的前提是 $den_i\ne0$（如严格对角占优）。

例 3（教材 2.2.4）：教材用五对角/三对角方程组演示追赶法，精确解为 $(0.21,-0.52,1.2,0.82,-0.64)^{\mathrm T}$。关键是：分解不产生填充，带外元素始终为零。

2.2.5 拟三对角方程组（教材有、课堂未展开）

拟三对角矩阵形如 $$A=\begin{pmatrix} b_1&c_1&&&d_1\ a_2&b_2&c_2&&\ &\ddots&\ddots&\ddots&\ &&a_{n-1}&b_{n-1}&c_{n-1}\ e_1&&&a_n&b_n \end{pmatrix},$$ 即三对角外加右上角 $d_1$ 与左下角 $e_1$。教材 2.2.5 给出把它分解为两个三对角矩阵乘积的方法，从而仍可用追赶法求解。课堂未展开，考试按老师范围；需要时按教材补读。

2.2.6 习题（教材习题 4–8）