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

問題1

給定 $f\in C[a,b]\!\,$ ，令 $p_{n}^{*}\!\,$ 表示對 $f\!\,$ 在度數為 $\leq n\!\,$ 的多項式中的最佳一致逼近，即

\max _{x\in [a,b]}|f(x)-p_{n}(x)|\!\,

透過選擇 $p_{n}=p_{n}^{*}\!\,$ 最小化。令 $e(x)=f(x)-p_{n}^{*}(x)\!\,$ 。證明至少存在兩個點 $x_{1},x_{2}\in [a,b]\!\,$ ，使得

|e(x_{1})|=|e(x_{2})|=\max _{x\in [a,b]}|f(x)-p_{n}^{*}(x)|\!\,

並且 $e(x_{1})=-e(x_{2})\!\,$

解答1

由於 $f(x)\!\,$ 和 $p_{n}^{*}(x)\!\,$ 都是連續函式，因此函式

e(x)=f(x)-p_{n}^{*}(x)\!\,

也是連續函式，因此 $e(x)\!\,$ 在區間 $[a,b]\!\,$ 上存在最大值和最小值。

設 $M=\max _{x\in [a,b]}e(x)\!\,$ 和 $m=\min _{x\in [a,b]}e(x)\!\,$

如果 $M\neq -m\!\,$ ，則存在一個多項式 $q(x)=p_{n}^{*}(x)+{\frac {M+m}{2}}\!\,$ （假設的最佳逼近 $p_{n}^{*}(x))\!\,$ 的垂直平移），它是對 $f(x)\!\,$ 更好的逼近。

${\begin{aligned}f(x)-q(x)&=f(x)-p_{n}^{*}(x)-{\frac {M+m}{2}}\\&\leq M-{\frac {M+m}{2}}\\&={\frac {M-m}{2}}\\\\\\f(x)-q(x)&\geq m-{\frac {M+m}{2}}\\&={\frac {m-M}{2}}\end{aligned}}\!\,$

因此，

$\|f(x)-q(x)\|\leq {\frac {M-m}{2}}\leq \|f-p_{n}^{*}\|=M\!\,$

當且僅當 $m=-M\!\,$ 時，等式成立。

問題 2a

求節點 $x_{1}\!\,$ 和權重 $w_{1}\!\,$ ，使得積分規則

$I=\int _{0}^{1}x^{-{\frac {1}{2}}}f(x)dx\approx w_{1}f(x_{1})\!\,$

對線性函式精確。（不需要正交多項式的知識。）

解 2a

令 $f(x)=1\!\,$ 。則

$\int _{0}^{1}{\frac {1}{x^{\frac {1}{2}}}}=w_{1}\cdot 1\!\,$

計算後得到

$w_{1}=2\!\,$

令 $f(x)=x\!\,$ 。則

$\int _{0}^{1}{\frac {x}{x^{\frac {1}{2}}}}=w_{1}\cdot x_{1}=2x_{1}\!\,$

計算後得到

$x_{1}={\frac {1}{3}}\!\,$

問題 2b

證明對於近似 $I\!\,$ ，不存在任何一點規則可以對二次函式精確。

解 2b

假設存在一個用於近似 $I\!\,$ 的一點規則，該規則對二次函式精確。

令 $f(x)=x^{2}\!\,$ 。

然後，

$\int _{0}^{1}{\frac {x^{2}}{x^{\frac {1}{2}}}}={\frac {2}{5}}\!\,$

但是

$w_{1}x_{1}^{2}=2({\frac {1}{3}})^{2}={\frac {2}{9}}\!\,$ ,

這是一個矛盾。

問題 2c

事實上

$I-w_{1}f(x_{1})=cf''(\xi ){\mbox{ for some }}\xi \in [0,1]\!\,$

求 $c\!\,$ 。

解答 2c

令 $f(x)=x^{2}\!\,$ 。則 $f''(x)=2\!\,$

利用在(b)部分計算的值，我們有

${\frac {2}{5}}-{\frac {2}{9}}=c\cdot 2\!\,$

這意味著

$c={\frac {4}{45}}\!\,$

問題 2d

令 $f(x)\!\,$ 和 $g(x)\!\,$ 為兩個次數小於等於 $3\!\,$ 的多項式。假設 $f\!\,$ 和 $g\!\,$ 在 $x=a\!\,$ ， $x=b\!\,$ 和 $x=(a+b)/2\!\,$ 處相等。證明

$\int _{a}^{b}f(x)dx=\int _{a}^{b}g(x)dx\!\,$

解法 2d

存在 $w_{1},w_{2},w_{3}\!\,$ 使得如果 $f(x)\!\,$ 是一個次數小於等於 $3\!\,$ 的多項式

$\int _{a}^{b}f(x)dx=w_{1}f(a)+w_{2}f(b)+w_{3}f({\frac {a+b}{2}})\!\,$

因此，

${\begin{aligned}\int _{a}^{b}f(x)dx&=w_{1}f(a)+w_{2}f(b)+w_{3}f({\frac {a+b}{2}})\\&=w_{1}g(a)+w_{2}g(b)+w_{3}g({\frac {a+b}{2}})\\&=\int _{a}^{b}g(x)dx\end{aligned}}\!\,$

問題 3

設 $A\in R^{n\times n}\!\,$ 為非奇異矩陣，且 $b\in R^{n}\!\,$ 。考慮以下用於求解 $Ax=b\!\,$ 的迭代：

$x_{k+1}=x_{k}+\alpha (b-Ax_{k})\!\,$

問題 3a

證明如果 $A\!\,$ 的所有特徵值都具有正實部，則存在某個實數 $\alpha \!\,$ 使得對於任何起始向量 $x_{0}\!\,$ ，迭代都收斂。討論在 $A\!\,$ 為對稱矩陣的情況下如何最優地選擇 $\alpha \!\,$ ，並確定收斂速度。

解答 3a

任何起始向量的收斂性

使用迭代 $\,\!x_{k+1}=x_{k}+\alpha (b-Ax_{k})$ ，我們得到

${\begin{aligned}e_{k+1}&=x_{k+1}-x^{*}\\&=x_{k}-x^{*}+\alpha (b-Ax_{k})\\&=x_{k}-x^{*}+\alpha (Ax^{*}-Ax_{k})\\&=e_{k}-\alpha Ae_{k}\\&=(I-\alpha A)e_{k}\end{aligned}}$

然後，計算範數得到

$\,\!\|e_{k+1}\|\leq \|I-\alpha A\|\|e_{k}\|$ .

特別是，考慮 $\,\!\|\cdot \|_{2}$ ，我們有

$\,\!\|e_{k+1}\|_{2}\leq \|I-\alpha A\|_{2}\|e_{k}\|_{2}$ .

現在，為了研究該方法的收斂性，我們需要分析 $\,\!\|I-\alpha A\|_{2}$ 。我們使用以下特徵

${\begin{aligned}\|I-\alpha A\|_{2}^{2}&=\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)\\&=\rho \left(I-\alpha A^{*}-\alpha A+|\alpha |^{2}AA^{*}\right)\end{aligned}}$

讓我們用 $\,\!\lambda$ 表示矩陣 $\,\!A$ 的一個特徵值。然後 $\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)<1\,\!$ 意味著

$1-2\alpha Re(\lambda )+\alpha ^{2}|\lambda |^{2}<1\!\,$

即

$-2\alpha Re(\lambda )+\alpha ^{2}|\lambda |^{2}<0\!\,$

上述方程關於 $\alpha \!\,$ 是二次的，且開口向上。因此，使用二次公式，我們可以找到方程的根為

$\alpha _{1}=0\quad \alpha _{2}=2{\frac {Re(\lambda )}{|\lambda |^{2}}}\!\,$

然後，如果矩陣 $\,\!A$ 的所有特徵值的 $\,\!Re(\lambda )$ 都大於0，我們可以找到一個 $\,\!\alpha$ ，使得 $\,\!\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)<1$ ，即該方法收斂。

如果A是對稱矩陣，則選擇alpha

另一方面，如果矩陣 $\,\!A$ 是對稱的，則有 $\,\!\|I-\alpha A\|_{2}=\rho \left(I-\alpha A\right)$ 。然後使用舒爾分解，我們可以找到一個酉矩陣 $\,\!U$ 和一個對角矩陣 $\,\!\Lambda$ ，使得 $\,\!A=U^{*}\Lambda U$ ，因此，

${\begin{aligned}\|I-\alpha A\|_{2}&=\|I-\alpha \Lambda \|_{2}\\&=\rho (I-\alpha \Lambda )\\&=\max _{i=1,\dots ,n}(1-\alpha \lambda _{i})\\\end{aligned}}$

最後一個表示式在 $\,\!(1-\alpha \lambda _{1})=-(1-\alpha \lambda _{n})$ 時最小化，即當 $\,\!\alpha _{opt}=2/(\lambda _{1}+\lambda _{n})$ 時最小化。使用 $\,\!\alpha$ 的這個最優值，我們得到

$\,\!(I-\alpha _{opt}\Lambda )_{i,i}=1-{\frac {2}{\lambda _{1}+\lambda _{n}}}\lambda _{i},$

這意味著

$\,\!\|I-\alpha _{opt}\Lambda \|_{2}={\frac {\lambda _{n}-\lambda _{1}}{\lambda _{1}+\lambda _{n}}}$ .

最後，我們得到

$\,\!\|e_{k+1}\|_{2}\leq {\frac {\lambda _{n}-\lambda _{1}}{\lambda _{1}+\lambda _{n}}}\|e_{k}\|_{2}$ .

問題 3b

證明如果 $A\!\,$ 的一些特徵值具有負實部，而另一些具有正實部，則不存在實數 $\alpha \!\,$ 使得迭代收斂。

解答 3b

如果對於 $i=1,2,\ldots ,n\!\,$ ， $Re(\lambda _{i})>0\!\,$ ，則當

$\alpha \in (0,2{\frac {Re(\lambda )}{|\lambda |^{2}}})\!\,$

因此 $\alpha >0\!\,$ 。

類似地，如果 $Re(\lambda _{i})<0\!\,$ 對於 $i=1,2,\ldots ,n\!\,$ ，則當以下條件滿足時，會發生收斂：

$\alpha \in (2{\frac {Re(\lambda )}{|\lambda |^{2}}},0)\!\,$

因此 $\alpha <0\!\,$ 。

如果一些特徵值是正數，一些是負數，則不存在一個實數 $\alpha \!\,$ 使迭代收斂，因為 $\alpha \!\,$ 不能同時為正數和負數。

問題 3c

令 $p=\|I-\alpha A\|<1\!\,$ 為與向量範數相關的矩陣範數。證明誤差可以用連續迭代之間的差來表示，即

\|x-x_{k+1}\|\leq {\frac {\rho }{1-\rho }}\|x_{k}-x_{k+1}\|\!\,

（此證明簡短但略微棘手）

解答 3c

${\begin{aligned}\|x-x_{k+1}\|&\leq p\|x-x_{k+1}+x_{k+1}-x_{k}\|\\&\leq p\|x-x_{k+1}\|+p\|x_{k+1}-x_{k}\|\\(1-p)\|x-x_{k+1}\|&\leq p\|x_{k+1}-x_{k}\|\\\|x-x_{k+1}\|&\leq {\frac {p}{1-p}}\|x_{k+1}-x_{k}\|\end{aligned}}\!\,$