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

問題 4

人們希望透過以下一種或多種迭代方法來求解方程 $x+\ln x=0\!\,$，其根為 $r\approx 0.5\!\,$ (i) $x_{k+1}=-\ln x_{k}\!\,$ (ii) $x_{k+1}=e^{-x_{k}}\!\,$ (iii) $x_{k+1}={\frac {x_{k}+e^{-x_{k}}}{2}}\!\,$

問題 4a

這三種方法中哪一種可以使用？

解答 4a

方法 {ii} 和 {iii} 是 $x+\ln(x)=0\!\,$ 的合適的不動點迭代。

{i} 不是一個不動點迭代

為了成為合適的不動點迭代，每次迭代的範圍必須在下次迭代的域內。在 {i} 的情況下，$x_{k+1}=-\ln x_{k}\!\,$ 可以返回 $(-\infty ,\infty )\!\,$ 中的值，但只能接受 $(0,\infty )\!\,$ 中的 x 值。

{ii} 和 {iii} 是不動點迭代

令 $f(x):=e^{-x}\!\,$ 和 $g(x):={\frac {x+e^{-x}}{2}}\!\,$

很明顯

$f:(-\infty ,\infty )\to (0,\infty )\!\,$

以及

$g:(-\infty ,\infty )\to (0,\infty )\!\,$

同時注意到給定域 $D=(0,1)$

$|f(x)-f(y)|\leq |f'(\eta )||x-y|\!\,$ 對於某些 $\eta \in D\!\,$

其中 $\max _{\eta \in D}|f'(\eta )|=\max _{\eta \in D}|e^{-x}|\leq 1\!\,$

以及

$|g(x)-g(y)|\leq |g'(\eta )||x-y|\!\,$ 對於某些 $\eta \in D\!\,$

其中 $\max _{\eta \in D}|g'(\eta )|=\max _{\eta \in D}|{\frac {1}{2}}(1-e^{-x})|\approx 0.316060279\!\,$

也就是說，f、g 都是壓縮對映。

問題 4b

應該使用哪種方法？

解決方案 4b

對於區間 (0,1)，{iii} 比 {ii} 更好的不動點迭代，因為它的 Lipschitz 常數更小。

問題 4c

給出更好的迭代公式。

解決方案 4c

牛頓法給出的迭代公式具有二次收斂性，相比之下，{iii} 的收斂性是線性的。

問題 5

考慮以下邊界值問題： ${\begin{cases}-u''+e^{u}=0&0<x<1\\u(0)=u(1)=0&\end{cases}}\!\,$ 使用在等距網格上連續分段線性函式的有限元方法離散該問題。積分採用梯形法則。將該方法寫成以下形式： $AU_{h}+F_{h}(U_{h})=0\!\,$ 其中 $U_{h}\in \mathbb {R} ^{m}\!\,$ 表示近似解的未知節點值向量，$A\!\,$ 是一個 $m\times m\!\,$ 矩陣，其元素與離散引數 $h\!\,$ 無關，並且 $F_{h}:\mathbb {R} ^{m}\rightarrow \mathbb {R} ^{m}\!\,$ 是一個非線性的向量值函式。

解決方案 5

尋找弱形式

令 $V=H_{0}^{1}(0,1):=\{v\in H^{1}:v(0)=v(1)=0\}\!\,$.

用測試函式 $v\in V\!\,$ 乘以原方程並進行分部積分，我們得到

$\int _{0}^{1}(-u''v)dx=\int _{0}^{1}u'v'dx-\left.u'v\right|_{0}^{1}=\int _{0}^{1}u'v'dx\!\,$

因此變分形式為：尋找 $u\in V\!\,$ 使得

$a(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}e^{u}vdx=l(v)=0\!\,$ 對所有的 $v\in V\!\,$

定義分段線性基函式

考慮區間 $[0,1]\!\,$ 的一個劃分，

${\mathcal {\tau }}_{h}:0=x_{0}<x_{1}<\dots <x_{m+1}=1\!\,$.

將我們的有限元空間設為

$V_{h}=\{v\in V:\left.v\right|_{[x_{i-1},x_{i}]}\in {\mathcal {P}}_{1}([x_{i-1},x_{i}]),i=1,\dots ,m+1,v(0)=v(1)=0\}\!\,$.

對於 $V_{h}\!\,$ 的基底，我們使用帽子函式 $\{\phi _{j}\}_{j=1}^{m}\!\,$，即對於 $j=1,2,\ldots ,m\!\,$

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

因此，

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

因此離散公式變為：求解 $u_{h}\in V_{h}\!\,$ 使得

$a(u_{h},v_{h})=\int _{0}^{1}u_{h}'v_{h}'dx+\int _{0}^{1}e^{u_{h}}v_{h}dx=0,\forall v_{h}\in V_{h}\!\,$.

由於 $\{\phi _{j}\}_{j=1}^{m}\!\,$ 是 $V_{h}\!\,$ 的一個基，我們有

$u_{h}=\sum _{j=1}^{n}u_{hj}\phi _{j}\!\,$.

然後，我們得到以下等價的離散問題：求解 $u_{h}=(u_{h1},\ldots ,u_{hm})^{t}\!\,$ 使得

$a(u_{h},\phi _{i})=\sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0{\mbox{ for }}i=1,\dots ,m\!\,$ .

將問題改寫成矩陣形式

針對 $i=1,2,\ldots ,m\!\,$ 的等價離散問題

$\sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0\!\,$

可以改寫成以下矩陣形式

$\underbrace {\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&\ldots \\\ddots &\ddots &\ddots &\\&-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}\\&&-{\frac {1}{h}}&{\frac {2}{h}}\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{h1}\\\vdots \\\vdots \\u_{hm}\end{bmatrix}} _{U_{h}}+\underbrace {h{\begin{bmatrix}e^{u_{h1}}\\e^{u_{h2}}\\\vdots \\e^{u_{hm}}\end{bmatrix}}} _{F_{h}(U_{h})}\!\,$

第一個積分可以計算如下

${\begin{aligned}\int _{0}^{1}\phi _{j}'\phi _{i}'&={\begin{cases}{\frac {2}{h}}&{\mbox{for }}i=j\\-{\frac {1}{h}}&{\mbox{for }}|i-j|=1\\0&{\mbox{otherwise}}\end{cases}}\end{aligned}}\!\,$

第二個積分可以使用梯形法則近似，即

${\begin{aligned}\int _{x_{i-1}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)&=\int _{x_{i-1}}^{x_{i}}e^{u_{h}}\phi _{i}(x)+\int _{x_{i}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)\\&\approx \left({\frac {e^{u_{h}(x_{i-1})}\overbrace {\phi _{i}(x_{i-1})} ^{0}+e^{u_{h}(x_{i})}\phi _{i}(x_{i})}{2}}\right)h+\left({\frac {e^{u_{h}(x_{i})}\phi _{i}(x_{i})+e^{u_{h}(x_{i+1})}\overbrace {\phi _{i}(x_{i+1})} ^{0}}{2}}\right)h\\&=he^{u_{h}(x_{i})}\overbrace {\phi _{i}(x_{i})} ^{1}\\&=he^{u_{h}(x_{i})}\\&=he^{\sum _{j=1}^{m}u_{hj}\phi _{j}(x_{i})}\\&=he^{u_{hi}}\end{aligned}}\!\,$

注意到邊界條件規定 $u_{h0}=u_{h(m+1)}=0\!\,$。

問題 6

確定兩步格式的區域性精度階數和穩定性性質 $x_{i+2}-3x_{i+1}+2x_{i}=\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]\!\,$ 作為常微分方程 $x'(t)=f(t,x)\!\,$ 的近似方法。其收斂速度是多少？

解題 6

區域性精度階

請注意 $x_{i}\approx x(t_{i})\!\,$。另外，我們將均勻步長 $\Delta t\!\,$ 記作 h。因此，

$t_{i+1}=t_{i}+h\!\,$

$t_{i+2}=t_{i}+2h\!\,$

因此，給定方程可以寫成

$x(t_{i}+2h)-3x(t_{i}+h)+2x(t_{i})\approx h\left[{\frac {13}{12}}x'(t_{i}+2h)-{\frac {5}{3}}x'(t_{i}+h)-{\frac {5}{12}}x'(t_{i})\right]\!\,$

使用泰勒展開式展開左手邊

在 $t_{i}\!\,$ 處展開，我們得到

${\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&x(t_{i}+2h)&-3x(t_{i}+h)&2x(t_{i})&\Sigma \\\hline &&&&\\0&x(t_{i})&-3x(t_{i})&2x(t_{i})&0\\&&&&\\1&2x'(t_{i})h&-3x'(t_{i})h&0&-x'(t_{i})h\\&&&&\\2&{\frac {4}{2!}}x''(t_{i})h^{2}&-{\frac {3}{2!}}x''(t_{i})h^{2}&0&{\frac {1}{2}}x''(t_{i})h^{2}\\&&&&\\3&{\frac {8}{3!}}x'''(t_{i})h^{3}&-{\frac {3}{3!}}x'''(t_{i})h^{3}&0&{\frac {5}{6}}x'''(t_{i})h^{3}\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\&&&&\\\hline \end{array}}$

使用泰勒展開式展開右手邊

同樣地，關於 $t_{i}\!\,$ 展開得到

${\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&{\frac {13}{12}}hx'(t_{i}+2h)&-{\frac {5}{3}}hx'(t_{i}+h)&-{\frac {5}{12}}hx'(t_{i})&\Sigma \\\hline &&&&\\0&0&0&0&0\\&&&&\\1&{\frac {13}{12}}hx'(t_{i})&-{\frac {5}{3}}hx'(t_{i})&-{\frac {5}{12}}hx'(t_{i})&-1\cdot hx'(t_{i})\\&&&&\\2&{\frac {13}{12}}(2h)hx''(t_{i})&-{\frac {5}{3}}hhx''(t_{i})&0&{\frac {1}{2}}h^{2}x''(t_{i})\\&&&&\\3&{\frac {13}{12}}(2h)^{2}{\frac {hx'''(t_{i})}{2}}&-{\frac {5}{3}}h^{2}{\frac {hx'''(t_{i})}{2}}&0&{\frac {4}{3}}h^{3}x'''(t_{i})\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\\hline \end{array}}$

比較項以確定階數

對左右兩邊泰勒展開式求差，可以看出該二步方程是二階的，因為直到二階項為止都匹配上了。

$x_{i+2}-3x_{i+1}+2x_{i}-\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]={\mathcal {O}}(\Delta t^{3})\!\,$

注意，左邊的三階項與右邊的三階項不同。（${\frac {5}{6}}\neq {\frac {4}{3}}\!\,$)

穩定性條件

如果方程

$\lambda ^{2}-3\lambda +2=0\!\,$

滿足$|\lambda _{j}|\leq 1\!\,$，並且如果$|\lambda _{j}|=1\!\,$，則它必須是一個單根。

由於$\lambda ^{2}-3\lambda +2=(\lambda -1)(\lambda -2)=0\!\,$得到根1和2，因此這個二步方程是不穩定的。

收斂性

多步法收斂當且僅當它穩定且一致。我們的二步方程不穩定，因此不能保證收斂。