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

問題 4

設 $\mathbf {f:} \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}\!\,$ ，假設 $\mathbf {f} (x^{*})=0\!\,$ ，並假設 $\mathbf {f'} (x^{*})\!\,$ 是非奇異的。考慮以下迭代

$x_{k+1}=x_{k}-B_{k}^{-1}\mathbf {f} (x_{k}),\qquad (k\geq 0)\!\,$

問題 4a

推匯出以下關於 $e_{k+1}=x_{k+1}-x^{*}\!\,$ 的誤差方程

$e_{k+1}=B_{k}^{-1}\left((B_{k}-\mathbf {f'} (x^{*}))e_{k}-\int _{0}^{1}(\mathbf {f'} (sx_{k}+(1-s)x^{*})-\mathbf {f'} (x^{*}))e_{k}\,ds\right)\!\,$

解答 4a

注意以下恆等式

F(x)-F(y)=\int _{0}^{1}F'(sx+(1-s)y)(x-y)ds\qquad (*)\!\,

誤差 $e_{k+1}\!\,$ 由下式給出

${\begin{aligned}e_{k+1}&=x_{k+1}-x_{*}\\&=\underbrace {x_{k}-x_{*}} _{e_{k}}-B_{k}^{-1}f(x_{k})\\&=e_{k}-B_{k}^{-1}(f(x_{k})-\underbrace {f(x_{*})} _{0})\\&=B_{k}^{-1}\left\{(B_{k}-f'(x_{*}))e_{k}-\int _{0}^{1}\left[f'(sx_{k}+(1-s)x_{*})-f'(x_{*})\right]e_{k}ds\right\}\\\end{aligned}}$

問題 4b

令 $B_{k}=B\in \mathbb {R} ^{n\times n}\!\,$ 是一個固定矩陣。找出關於 B 的條件，以保證區域性收斂。你期望的收斂速度是多少，為什麼？

解 4b

假設 $B\!\,$ 是可逆的， $\|B-f'(x_{*})\|\!\,$ 是有界的，並且 $f'\!\,$ 是 Lipschitz 連續的。

${\begin{aligned}\|e_{k+1}\|&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|\|e_{k}\|-\int _{0}^{1}\underbrace {\|f'(sx_{k}+(1-s)x_{*})-f'(x_{*})\|} _{\leq L\|sx_{k}+(1-s)x_{*}-x_{*}\|}\|e_{k}\|ds\right\}\\&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|\|e_{k}\|-\int _{0}^{1}L\|e_{k}\|^{2}sds\right\}\\&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|-{\frac {L}{2}}\|e_{k}\|\right\}\|e_{k}\|\end{aligned}}$

這意味著區域性超線性收斂。

問題 4c

找到關於 $\|B_{k}-\mathbf {f'} (x_{k})\|\!\,$ 的充分條件，使收斂變為超線性。選擇哪個 $B_{k}\!\,$ 對應於牛頓法，你期望什麼收斂速度？

解 4c

超線性收斂

${\frac {\|e_{k+1}\|}{\|e_{k}\|}}\rightarrow 0\!\,$ 當 $k\rightarrow \infty \!\,$

找到超線性收斂的條件

從部分 (b)

${\frac {\|e_{k+1}\|}{\|e_{k}\|}}\leq \|B_{k}^{-1}\|\{\|B_{k}-f'(x_{*})\|-{\frac {L}{2}}\|e_{k}\|\}\!\,$

由於 $\|e_{k}\|\rightarrow 0{\mbox{ as }}k\rightarrow \infty \!\,$ ，如果

$\|B_{k}-f'(x_{*})\|\rightarrow 0\!\,$

當 $k\rightarrow 0\!\,$ ，我們有超線性收斂，即

$B_{k}=f'(x_{k}){\mbox{ Newton Iteration form}}\!\,$

問題 5

令 $f(t,y)\!\,$ 關於 $y$ 一致 Lipschitz。令 $y(t)\!\,$ 是以下初值問題的解： $y'=f(t,y),\;y(0)=y_{0}\!\,$ 。考慮梯形法

$(1)\qquad y_{i+1}=y_{i}+{h \over 2}\left(f(t_{i},y_{i})+f(t_{i+1},y_{i+1})\right),\qquad (i\geq 0)\!\,$ .

問題 5a

找到關於步長 $h\!\,$ 的條件，以確保 (1) 可以關於 $y_{i+1}\!\,$ 唯一求解。

解 5a

該隱式方法可以看作是一個不動點迭代

$y_{i+1}=\underbrace {y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},y_{i+1}))} _{g(y_{i+1})}\!\,$

我們需要 $\left|{\frac {\partial g(y_{i+1})}{\partial y_{i+1}}}\right|<1\!\,$

這意味著

$h<{\frac {2}{\left|{\frac {\partial f(t_{i+1},y_{i+1})}{\partial y_{i+1}}}\right|}}\!\,$

問題 5b

定義區域性截斷誤差並進行估計。檢查 $f\!\,$ 所需的額外正則性以進行此估計。

解決方案 5b

重寫 (1) 並用 $y_{k}{\mbox{ with }}y(t_{k}){\mbox{ and }}f(t_{k},y_{k}){\mbox{ with }}y'(t_{k})\!\,$ 代替，我們得到階為 p 的一致性公式

$y(t_{i+1})-y(t_{i})-{h \over 2}y'(t_{i})-{h \over 2}y(t_{i+1})={\mathcal {O}}(h^{p+1})\!\,$

對於均勻步長 h

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

關於 $t_{i}\!\,$ 的泰勒級數展開給出

問題 5c

證明 (1) 的全域性誤差估計

解決方案 5c

問題 6

考慮二點邊值問題

$(2)\qquad -au''+bu=f(x),\quad 0<x<1,\qquad u(0)=u_{0},\,u(1)=u_{1}\!\,$ ,

其中 $a,b>0\!\,$ 為常數， $f\in C[0,1]\!\,$ 。令 ${\mathcal {P}}=\{x_{i}\}_{i=0}^{n+1}\!\,$ 是 [0,1] 的均勻劃分，其網格大小為 $h\!\,$ 。

問題 6a

使用中心有限差分法對 (2) 進行離散化。將系統寫成

$A\mathbf {U} =\mathbf {F} \!\,$

並確定 $A\in \mathbb {R} ^{n\times n}{\mbox{ and }}\mathbf {U} ,\mathbf {F} \in \mathbb {R} ^{n}\!\,$ 。證明 A 是非奇異的。

解答 6a

使用泰勒展開式，我們可以近似二階導數如下

$u''(x)={\frac {u(x+h)-2u(x)+u(x-h)}{h^{2}}}\!\,$

我們可以透過將初始條件 $u(0)=u_{0},u(1)=u_{1}\!\,$ 代入 $U_{1}\!\,$ 和 $U_{n}\!\,$ 的方程中，從 n+2 個方程中消去兩個方程。

然後我們有系統

$\underbrace {\begin{bmatrix}{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&&&&\\-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&&&\\&-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&\\&&\ddots &\ddots &\ddots &\\&&&&-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}U_{1}\\U_{2}\\U_{3}\\\vdots \\U_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}f(x_{1})+{\frac {a}{h^{2}}}u_{0}\\f(x_{2})\\f(x_{3})\\\vdots \\f(x_{n})+{\frac {a}{h^{2}}}u_{1}\end{bmatrix}} _{F}\!\,$

矩陣 $A\!\,$ 是非奇異的，因為它是對角佔優的。

問題 6b

定義截斷誤差，並根據 $h\!\,$ 推匯出該方法的誤差界限。不加證明地給出如下形式的誤差估計

$\max _{1\leq i\leq n}|u(x_{i})-U_{i}|\leq Ch^{s}\!\,$

並指定階數 s。

解答 6b

區域性截斷誤差

$LTE={\frac {u(x_{i}+h)+u(x_{i}-h)-2u(x_{i})}{h^{2}}}-u''(x_{i})={\frac {u^{(4)}(\xi )}{12}}h^{2}\!\,$

區域性截斷誤差的界限

${\frac {1}{12}}\|u^{(4)}\|_{\infty }h^{2}\!\,$

推匯出最大誤差的界限

令 $L=-a\partial _{xx}+b\!\,$ ， $L_{h}=A\!\,$ ，以及 $R_{h}\!\,$ 是區域性截斷誤差。

然後

${\begin{aligned}Lu&=f\\L_{h}u&=f+R_{h}\\L_{h}U&=f\end{aligned}}\!\,$

減去最後兩個方程得到

$L_{h}(u-U)=R_{h}\!\,$

因此，

$\|u-U\|_{\infty }\leq \|L_{h}^{-1}\|\|R_{h}\|\!\,$

$\|u-U\|_{\infty }\leq Ch^{2}\!\,$ ，也就是說誤差是二階的。

問題 6c

證明以下離散單調性：如果 $\mathbf {U} _{i}\!\,$ 是對應於強迫 $f_{i}\!\,$ 的解，對於 $i=1,2\!\,$ ，並且 $f_{1}\leq f_{2}\!\,$ ，則 $\mathbf {U} _{1}\leq \mathbf {U} _{2}\!\,$ 按成分排列。