數值方法資格考試試題及解答（馬里蘭大學）/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