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

用正交投影分离列方向,推导 QR 与最小二乘的联系。

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

QR 分解QR Factorization

把矩阵分成正交与上三角因子,常用于最小二乘和特征值算法。

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

本课要建立的能力

用正交投影分离列方向,推导 QR 与最小二乘的联系。

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

01先把问题说具体

方程数量比未知数多时,通常无法全部精确满足。怎样找使残差平方和最小的近似解?

02一步步得到方法

Q 保存正交方向,R 保存组合系数

对矩阵 A 的各列依次处理。先将第一列归一化为 q₁;第二列减去在 q₁ 上的投影,再归一化为 q₂。继续减去所有已获得方向的投影,得到彼此正交的单位向量。

投影系数 rᵢⱼ=qᵢᵀaⱼ,残余长度给出对角 rⱼⱼ。于是每个原列都是 q 列的线性组合,即 A=QR。QᵀQ=I,R 为上三角。

为何能用于最小二乘

设 Q 为瘦正交基,残差可分成列空间内和正交补两部分。正交补与 x 无关,要最小化只需令 Rx=Qᵀb,然后回代。

本代码是修改 Gram–Schmidt 教学版,逐次更新残余,通常比经典版本更稳定;但近线性相关列仍可能失去正交性,工程上常用 Householder QR 或重正交化。不要为方便而显式形成正规方程 AᵀA,它会平方条件数。

正交基让投影系数容易解释

把 A 的列分解为一组正交单位方向 Q,R 保存每列在这些方向上的坐标。Gram–Schmidt 逐个减去已有方向的投影,再对剩余向量归一化。

若用于最小二乘,A≈QR 后可把目标转成求解上三角系统 Rx=Qᵀb,避免显式形成可能放大条件数的 AᵀA。列几乎相关时正交化更敏感,Householder 等实现通常更可靠。

03把一个小例子完全算清楚

A 的列 a₁=(1,0),a₂=(1,1)。

步骤计算与状态为什么这样做
第一列q₁=(1,0),r₁₁=1归一化
第二列投影r₁₂=q₁ᵀa₂=1减去 (1,0)
残余(0,1),长度 1,q₂=(0,1)Q=I,R=A

窄屏可左右滑动表格,阅读完整计算与理由。

更一般矩阵下 Q 不是单位阵,但仍将列分解成正交方向与上三角系数。

04为什么这个方法成立

  1. 每次减去在已有 q 上的投影,精确算术下残余与已有方向正交。
  2. 残余非零时归一化得到新单位方向。
  3. 保存投影与残余系数后可重构每个原列,因此 A=QR;线性相关时残余为零,需要秩处理。

05把推导翻译成代码

Python · 可独立运行的教学实现

from math import sqrt
def qr(a):
    m,n = len(a),len(a[0])
    assert m >= n
    q = [[0.0]*n for _ in range(m)]
    r = [[0.0]*n for _ in range(n)]
    for j in range(n):
        v = [float(a[row][j]) for row in range(m)]
        for i in range(j):
            r[i][j] = sum(q[row][i]*v[row] for row in range(m))
            v = [v[row]-r[i][j]*q[row][i] for row in range(m)]
        r[j][j] = sqrt(sum(x*x for x in v))
        if r[j][j] < 1e-12:
            raise ArithmeticError("dependent or nearly dependent columns")
        for row in range(m):
            q[row][j] = v[row]/r[j][j]
    return q,r

逐个理解关键决定

q[row][i]*v[row]
对当前残余做投影,体现修改 Gram–Schmidt。
v[row]/r[j][j]
除以残余范数得到单位向量,零残余表示秩不足。

06时间、空间与实现范围

m×n、m≥n,时间 O(mn²),存储 Q 为 O(mn)、R 为 O(n²)。

本实现要求列满秩,阈值是教学保护;秩亏与强病态问题宜用带列主元 QR 或 SVD。

07改变条件,检查哪里会出错

Q 正交就认为任意有限精度实现完全稳定

舍入会损害正交性,应检查 QᵀQ 与 A−QR。

只检查 QR≈A,不检查 Q 的正交性

两者是不同要求,应同时核对重构残差与 QᵀQ≈I。

08从手算到独立迁移

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

练习 1 · 复现与理解

两列完全相同会发生什么?

需要一点提示

第二列减投影后剩什么?

查看解析与答案

残余为零,不能归一化,说明列线性相关。

练习 2 · 边界与辨析

为什么 QᵀQ=I 而 QQᵀ 未必是 I?

需要一点提示

瘦 Q 形状 m×n。

查看解析与答案

列正交给 n×n 单位阵;m>n 时 QQᵀ 是列空间投影,不是整个空间的单位算子。

练习 3 · 变式与迁移

如何求最小二乘 x?

需要一点提示

利用正交投影。

查看解析与答案

计算 Qᵀb,再解上三角 Rx=Qᵀb,残差正交于 A 的列空间。

继续深入这个专题

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

Driscoll 与 Braun · Fundamentals of Numerical Computation

理解之后,继续递进

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