线性方程组与问题背景¶

本讲讨论 解线性代数方程组的直接法 ，核心是把

通过有限步代数变换化为易解的三角方程组。

典型来源：

• 基尔霍夫定律电路方程 可写成矩阵形式 \(Ax=b\)。
• 线性积分方程离散化 ：例如

取网格点 \(x_j=j/n\)，并用求积公式近似积分，可得到线性方程组

一些常见矩阵结构（复习）¶

• 对角矩阵 ：\(i\neq j\Rightarrow a_{ij}=0\)，记 \(A=\mathrm{diag}\{a_{11},\dots,a_{nn}\}\)。
• 三对角矩阵 ：\(|i-j|>1\Rightarrow a_{ij}=0\)。
• 上/下三角矩阵 ：上三角 \(i>j\Rightarrow a_{ij}=0\)；下三角 \(i<j\Rightarrow a_{ij}=0\)。
• 三角矩阵性质 ：
• 上（下）三角矩阵的逆仍为上（下）三角矩阵；
• 两个上（下）三角矩阵乘积仍为上（下）三角矩阵；
• 若对角线全为 1（单位三角矩阵），上述性质同样成立且逆仍为单位三角矩阵。
• 对称矩阵 ：\(A^T=A\)。
• 对称正定 ：\(A^T=A\) 且 \(\forall x\neq 0,\; x^TAx>0\)；半正定则为 \(\ge 0\)。
• 正交矩阵 ：\(A^T=A^{-1}\)。

上三角方程组与回代¶

若已经得到上三角方程组 \(Ux=\tilde b\)：

只要满足 \(u_{ii}\neq 0\)，就可以按 \(x_n,x_{n-1},\dots,x_1\) 回代 求解。

回代伪代码（解向量覆盖右端向量）：

for i = n, n-1, ..., 1:
    for j = n, n-1, ..., i+1:
        b[i] = b[i] - a[i,j] * b[j]
    b[i] = b[i] / a[i,i]

GAUSS 消去法（不选主元）¶

目标：通过消元把 \(Ax=b\) 化为等价的上三角系统 \(Ux=\tilde b\)。

消元的行变换（核心公式）¶

第 1 步把第 1 列下面的元素消成 0：假设 \(a^{(1)}_{11}\neq 0\)，对 \(k=2,\dots,n\) 做

得到新矩阵 \(A^{(2)}\)。之后对第 2 列、…、第 \(n-1\) 列重复，总共 \(n-1\) 次，最终得到上三角 \(A^{(n)}=U\)，以及对应右端项 \(\tilde b\)。

算法流程（in-place 版本）¶

消元阶段伪代码：

for k = 1,2,...,n-1:
    for i = k+1,...,n:
        c = -a[i,k] / a[k,k]
        for j = k+1,...,n:
            a[i,j] = a[i,j] + c * a[k,j]
        b[i] = b[i] + c * b[k]

要点：

• 通常 不做对角元归一化 （避免额外除法）。
• 为减少不必要计算/写入，程序实现里常只更新 \(j\ge k+1\) 的部分；左下角最终不会用于回代。

复杂度（经典结论）¶

以浮点运算计：

• 除法次数 ：\((n-1)+(n-2)+\cdots+1=\frac{n(n-1)}2\)。
• 乘法次数 ：主导项约为 \(n^3/3\)；加法同阶约 \(n^3/3\)。
• 空间复杂度 ：直接覆盖修改 \(A\) 与 \(b\)，额外存储可做到 \(O(n^2)\)（矩阵本身占用）。

矩阵解释：消元矩阵、LU 分解¶

用消元矩阵表示一步消元¶

第 1 步消元可写成

其中

一般第 \(k\) 步：

把 \(m_k\)（第 \(k\) 列消元乘子向量）与标准基 \(e_k\) 写成向量形式，可得

利用 Sherman–Morrison（\(k=1\) 的 SMW 退化形式）并结合 \(m_k^T e_k=0\)，有简洁逆：

LU 分解（不选主元时）¶

连乘得到

于是

其中 \(L\) 是 单位下三角矩阵 （对角线为 1），\(U\) 是上三角矩阵。

用 LU 解方程组的视角：

1) 先解 \(Ly=b\)（前代）；2) 再解 \(Ux=y\)（回代）。

数值问题：为什么要选主元¶

GAUSS 消去法要求每一步主元 \(a^{(k)}_{kk}\neq 0\)。即便不为 0，但若 \(|a^{(k)}_{kk}|\) 很小，会导致

• 除以接近 0 的数 使消元乘子很大；
• 放大舍入误差，出现严重数值不稳定。

典型反例（误差很大）¶

考虑

真解为 \(x_1=-1,\; x_2=1+\varepsilon\)。

若直接以 \(\varepsilon\) 为首主元做消元，会产生形如 \(1-1/\varepsilon\) 的灾难性量级；当 \(\varepsilon\) 小到接近机器精度时，浮点表示会把一些“1 与巨大数相减”的结果近似为 \(-1/\varepsilon\)，最终得到明显错误的解（课件中示例出现 \(x_1=0,x_2=1\) 这种错误）。

列主元（部分选主元）消去法¶

处理第 \(k\) 步主元时，在当前列 \(k\) 的行 \(k,\dots,n\) 中选择绝对值最大的元素作为主元：

然后 交换第 \(p\) 行与第 \(k\) 行 ，再继续消元。

这样能显著提高稳定性，并避免除以接近 0 的数。

初等交换矩阵与排列矩阵¶

交换两行可表示为左乘一个初等交换矩阵 \(P_k\)。它满足：

• \(P_k=P_k^T\)（对称）
• \(P_k^{-1}=P_k\)，即 \(P_kP_k=I\)（交换两次恢复原状）

把所有交换连乘得到一个排列矩阵

其性质：

• \(P^{-1}=P^T\)（正交矩阵）
• 每个元素为 0 或 1，且 每行每列恰有一个 1 。

带列主元的 LU（PLU）分解¶

列主元消去的整体过程可写成

经过整理可得

也就是常见的 PLU 分解 （或称带置换的 LU 分解）。

实现要点：用置换向量代替“真的换行”¶

实际编程时，为了避免频繁搬动整行数据，可维护一个置换向量 \(p\)：

• 初始 \(p=[1,2,\dots,n]\)；
• 每次交换两行 \(s,t\)，只交换 \(p[s]\) 与 \(p[t]\)；
• 访问矩阵第 \(k\) 行时用 \(p[k]\) 映射到真实行号。

由 \(p\) 可以构造排列矩阵：

列主元消去法伪代码（课件版本）：

p[i] = i, i=1..n
for k = 1..n-1:
    s = argmax_{i=k..n} |a[p[i], k]|
    swap(p[s], p[k])
    for i = k+1..n:
        c = -a[p[i], k] / a[p[k], k]
        for j = k+1..n:
            a[p[i], j] = a[p[i], j] + c * a[p[k], j]
        b[p[i]] = b[p[i]] + c * b[p[k]]

复杂度与不选主元的 Gauss 消去同阶：乘加主导项仍为 \(O(n^3)\)，但会多出比较操作。

例题摘记¶

例 2.1（手工消元）¶

方程组（课件给出）通过对增广矩阵做行变换，最终得到上三角后回代，结论：

• \(x_3=1\)
• \(x_2=-1\)
• \(x_1=0\)

（这类题复习重点： 每步消元的“消元乘子”与行变换写法 ，以及最终回代。）

例 2.3（列主元 + PLU）¶

对

按列主元策略进行两次行交换与消元，可得到 \(PA=LU\)（课件给出了具体的 \(P,L,U\)）。

小结¶

• Gauss 消去 ：消元 + 回代，计算量主导为 \(O(n^3)\)。
• 矩阵视角 ：消元矩阵 \(M_k\) 使得 \(A\) 逐步变上三角；不选主元时得到 \(A=LU\)。
• 数值稳定性 ：主元过小会放大舍入误差；用 列主元（部分选主元） 更稳健。
• 带主元的分解 ：最终得到 \(PA=LU\)，实现时常用置换向量 \(p\) 降低交换成本。