数值代数历年回忆卷 — Arendelle Royal Library

迁移自 zju-math-courses-collection 的 numeric_algebra/memory_exam.tex（2026 春夏数值代数）。把 review.tex 中分散在各章的回忆题重新整理成一份单独的刷题文档，难度按”手算量、知识耦合度、证明抽象度”排序，不代表真实试卷题号顺序。

难度梯度说明

梯度	定位
第一梯度	基础识别与一步计算：范数、正定性、一两步迭代、二维正交变换、简单特征值。
第二梯度	标准算法手算：LU/PLU、Cholesky、\(LDL^T\)、追赶法、正规方程。
第三梯度	参数与迭代综合：迭代矩阵、谱半径收敛判别、CG 手算。
第四梯度	证明分析题：浮点误差、范数性质、最小二乘投影、Krylov 与共轭向量。
第五梯度	拓展挑战题：Householder 相似变换、Hessenberg/QR、幂法异常情形、SVD。

第一梯度：基础识别与一步计算

设
\[ x=(-1,2,-3,4)^T.\]
求 \(\norm{x}_1,\norm{x}_2,\norm{x}_\infty\)。
设
\[ A(a)=\begin{bmatrix}1&0&a\\0&1&0\\a&0&1\end{bmatrix}\]
是线性方程组 \(Ax=b\) 的系数矩阵。问：\(a\) 为何值时，\(A\) 是正定的？
对方程组
\[ \begin{bmatrix}2&-1&0\\-1&2&-1\\0&-1&2\end{bmatrix} \begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}1\\1\\0\end{bmatrix},\qquad x^{(0)}=(0,0,0)^T,\]
(1) 计算其 Jacobi 迭代解 \(x^{(1)},x^{(2)}\)；(2) 证明 Jacobi 方法关于该方程组收敛。
确定 \(c=\cos\theta\)、\(s=\sin\theta\) 和 \(\beta\)，使
\[ \begin{bmatrix}c&s\\-s&c\end{bmatrix} \begin{bmatrix}7\\-1\end{bmatrix} = \begin{bmatrix}\beta\\\beta\end{bmatrix}.\]
设
\[ A=\begin{bmatrix}2&-1\\-1&2\end{bmatrix}.\]
用 Jacobi 方法求其特征值。
默写实数域上矩阵 \(A\) 的 Schur 分解定理。

第二梯度：标准算法手算

设
\[ A=\begin{bmatrix}1&4&7\\2&5&8\\3&6&10\end{bmatrix},\qquad b=\begin{bmatrix}1\\1\\1\end{bmatrix}.\]
求 \(A\) 的 \(LU\) 分解和 \(PLU\) 分解，分别求解方程 \(Ax=b\)。
设
\[ A=\begin{bmatrix}1&-1&3\\4&-2&1\\-3&-1&-4\end{bmatrix}.\]
计算 \(A\) 选取列主元的 \(LU\) 分解，即 \(PA=LU\)，求 \(P,L,U\)。
设
\[ A=\begin{bmatrix}-1&2&0\\-3&11&0\\0&10&2\end{bmatrix},\qquad b=\begin{bmatrix}0\\5\\4\end{bmatrix}.\]
(1) 求矩阵 \(A\) 的 \(LU\) 分解；(2) 求矩阵 \(A\) 的列主元 \(LU\) 分解，写出 \(P,L,U\)；(3) 求解方程 \(Ax=b\)；(4) 说明为什么要在高斯消去法中选主元，并举出没有 \(LU\) 分解的非奇异矩阵的例子。
设
\[ A=\begin{bmatrix}4&-2&0\\-2&2&1\\0&1&10\end{bmatrix}.\]
(1) 证明 \(A\) 为对称正定矩阵；(2) 计算其 Cholesky 分解。
设
\[ A=\begin{bmatrix} 10&8&4&8\\ 8&13&10&7\\ 4&10&9&12\\ 8&7&12&15 \end{bmatrix},\qquad b=\begin{bmatrix}38\\18\\35\\42\end{bmatrix}.\]
用平方根法求解 \(Ax=b\)。
设
\[ A=\begin{bmatrix} 4&-2&4&2\\ -2&10&-2&-7\\ 4&-2&8&4\\ 2&-7&4&7 \end{bmatrix},\qquad b=\begin{bmatrix}8\\2\\16\\6\end{bmatrix}.\]
用改进平方根法求解 \(Ax=b\)。
设
\[ A=\begin{bmatrix}-2&-4&0\\-4&-2&0\\0&0&4\end{bmatrix},\qquad b=\begin{bmatrix}0\\6\\4\end{bmatrix}.\]
(1) 求 \(\norm{A}_1,\norm{A}_2,\norm{A}_\infty\)；(2) 用追赶法求解 \(Ax=b\)。
设
\[ A=\begin{bmatrix}0&-1\\3&2\\0&-2\end{bmatrix},\qquad b=\begin{bmatrix}-1/3\\5/3\\-2/3\end{bmatrix},\]
(1) 求 \(Ax=b\) 的最小二乘解的正规方程；(2) 用平方根法解该正规方程。

第三梯度：参数、收敛与迭代综合

设 \(Ax=b\) 的系数矩阵如下：
\[ A_1=\begin{bmatrix}2&1&1\\1&-1&-1\\1&1&-2\end{bmatrix},\qquad A_2=\begin{bmatrix}1&2&-2\\1&1&-1\\2&-2&1\end{bmatrix}.\]
分别求两个矩阵的 Jacobi 迭代矩阵，并判断 Jacobi 迭代法的收敛性。
考虑线性方程组 \(Ax=b\)，其中
\[ A(a)=\begin{bmatrix}1&0&a\\0&1&0\\a&0&1\end{bmatrix}.\]
(1) \(a\) 为何值时，\(A\) 是正定的？(2) 写出 Jacobi 迭代法的迭代矩阵；\(a\) 为何值时，Jacobi 迭代法收敛？(3) 写出 Gauss—Seidel 迭代法的迭代矩阵；\(a\) 为何值时，Gauss—Seidel 迭代法收敛？
考虑二阶线性方程组
\[ A(\rho)=\begin{bmatrix}1&\rho\\ \rho&2\end{bmatrix}.\]
(1) 分别写出 Jacobi 迭代法和 Gauss—Seidel 迭代法的迭代格式；(2) 分别判断 Jacobi 迭代法与 Gauss—Seidel 迭代法在何时收敛。
设
\[ A=\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix},\qquad a_{11}a_{22}\ne0.\]
证明：求解 \(Ax=b\) 的 Jacobi 迭代和 Gauss—Seidel 迭代同时收敛或同时发散。
设
\[ A=\begin{bmatrix}2&1&0\\1&2&1\\0&1&1\end{bmatrix},\qquad b=\begin{bmatrix}1\\0\\1\end{bmatrix},\qquad x^{(0)}=\begin{bmatrix}0\\0\\1\end{bmatrix}.\]
用共轭梯度法求解 \(Ax=b\)。

第四梯度：证明分析题

在标准浮点模型下，证明顺序连乘满足
\[ \fl(x_1\cdots x_n)=x_1\cdots x_n(1+\varepsilon),\qquad |\varepsilon|\le\gamma_{n-1}.\]
证明顺序求和可写成
\[ \fl\left(\sum_{i=1}^n x_i\right)=\sum_{i=1}^n x_i(1+\eta_i),\]
并给出 \(\eta_i\) 的上界。
证明矩阵向量乘法具有后向误差形式
\[ \fl(Ax)=(A+E)x,\]
并估计 \(E\) 的元素级上界。
证明
\[ \fl(x^Tx)=x^Tx(1+\alpha),\qquad |\alpha|\le n\mathbf u+O(\mathbf u^2).\]
设 \(X\in\R^{n\times n}\) 非奇异，对任意 \(A\in\R^{n\times n}\) 定义
\[ \norm{A}_X=\norm{X^{-1}AX}_2.\]
证明 \(\norm{\cdot}_X\) 是矩阵范数。
对 \(A\in\R^{n\times n}\)，定义
\[ \norm{A}_{\max}=\max_{i,j}|a_{ij}|,\]
证明 \(\norm{\cdot}_{\max}\) 是一个向量意义下的范数，并举例说明它不满足矩阵范数的相容性。
设 \(A=(a_{ij})\in\R^{n\times n}\)，
\[ \norm{A}_F=\left(\sum_{i,j=1}^n |a_{ij}|^2\right)^{1/2}.\]
(1) 证明 \(\norm{\cdot}_F\) 是一个矩阵范数；(2) 设 \(U,V\) 是正交阵，证明
\[ \norm{A}_F=\norm{U^TAV}_F.\]
设 \(A\in\R^{m\times n}\)，\(m>n\)，且 \(A\) 列满秩。证明
\[ \norm{A(A^TA)^{-1}A^T}_2=1.\]
设 \(A\in\R^{m\times n}\)，\(X\in\R^{n\times m}\)。若存在 \(X\)，使得对任意 \(b\in\R^m\)，\(x=Xb\) 都能使 \(\norm{b-Ax}_2\) 最小。求证：
\[ (1)\ AXA=A;\qquad (2)\ (AX)^T=AX.\]
设 \(A=A^T\) 只有 \(k\) 个互不相同的特征值，\(r\in\R^n\)。证明
\[ \dim\mathrm{span}\{r,Ar,\dots,A^{n-1}r\}\le k.\]
进一步说明为什么当 \(A=A^T>0\) 且只有 \(\ell\) 个互异特征值时，CG 至多 \(\ell\) 步得到精确解。
设 \(A\) 为 \(n\) 阶对称正定矩阵，\(p_1,p_2,\dots,p_n\) 为一列共轭向量，即满足
\[ p_i^TAp_j=0\qquad(i\ne j).\]
试证明：(1) \(p_1,p_2,\dots,p_n\) 线性无关；(2)
\[ A^{-1}=\sum_{k=1}^n\frac{p_kp_k^T}{p_k^TAp_k}.\]

第五梯度：拓展挑战题

分别应用幂法于矩阵
\[ A=\begin{bmatrix}\lambda&1\\0&\lambda\end{bmatrix},\qquad B=\begin{bmatrix}\lambda&1\\0&-\lambda\end{bmatrix},\qquad \lambda>0,\]
分析幂法得到的迭代序列、特征值近似和特征向量近似的行为。
设
\[ x=(3,1,6,4,2,2)^T.\]
求 Householder 变换 \(H\) 和常数 \(\alpha\)，使得
\[ Hx=(3,\alpha,4,6,0,0)^T.\]
设 \(x\ne0\) 且 \(x\) 与 \(e_1\) 不平行。求 Householder 变换 \(H\)，使
\[ Hx=\norm{x}_2e_1.\]
判断 \(He_1\) 是否与 \(x\) 平行，并说明理由。
设
\[ A=\begin{bmatrix}8&3&-2\\0&2&4\\0&2&-1\end{bmatrix}.\]
通过正交相似变换将 \(A\) 变换为一个上 Hessenberg 矩阵。
设
\[ A=\begin{bmatrix}3&*&*\\0&*&*\\-1&*&*\end{bmatrix}.\]
用 Householder 变换将 \(A\) 相似变换为上 Hessenberg 矩阵 \(B\)。（此题来自回忆图，星号处原图未给出具体数值。）
对
\[ A=\begin{bmatrix} 1&1&2&2\\ 1&29&28&25\\ 2&-2&-1&2\\ 2&1&-13&-1 \end{bmatrix},\]
使用 Householder 变换将 \(A\) 归约为上 Hessenberg 矩阵。即找出 \(u_1,u_2\)，使
\[ P_1=I_3-2u_1u_1^T,\qquad P_2=I_2-2u_2u_2^T.\]
并有
\[ \begin{bmatrix}I_2&0\\0&P_2\end{bmatrix} \begin{bmatrix}1&0\\0&P_1\end{bmatrix} A \begin{bmatrix}1&0\\0&P_1\end{bmatrix} \begin{bmatrix}I_2&0\\0&P_2\end{bmatrix} =H_0,\]
其中 \(H_0\) 为上 Hessenberg 矩阵。
写出对 \(H_0\in\R^{n\times n}\) 的 QR 迭代算法的伪代码：
\[ H_k=Q_kR_k,\qquad H_{k+1}=R_kQ_k.\]
并证明 QR 迭代保持 Hessenberg 结构，即若 \(H_0\) 为上 Hessenberg 矩阵，则 \(H_1,H_2,\dots\) 均为上 Hessenberg 矩阵。
设 \(A\in\R^{m\times n}\)，\(m\ge n\)，其奇异值满足
\[ \sigma_1\ge\sigma_2\ge\cdots\ge\sigma_r> \sigma_{r+1}=\cdots=\sigma_n=0,\]
且奇异值分解为
\[ A=U\Sigma V^T,\qquad U=[u_1,\dots,u_m],\quad V=[v_1,\dots,v_n],\]
其中 \(U,V\) 均为正交阵。 (1) 用奇异值分解定义 \(A\) 的 Moore—Penrose 广义逆；(2) 对任意 \(v\in\R^n\)，证明
\[ \norm{Av}_2\le\sigma_1\norm{v}_2,\qquad \norm{Av}_2\ge\sigma_n\norm{v}_2,\]
并说明 \(v\) 满足什么条件时上述等号成立；(3)（附加）证明奇异值的极大极小刻画：
\[ \sigma_k=\min_{\dim V=n-k+1}\max_{0\ne v\in V}\frac{\norm{Av}_2}{\norm{v}_2} = \max_{\dim V=k}\min_{0\ne v\in V}\frac{\norm{Av}_2}{\norm{v}_2}.\]

同型计算题集中训练

直接法

设
\[ A=\begin{bmatrix}2&1&1\\4&5&3\\-2&5&4\end{bmatrix},\qquad b=\begin{bmatrix}4\\12\\5\end{bmatrix}.\]
求 \(A=LU\)，并解 \(Ax=b\)。
设
\[ A=\begin{bmatrix}0&2&1\\1&1&0\\2&-1&1\end{bmatrix},\qquad b=\begin{bmatrix}1\\2\\3\end{bmatrix}.\]
按列主元消去计算 \(PA=LU\)，并解 \(Ax=b\)。
设
\[ A=\begin{bmatrix}4&2&-2\\2&10&2\\-2&2&5\end{bmatrix},\qquad b=\begin{bmatrix}2\\8\\-1\end{bmatrix}.\]
先判断 \(A\) 是否正定，再用 Cholesky 分解求解 \(Ax=b\)。
设
\[ A=\begin{bmatrix}2&-2&0\\-2&5&1\\0&1&3\end{bmatrix},\qquad b=\begin{bmatrix}0\\3\\4\end{bmatrix}.\]
用改进平方根法，即 \(A=LDL^T\)，求解 \(Ax=b\)。
用追赶法求解三对角方程组
\[ \begin{bmatrix} 4&-1&0&0\\ -2&5&-1&0\\ 0&-1&4&-1\\ 0&0&-2&3 \end{bmatrix} x= \begin{bmatrix}3\\4\\5\\1\end{bmatrix}.\]
用 Gauss—Jordan 消元求
\[ A=\begin{bmatrix}1&2&1\\0&1&1\\2&1&0\end{bmatrix}\]
的逆矩阵。

范数、最小二乘与正交变换

设 \(x=(2,-1,2,-2)^T\)。求 \(\norm{x}_1,\norm{x}_2,\norm{x}_\infty\)。
设
\[ T=\begin{bmatrix} 2&-1&0\\ -1&2&-1\\ 0&-1&2 \end{bmatrix}.\]
求 \(\norm{T}_1,\norm{T}_2,\norm{T}_\infty,\kappa_2(T)\)。
对超定方程组 \(Ax\approx b\)，其中
\[ A=\begin{bmatrix}1&0\\1&1\\1&2\end{bmatrix},\qquad b=\begin{bmatrix}1\\2\\2\end{bmatrix}.\]
写出正规方程，并求最小二乘解。
构造 Householder 矩阵 \(H\)，使
\[ H(1,2,2)^T=3e_1.\]
确定 \(c,s\)，使
\[ \begin{bmatrix}c&s\\-s&c\end{bmatrix} \begin{bmatrix}3\\4\end{bmatrix} = \begin{bmatrix}5\\0\end{bmatrix}.\]

迭代法与特征值

设
\[ A(a)=\begin{bmatrix}2&a\\a&3\end{bmatrix}.\]
写出 Jacobi 与 Gauss—Seidel 迭代矩阵，并判断两种方法关于参数 \(a\) 的收敛范围。
对
\[ A=\begin{bmatrix}2&1\\1&2\end{bmatrix},\qquad b=\begin{bmatrix}1\\0\end{bmatrix},\qquad x^{(0)}=0,\]
用共轭梯度法计算到精确解。
对
\[ A=\begin{bmatrix}3&0\\0&1\end{bmatrix},\qquad x^{(0)}=(1,1)^T,\]
采用无穷范数归一化的幂法，写出 \(x^{(1)},x^{(2)}\) 和对应主特征值近似。
对
\[ A=\begin{bmatrix}2&1\\1&2\end{bmatrix}\]
做一步 QR 迭代：\(A=QR,\ A_1=RQ\)。

同型题核对答案

\[ L=\begin{bmatrix}1&0&0\\2&1&0\\-1&2&1\end{bmatrix},\quad U=\begin{bmatrix}2&1&1\\0&3&1\\0&0&3\end{bmatrix},\quad x=\begin{bmatrix}11/9\\11/9\\1/3\end{bmatrix}.\]
\[ P=\begin{bmatrix}0&0&1\\1&0&0\\0&1&0\end{bmatrix},\quad L=\begin{bmatrix}1&0&0\\0&1&0\\1/2&3/4&1\end{bmatrix},\quad U=\begin{bmatrix}2&-1&1\\0&2&1\\0&0&-5/4\end{bmatrix},\] \[ x=\begin{bmatrix}8/5\\2/5\\1/5\end{bmatrix}.\]
顺序主子式为 \(4,36,108\)，故 \(A\) 正定；
\[ L=\begin{bmatrix}2&0&0\\1&3&0\\-1&1&\sqrt3\end{bmatrix},\qquad x=\begin{bmatrix}-11/27\\28/27\\-7/9\end{bmatrix}.\]
\[ L=\begin{bmatrix}1&0&0\\-1&1&0\\0&1/3&1\end{bmatrix},\quad D=\diag(2,3,8/3),\quad x=\begin{bmatrix}5/8\\5/8\\9/8\end{bmatrix}.\]
\[ x=\begin{bmatrix}197/168\\71/42\\59/28\\73/42\end{bmatrix}.\]
\[ A^{-1}=\begin{bmatrix}-1&1&1\\2&-2&-1\\-2&3&1\end{bmatrix}.\]
\(\norm{x}_1=7,\ \norm{x}_2=\sqrt{13},\ \norm{x}_\infty=2\)。
\(\norm{T}_1=4,\ \norm{T}_\infty=4\)，特征值为 \(2-\sqrt2,2,2+\sqrt2\)，所以
\[ \norm{T}_2=2+\sqrt2,\qquad \kappa_2(T)=3+2\sqrt2.\]
\[ A^TA=\begin{bmatrix}3&3\\3&5\end{bmatrix},\qquad A^Tb=\begin{bmatrix}5\\6\end{bmatrix},\qquad x=\begin{bmatrix}7/6\\1/2\end{bmatrix}.\]
可取
\[ u=\frac{1}{\sqrt3}(-1,1,1)^T,\qquad H=I-2uu^T= \begin{bmatrix} 1/3&2/3&2/3\\ 2/3&1/3&-2/3\\ 2/3&-2/3&1/3 \end{bmatrix}.\]
\(c=3/5,\ s=4/5\)。
\[ B_J=\begin{bmatrix}0&-a/2\\-a/3&0\end{bmatrix},\qquad B_{GS}=\begin{bmatrix}0&-a/2\\0&a^2/6\end{bmatrix}.\]
两者均当且仅当 \(|a|<\sqrt6\) 时收敛。
CG 第一步
\[ \alpha_0=\frac12,\quad x^{(1)}=(1/2,0)^T,\quad r^{(1)}=(0,-1/2)^T,\] \[ \beta_0=\frac14,\quad p^{(1)}=(1/4,-1/2)^T,\quad \alpha_1=\frac23,\quad x^{(2)}=(2/3,-1/3)^T.\]
用无穷范数归一化，
\[ x^{(1)}=(1,1/3)^T,\qquad x^{(2)}=(1,1/9)^T,\]
主特征值近似为 \(3\)。
\[ Q=\begin{bmatrix}2/\sqrt5&-1/\sqrt5\\1/\sqrt5&2/\sqrt5\end{bmatrix},\quad R=\begin{bmatrix}\sqrt5&4/\sqrt5\\0&3/\sqrt5\end{bmatrix},\] \[ A_1=RQ=\begin{bmatrix}14/5&3/5\\3/5&6/5\end{bmatrix}.\]