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

問題 1

考慮定積分 $I(f)=\int _{a}^{b}f(x)dx\!\,$ 令$Q_{n}(f)\!\,$ 表示用具有 $n\!\,$ 個均勻子區間的複合中點規則對$I(f)\!\,$ 的近似值。對於每個$j\in \mathbb {Z} \!\,$ 設定 $x_{j}=a+j{\frac {b-a}{n}},\quad \quad x_{j+{\frac {1}{2}}}={\frac {x_{j}+x_{j+1}}{2}}\!\,$. 令$K(x)\!\,$ 由下式定義 $K(x)=-{\frac {1}{2}}(x-x_{j})^{2},\quad x_{j-{\frac {1}{2}}}<x<x_{j+{\frac {1}{2}}}\!\,$. 假設$f\in C^{2}([a,b])\!\,$.

問題 1a

證明正交誤差$E_{n}(f)\!\,$ 滿足 $E_{n}\equiv Q_{n}(f)-I(f)=\int _{a}^{b}K(x)f''(x)dx\!\,$ 提示：對每個子區間 $[x_{j-1},x_{j}]\!\,$ 使用分部積分。

解法 1a

對 $\int K(x)f''(x)dx\!\,$ 進行分部積分，積分割槽間為任意點 $p\!\,$ 和 $q\!\,$ ，得到

$\int _{p}^{q}K(x)f''(x)dx=\left[(x-x_{j})f(x)-{\frac {1}{2}}(x-x_{j})^{2}f'(x)\right]_{x=p}^{x=q}-\int _{p}^{q}f(x)dx\!\,$

由於 $K(x)\!\,$ 定義在 $[x_{j-{\frac {1}{2}}},x_{j+{\frac {1}{2}}}]\!\,$ 上，我們使用

$[p,q]=[x_{j},x_{j+{\frac {1}{2}}}]\!\,$

和

$[p,q]=[x_{j-{\frac {1}{2}}},x_{j}]\!\,$

使用第一個區間，我們得到

${\frac {1}{2}}\left[-{\frac {1}{4}}(x_{j+1}-x_{j})^{2}f'(x_{j+{\frac {1}{2}}})+(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})\right]\qquad \mathbf {(1)} \!\,$

對於第二個區間，我們得到

${\frac {1}{2}}\left[{\frac {1}{4}}(x_{j-1}-x_{j})^{2}f'(x_{j-{\frac {1}{2}}})+(x_{j}-x_{j-1})f(x_{j-{\frac {1}{2}}})\right]\qquad \mathbf {(2)} \!\,$

由於這些公式適用於任意半個子區間，我們可以將方程 $\mathbf {(2)} \!\,$ 的索引移動一個單位。對於區間 $[x_{j+{\frac {1}{2}}},x_{j+1}]\!\,$ 的公式為

${\frac {1}{2}}\left[{\frac {1}{4}}(x_{j}-x_{j+1})^{2}f'(x_{j+{\frac {1}{2}}})+(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})\right]\qquad \mathbf {(2')} \!\,$

將 $\mathbf {(1)} \!\,$ 和 $\mathbf {(2')} \!\,$ 結合起來，並以與分部積分相同的形式寫出來，得到

$\int _{x_{j}}^{x_{j+1}}K(x)f''(x)dx=(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})-\int _{x_{j}}^{x_{j+1}}f(x)dx\!\,$

最後一步是對所有 $n\!\,$ 個子區間進行求和，注意到 $x_{j+1}-x_{j}=(b-a)/n\!\,$

${\begin{aligned}\sum _{j=0}^{n-1}\int _{x_{j}}^{x_{j+1}}K(x)f''(x)dx&=\sum _{j=0}^{n-1}(x_{j+1}-x_{j})f(x_{j+{\frac {1}{2}}})-\sum _{j=0}^{n-1}\int _{x_{j}}^{x_{j+1}}f(x)dx\\\int _{a}^{b}K(x)f''(x)dx&={\frac {b-a}{n}}\sum _{j=0}^{n-1}f((x_{j}+x_{x+1})/2)-\int _{a}^{b}f(x)dx\\\int _{a}^{b}K(x)f''(x)dx&=Q_{n}(f)-I(f)\end{aligned}}$

問題 1b

推匯出誤差的嚴格界，形式如下 $|E_{n}(f)|\leq M_{n}\|f''\|_{\infty }\!\,$ 對於每個 $f\in C^{2}([a,b])\!\,$. 這裡 $\|\cdot \|_{\infty }\!\,$ 表示在 $[a,b]\!\,$ 上的最大範數。請記住，當不等式對於某個非零 $f\!\,$ 等於時，上述界是嚴格的。

解 1b

應用 (a) 部分的結果，三角不等式，並提取常數 $\|f(x)\|_{\infty }\!\,$，我們有

${\begin{aligned}|E_{n}(f)|&=|\int _{a}^{b}K(x)f^{\prime \prime }(x)dx|\\&\leq \int _{a}^{b}|K(x)||f^{\prime \prime }(x)|dx\\&\leq \|f^{\prime \prime }(x)\|_{\infty }\underbrace {\int _{a}^{b}|K(x)|dx} _{M_{n}}\end{aligned}}$

$M_{n}\!\,$ 是一個有限常數，因為 $[a,b]\!\,$ 是緊集，並且 $|K(x)|\!\,$ 在它定義的每個有限個區間上是連續的。

當

$f''(x)=c,$

時，上述不等式成為等式，其中 $c$ 是任意常數。

問題 2

考慮用於求可逆矩陣 $A\in \mathbb {R} ^{n\times n}\!\,$ 特徵值的（未移位）$QR-\!\,$ 演算法。

問題 2a

給出演算法。

解答 2a

QR 演算法產生一系列相似的矩陣 $\{A_{i}\}\!\,$，它們的極限趨向於上三角形或接近上三角形。這是有利的，因為上三角矩陣的特徵值位於其對角線上。

i = 0   
A_1 = A 
while ( error > tolerance  )   
   A_i=Q_i R_i  (QR decomposition/factorization)
   A_{i+1}=R_i Q_i (multiply R and Q, the reverse multiplication)
   i=i+1 (increment)

問題 2b

證明由該演算法生成的每個矩陣 $A_{n}\!\,$ 與 $A\!\,$ 正交相似。

解答 2b

從演算法的因式分解步驟（QR 分解）中，我們有

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

這意味著

$Q_{i}^{-1}A_{i}=R_{i}\!\,$

將此代入逆向相乘步驟，我們得到

${\begin{aligned}A_{i+1}&=R_{i}Q_{i}\\&=Q_{i}^{-1}A_{i}Q_{i}\end{aligned}}$

問題 2c

證明如果 $A\!\,$ 是上 Hessenberg 矩陣，那麼由該演算法生成的每個矩陣 $A_{n}\!\,$ 也是上 Hessenberg 矩陣。

解答 2c

一系列 Givens 旋轉矩陣左乘 $A\!\,$（一個上 Heisenberg 矩陣）產生一個上三角矩陣 $R\!\,$，即

$G_{(n-1,n)}\cdots G_{(2,3)}G_{(1,2)}A=R\!\,$

由於 Givens 旋轉矩陣都是正交矩陣，我們可以寫成

$A=\underbrace {(G_{(n-1,n)}\cdots G_{(2,3)}G_{(1,2)})^{T}} _{Q}R\!\,$

即

$A=QR\!\,$

如果我們令 $A_{0}:=A\!\,$，我們有 $A_{0}=Q_{0}R_{0}\!\,$，或者更一般地，對於 $k=1,2,3,\ldots \!\,$

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

在每種情況下，構成 $Q\!\,$ 的一系列 Givens 旋轉矩陣具有以下結構

${\begin{aligned}Q&=G_{(1,2)}^{T}G_{2,3}^{T}\cdots G_{(n-1,n)}^{T}\\&={\begin{pmatrix}*&*&0&0&\cdots &0\\\!\,*&*&0&0&\cdots &0\\0&0&1&0&\cdots &0\\0&0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&\cdots &\cdots &0&1\\\end{pmatrix}}{\begin{pmatrix}1&0&0&0&\cdots &0\\0&*&*&0&\cdots &0\\0&*&*&0&\cdots &0\\0&0&0&1&\cdots &0\\\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&\cdots &\cdots &0&1\\\end{pmatrix}}\cdots {\begin{pmatrix}1&0&0&0&\cdots &0\\0&1&0&0&\cdots &0\\\vdots &\ddots &\ddots &\ddots &\ddots &0\\0&0&0&1&0&0\\0&0&0&0&*&*\\0&0&0&0&*&*\\\end{pmatrix}}\\&={\begin{pmatrix}*&*&*&\cdots &*\\\!\,*&*&*&\cdots &*\\0&*&*&\cdots &*\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&0&0&*&*\\\end{pmatrix}}\end{aligned}}$

所以 $Q\!\,$ 是上 Hessenberg 矩陣。

從演算法中，我們有

${\begin{aligned}A_{k+1}&=R_{k}Q_{k}\\&={\begin{pmatrix}*&*&*&\cdots &*\\0&*&*&\cdots &*\\0&0&*&\cdots &*\\\vdots &\vdots &\ddots &\ddots &\vdots \\0&0&0&0&*\\\end{pmatrix}}{\begin{pmatrix}*&*&*&\cdots &*\\\!\,*&*&*&\cdots &*\\0&*&*&\cdots &*\\\vdots &\ddots &\ddots &\ddots &\vdots \\0&0&0&*&*\\\end{pmatrix}}\end{aligned}}$

我們可以得出結論，$A_{k+1}\!\,$ 是上 Hessenberg 矩陣，因為對於 $j=1,2,\ldots ,n-2\!\,$，$A_{k+1}\!\,$ 的第 $j\!\,$ 列是 $R_{k}\!\,$ 的前 $j+1\!\,$ 列的線性組合，因為 $Q_{k}\!\,$ 也是上 Hessenberg 矩陣。

問題 2d

設 ${\begin{pmatrix}3&3\\1&5\end{pmatrix}}$ 對於這個 $A\!\,$，序列 $\{A_{n}\}\!\,$ 有一個極限。找到這個極限。給出你的推理。

解答 2d

可以計算出 $A\!\,$ 的特徵值。它們是 $6\!\,$ 和 $2\!\,$。此外，演算法中矩陣相乘的結果表明，對角線差 $(a_{1,2}-a_{2,1})\!\,$ 對於所有 $i\!\,$ 都是常數。

由於 $A\!\,$ 的極限是一個上三角矩陣，對角線上是 $A\!\,$ 的特徵值，所以極限是

${\begin{pmatrix}6&2\\0&2\end{pmatrix}}\!\,$

問題 3

令 $A\in \mathbb {R} ^{N\times N}\!\,$ 為對稱正定矩陣。令 $b\in \mathbb {R} ^{N}\!\,$。考慮使用共軛梯度法求解 $Ax=b\!\,$。則第 $n^{th}\!\,$ 次迭代 $x^{(n)}\!\,$ 滿足 $\|x^{(n)}-x\|_{A}\leq \|y-x\|_{A}\!\,$ 對於所有 $y\in x^{(0)}+{\mathcal {K}}_{n}(r^{(0)},A)\!\,$， 其中 $\|\cdot \|_{A}\!\,$ 表示向量 A-範數，$r^{(0)}\!\,$ 是初始殘差，並且 ${\mathcal {K}}_{n}(r^{(0)},A)={\mbox{span}}\{r^{(0)},Ar^{(0)},\dots ,A^{n-1}r^{(0)}\}\!\,$.

問題 3a

證明誤差 $x^{(n)}-x\!\,$ 有界為 $\|x^{(n)}-x\|_{A}\leq \|p_{n}(A)\|_{A}\|x^{(0)}-x\|_{A}\!\,$, 其中 $p_{n}(z)\!\,$ 是任何滿足 $p_{n}(0)=1\!\,$ 的不超過 $n\!\,$ 次的實多項式。這裡 $\|p_{n}(A)\|_{A}\!\,$ 表示由向量 A-範數引起的 $p_{n}(A)\!\,$ 的矩陣範數。

解答 3a

我們知道對於任何 $y\in x^{(0)}+{\mathcal {K}}_{n}(r^{(0)},A)\!\,$，都有 $\|x^{(n)}-x\|_{A}\leq \|y-x\|_{A}\!\,$。因此，如果我們能找到一個 $y\in x^{(0)}+{\mathcal {K}}_{n}(r^{(0)},A)\!\,$ 使得

$\|x^{(n)}-x\|_{A}\leq \|y-x\|_{A}\leq \|p_{n}(A)\|_{A}\|x^{(0)}-x\|_{A}\!\,$,

那麼我們就可以解決部分 a。

重寫 r^(0)

首先從 $r^{(0)}\!\,$ 的定義出發，

${\begin{aligned}r^{(0)}&=Ax^{(0)}-b\\&=Ax^{(0)}-Ax\\&=A(x^{(0)}-x)\end{aligned}}$

重寫 Krylov 空間

因此，我們可以將 ${\mathcal {K}}_{n}(r^{(0)},A)\!\,$ 重寫如下

${\begin{aligned}{\mathcal {K}}_{n}(r^{(0)},A)&={\mathcal {K}}_{n}(A(x^{(0)}-x),A)\\&={\mbox{span}}\{A(x^{(0)}-x),A^{2}(x^{(0)}-x),\ldots ,A^{n}(x^{(0)}-x)\}\end{aligned}}$

顯式寫出y

然後我們可以顯式地寫出$y\!\,$如下

${\begin{aligned}y&\in x_{0}+{\mathcal {K}}_{n}(r^{(0)},A)\\&\in x_{0}+{\mathcal {K}}_{n}(A(x^{(0)}-x),A)\\&=x_{0}+\alpha _{1}A(x^{(0)}-x)+\alpha _{2}A^{2}(x^{(0)}-x)+\ldots +\alpha _{n}A^{n}(x^{(0)}-x)\\&{\mbox{for arbitrary real numbers }}\alpha _{i}\quad i=1,2,\ldots ,n\end{aligned}}$

代入並應用不等式

我們將$y\!\,$代入假設不等式，並應用矩陣範數的範數不等式得到所需結果。

${\begin{aligned}\|x^{(n)}-x\|_{A}&\leq \|y-x\|_{A}\\&=\|(x_{0}-x)+\alpha _{1}A(x^{(0)}-x)+\alpha _{2}A^{2}(x^{(0)}-x)+\ldots +\alpha _{n}A^{n}(x^{(0)}-x)\|_{A}\\&=\|\alpha _{n}A^{n}(x^{(0)}-x)+\alpha _{n-1}A^{n-1}(x^{(0)}-x)+\ldots +\alpha _{2}A^{2}(x^{(0)}-x)+\alpha _{1}A(x^{(0)}-x)+(x_{0}-x)\|_{A}\\&=\|P(A)(x^{(0)}-x)\|_{A}\\&\leq \|P(A)\|_{A}\|x^{(0)}-x\|_{A}\end{aligned}}$

問題 3b

令 $T_{n}(z)\!\,$ 表示 $n^{th}\!\,$ 切比雪夫多項式。令 $\lambda _{min}\!\,$ 和 $\lambda _{max}\!\,$ 分別表示 $A\!\,$ 的最小和最大特徵值。將部分 (a) 的結果應用於 $p_{n}(z)={\frac {T_{n}({\frac {\lambda _{max}+\lambda _{min}-2z}{\lambda _{max}-\lambda _{min}}})}{T_{n}({\frac {\lambda _{max}+\lambda _{min}}{\lambda _{max}-\lambda _{min}}})}}$ 來證明 $\|x^{(n)}-x\|_{A}\leq {\frac {1}{T_{n}({\frac {\lambda _{max}+\lambda _{min}}{\lambda _{max}-\lambda _{min}}})}}\|x^{(0)}-x\|_{A}$. 無需證明即可使用以下事實 $\|p_{n}(A)\|_{A}=\max\{|p_{n}(z)|:z\in Sp\{A\}\}\!\,$, 其中 $Sp(A)\!\,$ 表示 $A\!\,$ 的特徵值集，以及對於每個 $n\in \mathbb {N} \!\,$ 多項式 $T_{n}(z)\!\,$ 的次數為 $n\!\,$，當 $z>1\!\,$ 時為正數，並滿足 $T_{n}(\cos(\theta ))=\cos(n\theta )\quad \quad {\mbox{for all}}\;\theta \in \mathbb {R} \!\,$.

解法 3b

概述

我們要證明

$\|p_{n}(A)\|_{A}={\frac {1}{T_{n}({\frac {\lambda _{\max }+\lambda _{\min }}{\lambda _{\max }-\lambda _{\min }}})}}\!\,$

最大化 p_n(z) 的分子

根據假設，

$\|p_{n}(A)\|_{A}=\max\{|p_{n}(z)|:z\in Sp\{A\}\}\!\,$

由於只有 $p_{n}(z)\!\,$ 的分子取決於 $z\!\,$，因此我們只需要最大化分子，就可以最大化 $|p_{n}(z)|\!\,$。也就是說，求解

$z:\max _{z\in [\lambda _{\min },\lambda _{\max }]}\left|T_{n}\left({\frac {\lambda _{\max }+\lambda _{\min }-2z}{\lambda _{\max }-\lambda _{\min }}}\right)\right|\!\,$

重寫 T_n

令 $\cos(\theta )=x\!\,$. 那麼

$\theta =\arccos(x)\!\,$

因此，

${\begin{aligned}T_{n}(\cos \theta )&=T_{n}(x)\\&=\cos(n\theta )\\&=\cos(n\arccos(x))\end{aligned}}$

所以

$T_{n}(x)=\cos(n\arccos(x))\!\,$

T_n 的最大值為 1

將 $T_{n}\!\,$ 的自變量表示為 $x(z)\!\,$，因為自變數依賴於 $z\!\,$。因此，

$x(z)={\frac {\lambda _{\max }+\lambda _{\min }-2z}{\lambda _{\max }-\lambda _{\min }}}\!\,$,

那麼，

$x(\lambda _{\min })={\frac {\lambda _{\max }-\lambda _{\min }}{\lambda _{\max }-\lambda _{\min }}}=1\!\,$

$x(\lambda _{\max })={\frac {\lambda _{\min }-\lambda _{\max }}{\lambda _{\max }-\lambda _{\min }}}=-1\!\,$

因此 $x(z)\in [-1,1]\!\,$.

現在，由於 $\;\arccos(x)\;$ 在 $x\in [-1,1]\!\,$ 時是實數，

$-1\leq \underbrace {\cos(n\overbrace {\arccos(x)} ^{\in \mathbb {R} })} _{T_{n}(x)}\leq 1\!\,$

因此，

$\max _{x\in [-1,1]}T_{n}(x)=\max _{x\in [-1,1]}|\cos(n\arccos(x))|=1\!\,$

證明 T_n(1)=1

令 $z=\lambda _{\min }\!\,$， 那麼

$\left|T_{n}\left({\frac {\lambda _{\max }+\lambda _{\min }-2(\lambda _{\min })}{\lambda _{\max }-\lambda _{\min }}}\right)\right|=|T_{n}(1)|\!\,$

使用我們的公式，我們有：

${\begin{aligned}|T_{n}(1)|&=|\cos(n\cdot \arccos(1))|\\&=|\cos(n\cdot 2\pi k)|\quad k\in \mathbf {Z} \\&=1\end{aligned}}$

換句話說，如果 $z=\lambda _{\min }\!\,$，$T_{n}\!\,$ 取得其最大值 $1\!\,$.