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

問題 4a

證明二步法 $y_{n+1}=2y_{n-1}-y_{n}+h[{\frac {5}{2}}f(x_{n},y_{n})+{\frac {1}{2}}f(x_{n-1},y_{n-1})]\qquad (1)\!\,$ 是二階的，但不滿足根條件。

解答 4a

二階方法

方法 $(1)\!\,$ 找到 $y\!\,$ 的近似值，使得 $y'=f(x,y)\!\,$.

令 $x_{n}=a_{0}+hn\!\,$ 為第 $n\!\,$ 個評估點，其中 $a_{0}\!\,$ 是起點，$h\!\,$ 是步長。

關於 a_0 的 y' 的泰勒展開

${\begin{aligned}y'(x_{n})&=y'(a_{0}+hn)\\&=y'(a_{0})+hny''(a_{0})+h^{2}n^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y'(x_{n-1})&=y'(a_{0}+h(n-1))\\&=y'(a_{0})+h(n-1)y''(a_{0})+h^{2}(n-1)^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}$

將上述結果代入公式 $(1)\!\,$ 右側的第二項，並簡化得到

${\begin{aligned}h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]&={\frac {5}{2}}[hy'(a_{0})+h^{2}ny''(a_{0})+{\mathcal {O}}(h^{3})]+{\frac {1}{2}}[hy'(a_{0})+h^{2}(n-1)y''(a_{0})+{\mathcal {O}}(h^{3})]\\&=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\end{aligned}}\!\,$

y 關於 a_0 的泰勒展開

由於 $y_{n}\approx y(x_{n})\!\,$，我們也對 $y\!\,$ 關於 $a_{0}\!\,$ 進行泰勒展開

${\begin{aligned}y(x_{n+1})&=y(a_{0})+h(n+1)y'(a_{0})+h^{2}(n+1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n})&=y(a_{0})+hny'(a_{0})+h^{2}n^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n-1})&=y(a_{0})+h(n-1)y'(a_{0})+h^{2}(n-1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}$

代入並簡化得到，

$y_{n+1}+y_{n}-2y_{n-1}=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\!\,$

取泰勒展開式的差

因此 $y_{n+1}+y_{n}-2y_{n-1}-h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]={\mathcal {O}}(h^{3})\!\,$ 表明 (1) 是一種二階方法。

不滿足根條件

方程 (1) 的特徵方程為

$\lambda ^{2}+\lambda -2=0\!\,$

得到根

$\lambda _{1}=1\!\,$

$\lambda _{2}=-2\!\,$

$\lambda _{2}\!\,$ 顯然不滿足 $|\lambda _{j}|\leq 1\!\,$

問題 4b

舉例說明方法 (1) 在求解 $y'=f(x,y)\!\,$ 時，可能不會收斂。

解題 4b

令 $f(x,y)=0,y(0)=y_{0}=1\!\,$。則 $y(t)=1\!\,$。我們得到差分方程

$y_{n+1}+y_{n}-2y_{n-1}=0\!\,$

它的通解為（使用根）：

$y_{n}=C_{1}(-2)^{n}+C_{2}\cdot 1^{n}\!\,$

如果 $C_{1}\neq 0\!\,$，那麼 $y_{n}\rightarrow \infty \!\,$ 當 $n\rightarrow \infty \!\,$

$y_{0}=C_{1}+C_{2}\!\,$

$y_{1}=-2C_{1}+C_{2}\!\,$

因此， ${\frac {y_{0}-y_{1}}{3}}=C_{1}\!\,$。因此，如果 $y_{0}\neq y_{1}\!\,$，那麼 $C_{1}\neq 0\!\,$。

問題 5

考慮邊界值問題 $-u''+(1+x)u=x^{2}\quad u'(0)=1,u(1)=1\qquad (2)\!\,$

問題 5a

證明 $(2)\!\,$ 最多隻有一個解

解 5a

令 $u_{1}\!\,$ 和 $u_{2}\!\,$ 為解。令 $u\equiv u_{1}-u_{2}\!\,$.

透過減去兩個方程及其條件，我們有

$-u''+(1+x)u=0\quad u'(0)=0,u(1)=0\!\,$

用測試函式 $v\in V=\{v\in H^{1}:v(1)=0\}\!\,$ 乘，並從 0 到 1 進行分部積分，我們需要找到 $u\in V\!\,$ 使得對於所有 $v\in V\!\,$

$\int _{0}^{1}u'v'+\int _{0}^{1}(1+x)uv=0\!\,$

令 $v=u\!\,$。然後，我們有

$\int _{0}^{1}(u')^{2}+\int _{0}^{1}(1+x)u^{2}=0\!\,$

由於 $(u')^{2}\!\,$，$(1+x)\!\,$ 以及 $u^{2}\!\,$ 都為 $>0\!\,$，$u^{2}=0\!\,$。因此 $u_{1}=u_{2}\!\,$.

問題 5b

將問題離散化。對 $[0,1]:\!\,$ 進行均勻劃分 $x_{i}=ih,i=0,1,2,\ldots ,n,\quad h={\frac {1}{n}}\!\,$ 使用三點差分公式計算 $u''\!\,$，並使用最簡單的差分公式計算 $x=0\!\,$ 處的邊界條件。將所得系統寫成矩陣向量方程 $Ax=b\!\,$，其中 $x=(u_{1},u_{2},\cdots ,u_{n-1})^{T}\!\,$

解題 5b

三點差分公式計算 $u''\!\,$ 為

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

i=2,...,n-2 的方程

將差分公式代入 $(2)\!\,$，在矩陣形式中，我們得到

${\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+ih)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{i-1}\\u_{i}\\u_{i+1}\end{bmatrix}}=(ih)^{2}$

i = 1 時的方程

我們可以使用近似值消除 $u_{0}\!\,$ 變數

$u'(0)={\frac {u_{1}-u_{0}}{h}}=1\!\,$

這意味著

$u_{0}=u_{1}-h\!\,$

使用這種關係和三個差分公式，我們有

${\begin{bmatrix}{\frac {1}{h^{2}}}+(1+h)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{1}\\u_{2}\end{bmatrix}}=h^{2}-{\frac {1}{h}}\!\,$

i = n - 1 時的方程

由於 $u(1)=u_{n}=1\!\,$，我們可以透過代入到 n-1 方程中來消除 $u_{n}\!\,$ 變數。

${\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+(n-1)h)\end{bmatrix}}{\begin{bmatrix}u_{n-2}\\u_{n-1}\end{bmatrix}}=h^{2}-((n-1)h)^{2}+{\frac {1}{h^{2}}}$

問題 5c

證明在 $(b)\!\,$ 中找到的方程有一個唯一解

解決方案 5c

由於矩陣 $A\!\,$ 是對角佔優的，所以系統 $Ax=b\!\,$ 有唯一的解。

問題 5d

將問題 $(2)\!\,$ 轉化為具有齊次邊界條件的等價問題。

解 5d

令 $u\!\,$ 是邊界值問題的解，表示為兩個不同邊界值問題的解之和，即

$u=w+v\!\,$ 其中

$-w''+(1+x)w=f(x)\quad w'(0)=0,w(1)=0\!\,$

$-v''+(1+x)v=g(x)\quad v'(0)=1,v(1)=1\qquad (*)\!\,$

$-u''+(1+x)u=x^{2}=f(x)+g(x)\quad u'(0)=1,u(1)=1\!\,$

假設 $v(x)=ax+b\!\,$。然後

$v'(0)=a=1\!\,$ 以及 $v(1)=1+b=1\!\,$，這意味著 $b=0\!\,$，因此

$v(x)=x\!\,$

代入 $(*)\!\,$，我們有

$-0+(1+x)x=g(x)\!\,$

這意味著

$g(x)=x^{2}+x\!\,$

由於 $f(x)+g(x)=x^{2}\!\,$，我們有 $f(x)=-x\!\,$

因此，一個具有齊次邊界條件的等效邊值問題由下式給出：

$-w''+(1+x)w=-x\quad w'(0)=0,w(1)=0\!\,$

問題 5e

獲得在 $(d)\!\,$ 中制定的問題的變分公式。指定所涉及的索伯列夫空間 $H\!\,$。證明此問題具有唯一解，我們用 $v\!\,$ 表示。

解答 5e

變分公式和索伯列夫空間

使用問題的符號，我們要找到 $v\in H=\{w\in H^{1}:w(1)=0\}\!\,$，使得對於所有 $w\in H\!\,$，我們有：

$a(v,w)=\int _{0}^{1}v'w'+\int _{0}^{1}(1+x)vw=-\int _{0}^{1}xw=F(w)\!\,$

上述結果來自分部積分和應用邊界條件。

唯一解

為了表明 $v\!\,$ 是唯一的，我們證明 Lax-Milgram 定理的假設得到滿足。

a(v,w) 有界且連續

${\begin{aligned}a(v,w)&=\int _{0}^{1}v'w'+\int _{0}^{1}\underbrace {(1+x)} _{\leq 2}vw\\&\leq 2\left[\int _{0}^{1}v'w'+\int _{0}^{1}vw\right]\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}\right]^{\frac {1}{2}}+\left[\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]\quad {\mbox{ Cauchy-Schwartz in L2 }}\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}+\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}+\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]{\mbox{ Cauchy-Schwartz in R2 }}\\&=2\|w\|_{1}\|v\|_{1}\end{aligned}}\!\,$

a(v,v) 協ercive

${\begin{aligned}a(v,v)&=\int _{0}^{1}v'^{2}+\int _{0}^{1}\underbrace {(1+v)} _{\geq 1}v^{2}\\&\geq \int _{0}^{1}v'^{2}+\int v^{2}\\&=\|v\|_{1}^{2}\end{aligned}}$

F(v) 有界

$|F(v)|=|-\int _{0}^{1}xv|\leq |\int _{0}^{1}v|\leq \|v\|_{1}^{2}\!\,$

問題 5f

考慮使用分段線性有限元逼近 $v\!\,$。精確地定義分段線性有限元子空間（使用分割槽 (3)）。證明有限元問題有唯一解。

問題 5g

證明 $\|v-v_{h}\|_{H}\leq Ch\!\,$，並指出常數 $C\!\,$ 如何依賴於 $v\!\,$ 的導數。

問題 6

令 $f:\mathbb {R} \to \mathbb {R} \!\,$ 為一個非線性函式，零點為 $x_{*}\!\,$ $f(x,y)={\begin{bmatrix}x^{2}-2x+y\\2x-y^{2}-1\end{bmatrix}}\!\,$，$x_{*}={\begin{bmatrix}1\\1\end{bmatrix}}\!\,$. 考慮迭代 $x_{n+1}=x_{n}-Af(x_{n})\!\,$，$A={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}\qquad (4)\!\,$.

問題 6a

證明 (4) 是區域性收斂的。

解答 6a

$\phi (x_{n}):=x_{n+1}=x_{n}-Af(x_{n})\!\,$ 是一個不動點迭代。根據壓縮對映定理，如果 $\phi (x)\!\,$ 在 $x_{*}\!\,$ 的某個鄰域內是壓縮對映，則該迭代至少線性收斂。

我們需要證明存在一個$\gamma <1\!\,$，使得$\|\phi (x)-\phi (y)\|\leq \gamma \|x-y\|\!\,$。

根據中值定理，我們有$\|\phi (x)-\phi (y)\|\leq \|D\phi (\xi )\|\|x-y\|\!\,$，即$\gamma =D\phi (\xi )\!\,$，其中$\xi \!\,$ 在$x_{*}\!\,$ 的鄰域內。

特別地，$\|D\phi (x_{*})\|=\|I-AD\phi (x_{*})\|=0<1\!\,$，這意味著$\phi (x)\!\,$ 是一個壓縮對映，並且迭代方法至少以線性速度收斂。

計算雅可比矩陣

$D\phi =Dx-ADf\!\,$

$Dx=I\!\,$

$Df={\begin{pmatrix}2x-2&1\\2&-2y\end{pmatrix}}\!\,$

${\begin{aligned}D\phi (x_{*})&=I-AD\phi (x_{*})\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&{\frac {1}{2}}\\1&0\end{pmatrix}}{\begin{pmatrix}2(1)-2&1\\2&-2(1)\end{pmatrix}}\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&0\\0&1\end{pmatrix}}\\&={\begin{pmatrix}0&0\\0&0\end{pmatrix}}\\\|D\phi (x_{*})\|&=0\end{aligned}}$

$\!\,$

問題 6b

證明收斂速度至少為二次。

解題 6b

${\begin{aligned}e_{n+1}&=x_{n+1}-x_{*}\\&=\underbrace {x_{n}-Af(x_{n})} _{\phi (x_{n})}-x_{*}\\&=\phi (x_{n})-x_{*}\\&=\left(\phi (x_{*})+(x_{n}-x_{*})^{T}\underbrace {D_{\phi }(x_{*})} _{0}+(x_{n}-x_{*})^{T}{\frac {H_{\phi }(x_{*})}{2!}}(x_{n}-x_{*})+R(x_{n},x_{*})\right)-x_{*}\\&=\left(x_{*}+A\underbrace {f(x_{*})} _{0}+{\frac {H_{\phi }(x_{*})}{2!}}\underbrace {(x_{n}-x_{*})^{T}(x_{n}-x_{*})} _{e_{n}^{2}}+R(x_{n},x_{*})\right)-x_{*}\\&\leq Ce_{n}^{2}+R(x_{n},x_{*})\end{aligned}}\!\,$

其中 $R(x_{n},x_{*})\!\,$ 滿足 ${\frac {\|R(x_{n},x_{*})\|}{\|x_{n}-x_{*}\|}}\rightarrow 0\!\,$ 當 $\|x_{n}-x_{*}\|\rightarrow 0\!\,$.

然後，我們得到 $\|e_{n+1}\|\leq C\|e_{n}\|^{2}\!\,$.

問題 6c

寫出牛頓迭代並將其與 (4) 進行比較。

解答 6c

牛頓迭代如下所示

$x_{n+1}=x_{n}-B(x_{n})f(x_{n})\!\,$

${\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}={\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}-\underbrace {{\begin{bmatrix}2x_{n}-2&1\\2&-2y_{n}\end{bmatrix}}^{-1}} _{B}{\begin{bmatrix}x_{n}^{2}-2x_{n}+y_{n}\\2x_{n}-y_{n}^{2}-1\end{bmatrix}}$

其中 B 是 f 的雅可比矩陣的逆矩陣。

$B(x_{*})={\begin{bmatrix}2(1)-2&1\\2&-2(1)\end{bmatrix}}^{-1}={\begin{bmatrix}0&1\\2&-2\end{bmatrix}}^{-1}={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}=A$

也就是說，$B(x_{*})\!\,$ 在牛頓迭代中給出 (4)。