數值方法資格考試問題及解答（馬里蘭大學）/2004年1月

問題 1

令 $a=x_{0}<x_{1}<\cdots <x_{n}=b\!\,$ 是區間 $[a,b]\!\,$ 的任意固定分割槽。函式 $q(x)\!\,$ 是一個二次樣條函式，如果 (i) $q\in C^{1}[a,b]\!\,$ (ii) 在每個子區間 $[x_{i},x_{i+1}]\!\,$ 上，$q\!\,$ 是一個二次多項式。 問題是構造一個二次樣條 $q(x)\!\,$ 來插值資料點 $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\!\,$。該構造類似於三次樣條的構造，但要容易得多。

問題 1a

證明如果我們知道 $z_{i}\equiv q'(x_{i}),i=0,\ldots ,n\!\,$，我們可以構造 $q\!\,$。

解答 1a

考慮區間 $[x_{i},x_{i+1}]\!\,$. 由於 $q'_{i}(x)\!\,$ 在此區間上是線性的，使用點斜式，我們有

$q_{i}'(x)={\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}(x-x_{i})+z_{i}\!\,$

積分，我們有

$q_{i}(x)=z_{i}x+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+K_{i}\!\,$

或者，用更方便的形式，

$q_{i}(x)=z_{i}(x-x_{i})+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+y_{i}\!\,$

問題 1b

找到能夠確定 $z_{i}\!\,$ 的方程。你應該發現其中一個 $z_{i}\!\,$ 可以任意指定，例如 $z_{0}=0\!\,$

解 1

由於 $q\!\,$ 在 $[a,b]\!\,$ 上是連續的，

$q_{i-1}(x_{i})=q_{i}(x_{i})=y_{i}\!\,$

即

$z_{i-1}(x_{i}-x_{i-1})+{\frac {z_{i}-z_{i-1}}{x_{i}-x_{i-1}}}{\frac {(x_{i}-x_{i-1})^{2}}{2}}+y_{i-1}=y_{i}\!\,$

簡化並重新排列項，得到遞迴公式

$z_{i}=-z_{i-1}+{\frac {2(y_{i}-y_{i-1})}{x_{i}-x_{i-1}}}\quad i=1,\ldots n\!\,$

問題 2a

給出$QR\!\,$ 演算法的定義，該演算法用於尋找矩陣 $A\!\,$ 的特徵值。 定義無移位版本和帶有移位 $\chi _{0},\chi _{1},\chi _{2},\ldots \!\,$ 的版本。

解答 2a

無移位版本

$Q_{k}R_{k}=A_{k}\!\,$

$A_{k+1}=R_{k}Q_{k}\!\,$

移位版本

$Q_{k}R_{k}=A_{k}-\chi _{k}I\!\,$

$A_{k+1}=R_{k}Q_{k}+\chi _{k}I\!\,$

問題 2b

證明在每種情況下，由 $QR\!\,$ 演算法生成的矩陣 $A_{1},A_{2}\!\,$ 與 $A\!\,$ 酉等價（即 $A_{i}=U_{i}AU_{i}^{H},U_{i}\!\,$ 為酉矩陣）。

解 2b

假設存在某個酉矩陣 $U$，使得 $A_{m}=U^{T}AU$。由於 $R_{m}=Q_{m}^{T}A_{m}$，我們有

$A_{m+1}=R_{m}Q_{m}=Q_{m}^{T}A_{m}Q_{m}=Q_{m}^{T}U^{T}AUQ_{m}$

這符合我們的預期，因為 $Q_{m}U$ 是酉矩陣。

對於移位的情況，使用 $R_{m}=Q_{m}^{T}(A_{m}-\chi _{m}I)$ 這個事實，相同的論證也成立。

問題 2c

設 $A={\begin{pmatrix}3&1\\1&2\end{pmatrix}}\!\,$ 使用平面旋轉（Givens 旋轉）對 $QR\!\,$ 演算法執行一步操作，首先不進行平移，然後使用平移 $\chi _{0}=1\!\,$。 哪個方法效果更好？ $A\!\,$ 的特徵值為 $\lambda _{1}=1.382,\lambda _{2}=3.618\!\,$。 （回想一下，平面旋轉是一個形式為 $Q={\begin{pmatrix}c&-s\\s&c\end{pmatrix}}\!\,$ 的矩陣，其中 $c^{2}+s^{2}=1\!\,$

解決方案 2c

平移迭代似乎效果更好，因為它的對角線元素比未平移迭代的對角線元素更接近實際特徵值。

未平移迭代

$A_{1}={\begin{pmatrix}3.5&.5\\.5&1.5\end{pmatrix}}\!\,$

平移迭代

$A_{1}={\begin{pmatrix}3.6&.2\\.2&1.4\end{pmatrix}}\!\,$

問題 3

設 $A\!\,$ 是一個 $N\times N\!\,$ 對稱正定矩陣。那麼我們知道求解 $Ax=b\!\,$ 等價於最小化泛函 $F(x)={\frac {1}{2}}\langle x,Ax\rangle -\langle b,x\rangle \!\,$，其中 $\langle \cdot ,\cdot \rangle \!\,$ 表示 $R^{N}\!\,$ 中的標準內積。為了透過最小化 $F\!\,$ 來解決問題，我們考慮一般的迭代方法 $x_{v+1}=x_{v}+\alpha _{v}d_{v}\!\,$

問題 3a

當 $x_{v}\!\,$ 和 $d_{v}\!\,$ 給定，證明最小化 $F(x_{v}+\alpha d_{v})\!\,$（作為 $\alpha \!\,$ 的函式）的 $\alpha _{v}\!\,$ 值可以用殘差 $r_{v}\!\,$ 表示為 $\alpha _{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }},\quad r_{v}=b-Ax_{v}\!\,$

解決方案 3a

有用的關係

由於 $A\!\,$ 是對稱的

$(Ax,y)=(x,A^{T}y)=(x,Ay)\!\,$

此關係將在整個解決方案中使用。

代入泛函

${\begin{aligned}F(x_{v}+\alpha d_{v})&={\frac {1}{2}}\langle x_{v}+\alpha d_{v},Ax_{v}+\alpha Ad_{v}\rangle -\langle b,x_{v}+\alpha d_{v}\rangle \\&={\frac {\langle d_{v},Ad_{v}\rangle }{2}}\alpha ^{2}+\alpha \langle d_{v},Ax_{v}\rangle -\alpha \langle b,d_{v}\rangle +{\frac {1}{2}}\langle x_{v},Ax_{v}\rangle -\langle b,x_{v}\rangle \end{aligned}}\!\,$

對 alpha 求導數

$F'(x_{v}+\alpha d_{v})=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}\rangle -\langle b,d_{v}\rangle \!\,$

將導數設為零

$0=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}-b\rangle \!\,$

這意味著

$\alpha ={\frac {\langle d_{v},r_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,$

問題 3b

令 $\{d_{j}\}_{j=1}^{N}\!\,$ 是 $A\!\,$-正交基於 $R^{N}\!\,$，$\langle d_{j},Ad_{k}\rangle =0,j\neq k\!\,$。考慮解 $x\!\,$ 在此基下的展開式 $x=\sum _{j=1}^{N}{\hat {x_{j}}}d_{j}\!\,$ 利用 $A-\!\,$正交性來計算 ${\hat {x}}_{j}\!\,$ 關於解 $x\!\,$ 和 $d_{j}\!\,$ 的表示式

解 3b

${\begin{aligned}\langle x,Ad_{k}\rangle &=\langle \sum _{j=1}^{n}{\hat {x}}_{j}d_{j},Ad_{k}\rangle \\&=\sum _{j=1}^{N}{\hat {x}}_{j}\langle d_{j},Ad_{k}\rangle \\&={\hat {x}}_{k}\langle d_{k},Ad_{k}\rangle \end{aligned}}\!\,$

這意味著

${\hat {x}}_{k}={\frac {\langle x,Ad_{k}\rangle }{\langle d_{k},Ad_{k}\rangle }}\!\,$

問題 3c

令 $x_{v}\!\,$ 表示部分和 $x_{v}=\sum _{j=1}^{v-1}{\hat {x}}_{j}d_{j},\quad v=2,3,\ldots \!\,$ 使得 $x_{v+1}=x_{v}+{\hat {x}}_{v}d_{v}\!\,$ 其中 ${\hat {x}}_{v}\!\,$ 是在 (b) 中找到的係數。利用 $x_{v}\in {\mbox{span}}\{d_{1},d_{2},\ldots ,d_{v-1}\}\!\,$ 以及 $A\!\,$-正交性的 $d_{j}\!\,$ 推斷出係數 ${\hat {x}}_{v}\!\,$ 由最優 $\alpha _{v}\!\,$ 給出，即 ${\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}=\alpha _{v}\!\,$

解 3c

${\begin{aligned}\langle r_{v},d_{v}\rangle &=\langle b-Ax_{v},d_{v}\rangle \\&=\langle Ax-Ax_{v},dv\rangle \\&=\langle Ax,d_{v}\rangle -\langle Ax_{v},d_{v}\rangle \\&=\langle x,Ad_{v}\rangle -\underbrace {\langle x_{v},Ad_{v}\rangle } _{0}\\&={\hat {x}}_{v}\langle d_{v},Ad_{v}\rangle \end{aligned}}\!\,$

這意味著

${\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,$