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

問題4a

給定一個光滑函式$f(x)\!\,$，說明割線法用於求解$\mathbb {R} \!\,$ 中非線性方程的近似解。 $f(x)=0\!\,$

解答4a

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

問題4b

說明此方法的收斂階數，並解釋如何推匯出它。

解答4b

如果$f''(x)\!\,$ 有界且 $x_{0}\!\,$ 接近 $x_{*}\!\,$，則割線法的收斂階數為$\phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.6180339887\!\,$（黃金分割率）。

部分證明可以在這裡找到。

問題4c

是否存在收斂階數更高的情況？解釋你的答案。

問題5

考慮初始值問題 $y'=f(t,y),\quad y(0)=y_{0}\!\,$

問題 5a

將 ODE 寫成積分形式，並解釋如何使用梯形求積公式推匯出具有均勻時間步長 $h={\frac {T}{N}}\!\,$ 的梯形方法。 $y_{n+1}=y_{n}+{\frac {h}{2}}(f(t_{n+1},y_{n+1})+f(t_{n},y_{n}))\!\,$

解 5a

$y(t_{n+1})-y(t_{n})=\int _{t_{n}}^{t_{n+1}}y'=\int _{t_{n}}^{t_{n+1}}f(t,y)\approx {\frac {h}{2}}(f(t_{n+1},y_{n+1})+f(t_{n},y_{n}))\!\,$

問題 5b

定義絕對穩定性的概念。也就是說，考慮將該方法應用於 $f(t,y)=\lambda y\!\,$，其中 $\lambda \!\,$ 為實數。證明絕對穩定區域包含複數 $h\lambda \!\,$ 平面的整個負實軸。

解 5b

令 $f(t,y)=\lambda y\!\,$，我們有

$y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h}{2}}\lambda y_{n}\!\,$

如果我們令 $h\lambda =z\!\,$，並對該方程進行重新排列，我們得到

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

我們需要 $M<1\!\,$。如果 $\lambda \!\,$ 是一個負實數，則該條件成立。

問題 5c

假設 $f(t,y)=Ay\!\,$，其中 $A\in R^{n\times n}\!\,$ 是一個對稱矩陣，並且 $y\in R^{n}\!\,$。檢驗 $A\!\,$ 的哪些屬性保證了該方法是絕對穩定的（提示：研究 $A\!\,$ 的特徵值）。

解答 5

我們現在希望得到的是

$\left\|{\frac {1+{\frac {h}{2}}A}{1-{\frac {h}{2}}A}}\right\|<1\!\,$

即

$\|1+{\frac {h}{2}}A\|<\|1-{\frac {h}{2}}A\|\!\,$

或者（由於 $A\!\,$ 是對稱的）

$\rho (I+{\frac {h}{2}}Q\Lambda Q^{T})<\rho (I-{\frac {h}{2}}Q\Lambda Q^{T})\!\,$

或者（由於乘以正交矩陣不會影響範數）

$\rho (I+{\frac {h}{2}}\Lambda )<\rho (I-{\frac {h}{2}}\Lambda )\!\,$

或者（根據定義）

$\max _{i}\{1+{\frac {h}{2}}\lambda _{i}\}<\max _{i}\{1-{\frac {h}{2}}\lambda _{i}\}\!\,$

如果 $A\!\,$ 是負定的（所有特徵值都為負），上述不等式成立。

問題 6

考慮在 $(0,1):\!\,$ 中的以下兩點邊值問題： $(1)\qquad -u_{xx}+u=1,\quad u'(0)=u'(1)=0\!\,$

問題 6a

給出 (1) 的變分形式，即將其表達為 $(2)\qquad u\in H:a(u,v)=F(v),{\mbox{ for all }}v\in H\!\,$ 定義函式空間 $H\!\,$、雙線性形式 $a\!\,$ 和線性泛函 $F\!\,$ 並說明 $(1)\!\,$ 和 $(2)\!\,$ 之間的聯絡。證明解 $u\!\,$ 是唯一的。

解 6a

變分形式

透過用測試函式 $v\in H\!\,$ 乘以並從 0 到 1 積分來推匯出變分形式。使用分部積分並代入初始條件，則有

找到 $u\in H=\{v\in H^{1}(0,1)\}\!\,$ 使得對於所有 $v\in H\!\,$

$\underbrace {\int _{0}^{1}u'v'+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}v} _{F(v)}\!\,$

（1）和（2）之間的關係

（2）是（1）的等效公式，但它不涉及二階導數。

唯一解的存在性

根據 Lax-Milgram 定理，我們有唯一解的存在性。

• 雙線性形式連續/有界：$a(u,v)\leq C\|u\|_{1}\|v\|_{1}\!\,$

• 雙線性形式強制性：$a(u,u)\geq 1\cdot \|u\|_{1}^{2}\!\,$

• 泛函有界：$F(v)\leq \|v\|_{1}\!\,$

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

問題 6b

使用分段線性元素在均勻劃分 $P=\{x_{i}=(i-1)h\}_{i=1}^{N}\!\,$ 上寫出有限元方法，網格大小為 $h={\frac {1}{N-1}}\!\,$。如果 $U=(u_{i})_{i=1}^{N}\!\,$ 是有限元解的節點值向量，求剛度矩陣 $A\!\,$ 和右端項 $F\!\,$，使得 $AU=F\!\,$。證明 $A\!\,$ 是對稱正定的。證明解 $U\!\,$ 是唯一的。

解 6b

定義帽子函式 $\{\phi _{i}\}_{i=1}^{N}\!\,$ 作為離散空間的基。注意 $\phi _{0}\!\,$ 和 $\phi _{n}\!\,$ 的支撐範圍只有其他基函式的一半。使用此基，我們有

$\underbrace {\begin{bmatrix}{\frac {h}{3}}+{\frac {1}{h}}&{\frac {h}{6}}-{\frac {1}{h}}&&&&&\\{\frac {h}{6}}-{\frac {1}{h}}&{\frac {2}{3}}h+{\frac {2}{h}}&{\frac {h}{6}}-{\frac {1}{h}}&&&&\\&\ddots &\ddots &\ddots &&&\\&&&&&{\frac {h}{6}}-{\frac {1}{h}}&{\frac {h}{3}}+{\frac {1}{h}}\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{1}\\u_{2}\\\vdots \\u_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}{\frac {h}{2}}\\h\\\vdots \\{\frac {h}{2}}\end{bmatrix}} _{F}\!\,$

觀察到 $A\!\,$ 是對稱的。根據格爾欣定理，它是正定的。解 $U\!\,$ 是唯一的，因為 $A\!\,$ 是對角佔優的。

問題 6c

考慮 $[0,1]\!\,$ 的兩個劃分 $P_{1}\!\,$ 和 $P_{2}\!\,$，其中 $P_{2}\!\,$ 是 $P_{1}\!\,$ 的細化。令 $V_{1}\!\,$ 和 $V_{2}\!\,$ 為相應的分段線性有限元空間。證明 $V_{1}\!\,$ 是 $V_{2}\!\,$ 的子空間。

解 6c

如果 $v\in V_{1}\!\,$，那麼它也在 $V_{2}\!\,$ 中，因為 $P_{2}\!\,$ 是 $P_{1}\!\,$ 的細化。換句話說，由於 $V_{1}\!\,$ 在每個區間上是分段線性的，它在細化後的區間上也是分段線性的。

問題 6d

令 $u_{1}\in V_{1}\!\,$ 和 $u_{2}\in V_{2}\!\,$ 是有限元解。證明正交性等式。 $\|u-u_{1}\|_{H^{1}}^{2}=\|u-u_{2}\|_{H^{1}}^{2}+\|u_{1}-u_{2}\|_{H^{1}}^{2}\!\,$

解答 6

從誤差的正交性，我們有

$a(u-u_{h},v_{h})=0\!\,$ 對於所有 $v\in V_{h}\!\,$

具體來說，

$a(u-u_{2},u_{1}-u_{2})=0\!\,$

然後

$\underbrace {a(u-u_{1},u-u_{1})} _{\|u-u_{1}\|_{H^{1}}^{2}}+2\underbrace {a(u-u_{2},u_{1}-u_{2})} _{0}=\underbrace {a(u-u_{2},u-u_{2})} _{\|u-u_{2}\|_{H^{1}}^{2}}+\underbrace {a(u_{1}-u_{2},u_{1}-u_{2})} _{\|u_{1}-u_{2}\|_{H^{1}}^{2}}\!\,$