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

問題 4

考慮以下系統 $x=1+h{\frac {e^{-x^{2}}}{1+y^{2}}}{\mbox{,}}\qquad y=.5+h\arctan(x^{2}+y^{2})\!\,$.

問題 4a

證明如果引數 $h>0\!\,$ 選擇得足夠小，那麼該系統在某個矩形區域內有唯一解 $(x^{*},y^{*})\!\,$。

解答 4a

方程組可以用矩陣表示。

$f(x,y)={\begin{bmatrix}1+h{\frac {e^{-x^{2}}}{1+y^{2}}}\\\\.5+h\arctan(x^{2}+y^{2})\end{bmatrix}}\!\,$

$f(x,y)\!\,$ 的雅可比矩陣，$J(f)\!\,$，可以使用偏導數計算

$J(f)={\begin{bmatrix}{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)&{\frac {-h2ye^{-x^{2}}}{(1+y^{2})^{2}}}\\h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}\end{bmatrix}}\!\,$

如果 $h\!\,$ 足夠小，並且 $x,y\!\,$ 限制在有界區域 $B\!\,$ 內，

$\underbrace {\|J(f)\|} _{C}<1\!\,$

根據中值定理，對於 ${\vec {x_{1}}},{\vec {x_{2}}}\in B\!\,$，存在 ${\vec {\xi }}\!\,$ 使得

$f({\vec {x_{1}}})-f({\vec {x_{2}}})=J(f({\vec {\xi }}))({\vec {x_{1}}}-{\vec {x_{2}}})\!\,$

由於 $\|J(f)\|\!\,$ 在區域 $B\!\,$ 內是有界的，給定足夠小的 $h\!\,$

$\|f({\vec {x_{1}}})-f({\vec {x_{2}}})\|\leq C\|{\vec {x_{1}}}-{\vec {x_{2}}}\|\!\,$

因此，$f\!\,$ 是一個壓縮對映，根據壓縮對映定理，在矩形區域記憶體在唯一的固定點（解）。

問題 4b

推匯出求解該系統的固定點迭代方案，並證明其收斂性。$\!\,$

解答 4b

使用牛頓法

為了解決這個問題，我們可以使用牛頓法。事實上，我們想要找到以下函式的零點

$g(x,y)={\begin{bmatrix}x\\\\y\end{bmatrix}}-{\begin{bmatrix}1+h{\frac {e^{-x^{2}}}{1+y^{2}}}\\\\.5+h\arctan(x^{2}+y^{2})\end{bmatrix}}\!\,$

$g(x,y)\!\,$ 的雅可比矩陣，$J(g)\!\,$，可以使用偏導數計算

$J(g)={\begin{bmatrix}1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)&{\frac {-he^{-x^{2}}}{1+y^{2}}}\\h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}\end{bmatrix}}\!\,$

然後，求解這個線性方程組的牛頓法由以下公式給出

${\begin{bmatrix}x_{k+1}\\\\y_{k+1}\end{bmatrix}}={\begin{bmatrix}x_{k}\\\\y_{k}\end{bmatrix}}-\underbrace {{\frac {1}{det(J(g))}}{\begin{bmatrix}1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}&{\frac {he^{-x^{2}}}{1+y^{2}}}\\-h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)\end{bmatrix}}} _{J(g)^{-1}}g(x_{k},y_{k})\!\,$

透過驗證牛頓假設成立來證明收斂性

g 的雅可比矩陣是 Lipschitz 連續的

我們想證明 $J(g)\!\,$ 是一個 Lipschitz 函式。事實上，

${\begin{aligned}\|J(g)({\vec {x_{1}}})-J(g)({\vec {x_{2}}})\|&=\|(I-J(f))({\vec {x_{1}}})-(I-J(f))({\vec {x_{2}}})\|\\&=\|{\vec {x_{1}}}-{\vec {x_{2}}}-J(f){\vec {x_{1}}}+J(f){\vec {x_{2}}}\|\\&\leq \|{\vec {x_{1}}}-{\vec {x_{2}}}\|+\|J(f){\vec {x_{2}}}-J(f){\vec {x_{1}}}\|\end{aligned}}\!\,$

現在，利用 $J(f)\!\,$ 是 Lipschitz 連續的，我們得到

$\|J(g)({\vec {x_{1}}})-J(g)({\vec {x_{2}}})\|\leq (1+C)\|({\vec {x_{1}}})-({\vec {x_{2}}})\|\!\,$

g 的雅可比矩陣是可逆的

由於 $J(f)\!\,$ 是一個壓縮對映，$f\!\,$ 的雅可比矩陣的譜半徑小於 1，即

$\rho (J(f))<1\!\,$.

另一方面，我們知道 $J(g)\!\,$ 的特徵值為 $\lambda (J(g))=1-\lambda (J(f))\!\,$.

因此，可以得到 $det(I-(J(g)))\neq 0\!\,$，或者等效地 $J(g)\!\,$ 是可逆的。

g 的雅可比矩陣的逆矩陣是有界的

$\underbrace {{\frac {1}{det(J(g))}}{\begin{bmatrix}1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}&{\frac {he^{-x^{2}}}{1+y^{2}}}\\-h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)\end{bmatrix}}} _{J(g)^{-1}}\!\,$

由於 $J(g)^{-1}\!\,$ 存在，${\mbox{det}}(J(g))\neq 0\!\,$。給定一個有界區域（有界 $x,y\!\,$），上述矩陣的每個元素都是有界的。因此，範數是有界的。

(g 的雅可比矩陣)^-1(x_0) * g(x_0) 的範數是有界的

$\|J(g)^{-1}(x_{0})*g(x_{0})\|<\infty \!\,$，因為 $J(g)^{-1}\!\,$ 和 $g(x)\!\,$ 都是有界的。

然後，使用一個足夠好的近似值 $(x_{0},y_{0})\!\,$，我們可以得到牛頓法至少是二次收斂的，即：

$\|(x_{k-1},y_{k+1})-(x^{*},y^{*})\|\leq K\|(x_{k},y_{k})-(x^{*},y^{*})\|^{2}.\!\,$

問題 5a

概述用於數值求解初值問題 $y'=f(x,y){\mbox{, }}y(x_{0})=y_{0}\!\,$ 的 Adams-Bashforth 方法的推導。

解 5a

我們想要解以下初值問題：$y'=f(x,y){\mbox{, }}y(x_{0})=y_{0}\!\,$。

首先，我們將該表示式在 $[t_{n},t_{n+1}]\!\,$ 上積分，得到

$y(t_{n+1})=y(t_{n})+\int _{t_{n}}^{t_{n+1}}f(t,y(t))dt\!\,$,

為了近似右側的積分，我們使用一個適當的 p 次插值多項式來近似它的被積函式 $f(t,y(t))\!\,$，在 $t_{n},t_{n-1},...,t_{n-p}\!\,$ 上。

這個想法產生了 Adams-Bashforth 方法。

$y_{n+1}=y_{n}+\int _{t_{n}}^{t_{n-1}}\sum _{k=0}^{p}g(t_{n-k})l_{k}(t)dt\!\,$,

其中，$y_{n}\!\,$ 表示近似解，$g(t)\equiv f(t,y)\!\,$，以及 $l_{k}(t)\!\,$ 表示相關的拉格朗日多項式。

問題 5b

推導 Adams-Bashforth 公式 $y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\qquad \qquad (1)\!\,$

解答 5b

從 (a) 我們得到

$y_{i+1}=y_{i}+\int _{x_{i}}^{x_{i+1}}fdx\!\,$ 其中 $\int _{x_{i}}^{x_{i+1}}fdx\approx \int _{x_{i}}^{x_{i+1}}\left[{\frac {x-x_{i}}{x_{i-1}-x_{i}}}f_{i-1}+{\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}f_{i}\right]dx\!\,$

然後，如果我們令 $x=x_{i}+sh\!\,$，其中 h 是固定步長，我們可以得到

${\begin{aligned}dx&=hds\\x-x_{i}&=sh\\x-x_{i-1}&=(1+s)h\\x_{i}-x_{i-1}&=h\end{aligned}}$

$h\int _{0}^{1}\left[{\frac {sh}{-h}}f_{i-1}+{\frac {(1+s)h}{h}}f_{i}\right]ds=h\left[-{\frac {1}{2}}f_{i-1}+{\frac {3}{2}}f_{i}\right]\!\,$

所以，我們得到了所需的 Adams-Bashforth 方法

$y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\!\,$

問題 5c

分析方法 (1)。具體來說，求區域性截斷誤差，證明收斂性，並求收斂階。

解答 5c

使用泰勒展開式求區域性截斷誤差

注意 $y_{i}\approx y(t_{i})\!\,$。另外，用 h 表示均勻步長 $\Delta t\!\,$。因此，

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

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

因此，給定方程可以寫成

$y(t_{i}+h)-y(t_{i})\approx h\left[-{\frac {1}{2}}y'(t_{i}-h)+{\frac {3}{2}}y'(t_{i})\right]\!\,$

展開左側

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

${\begin{array}{|c|c|c|c|}{\mbox{Order}}&y(t_{i}+h)&y(t_{i})&\Sigma \\\hline &&&\\0&y(t_{i})&y(t_{i})&0\\&&&\\1&-y'(t_{i})h&0&-y'(t_{i})h\\&&&\\2&{\frac {1}{2!}}y''(t_{i})h^{2}&0&{\frac {1}{2}}y''(t_{i})h^{2}\\&&&\\3&-{\frac {1}{3!}}y'''(t_{i})h^{3}&0&-{\frac {1}{6}}y'''(t_{i})h^{3}\\&&&\\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}}$

收斂性證明：穩定性和一致性

一個方法收斂當且僅當它既穩定又一致。

穩定性

很容易證明該方法是零穩定，因為它滿足根條件。因此，它穩定。

一致性

截斷誤差是二階的。當 h 趨於零時，截斷誤差趨於零。所以該方法是一致的。

收斂階數

Dahlquist 原理：一致性 + 穩定性 = 收斂。收斂階數為 2。

問題 6

考慮問題 $-u''+u=f(x),\;\;0\leq x\leq 1,\;\;u(0)=u(1)=0.\qquad \qquad (2)$

問題 6a

給出 (2) 的變分公式，即用以下形式表達 (2)： $u\in H,\;\;B(x,y)=F(v),\;\;\forall v\in H\qquad \qquad (3)\!\,$ 定義空間 H、雙線性形式 B 和線性泛函 F，並說明 (2) 和 (3) 之間的關係。

解 6a

將 (2) 乘以一個測試函式，並使用分部積分法得到

$-\int _{0}^{1}u''vdx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx\!\,$

$\underbrace {\left.-u'v\right|_{0}^{1}} _{0}+\int _{0}^{1}u'v'dx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx\!\,$

因此，與問題 (2) 相關的弱形式或變分形式如下：找到 $u\in H\!\,$ 使得

$B(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx=F(v)\!\,$ 對於所有 $v\in H,\!\,$

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

問題 6b

設 $0=x_{0}<x_{1}<\cdots <x_{n}=1\!\,$ 是 $[0,1]\!\,$ 上的一個網格，其中 $h=\max _{j=0,1,\dots ,n-1}(x_{j+1}-x_{j})\!\,$，設 $V_{h}=\left\{u:u{\mbox{ continuous on }}[0,1],u|_{[x_{j},x_{j+1}]}{\mbox{ is linear for each }}j,u(0)=u(1)=0\right\}\!\,$. 定義有限元逼近，$u_{h}{\mbox{ to }}u\!\,$ 基於逼近空間 $V_{h}\!\,$。關於$\|u-u_{h}\|_{1}\!\,$ 在$H^{1}(0,1)\!\,$ 上的 Sobolev 範數誤差能說什麼？

解 6b

定義分段線性基

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

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

定義 u_h

由於$\{\phi _{j}\}_{j=1}^{n-1}\!\,$ 是$V_{h}\!\,$ 的基底，並且$u_{h}\in V_{h}\!\,$，我們有

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

離散問題

現在，我們可以寫下離散問題：找到 $u_{h}\in V_{h}\!\,$ 使得

$B(u_{h},v_{h})=F(v_{h})\!\,$ 對於所有 $v_{h}\in V_{h}.\!\,$

如果我們認為 $\{\phi _{j}\}_{j=1}^{n-1}\!\,$ 是 $V_{h}\!\,$ 的一個基底，以及雙線性形式 $B\!\,$ 和泛函 $F\!\,$ 的線性，我們得到等價的問題

找到 $u_{h}=(u_{h,1},\dots ,u_{h,{n-1}})\in \mathbb {R} ^{n-1}\!\,$ 使得

$\sum _{j=1}^{n-1}u_{h,j}\left\{\int _{0}^{1}\phi _{j}'\phi _{i}'dx+\int _{0}^{1}\phi _{j}\phi _{i}dx\right\}=\int _{0}^{1}f\phi _{i}dx,\quad i=1,\dots ,n-1.\!\,$

最後一個問題可以表述為矩陣問題，如下所示

找到 $u_{h}=(u_{h,1},\dots ,u_{h,{n-1}})\in \mathbb {R} ^{n-1}\!\,$ 使得

$Au_{h}=F,\!\,$

其中 $A_{ij}=\int _{0}^{1}\phi _{j}'\phi _{i}'dx+\int _{0}^{1}\phi _{j}\phi _{i}dx\!\,$ 且 $F_{j}=\int _{0}^{1}f\phi _{i}dx\!\,$.

邊界誤差

一般來說，我們可以使用 Cea 引理得到

$\|u-u_{h}\|_{1}\leq C\inf _{v_{h}\in V_{h}}\|u-v_{h}\|_{1}$

特別是，我們可以考慮$v_{h}\!\,$ 作為拉格朗日插值，記為 $v_{I}\!\,$。那麼，

$\|u-u_{h}\|_{1}\leq C\|u-v_{I}\|_{1}\leq Ch\|u\|_{H^{2}(0,1)}$.

很容易證明有限元解在節點上是精確的。那麼它就與拉格朗日插值一致，我們有以下的點估計

$\|u(x)-u_{h}(x)\|_{L^{\infty }([x_{i-1},x_{i}])}\leq \max _{x\in [x_{i-1},x_{i}]}{\frac {u^{(2)}(x)}{(2)!}}\left({\frac {h}{2}}\right)^{2}$

問題 6c

推匯出 $\|u-u_{h}\|_{0}\!\,$ 的估計，即 $L_{2}(0,1)\!\,$ 中的誤差。提示：令 w 為以下方程的解 (#) :${\begin{cases}-w''+w=u-u_{h},\\w(0)=w(1)=0.\end{cases}}$ 我們用變分方法來刻畫 $w\!\,$: $w\in H_{0}^{1},\;\;B(w,v)=\int (u-u_{h})vdx,\forall v\in H_{0}^{1}\!\,$. 令 $v=u-u_{h}\!\,$，得到 $B(w,u-u_{h})=\int (u-u_{h})^{2}dx=\|u-u_{h}\|_{L_{2}}^{2}.\qquad \qquad (4)\!\,$ 使用公式 (4) 估計 $\|u-u_{h}\|_{L_{2}}\!\,$.

解 6c

雙線性形式的連續性

${\begin{aligned}B(u,v)&=\int uv+\int u'v'\\&\leq \|u\|_{0}\|v\|_{0}+\|u'\|_{0}\|v'\|_{0}{\mbox{ (Cauchy-Schwarz in L2) }}\\&\leq (\|u\|_{0}^{2}+\|u'\|_{0}^{2})^{\frac {1}{2}}(\|v\|_{0}^{2}+\|v'\|^{2})^{\frac {1}{2}}{\mbox{ ( Cauchy-Schwarz in R2 ) }}\\&=\|u\|_{1}\cdot \|v\|_{1}\end{aligned}}\!\,$

誤差的正交性

$B(u-u_{h},v_{h})=0,\quad \forall v_{h}\in V_{h}\!\,$.

w 的 L2 範數的界

${\begin{aligned}\|w\|_{0}^{2}&\leq \|w\|_{1}^{2}\\&=B(w,w)\\&=\int (u-u_{h})w\\&\leq \|u-u_{h}\|_{0}\|w\|_{0}{\mbox{ (Cauchy-Schwarz in L2 ) }}\end{aligned}}\!\,$

因此，

$(*)\qquad \|w\|_{0}\leq \|u-u_{h}\|_{0}\!\,$

w 的 L2 範數的界

從 $(\#)\!\,$，我們有

$-w''+w=u-u_{h}\!\,$

那麼，

${\begin{aligned}\|w''\|_{0}&\leq \|w\|_{0}+\|u-u_{h}\|_{0}{\mbox{ (triangle inequality) }}\\&\leq \|u-u_{h}\|_{0}+\|u-u_{h}\|_{0}{\mbox{ (by (*) ) }}\\&=2\|u-u_{h}\|_{0}\end{aligned}}\!\,$

L2 誤差界限

${\begin{aligned}\|u-u_{h}\|_{L^{2}}^{2}&=B(w,u-u_{h}){\mbox{ ( from equation (4) ) }}\\&=B(w,u-u_{h})-\underbrace {B(w_{h},u-u_{h})} _{0}\\&=B(w-w_{h},u-u_{h})\\&\leq \|w-w_{h}\|_{H^{1}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}{\mbox{ (Continuity of Bilinear Form) }}\\&\leq Ch\|w\|_{H^{2}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}{\mbox{ (Cea Lemma and Polynomial Interpolation Error) }}\end{aligned}}$

最後，從 (#)，我們有 $\|w\|_{H^{2}(0,1)}\leq C\|u-u_{h}\|_{L_{2}(0,1)}\!\,$。然後，

$\|u-u_{h}\|_{L^{2}(0,1)}^{2}\leq Ch\|u-u_{h}\|_{L_{2}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}\!\,$,

或者等效地，

$\|u-u_{h}\|_{L^{2}(0,1)}\leq Ch\|u-u_{h}\|_{H^{1}(0,1)}\leq Ch^{2}\|u\|_{H^{2}(0,1)}\!\,$.

問題 6d

假設 $\{\phi _{1}^{h},\dots ,\phi _{N_{h}}^{h}\}\!\,$ 是 $V_{h}{\mbox{ where }}N_{h}=\dim V_{h}{\mbox{, so }}u_{h}=\sum _{j=1}^{N_{h}}c_{j}^{h}\phi _{j}^{h}{\mbox{, for appropriate coefficients }}c_{j}^{h}.\!\,$ 的一個基底。證明 $\|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-C^{T}AC\!\,$ 其中 $C=[c_{1}^{h},\dots ,c_{N_{h}}^{h}]^{T}{\mbox{ and }}A\!\,$ 是剛度矩陣。

解 6d

我們知道

${\begin{aligned}\|u-u_{h}\|_{1}^{2}&=\langle u-u_{h},u-u_{h}\rangle _{H^{1}(0,1)}\\&=\langle u-u_{h},u\rangle _{H^{1}(0,1)}-\underbrace {\langle u-u_{h},u_{h}\rangle _{H^{1}(0,1)}} _{0}\\&=\|u\|_{H^{1}(0,1)}^{2}-\langle u_{h},u\rangle _{H^{1}(0,1)}\\&=\|u\|_{H^{1}(0,1)}^{2}-\|u_{h}\|_{H^{1}(0,1)}^{2}\end{aligned}}$

其中最後兩行的替換來自於誤差的正交性。

現在，$\|u_{h}\|_{H^{1}(0,1)}^{2}=\sum _{j=1}^{n-1}\sum _{i=1}^{n-1}u_{h,j}u_{h,i}\left(\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\int _{0}^{1}\phi _{i}\phi _{j}dx\right)=\sum _{j=1}^{n-1}\sum _{i=1}^{n-1}u_{h,j}A_{ij}u_{h,i}=C^{t}AC.\!\,$

然後，我們得到

$\|u-u_{h}\|_{1}^{2}=\|u\|_{H^{1}(0,1)}^{2}-C^{t}AC.\!\,$