Ran Wei/数学系列
English
计算机科学与人工智能的数学基础 — Ran Wei

正交性、投影与最小二乘

不用微积分推导最近点投影与正规方程,构造 QR,区分拟合与权重唯一,诊断数值和建模限制。

10 小时4 个时段3 个实验12 道练习与 2 道拓展10 道自测题

完成后你能够

  • 定义内积并说明正交勾股分解。
  • 推导向量及子空间投影与唯一性。
  • 构造格拉姆–施密特并核对约化 QR。
  • 用 QR 解满列秩最小二乘,明确全部形状。
  • 不用求导证明正规方程必要与充分。
  • 描述秩亏最小化族与唯一最小范数代表。
  • 区分数值求解质量、系数敏感性与未来预测主张。

开始之前

模块 11:基、四基本空间、秩–零化度与零空间参数等价。回顾模块 09 点积及欧几里得范数。

目录

学习计划

10 小时

时间包含练习,是估计值;可按需要拆分时段。可选拓展练习额外需要 35 分钟。进度保存在当前浏览器,中英文版本共享。

1

把近似变成精确的几何问题

Xw=y 可能无解,却仍有唯一的最近预测向量。当测量目标不在设计列空间时,这个区别很重要。最小二乘按指定距离选择最近预测;它本身不使系数唯一,不保证测量可靠,也不保证未来记录上的预测有效。

本课先推导几何,再介绍算法。你将证明投影公式,构造标准正交基,用 QR 求解,并不靠求导建立正规方程。最后描述秩亏最小化族及其中最小范数代表。实验比较数学等价、浮点计算与数据敏感性。

检索检查:给矩阵的列、零空间,解释零位移为何不改变预测。需要时复习模块 11。点积与长度见模块 09。不假设微积分,后面会用求导再次推导正规方程。实验采用 NumPy 准备的固定环境。

2

内积、正交与勾股分解

实内积为两个向量指定实数 ⟨u,v⟩,对每个变量线性、对称、正定:⟨v,v⟩≥0,且仅 v=0 时等号成立。这些条件推广坐标点积并保留几何推理。相应范数为 √⟨v,v⟩,正交指 ⟨u,v⟩=0。正交相对于选定内积;改变坐标权重可改变正交关系,而加法和线性相关仍相同。

欧几里得积为 uᵀv=Σuᵢvᵢ。加权积为 uᵀWv,其中 W 对称正定。若 W 为对角矩阵且 αᵢ>0,则积为 Σαᵢuᵢvᵢ,对称、双线性逐项成立。非零向量至少一个非零坐标贡献严格正平方,因此满足全部条件。它等于先把坐标缩放 √αᵢ,再用普通点积。某权重为零会使非零向量零长度,只是半正定表达式,不是整个坐标空间的内积;负权重连非负性也破坏。

u,v 正交时,展开得到 ‖u+v‖²=‖u‖²+2⟨u,v⟩+‖v‖²=‖u‖²+‖v‖²。这一勾股恒等式驱动投影和最小二乘。不正交时交叉项保留,直接相加平方长度通常错误。向量不必是坐标轴,只要在指定积下垂直即可。有限个两两正交成分的和也可用相同展开得到平方和。

例题详解
内积改变垂直方向

u=(1,1),r=(1,−1) 欧几里得点积为零;W=diag(4,1) 下加权积为 4−1=3,所以不正交。s=(1,−4) 与 u 加权正交,因为 4·1+1·(−4)=0。向量空间与线性关系没变,距离和垂直性的测量变了。

标准正交列表 q₁,…,q_r 的向量都为单位长度,且两两正交。这样的列表自动独立:将零组合与 q_j 点乘,第 j 个系数必须为零。以它们为列组成 Q,QᵀQ=I_r,形状 r×r。若 Q 是 m×r 且 r<m,这不意味着 QQᵀ=I_m;后者将是较小列空间的投影。把矩形 Q 当成正交方阵会混淆两种约定。

拟合中的加权距离是“哪些误差更重要”的建模选择。大权重更惩罚某些坐标误差,可反映已知测量精度或应用目标,但需要依据。只声明加权内积并未提供统计噪声模型。除非明确标注,以下推导采用欧几里得几何,使目标、残差正交与算法一致。

零向量与每个向量垂直,却不能归一化,也没有定义角度。需要方向的算法须防止除零范数。非零向量欧几里得正交等价于夹角余弦为零,但把余弦当概率是额外、未由代数支持的解释。本课正交是能证明分解的精确关系,不是含糊地说特征“无关联”。

检验理解

Q 在 R³ 只有一条单位列时,QᵀQ=I 能推出 QQᵀ=I 吗?权重 (1,0,1) 能在 R³ 定义内积吗?

查看答案

不能。QQᵀ 的像为直线,不能是 R³ 的恒等映射。中间零权重让 (0,1,0) 长度为零,违反正定。结论来自维数和定义,不是实现约定。

3

到直线及子空间的投影

给非零 u 与目标 y,在 span{u} 求最近点 p=cu。令残差 r=y−cu 垂直 u,得到 uᵀy−c uᵀu=0。uᵀu>0,故唯一系数 c=(uᵀy)/(uᵀu)。c 是标量,p 是原目标空间的向量;只有某些坐标约定下数值会巧合,代码应分别命名。

为何垂直选择使距离最小?任意其他 a 满足 y−au=r+(c−a)u,两项正交,所以 ‖y−au‖²=‖r‖²+(c−a)²‖u‖²。第二项非负,恰在 a=c 为零。无需微积分,已证明最优与唯一。若生成向量为零,其张成为零空间,投影直接是零,不需要未定义分式。重缩放非零生成元使 c 反向缩放,p 不变,符合子空间投影的含义。

例题详解
投影到对角线

y=(3,2),u=(1,1),c=5/2,p=(5/2,5/2)。残差 (1/2,−1/2) 垂直 u,平方长度 1/2。任意候选 (a,a) 的平方误差为 1/2+2(a−5/2)²,因此最小值唯一。目标不在线上,非零残差是预期结果,不表示投影失败。

有限维子空间 S 有标准正交基列 Q,定义 p=QQᵀy,基坐标为 Qᵀy。残差满足 Qᵀr=Qᵀy−QᵀQ Qᵀy=0,因此垂直每条基及 S 中每条向量。对其他 s∈S,y−s=r+(p−s) 正交分解,‖y−s‖²=‖r‖²+‖p−s‖²,证明最近点存在且预测向量唯一。第 3 节将构造任意有限维 S 所需的标准正交基。

投影矩阵 P=QQᵀ 对称且幂等:Pᵀ=P,P²=Q(QᵀQ)Qᵀ=P。幂等指已投影再投影不变,对称反映欧几里得垂直。像为 S,因为 Py∈S 且 s∈S 时 Ps=s;核为 S⊥,因为 Qᵀy=0 等价于垂直基。补投影 I−P 给残差。它们描述唯一正交分解 y=p+r,不是可逆坐标变换。

勾股也证明投影不增加长度:‖Py‖²≤‖y‖²。对差向量应用并用线性性,得到 ‖Py−Pz‖≤‖y−z‖。固定子空间下,拟合观测向量变化不超过目标变化;但从它恢复系数坐标仍可能敏感。这解释了为何应分别讨论预测与参数稳定性。

对角线投影的正交分解三二投影到一一张成为二点五二点五,余量零点五负零点五垂直一一,平方长度二分之一。最近点:投影与残差垂直p=(2.5,2.5)y=(3,2)r=(0.5,−0.5)u·r = 0‖r‖² = 1/2其他候选增加平方项
图 12.1

目标分为对角线投影与垂直残差。线上其他候选会添加正交的额外误差。

若 U 独立但非标准正交地张成 S,垂直条件为 Uᵀ(y−Uc)=0。UᵀU 可逆,因为对非零 c,cᵀUᵀUc=‖Uc‖²>0,由列独立性得到。因此解 (UᵀU)c=Uᵀy,形式上 P=U(UᵀU)⁻¹Uᵀ。公式解释映射,却不要求显式计算逆作为最佳数值算法。QR 能不形成格拉姆矩阵而算同一投影。

对正对角权重,直线系数改为 (uᵀWy)/(uᵀWu),残差满足 uᵀWr=0。y=(3,2),u=(1,1),W=diag(4,1) 时,系数 14/5,投影 (2.8,2.8),残差 (0.2,−0.8) 加权正交却不欧几里得正交。最近点改变是因为目标改变。对仿射集合 p₀+S,应先将 y−p₀ 投影到 S 再加 p₀,不把偏移可行集当成过零子空间。

交互演示

改变二维目标及非零直线方向,读取投影、残差与点积核对,比较欧几里得和正权距离。

检验理解

两组不同标准正交基张成同一子空间,它们的欧几里得投影能把目标映到不同向量吗?

查看答案

不能。二者都产生 S 成员且残差垂直 S,最近点唯一性迫使结果相同。基坐标可能不同,但指定子空间与内积下的投影向量、映射不依赖基。

4

格拉姆–施密特与标准正交坐标

从 Rᵐ 中独立 a₁,…,a_d 出发,格拉姆–施密特构造相同逐步张成的标准正交列表。先 q₁=a₁/‖a₁‖。第 j 步移除前面方向成分:v_j=a_j−Σ_{i<j}(qᵢᵀa_j)qᵢ,再令 q_j=v_j/‖v_j‖。与前面 q_k 点乘,得到 q_kᵀa_j−q_kᵀa_j=0,因为标准正交交叉项都消失。因此余量垂直已有张成。

独立输入在精确运算下余量不可能零,否则 a_j 已是前面 q 的组合,也是前面 a 的组合,违反独立。归一化由此定义良好。每条 a_j 是 q₁,…,q_j 的组合,每条 q_j 是 a₁,…,a_j 的组合,所以逐步张成相同。归纳证明整个构造及张成保持,也证明每个有限维欧几里得子空间从普通基都可得到标准正交基。

例题详解
两列构造

a₁=(1,1,0),a₂=(1,0,1)。q₁=(1,1,0)/√2,q₁ᵀa₂=1/√2。v₂=(1/2,−1/2,1),长度 √(3/2),所以 q₂=(1,−1,2)/√6。点积为零,长度都一。上三角系数 R=[[√2,1/√2],[0,√(3/2)]] 的各列表达原 a 的 q 坐标,QR 重构原列。

合写为 A=QR。m≥d 且列独立时,约化 Q 是 m×d,QᵀQ=I_d,R 是 d×d 上三角。上三角项 rᵢⱼ=qᵢᵀa_j,对角正值为余量长度;非零对角使 R 可逆。三角结构记录建立张成的顺序。反转一条 q 列的符号,并同时反转 R 相应行,QR 不变,所以库 QR 与手算符号不同不意味着错误。

相关列的精确零余量是诊断。不要除零或声称得到了 d 个标准正交方向。可跳过冗余向量构造列空间的 r 列基,或用处理相关的分解。浮点极小余量需要明确分辨率策略:可能是精确相关、近相关或累积误差。固定绝对阈值随单位改变含义。实验简单保护用于说明判定,不是通用的揭示秩求解器。

经典格拉姆–施密特对原 a_j 计算全部去除系数,再减总贡献;修改版逐次去一个成分,下一系数对当前余量计算。精确正交下两者公式相同,浮点下舍入可不同。逐次移除通常更好保持正交,但不免疫严重近相关。再正交化或豪斯霍尔德 QR 可处理算法误差,却不创造病态设计缺失的信息。

标准正交基使坐标简单:qᵢᵀy 读取第 i 方向成分,成分平方和为投影平方长度,残差长度补充遗漏垂直部分。方形正交 Q 没有遗漏,坐标保持整个范数;矩形 Qᵀy 只保留较小列空间坐标。这区分完整坐标变换与降维。

两列格拉姆施密特从一零一减去沿第一标准正交方向的成分得二分之一负二分之一一,归一化得到一负一二除根号六,QR重构原列。先去成分,再归一化:保留相同张成a₂=(1,0,1)q₁=(1,1,0)/√2q₁·a₂=1/√2v₂(1/2,−1/2,1)‖v₂‖=√(3/2)q₂(1,−1,2)/√6q₁·q₂=0A = QR; R = [[√2,1/√2],[0,√(3/2)]]
图 12.2

移除第一成分留下垂直余量,归一化得到第二方向。三角系数保留重构信息。

检验理解

第二列为第一列两倍,其余量是什么?将极小计算余量设零能证明精确相关吗?

查看答案

精确余量零,不能归一化。阈值处理是数值分辨率判定,不是精确证明。报告输入模型与容差;要证明精确关系时采用精确算术。

5

QR 最小二乘与浮点限制

满列秩 X 为 m×d,m≥d,约化 X=QR。把 y 写为 QQᵀy+r,其中 Qᵀr=0,于是 y−Xw=r+Q(Qᵀy−Rw)。勾股与 Q 对 d 维坐标的保长度性给出 ‖y−Xw‖²=‖r‖²+‖Qᵀy−Rw‖²。第一项固定;R 可逆,第二项恰在 Rw=Qᵀy 时为零。回代解三角系统得到唯一 w。

形状明确:y 长 m,Qᵀy 长 d,R 为 d×d,w 长 d,预测 QQᵀy 长 m。库可把 y 存为列或支持多个目标列,应分别声明存储约定。Y 为 m×k 时,相同 R 解右端 QᵀY 的 d×k 权重;每列独立目标问题,复用分解避免重复几何计算。

例题详解
三记录直线拟合

记录 (0,1),(1,2),(2,2),拟合 y≈w₀+w₁x。X 行为 (1,0),(1,1),(1,2)。下节将证明的正规方程为 3w₀+3w₁=5、3w₀+5w₁=6,相减得 w₁=1/2,w₀=7/6。预测 (7/6,5/3,13/6),残差 (−1/6,1/3,−1/6),SSE 为 1/6。与截距和 x 列点积都零。QR 不以 XᵀX 为数值输入也得同权重。

豪斯霍尔德 QR 提供另一构造。单位 v 下 H=I−2vvᵀ 对称,展开 HᵀH 的 −4vvᵀ 与 4v(vᵀv)vᵀ 抵消,得到 I,所以是保范数反射。对非零列段 x,令 v 正比 x+s‖x‖e₁,s 与首坐标同号,首坐标零时取一;这样避免相近首项相减。反射将 x 映为 −s‖x‖e₁。逐次对尾列段反射,使各对角以下为零,正交乘积给 Q。这解释实际 QR 不必使用教学版格拉姆–施密特。

当格拉姆矩阵损失分辨率,应避免形成它。X 列为 (1,1,1) 与 (1,1+δ,1−δ),精确 XᵀX=[[3,3],[3,3+2δ²]]。独立差 δ 在格拉姆矩阵变成更小平方项。δ=10⁻⁸、本地双精度实验中,3+2δ² 舍入为三,计算矩阵奇异;原浮点 X 仍保留不同列项,QR 和最小二乘库可利用这些信息。精确公式等价,不代表计算中间量等价。

这不证明每次正规方程计算失败;良好条件的小问题可准确工作,如手算直线例。它展示近共线特征中的可避免损伤。格拉姆矩阵使二范数条件数平方的结论将在模块 14 从奇异值推导;这里 δ² 已明确展示机制,不预设该定理。

算法稳定与问题敏感仍不同。可靠 QR 可以准确求解给定数值,但沿弱方向极小扰动目标,系数仍剧变。实验 3 向 y 加 (0,δ,−δ),权重约变 (−1,1),残差仍极小。小拟合误差只证明与当前目标一致,不证明可靠恢复物理真系数。适当特征缩放、测量假设、后续正则化会改变模型或分辨率决策,却不取消区别。

检验理解

为何解 Rw=Qᵀy 而不显式构造 R⁻¹?QR 残差极小就证明测量扰动鲁棒吗?

查看答案

三角系统直接用回代得到所需权重,显式逆添加不必要中间工作。小残差只针对给定数据,即使算法稳定,弱方向仍可能放大小数据扰动。

6

不用求导推导正规方程

任意 X 下最小化 F(w)=‖y−Xw‖²,即最小二乘;平方指各坐标残差平方和。除以固定观测数或乘正常数改变数值却不改变最小化者。换度量、加惩罚、限制 w 可改变解集,需要重新推导。

S=C(X) 有限维,y 的正交投影 p 存在唯一。p∈S,至少存在一个 w 满足 Xw=p。这些且只有这些权重最小化,因为 ‖y−Xw‖²=‖y−p‖²+‖p−Xw‖²。因此秩亏也有最小化权重。拟合向量由子空间与距离唯一确定,但从权重到该向量可能多对一。

垂直条件给正规方程 Xᵀ(y−Xw)=0,即 XᵀXw=Xᵀy。必要性也可用标量变化证明:若残差 r 与某列 a_j 点积非零,只改变第 j 权重 t,则目标变化 t²‖a_j‖²−2t a_jᵀr。此时列非零,取 t=(a_jᵀr)/‖a_j‖² 就严格降低目标,违反最小。因此每列点积为零。没有导数,且覆盖全部不受约束实权重。

充分性:若 Xᵀr=0,权重变化 h 给残差 r−Xh,rᵀXh=0,所以 F(w+h)=F(w)+‖Xh‖²≥F(w)。每个正规方程解都是全局最小化者,等号恰在 h∈N(X)。已证明双向与完整族,不只找到驻点候选。满列秩迫使 h=0,最小化者唯一;否则 w+N(X) 全部最小且预测相同。

例题详解
残差在观测空间中垂直

三记录直线例的 Xᵀr 两分量是 Σrᵢ=0 与 Σxᵢrᵢ=0。r=(−1/6,1/3,−1/6) 满足二者。残差在 R³,垂直二维可能预测平面。散点图中三个竖直误差线段一般并不垂直 x–y 平面的拟合直线;正规方程讨论的是另一空间的观测向量几何。

有全一截距列时,残差垂直意味着其和零;无该列则无自动保证。精确拟合的残差零,零垂直所有列,故插值为特殊情形。残差可非零而 Xᵀr 零,如直线例;混淆两数组会把正确近似拟合说成精确拟合。

两种空间中的回归残差散点图显示三个竖直误差,观测三维残差负六分之一三分之一负六分之一与设计两列点积均零。竖直线段是坐标;正交成立在观测空间散点图:x–y 平面012观测向量:R³r=(−1/6,1/3,−1/6)Xᵀr=(0,0)残差垂直设计列平面,而非每个散点图线段垂直拟合线。
图 12.3

回归将 Rᵐ 的观测向量投影到设计列空间。散点图竖直残差显示它的各坐标,垂直性则在观测空间成立。

对称正定 W 的加权最小二乘最小化 rᵀWr,相同分解或变化给 XᵀWr=0、XᵀWXw=XᵀWy。对角权重可把 X 与 y 每行乘权重平方根后解普通欧几里得问题。零或负权重需另外处理,不能原样套内积证明。权重的数值形状与解释均属于规格。

正规方程描述最优,不要求以其格拉姆矩阵作为算法。QR 或 SVD 解可在数值容差内满足它们而避免该中间量。检查拟合应报告残差、尺度相关容差下 Xᵀr 及声明秩。好的最优性检查证明指定目标求解质量,却不独立证明噪声、遗漏变量、因果或外推。

检验理解

为何 Xᵀr=0 能在 r≠0 时成立?最小化 w 下何时 F(w+h)=F(w)?

查看答案

非零残差可在左零空间,垂直所有预测方向。目标相同恰在 Xh=0,即参数变化为零方向。满列秩排除非零此类变化。

7

最小范数权重与伪逆几何

秩亏设计的一个最小化者 w₀ 给出族 w₀+N(X)。选择代表的常见额外规则是最小化欧几里得参数范数。模块 11 已将参数空间正交分为 R(X) 与 N(X)。写 w₀=u+k,u 在行空间,k 在核。Xk=0,所以 Xu=Xw₀,u 也最小化。所有等价最小化者为 u+n;正交给 ‖u+n‖²=‖u‖²+‖n‖²,恰在 n=0 唯一最小。

因此最小范数最小二乘解是唯一位于行空间的最小化者。唯一性来自新增参数度量选择,不是观测新增信息。重参数化或特征缩放可以改变普通欧几里得范数最小系数,即使可能预测不变。所以此规则也依赖坐标约定。

例题详解
重复特征分摊可辨识系数

X 行 (1,x,x),x=0,1,2,目标 (1,2,2)。拟合要求 w₀=7/6,w₁+w₂=1/2,族为 (7/6,t,1/2−t)。范数平方 (7/6)²+t²+(1/2−t)²=(7/6)²+1/8+2(t−1/4)²,故最小范数 (7/6,1/4,1/4)。加任意 (0,−1,1) 倍数不改拟合。均分斜率由参数范数约定支持,不证明每个重复特征各有一半物理效应。

把 y 映到唯一代表的映射是伪逆 X⁺。几何有两步:先将 y 投影到 C(X),再应用 X 从 R(X) 到 C(X) 的限制逆。模块 11 证明该限制双射:行空间内核零,且到达整个列空间。投影和限制逆都线性,复合从 Rᵐ 到 Rᵈ,可表示为 d×m 矩阵,无需 X 的方阵逆。

它满足 XX⁺=P_C、X⁺X=P_R,分别是列和行空间正交投影。第一式因为投影、提升再映回给原投影目标;第二式因为参数分成行与核成分,提升只选行成分。因此 XX⁺X=X、X⁺XX⁺=X⁺,且 XX⁺、X⁺X 对称。这四式是 Moore–Penrose 条件。几何构造证明条件,也说明矩形伪逆不同于普通双侧逆。模块 14 将推导奇异值公式及数值阈值问题。

伪逆的投影与提升任意目标先到列空间最近预测,再用从行空间到列空间的限制逆提升为最小范数权重。伪逆:先投影目标,再选择无零成分的权重y ∈ Rᵐ任意目标p ∈ C(X)最近预测w_min ∈ R(X)最小范数代表XX⁺ = P_C; X⁺X = P_R没有消除核,也没有使列空间外的目标精确可达。
图 12.4

目标先投影到列空间,再由行空间限制逆选择没有核成分的系数,形成最小范数代表。

数值伪逆可按容差丢弃足够弱方向,改变计算所用有效子空间。返回最小范数针对该数值策略及数组,应与精确构造分开。固定最小二乘接口中,秩亏设计可能返回空残差汇总数组,而实际残差仍非零。应显式计算 y−Xw,不把空汇总当精确拟合证据。

最后区分三个问题:在目标度量下什么向量离观测最近?等价拟合中选择哪个系数代表?对新记录应转移什么预测或解释?正交投影回答第一个,满秩或额外约定回答第二个,第三个需要特征域假设与后续统计证据。训练零残差可能来自插值而未来表现差,小残差也可与不稳定系数共存。应把这些边界和代数一起保留,不对成功求解调用添加无依据结论。

检验理解

伪逆使全部目标精确可达吗?唯一最小范数向量去除了设计的零空间吗?

查看答案

没有。XX⁺y 是投影,仅 y 属于列空间时等于 y。零空间仍是 X 的性质;最小范数从既有等价族选行空间代表,没有使观测映射单射。

8

常见误解

主张 修正
投影系数就是投影向量 还要乘生成向量。
矩形 Q 的 QᵀQ=I 就有 QQᵀ=I QQᵀ 投影到 Q 的列空间。
零余量可归一化 零说明相关,需要保护。
正规方程必须求导 垂直或标量变化可证明双向。
散点图残差垂直拟合直线 正交成立在观测向量空间。
拟合唯一意味着权重唯一 零方向不改变预测。
空残差汇总意味着精确拟合 按库约定计算实际残差。
小残差保证系数鲁棒 弱方向会放大数据扰动。
9

三个 CPU 实验

采用数组准备中的 Python 3.11 与 NumPy 基线。输出来自运行可下载脚本。先预测形状和恒等式,对浮点相等用容差,并与精确证明区分。

实验 A 投影与正交化

比较欧几里得及加权对角线投影,预测各几何中哪个残差积应为零。追踪修改版格拉姆–施密特,验证 QᵀQ 和 QR,解释重复列保护,而非删掉保护继续运行。

下载 lab1_projections_and_bases.py

"""Projection depends on the inner product; orthonormalisation preserves span."""
import numpy as np
np.set_printoptions(precision=6, suppress=True)

y = np.array([3., 2.])
u = np.array([1., 1.])
coefficient = (u@y)/(u@u)
projection = coefficient*u
residual = y-projection
assert np.allclose(projection, [2.5, 2.5]) and np.isclose(u@residual, 0)
print("Euclidean coefficient / projection / residual:", coefficient, projection, residual)
weights = np.array([4., 1.])
weighted_coefficient = (u@(weights*y))/(u@(weights*u))
weighted_residual = y-weighted_coefficient*u
print("Weighted coefficient / residual:", weighted_coefficient, weighted_residual)
print("Weighted / Euclidean residual dot:", u@(weights*weighted_residual), u@weighted_residual)
assert np.isclose(weighted_coefficient, 2.8) and np.isclose(u@(weights*weighted_residual), 0)

def modified_gram_schmidt(A, tolerance=1e-12):
    Q = np.zeros_like(A, dtype=float)
    R = np.zeros((A.shape[1], A.shape[1]))
    for j in range(A.shape[1]):
        remaining = A[:, j].astype(float).copy()
        for i in range(j):
            R[i, j] = Q[:, i]@remaining
            remaining -= R[i, j]*Q[:, i]
        R[j, j] = np.linalg.norm(remaining)
        if R[j, j] <= tolerance:
            raise ValueError("Dependent or unresolved column: do not normalise zero")
        Q[:, j] = remaining/R[j, j]
    return Q, R

A = np.array([[1., 1.], [1., 0.], [0., 1.]])
Q, R = modified_gram_schmidt(A)
print("Q:", Q.tolist())
print("R:", R.tolist())
print("Orthogonality / reconstruction checks:", np.allclose(Q.T@Q, np.eye(2)), np.allclose(Q@R, A))
assert np.allclose(Q.T@Q, np.eye(2)) and np.allclose(Q@R, A)
try:
    modified_gram_schmidt(np.ones((3, 2)))
except ValueError as error:
    print("Duplicate-column guard:", error)
else:
    raise AssertionError("A zero remainder must not be normalised")
输出
Euclidean coefficient / projection / residual: 2.5 [2.5 2.5] [ 0.5 -0.5]
Weighted coefficient / residual: 2.8 [ 0.2 -0.8]
Weighted / Euclidean residual dot: 8.881784197001252e-16 -0.5999999999999996
Q: [[0.7071067811865475, 0.40824829046386313], [0.7071067811865475, -0.40824829046386296], [0.0, 0.8164965809277261]]
R: [[1.4142135623730951, 0.7071067811865475], [0.0, 1.224744871391589]]
Orthogonality / reconstruction checks: True True
Duplicate-column guard: Dependent or unresolved column: do not normalise zero

交付:两目标、投影和残差条件,再给两列分解形状及重构。解释为何极小舍入点积与精确正交定理相容。

实验 B QR 拟合与最小范数族

用约化 QR 和库拟合三记录,显式核对残差垂直。重复 x 特征,预测权重族,验证最小范数代表垂直零方向。单独查看残差汇总和实际残差。

下载 lab2_qr_and_minimum_norm.py

"""A unique fitted vector may have an affine family of minimising weights."""
import numpy as np
np.set_printoptions(precision=6, suppress=True)
x = np.array([0., 1., 2.])
X = np.column_stack((np.ones(3), x))
y = np.array([1., 2., 2.])
Q, R = np.linalg.qr(X, mode="reduced")
w_qr = np.linalg.solve(R, Q.T@y)
w_library, returned_residuals, rank, values = np.linalg.lstsq(X, y, rcond=None)
residual = y-X@w_qr
assert np.allclose(w_qr, [7/6, 1/2]) and np.allclose(w_qr, w_library)
assert np.allclose(X.T@residual, 0)
print("X / Q / R shapes:", X.shape, Q.shape, R.shape)
print("QR / library weights:", w_qr, w_library)
print("Fitted values / residual:", X@w_qr, residual)
print("Residual sum of squares:", residual@residual)
print("Normal-equation check:", np.allclose(X.T@residual, 0))

duplicate = np.column_stack((np.ones(3), x, x))
w_min, library_residuals, duplicate_rank, _ = np.linalg.lstsq(duplicate, y, rcond=None)
null = np.array([0., -1., 1.])
alternative = w_min + 2*null
assert np.allclose(w_min, [7/6, 1/4, 1/4])
assert np.allclose(duplicate@alternative, duplicate@w_min)
assert np.isclose(w_min@null, 0)
assert np.allclose(np.linalg.pinv(duplicate)@y, w_min)
print("Duplicate design rank / minimum-norm weights:", duplicate_rank, w_min)
print("Alternative weights / same fit:", alternative, np.allclose(duplicate@alternative, duplicate@w_min))
print("Squared norms:", w_min@w_min, alternative@alternative)
print("Rank-deficient returned residuals:", library_residuals.tolist())
print("Explicit rank-deficient SSE:", np.linalg.norm(y-duplicate@w_min)**2)
assert library_residuals.size == 0 and np.linalg.norm(y-duplicate@w_min) > 0
print("An empty library residual array does not assert a zero actual residual.")
输出
X / Q / R shapes: (3, 2) (3, 2) (2, 2)
QR / library weights: [1.166667 0.5     ] [1.166667 0.5     ]
Fitted values / residual: [1.166667 1.666667 2.166667] [-0.166667  0.333333 -0.166667]
Residual sum of squares: 0.16666666666666674
Normal-equation check: True
Duplicate design rank / minimum-norm weights: 2 [1.166667 0.25     0.25    ]
Alternative weights / same fit: [ 1.166667 -1.75      2.25    ] True
Squared norms: 1.4861111111111098 9.48611111111111
Rank-deficient returned residuals: []
Explicit rank-deficient SSE: 0.1666666666666668
An empty library residual array does not assert a zero actual residual.

交付:唯一预测向量、完整等价系数族、最小范数成员、SSE。解释空秩亏汇总为何不意味着全部记录精确拟合。

实验 C 格拉姆舍入与目标敏感性

运行前写精确格拉姆矩阵,比较舍入矩阵、QR 与库权重,再沿弱方向扰动目标,测系数变化与残差。捕获正规方程结果针对本基线,其他算术后端可能返回不准系数而非同一异常。

下载 lab3_gram_rounding.py

"""Forming a Gram matrix can erase a weak direction; QR cannot cure noisy data."""
import numpy as np
np.set_printoptions(precision=9, suppress=True)
delta = 1e-8
X = np.array([[1., 1.], [1., 1.+delta], [1., 1.-delta]])
truth = np.array([1., 2.])
y = X@truth
gram = X.T@X
Q, R = np.linalg.qr(X, mode="reduced")
w_qr = np.linalg.solve(R, Q.T@y)
w_library, _, rank, _ = np.linalg.lstsq(X, y, rcond=None)
print("Rounded Gram matrix:", gram.tolist())
print("QR / library weights:", w_qr, w_library)
print("Library rank / condition number of X:", rank, format(np.linalg.cond(X), ".6e"))
assert rank == 2 and np.allclose(w_qr, truth, atol=1e-6)
try:
    w_normal = np.linalg.solve(gram, X.T@y)
except np.linalg.LinAlgError:
    print("Normal equations: singular after Gram rounding")
else:
    print("Normal-equation weights / coefficient error:", w_normal, np.linalg.norm(w_normal-truth))
perturbed = y + np.array([0., delta, -delta])
changed = np.linalg.solve(R, Q.T@perturbed)
print("Target perturbation norm:", format(np.linalg.norm(perturbed-y), ".6e"))
print("QR weights after target perturbation:", changed)
print("Weight change norm:", format(np.linalg.norm(changed-w_qr), ".6e"))
print("Perturbed residual norm:", format(np.linalg.norm(perturbed-X@changed), ".6e"))
assert np.linalg.norm(changed-w_qr) > 1
assert np.linalg.norm(perturbed-X@changed) < 1e-12
print("A stable algorithm avoids avoidable Gram damage; a tiny residual does not guarantee insensitive coefficients.")
输出
Rounded Gram matrix: [[3.0, 3.0], [3.0, 3.0]]
QR / library weights: [0.99999999 2.00000001] [1.000000011 1.999999989]
Library rank / condition number of X: 2 2.449490e+08
Normal equations: singular after Gram rounding
Target perturbation norm: 1.414214e-08
QR weights after target perturbation: [0.000000001 2.999999999]
Weight change norm: 1.414214e+00
Perturbed residual norm: 4.440892e-16
A stable algorithm avoids avoidable Gram damage; a tiny residual does not guarantee insensitive coefficients.

交付:区分可避免的格拉姆舍入损伤与设计对目标变化的内在敏感。稳定求解器避免前者,不能消除后者。说明小残差实际证明什么。

10

练习与完整解答

练习 1–12 必做,13–14 额外 35 分钟。除标注加权外均用欧几里得内积,残差为 y−Xw。

练习 1★★★计算6 分钟

将 (3,2) 投影到 span{(1,1)},求残差及平方长度。

查看解答

c=5/2,p=(5/2,5/2),r=(1/2,−1/2),‖r‖²=1/2,残差与 (1,1) 点积零。其他 (a,a) 平方误差为 1/2+2(a−5/2)²,证明所示最小。

练习 2★★★计算6 分钟

Q=(1,0,0) 为一条单位列,求 QᵀQ、QQᵀ 和 (2,3,4) 的投影。

查看解答

QᵀQ 为 1×1 单位矩阵,QQᵀ=diag(1,0,0),投影 (2,0,0),残差 (0,3,4) 垂直直线。一维投影不是 3×3 恒等矩阵。

练习 3★★★计算6 分钟

a₁=(1,1,0),a₂=(1,0,1) 正交化,求第一移除系数和第二余量。

查看解答

q₁=(1,1,0)/√2,系数 1/√2,v₂=a₂−(1/2,1/2,0)=(1/2,−1/2,1),平方长度 3/2,q₂=(1,−1,2)/√6。与 q₁ 点积零,长度一。

练习 4★★★计算6 分钟

满列秩 X 为 7×3、y 为单目标,给约化 Q,R,Qᵀy,w,p 形状及求解式。

查看解答

Q 为 7×3,R 为 3×3,Qᵀy 和 w 长三,p=Xw 长七。回代解 Rw=Qᵀy。QᵀQ=I₃,QQᵀ 是秩三的 7×7 投影。

练习 5★★★proof15 分钟

不求导,从残差垂直证明子空间投影为唯一最近点。

查看解答

p∈S,r=y−p 垂直 S。任意 s∈S 的 p−s 也在 S,所以 ‖y−s‖²=‖r‖²+‖p−s‖²≥‖r‖²。正定使等号仅在 s=p,唯一。取标准正交基 Q,p=QQᵀy 给存在,Qᵀr=0 核对垂直。

练习 6★★★proof15 分钟

用标量变化与正交展开证明不受约束最小二乘的正规方程必要与充分。

查看解答

若 a_jᵀr≠0,改第 j 权重 t=(a_jᵀr)/‖a_j‖²,使目标降低 (a_jᵀr)²/‖a_j‖²,矛盾,所以各列积零。反过来 Xᵀr=0 时 rᵀXh=0,F(w+h)=F(w)+‖Xh‖²≥F(w),等号恰在零方向。无需求导或满秩假设。

练习 7★★★proof15 分钟

证明秩亏最小二乘族在行空间有唯一最小欧几里得范数成员。

查看解答

分解 w₀=u+k 为行与零成分,Xu=Xw₀。全部等价最小化者是 u+n。两空间垂直,‖u+n‖²=‖u‖²+‖n‖²,正定使 n=0 唯一最小。这是额外代表规则,不是原最小二乘权重唯一。

练习 8★★★application13 分钟

拟合 (0,1),(1,2),(2,2) 的 y≈w₀+w₁x,给残差、SSE、两个正规检查。

查看解答

XᵀX=[[3,3],[3,5]],Xᵀy=(5,6),解 w₁=1/2,w₀=7/6。预测 (7/6,5/3,13/6),残差 (−1/6,1/3,−1/6),SSE=1/36+1/9+1/36=1/6。残差和零,x 加权和 1/3−2/6=0,满列秩使权重唯一。

练习 9★★★application13 分钟

W=diag(4,1) 下将 (3,2) 投影到 span{(1,1)},比较加权与普通残差垂直。

查看解答

c=(12+2)/(4+1)=14/5,p=(14/5,14/5),r=(1/5,−4/5)。加权积 4/5−4/5=0,普通积 −3/5。它最小化 4(3−a)²+(2−a)²,欧几里得点 (5/2,5/2) 解的是另一目标。

练习 10★★★application13 分钟

重复练习 8 的 x 列,给全部最小化权重并推导最小范数者。

查看解答

族为 (7/6,t,1/2−t),只辨识重复系数之和。范数平方 (7/6)²+1/8+2(t−1/4)²,最小在 t=1/4,故 (7/6,1/4,1/4)。零方向 (0,−1,1) 垂直该代表。所有成员同预测、SSE=1/6。

练习 11★★★diagnosis16 分钟

散点图把竖直残差标成垂直拟合直线,并说每个最小二乘残差和零。修正。

查看解答

正交是 Rᵐ 的 r 垂直 C(X),不是 x–y 图中每段几何。残差和零要求设计含全一截距。无截距时取 X=[[1],[2]],y=(1,0),系数 1/5,残差 (4/5,−2/5),Xᵀr=0 但和 2/5。因此最优条件不自动保证所有设计残差和零。

练习 12★★★diagnosis16 分钟

程序把空残差汇总说成精确拟合,在弱方向设计仍形成 XᵀX,并把小残差说成鲁棒系数恢复。给三修正。

查看解答

显式算 y−Xw 及 SSE;实验 B 秩亏空汇总仍 SSE=1/6。用 QR 或合适最小二乘求解器避免格拉姆损伤,实验 C 的 δ 差在格拉姆进入为 δ²,可能消失。最后单独扰动数据分析条件性:QR 残差仍小,目标范数变化约 1.4×10⁻⁸ 时权重约变 (−1,1)。算法选择不证明数据不敏感。

练习 13★★★extension15 分钟

求 y=(3,0) 到仿射线 (1,0)+span{(1,1)} 的最近点,并证明平移规则。

查看解答

平移目标 y−p₀=(2,0),对角投影 (1,1),加 p₀ 得 (2,1),残差 (1,−1)。任意候选 p₀+s 满足 ‖y−(p₀+s)‖=‖(y−p₀)−s‖,子空间最近点定理证明规则与唯一。

练习 14★★★extension20 分钟

证明两个正交投影乘积不一定正交投影,并证明可交换时投影到交集。

查看解答

P=[[1,0],[0,0]],Q=(1/2)[[1,1],[1,1]] 都对称幂等。PQ=(1/2)[[1,1],[0,0]] 不对称也不幂等,不是正交投影。若可交换,(PQ)ᵀ=QP=PQ,(PQ)²=P²Q²=PQ。PQy 被 P、Q 都固定,所以在两像交集;反过来被两者固定的向量也被 PQ 固定。因此其像为交集,对称幂等保证垂直残差分解。

11

十题自测

1
非零 u 下,y 到 span{u} 的投影为?
2
Q 为 m×d 标准正交列,d<m,QQᵀ 是什么?
3
格拉姆–施密特余量精确为零,说明什么?
4
哪个约化 QR 方程解满列秩最小二乘?
5
正规方程对残差 r=y−Xw 声称什么?
6
不受约束最小二乘何时权重唯一?
7
最小欧几里得范数代表如何选择?
8
秩亏库返回空残差汇总,应该检查什么?
9
QR 避免近共线设计的格拉姆舍入后,还可能什么?
查看答案

投影 p∈C(X) 给 y−Xw=(y−p)+(p−Xw) 正交和,最小要求 Xw=p。等价地 r 垂直所有列,Xᵀr=0。于是 F(w+h)=F(w)+‖Xh‖²,恰好 N(X) 的变化保持最优。权重族 w+N(X),预测唯一。将 w 分行与零成分,保留行成分;添加非零核成分严格增加平方范数。这选择最小范数代表,不使原映射单射。

12

带着问题阅读

使用作者 Mathematics for Machine Learning 配套网站的正交、投影、线性回归选段。数值约定参见官方 NumPy 1.26 QR、最小二乘、伪逆。补充本课原创证明和例子。

时间 选段与问题
时段 1 · 20 分钟 投影:哪个假设让额外距离平方非负且唯一为零?
时段 4 · 20 分钟 QR 形状、秩依赖残差返回、伪逆阈值:每次调用承诺什么?
13

检索结业任务与下一步

不看笔记推导直线投影,证明子空间唯一,构造两列 QR。不用微积分证明正规方程双向,区分拟合唯一、权重唯一和最小范数,再描述一个数值及一个建模限制。

结业任务:X=[[1],[1],[1]],y=(1,2,3) 的权重二、拟合 (2,2,2)、残差 (−1,0,1)、SSE 二,残差与设计列点积零。重复列后权重 (t,2−t),最小范数 (1,1)。解释预测为何没变,以及二者为何都不保证未来数据。

进入下一课:能先识别空间、目标与算法再解释拟合。模块 13 讲特征值和二次型,模块 14 推导奇异值与计算伪逆。开放状态见课程概览。

14

记法与双语术语

术语或记法 含义 English
内积、正交 选定正定双线性几何、零积 Inner product / orthogonal
Q、QᵀQ=I 标准正交列、坐标单位矩阵 Orthonormal columns
P、p、r 投影映射、拟合向量、目标减拟合 Projection / fit / residual
格拉姆–施密特 去前成分后归一化 Gram–Schmidt
QR、R 正交三角分解、上三角因子 QR / upper triangular factor
Xᵀr=0 欧几里得最小二乘最优 Normal equations
SSE 残差平方和 Sum of squared residuals
最小范数、X⁺ 额外系数标准、伪逆 Minimum norm / pseudoinverse
敏感性、稳定性 数据响应、算法误差行为 Sensitivity / stability