數值方法資格考試問題及解答 (馬里蘭大學)/Aug06 667

問題 4

假設 $f:R\rightarrow R\!\,$ 是光滑的，並且邊值問題

$u''=f(u){\mbox{ on }}(0,1),\quad u(0)=(1)=0\!\,$

有唯一解。

問題 4a

對於 $N\in \mathbb {N} \!\,$ ，令 $x_{i}={\frac {1}{N}},i=0,\ldots ,N\!\,$ 。寫出一個 $N+1\!\,$ 個方程的系統，透過用對稱差分商替換二階導數來獲得解在 $x_{i}\!\,$ 處的近似值 $u_{i}\!\,$ 。

解答 4a

對稱差分商由下式給出

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

因此我們有以下包含初始條件 $u(0)=u(1)=0\!\,$ 的方程組。

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

問題 4b

將方程組寫成 $F(U)=0\!\,$ 的形式。定義 $F\!\,$ 的定義域和值域，並解釋變數 $U\!\,$ 的含義。

解 4b

$\underbrace {AU-f} _{F(U)}=0\!\,$

定義域： $R^{N+1}\!\,$

值域： $R^{N+1}\!\,$

$U\!\,$ 是一個包含 $N+1\!\,$ 個近似值 $u_{i}\!\,$ 的向量，用於在 $x_{i}\!\,$ 處對解 $u\!\,$ 進行近似。

問題 4c

針對 (b) 中的系統，以 $U^{(0)}=0\!\,$ 為初始值，構建牛頓法來求解該系統。儘可能給出所有相關物件的顯式表示式。確定一個充分條件，確保牛頓方案中的迭代值 $U^{(k)}\!\,$ 有定義。無需進行任何進一步計算，你能判斷序列 $U^{(k)}\!\,$ 是否收斂嗎？為什麼或為什麼不？

解 4c

牛頓法

$U^{k+1}=U^{k}-J(F(U^{(k)})^{-1}F(U^{(k)})\!\,$

其中 $J(A)\!\,$ 表示矩陣 $A\!\,$ 的雅可比矩陣。

具體而言，

$J(F(U^{(k)})=J(AU-F)=A-J(F)\!\,$

充分條件

如果 $J(F(U^{(k)})^{-1}\!\,$ 存在，則迭代值 $U^{(k)}\!\,$ 有定義。

序列收斂性

由於牛頓法只能保證區域性收斂，因此我們無法判斷該序列是否收斂。

一般來說，為了保證牛頓法的區域性收斂，我們需要

$F\!\,$ 可微

$D(F(U^{*}))\!\,$ 可逆

$D(F)\!\,$ 滿足利普希茨條件

$U^{(0)}\!\,$ 接近解 $U^{*}\!\,$

問題 5

考慮邊界值問題

-u''=f,\quad 0<x<1\!\,

邊界條件為 $u(0)=0\!\,$ 和 $u'(1)+\alpha u(1)=0\!\,$ 。這裡 $\alpha \!\,$ 是給定的正數。

問題 5a

描述一種使用分段線性函式（基於均勻網格）求解該問題的伽遼金方法。

弱形式

找到 $u\in U=\{u\in H^{1}:u(0)=0\}\!\,$ 使得對於所有 $v\in U\!\,$

$\int _{0}^{1}-u''v=\int _{0}^{1}fv\!\,$

在進行分部積分並代入初始條件後，我們得到

$\int _{0}^{1}u'v'=\int _{0}^{1}fv-\alpha u(1)v(1)\!\,$

令 $\{x_{i}\}_{i=0}^{N+1}\!\,$ 為 $[0,1]\!\,$ 的均勻分割節點，其中 $x_{0}=0\!\,$ 且 $x_{i}=ih\!\,$ .

令 $\{\phi _{i}\}_{i=0}^{N+1}\!\,$ 為以下定義的標準“帽”函式

對於 $i=1,2\ldots ,N\!\,$

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

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

同時， $\phi _{0}=0\!\,$ ，因為 $u(0)=0\!\,$

然後 $\{\phi _{i}\}_{i=0}^{N+1}\!\,$ 形成離散空間 $U_{h}=\{u\in H^{1}[0,1]:u(0)=0,u{\mbox{ piecewise linear }}\}\!\,$ 的基。

問題 5b

推匯出此 Galerkin 方法的矩陣方程。顯式寫出涉及 $\alpha \!\,$ 的線性系統的那個方程。

離散弱形式

尋找 $u_{h}\in U_{h}\!\,$ 使得對於所有 $v\in U_{h}\!\,$

$\int _{0}^{1}u_{h}'v_{h}'=\int _{0}^{1}fv_{h}-\alpha u(1)v(1)\!\,$

由於 $\{\phi _{i}\}_{i=0}^{N+1}\!\,$ 形成基，我們有

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

同樣對於 $j=1,\ldots ,N+1\!\,$

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

用矩陣形式表示

${\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&&&\\-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}&&&\\&\ddots &\ddots &\ddots &&\\&&&&-{\frac {1}{h}}&{\frac {2}{h}}+\alpha \end{bmatrix}}{\begin{bmatrix}u_{h_{1}}\\u_{h_{2}}\\\vdots \\u_{h_{N+1}}\end{bmatrix}}={\begin{bmatrix}\int _{0}^{1}f\phi _{1}\\\int _{0}^{1}f\phi _{2}\\\vdots \\\int _{0}^{1}f\phi _{N+1}\end{bmatrix}}\!\,$

問題 6

考慮線性多步法

$y_{n+1}={\frac {4}{3}}y_{n}-{\frac {1}{3}}y_{n-1}+{\frac {2}{3}}hf(x_{n+1},y_{n+1})\!\,$

用於求解初值問題 $y'(x)=f(x,y(x)),y(0)=y_{0}\!\,$

問題 6a

證明截斷誤差為 2 階。

問題 6b

說明線性多步法的相容性條件，並驗證該問題的方案是否滿足此條件。

解答 6b

${\begin{aligned}y_{n+1}&=\sum _{j=0}^{p}a_{j}y_{n-j}+h\sum _{j=-1}^{p}b_{j}f(t_{n-j},y_{n-j})\\&=a_{0}y_{n}+a_{1}y_{n-1}+\ldots +a_{p}y_{n-p}+h[b_{-1}f(t_{n+1},y_{n+1})+b_{0}f(t_{n},y_{n})+b_{1}f(t_{n-1},y_{n-1})+\ldots +b_{p}f(t_{n-p},y_{n-p})]\end{aligned}}\!\,$