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

問題 5a

說明牛頓法，用於近似求解

f(x)=0\!\,

其中 $f(x)\!\,$ 是實變數 $x\!\,$ 的實值函式

解答 5a

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

問題 5b

說明並證明該方法的收斂結果。

解答 5b

${\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,$

問題 5c

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

解答 5c

區域性收斂的典型階數是二次。

將牛頓法視為一個不動點迭代，即

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

那麼

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

$g'(x_{*})=0\!\,$

將 $g(x_{k})\!\,$ 在 $x_{*}\!\,$ 處展開得到誤差表示式

$\underbrace {g(x_{k})} _{x_{k+1}}=\underbrace {g(x_{*})} _{x_{*}}+\underbrace {g'(x_{*})} _{0}e_{k}+{\frac {g''(x_{*})}{2}}e_{k}^{2}+{\frac {g'''(\xi )}{6}}e_{k}^{3}\!\,$

注意，如果 $g''(x_{*})=0\!\,$ ，那麼我們得到比二次收斂更快的收斂速度。

問題 6

考慮邊界值問題

{\begin{cases}-u''(x)+u(x)=f(x),0\leq x\leq 1\\u'(0)=2,u(1)=0\end{cases}}\qquad (1)\!\,

問題 6a

推匯出 (1) 的變分公式。

解答 6a

求 $u\in H\!\,$ 使得對於所有 $v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,$

$\underbrace {\int _{0}^{1}u'v'dx+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}fv-2v(0)} _{f(v)}\!\,$

問題 6b

有限元近似指的是什麼？ $u_{h}\!\,$ 對 $u\!\,$

解 6b

令 $P=\{x_{i}\}_{i=0}^{N}\!\,$ 是 $[0,1]\!\,$ 的一個劃分。選擇一個合適的離散子空間 $V_{h}\!\,$ 和基函式 $\{\phi _{i}\}_{i=0}^{N}\!\,$ 。然後

$u_{h}=\sum _{i=0}^{N}u_{hi}\phi _{i}\!\,$

係數 $u_{hi}\!\,$ 可以透過求解以下方程組來找到

對於 $j=0,1,\ldots ,N\!\,$

$\sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\sum _{i=0}^{N}u_{hi}\int _{0}^{1}\phi _{i}\phi _{j}dx=\int _{0}^{1}f\phi _{j}-2\phi _{j}(0)\!\,$

問題 6c

給出並證明對以下內容的估計

$\|u-u_{h}\|_{1}\equiv \left(\int _{0}^{1}|u(x)-u_{h}(x)|^{2}dx+\int _{0}^{1}|u'(x)-u_{h}'(x)|^{2}dx\right)^{\frac {1}{2}}\!\,$

解 6c

Cea 引理

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

特別是選擇 $v_{I}\!\,$ 為 $u\!\,$ 的線性插值。

然後,

$\|u-u_{h}\|\leq C\|u''\|_{\infty }h\!\,$

解 6c 的另一種解法

令 $\{x_{k}\}_{0}^{n}$ 為 $[0,1]$ 的離散網格，步長為 $h$ 。考慮以下積分

$\int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx$ .

對於某個 $\xi _{k}\in [x_{k},x_{k+1}]$ ， $u(x)-u_{h}(x)=u'(\xi _{k})*h$ 因為 $u_{h}$ 在此區間上只是一個線性插值。因此

$\int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx=\int _{x_{k}}^{x_{k+1}}h^{2}u'(\xi _{k})^{2}dx=h^{3}u'(\xi _{k})^{2}\leq h^{3}||u'||_{\infty }$ .

類似地，我們可以用 $h^{3}||u''||_{\infty }$ 對導數誤差的 $L_{2}(x_{k},x_{k}+h)$ 範數進行界定。當有 $n=1/h$ 個這樣的區間時，我們有

$\ ||u-u_{h}\||^{2}\leq 2nh^{3}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2})=2h^{2}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2}).$

問題 6d

證明公式

$\|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\!\,$

解答 6d

${\begin{aligned}\underbrace {a(u-u_{h},u-u_{h})} _{\|u-u_{h}\|_{1}^{2}}+2\underbrace {a(u-u_{h},u_{h})} _{0}&=a(u,u)-2a(u,u_{h})+a(u_{h},u_{h})+2a(u,u_{h})-2a(u_{h},u_{h})\\&=a(u,u)-a(u_{h},u_{h})\\&=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\end{aligned}}\!\,$

問題 7

考慮初值問題

y'=f(t,y),\quad y(t_{0})=y_{0}\!\,

其中 $f\!\,$ 滿足 Lipschitz 條件

|f(t,y)-f(t,z)|\leq L|y-z|\!\,

對於所有 $t,y,z\!\,$ 。用於求解此問題的稱為中點規則的數值方法定義為

y_{n+1}=y_{n-1}+2hf(t_{n},y_{n})\!\,

其中 $h\!\,$ 是時間步長，而 $y_{n}\approx y(t_{n})\!\,$ 對於 $t_{n}=t_{0}+nh\!\,$ 。這裡 $y_{0}\!\,$ 是給定的，而 $y_{1}\!\,$ 假設用其他方法計算。

問題 7a

假設問題在一個有限區間 $t_{0}\leq t\leq b\!\,$ 上提出，其中 $h={\frac {(b-t_{0})}{M}}\!\,$ 。直接證明，即不引用任何主要結果，中點法是穩定的。也就是說，證明如果 ${\hat {y_{0}}}\!\,$ 和 ${\hat {y_{1}}}\!\,$ 滿足

|y_{0}-{\hat {y_{0}}}|\leq \epsilon ,\quad |y_{1}-{\hat {y_{1}}}|\leq \epsilon \!\,

那麼存在一個常數 $C\!\,$ 與 $h\!\,$ 無關，使得

|y_{n}-{\hat {y_{n}}}|\leq C\epsilon \!\,

對於 $0\leq n\leq M\!\,$

解 7a

${\begin{aligned}y_{n+1}&=y_{n-1}+2hf(t_{n},y_{n})\\{\hat {y}}_{n+1}&={\hat {y}}_{n-1}+2hf(t_{n},{\hat {y}}_{n})\end{aligned}}$

將兩個方程相減，令 $e_{n}\equiv y_{n}-{\hat {y}}_{n}\!\,$ ，並應用Lipschitz性質，得到：

${\begin{aligned}e_{n+1}&\leq e_{n-1}+2hLe_{n}\\&\leq (1+2hL)\max\{e_{n},e_{n-1}\}\end{aligned}}\!\,$

因此：

${\begin{aligned}e_{n}&\leq (1+2hL)^{n-1}\epsilon \\&\leq (1+2hL)^{n}\epsilon \\&\leq e^{2Lhn}\epsilon \\&\leq e^{2L(t_{n}-t_{0})}\epsilon \end{aligned}}\!\,$