专题进阶 · 数值算法推荐总顺序 · 第 113 / 148 课

把消元过程保存为三角因子,一次分解复用多个右端项,并明确置换约定。

先学会这些,再进入本课 高斯消元
还有 1 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 数值算法

LU 分解LU Factorization

把矩阵分解为三角因子,适合同一矩阵对应多个右端项;一般需要置换。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

把消元过程保存为三角因子,一次分解复用多个右端项,并明确置换约定。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

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为什么这个方法成立

  1. 每次消元可表示为单位下三角变换,逆变换的乘子汇集为 L。
  2. 置换同步作用于 U、行索引及既有 L 乘子,保持 PA=LU。
  3. 两个三角系统与原系统等价,因此可复用因子求解任意右端。

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从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

L 的对角为什么可全设 1?

需要一点提示

本约定将缩放留在 U。

查看解析与答案

这是 Doolittle 型单位下三角约定;其他分解也可采用不同对角规范。

练习 2 · 边界与辨析

如何检查分解本身?

需要一点提示

先不求任何 x。

查看解析与答案

重构 L·U,与按 perm 重排的原 A 比较,检查相对残差。

练习 3 · 变式与迁移

A 变了一行还能直接用旧 L、U 吗?

需要一点提示

因子属于哪一个矩阵?

查看解析与答案

不能一般直接复用,需要重新分解或使用专门低秩更新方法。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Driscoll 与 Braun · Fundamentals of Numerical Computation

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。