数值方法资格考试试题及解答（马里兰大学）/2008 年 8 月

问题 1

令 $A\in \mathbb {R} ^{m\times n},b\in \mathbb {R} ^{m},\!\,$ 且 $p\in \mathbb {R} ^{n}$ ，其中 $m>n\!\,$ ，并令 $\delta \!\,$ 为一个标量。证明约束最小二乘问题，

{\mbox{minimize }}\|b-Ax\|_{2}\quad \quad {\mbox{ subject to }}p^{T}x=\delta

可以简化为求解相关的无约束最小二乘问题。该算法应首先找到 Householder 变换 $H\!\,$ ，使得

Hp=\|p\|_{2}e_{1}

并令

y=Hx\!\,

解答 1

由于 Householder 矩阵是正交的，并且是厄米特矩阵（如果矩阵是实数，则为对称矩阵），因此我们有

$y=Hx\Rightarrow x=H^{T}y=Hy$

然后约束可以写成

${\begin{aligned}p^{T}x&=\delta \\p^{T}(H^{T}y)&=\delta \\(Hp)^{T}y&=\delta \\(\|p\|_{2}e_{1})^{T}y&=\delta \\\|p\|_{2}e_{1}^{T}y&=\delta \\y_{1}&={\frac {\delta }{\|p\|_{2}}}\end{aligned}}$

因此，列向量 $y\!\,$ 的第一个元素， $y_{1}\!\,$ （一个标量），代表了我们的约束。

现在我们要证明我们可以将 $\|Ax-b\|_{2}\!\,$ 写成一个相关的无约束问题。将 $x\!\,$ 代入 $Ax\!\,$ 中，我们得到：

$Ax=AHy\!\,$

令 $AH=B={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}$ ，其中 $B_{1}\!\,$ 是 $B\!\,$ 的第一列，而 ${\hat {B}}\!\,$ 是其余的列。

因为：

y={\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}

分块矩阵乘法得到：

${\begin{aligned}AHy&=By\\&={\begin{bmatrix}B_{1}&{\hat {B}}\end{bmatrix}}{\begin{bmatrix}y_{1}\\{\hat {y}}\end{bmatrix}}\\&=y_{1}B_{1}+{\hat {B}}{\hat {y}}\end{aligned}}$

因此， $\min _{y}\|b-AHy\|_{2}=\min _{\hat {y}}\|b-y_{1}B_{1}-{\hat {B}}{\hat {y}}\|_{2}$ ，这是一个无约束问题。

问题 2

证明或反驳以下插值多项式对于所有 $y_{1},y_{2},y_{3}\!\,$ 和所有不同 $x_{1},x_{2},x_{3}\!\,$ 都存在。

问题 2a

a.\qquad y_{i}=c_{1}+c_{2}x_{i}+c_{3}x_{i}^{2}\!\,

解 2a

将 $x_{i},\,y_{i},\;i=1,2,3,\,$ 对代入该方程得到以下矩阵方程

{\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&x_{1}&x_{1}^{2}\\1&x_{2}&x_{2}^{2}\\1&x_{3}&x_{3}^{2}\end{bmatrix}} _{A}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}

其中 A 是范德蒙矩阵，已知它是非奇异的。这证明了系数 $c_{1},\,c_{2},\,c_{3}$ 的存在性和唯一性。

问题 2b

b.\qquad y_{i}=c_{1}+c_{2}x_{i}^{2}+c_{3}x_{i}^{4}\!\,

解 2b

现在，将 $x_{i},\,y_{i},\;i=1,2,3,\,$ 对代入得到

{\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}={\begin{bmatrix}1&x_{1}^{2}&x_{1}^{4}\\1&x_{2}^{2}&x_{2}^{4}\\1&x_{3}^{2}&x_{3}^{4}\end{bmatrix}}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}

考虑唯一的点集 $x_{1}=1,\ x_{2}=-1,\ x_{3}=0.\$

系统简化为

{\begin{bmatrix}y_{1}\\y_{2}\\y_{3}\end{bmatrix}}=\underbrace {\begin{bmatrix}1&1&1\\1&1&1\\1&0&0\end{bmatrix}} _{A}{\begin{bmatrix}c_{1}\\c_{2}\\c_{3}\end{bmatrix}}

这里，矩阵 $A\!\,$ 明显是奇异的。

更一般地，矩阵 $A$ 的行列式由下式给出

$\left|{\begin{array}{ccc}1&x_{1}^{2}&x_{1}^{4}\\1&x_{2}^{2}&x_{2}^{4}\\1&x_{3}^{2}&x_{3}^{4}\end{array}}\right|=(x_{2}^{2}-x_{1}^{2})(x_{3}^{2}-x_{1}^{2})(x_{3}^{2}-x_{2}^{2})=0$ 如果 $x_{j}=-x_{i}$ 对于任何 $i\neq j$

问题 3

考虑线性方程组 $\!\,Ax=b$ ，其中 $\!\,A$ 是一个 n 阶对称正定矩阵。求解该系统的共轭梯度法 (CG) 为

Choose  $\!\,x_{0}$ , compute  $\!\,r_{0}=b-Ax_{0}$ 
 Set  $\!\,p_{0}=r_{0}$ 
 for  $\!\,k=0$  until convergence
  $\!\,\alpha _{k}=(r_{k},r_{k})/(p_{k},Ap_{k})$ 
  $\!\,x_{k+1}=x_{k}+\alpha _{k}p_{k}$ 
  $\!\,r_{k+1}=r_{k}-\alpha _{k}Ap_{k}$ 
 <Test for Convergence>
  $\!\,\beta _{k}=(r_{k+1},r_{k+1})/(r_{k},r_{k})$ 
  $\!\,p_{k+1}=r_{k+1}+\beta _{k}p_{k}$ 
end

其中 $\!\,(v,w)=\sum _{i=1}^{n}v_{i}w_{i}$ 是欧几里得内积。

令 $\!\,Q$ 是另一个 **对称**^[1] 正定矩阵，阶数为 $\!\,n$ 。我们知道形式

\langle v,w\rangle _{A}\equiv (Av,w)\quad \quad \quad \langle v,w\rangle _{Q}\equiv (Qv,w)

是在 $\!\,R^{n}$ 上的内积。此外，矩阵 $M\,\!$ 关于 $Q\,\!$ 内积 $\langle \,,\,\rangle _{Q}\,\!$ 对称，如果 $\langle Mv,w\rangle _{Q}=\langle v,Mw\rangle _{Q}\,\!$ 对于所有 $v,w\,\!$ 在 $R^{n}\,\!$ 中成立，并且 $M\,\!$ 关于 $\langle \,,\,\rangle _{Q}\,\!$ 正定，如果 $\langle Mv,v\rangle _{Q}>0\,\!$ 对于所有非零 $v\,\!$

问题 3a

证明 $Q^{-1}A\,\!$ 关于 $Q\,\!$ -内积是对称且正定的。

解 3a

{\begin{aligned}\langle Q^{-1}Av,w\rangle _{Q}&=(QQ^{-1}Av,w)\\&=(Av,w)\\\langle v,Q^{-1}Aw\rangle _{Q}&=(Qv,Q^{-1}Aw)\\&=(Q^{-T}Qv,Aw)\\&=(Q^{-1}Qv,Aw)\\&=(v,Aw)\\&=(A^{T}v,w)\\&=(Av,w)\\\\\langle Q^{-1}Av,v\rangle _{Q}&=(QQ^{-1}Av,v)\\&=(Av,v)\\&>0\\\end{aligned}}

问题 3b

鉴于此，CG 可以用来以适当的方式求解方程 $Q^{-1}Ax=Q^{-1}b\,\!$ 。指定该算法并指出任何与 $Q=I\,\!$ 相比所需额外计算量。

解 3b

Choose  $\!\,x_{0}$ 
 $\!\,r_{0}=b-Ax_{0}$ 
 ${\tilde {r}}_{0}$  :  solve  $Q{\tilde {r}}_{0}=r_{0}\!\,$ 
 $\!\,p_{0}={\tilde {r}}_{0}$ 
for  $\!\,k=0,1,2,...$  until convergence
  $\!\,\alpha _{k}=(r_{k},{\tilde {r}}_{k})/(p_{k},Ap_{k})$ 
  $\!\,x_{k+1}=x_{k}+\alpha _{k}p_{k}$ 
  $\!\,r_{k+1}=r_{k}-\alpha _{k}Ap_{k}$ 
 <Test for Convergence>
  ${\tilde {r}}_{k+1}$  :  solve  $Q{\tilde {r}}_{k+1}=r_{k+1}\!\,$ 
  $\!\,\beta _{k}=(r_{k+1},{\tilde {r}}_{k+1})/(r_{k},{\tilde {r}}_{k})$ 
  $\!\,p_{k+1}={\tilde {r}}_{k+1}+\beta _{k}p_{k}$ 
end