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

問題 1

設 $x_{1},x_{2},\ldots ,x_{n}$ 是不同的實數，並考慮矩陣

V=\left({\begin{array}{ccccc}1&x_{1}&x_{1}^{2}&\cdots &x_{1}^{n-1}\\1&x_{2}&x_{2}^{2}&\cdots &x_{2}^{n-1}\\\vdots &\vdots &\vdots &\ddots &\vdots \\1&x_{n}&x_{n}^{2}&\cdots &x_{n}^{n-1}\\\end{array}}\right)

證明 $V^{-1}$ 可以表示為

V^{-1}=\left({\begin{array}{c}\\\\\alpha ^{(1)},\alpha ^{(2)},\alpha ^{(3)},\cdots ,\alpha ^{(n)}\\\\\\\end{array}}\right)

其中列向量 $\alpha ^{(j)}=(\alpha _{1}^{(j)},\alpha _{2}^{(j)},\cdots ,\alpha _{n}^{(j)})^{T}$ 生成一個多項式

p_{j}(x)=\sum _{i=1}^{n}\alpha _{i}^{(j)}x^{i-1}

滿足

p_{j}(x)={\frac {\prod _{i=1,i\neq j}^{n}(x-x_{i})}{\prod _{i=1,i\neq j}^{n}(x_{j}-x_{i})}}

您可以引用您瞭解的任何關於多項式插值的知識來證明 $V$ 是非奇異的。

解答 1

我們想要證明

\,\!VV^{-1}=I

或者等價地， $\,\!i$ th， $\,\!j$ th $\,\!VV^{-1}$ 的項是 $\,\!1$ 當 $\,\!i=j$ ，並且是 $\,\!0$ 當 $\,\!i\neq j$ ，也就是說

\{VV^{-1}\}_{ij}=\delta _{ij}=\left\{{\begin{array}{cc}1&{\mbox{ if }}i=j\\0&{\mbox{ if }}i\neq j\end{array}}\right.

首先注意到

\,\!\{VV^{-1}\}_{ij}={\begin{bmatrix}1+x_{i}^{1}+x_{i}^{2}+\cdots +x_{i}^{n-1}\end{bmatrix}}{\begin{bmatrix}\alpha _{1}^{(j)}\\\alpha _{2}^{(j)}\\\vdots \\\alpha _{n}^{(j)}\end{bmatrix}}=\sum _{k=1}^{n}\alpha _{k}^{(j)}x_{i}^{k-1}

同樣地，注意到

\,\!p_{j}(x_{i})=\sum _{k=1}^{n}\alpha _{k}^{(j)}x_{i}^{k-1}=\delta _{ij}

因此，

\,\!\{VV^{-1}\}_{ij}=p_{j}(x_{i})=\delta _{ij}

問題 2

令 $A\,\!$ 為一個實數矩陣，階數為 $n\,\!$ ，特徵值為 $\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}\,\!$ ，以及 $n\,\!$ 個線性無關的特徵向量 $v_{1},v_{2},\ldots ,v_{n}\,\!$ .

假設您想找到一個特徵向量 $v_{j}\,\!$ ，它對應於特徵值 $\lambda _{j}\,\!$ ，並且您已知 $\sigma \,\!$ 使得

|\lambda _{j}-\sigma |<|\lambda _{i}-\sigma |{\mbox{ for all }}i\neq j\,\!

指定一個數值演算法，用於找到 $v_{j}\,\!$ ，並給出該演算法的收斂證明，證明它在適當的情況下是收斂的。

解決方案 2

移位逆冪法

令

{\begin{aligned}{\tilde {A}}&=(A-\sigma I)^{-1}\\\end{aligned}}

然後，

{\tilde {\lambda _{i}}}={\frac {1}{|\lambda _{i}-\sigma |}}

這表明

{\tilde {\lambda _{j}}}>{\tilde {\lambda }}_{i}{\mbox{ for all }}i\neq j

因為移動特徵值和矩陣求逆不會影響特徵向量，

{\tilde {A}}v_{i}={\tilde {\lambda _{i}}}v_{i}\quad \quad i=1,2,\ldots ,n

假設對於所有 $\!\,i$ ， $\|v_{i}\|=1$ 。生成 $w_{0},w_{1},w_{2},\ldots$ 以找到 $\,\!v_{j}$ 。從任意 $\,\!w_{0}$ 開始，滿足 $\,\!\|w_{0}\|=1$ 。

For  $\,\!k=0,1,2,\ldots$ 
   $\,\!{\hat {w}}_{k+1}={\tilde {A}}w_{k}$ 
   $\,\!w_{k+1}={\frac {{\hat {w}}_{k+1}}{\|{\hat {w}}_{k+1}\|}}$ 
   $\lambda _{j}^{(k+1)}={\frac {({\hat {w}}_{k+1},w_{k})}{(w_{k},w_{k})}}={\frac {({\tilde {A}}w_{k},w_{k})}{(w_{k},w_{k})}}$  (Rayleigh quotient)
End

冪法收斂性

如果對於所有 $\!\,i\neq 1$ ， $\,\!|\lambda _{1}|>|\lambda _{i}|$ ，那麼 $\,\!A^{k}w_{0}$ 將被 $\,\!v_{1}$ 支配。

因為 $v_{1},v_{2},\ldots ,v_{n}$ 線性無關，它們構成 $R^{n}\,\!$ 的基底。因此，

w_{0}=\alpha _{1}v_{1}+\alpha _{2}v_{2}+\ldots +\alpha _{n}v_{n}\,\!

根據特徵向量的定義，

{\begin{aligned}Aw_{0}&=\alpha _{1}\lambda _{1}v_{1}+\alpha _{2}\lambda _{2}v_{2}+\ldots +\alpha _{n}\lambda _{n}v_{n}\\A^{2}w_{0}&=\alpha _{1}\lambda _{1}^{2}v_{1}+\alpha _{2}\lambda _{2}^{2}v_{2}+\ldots +\alpha _{n}\lambda _{n}^{2}v_{n}\\&\vdots \\A^{k}w_{0}&=\alpha _{1}\lambda _{1}^{k}v_{1}+\alpha _{2}\lambda _{k}^{2}v_{2}+\ldots +\alpha _{n}\lambda _{n}^{k}v_{n}\\\end{aligned}}

為了找到 $w_{k}\,\!$ 的一般形式，即第 k 步的近似特徵向量，可以觀察演算法中的幾個步驟。

{\begin{aligned}{\hat {w}}_{1}&=Aw_{0}\\w_{1}&={\frac {{\hat {w}}_{1}}{\|{\hat {w}}_{1}\|}}={\frac {Aw_{0}}{\|Aw_{0}\|}}\\{\hat {w}}_{2}&=Aw_{1}={\frac {A^{2}w_{0}}{\|Aw_{0}\|}}\\w_{2}&={\frac {{\hat {w}}_{2}}{\|{\hat {w}}_{2}\|}}={\frac {\frac {A^{2}w_{0}}{\|Aw_{0}\|}}{\frac {\|A^{2}w_{0}\|}{\|Aw_{0}\|}}}={\frac {A^{2}w_{0}}{\|A^{2}w_{0}\|}}\\{\hat {w}}_{3}&={\frac {A^{3}w_{0}}{\|A^{2}w_{0}\|}}\\w_{3}&={\frac {\frac {A^{3}w_{0}}{\|A^{2}w_{0}\|}}{\frac {\|A^{3}w_{0}\|}{\|A^{2}w_{0}\|}}}={\frac {A^{3}w_{0}}{\|A^{3}w_{0}\|}}\\\end{aligned}}

根據歸納法,

w_{k}={\frac {A^{k}w_{0}}{\|A^{k}w_{0}\|}}

因此，

{\begin{aligned}w_{k}&={\frac {A^{k}w_{0}}{\|A^{k}w_{0}\|}}\\&={\frac {\alpha _{1}\lambda _{1}^{k}v_{1}+\alpha _{2}\lambda _{2}^{k}v_{2}+\ldots +\alpha _{n}\lambda _{n}^{k}v_{n}}{\|A^{k}w_{0}\|}}\\&={\frac {\lambda _{1}^{k}(\alpha _{1}v_{1}+\alpha _{2}({\frac {\lambda _{2}}{\lambda _{1}}})^{k}v_{2}+\ldots +\alpha _{n}({\frac {\lambda _{n}}{\lambda _{1}}})^{k}v_{n})}{\|A^{k}w_{0}\|}}\end{aligned}}

比較加權 $w_{k}\!\,$ 和 $v_{1}\!\,$ ,

{\begin{aligned}\left\|{\frac {\|A^{k}w_{0}\|}{\lambda _{1}^{k}}}w_{k}-\alpha _{1}v_{1}\right\|&=\left\|\alpha _{2}\left({\frac {\lambda _{2}}{\lambda _{1}}}\right)^{k}v_{2}+\ldots +\alpha _{n}\left({\frac {\lambda _{n}}{\lambda _{1}}}\right)^{k}v_{n}\right\|\\&\leq \alpha _{2}\left|{\frac {\lambda _{2}}{\lambda _{1}}}\right|^{k}+\ldots +\alpha _{n}\left|{\frac {\lambda _{n}}{\lambda _{1}}}\right|^{k}\end{aligned}}

因為假設 $\|v_{i}\|=1$ 。

上述表示式在 $\,\!0$ 趨於 $k\rightarrow \infty$ ，因為對於所有 $\,\!|\lambda _{1}|>|\lambda _{i}|$ ，都有 $\!\,i\neq 1$ 。因此，隨著 $\!\,k$ 的增長， $\!\,w_{k}$ 與 $\!\,v_{1}$ 平行。因為 $\|w_{k}\|=1$ ，因此必然有 $w_{k}\rightarrow \pm v_{1}$ 。

問題 3

假設 A 是一個上三角非奇異矩陣。證明當使用雅克比迭代和高斯-賽德爾迭代求解 $A\mathbf {x} =\mathbf {b}$ 時，它們會在有限步內收斂。

解 3

迭代推導

令 $A=D+L+U\!\,$ ，其中 $D\!\,$ 是一個對角矩陣， $L\!,$ 是一個下三角矩陣，其對角線為零，而 $U\!\,$ 也是一個上三角矩陣，其對角線也為零。

雅克比迭代可以透過將 $L+U\!\,$ 代入 $Ax=b\!\,$ 中，並求解 $x\!\,$ ，即

${\begin{aligned}Ax&=b\\(D+L+U)x&=b\\Dx+(L+U)x&=b\\Dx&=b-(L+U)x\\x&=D^{-1}(b-(L+U)x)\end{aligned}}$

假設條件下，由於 $L=0\!\,$ ，迭代公式為

x^{(i+1)}=D^{-1}(b-Ux^{(i)})\!\,

類似地，將 $Ax=b\!\,$ 代入，將 $D+L\!\,$ 分組，並解出 $x\!\,$ ，即

${\begin{aligned}Ax&=b\\(D+L+U)x&=b\\(D+L)x+Ux&=b\\(D+L)x&=b-Ux\\x&=(D+L)^{-1}(b-Ux)\end{aligned}}$

由於假設條件下 $L=0\!\,$ ，雅可比迭代和高斯-賽德爾迭代的公式相同。

x^{(i+1)}=D^{-1}(b-Ux^{(i)})\!\,

有限步收斂

雅可比迭代和高斯-賽德爾迭代是將矩陣 $A\in \mathbb {R} ^{n\times n}\!\,$ 分解成 $D\!\,$ 、 $U\!\,$ 和 $L\!\,$ ：分別是對角矩陣、上三角矩陣（對角線以上部分）和下三角矩陣（對角線以下部分）。它們的迭代過程如下：

x^{(i+1)}=(D+L)^{-1}(b-Ux^{(i)})\!\,

（高斯-賽德爾）

x^{(i+1)}=D^{-1}(b-(U+L)x^{(i)})\!\,

(雅可比方法)

在本例中， $A\!\,$ 為上三角矩陣，因此 $L\!\,$ 為零矩陣。因此，高斯-賽德爾方法和雅可比方法具有以下相同的形式

x^{(i+1)}=D^{-1}(b-Ux^{(i)})\!\,

此外， $x\!\,$ 可以寫成

x=D^{-1}(b-Ux)\!\,

從 $x^{(i+1)}\!\,$ 中減去 $x\!\,$ ，我們得到

${\begin{aligned}e^{(i+1)}&=x^{(i+1)}-x\\&=D^{-1}(b-Ux^{(i)})-D^{-1}(b-Ux)\\&=D^{-1}U(-x^{(i)}+x)\\&=D^{-1}Ue^{(i)}\\&=D^{-1}U(D^{-1}Ue^{(i-1)})=(D^{-1}U)^{2}e^{(i-1)}\\&\vdots \\&=(D^{-1}U)^{i+1}e^{(0)}\end{aligned}}$

在我們這個問題中， $D^{-1}\!\,$ 是對角矩陣， $U\!\,$ 是上三角矩陣，對角線上為零。注意，積 $D^{-1}U\!\,$ 也是上三角矩陣，對角線上為零。

令 $R=D^{-1}U\!\,$ ， $R\in \mathbb {R} ^{n\times n}\!\,$

R={\begin{pmatrix}0&*&*&\cdots &*\\0&0&*&\cdots &*\\\vdots &\vdots &\ddots &\ddots &\vdots \\0&\cdots &\cdots &0&*\\0&\cdots &\cdots &0&0\end{pmatrix}}

此外，令 ${\tilde {R}}\in \mathbb {R} ^{n\times n}\!\,$ 為相關矩陣

{\begin{aligned}{\tilde {R}}&=\left({\begin{array}{ccc|cccc}0&\cdots &0&*&*&\cdots &*\\0&\cdots &0&0&*&\cdots &*\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&\cdots &0&0&\cdots &0&*\\\hline 0&\cdots &0&0&\cdots &0&0\\\vdots &\vdots &\vdots &\vdots &\cdots &\vdots &\vdots \\0&\cdots &0&0&\cdots &0&0\\\end{array}}\right)\\&=\left({\begin{array}{c|c}\mathbf {a} &T\\\hline \mathbf {0} &\mathbf {a} ^{T}\\\end{array}}\right)\end{aligned}}

其中 $\mathbf {a} \!\,$ 是 $k\times (n-k)\!\,$ ， $T\!\,$ 是 $k\times k\!\,$ ，並且 $\mathbf {0} \!\,$ 是 $(n-k)\times (n-k)\!\,$ .

最後，乘積 $R{\tilde {R}}\!\,$ （稱為 (1)）是

{\begin{aligned}R{\tilde {R}}&={\begin{pmatrix}0&*&*&\cdots &*\\0&0&*&\cdots &*\\\vdots &\vdots &\ddots &\ddots &\vdots \\0&\cdots &\cdots &0&*\\0&\cdots &\cdots &0&0\end{pmatrix}}\left({\begin{array}{ccc|cccc}0&\cdots &0&*&*&\cdots &*\\0&\cdots &0&0&*&\cdots &*\\\vdots &\vdots &\vdots &\vdots &\ddots &\ddots &\vdots \\0&\cdots &0&0&\cdots &0&*\\\hline 0&\cdots &0&0&\cdots &0&0\\\vdots &\vdots &\vdots &\vdots &\cdots &\vdots &\vdots \\0&\cdots &0&0&\cdots &0&0\\\end{array}}\right)\\&=\left({\begin{array}{ccc|ccccc}0&\cdots &0&0&*&\cdots &\cdots &*\\0&\cdots &0&0&0&*&\cdots &*\\\vdots &\vdots &\vdots &\vdots &\cdots &\cdots &\ddots &\vdots \\0&\cdots &0&0&\cdots &\cdots &0&*\\\hline 0&\cdots &0&0&\cdots &\cdots &0&0\\\vdots &\vdots &\vdots &\vdots &\cdots &\cdots &\vdots &\vdots \\0&\cdots &0&0&\cdots &\cdots &0&0\\\end{array}}\right)\\&=\left({\begin{array}{c|c}\mathbf {a} &{\tilde {T}}\\\hline \mathbf {0} &\mathbf {a} ^{T}\\\end{array}}\right)\end{aligned}}

這裡 ${\tilde {T}}\!\,$ 的結構與 $T\!\,$ 幾乎完全相同，只是它的對角元素為零。

此時，在 $n\!\,$ 步（起始矩陣的大小）時，收斂應該是顯而易見的，因為 $R\!\,$ 僅僅是 ${\tilde {R}}\!\,$ ，其中 $k=0\!\,$ ，每次 $R\!\,$ 被 ${\tilde {R}}\!\,$ 乘以，第 k 個上對角線被清零（其中 k=0 表示對角線本身）。經過 $n-1\!\,$ 次應用 $R\!\,$ 後，結果將是大小為 $n\!\,$ 的零矩陣。

簡而言之， $R^{n}\!\,$ 是大小為 $n\!\,$ 的零矩陣。

因此， $e^{(n)}=(D^{-1}U)^{n}e^{(0)}\equiv 0\!\,$ ，也就是說，當 $A\in \mathbb {R} ^{n\times n}\!\,$ 為上三角矩陣時，用於求解 $A\mathbf {x} =b\!\,$ 的雅可比和高斯-賽德爾方法在 $n\!\,$ 步內收斂。

(1) 的例子

$n=3\!\,$

R={\begin{pmatrix}0&*&*\\0&0&*\\0&0&0\\\end{pmatrix}}

R^{2}={\begin{pmatrix}0&*&*\\0&0&*\\0&0&0\\\end{pmatrix}}{\begin{pmatrix}0&*&*\\0&0&*\\0&0&0\\\end{pmatrix}}={\begin{pmatrix}0&0&*\\0&0&0\\0&0&0\\\end{pmatrix}}

n=4\!\,