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

問題 1

考慮系統$Ax=b\,\!$。GMRES 方法從點$\,\!x_{0}$ 開始，並對殘差進行歸一化$\,\!r_{0}=b-Ax_{0}$，使得$\,\!v_{1}={\frac {r_{0}}{\nu }}$ 的 2 範數為 1。然後它構建正交的 Krylov 基$\,\!V_{k}=(v_{1}\,v_{2}\,\cdots v_{m})$ 滿足 $\,\!AV_{k}=V_{k+1}H_{k}$ 其中$\,\!H_{k}$ 是一個$\,\!(k+1)\times k$ 上 Hessenberg 矩陣。然後人們尋找$\displaystyle x$ 的近似形式 $\,\!x(c)=x_{0}+V_{k}c$ 選擇$\,\!c_{k}$ 使$\,\!\|r(c)\|=\|b-Ax(c)\|$ 最小化，其中$\,\!\|\cdot \|$ 是通常的歐幾里得範數。

問題 1a

證明$\,\!c_{k}$ 使$\|\nu e_{1}-H_{k}c\|$ 最小化。

解答 1a

我們需要證明$\,\!\|b-Ax(c)\|=\|\nu e_{1}-H_{k}c\|$

${\begin{aligned}\|b-Ax(c)\|&=\|b-A(x_{0}+V_{k}c)\|\\&=\|b-Ax_{0}-AV_{k}c\|\\&=\|r_{0}-AV_{k}c\|\\&=\|r_{0}-V_{k+1}H_{k}c\|\\&=\|\nu v_{1}-V_{k+1}H_{k}c\|\\&=\|V_{k+1}\underbrace {(\nu e_{1}-H_{k}c)} _{h_{c}}\|\\&=(V_{k+1}h_{c},V_{k+1}h_{c})^{\frac {1}{2}}\\&=((V_{k+1}h_{c})^{T}V_{k+1}h_{c})^{\frac {1}{2}}\\&=(h_{c}^{T}V_{k+1}^{T}V_{k+1}h_{c})^{\frac {1}{2}}\\&=(h_{c}^{T}h_{c})^{\frac {1}{2}}\\&=\|h_{c}\|\\&=\|\nu e_{1}-H_{k}c\|\end{aligned}}$

問題 1b

假設我們選擇使用正交三角化（QR）方法來求解問題a中的最小二乘問題以求解$c_{k}\!\,$。該方法的浮點運算順序是多少？請給出原因。

解答 1b

我們希望將$H_{k}\!\,$，一個$(k+1)\times k\!\,$ 上 Hessenberg 矩陣，轉換為 QR 形式。

成本大約為$4k^{2}+{\frac {1}{2}}k^{2}=4.5k^{2}$，來自 Given's 旋轉和回代的成本。

Given's 旋轉成本

我們需要$k\!\,$ 個 Given's 旋轉相乘以將每個$k\!\,$ 個次對角線項置零，從而將$H_{k}\!\,$ 轉換為上三角形式$R\!\,$，

每次連續的 Given's 旋轉乘以一個上 Hessenberg 矩陣需要減少四個乘法，因為每個先前的次對角線項已被 Given's 旋轉乘法置零。

因此，$k\!\,$ 個 Given's 旋轉相乘的成本為

$4k+4(k-1)+\ldots +4\cdot 1<4k\cdot k=4k^{2}$

回代成本

$R\!\,$ 是一個$(k+1)\times k\!\,$ 上三角矩陣，最後一行全為零。因此，我們需要回代$k\!\,$ 行上三角。

$1+2+\ldots +k={\frac {k(k+1)}{2}}={\frac {k^{2}}{2}}+{\frac {k}{2}}$

問題 2

我們希望近似積分$I(f)\equiv \int _{a}^{b}f(x)dx$

問題 2a

說明覆合梯形法則$Q_{T,n}\!\,$ 用於逼近$I(f)\!\,$ 在寬度為$h={\frac {b-a}{n}}\!\,$ 的均勻劃分上，並給出誤差$I(f)-Q_{T,n}\!\,$ 的公式，該公式適合外推。

解 2a

複合梯形法則為

$Q_{T,n}(f)={\frac {h}{2}}(f(a)+f(b))+h\sum _{k=1}^{n-1}f(x_{k})\!\,$

誤差為

$I(f)-Q_{T,n}(f)=-{\frac {(b-a)f^{\prime \prime }(\xi )}{12}}h^{2}$

其中 $\xi \in [a,b]\!\,$.

複合梯形誤差推導

區域性誤差，即在一個區間上的誤差，為

$-{\frac {h^{3}}{12}}f^{\prime \prime }(\eta )\!\,$.

觀察到

$n\min _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\leq \sum _{i=1}^{n}f^{\prime \prime }(\eta _{i})\leq n\max _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\!\,$

這意味著

$\min _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\leq \sum _{i=1}^{n}{\frac {f^{\prime \prime }(\eta _{i})}{n}}\leq \max _{\eta \in [a,b]}f^{\prime \prime }(\eta _{i})\!\,$

因此，中值定理意味著存在一個 $\xi \in [a,b]\!\,$ 使得

$f^{\prime \prime }(\xi )=\sum _{i=1}^{n}{\frac {f^{\prime \prime }(\eta _{i})}{n}}\!\,$.

將等式兩邊都乘以 $n\!\,$,

$nf^{\prime \prime }(\xi )=\sum _{i=1}^{n}f^{\prime \prime }(\eta _{i})\!\,$

使用此關係，我們有

${\begin{aligned}I(f)-Q_{T,n}(f)&=\sum _{i=1}^{n}I_{i}(f)-Q_{i}(f)\\&=\sum _{i=1}^{n}\left[-{\frac {h^{3}}{12}}f^{\prime \prime }(\eta _{i})\right]\\&=-{\frac {h^{3}}{12}}f^{\prime \prime }(\xi )n\\&=-{\frac {h^{3}}{12}}f^{\prime \prime }(\xi )({\frac {b-a}{h}})\\&=-{\frac {h^{2}}{12}}f^{\prime \prime }(\xi )(b-a)\end{aligned}}$

區域性誤差的推導

多項式插值的誤差可以透過使用以下定理找到

 Assume $f^{n+1}\!\,$ exists on $[a,b]\!\,$ and $\{x_{0},x_{1},\ldots ,x_{n}|x\in [a,b]\}.\!\,$ $P_{n}\!\,$ interpolates $f\!\,$ at $\{x_{j}\}_{j=0}^{n}\!\,$.  
 Then there is a $\xi _{x}\!\,$ ($\xi \!\,$ is dependent on $x\!\,$) such that 
 
 $f(x)-p_{n}(x)={\frac {(x-x_{0})(x-x_{1})...(x-x_{n})}{(n+1)!}}f^{(n+1)}(\xi _{x})\!\,$
 
 where $\xi _{x}\!\,$ lies in $(m,M)\!\,$,  $m=\min\{x_{0},x_{1},\ldots ,x_{n},X\}\!\,$,  $M=\max\{x_{0},x_{1},\ldots ,x_{n},X\}\!\,$

應用該定理得到：

$f(x)-p_{1}(x)=(x-a)(x-b){\frac {f^{\prime \prime }(\xi _{x})}{2}}$

因此，

${\begin{aligned}E(f)&=\int _{a}^{b}f(x)-p_{1}(x)dx\\&=\int _{a}^{b}\underbrace {\underbrace {(x-a)} _{>0}\underbrace {(x-b)} _{<0}} _{w(x)}{\frac {f^{\prime \prime }(\xi _{x})}{2}}dx\end{aligned}}$

由於 $a\!\,$ 是區間的起點，$x-a\!\,$ 總是正數。相反，由於 $b\!\,$ 是區間的終點，$x-b\!\,$ 總是負數。因此，$w(x)<0\!\,$ 的符號始終一致。因此，根據 積分中值定理，存在一個 $\zeta \in [a,b]\!\,$ 使得

$E(f)={\frac {f^{\prime \prime }(\zeta )}{2}}\int _{a}^{b}(x-a)(x-b)dx\!\,$

請注意，$f^{\prime \prime }(\zeta )$ 是一個常數，與 $x\!\,$ 無關。

對 $\int _{a}^{b}(x-a)(x-b)dx\!\,$ 進行積分，得到：

${\begin{aligned}E(f)&={\frac {f^{\prime \prime }(\zeta )}{2}}\left(-{\frac {(b-a)}{6}}\right)\\&=-{\frac {f^{\prime \prime }(\zeta )(b-a)}{12}}\!\,\end{aligned}}$

問題 2b

使用誤差公式推導一個新的求積公式，該公式透過對複合梯形公式進行一次外推得到。這個公式是什麼？它的誤差如何依賴於 $h\!\,$？你可以假設 $f\!\,$ 是你需要的那樣光滑。

解 2b

STOER AND BUESCH 第 162 頁

RICHARD HAMMING 的《應用數值分析導論》第 178 頁

複合梯形公式在 $n\!\,$ 個點時的誤差為

$E_{n}=I(f)-Q_{T,n}={\frac {-(b-a)h^{2}}{12}}+{\mathcal {O}}(h^{3})\!\,$

當有 $2n\!\,$ 個點時，有雙倍的區間，但是區間寬度減半。因此，複合梯形公式在 $2n\!\,$ 個點時的誤差為

$E_{2n}=I(f)-Q_{T,2n}=2\cdot {\frac {-(b-a)({\frac {h}{2}})^{2}}{12}}+{\mathcal {O}}(h^{3})={\frac {-(b-a)h^{2}}{24}}+{\mathcal {O}}(h^{3})\!\,$

我們可以透過選擇 $E_{n}\!\,$ 和 $E_{2n}\!\,$ 的適當線性組合來消除 $h^{2}\!\,$ 項。這將得到一個新的誤差規則，該規則的誤差為 $h^{3}\!\,$。

${\begin{aligned}E_{n}-2E_{2n}&={\frac {-(b-a)h^{2}}{12}}-2\cdot {\frac {-(b-a)h^{2}}{24}}+{\mathcal {O}}(h^{3})\\&={\mathcal {O}}(h^{3})\end{aligned}}$

將我們對 $E_{n}\!\,$ 和 $E_{2n}\!\,$ 的方程代入左側，得到

$I(f)-Q_{T,n}-2I(f)-2Q_{T,2n}={\mathcal {O}}(h^{3})\!\,$

$I(f)=2Q_{T,2n}-Q_{T,n}+{\mathcal {O}}(h^{3})\!\,$

如果我們把這個新規則稱為 ${\hat {Q}}\!\,$，我們有

${\hat {Q}}=2Q_{T,2n}-Q_{T,n}\!\,$，其誤差為 ${\mathcal {O}}(h^{3})\!\,$ 級。

問題 3

考慮用於計算 2 x 2 矩陣 $A\!\,$ 的移位 QR 迭代：從 $A_{0}=A\!\,$ 開始，計算 $A_{k}-\sigma _{k}I=Q_{k}R_{k}\quad \quad \quad A_{k+1}=R_{k}Q_{k}+\sigma _{k}I$ 其中 $\sigma _{k}\!\,$ 是一個標量位移。

問題 3a

如果 $A_{k}={\begin{bmatrix}a_{11}&a_{12}\\a_{21}&a_{22}\end{bmatrix}},$ 指定正交矩陣 $Q_{k}\!\,$，在使用 Givens 旋轉進行此步驟時，該矩陣應使用平移矩陣的條目進行描述。

解 3a

設 ${\tilde {A}}_{k}\!\,$ 是 $\sigma _{k}\!\,$ 平移的 $A_{k}\!\,$ 矩陣，即

${\tilde {A}}_{k}=A_{k}-\sigma _{k}I={\begin{bmatrix}a_{11}-\sigma _{k}&a_{12}\\a_{21}&a_{22}-\sigma _{k}\end{bmatrix}},$

$Q_{k}^{T}\!\,$ 是一個 2x2 的正交 Givens 旋轉矩陣。 $Q_{k}^{T}\!\,$ 的條目被選擇，這樣當 $Q_{k}^{T}\!\,$ 乘以 2x2 矩陣 ${\tilde {A}}_{k}\!\,$ 時， $Q_{k}^{T}\!\,$ 將使 ${\tilde {A}}_{k}\!\,$ 的 (2,1) 項為零，並按比例縮放 ${\tilde {A}}_{k}\!\,$ 的剩餘三個條目，即

$Q_{k}^{T}{\tilde {A}}_{k}={\begin{bmatrix}*&*\\0&*\end{bmatrix}}=R_{k}$

其中 $*\!\,$ 表示我們不感興趣的可計算標量值，而 $R_{k}\!\,$ 是我們使用 QR 演算法尋求的所需上三角矩陣。

由於 $Q_{k}^{T}\!\,$ 是正交的，上面的等式意味著

${\begin{aligned}Q_{k}^{T}{\tilde {A}}_{k}&=R_{k}\\Q_{k}Q_{k}^{T}{\tilde {A}}_{k}&=Q_{k}R_{k}\\{\tilde {A}}_{k}&=Q_{k}R_{k}\end{aligned}}$

給定旋轉 $Q_{k}^{T}\!\,$ 由下式給出

$Q_{k}^{T}={\begin{bmatrix}c&s\\-s&c\end{bmatrix}}$

其中

${\begin{aligned}c&={\frac {a_{11}-\sigma _{k}}{r}}\\s&={\frac {a_{21}}{r}}\\r&={\sqrt {(a_{11}-\sigma _{k})^{2}+a_{21}^{2}}}\end{aligned}}$

對 $Q_{k}^{T}\!\,$ 求轉置，得到

$Q_{k}={\begin{bmatrix}c&-s\\s&c\end{bmatrix}}$

問題 3b

假設 $a_{21}=\delta \!\,$，一個小數，並且 $|a_{12}|\leq (a_{11}-a_{22})^{2}\!\,$。證明，透過適當的平移 $\sigma _{k}\!\,$，$A_{k+1}\!\,$ 的 (2,1) 項的大小為 $O(\delta ^{2})\!\,$。這對於 QR 迭代的收斂速度說明了什麼？

解 3b

根據假設和（a）部分，

${\begin{aligned}A_{k+1}&=R_{k}Q_{k}+\sigma _{k}I\\&={\begin{bmatrix}*&*\\0&r_{22}\end{bmatrix}}{\begin{bmatrix}c&-s\\s&c\end{bmatrix}}+{\begin{bmatrix}\sigma _{k}&0\\0&\sigma _{k}\end{bmatrix}}\end{aligned}}$

令 $A_{k+1}(2,1)\!\,$ 是 $A_{k}\!\,$ 的 (2,1) 項。利用上面的等式，我們可以透過求 $R_{k}\!\,$ 的第二行和 $Q_{k}\!\,$ 的第一列的內積，並加上 $\sigma _{k}I\!\,$ 的 (2,1) 項來找到 $A_{k+1}(2,1)\!\,$，即

${\begin{aligned}A_{k+1}(2,1)&=(0\cdot c+r_{22}\cdot s)+0\\&=r_{22}s\end{aligned}}$

我們需要找到 $r_{22}\!\,$ 的值，所以我們需要計算 $R_{k}\!\,$.

根據假設和 $Q_{k}\!\,$ 的正交性，我們有

${\begin{aligned}A_{k}-\sigma _{k}I&=Q_{k}R_{k}\\Q_{k}^{T}(A_{k}-\sigma _{k}I)&=Q_{k}^{T}Q_{k}R_{k}\\Q_{k}^{T}(A_{k}-\sigma _{k}I)&=R_{k}\\R_{k}&=Q_{k}^{T}(A_{k}-\sigma _{k}I)\\&={\begin{bmatrix}c&s\\-s&c\end{bmatrix}}{\begin{bmatrix}a_{11}-\sigma _{k}&a_{12}\\\delta &a_{22}-\sigma _{k}\end{bmatrix}}\end{aligned}}$

從 $R_{k}\!\,$ 中，我們可以透過使用內積找到其 (2,2) 元素 $r_{2}2\!\,$。

$r_{22}=-s\cdot a_{12}+c\cdot (a_{22}-\sigma _{k})\!\,$

現在我們有了 $r_{22}\!\,$，我們可以透過使用適當的代入來計算 $A_{k+1}(2,1)\!\,$。

${\begin{aligned}A_{k+1}(2,1)&=r_{22}\cdot s\\&=(-sa_{12}+c(a_{22}-\sigma _{k}))s\\&=-s^{2}a_{12}+cs(a_{22}-\sigma _{k})\\&={\frac {-\delta ^{2}a_{12}}{(a_{11}-\sigma _{k})^{2}+\delta ^{2}}}+{\frac {(a_{11}-\sigma _{k})(a_{22}-\sigma _{k})\delta }{(a_{11}-\sigma _{k})^{2}+\delta ^{2}}}\\&={\frac {-\delta ^{2}a_{12}+\delta (a_{11}-\sigma _{k})(a_{22}-\sigma _{k})}{(a_{11}-\sigma _{k})^{2}+\delta ^{2}}}\\&\approx {\frac {-\delta ^{2}a_{12}+\delta (a_{11}-\sigma _{k})(a_{22}-\sigma _{k})}{(a_{11}-\sigma _{k})^{2}}}\end{aligned}}$

因為 $\delta \!\,$ 是一個很小的數。

令我們的平移 $\sigma _{k}=a_{22}\!\,$。 那麼上面的等式將得到：

${\begin{aligned}A_{k+1}(2,1)&\approx {\frac {-\delta ^{2}a_{12}+\delta (a_{11}-\sigma _{k})(a_{22}-\sigma _{k})}{(a_{11}-\sigma _{k})^{2}}}\\&\approx {\frac {-\delta ^{2}a_{12}+\delta (a_{11}-a_{22})(a_{22}-a_{22})}{(a_{11}-a_{22})^{2}}}\\&={\frac {-\delta ^{2}a_{12}}{(a_{11}-a_{22})^{2}}}\end{aligned}}$

因此，

${\begin{aligned}|A_{k+1}(2,1)|&\approx \left|{\frac {\delta ^{2}a_{12}}{(a_{11}-a_{22})^{2}}}\right|\\&\leq |\delta ^{2}|\end{aligned}}$

因為 $|a_{12}|\leq (a_{11}-a_{22})^{2}\!\,$

因此，我們已經證明 $A_{k+1}(2,1)\!\,$ 是 $\delta ^{2}\!\,$ 階。

如果 $\delta \!\,$ 很小，則 QR 收斂速度將是二次的。