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

問題 1

推匯出單點、雙點和三點高斯求積公式，使得 $\int _{-1}^{1}f(x)x^{4}dx\approx \sum _{j=1}^{n}f(x_{j})w_{j}\!\,$ 給出這些公式誤差的界限。

解答 1

找到相對於權重函式的正交多項式

對於這個問題，我們需要前三個正交多項式 $P_{1},P_{2},{\mbox{ and }}P_{3}\!\,$ 相對於加權內積

$\left\langle f,g\right\rangle =\int _{-1}^{1}f(x)g(x)w(x)dx\!\,$

其中 $w(x)=x^{4}\!\,$ 在我們的例子中。這可以透過對基 $\left\{1,x,x^{2},x^{3}\right\}\!\,$ 使用 Gram-Schmidt 正交化來完成

零階多項式

令 $P_{0}(x)=1\!\,$

一階多項式

${\begin{aligned}P_{1}(x)&=x-{\frac {\left\langle 1,x\right\rangle }{\left\langle 1,1\right\rangle }}\cdot 1\\&=x-\underbrace {\frac {\int _{-1}^{1}x^{5}dx}{\int _{-1}^{1}x^{4}dx}} _{\frac {0}{2/5}}\\&=x\end{aligned}}$

二階多項式

${\begin{aligned}P_{2}(x)&=x^{2}-{\frac {\left\langle 1,x^{2}\right\rangle }{\left\langle 1,1\right\rangle }}\cdot 1-{\frac {\left\langle x,x^{2}\right\rangle }{\left\langle x,x\right\rangle }}\cdot x\\&=x^{2}-{\frac {\int _{-1}^{1}x^{6}dx}{\int _{-1}^{1}x^{4}dx}}-x\cdot \underbrace {\frac {\int _{-1}^{1}x^{7}dx}{\int _{-1}^{1}x^{6}dx}} _{\frac {0}{2/7}}\\&=x^{2}-{\frac {5}{7}}\end{aligned}}$

三階多項式

${\begin{aligned}P_{3}(x)&=x^{3}-{\frac {\left\langle 1,x^{3}\right\rangle }{\left\langle 1,1\right\rangle }}\cdot 1-{\frac {\left\langle x,x^{3}\right\rangle }{\left\langle x,x\right\rangle }}\cdot x-{\frac {\left\langle x^{2}-{\frac {5}{7}},x^{3}\right\rangle }{\left\langle x^{2}-{\frac {5}{7}},x^{2}-{\frac {5}{7}}\right\rangle }}\cdot (x^{2}-{\frac {5}{7}})\\&=x^{3}-0-{\frac {7}{2}}x\cdot {\frac {\int _{-1}^{1}x^{8}dx}{\int _{-1}^{1}x^{6}dx}}-0\\&=x^{3}-{\frac {7}{9}}x\end{aligned}}$

求多項式的根

這些多項式的根將用作高斯求積中的插值節點。

${\begin{array}{|c|c|}{\mbox{Polynomial}}&{\mbox{Roots}}\\\hline P_{1}(x)=x&0\\\\P_{2}(x)=x^{2}-{\frac {5}{7}}&\pm {\sqrt {\frac {5}{7}}}\\\\P_{3}(x)=x^{3}-{\frac {7}{9}}x&0,\pm {\sqrt {\frac {7}{9}}}\\\\\hline \end{array}}$

計算係數的公式

在高斯求積中，我們有

$w_{j}=\int _{-1}^{1}l_{i}(x)x^{4}dx\!\,$，其中

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

1點公式

$l_{1}(x)=1\!\,$

$w_{1}=\int _{-1}^{1}x^{4}dx={\frac {2}{5}}\!\,$

$\int _{-1}^{1}f(x)x^{4}dx\approx {\frac {2}{5}}f(x_{1})\!\,$

其中 $x_{1}\!\,$ 是 $P_{1}(x)\!\,$ 的根。

2 點公式

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

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

$w_{1}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{1}-x_{2}}}x^{4}dx={\frac {2x_{2}}{5(x_{2}-x_{1})}}\!\,$

$w_{2}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{2}-x_{1}}}x^{4}dx={\frac {2x_{1}}{5(x_{1}-x_{2})}}\!\,$

$\int _{-1}^{1}f(x)x^{4}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})\!\,$

其中 $x_{1}{\mbox{ and }}x_{2}\!\,$ 是 $P_{2}(x)\!\,$ 的根。

3 點公式

$l_{1}(x)={\frac {x-x_{2}}{x_{1}-x_{2}}}{\frac {x-x_{3}}{x_{1}-x_{3}}}\!\,$

$l_{2}(x)={\frac {x-x_{1}}{x_{2}-x_{1}}}{\frac {x-x_{3}}{x_{2}-x_{3}}}\!\,$

$l_{3}(x)={\frac {x-x_{1}}{x_{3}-x_{1}}}{\frac {x-x_{2}}{x_{3}-x_{2}}}\!\,$

$w_{1}=\int _{-1}^{1}{\frac {x-x_{2}}{x_{1}-x_{2}}}{\frac {x-x_{3}}{x_{1}-x_{3}}}x^{4}dx={\frac {1}{(x_{1}-x_{2})(x_{1}-x_{3})}}\left({\frac {2}{7}}+{\frac {2x_{2}x_{3}}{5}}\right)\!\,$

$w_{2}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{2}-x_{1}}}{\frac {x-x_{3}}{x_{2}-x_{3}}}x^{4}dx={\frac {1}{(x_{2}-x_{1})(x_{2}-x_{3})}}\left({\frac {2}{7}}+{\frac {2x_{1}x_{3}}{5}}\right)\!\,$

$w_{3}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{3}-x_{1}}}{\frac {x-x_{2}}{x_{3}-x_{2}}}x^{4}dx={\frac {1}{(x_{3}-x_{1})(x_{3}-x_{2})}}\left({\frac {2}{7}}+{\frac {2x_{1}x_{2}}{5}}\right)\!\,$

$\int _{-1}^{1}f(x)x^{4}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})+w_{3}f(x_{3})\!\,$

其中 $x_{1}{\mbox{, }}x_{2}{\mbox{ and }}x_{3}\!\,$ 是 $P_{3}(x)\!\,$ 的根。

推導誤差界

我們知道，這種求積公式對所有次數不超過 $2n-1\!\,$ 的多項式是精確的。

我們選擇一個次數不超過 $2n-1\!\,$ 的多項式 $p\!\,$，它對 Hermite 插值，即

$p(x_{i})=f(x_{i})\quad p'(x_{i})=f'(x_{i})\quad (0\leq i\leq n-1)\!\,$

這種插值的誤差是

$f(x)-p(x)={\frac {f^{(2n)}(\zeta (x))}{(2n)!}}\prod _{i=0}^{n-1}(x-x_{i})^{2}\!\,$

按照以下步驟計算求積公式的誤差

${\begin{aligned}E&=\int _{-1}^{1}f(x)x^{4}dx-\sum _{i=0}^{n-1}w_{i}f(x_{i})\\&=\int _{-1}^{1}f(x)x^{4}dx-\sum _{i=0}^{n-1}w_{i}p(x_{i})\\&=\int _{-1}^{1}f(x)x^{4}dx-\int _{-1}^{1}p(x)x^{4}dx\\&=\int _{-1}^{1}(f(x)-p(x))x^{4}dx\\&=\int _{-1}^{1}{\frac {f^{(2n)}(\zeta (x))}{(2n)!}}\prod _{i=0}^{n-1}(x-x_{i})^{2}\cdot x^{4}dx\\&={\frac {f^{(2n)}(\xi )}{(2n)!}}\int _{-1}^{1}x^{4}\cdot \underbrace {\prod _{i=0}^{n-1}(x-x_{i})^{2}} _{(p_{n}(x))^{2}}dx\end{aligned}}\!\,$

其中最後一行來自積分的均值定理。

注意 $p_{n}(x)\!\,$ 僅僅是關於權重函式正交的多項式，因為 $x_{i}\!\,$ 是多項式的根。

因此，1點高斯求積的誤差為

${\begin{aligned}E&={\frac {f^{(2)}(\xi )}{(2)!}}\int _{-1}^{1}x^{4}\cdot x^{2}dx\\&={\frac {f^{(2)}(\xi )}{7}}\end{aligned}}\!\,$

2點求積的誤差

${\begin{aligned}E&={\frac {f^{(4)}(\xi )}{(4)!}}\int _{-1}^{1}x^{4}\cdot (x^{2}-{\frac {5}{7}})^{2}dx\end{aligned}}\!\,$

3點求積的誤差

${\begin{aligned}E&={\frac {f^{(6)}(\xi )}{(6)!}}\int _{-1}^{1}x^{4}\cdot (x^{3}-{\frac {7}{9}}x)^{2}dx\end{aligned}}\!\,$

問題 2

我們希望用迭代方法求解 $Ax=b\!\,$，其中 $A={\begin{bmatrix}1&1&-1\\1&2&1\\1&1&1\end{bmatrix}}\!\,$ 證明對於該 $A\!\,$，雅可比迭代法和高斯-賽德爾迭代法都收斂。解釋為什麼對於該 $A\!\,$，其中一種方法比另一種方法更好。

解題 2

雅可比迭代法

將 $A\!\,$ 分解成對角、下三角和上三角部分，即

$A=D+(L+U)\!\,$

透過以下方式解出 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}}\!\,$

高斯-賽德爾迭代法

將 $A\!\,$ 分解成對角、下三角和上三角部分，即

$A=(D+L)+U\!\,$

透過以下方式解出 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}}\!\,$

雅可比收斂性

如果 $D^{-1}(L+U)\!\,$ 的譜半徑小於 1，即雅可比迭代法收斂。

$\rho (D^{-1}(L+U))<1\!\,$

矩陣的特徵值為

$D^{-1}(L+U)={\begin{bmatrix}0&1&-1\\{\frac {1}{2}}&0&{\frac {1}{2}}\\1&1&0\end{bmatrix}}\!\,$

是 $\lambda =0,0,0\!\,$，即特徵值 $0\!\,$ 的階數為 3。

因此，譜半徑為 $\rho =0<1\!\,$.

高斯-賽德爾迭代收斂

如果 $(D+L)^{-1}U\!\,$ 的譜半徑小於 1，則高斯-賽德爾迭代收斂，即

$\rho ((D+L)^{-1}U)<1\!\,$

矩陣的特徵值為

$(D+L)^{-1}U={\begin{bmatrix}0&1&-1\\0&-{\frac {1}{2}}&1\\0&-{\frac {1}{2}}&0\end{bmatrix}}\!\,$

是 $\lambda =0,-{\frac {1}{4}}+{\frac {{\sqrt {7}}i}{4}},-{\frac {1}{4}}-{\frac {{\sqrt {7}}i}{4}}\!\,$

因此，譜半徑為 $\rho ={\sqrt {{\frac {1}{16}}+{\frac {7}{16}}}}={\frac {\sqrt {2}}{2}}\approx .7<1\!\,$.

方法比較

通常，高斯-賽德爾迭代比雅可比迭代收斂更快，因為高斯-賽德爾迭代使用新的$x_{i}\!\,$ 分量，當它們可用時，但在這種情況下，$\rho _{Jacobi}<\rho _{Gauss-Seidel}\!\,$，因此雅可比迭代速度更快。

問題 3

考慮以下三項多項式遞迴 $p_{k+1}(x)=(x-\mu _{k})p_{k}(x)-\nu _{k}^{2}p_{k-1}(x)\quad {\mbox{ for }}k=1,2,\dots ,\!\,$ 由$p_{0}(x)=1{\mbox{ and }}p_{1}(x)=x-\mu _{0}\!\,$ 初始化，其中每個$\mu _{k}{\mbox{ and }}\nu _{k}\!\,$ 都是實數，每個$\nu _{k}\!\,$ 都不為零。

問題 3a

證明每個$p_{k}(x)\!\,$ 是一個首一多項式，其度數為$k\!\,$，並且對於每個$n=0,1,\dots \!\,$，有 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{n}(x)\right\}=\operatorname {span} \left\{1,x,x^{2},\dots ,x^{n}\right\}\!\,$

解 3a

我們透過歸納法證明該結論。

基本情況

$p_{0}(x)=1\!\,$ 是一個首一多項式，次數為零，且 $\operatorname {span} \left\{p_{0}(x)\right\}=\operatorname {span} \left\{1\right\}\!\,$。

$p_{1}(x)=x-\mu _{0}\!\,$ 是一個首一多項式，次數為一，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x)\right\}=\operatorname {span} \left\{1,x\right\}\!\,$。

$p_{2}(x)=(x-\mu _{0})(x-\mu _{1})-\nu _{1}^{2}\!\,$ 是一個首一多項式，次數為 2，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),p_{2}(x)\right\}=\operatorname {span} \left\{1,x,x^{2}\right\}\!\,$。

歸納步驟

假設 $p_{k-1}(x)\!\,$ 是一個首一多項式，次數為 $k-1\!\,$，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{k-1}(x)\right\}=\operatorname {span} \left\{1,x,\dots ,x^{k-1}\right\}\!\,$。

同時假設 $p_{k}(x)\!\,$ 是一個首一多項式，次數為 $k\!\,$，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{k}(x)\right\}=\operatorname {span} \left\{1,x,\dots ,x^{k}\right\}\!\,$。

然後從假設來看，$p_{k+1}(x)=(x-\mu _{k})p_{k}(x)-\nu _{k}^{2}p_{k-1}(x)\!\,$ 是一個首項係數為1，次數為 $k+1\!\,$ 的多項式。

同時，

$\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{k+1}(x)\right\}=\operatorname {span} \left\{1,x,\dots ,x^{k+1}\right\}\!\,$

因為 $p_{k+1}(x)\!\,$ 只是 $x^{n+1}\!\,$ 加上在 $\operatorname {span} \left\{1,x,\dots ,x^{k}\right\}\!\,$ 中已經存在的低階項的線性組合。

問題 3b

證明對每個 $k=0,1,\dots \!\,$，多項式 $p_{k}(x)\!\,$ 有 $k\!\,$ 個單根實根，它們與 $p_{k-1}(x)\!\,$ 的根交錯排列。

解答 3b

我們透過數學歸納法來證明這個結論。

基本情況

讓我們考慮 $k=2\!\,$ 的情況。我們知道

$p_{2}(x)=(x-\mu _{0})(x-\mu _{1})-\nu _{1}^{2}.\!\,$

二次方程公式表明 $p_{2}(x)\!\,$ 有兩個簡單的實根。

令 $r_{21}\!\,$ 和 $r_{22}\!\,$ 為 $p_{2}(x)\!\,$ 的零點。然後，我們有（因為符號變化）

$p_{2}(\mu _{0})=-\nu _{1}^{2}\!\,$ 和 $\lim _{x\rightarrow \infty }p_{2}(x)>0\!\,$ $\Rightarrow \!\,$ 存在 $r_{22}\in (\mu _{0},\infty )\!\,$ 使得 $p_{2}(r_{22})=0\!\,$。

$p_{2}(\mu _{0})=-\nu _{1}^{2}\!\,$ 和 $\lim _{x\rightarrow -\infty }p_{2}(x)>0\!\,$ $\Rightarrow \!\,$ 存在 $r_{21}\in (-\infty ,\mu _{0})\!\,$ 使得 $p_{2}(r_{21})=0\!\,$。

總之，$r_{21}<\underbrace {\mu _{0}} _{r_{11}}<r_{22}.\!\,$.

歸納步驟

設$r_{k-1,1},\dots ,r_{k-1,k-1}\!\,$ 和 $r_{k,1},\dots ,r_{k,k}\!\,$ 分別是$p_{k-1}(x)\!\,$ 和 $p_{k}(x)\!\,$ 的簡單實根，使得$p_{k}\!\,$ 的根與$p_{k-1}\!\,$ 的根交錯，即

$r_{k,1}<r_{k-1,1}<r_{k,2}<r_{k-1,2}<\dots <r_{k-1,k-1}<r_{k,k}.\!\,$

那麼，我們有

$p_{k+1}(r_{k,1})=(r_{k,1}-\mu _{k})\underbrace {p_{k}(r_{k,1})} _{0}-\nu _{k}^{2}p_{k-1}(r_{k,1})=-\nu _{k}^{2}p_{k-1}(r_{k,1}),\!\,$

$p_{k+1}(r_{k,2})=(r_{k,2}-\mu _{k})\underbrace {p_{k}(r_{k,2})} _{0}-\nu _{k}^{2}p_{k-1}(r_{k,2})=-\nu _{k}^{2}p_{k-1}(r_{k,2}).\!\,$

根據歸納假設，$p_{k-1}(r_{k,1})\!\,$ 和 $p_{k-1}(r_{k,2})\!\,$ 具有不同的符號，因為 $r_{k,1}<r_{k-1,1}<r_{k,2}\!\,$。因此，存在一個 $r_{k+1,1}\in (r_{k,1},r_{k,2})\!\,$ 使得 $p_{k+1}(r_{k+1,1})=0\!\,$。

對所有區間 $(r_{k,j},r_{k,j+1})\!\,$ 以相同的方式進行，我們得到存在一個 $r_{k+1,j}\in (r_{k,j},r_{k,j+1})\!\,$ 使得 $p_{k+1}(r_{k+1,j})=0\!\,$ 對於 $j=1,\dots ,k-1.\!\,$

現在我們考慮 $p_{k+1}\!\,$ 最小的和最大的根，即 $r_{k+1,0},r_{k+1,k+1}\!\,$

因為對於 $k=0,1,2,\ldots \!\,$，$p_{k}\!\,$ 是一個首一多項式，

$\lim _{x\rightarrow \infty }p_{k}(x)=\infty \!\,$

因此，對於任何 $x>r_{k}\!\,$（任何大於 $p_{k}\!\,$ 最大根的 $x\!\,$）

$p_{k}(x)>0\!\,$

因此

$\lim _{x\rightarrow \infty }p_{k+1}(x)>0\!\,$ 和 $p_{k+1}(r_{k,k})=-\nu _{k}^{2}p_{k-1}(r_{k,k})<0,\!\,$

意味著存在 $r_{k+1,k}\in (r_{k,k},\infty )\!\,$ 使得 $p_{k+1}(r_{k+1,k})=0\!\,$.

如果 $k+1\!\,$ 是偶數，則根據類似的推理

$\lim _{x\rightarrow -\infty }p_{k+1}(x)>0\!\,$ 和 $p_{k+1}(r_{k,1})=-\nu _{k}^{2}p_{k-1}(r_{k,1})<0,\!\,$ $\Rightarrow \!\,$ 存在 $r_{k+1,0}\in (-\infty ,r_{k,1})\!\,$ 使得 $p_{k+1}(r_{k+1,0})=0\!\,$.

如果 $k+1\!\,$ 是奇數，

$\lim _{x\rightarrow -\infty }p_{k+1}(x)<0\!\,$ 並且 $p_{k+1}(r_{k,1})=-\nu _{k}^{2}p_{k-1}(r_{k,1})>0,\!\,$ $\Rightarrow \!\,$ 存在 $r_{k+1,0}\in (-\infty ,r_{k,1})\!\,$ 使得 $p_{k+1}(r_{k+1,0})=0\!\,$。

問題 3c

證明對於每個 $n=0,1,\dots \!\,$，$p_{k+1}(x)\!\,$ 的根是以下對稱三對角矩陣的特徵值 $T={\begin{pmatrix}\mu _{0}&\nu _{1}&0&\cdots &0\\\nu _{1}&\mu _{1}&\nu _{2}&\ddots &\vdots \\0&\nu _{2}&\nu _{2}&\ddots &0\\\vdots &\ddots &\ddots &\ddots &\nu _{n}\\0&\cdots &0&\nu _{n}&\mu _{n}\end{pmatrix}}$

解 3c

令 $T_{n+1}={\begin{pmatrix}\mu _{0}&\nu _{1}&0&\cdots &0\\\nu _{1}&\mu _{1}&\nu _{2}&\ddots &\vdots \\0&\nu _{2}&\nu _{2}&\ddots &0\\\vdots &\ddots &\ddots &\ddots &\nu _{n}\\0&\cdots &0&\nu _{n}&\mu _{n}\end{pmatrix}}$

那麼 $\operatorname {det} (xI_{n+1}-T_{n+1})\!\,$ 是一個關於 $x\!\,$ 的首一多項式，其次數為 $n+1\!\,$。

沿著最後一行展開這個行列式，我們得到

$\operatorname {det} (xI_{n+1}-T_{n+1})=(x-\mu _{n})\operatorname {det} (xI_{n}-T_{n})-\nu _{n}^{2}\operatorname {det} (xI_{n-1}-T_{n-1})\qquad (1)\!\,$

其中 $\operatorname {det} (xI_{n}-T_{n})\!\,$ 和 $\operatorname {det} (xI_{n-1}-T_{n-1})\!\,$ 分別是次數為 $n\!\,$ 和 $n-1\!\,$ 的首一多項式。

注意 $\operatorname {det} (xI_{1}-T_{1})=x-\mu _{0}\equiv p_{1}(x)\!\,$，並且如果我們令 $p_{0}(x)\equiv 1\!\,$，那麼 (1) 等價於問題中陳述的三項遞推關係。

因此，$p_{n+1}(x)\equiv \operatorname {det} (xI_{n+1}-T_{n+1})=0\!\,$ 表明 $p_{n+1}(x)\!\,$ 的根是 $T_{n+1}\!\,$ 的特徵值。