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为什么这个方法成立
- 每次减去在已有 q 上的投影,精确算术下残余与已有方向正交。
- 残余非零时归一化得到新单位方向。
- 保存投影与残余系数后可重构每个原列,因此 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
两列完全相同会发生什么?
需要一点提示
第二列减投影后剩什么?
查看解析与答案
残余为零,不能归一化,说明列线性相关。
为什么 QᵀQ=I 而 QQᵀ 未必是 I?
需要一点提示
瘦 Q 形状 m×n。
查看解析与答案
列正交给 n×n 单位阵;m>n 时 QQᵀ 是列空间投影,不是整个空间的单位算子。
如何求最小二乘 x?
需要一点提示
利用正交投影。
查看解析与答案
计算 Qᵀb,再解上三角 Rx=Qᵀb,残差正交于 A 的列空间。
继续深入这个专题
本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。
Driscoll 与 Braun · Fundamentals of Numerical Computation