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

問題 4

考慮用隱式方法求解非線性常微分方程組問題 $y'=f(t,y)\!\,$ 第 $n\!\,$ 步包括求解未知數 $y\!\,$，其形式為非線性代數方程組 $y=\alpha hf(t_{n},y)+g_{n-1}\quad (1)\!\,$ 其中 $g_{n-1}\in \mathbb {R} ^{n}\!\,$ 已知，$\alpha >0\!\,$ 且 $h\!\,$ 是步長。令 $f\in C^{1}\!\,$

問題 4a

將 $(1)\!\,$ 寫成不動點迭代，並找到 $h\!\,$ 和 $f(t_{n},y)\!\,$ 的條件，使得該迭代在

ononon

解答 4a

不動點迭代

等式 $(1)\!\,$ 非常適合用固定點迭代法求解。

$y_{n}^{j+1}=\underbrace {\alpha hf(t_{n},y_{n}^{j})+g_{n-1}} _{\phi (y_{n}^{j})}\!\,$

注意，等式右側僅是 $y_{n}^{j}\!\,$ 的函式，因為 $\alpha ,h,t_{n},g_{n-1}\!\,$ 在求解固定點 $y_{n}^{*}\!\,$ 時是固定的，其中 $\phi (y_{n}^{*})=y_{n}^{*}\!\,$

還要注意，$j\!\,$ 是固定點迭代的索引。

區域性收斂條件

當 $\phi \!\,$ 的雅可比矩陣的範數小於 1 時，固定點迭代將收斂，即

$\|D(\phi )\|<1\!\,$

由於 $\|D(\phi )\|=\|\alpha hD(f)\|\!\,$，我們等效地得到條件

$\|D(f)\|<{\frac {1}{\alpha h}}\!\,$

問題 4b

寫出$(1)\!\,$ 的牛頓迭代，並給出關於$h\!\,$ 和 $f(t_{n},y)\!\,$ 的條件，以保證該迭代的區域性收斂。給出關於$f\!\,$ 的精確附加假設，以保證二次收斂。

解 4b

牛頓迭代

牛頓迭代用來求解$\psi (y)=0\!\,$，迭代公式為

$y_{i+1}=y_{i}-D(\psi (y_{i}))^{-1}\psi (y_{i})\!\,$

設 $\psi (y)=y-\phi (y)\!\,$

區域性收斂條件

如果$D(\psi (y))^{-1}\!\,$ 存在，即$D(\psi (y))\!\,$ 可逆，或等價地是非奇異的，那麼區域性收斂就得到了保證。

注意

$D(\psi (y))=I-D(\phi (y))\!\,$

二次收斂的條件

如果$D(\psi (y))\!\,$ 是 Lipschitz 連續的，那麼我們有二次收斂，並且$\psi (y)\!\,$ 在根的鄰域內是兩次連續可微的。

問題 5

這個問題是關於為求解 ODE 選擇特定的單步法和特定的多步法。 $y'=f(t,y)\!\,$

問題 5a

寫出梯形法，定義其區域性截斷誤差並估計它。

解 5a

梯形方法（隱式，Adams-Moulton）

$y_{n+1}=y_{n}+{\tfrac {1}{2}}h{\big (}f(t_{n+1},y_{n+1})+f(t_{n},y_{n}){\big )}\!\,$

定義區域性截斷誤差

區域性截斷誤差如下所示

${\mbox{error}}=(y(t_{n+1})-y(t_{n}))-{\tfrac {1}{2}}h{\big (}f(t_{n+1},y(t_{n+1}))+f(t_{n},y_{n}){\big )}\!\,$

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

注意 $y_{i}\approx y(t_{i})\!\,$. 均勻步長為 $h\!\,$. 因此，

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

因此，給定方程可以寫成

$y(t_{i}+h)-y(t_{i})\approx {\frac {1}{2}}h(y'(t_{i}+h)+y'(t_{n}))\!\,$

展開左邊

關於 $t_{n}\!\,$ 展開，我們得到

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

展開右手邊

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

${\begin{array}{|c|c|c|c|}{\mbox{Order }}h&{\frac {1}{2}}hy'(t_{n}+h)&{\frac {1}{2}}hy'(t_{n})&\Sigma \\\hline &&&\\0&0&0&0\\&&&\\1&{\frac {1}{2}}h\cdot y'(t_{n})&{\frac {1}{2}}hy'(t_{n})&y'(t_{n})h\\&&&\\2&{\frac {1}{2}}h\cdot y''(t_{n})h&0&{\frac {1}{2}}y''(t_{n})h^{2}\\&&&\\3&{\frac {1}{2}}h\cdot {\frac {y'''}{2}}(t_{n})h^{2}&0&{\frac {y'''}{4}}(t_{n})h^{3}\\&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})\\\hline \end{array}}$

計算區域性截斷誤差

由於 $h\!\,$ 的 3 階項不一致 (${\frac {y'''(t_{n})}{6}}h^{3}\neq {\frac {y'''(t_{n})}{4}}h^{3}\!\,$)，誤差為 $h^{2}\!\,$ 階。

問題 5b

證明以下多步法的截斷誤差與 (a) 中的截斷誤差同階 $y_{n+1}=2y_{n}-y_{n-1}-hf(t_{n-1},y_{n-1})+hf(t_{n},y_{n})\!\,$

解 5b

我們需要證明 $y(t_{n+1})-2y(t_{n})+y(t_{n-1})+hy'(t_{n-1})-hy'(t_{n})={\mathcal {O}}(h^{3})\!\,$

再次注意，${\begin{aligned}t_{n+1}&=t_{n}+h\\t_{n-1}&=t_{n}-h\end{aligned}}\!\,$

${\begin{array}{|c|c|c|c|c|c|c|}{\mbox{Order of }}h&y(t_{n}+h)&-2y(t_{n})&y(t_{n}-h)&hy'(t_{n}-h)&-hy'(t_{n})&\Sigma \\\hline 0&y(t_{n})&-2y(t_{n})&y(t_{n})&0&0&0\\&&&&&&\\1&y'(t_{n})h&0&-y'(t_{n})h&y'(t_{n})h&-y'(t_{n})&0\\&&&&&&\\2&{\frac {1}{2}}y''(t_{n})h^{2}&0&{\frac {1}{2}}y''(t_{n})h^{2}&-y''(t_{n})h^{2}&0&0\\&&&&&&\\3&{\frac {1}{6}}y'''(t_{n})h^{3}&0&-{\frac {1}{6}}y'''(t_{n})h^{3}&{\frac {1}{2}}y'''(t_{n})h^{3}&0&{\frac {1}{2}}y'''(t_{n})h^{3}\\&&&&&&\\\hline \end{array}}$

因此，該方法也是二階一致的。

問題 5c

對於這兩種方法，我們可以說些什麼關於全域性收斂速度？證明您的結論。

解決方案 5c

梯形法是穩定的，因為它滿足根條件。（特徵方程的根為 1，並且只有一個簡單根。）

第二種方法不穩定，因為特徵方程有一個 1 的二重根。

梯形法和第二種方法都與 $h^{2}\!\,$ 一致。

注意，收斂發生當且僅當方法既穩定又一致。

因此，梯形法一般情況下會收斂，而第二種方法不會。mkmkmkmlmklml

問題 6

考慮邊界值問題 $L(u)=-u''+bu=f,\;\;x\in I\equiv [0,1],\;\;u(0)=u(1)=0\qquad (2)\!\,$ 其中 $b\geq 0\!\,$ 是常數。 令 $\{0=x_{0}<x_{1}<\dots <x_{n}=1\}\!\,$ 是一個具有均勻網格間距 $h\!\,$ 的網格。 令 $V_{h}=\{v\in C[0,1]:\left.v\right|_{[x_{i-1},x_{i}]}{\mbox{ is linear for each i, }}v(0)=v(1)=0\}\!\,$ 為相應的有限元空間，令 $u_{h}=R_{h}(u)\!\,$ 為 (2) 的相應有限元解。 注意， $R_{h}\!\,$ 是一個投影運算元，即瑞茲投影，投影到有限維空間 $V_{h}\!\,$ 上，該空間相對於由問題 (2) 誘導的元素標量積 $a(\cdot ,\cdot )\!\,$。

問題 6a

令 $|\cdot |_{1}\!\,$ 為 $H^{1}\!\,$-半範數，即對所有 $v\in H_{0}^{1}(I)\!\,$，有 $|v|_{1}^{2}=\int _{I}|v'|^{2}\!\,$。求常數 $\Lambda \!\,$，用引數 $b\!\,$ 表示，使得 $|u_{h}|_{1}\leq \Lambda |u|_{1}\!\,$ 提示：回顧 Poincaré 不等式 $\|v\|_{0}\leq {\frac {1}{2}}|v|_{1}\!\,$ 對所有 $v\in H_{0}^{1}(I)\!\,$ 成立，其中 $\|\cdot \|_{0}\!\,$ 表示 $L^{2}\!\,$-範數

解 6a

弱形式

對所有 $v\in V\!\,$，用分部積分得到

$\int u'v'+b\int uv=\int fv\!\,$

具體來說，

$\int u'u_{h}'+b\int uu_{h}=\int fu_{h}\!\,$

離散形式（有限元公式）

類似地，有限元公式是找到$u_{h}\in V_{h}\!\,$ 使得對於所有 $v_{h}\in V_{h}\!\,$

$\int u_{h}'v_{h}'+b\int u_{h}v_{h}=\int fv_{h}\!\,$

具體來說，

$\int u_{h}'u_{h}'+b\int u_{h}u_{h}=\int fu_{h}\!\,$

等式兩邊並應用不等式

${\begin{aligned}\int _{0}^{1}u_{h}'u_{h}'+b\int _{0}^{1}u_{h}u_{h}&=\int _{0}^{1}u'u_{h}'+b\int _{0}^{1}uu_{h}\\&\leq |u|_{1}|u_{h}|_{1}+b\|u\|_{0}\|u_{h}\|_{0}{\mbox{ Cauchy-Schwartz}}\\&\leq |u|_{1}|u_{h}|_{1}+b{\frac {1}{2}}|u|_{1}{\frac {1}{2}}|u_{h}|_{1}{\mbox{ Poincare}}\\&=|u_{h}|_{1}(1+{\frac {b}{4}})|u|_{1}\end{aligned}}$

因此我們有：

${\begin{aligned}|u_{h}|_{1}^{2}\leq |u_{h}|_{1}^{2}+b\|u_{h}\|_{0}^{2}&\leq |u_{h}|_{1}(1+{\frac {b}{4}})|u|_{1}\\|u_{h}|_{1}^{2}&\leq |u_{h}|_{1}(1+{\frac {b}{4}})|u|_{1}\\|u_{h}|_{1}&\leq (1+{\frac {b}{4}})|u|_{1}\end{aligned}}$

問題 6b

如果 $I_{h}u\in V_{h}\!\,$ 是 $u\!\,$ 的拉格朗日插值，證明 $R_{h}(I_{h}u)=I_{h}u\!\,$。推斷 $|u_{h}-I_{h}u|_{1}\leq \Lambda |u-I_{h}u|_{1}\!\,$

解答 6b

證明等式

對於所有 $v\in H_{0}^{1}(0,1)\!\,$

$a(u,v)=\int u'v'dx+b\int uvdx=\int fv\!\,$

特別地，對於所有 $v_{h}\in V_{h}\!\,$

$a(u,v_{h})=\int u'v_{h}'dx+b\int uv_{h}dx=\int fv_{h}\quad \quad (1)\!\,$

能量標積的離散形式對所有 $u_{h},v_{h}\in V_{h}\!\,$

$a(u_{h},v_{h})=\int u_{h}'v_{h}'dx+b\int u_{h}v_{h}dx=\int fv_{h}\quad \quad (2)\!\,$

從公式(1)中減去公式(2), 我們有

$a(u-u_{h},v_{h})=0\!\,$

令 $R_{h}(I_{h}u)={\overline {u_{h}}}\in V_{h}\!\,$. 注意根據假設 $I_{h}u\in V_{h}\!\,$. 然後,

$a(I_{h}u-{\overline {u_{h}}},I_{h}u-{\overline {u_{h}}})=0\!\,$

根據橢圓性,

$0=a(I_{h}u-{\overline {u_{h}}},I_{h}u-{\overline {u_{h}}})\geq \alpha \|I_{h}u-{\overline {u_{h}}}\|^{2}\!\,$

這意味著

$I_{h}u-{\overline {u_{h}}}=0\!\,$

即

$I_{h}u={\overline {u_{h}}}\!\,$

推匯出不等式

因此我們有

$R_{h}(u-I_{h}u)=u_{h}-I_{h}u\!\,$

與 (a) 部分類似，我們有

$|u_{h}-I_{h}u|_{1}\leq \Lambda |u-I_{h}u|_{1}\!\,$

問題 6c

利用 (b) 推匯出誤差估計 $|u-u_{h}|_{1}\leq (1+\Lambda )|u-I_{h}u|_{1}\!\,$ 並用 $h\!\,$ 的適當冪來對右端進行限制。明確說明 $u\!\,$ 所需的正則性。

解 6c

證明不等式

${\begin{aligned}|u-u_{h}|_{1}&=|u-I_{h}u+I_{h}u-u_{h}|_{1}\\&\leq |u-I_{h}u|_{1}+|I_{h}u-u_{h}|_{1}\\&\leq |u-I_{h}u|_{1}+\Lambda |u-I_{h}u|_{1}\\&=(1+\Lambda )|u-I_{h}u|_{1}\end{aligned}}$

限制右端

對於 $x\in [x_{i-1},x_{i}]\!\,$，牛頓多項式插值誤差給出了某個 $\xi _{i}\in [x_{i-1},x_{i}]\!\,$

${\begin{aligned}|u-I_{h}u|_{1}^{2}&=\left|{\frac {u^{(2)}(\xi _{i})}{2}}(x-x_{i})(x-x_{i-1})\right|_{1}^{2}dx\\&=\int _{0}^{1}\left(\left[{\frac {u^{(2)}(\xi _{i})}{2}}(x-x_{i})(x-x_{i-1})\right]'\right)^{2}\\&=\left({\frac {u^{(2)}(\xi _{i})}{2}}\right)^{2}\int _{0}^{1}[\underbrace {(x-x_{i-1})} _{\leq h}\underbrace {(x-x_{i})} _{\leq h}]dx\\&\leq (u^{(2)}(\xi _{i})h)^{2}\end{aligned}}\!\,$

因此，整個區間上的誤差由下式給出：

${\begin{aligned}|u-I_{h}u|_{1}^{2}&\leq \sum _{i=1}^{n}(u^{(2)}(\xi _{i})h)^{2}\\&\leq \max _{0<\xi <1}(u^{(2)}(\xi )h)^{2}\cdot n\end{aligned}}\!\,$

這意味著

$|u-I_{h}u|_{1}\leq \max _{0<\xi <1}u^{(2)}(\xi _{i}){\sqrt {n}}h\!\,$

$u\!\,$ 需要二階可微。