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

問題 4a

描述牛頓法尋找光滑函式 $f:R\rightarrow R\!\,$ 的根的方法。

解答 4a

牛頓法

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,$

問題 4b

假設 $f:R\rightarrow R\!\,$ 是一個光滑函式，滿足 $f'(x)>0,\quad f''(x)>0,\quad {\mbox{ for all }}x\in R\!\,$ 並且有一個根 $x^{*}\!\,$。繪製一張幾何圖，說明該方法的收斂性，並給出牛頓法對於任何初始猜測 $x_{0}\in R\!\,$ 收斂到 $x^{*}\!\,$ 的解析證明。

解答 4b

從圖中可以看出，如果 $x_{k}<x_{*}\!\,$，則經過一步後 $x_{k+1}\!\,$ 將大於 $x_{*}\!\,$。這是因為根據假設，該函式始終遞增且向上凹。

然後不妨假設 $x_{k}>x_{*}\!\,$。

從牛頓法的兩邊減去 $x_{*}\!\,$，得到了連續誤差之間關係的表示式。

$\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}=\underbrace {x_{k}-x_{*}} _{e_{k}}-{\frac {f(x_{k})}{f'(x_{k})}}\qquad (*)\!\,$

將$f(x_{k})\!\,$在$f(x_{*})\!\,$處展開，使用泰勒展開得到

$f(x_{k})=\underbrace {f(x_{*})} _{0}+f'(\xi )\underbrace {(x_{k}-x_{*})} _{e_{k}}\!\,$

其中$\xi \in [x_{*},x_{k}]\!\,$

將這個表示式代入 (*)，得到

$e_{k+1}=(1-\underbrace {\frac {f'(\xi )}{f'(x_{k})}} _{M})e_{k}\!\,$

由於$f'(x)>0\!\,$且始終遞增（根據假設），$M\!\,$是一個小於 1 的正數。因此，隨著$k\!\,$的增加，誤差會減小，這意味著該方法始終收斂。

問題 5

這個問題的目標是在合適的有限元空間中求解邊值問題 $-u''=f{\mbox{ on }}(0,1),\quad u(0)=0,u(1)=0\!\,$ 在合適的有限元空間中。

問題 5a

對於 $N\in \mathbb {N} \!\,$，令 $x_{i}=i/N,i=0,\ldots ,N\!\,$。定義一個合適的 $N-1\!\,$ 維子空間 $V_{N}\!\,$ 在 $H_{0}^{1}\!\,$ 中與點 $x_{i}\!\,$ 相關聯。令 $\phi _{1},\ldots ,\phi _{N-1}\!\,$ 是 $V_{N}\!\,$ 中的任意基。解釋如何確定係數 $u_{i}\!\,$ 在表示元素解中的 $u_{N}=\sum _{i=1}^{N-1}u_{i}\phi _{i}\!\,$ 透過解線性方程組。證明存在唯一解

解 5a

定義合適的子空間

$V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,$

它有一個基函式，即帽子函式 $\{\phi _{i}\}_{i=1}^{N-1}\!\,$，定義如下

$\phi _{i}(x)={\begin{cases}{\frac {x-x_{i-1}}{h}}&{\mbox{ for }}x\in [x_{i-1},x_{i}]\\{\frac {x_{i+1}-x}{h}}&{\mbox{ for }}x\in [x_{i},x_{i+1}]\\0&{\mbox{ otherwise}}\end{cases}}\!\,$

如何確定係數

離散弱變分形式給出如下

找到 $u_{N}\in V_{N}\!\,$ 使得對於所有的 $v\in V_{N}\!\,$

$\underbrace {\int _{0}^{1}u_{N}'v_{N}'} _{a(u_{N},v_{N})}=\underbrace {\int _{0}^{1}fv_{N}} _{F(v_{N})}\!\,$

由於我們有一個基 $\{\phi _{i}\}_{i=1}^{N-1}\!\,$，我們有一個方程組（可以用矩陣形式表示）

對於 $j=1,2,\ldots ,N-1\!\,$

$\sum _{i=1}^{N-1}u_{i}\int _{0}^{1}\phi _{i}\phi _{j}=\int _{0}^{1}f\phi _{j}\!\,$

唯一解的存在性

唯一解的存在性來自 Lax-Milgram 定理。

注意以下幾點

• 雙線性形式連續（有界）例如 $a(u_{N},v_{N})\leq \|u_{N}\|_{1}\|v_{N}\|_{1}\!\,$

${\begin{aligned}a(u,v)&=\int u'v'\\&\leq |u|_{1}|v|_{1}{\mbox{ Cauchy Schwartz in L2 }}\\&\leq \|u\|_{1}\|v\|_{1}{\mbox{ dominance of spaces }}\end{aligned}}\!\,$

• 雙線性形式強制性，例如 $a(u_{N},u_{N})\geq C\|u_{N}\|_{1}^{2}\!\,$

${\begin{aligned}a(v,v)&=\int v'^{2}\\&=|v|_{1}^{2}\\&\geq C\|v\|_{1}^{2}{\mbox{ Poincare inequality}}\end{aligned}}\!\,$

Poincare 不等式：$\|v\|_{0}\leq \|v\|_{1}\leq C|v|_{1}\!\,$

• $F(v_{N})\leq C\|v_{N}\|_{1}\!\,$

${\begin{aligned}\int fv&\leq \|f\|_{0}\|v\|_{0}\\&\leq \|f\|_{1}\|v\|_{1}\end{aligned}}\!\,$

問題 5b

證明 $a(u,v)=\int _{0}^{1}u'v'dx\!\,$ 在 $H_{0}^{1}\!\,$ 上定義了一個內積，因此在 $H_{0}^{1}\!\,$ 中定義了一個正交的概念。

問題 5b 的解答

• $a(u,v)=a(v,u)\!\,$

• $a(\alpha u,v)=\int \alpha u'v'=\alpha \int u'v'=\alpha a(u,v)\!\,$

• $a(u+w,v)=\int (u'+w')v'=\int u'v'+\int w'v'=a(u,v)+a(w,v)\!\,$

• $a(u,u)=\int u'^{2}\neq 0{\mbox{ if }}u\neq 0\!\,$

問題 5c

令 $\phi _{1}=1-2|x-{\frac {1}{2}}|\!\,$ 是 一維空間 $V_{2}\!\,$ 的基函式。在 $V_{4}\!\,$ 中找到包含基函式 $\phi _{1}\!\,$ 的正交基。繪製基函式。說明你將如何構建包含 $V^{2^{n-1}}\!\,$ 基函式的 $V_{2^{n}}\!\,$ 基。

Solution 5c

$\phi _{1}={\begin{cases}2x&{\mbox{ for }}x\in [0,{\frac {1}{2}}]\\2-2x&{\mbox{ for }}x\in [{\frac {1}{2}},1]\end{cases}}\!\,$

$\phi _{2}={\begin{cases}8x&{\mbox{ for }}x\in [0,{\frac {1}{4}}]\\-8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{4}},{\frac {1}{2}}]\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

$\phi _{3}={\begin{cases}8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{2}},{\frac {3}{4}}]\\-8(x-1)&{\mbox{ for }}x\in [{\frac {1}{4}},1]\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

在每個新相鄰子區間上定義一個新的帽子函式。這些帽子函式的高度應該與前一個基底的帽子函式相同。

問題 5d

對於這個特殊的基底，(a) 中線性方程組的結構是什麼？

解答 5d

對於我們在 (a) 中的系統，該系統產生一個對角矩陣。

問題 6

為了求解方程 $y'=f(x,y)\!\,$，考慮如下方案 $y_{n+1}=y_{n}+{\frac {h}{2}}(y_{n}'+y'_{n+1})+{\frac {h^{2}}{12}}(y''_{n}-y''_{n+1})\!\,$ 其中 $y_{n}'=f(x_{n},y_{n})\!\,$ 且 $y_{n}''=f_{x}(x_{n},y_{n})+f(x_{n},y_{n})f_{y}(x_{n},y_{n})\!\,$

問題 6a

證明該方案是四階精度的。

解答 6a

${\begin{array}{|c|c|c|c|c|c|c|c|}{\mbox{Order}}&y(t+h)&-y(t)&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t+h)&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t+h)&\Sigma \\\hline &&&&&&&\\0&y(t)&-y(t)&0&0&0&0&0\\1&y'(t)h&0&-{\frac {h}{2}}y'(t)&-{\frac {h}{2}}y'(t)&0&0&0\\2&{\frac {y''(t)h^{2}}{2}}&0&0&-{\frac {h}{2}}y''(t)h&-{\frac {h^{2}}{12}}y''(t)&{\frac {h^{2}}{12}}y''(t)&0\\3&{\frac {y'''(t)h^{3}}{6}}&0&0&-{\frac {h}{2}}{\frac {y'''(t)}{2}}h^{2}&0&{\frac {h^{2}}{12}}y'''(t)h&0\\4&y''''(t){\frac {h^{4}}{24}}&0&0&-{\frac {h}{2}}y''''(t){\frac {h^{3}}{6}}&0&{\frac {h^{2}}{12}}y''''(t){\frac {h^{2}}{2}}&0\\5&O(h^{5})&0&0&O(h^{5})&0&O(h^{5})&O(h^{5})\\\hline \end{array}}$

問題 6b

為了進行穩定性分析，我們令 $f(x,y)=\lambda y\!\,$。說明對於該方案，${\overline {\lambda }}=h\lambda \!\,$ 屬於絕對穩定區域的含義，並證明該方案的絕對穩定區域包含整個負實軸。

解 6b

$y_{n}''={\frac {d}{dx}}\lambda y+\lambda y{\frac {d}{dy}}\lambda y=\lambda ^{2}y\!\,$

$y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h^{2}}{12}}[\lambda ^{2}y_{n}-\lambda ^{2}y_{n+1}]\!\,$

令 $z=h\lambda \!\,$ 並重新排列項得到

$y_{n+1}=\underbrace {\left({\frac {1+{\frac {z}{2}}+{\frac {z^{2}}{12}}}{1-{\frac {z}{2}}+{\frac {z^{2}}{12}}}}\right)} _{M}y_{n}\!\,$

如果 $z\!\,$ 是負實數，則 $M<1\!\,$