數值方法資格考試問題及解答 (馬里蘭大學) / 2004 年 8 月

問題 1

為了計算 ${\sqrt {2}}\!\,$ ，我們考慮以下歐多克斯迭代：從 $x_{0}=y_{0}=1\!\,$ 開始，我們設定 $x_{n+1}=x_{n}+y_{n}\!\,$ ，然後是 $y_{n+1}=x_{n+1}+x_{n}\!\,$ 。然後 $y_{n}/x_{n}\rightarrow {\sqrt {2}}\!\,$

問題 1a

用冪法解釋歐多克斯方法。

解答 1a

迭代可以用矩陣形式表示如下

${\begin{aligned}x_{n+1}&=x_{n}+y_{n}\\y_{n+1}&=x_{n+1}+x_{n}=2x_{n}+y_{n}\end{aligned}}\!\,$

它可以寫成

$\underbrace {\begin{bmatrix}1&1\\2&1\end{bmatrix}} _{A}{\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}={\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}\!\,$

因此，迭代只是冪法，因為每一步都由矩陣 $A\!\,$ 的乘法表示。

冪法收斂於最大特徵值的特徵向量。

矩陣 $A\!\,$ 的特徵值計算為 $1\pm {\sqrt {2}}\!\,$ 。因此，最大特徵值為 $1+{\sqrt {2}}\!\,$

對應的特徵向量是

${\begin{bmatrix}{\sqrt {2}}\\2\end{bmatrix}}\!\,$

那麼 $y_{n}/x_{n}\rightarrow {\sqrt {2}}\!\,$ ，如預期的那樣。

問題 1b

為了使誤差 $|y_{n}/x_{n}-{\sqrt {2}}|\leq 10^{-6}\!\,$ ，需要多少次迭代？

解決方案 1b

由於收斂是線性的，因此需要 7 步才能達到誤差界限。

問題 2

令 $\{p_{n}(x)\}\!\,$ 是關於 $[a,b]\!\,$ 的一組正權重函式 $w(x)\!\,$ （ $p_{n}\!\,$ 的度數為 $n\!\,$ ）的正交單項式序列。證明 $p_{n}\!\,$ 滿足以下形式的三項遞推公式：

$p_{n}(x)=(x-a_{n})p_{n-1}(x)-b_{n}p_{n-2}(x)\!\,$

給出係數 $a_{n}\!\,$ 和 $b_{n}\!\,$ 的表示式。

解決方案 2a

首先注意到 $p_{n}-xp_{n-1}\in \Pi ^{n-1}\!\,$ ，因此我們可以將其表示為度數為 $n-1\!\,$ 或更低的單項式線性組合，即

$p_{n}-xp_{n-1}=-a_{n}p_{n-1}-b_{n}p_{n-2}+\sum _{i=0}^{n-3}\alpha _{i}p_{i}\qquad (*)\!\,$

將 $(*)\!\,$ 兩邊的內積與 $p_{n-1}\!\,$ 進行計算，根據多項式的正交性，可以得到

$-\langle xp_{n-1},p_{n-1}\rangle =-a_{n}\langle p_{n-1},p_{n-1}\rangle \!\,$

然後，重新排列項可得

$a_{n}={\frac {\langle xp_{n-1},p_{n-1}\rangle }{\langle p_{n-1},p_{n-1}\rangle }}\!\,$

類似地，將 $(*)\!\,$ 兩邊的內積與 $p_{n-2}\!\,$ 進行計算，根據多項式的正交性，可以得到

$b_{n}={\frac {\langle xp_{n-1},p_{n-2}\rangle }{\langle p_{n-2},p_{n-2}\rangle }}\!\,$

注意

${\begin{aligned}\langle xp_{n-1},p_{n-2}\rangle &=\langle p_{n-1},xp_{n-2}\rangle \\&=\langle p_{n-1},p_{n-1}+\sum _{i=0}^{n-2}\alpha _{i}p_{i}\rangle \\&=\langle p_{n-1},p_{n-1}\rangle \end{aligned}}\!\,$