01先把问题说具体
同一矩阵 A 要分别解 Ax=b₁、Ax=b₂。每次都重新消元会重复哪些工作?
02一步步得到方法
消元乘子就是 L 的元素
高斯消元中把第 i 行减去 factor 倍第 k 行,这个 factor 可以保存到下三角矩阵 L 的 (i,k) 位置,L 对角线取 1。最终上三角结果为 U。
使用行交换时,本课约定 PA=LU,其中 P 把 A 的行按 perm 顺序重排。某些库采用 A=PLU,返回的 P 可能是这里的逆置换,使用前必须核对文档。
分解与求解分成两个阶段
由 PAx=Pb 得 L(Ux)=Pb。先解 Ly=Pb,因 L 为下三角可前代;再解 Ux=y,后代。更换 b 时,L、U 不变,只需两次三角求解。
第 k 步交换行时,已经算好的 L 的前 k 列乘子也要随行交换;尚未计算的部分不能当作完整系数随意移动。漏掉这个细节会得到无法重构 PA 的因子。
分解成本可以在多组右端之间复用
同一个 A 配多个 b 时,反复做完整高斯消元会重复大量工作。先分解一次,再对每个右端先前代解 Ly=Pb、后代解 Ux=y,可以复用昂贵的矩阵处理。
含主元交换时,置换关系必须跟代码约定一致。本课使用 PA=LU,因此右端是 Pb;不同库也可能返回 A=PLU 形式,不能只看变量都叫 P 就认为方向相同。
03把一个小例子完全算清楚
A=[[2,1],[4,3]]。
| 步骤 | 计算与状态 | 为什么这样做 |
|---|---|---|
| 行交换 | perm=[1,0],PA=[[4,3],[2,1]] | 使用部分主元 |
| 消元乘子 | L=[[1,0],[0.5,1]] | 保存 0.5 |
| 上三角 | U=[[4,3],[0,−0.5]] | 验证 L·U=PA |
窄屏可左右滑动表格,阅读完整计算与理由。
一次因子分解之后,许多右端项只需较便宜的前代和回代。
04为什么这个方法成立
- 每次消元可表示为单位下三角变换,逆变换的乘子汇集为 L。
- 置换同步作用于 U、行索引及既有 L 乘子,保持 PA=LU。
- 两个三角系统与原系统等价,因此可复用因子求解任意右端。
05把推导翻译成代码
Python · 可独立运行的教学实现
def lu_factor(a):
n = len(a)
u = [list(map(float,row)) for row in a]
l = [[float(i==j) for j in range(n)] for i in range(n)]
perm = list(range(n))
for k in range(n):
p = max(range(k,n),key=lambda i:abs(u[i][k]))
if abs(u[p][k]) < 1e-12:
raise ArithmeticError("small pivot")
u[k],u[p] = u[p],u[k]
perm[k],perm[p] = perm[p],perm[k]
l[k][:k],l[p][:k] = l[p][:k],l[k][:k]
for i in range(k+1,n):
l[i][k] = u[i][k]/u[k][k]
for j in range(k,n):
u[i][j] -= l[i][k]*u[k][j]
return perm,l,u
def lu_solve(factors,b):
perm,l,u = factors
n = len(b); y,x = [0.0]*n,[0.0]*n
for i in range(n):
y[i] = b[perm[i]]-sum(l[i][j]*y[j] for j in range(i))
for i in range(n-1,-1,-1):
x[i] = (y[i]-sum(u[i][j]*x[j] for j in range(i+1,n)))/u[i][i]
return x逐个理解关键决定
l[k][:k],l[p][:k]- 交换已经形成的下三角乘子,保留分解不变量。
b[perm[i]]- 右端必须使用与 A 相同的行置换。
06时间、空间与实现范围
一次分解 O(n³),每个右端求解 O(n²),存储 O(n²)。
当右端数量多时复用明显;稀疏矩阵还要考虑填充、重排序和稀疏因子存储。
07改变条件,检查哪里会出错
解 Ly=b 而非 Ly=Pb
存在行交换时会解错系统。
后续主元交换未同步已计算的 L 部分
早先消元乘数也关联具体行,交换时要保留正确分解关系。
08从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
L 的对角为什么可全设 1?
需要一点提示
本约定将缩放留在 U。
查看解析与答案
这是 Doolittle 型单位下三角约定;其他分解也可采用不同对角规范。
如何检查分解本身?
需要一点提示
先不求任何 x。
查看解析与答案
重构 L·U,与按 perm 重排的原 A 比较,检查相对残差。
A 变了一行还能直接用旧 L、U 吗?
需要一点提示
因子属于哪一个矩阵?
查看解析与答案
不能一般直接复用,需要重新分解或使用专门低秩更新方法。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Driscoll 与 Braun · Fundamentals of Numerical Computation