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

問題 1

令 $f\!\,$ 在 $[0,1]\!\,$ 上連續。一個次數不超過 $n\!\,$ 的多項式 $p\!\,$ 稱為 $f\!\,$ 的最佳（或切比雪夫）逼近，如果 $p\!\,$ 使表示式最小化 $E(p)=\max _{x\in [0,1]}|f(x)-p(x)|\!\,$

問題 1a

證明 $p\!\,$ 是最佳逼近的一個充分條件是存在點 $x_{0}<x_{1}<\cdots <x_{n+1}\;{\mbox{in}}\;[0,1]\!\,$ 使得 $f(x_{i})-p(x_{i})=-[f(x_{i+1})-p(x_{i+1})]=\pm E(p),\qquad i=0,1,2,\dots ,n\!\,$.

解答 1a

假設存在 $q\in \Pi ^{n}\!\,$ 使得

$E(q)<E(p)\!\,$

那麼對於 $i=0,1,\ldots ,n\!\,$

$|f(x_{i})-q(x_{i})|\leq |f(x_{i})-p(x_{i})|\!\,$

令 $e(q)=f(x)-q(x)\!\,$ 以及 $e(p)=f(x)-p(x)\!\,$.

那麼 $e\equiv e(q(x))-e(p(x))\!\,$ 取決於 $e(p)\!\,$ 的符號，因為

$|e(p(x_{i}))|\geq |e(q(x_{i}))|\!\,$

由於 $e(p)\!\,$ 在 $n+1\!\,$ 次（假設）改變符號，$e\!\,$ 有 $n+1\!\,$ 個零點。

然而 $e=p-q\!\,$，因此最多隻有 $n\!\,$ 個零點。 因此 $e\equiv 0\!\,$ 且 $p=q\!\,$

問題 1b

計算對 $x^{2}\;{\mbox{in}}\;[0,1]\!\,$ 的最佳線性逼近。 [提示：在拋物線上畫一條線將讓你推測出兩個振盪點的位置。 使用 (a) 中的條件來確定第三個點和 $p\!\,$ 的係數。]

解 1b

首先，我們需要在 [0,1] 中找到 $T_{2}(x)\!\,$ 的根，它們由下式給出

$x_{k}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {2k-1}{4}}\pi )\!\,$

因此，我們的插值點為

$x_{1}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {\pi }{4}})\!\,$

$x_{2}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {3\pi }{4}})={\frac {1}{2}}-{\frac {1}{2}}\cos({\frac {\pi }{4}})\!\,$

我們的線性插值函式經過點 $(x_{1},x_{1}^{2})\!\,$ 和 $(x_{2},x_{2}^{2})\!\,$，使用點斜式得到方程

$y-x_{1}^{2}={\frac {x_{2}^{2}-x_{1}^{2}}{x_{2}-x_{1}}}(x-x_{1})\!\,$

或者

$y=x-{\frac {1}{8}}\!\,$

問題 2

我們將關注最小化以下最小二乘問題的： $\rho ^{2}(x)=\|b-Ax\|^{2}\!\,$. 這裡 $A\!\,$ 是一個 $m\times n\!\,$ 矩陣，秩為 $n\!\,$ （這意味著 $m\geq n\!\,$），$\|\cdot \|\!\,$ 是歐幾里得向量範數。令 $A={\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}\!\,$ 是 $A\!\,$ 的 QR 分解。這裡 $Q_{1},Q_{2}\;{\mbox{and}}\;R\!\,$ 分別是 $m\times n,m\times (m-n),\;{\mbox{and}}\;n\times n\!\,$。

問題 2a

證明最小二乘問題的解滿足 QR 方程$Rx=Q_{1}^{T}b\!\,$，並且解是唯一的。進一步證明$\rho (x)=\|Q_{2}^{T}b\|\!\,$.

解 2a

這兩個問題是等價的

首先注意到

$A={\begin{pmatrix}Q_{1}Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}=Q_{1}R$

那麼我們可以寫成

${\begin{aligned}\|b-Ax\|&=\|b-Q_{1}Rx\|\\&=\|Q_{1}^{T}b-Q_{1}^{T}Q_{1}Rx\|\\&=\|Q_{1}^{T}b-Rx\|\end{aligned}}$

注意，乘以正交矩陣不會影響範數。

那麼求解$\min _{x}\|b-Ax\|^{2}\!\,$等價於求解$\min _{x}\|Q_{1}^{T}b-Rx\|^{2}\!\,$，這等價於求解$Rx=Q_{1}^{T}b\!\,$。注意，解存在且唯一，因為$R\!\,$是 n×n 且非奇異的。

證明$\rho (x)=\|Q_{2}^{T}b\|$

類似地

${\begin{aligned}\|b-Ax\|&=\|b-Q_{1}Rx\|\\&=\|Q_{2}^{T}b-\underbrace {Q_{2}^{T}Q_{1}} _{0}Rx\|\\&=\|Q_{2}^{T}b\|\end{aligned}}$

那麼

$\rho ^{2}(x)=\|b-Ax\|^{2}=\|Q_{2}^{T}b\|^{2}$，或者簡化為 $\rho (x)=\|Q_{2}^{T}b\|$，如預期那樣。

問題 2b

利用 QR 方程證明最小二乘解滿足正規方程 $(A^{T}A)x=A^{T}b\!\,$。

解 2b

${\begin{aligned}A^{T}Ax&=(Q_{1}R)^{T}Q_{1}Rx\\&=R^{T}Q_{1}^{T}Q_{1}Rx\\&=R^{T}Rx\\\\A^{T}b&=(Q_{1}R)^{T}b\\&=R^{T}\underbrace {Q_{1}^{T}b} _{Rx}\\&=R^{T}Rx\end{aligned}}\!\,$

問題 3

$\!\,$ 令 $\!\,A$ 為實對稱矩陣，令 $u_{0}\neq 0\!\,$ 為給定值。對於 $k=1,2,\ldots \!\,$，定義 $u_{k+1}\!\,$ 為向量 $Au_{k},u_{k},\ldots ,u_{0}\!\,$ 的線性組合，其中 $Au_{k}\!\,$ 的係數為 1 且與向量 $u_{k},\ldots ,u_{0}\!\,$ 正交；即 $u_{k+1}=Au_{k}-\alpha _{k}u_{k}-\beta _{k}u_{k-1}-\gamma _{k}u_{k-2}-\cdots \!\,$

問題 3a

求 $\alpha _{k}\!\,$ 和 $\beta _{k}\!\,$ 的公式。

解 3a

使用 Gram-Schmidt 正交化，我們有

${\begin{aligned}\alpha _{k}&={\frac {(Au_{k},u_{k})}{\|u_{k}\|^{2}}}\\\beta _{k}&={\frac {(Au_{k},u_{k-1})}{\|u_{k-1}\|^{2}}}\end{aligned}}$

問題 3b

證明 $\gamma _{k}=\delta _{k}=\ldots =0\!\,$ 在哪裡你使用了 $A\!\,$ 的對稱性？

解 3b

因為

$\gamma _{k}={\frac {(Au_{k},u_{k-2})}{\|u_{k-2}\|^{2}}}$

, 如果 $\gamma _{k}=0\!\,$，那麼

$(Au_{k},u_{k-2})=0\!\,$

因為 $A\!\,$ 是對稱的，

$(Au_{k},u_{k-2})=(u_{k},A^{T}u_{k-2})=(u_{k},Au_{k-2})\!\,$

根據假設，$(u_{i},u_{j})={\begin{cases}1&{\mbox{if }}i=j\\0&{\mbox{if }}i\neq j\end{cases}}$

同樣根據假設，

${\begin{aligned}Au_{k}&=u_{k+1}+\alpha _{k}u_{k}+\beta _{k}u_{k-1}+\gamma _{k}u_{k-2}+\ldots \\Au_{k-2}&=u_{k-1}+\alpha _{k-2}u_{k-2}+\beta _{k-2}u_{k-3}+\gamma _{k-2}u_{k-4}+\ldots \end{aligned}}$

使用上述結果，我們有，

${\begin{aligned}(Au_{k},u_{k-2})&=(u_{k},Au_{k-2})\\&=(u_{k},u_{k-1}+\alpha _{k-2}u_{k-2}+\beta _{k-2}u_{k-3}+\gamma _{k-2}u_{k-4}+\ldots )\\&=(u_{k},u_{k-1})+\alpha _{k-2}(u_{k},u_{k-2})+\beta _{k-2}(u_{k},u_{k-3})+\gamma _{k-2}(u_{k},u_{k-4})+\ldots )\\&=0\end{aligned}}$

問題 3c

對於哪些非零向量 $u_{0}\!\,$，$u_{1}=0\!\,$ 成立？

解 3c

對於 $k=0\!\,$，

$u_{1}=Au_{0}-\alpha _{0}u_{0}\!\,$

如果 $u_{1}=0\!\,$，那麼

$Au_{0}=\alpha _{0}u_{0}\!\,$

由於 $\alpha _{0}\!\,$ 是一個標量，$u_{0}\!\,$ 是 $A\!\,$ 的特徵向量。