90分钟 · 100分 · 7道大题。原创自主练习，不是官方考试规格或权重预测。回答所有小问，写清计算与证明，尽量保留精确值；需要小数答案时说明舍入方法；特征向量及配对奇异向量一致反号可接受。以题面分母、定义域及平局规则为准，不可无条件求逆。本练习使用Casio fx-50FH II，可用一张双面A4参考纸；这是练习安排，不是新增官方考试规定。
配套题本 · Revision
评分用于自评；等价正确方法同分。单一算术错误后若方法正确，应保留相应方法分，不反复扣同一错误。请先读题本；以下说明条件与核对，不只列答案。
Q1. 最小二乘与响应变换 (16)
配套题本 Q1
(a) [6]
未知向量含截距与斜率；对残差平方范数求导。逐项汇总后得到矩阵，再消元求参数。正行列式证明满列秩，不能只用样本数多于参数数作理由。
未知量只有两个实数系数，所以c属于二维实向量空间；四个观测贡献四行，而不是四个待估系数。第一列全为1，是为了让每行都包含同一个截距。目标是残差平方和最小，不要求四条观测方程全部精确成立。最后一个乘积先把每个x与自己的响应相乘，再相加：−1+0+2+10=11。把第一条正规方程除以2，再将所得b代入第二条即可消元。最后应写出对新x返回响应的拟合函数，不能只列两个系数。
M = ( 1 − 1 1 0 1 1 1 2 ) , y = ( 1 2 2 5 ) , c = ( a b ) . ∇ c ∥ y − M c ∥ 2 = 2 M T ( M c − y ) = 0. ∑ x i = 2 , ∑ x i 2 = 6 , ∑ y i = 10 , ∑ x i y i = 11. ( 4 2 2 6 ) ( a b ) = ( 10 11 ) , 2 a + b = 5 , 10 b = 12. a ^ = 19 10 , b ^ = 6 5 , det ( M T M ) = 20 > 0. c ∈ R 2 , M ∈ R 4 × 2 , y ^ ( x ) = 19 10 + 6 5 x . \begin{gathered}
M=\begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix},\quad y=\begin{pmatrix}1\\2\\2\\5\end{pmatrix},\quad c=\binom ab.
\\ \nabla_c\|y-Mc\|^2=2M^T(Mc-y)=0.
\\ \sum x_i=2,\quad\sum x_i^2=6,\quad\sum y_i=10,\quad\sum x_iy_i=11.
\\ \begin{pmatrix}4&2\\2&6\end{pmatrix}\binom ab=\binom{10}{11},\quad 2a+b=5,\quad 10b=12.
\\ \widehat a=\frac{19}{10},\quad\widehat b=\frac65,\quad\det(M^TM)=20>0.
\\ c\in\mathbb R^2,\quad M\in\mathbb R^{4\times2},\quad \widehat y(x)=\frac{19}{10}+\frac65x.
\end{gathered} M = 1 1 1 1 − 1 0 1 2 , y = 1 2 2 5 , c = ( b a ) . ∇ c ∥ y − M c ∥ 2 = 2 M T ( M c − y ) = 0. ∑ x i = 2 , ∑ x i 2 = 6 , ∑ y i = 10 , ∑ x i y i = 11. ( 4 2 2 6 ) ( b a ) = ( 11 10 ) , 2 a + b = 5 , 10 b = 12. a = 10 19 , b = 5 6 , det ( M T M ) = 20 > 0. c ∈ R 2 , M ∈ R 4 × 2 , y ( x ) = 10 19 + 5 6 x . 评分： 设计与目标2；方程及乘积2；系数1；唯一性1。
配套题本 Q1(a)
(b) [6]
逐点代入再以观测减预测。两条内积为零不代表每个残差为零。自由截距使训练均值常数模型可行；OLS最小化同一训练RSS，故不差于该基线。也可用残差与中心化预测正交证明；不能直接推广到测试集、无截距或变换响应目标。
TSS围绕观测均值计算，不是围绕拟合值。先从1、2、2、5逐个减去5/2，再平方，四项如下。几何核对时，在中心化响应中加减拟合向量。残差既垂直于常数列，也垂直于任何拟合向量Mc，因此亦垂直于中心化拟合向量；这样才能对两个向量用勾股定理。TSS为正也不能省略：若所有响应相同，这个R²定义会除以零。此处训练R²非负，来自均值基线可行以及实际最小化的目标，而不是只要叫“回归”就成立。
y ^ = 1 10 ( 7 , 19 , 31 , 43 ) T , r = 1 10 ( 3 , 1 , − 11 , 7 ) T . 1 T r = 3 + 1 − 11 + 7 10 = 0 , x T r = − 3 − 11 + 14 10 = 0. R S S = 9 + 1 + 121 + 49 100 = 9 5 , y ˉ = 5 2 , T S S = 9 , R 2 = 1 − 9 / 5 9 = 4 5 . 0 ≤ R S S O L S ≤ R S S ( y ˉ , 0 ) = T S S , T S S = R S S + ∥ y ^ − y ˉ 1 ∥ 2 = 9 5 + 36 5 . T S S = ( − 3 / 2 ) 2 + ( − 1 / 2 ) 2 + ( − 1 / 2 ) 2 + ( 5 / 2 ) 2 = 9 + 1 + 1 + 25 4 = 9. y − y ˉ 1 = r + ( y ^ − y ˉ 1 ) , r T ( y ^ − y ˉ 1 ) = r T M c ^ − y ˉ r T 1 = 0. \begin{gathered}
\widehat y=\frac1{10}(7,19,31,43)^T,\quad r=\frac1{10}(3,1,-11,7)^T.
\\ \mathbf1^Tr=\frac{3+1-11+7}{10}=0,\quad x^Tr=\frac{-3-11+14}{10}=0.
\\ \mathrm{RSS}=\frac{9+1+121+49}{100}=\frac95,\quad\bar y=\frac52,\quad\mathrm{TSS}=9,\quad R^2=1-\frac{9/5}{9}=\frac45.
\\ 0\le\mathrm{RSS}_{\mathrm{OLS}}\le\mathrm{RSS}(\bar y,0)=\mathrm{TSS},\qquad
\mathrm{TSS}=\mathrm{RSS}+\|\widehat y-\bar y\mathbf1\|^2=\frac95+\frac{36}5.
\\ \mathrm{TSS}=(-3/2)^2+(-1/2)^2+(-1/2)^2+(5/2)^2=\frac{9+1+1+25}{4}=9.\\y-\bar y\mathbf1=r+(\widehat y-\bar y\mathbf1),\quad r^T(\widehat y-\bar y\mathbf1)=r^TM\widehat c-\bar y r^T\mathbf1=0.
\end{gathered} y = 10 1 ( 7 , 19 , 31 , 43 ) T , r = 10 1 ( 3 , 1 , − 11 , 7 ) T . 1 T r = 10 3 + 1 − 11 + 7 = 0 , x T r = 10 − 3 − 11 + 14 = 0. RSS = 100 9 + 1 + 121 + 49 = 5 9 , y ˉ = 2 5 , TSS = 9 , R 2 = 1 − 9 9/5 = 5 4 . 0 ≤ RSS OLS ≤ RSS ( y ˉ , 0 ) = TSS , TSS = RSS + ∥ y − y ˉ 1 ∥ 2 = 5 9 + 5 36 . TSS = ( − 3/2 ) 2 + ( − 1/2 ) 2 + ( − 1/2 ) 2 + ( 5/2 ) 2 = 4 9 + 1 + 1 + 25 = 9. y − y ˉ 1 = r + ( y − y ˉ 1 ) , r T ( y − y ˉ 1 ) = r T M c − y ˉ r T 1 = 0. 评分： 残差1；RSS1；TSS及R²2；正交1；基线或分解证明1。
配套题本 Q1(b)
(c) [4]
指数模型使用实对数，观测及A、B必须为正；拟合截距与斜率取指数还原。倒数模型要求观测非零，预测分母也须非零；其系数无需反变换。两者一般均不保证原尺度RSS最小；精确插值可能两者一致，但不是普遍保证。
指数模型中，输入x和设计矩阵的列不变；改变的是响应向量，变成(0,log2,log2,log5)。指数逆变换还原A与B，但不能把已经优化的对数误差自动改称原尺度误差。倒数模型中α、β本来就是原参数，无需再指数化；只在输出预测时取倒数。最小二乘本身不负责保证未来分母远离零。特殊的精确插值情形下，两种尺度的最优解可能重合；一次重合不能证明一般等价。
z i = log y i , θ 0 = log A , θ 1 = log B , min θ ∑ i ( log y i − θ 0 − θ 1 x i ) 2 , A = e θ 0 , B = e θ 1 . z = ( 0 , log 2 , log 2 , log 5 ) T , M = ( 1 − 1 1 0 1 1 1 2 ) . t i = 1 / y i , N = ( 1 e 1 1 1 e − 1 1 e − 2 ) , t = ( 1 , 1 / 2 , 1 / 2 , 1 / 5 ) T , min α , β ∑ i ( 1 / y i − α − β e − x i ) 2 , y ^ ( x ) = 1 α + β e − x . \begin{gathered}
z_i=\log y_i,\quad\theta_0=\log A,\quad\theta_1=\log B,\quad
\min_\theta\sum_i(\log y_i-\theta_0-\theta_1x_i)^2,\quad A=e^{\theta_0},\ B=e^{\theta_1}.
\\ z=(0,\log2,\log2,\log5)^T,\quad M=\begin{pmatrix}1&-1\\1&0\\1&1\\1&2\end{pmatrix}.
\\ t_i=1/y_i,\quad N=\begin{pmatrix}1&e\\1&1\\1&e^{-1}\\1&e^{-2}\end{pmatrix},\quad t=(1,1/2,1/2,1/5)^T,
\\ \min_{\alpha,\beta}\sum_i(1/y_i-\alpha-\beta e^{-x_i})^2,\qquad \widehat y(x)=\frac1{\alpha+\beta e^{-x}}.
\end{gathered} z i = log y i , θ 0 = log A , θ 1 = log B , θ min i ∑ ( log y i − θ 0 − θ 1 x i ) 2 , A = e θ 0 , B = e θ 1 . z = ( 0 , log 2 , log 2 , log 5 ) T , M = 1 1 1 1 − 1 0 1 2 . t i = 1/ y i , N = 1 1 1 1 e 1 e − 1 e − 2 , t = ( 1 , 1/2 , 1/2 , 1/5 ) T , α , β min i ∑ ( 1/ y i − α − β e − x i ) 2 , y ( x ) = α + β e − x 1 . 评分： 每模型2分，须含变换与矩阵、实际目标、定义域及还原。
配套题本 Q1(c)
Q2. 标准化、ridge与LASSO (18)
配套题本 Q2
(a) [4]
先取四数均值，偏差平方和除4再开平方。三栏两两正交，平方范数都是4；总体方差为1不等于栏范数为1。
均值要把各特征的四个观测相加后除以4。两个特征的偏差都包含两个−2和两个+2，因此总体方差为16/4=4，标准差是2。每个中心化观测除以2，才得到所列±1列。方差为1的列，其平方范数是样本数n，而不是1。不同设计列的内积因正负贡献抵消而为零。Mᵀy第二个分量是−1−3+5+11=12，可同时检查行序与乘法是否正确。
μ u = 4 , μ v = 12 , s u = s v = ( 4 + 4 + 4 + 4 ) / 4 = 2. M = ( 1 − 1 − 1 1 − 1 1 1 1 − 1 1 1 1 ) , M T M = 4 I 3 , M T y = ( 20 , 12 , 8 ) T . μ u = 2 + 2 + 6 + 6 4 = 4 , μ v = 10 + 14 + 10 + 14 4 = 12 , s u = ( − 2 ) 2 + ( − 2 ) 2 + 2 2 + 2 2 4 = 2 = s v . \begin{gathered}
\mu_u=4,\quad\mu_v=12,\quad s_u=s_v=\sqrt{(4+4+4+4)/4}=2.
\\ M=\begin{pmatrix}1&-1&-1\\1&-1&1\\1&1&-1\\1&1&1\end{pmatrix},\quad M^TM=4I_3,\quad M^Ty=(20,12,8)^T.
\\ \mu_u=\frac{2+2+6+6}{4}=4,\quad\mu_v=\frac{10+14+10+14}{4}=12,\quad s_u=\sqrt{\frac{(-2)^2+(-2)^2+2^2+2^2}{4}}=2=s_v.
\end{gathered} μ u = 4 , μ v = 12 , s u = s v = ( 4 + 4 + 4 + 4 ) /4 = 2. M = 1 1 1 1 − 1 − 1 1 1 − 1 1 − 1 1 , M T M = 4 I 3 , M T y = ( 20 , 12 , 8 ) T . μ u = 4 2 + 2 + 6 + 6 = 4 , μ v = 4 10 + 14 + 10 + 14 = 12 , s u = 4 ( − 2 ) 2 + ( − 2 ) 2 + 2 2 + 2 2 = 2 = s v . 评分： 统计量1；矩阵1；两个乘积各1。
配套题本 Q2(a)
(b) [6]
惩罚矩阵截距位置必须为零；求导两项各带2。所得对角系统正定，解唯一。代入标准化定义还原截距，不能保留标准化截距。在(6,14)两式均得15/2。此处共同缩小一半依赖正交栏且范数相同。
D的截距位置为0，两个斜率位置才为1。平方损失求导带因子2，4βᵀDβ求导为8Dβ；必须把整条方程除以2，不能只除损失项。最后对角系数4、8、8均为正，目标严格凸，解唯一。还原单位时，把两条标准化定义代入整个仿射表达式，再合并常数；两个中心化特征都会贡献常数，所以原截距不再是5。可选一个点在两套坐标下独立验算。此处斜率恰缩为一半，只因两列正交且平方范数都为4；相关特征不能逐坐标套用这个捷径。
D = diag ( 0 , 1 , 1 ) , 2 M T ( M β − y ) + 8 D β = 0 , ( M T M + 4 D ) β ^ = M T y , diag ( 4 , 8 , 8 ) β ^ = ( 20 , 12 , 8 ) T , β ^ = ( 5 , 3 / 2 , 1 ) T , y ^ = 5 + 3 2 u − 4 2 + v − 12 2 = − 4 + 3 4 u + 1 2 v . y ^ = 5 + 3 2 u − 4 2 + v − 12 2 = 5 − 3 − 6 + 3 4 u + 1 2 v = − 4 + 3 4 u + 1 2 v . ( u , v ) = ( 6 , 14 ) : 5 + 3 2 + 1 = 15 2 = − 4 + 9 2 + 7. 4 4 + 4 = 1 2 . \begin{gathered}
D=\operatorname{diag}(0,1,1),\quad2M^T(M\beta-y)+8D\beta=0,
\\(M^TM+4D)\widehat\beta=M^Ty,\quad\operatorname{diag}(4,8,8)\widehat\beta=(20,12,8)^T,
\\\widehat\beta=(5,3/2,1)^T,\qquad\widehat y=5+\frac32\frac{u-4}{2}+\frac{v-12}{2}=-4+\frac34u+\frac12v.
\\ \widehat y=5+\frac32\frac{u-4}{2}+\frac{v-12}{2}=5-3-6+\frac34u+\frac12v=-4+\frac34u+\frac12v.\\(u,v)=(6,14):\quad 5+\frac32+1=\frac{15}{2}=-4+\frac92+7.\\\frac{4}{4+4}=\frac12.
\end{gathered} D = diag ( 0 , 1 , 1 ) , 2 M T ( Mβ − y ) + 8 D β = 0 , ( M T M + 4 D ) β = M T y , diag ( 4 , 8 , 8 ) β = ( 20 , 12 , 8 ) T , β = ( 5 , 3/2 , 1 ) T , y = 5 + 2 3 2 u − 4 + 2 v − 12 = − 4 + 4 3 u + 2 1 v . y = 5 + 2 3 2 u − 4 + 2 v − 12 = 5 − 3 − 6 + 4 3 u + 2 1 v = − 4 + 4 3 u + 2 1 v . ( u , v ) = ( 6 , 14 ) : 5 + 2 3 + 1 = 2 15 = − 4 + 2 9 + 7. 4 + 4 4 = 2 1 . 评分： D与求导2；方程系数2；完整还原2。
配套题本 Q2(b)
(c) [5]
中心化特征令未罚截距等于响应均值；正交性消去斜率交叉项。正分支要求h>τ，负分支要求h<−τ；零点左导数非正、右导数非负，故边界也归零。第二斜率精确为零；整体目标乘2才保持解。残差相关性核对：正系数达阈值，零系数未越阈值。
特征列中心化后，不受惩罚的截距方程不再含斜率，因此截距等于响应均值。列正交又消去两斜率的交叉项；若不正交，就不能分别求两个一维最优解。零分支不能靠在零点对绝对值普通求导得到，而应要求左导数不正、右导数不负。正系数的特征与残差相关量应等于正阈值；零系数的相关量可处在阈值区间内任一点。残差核对因此同时检查了尖点条件与普通导数条件。整个目标乘正数才保持最小点不变；只改变平方损失系数会改变相对惩罚。
d = m T m > 0 , h = m T r , 1 2 ∥ r − m t ∥ 2 + τ ∣ t ∣ = d 2 t 2 − h t + τ ∣ t ∣ + constant . t > 0 : d t − h + τ = 0 ⟹ t = ( h − τ ) / d ( h > τ ) . t < 0 : d t − h − τ = 0 ⟹ t = ( h + τ ) / d ( h < − τ ) . t ∗ = S ( h , τ ) d , S ( h , τ ) = { h − τ h > τ , 0 ∣ h ∣ ≤ τ , h + τ h < − τ . − h − τ ≤ 0 ≤ − h + τ ⟺ ∣ h ∣ ≤ τ . β ^ 0 = 5 , β ^ 1 = S ( 12 , 10 ) 4 = 1 2 , β ^ 2 = S ( 8 , 10 ) 4 = 0. 1 2 R S S + 10 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) ⟷ R S S + 20 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) . r = ( − 7 / 2 , − 3 / 2 , − 1 / 2 , 11 / 2 ) T , 1 T r = 0 , z 1 T r = 10 , z 2 T r = 8. \begin{gathered}
d=m^Tm>0,\quad h=m^Tr,\quad\tfrac12\|r-mt\|^2+\tau|t|=\tfrac d2t^2-ht+\tau|t|+\text{constant}.
\\t>0:\quad dt-h+\tau=0\Longrightarrow t=(h-\tau)/d\quad(h>\tau).
\\t<0:\quad dt-h-\tau=0\Longrightarrow t=(h+\tau)/d\quad(h<-\tau).
\\ t^*=\frac{S(h,\tau)}d,\qquad S(h,\tau)=\begin{cases}h-\tau&h>\tau,\\0&|h|\le\tau,\\h+\tau&h<-\tau.\end{cases}
\\ -h-\tau\le0\le-h+\tau\ \Longleftrightarrow\ |h|\le\tau.
\\ \widehat\beta_0=5,\quad\widehat\beta_1=\frac{S(12,10)}4=\frac12,\quad\widehat\beta_2=\frac{S(8,10)}4=0.
\\ \tfrac12\mathrm{RSS}+10(|\beta_1|+|\beta_2|)\ \longleftrightarrow\ \mathrm{RSS}+20(|\beta_1|+|\beta_2|).
\\r=(-7/2,-3/2,-1/2,11/2)^T,\quad\mathbf1^Tr=0,\ z_1^Tr=10,\ z_2^Tr=8.
\end{gathered} d = m T m > 0 , h = m T r , 2 1 ∥ r − m t ∥ 2 + τ ∣ t ∣ = 2 d t 2 − h t + τ ∣ t ∣ + constant . t > 0 : d t − h + τ = 0 ⟹ t = ( h − τ ) / d ( h > τ ) . t < 0 : d t − h − τ = 0 ⟹ t = ( h + τ ) / d ( h < − τ ) . t ∗ = d S ( h , τ ) , S ( h , τ ) = ⎩ ⎨ ⎧ h − τ 0 h + τ h > τ , ∣ h ∣ ≤ τ , h < − τ . − h − τ ≤ 0 ≤ − h + τ ⟺ ∣ h ∣ ≤ τ . β 0 = 5 , β 1 = 4 S ( 12 , 10 ) = 2 1 , β 2 = 4 S ( 8 , 10 ) = 0. 2 1 RSS + 10 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) ⟷ RSS + 20 ( ∣ β 1 ∣ + ∣ β 2 ∣ ) . r = ( − 7/2 , − 3/2 , − 1/2 , 11/2 ) T , 1 T r = 0 , z 1 T r = 10 , z 2 T r = 8. 评分： 截距与正交1；含零分支推导2；系数1；惩罚20及理由1。
配套题本 Q2(c)
(d) [3]
全数据预处理让留出特征分布影响拟合。先划分，再仅用训练子集估计尺度；同一变换用于训练及验证；仅训练子集拟合候选，最后评分验证。汇总选参数，再全开发数据重拟合预处理及系数；最终测试集始终不参与。个别OLS的缩放不变性不能证明ridge泄漏流程正确。
验证折应模拟未见观测，所以即使没有看其响应，也不能让其特征分布参与均值和标准差的估计。顺序必须是先划分；在本折训练子集估计预处理；固定该变换用于两子集；在变换后的训练数据上拟合各候选惩罚；最后评估留出折。汇总验证误差选定惩罚后，再用整个开发训练集重新估计预处理与系数。最终测试集不参与以上任何选择。有些无惩罚OLS预测恰好对可逆缩放不变，但ridge的系数惩罚会随尺度改变；不能用一个不变的特例为泄漏流程辩护。
评分： 泄漏来源1；训练统计1；变换拟合评分顺序1。
配套题本 Q2(d)
Q3. 矩形SVD与最小范数 (18)
配套题本 Q3
(a) [6]
先算较小的AAᵀ，特征值8、4须开非负平方根，不能直接当奇异值。右向量由Aᵀu/σ配对，再补单位零空间向量。检查正交及两个外积贡献；左向量反号时配对右向量也须反号。
A有两行三列，先算AAᵀ可把问题化为较小的二阶特征值问题，而非三阶AᵀA。由(6−λ)²−4=0得到8和4，取非负平方根后才是奇异值。每个左特征向量先归一化，再用Aᵀu/σ构造配对右向量。完整分解虽只有两个正奇异值，仍需第三个右向量，它张成零空间。逐一检查尺寸：U为2×2、Σ为2×3、V为3×3。列正交还不够，要重建两个外积项，确认和为A。翻转一个左向量时必须同时翻转其配对右向量，才不会改变外积。
A A T = ( 6 2 2 6 ) , ( 6 − λ ) 2 − 4 = 0 , λ = 8 , 4. u 1 = 1 2 ( 1 1 ) , u 2 = 1 2 ( 1 − 1 ) , σ 1 = 2 2 , σ 2 = 2. v 1 = A T u 1 σ 1 = ( 1 , 0 , 0 ) T , v 2 = A T u 2 σ 2 = 1 2 ( 0 , 1 , 1 ) T , v 3 = 1 2 ( 0 , 1 , − 1 ) T . U = 1 2 ( 1 1 1 − 1 ) , Σ = ( 2 2 0 0 0 2 0 ) , V = ( 1 0 0 0 1 / 2 1 / 2 0 1 / 2 − 1 / 2 ) . U T U = I 2 , V T V = I 3 , A = ( 2 0 0 2 0 0 ) + ( 0 1 1 0 − 1 − 1 ) . det ( A A T − λ I ) = ( 6 − λ ) 2 − 4 = 0. σ 1 u 1 v 1 T = ( 2 0 0 2 0 0 ) , σ 2 u 2 v 2 T = ( 0 1 1 0 − 1 − 1 ) , A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T . \begin{gathered}
AA^T=\begin{pmatrix}6&2\\2&6\end{pmatrix},\quad(6-\lambda)^2-4=0,\quad \lambda=8,4.
\\u_1=\frac1{\sqrt2}\binom11,\ u_2=\frac1{\sqrt2}\binom1{-1},\quad\sigma_1=2\sqrt2,\ \sigma_2=2.
\\v_1=\frac{A^Tu_1}{\sigma_1}=(1,0,0)^T,\quad v_2=\frac{A^Tu_2}{\sigma_2}=\frac1{\sqrt2}(0,1,1)^T,\quad v_3=\frac1{\sqrt2}(0,1,-1)^T.
\\U=\frac1{\sqrt2}\begin{pmatrix}1&1\\1&-1\end{pmatrix},\quad\Sigma=\begin{pmatrix}2\sqrt2&0&0\\0&2&0\end{pmatrix},\quad V=\begin{pmatrix}1&0&0\\0&1/\sqrt2&1/\sqrt2\\0&1/\sqrt2&-1/\sqrt2\end{pmatrix}.
\\U^TU=I_2,\quad V^TV=I_3,\quad A=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix}+\begin{pmatrix}0&1&1\\0&-1&-1\end{pmatrix}.
\\ \det(AA^T-\lambda I)=(6-\lambda)^2-4=0.\\\sigma_1u_1v_1^T=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix},\quad\sigma_2u_2v_2^T=\begin{pmatrix}0&1&1\\0&-1&-1\end{pmatrix},\quad A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T.
\end{gathered} A A T = ( 6 2 2 6 ) , ( 6 − λ ) 2 − 4 = 0 , λ = 8 , 4. u 1 = 2 1 ( 1 1 ) , u 2 = 2 1 ( − 1 1 ) , σ 1 = 2 2 , σ 2 = 2. v 1 = σ 1 A T u 1 = ( 1 , 0 , 0 ) T , v 2 = σ 2 A T u 2 = 2 1 ( 0 , 1 , 1 ) T , v 3 = 2 1 ( 0 , 1 , − 1 ) T . U = 2 1 ( 1 1 1 − 1 ) , Σ = ( 2 2 0 0 2 0 0 ) , V = 1 0 0 0 1/ 2 1/ 2 0 1/ 2 − 1/ 2 . U T U = I 2 , V T V = I 3 , A = ( 2 2 0 0 0 0 ) + ( 0 0 1 − 1 1 − 1 ) . det ( A A T − λ I ) = ( 6 − λ ) 2 − 4 = 0. σ 1 u 1 v 1 T = ( 2 2 0 0 0 0 ) , σ 2 u 2 v 2 T = ( 0 0 1 − 1 1 − 1 ) , A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T . 评分： Gram及特征对2；奇异值配对2；零空间与完整尺寸2。
配套题本 Q3(a)
(b) [4]
伪逆交换尺寸，只倒数非零奇异值。此处满行秩使任意右端相容，因此最小二乘解也是精确解；一般伪逆问题未必如此。
伪逆交换原矩阵的行列数，所以Σ⁺是三行两列；只对两个正奇异值取倒数，绝不能对零取倒数。按VΣ⁺Uᵀ的次序相乘。A⁺乘b得到三个坐标，再代回原来两条方程，是独立的相容性检查。这里A满行秩，AA⁺是二阶单位矩阵，任何二维右端都能达到。一般矩阵的A⁺b只保证残差范数最小；要称它为精确解，必须另外确认相容性，本题确实完成了这一步。
Σ + = ( 1 / ( 2 2 ) 0 0 1 / 2 0 0 ) , A + = V Σ + U T = 1 4 ( 1 1 1 − 1 1 − 1 ) . x ∗ = 1 4 ( 6 + 2 , 6 − 2 , 6 − 2 ) T = ( 2 , 1 , 1 ) T , A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = b , A A + = I 2 . A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = ( 6 , 2 ) T = b , A A + = I 2 . \begin{gathered}
\Sigma^+=\begin{pmatrix}1/(2\sqrt2)&0\\0&1/2\\0&0\end{pmatrix},\quad A^+=V\Sigma^+U^T=\frac14\begin{pmatrix}1&1\\1&-1\\1&-1\end{pmatrix}.
\\x_*=\frac14(6+2,6-2,6-2)^T=(2,1,1)^T,\quad Ax_*=(4+1+1,4-1-1)^T=b,\quad AA^+=I_2.
\\ Ax_*=(4+1+1,\ 4-1-1)^T=(6,2)^T=b,\quad AA^+=I_2.
\end{gathered} Σ + = 1/ ( 2 2 ) 0 0 0 1/2 0 , A + = V Σ + U T = 4 1 1 1 1 1 − 1 − 1 . x ∗ = 4 1 ( 6 + 2 , 6 − 2 , 6 − 2 ) T = ( 2 , 1 , 1 ) T , A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = b , A A + = I 2 . A x ∗ = ( 4 + 1 + 1 , 4 − 1 − 1 ) T = ( 6 , 2 ) T = b , A A + = I 2 . 评分： 伪逆2；解1；回代1。
配套题本 Q3(b)
(c) [5]
原方程相加相减确定x₁与后两坐标之和。剩余变化属于零空间且与x*正交。展开范数得非负附加项，只有零变化取等号，同时证明最小及唯一；精确解不唯一不妨碍最小范数解唯一。
把原来两条方程相加，得到4x₁=8；相减，得到2x₂+2x₃=4。因此x₁=2，其余两个坐标之和为2，可用一个自由实数t参数化。这个表示覆盖全部精确解，而不是只列几个例子。与x∗之差h属于零空间，且与x∗的内积为2·0+t−t=0。先展开范数平方，再消去交叉项；非负剩余项证明最小，等号只能在t=0成立才证明唯一。几何上，伪逆解在行空间，而所有允许的位移在其正交补零空间。精确解无限多，不妨碍存在唯一的最短解。
2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 ⟹ x 1 = 2 , x 2 + x 3 = 2. x = ( 2 , 1 + t , 1 − t ) T = x ∗ + h , h = ( 0 , t , − t ) T ∈ ker A , x ∗ T h = 0. ∥ x ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 = 6 + 2 t 2 ≥ 6 , equality iff t = 0. 2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 , x 1 = 2 , x 2 + x 3 = 2. ∥ x ∗ + h ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 , x ∗ T h = 2 ⋅ 0 + t − t = 0. \begin{gathered}
2x_1+x_2+x_3=6,\quad2x_1-x_2-x_3=2\quad\Longrightarrow\quad x_1=2,\ x_2+x_3=2.
\\x=(2,1+t,1-t)^T=x_*+h,\quad h=(0,t,-t)^T\in\ker A,\quad x_*^Th=0.
\\\|x\|^2=\|x_*\|^2+2x_*^Th+\|h\|^2=6+2t^2\ge6,\qquad \text{equality iff }t=0.
\\ 2x_1+x_2+x_3=6,\quad2x_1-x_2-x_3=2,\quad x_1=2,\quad x_2+x_3=2.\\\|x_*+h\|^2=\|x_*\|^2+2x_*^Th+\|h\|^2,\quad x_*^Th=2\cdot0+t-t=0.
\end{gathered} 2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 ⟹ x 1 = 2 , x 2 + x 3 = 2. x = ( 2 , 1 + t , 1 − t ) T = x ∗ + h , h = ( 0 , t , − t ) T ∈ ker A , x ∗ T h = 0. ∥ x ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 = 6 + 2 t 2 ≥ 6 , equality iff t = 0. 2 x 1 + x 2 + x 3 = 6 , 2 x 1 − x 2 − x 3 = 2 , x 1 = 2 , x 2 + x 3 = 2. ∥ x ∗ + h ∥ 2 = ∥ x ∗ ∥ 2 + 2 x ∗ T h + ∥ h ∥ 2 , x ∗ T h = 2 ⋅ 0 + t − t = 0. 评分： 全部解2；正交1；范数1；取等唯一性1。
配套题本 Q3(c)
(d) [3]
保留最大奇异值项。残差仅一个非零奇异值，因此两范数恰好相同。四个非零条目平方和为4，但题求范数2，不是4；一般Frobenius汇总所有舍弃值平方，谱范数只取最大。
截断到秩一，是保留最大奇异值的整个外积项，不是随便保留A中的一个元素或一行。也可直接检查被舍弃矩阵：四个非零元素为±1，平方和为4，开平方才得到Frobenius范数2。谱范数是残差的最大奇异值，也为2。两者相同是因为仅余一个奇异方向；若舍弃多个方向，Frobenius合并各奇异值平方，而谱范数只取最大者，通常不同。
A 1 = σ 1 u 1 v 1 T = ( 2 0 0 2 0 0 ) , ∥ A − A 1 ∥ F = σ 2 2 = 2 , ∥ A − A 1 ∥ 2 = σ 2 = 2. \begin{gathered}
A_1=\sigma_1u_1v_1^T=\begin{pmatrix}2&0&0\\2&0&0\end{pmatrix},\quad\|A-A_1\|_F=\sqrt{\sigma_2^2}=2,\quad\|A-A_1\|_2=\sigma_2=2.
\end{gathered} A 1 = σ 1 u 1 v 1 T = ( 2 2 0 0 0 0 ) , ∥ A − A 1 ∥ F = σ 2 2 = 2 , ∥ A − A 1 ∥ 2 = σ 2 = 2. 评分： 近似1；各范数1。
配套题本 Q3(d)
Q4. 中心化PCA与重建 (15)
配套题本 Q4
(a) [4]
每行减同一均值，中心化后各栏和为零。此题分母3，不沿用前题总体分母4。
两个坐标分别求均值：第一坐标和为12，第二坐标和为4。样本按行存放，故从每行减去行向量μᵀ。中心化后两列的和都应为零，应先检查再算协方差。XcᵀXc的对角元素是各列平方和，非对角元素是逐行配对乘积之和。本题指定样本协方差，分母n−1=3；第2题的总体标准差分母却是n=4，不能因为都出现“方差”便擅自统一。
μ = ( 3 , 1 ) T , X c = X − 1 μ T = ( 2 2 − 2 − 2 1 − 1 − 1 1 ) , X c T X c = ( 10 6 6 10 ) , S = 1 3 ( 10 6 6 10 ) . μ = ( 5 + 1 + 4 + 2 4 , 3 − 1 + 0 + 2 4 ) T = ( 3 , 1 ) T . 2 2 + ( − 2 ) 2 + 1 2 + ( − 1 ) 2 = 10 , 2 ⋅ 2 + ( − 2 ) ( − 2 ) + 1 ( − 1 ) + ( − 1 ) 1 = 6. \begin{gathered}
\mu=(3,1)^T,\quad X_c=X-\mathbf1\mu^T=\begin{pmatrix}2&2\\-2&-2\\1&-1\\-1&1\end{pmatrix},\quad X_c^TX_c=\begin{pmatrix}10&6\\6&10\end{pmatrix},\quad S=\frac13\begin{pmatrix}10&6\\6&10\end{pmatrix}.
\\ \mu=\left(\frac{5+1+4+2}{4},\frac{3-1+0+2}{4}\right)^T=(3,1)^T.\\ 2^2+(-2)^2+1^2+(-1)^2=10,\quad2\cdot2+(-2)(-2)+1(-1)+(-1)1=6.
\end{gathered} μ = ( 3 , 1 ) T , X c = X − 1 μ T = 2 − 2 1 − 1 2 − 2 − 1 1 , X c T X c = ( 10 6 6 10 ) , S = 3 1 ( 10 6 6 10 ) . μ = ( 4 5 + 1 + 4 + 2 , 4 3 − 1 + 0 + 2 ) T = ( 3 , 1 ) T . 2 2 + ( − 2 ) 2 + 1 2 + ( − 1 ) 2 = 10 , 2 ⋅ 2 + ( − 2 ) ( − 2 ) + 1 ( − 1 ) + ( − 1 ) 1 = 6. 评分： 均值1；中心化1；乘积1；分母及协方差1。
配套题本 Q4(a)
(b) [6]
较大且严格不等的特征值确定主轴，符号条件确定代表向量。得分是四个标量，不是二维重建；先乘方向行向量再加均值。前两点在主轴上，后两点投影到均值。
S的对称结构提示先试(1,1)与(1,−1)两个特征方向，再归一化并比较特征值。较大特征值对应主轴；两个特征值不同，所以主轴唯一，但方向仍有正负两种，题目首坐标为正的约定才固定符号。得分向量为4×1，每项是沿主轴的一个标量坐标，不是二维重建点。把这个坐标乘回wᵀ才重建一行，再加均值行才恢复原坐标。前两个中心化点已在主轴上，完全保留；后两个与主轴垂直，得分为零，因此回到原坐标中的均值(3,1)，不是原点。
λ 1 = 16 / 3 , v 1 = 1 2 ( 1 , 1 ) T , λ 2 = 4 / 3 , v 2 = 1 2 ( 1 , − 1 ) T . w = v 1 , z = X c w = ( 2 2 , − 2 2 , 0 , 0 ) T , X ^ c = z w T = ( 2 2 − 2 − 2 0 0 0 0 ) , X ^ = ( 5 3 1 − 1 3 1 3 1 ) . \begin{gathered}
\lambda_1=16/3,\quad v_1=\frac1{\sqrt2}(1,1)^T,\quad\lambda_2=4/3,\quad v_2=\frac1{\sqrt2}(1,-1)^T.
\\w=v_1,\quad z=X_cw=(2\sqrt2,-2\sqrt2,0,0)^T,\quad\widehat X_c=zw^T=\begin{pmatrix}2&2\\-2&-2\\0&0\\0&0\end{pmatrix},\quad\widehat X=\begin{pmatrix}5&3\\1&-1\\3&1\\3&1\end{pmatrix}.
\end{gathered} λ 1 = 16/3 , v 1 = 2 1 ( 1 , 1 ) T , λ 2 = 4/3 , v 2 = 2 1 ( 1 , − 1 ) T . w = v 1 , z = X c w = ( 2 2 , − 2 2 , 0 , 0 ) T , X c = z w T = 2 − 2 0 0 2 − 2 0 0 , X = 5 1 3 3 3 − 1 1 1 . 评分： 特征对2；得分2；重建加均值2。
配套题本 Q4(b)
(c) [5]
每个中心化样本分为q方向投影与正交残差，逐行用勾股并求和，利用q单位范数得到恒等式。总能量固定，等价最大化Rayleigh商；在特征基展开证明最大值和等号条件。所求是总平方误差，不是开方或按样本平均。
总方差是S的迹，因此用保留特征值除以两个特征值之和。重建残差前两行为零，后两行为(1,−1)与(−1,1)，长度平方相加为4。这是总平方误差，不是平均后的1，也不是开平方后的2。用舍弃特征值核对时，要乘n−1，因为S采用了这个分母。一般恒等式先把每个中心化样本投影到单位向量q；由qᵀq=1，减去投影后的残差与q正交。勾股定理把每点长度平方拆成投影能量与残差能量；q为单位向量又保证投影向量长度平方等于其标量得分平方。对样本求和，用(n−1)S替换XcᵀXc，再移项。中心化总能量固定，所以最小残差等价于最大qᵀSq。最后在正交特征基展开q，才能证明最大值为λ₁，且特征值不同时等号只在±v₁成立。中心化和单位长度约束都不能删去。
λ 1 λ 1 + λ 2 = 4 5 , ∥ X − X ^ ∥ F 2 = 0 + 0 + 2 + 2 = 4 = ( n − 1 ) λ 2 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i ) ] , q T [ x c , i − q ( q T x c , i ) ] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 = ( n − 1 ) q T S q . q = a v 1 + b v 2 , a 2 + b 2 = 1 ⟹ q T S q = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 , equality iff q = ± v 1 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i ) ] , q T [ x c , i − q ( q T x c , i ) ] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 . q = a v 1 + b v 2 , a 2 + b 2 = 1 , q T S q = λ 1 a 2 + λ 2 b 2 = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 . \begin{gathered}
\frac{\lambda_1}{\lambda_1+\lambda_2}=\frac45,\quad\|X-\widehat X\|_F^2=0+0+2+2=4=(n-1)\lambda_2.
\\x_{c,i}=q(q^Tx_{c,i})+[x_{c,i}-q(q^Tx_{c,i})],\quad q^T[x_{c,i}-q(q^Tx_{c,i})]=0.
\\\|X_c\|_F^2=\|X_cqq^T\|_F^2+\|X_c-X_cqq^T\|_F^2,\quad \|X_cqq^T\|_F^2=\|X_cq\|^2=(n-1)q^TSq.
\\ q=av_1+bv_2,\ a^2+b^2=1\quad\Longrightarrow\quad q^TSq=\lambda_1-(\lambda_1-\lambda_2)b^2\le\lambda_1,
\quad\text{equality iff }q=\pm v_1.
\\ x_{c,i}=q(q^Tx_{c,i})+[x_{c,i}-q(q^Tx_{c,i})],\quad q^T[x_{c,i}-q(q^Tx_{c,i})]=0.\\\|X_c\|_F^2=\|X_cqq^T\|_F^2+\|X_c-X_cqq^T\|_F^2,\quad\|X_cqq^T\|_F^2=\|X_cq\|^2.\\q=av_1+bv_2,\quad a^2+b^2=1,\quad q^TSq=\lambda_1a^2+\lambda_2b^2=\lambda_1-(\lambda_1-\lambda_2)b^2\le\lambda_1.
\end{gathered} λ 1 + λ 2 λ 1 = 5 4 , ∥ X − X ∥ F 2 = 0 + 0 + 2 + 2 = 4 = ( n − 1 ) λ 2 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i )] , q T [ x c , i − q ( q T x c , i )] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 = ( n − 1 ) q T Sq . q = a v 1 + b v 2 , a 2 + b 2 = 1 ⟹ q T Sq = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 , equality iff q = ± v 1 . x c , i = q ( q T x c , i ) + [ x c , i − q ( q T x c , i )] , q T [ x c , i − q ( q T x c , i )] = 0. ∥ X c ∥ F 2 = ∥ X c q q T ∥ F 2 + ∥ X c − X c q q T ∥ F 2 , ∥ X c q q T ∥ F 2 = ∥ X c q ∥ 2 . q = a v 1 + b v 2 , a 2 + b 2 = 1 , q T Sq = λ 1 a 2 + λ 2 b 2 = λ 1 − ( λ 1 − λ 2 ) b 2 ≤ λ 1 . 评分： 比例1；总误差1；正交恒等式2；特征值论证1。
配套题本 Q4(c)
Q5. Gonzalez最远优先与近似保证 (12)
配套题本 Q5
(a) [4]
只有中心0时最远点为12。每点先取到两个中心距离的较小者，再对样本取最大；不能交换最小与最大。最差服务距离来自点7。
只有中心0时，各点非负，到中心的距离恰为其坐标，所以选12；不能改成相对于其他任意参照点最远。加上12后，最近中心分组为{0,2,3}与{7,10,12}。点7到两中心的距离为7与5，取较小的5；六个最近距离中的最大者于是为5。这是k-center最大服务半径，不是距离和或平方误差和。
c 2 = 12 , x 0 2 3 7 10 12 ∣ x ∣ 0 2 3 7 10 12 ∣ x − 12 ∣ 12 10 9 5 2 0 d ( x , C ) 0 2 3 5 2 0 , R G = 5. \begin{gathered}
c_2=12,\qquad\begin{array}{c|rrrrrr}x&0&2&3&7&10&12\\|x|&0&2&3&7&10&12\\|x-12|&12&10&9&5&2&0\\d(x,C)&0&2&3&5&2&0\end{array},\quad R_G=5.
\end{gathered} c 2 = 12 , x ∣ x ∣ ∣ x − 12∣ d ( x , C ) 0 0 12 0 2 2 10 2 3 3 9 3 7 7 5 5 10 10 2 2 12 12 0 0 , R G = 5. 评分： 中心1；距离表2；半径1。
配套题本 Q5(a)
(b) [3]
所选中心覆盖两个区间。下界只看0、7、12，两两至少相距5；两个覆盖球必有一球容纳其中两点，三角不等式迫使半径至少5/2，与构造相同。若限制比较中心为样本点，就是另一问题。
可行构造只给未知最优值的上界，本身还不证明最优。区间[0,3]以3/2为中心只需半径3/2；区间[7,12]以19/2为中心需半径5/2。两簇共同半径可取5/2，不要求第一簇也达到它。下界所用三点0、7、12的两两距离为7、12、5。两个球覆盖三点，必有一对同球；若半径小于5/2，三角不等式会使同球两点间距小于5，矛盾。下界与构造上界相等才证明最优；5/(5/2)=2则说明近似界确实可以达到。
c 1 ∗ = 3 / 2 , c 2 ∗ = 19 / 2 , [ 0 , 3 ] ⊆ B ( 3 / 2 , 5 / 2 ) , [ 7 , 12 ] ⊆ B ( 19 / 2 , 5 / 2 ) . R ∗ ≤ 5 / 2 , 5 ≤ d ( u , v ) ≤ d ( u , c ) + d ( c , v ) ≤ 2 r ⟹ R ∗ ≥ 5 / 2. R ∗ = 5 / 2 , R G / R ∗ = 2. \begin{gathered}
c_1^*=3/2,\quad c_2^*=19/2,\quad [0,3]\subseteq B(3/2,5/2),\quad[7,12]\subseteq B(19/2,5/2).
\\R^*\le5/2,\qquad5\le d(u,v)\le d(u,c)+d(c,v)\le2r\ \Longrightarrow\ R^*\ge5/2.
\\R^*=5/2,\qquad R_G/R^*=2.
\end{gathered} c 1 ∗ = 3/2 , c 2 ∗ = 19/2 , [ 0 , 3 ] ⊆ B ( 3/2 , 5/2 ) , [ 7 , 12 ] ⊆ B ( 19/2 , 5/2 ) . R ∗ ≤ 5/2 , 5 ≤ d ( u , v ) ≤ d ( u , c ) + d ( c , v ) ≤ 2 r ⟹ R ∗ ≥ 5/2. R ∗ = 5/2 , R G / R ∗ = 2. 评分： 可行中心1；三点两球下界1；最优及比值1。
配套题本 Q5(b)
(c) [5]
若最终半径为零立即成立；否则在k个中心外加一个最终最远样本p，仅用于证明。选每个中心时，它离任一旧中心至少为当轮覆盖半径，后者不小于最终半径；p也离每个最终中心至少该半径。将k+1点分给k个最优覆盖球，必有两点同球，再用三角不等式。若最优仅为下确界，对任意近最优覆盖证明后令多余半径趋零。证明要求度量，不适用于平方欧氏距离，也不是k-means平方和保证。
证明有两个不同任务。首先必须构造k+1个充分分离的输入点；没有分离下界，直接说鸽巢原理还不够。增加中心不会增加任何点到最近中心的距离，所以覆盖半径单调不增。选中cj时，它到旧中心集合的距离是对各旧中心距离取最小值；最小值已不小于最终半径，每个单独距离自然也不小于最终半径。额外最远点同理。其次才与最优覆盖比较，即使一个点被多个球覆盖，也任选其中一个球归属。必有同球一对，它既有此前的距离下界，又有2R∗的距离上界。额外点只是证明工具，不是要求算法输出k+1个中心。
d ( p , { c 1 , … , c k } ) = R G , i < j ⟹ d ( c j , c i ) ≥ R j − 1 ≥ R G . d ( p , c i ) ≥ R G ⟹ { c 1 , … , c k , p } pairwise separated by at least R G . R G ≤ d ( u , v ) ≤ d ( u , c ∗ ) + d ( c ∗ , v ) ≤ 2 R ∗ . R G ≤ 2 ( R ∗ + ε ) ( ε > 0 ) ⟹ R G ≤ 2 R ∗ . ∣ 0 − 2 ∣ 2 = 4 > ∣ 0 − 1 ∣ 2 + ∣ 1 − 2 ∣ 2 = 2. \begin{gathered}
d(p,\{c_1,\ldots,c_k\})=R_G,\qquad i<j\Longrightarrow d(c_j,c_i)\ge R_{j-1}\ge R_G.
\\d(p,c_i)\ge R_G\quad\Longrightarrow\quad\{c_1,\ldots,c_k,p\}\text{ pairwise separated by at least }R_G.
\\ R_G\le d(u,v)\le d(u,c^*)+d(c^*,v)\le2R^*.
\\R_G\le2(R^*+\varepsilon)\quad(\varepsilon>0)\Longrightarrow R_G\le2R^*.
\\|0-2|^2=4> |0-1|^2+|1-2|^2=2.
\end{gathered} d ( p , { c 1 , … , c k }) = R G , i < j ⟹ d ( c j , c i ) ≥ R j − 1 ≥ R G . d ( p , c i ) ≥ R G ⟹ { c 1 , … , c k , p } pairwise separated by at least R G . R G ≤ d ( u , v ) ≤ d ( u , c ∗ ) + d ( c ∗ , v ) ≤ 2 R ∗ . R G ≤ 2 ( R ∗ + ε ) ( ε > 0 ) ⟹ R G ≤ 2 R ∗ . ∣0 − 2 ∣ 2 = 4 > ∣0 − 1 ∣ 2 + ∣1 − 2 ∣ 2 = 2. 评分： 额外最远点1；分离2；鸽巢1；三角结论1。
配套题本 Q5(c)
Q6. Lloyd迭代与次优固定点 (12)
配套题本 Q6
(a) [6]
一维有序中心以中点分界。第一次更新后必须重分配，不能立即说收敛。第三次分配与第二次相同，按题意停；没有样本落在这些分界。下列四个代价依次对应初始分配、第一轮均值更新、第二轮重新分配、第二轮均值更新，核对两类步骤均不增。
一维中两个有序中心的中点就是最近中心分界。初始(0,1)给出分界1/2，只有0进第一簇；第二簇均值为(1+4+6+7+12)/5=6。算完均值不等于收敛：中心(0,6)须以分界3重新分配，点1于是移动。新均值分别为(0+1)/2=1/2与(4+6+7+12)/4=29/4。再算中点31/8=3.875，仍在1与4之间，下一次分配才确认两簇不变，这时才满足题定停止条件。没有观测等于这些边界，所以从未触发平局规则。检查下降时应注明代价是在分配后还是中心更新后，否则正确数字也可能对应错误状态。
assignment boundary C 1 , C 2 updated centers 1 1 / 2 { 0 } , { 1 , 4 , 6 , 7 , 12 } 0 , 6 2 3 { 0 , 1 } , { 4 , 6 , 7 , 12 } 1 / 2 , 29 / 4 3 31 / 8 { 0 , 1 } , { 4 , 6 , 7 , 12 } 1 / 2 , 29 / 4 191 ≥ 66 ≥ 42 ≥ 141 / 4. c 1 + c 2 2 = 1 / 2 + 29 / 4 2 = 31 8 = 3.875. \begin{gathered}
\begin{array}{c|c|c|c} \text{assignment}&\text{boundary}&C_1,C_2&\text{updated centers}\\1&1/2&\{0\},\{1,4,6,7,12\}&0,6\\2&3&\{0,1\},\{4,6,7,12\}&1/2,29/4\\3&31/8&\{0,1\},\{4,6,7,12\}&1/2,29/4\end{array}
\\191\ \ge\ 66\ \ge\ 42\ \ge\ 141/4.
\\\frac{c_1+c_2}{2}=\frac{1/2+29/4}{2}=\frac{31}8=3.875.
\end{gathered} assignment 1 2 3 boundary 1/2 3 31/8 C 1 , C 2 { 0 } , { 1 , 4 , 6 , 7 , 12 } { 0 , 1 } , { 4 , 6 , 7 , 12 } { 0 , 1 } , { 4 , 6 , 7 , 12 } updated centers 0 , 6 1/2 , 29/4 1/2 , 29/4 191 ≥ 66 ≥ 42 ≥ 141/4. 2 c 1 + c 2 = 2 1/2 + 29/4 = 8 31 = 3.875. 评分： 第一轮2；第二轮2；最终检查与停止2。
配套题本 Q6(a)
(b) [3]
分别计算每簇相对自身均值的偏差。一个更好的可行分组已足以否定全局最优，不必证明替代分组本身全局最优；精确正差不是舍入误差。
终点代价按簇分别算，必须用最终均值。第一簇有两个绝对值为1/2的偏差；第二簇从4、6、7、12减去29/4，得到−13/4、−5/4、−1/4、19/4，逐项平方后再相加。替代分组要重新求自己的均值，不能沿用Lloyd中心；其两部分平方和为26/3与62/3，总计88/3。只需一个目标严格更小的可行解，就能否定Lloyd终点全局最优，无须进一步证明替代解本身全局最优。精确差71/12为正，不是舍入造成的差异。
S S E L l o y d = 1 2 + 169 + 25 + 1 + 361 16 = 141 4 . x ˉ A = 5 / 3 , x ˉ B = 25 / 3 , S S E A = 25 + 4 + 49 9 = 26 3 , S S E B = 49 + 16 + 121 9 = 62 3 . S S E a l t e r n a t i v e = 88 3 < 141 4 , 141 4 − 88 3 = 71 12 > 0. S S E 1 = ( 0 − 1 / 2 ) 2 + ( 1 − 1 / 2 ) 2 = 1 2 , S S E 2 = 169 + 25 + 1 + 361 16 = 139 4 . S S E A = 25 + 4 + 49 9 = 26 3 , S S E B = 49 + 16 + 121 9 = 62 3 , 141 4 − 88 3 = 71 12 > 0. \begin{gathered}
\mathrm{SSE}_{\mathrm{Lloyd}}=\frac12+\frac{169+25+1+361}{16}=\frac{141}4.
\\\bar x_A=5/3,\quad\bar x_B=25/3,\quad\mathrm{SSE}_A=\frac{25+4+49}{9}=\frac{26}3,\quad\mathrm{SSE}_B=\frac{49+16+121}{9}=\frac{62}3.
\\\mathrm{SSE}_{\mathrm{alternative}}=\frac{88}3<\frac{141}4,\qquad\frac{141}4-\frac{88}3=\frac{71}{12}>0.
\\ \mathrm{SSE}_1=(0-1/2)^2+(1-1/2)^2=\frac12,\quad\mathrm{SSE}_2=\frac{169+25+1+361}{16}=\frac{139}{4}.\\\mathrm{SSE}_A=\frac{25+4+49}{9}=\frac{26}{3},\quad\mathrm{SSE}_B=\frac{49+16+121}{9}=\frac{62}{3},\quad\frac{141}{4}-\frac{88}{3}=\frac{71}{12}>0.
\end{gathered} SSE Lloyd = 2 1 + 16 169 + 25 + 1 + 361 = 4 141 . x ˉ A = 5/3 , x ˉ B = 25/3 , SSE A = 9 25 + 4 + 49 = 3 26 , SSE B = 9 49 + 16 + 121 = 3 62 . SSE alternative = 3 88 < 4 141 , 4 141 − 3 88 = 12 71 > 0. SSE 1 = ( 0 − 1/2 ) 2 + ( 1 − 1/2 ) 2 = 2 1 , SSE 2 = 16 169 + 25 + 1 + 361 = 4 139 . SSE A = 9 25 + 4 + 49 = 3 26 , SSE B = 9 49 + 16 + 121 = 3 62 , 4 141 − 3 88 = 12 71 > 0. 评分： 终点1；替代中心代价1；非全局结论1。
配套题本 Q6(b)
(c) [3]
围绕均值展开；中心化样本之和为零，交叉项消失。附加项非负且仅中心等于均值时为零。Lloyd只是固定另一部分时各自优化，联合问题非凸，更好分组可能需同时改变多个点及中心；前问正是反例。
证明均值公式时要固定簇成员。每个x−c中加减μ，展开平方长度，先保留交叉项再求和。按均值定义，中心化样本之和为零，交叉项才消失。剩下m‖μ−c‖²非负，而且m>0时仅在c=μ为零，证明的是固定这个簇时中心唯一最优。Lloyd交替优化两个条件子问题：中心固定时选最好分配，分配固定时选最好中心；这并不使联合问题成为凸问题，下降也不等于考虑过所有可能分组。更好的分组可能要同时改变若干分配与中心，(b)正是全局最优主张的具体反例。
m = ∣ C ∣ > 0 , μ = 1 m ∑ x ∈ C x , ∑ x ∈ C ( x − μ ) = 0. ∑ x ∈ C ∥ x − c ∥ 2 = ∑ x ∈ C ∥ ( x − μ ) + ( μ − c ) ∥ 2 = ∑ x ∈ C ∥ x − μ ∥ 2 + 2 ( ∑ x ∈ C ( x − μ ) ) T ( μ − c ) + m ∥ μ − c ∥ 2 = ∑ x ∈ C ∥ x − μ ∥ 2 + m ∥ μ − c ∥ 2 ≥ ∑ x ∈ C ∥ x − μ ∥ 2 . \begin{gathered}
m=|C|>0,\quad\mu=\frac1m\sum_{x\in C}x,\quad\sum_{x\in C}(x-\mu)=0.
\\\sum_{x\in C}\|x-c\|^2=\sum_{x\in C}\|(x-\mu)+(\mu-c)\|^2
\\=\sum_{x\in C}\|x-\mu\|^2+2\left(\sum_{x\in C}(x-\mu)\right)^T(\mu-c)+m\|\mu-c\|^2
\\=\sum_{x\in C}\|x-\mu\|^2+m\|\mu-c\|^2\ge\sum_{x\in C}\|x-\mu\|^2.
\end{gathered} m = ∣ C ∣ > 0 , μ = m 1 x ∈ C ∑ x , x ∈ C ∑ ( x − μ ) = 0. x ∈ C ∑ ∥ x − c ∥ 2 = x ∈ C ∑ ∥ ( x − μ ) + ( μ − c ) ∥ 2 = x ∈ C ∑ ∥ x − μ ∥ 2 + 2 ( x ∈ C ∑ ( x − μ ) ) T ( μ − c ) + m ∥ μ − c ∥ 2 = x ∈ C ∑ ∥ x − μ ∥ 2 + m ∥ μ − c ∥ 2 ≥ x ∈ C ∑ ∥ x − μ ∥ 2 . 评分： 分解与交叉项2；局部块与全局区别1。
配套题本 Q6(c)
Q7. Voronoi单元与中心位置 (9)
配套题本 Q7
(a) [3]
非负距离平方后消去共同二次项；前两比较给垂直及水平平分线，第三给斜线。公共顶点到三个站点距离都为√13。闭单元允许共享边界；若唯一分配还须平局规则。
先将s₁分别与另外两站比较，得到它的两条不等式。求s₂与s₃之间边界时，把两边距离平方展开，消去x²+y²，再移项得到线性条件。不等号方向取决于正在描述哪个站的单元，换另一单元就要反向。三单元共有点必须同时满足x≤2与x≥2，以及y≤3与y≥3，所以只能是(2,3)；再检查第三条边界及三条距离确实相同。闭Voronoi单元允许边界重合，要在边界赋予唯一簇标签才另外需要平局规则，这不是单元定义出错。
x 2 + y 2 ≤ ( x − 4 ) 2 + y 2 ⟺ x ≤ 2 , x 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ y ≤ 3. ( x − 4 ) 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ 3 y − 2 x ≤ 5. R 1 = { ( x , y ) : x ≤ 2 , y ≤ 3 } , R 2 = { ( x , y ) : x ≥ 2 , 3 y − 2 x ≤ 5 } , R 3 = { ( x , y ) : y ≥ 3 , 3 y − 2 x ≥ 5 } , R 1 ∩ R 2 ∩ R 3 = { ( 2 , 3 ) } , 3 ( 3 ) − 2 ( 2 ) = 5. − 8 x + 16 ≤ − 12 y + 36 ⟺ 3 y − 2 x ≤ 5 , ∥ ( 2 , 3 ) − s i ∥ = 13 ( i = 1 , 2 , 3 ) . \begin{gathered}
x^2+y^2\le(x-4)^2+y^2\Longleftrightarrow x\le2,
\qquad x^2+y^2\le x^2+(y-6)^2\Longleftrightarrow y\le3.
\\(x-4)^2+y^2\le x^2+(y-6)^2\Longleftrightarrow3y-2x\le5.
\\R_1=\{(x,y):x\le2,y\le3\},\quad R_2=\{(x,y):x\ge2,3y-2x\le5\},
\\R_3=\{(x,y):y\ge3,3y-2x\ge5\},\quad R_1\cap R_2\cap R_3=\{(2,3)\},\quad3(3)-2(2)=5.
\\ -8x+16\le-12y+36\ \Longleftrightarrow\ 3y-2x\le5,\quad\|(2,3)-s_i\|=\sqrt{13}\quad(i=1,2,3).
\end{gathered} x 2 + y 2 ≤ ( x − 4 ) 2 + y 2 ⟺ x ≤ 2 , x 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ y ≤ 3. ( x − 4 ) 2 + y 2 ≤ x 2 + ( y − 6 ) 2 ⟺ 3 y − 2 x ≤ 5. R 1 = {( x , y ) : x ≤ 2 , y ≤ 3 } , R 2 = {( x , y ) : x ≥ 2 , 3 y − 2 x ≤ 5 } , R 3 = {( x , y ) : y ≥ 3 , 3 y − 2 x ≥ 5 } , R 1 ∩ R 2 ∩ R 3 = {( 2 , 3 )} , 3 ( 3 ) − 2 ( 2 ) = 5. − 8 x + 16 ≤ − 12 y + 36 ⟺ 3 y − 2 x ≤ 5 , ∥ ( 2 , 3 ) − s i ∥ = 13 ( i = 1 , 2 , 3 ) . 评分： 各单元0.75；公共点及核对0.75。
配套题本 Q7(a)
(b) [3]
长度非负，平方保序；展开后是线性不等式。半空间内两点的凸组合由线性性仍在其中；若两点同属全部半空间，线段也同属全部，故交集凸。任意维成立，不依赖图形。
两边都是非负距离，所以平方保持大小关系。展开后共同二次项抵消，留下关于x的线性不等式，右端是常数；因此即使在无法画出的高维中，它仍是半空间。证明凸性时，取满足不等式的任意两点，用非负且和为1的权重1−t与t组合，线段每点仍满足该不等式。若两个端点属于所有半空间，线段每点也同时属于所有半空间，故属于交集。仅凭图形看起来凸，并不构成证明。
∥ x − s i ∥ ≤ ∥ x − s j ∥ ⟺ x T x − 2 x T s i + ∥ s i ∥ 2 ≤ x T x − 2 x T s j + ∥ s j ∥ 2 ⟺ x T ( s j − s i ) ≤ ∥ s j ∥ 2 − ∥ s i ∥ 2 2 , R i = ⋂ j ≠ i { x : x T ( s j − s i ) ≤ ∥ s j ∥ 2 − ∥ s i ∥ 2 2 } . u , v ∈ H = { x : a T x ≤ b } , t ∈ [ 0 , 1 ] ⟹ a T [ ( 1 − t ) u + t v ] ≤ ( 1 − t ) b + t b = b . \begin{gathered}
\|x-s_i\|\le\|x-s_j\|\Longleftrightarrow x^Tx-2x^Ts_i+\|s_i\|^2\le x^Tx-2x^Ts_j+\|s_j\|^2
\\\Longleftrightarrow x^T(s_j-s_i)\le\frac{\|s_j\|^2-\|s_i\|^2}{2},\quad R_i=\bigcap_{j\ne i}\left\{x:x^T(s_j-s_i)\le\frac{\|s_j\|^2-\|s_i\|^2}{2}\right\}.
\\u,v\in H=\{x:a^Tx\le b\},\quad t\in[0,1]\Longrightarrow a^T[(1-t)u+tv]\le(1-t)b+tb=b.
\end{gathered} ∥ x − s i ∥ ≤ ∥ x − s j ∥ ⟺ x T x − 2 x T s i + ∥ s i ∥ 2 ≤ x T x − 2 x T s j + ∥ s j ∥ 2 ⟺ x T ( s j − s i ) ≤ 2 ∥ s j ∥ 2 − ∥ s i ∥ 2 , R i = j = i ⋂ { x : x T ( s j − s i ) ≤ 2 ∥ s j ∥ 2 − ∥ s i ∥ 2 } . u , v ∈ H = { x : a T x ≤ b } , t ∈ [ 0 , 1 ] ⟹ a T [( 1 − t ) u + t v ] ≤ ( 1 − t ) b + t b = b . 评分： 半空间推导1；半空间凸1；交集论证1。
配套题本 Q7(b)
(c) [3]
均值是凸组合：等权非负且和为1。未必是样本，如{0,2}均值1。Medoid限于实际观测，此例0与2均可而1不合法。非空不可省，空簇没有该均值及权重。
第6题已证明固定非空簇的最佳中心为均值。接着按凸组合定义检查：每个系数1/m非负，所有系数和为1，故均值在凸包中。在凸包内比“就是某个观测点”弱；{0,2}的凸包是整个区间[0,2]，所以1在凸包内却未被观测。固定簇的medoid则从观测中挑选使距离总和最小者，并非取任意位置的算术平均。本例两端点均可作medoid。若m=0，除以m和上述凸组合都未定义，空簇必须另外处理。
C = { x 1 , … , x m } , m > 0 , μ = ∑ i = 1 m 1 m x i , 1 m ≥ 0 , ∑ i = 1 m 1 m = 1 , μ ∈ conv ( C ) . \begin{gathered}
C=\{x_1,\ldots,x_m\},\quad m>0,\quad\mu=\sum_{i=1}^m\frac1m x_i,\quad\frac1m\ge0,\quad\sum_{i=1}^m\frac1m=1,
\qquad\mu\in\operatorname{conv}(C).
\end{gathered} C = { x 1 , … , x m } , m > 0 , μ = i = 1 ∑ m m 1 x i , m 1 ≥ 0 , i = 1 ∑ m m 1 = 1 , μ ∈ conv ( C ) . 评分： 凸组合1；反例1；medoid限制1。
配套题本 Q7(c)
