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

問題 4

設 $f:R^{n}\rightarrow R\!\,$ 是一個非線性光滑函式。為了確定 $f\!\,$ 的（區域性）最小值，可以使用如下形式的下降方法

x_{k+1}=x_{k}+\alpha _{k}d_{k}\quad (k\geq 0)\quad \quad (1)\!\,

其中 $0\leq \alpha _{k}\leq 1\!\,$ 是透過回溯獲得的適當引數，而 $d_{k}$ 是一個下降方向，即它滿足

f(x_{k+1})<f(x_{k})\quad \quad (2)\!\,

問題 4a

寫出最速下降法（或梯度法），並證明存在 $0<\alpha _{k}\leq 1\!\,$ 使得由此產生的方法滿足 (2)

解答 4a

最速下降法

$x_{k+1}=x_{k}-\alpha _{k}\nabla f(x_{k})\!\,$

選擇 $\alpha _{k}\in (0,1]\!\,$ 使得 $\alpha _{k}\!\,$ 最小化 $f(x_{k}-\alpha _{k}\nabla f(x_{k}))\!\,$ ，即

$\alpha _{k}:\min _{0<\alpha _{k}\leq 1}f(x_{k}-\alpha _{k}\nabla f(x_{k}))\!\,$

方向導數為負

為了滿足 (2)，方向導數應該為負，即

$\nabla _{d_{k}}f(x_{k})=\lim _{\alpha _{k}\rightarrow 0}{\frac {f(x_{k}+\alpha _{k}d_{k})-f(x_{k})}{\alpha _{k}}}<0\!\,$

這意味著

$\underbrace {f(x_{k}+\alpha _{k}d_{k})} _{f(x_{k+1})}<f(x_{k})\!\,$

因為 $\alpha _{k}\in (0,1]\!\,$

問題 4b

寫出牛頓法，並檢驗是否存在 $\alpha _{k}\!\,$ 使得 (2) 成立。確定 $f(x)\!\,$ 的海森矩陣 $H(f(x))\!\,$ 上的條件，這些條件保證了 $\alpha _{k}\!\,$ 的存在。

解 4b

牛頓法

$x_{k+1}=x_{k}-H^{-1}(f(x_{k}))\nabla f(x_{k})\!\,$

方向導數為負

為了下降，我們需要方向導數為負，即

$\nabla _{\alpha _{k}d_{k}}f(x_{k})=\nabla f(x_{k})\cdot \alpha _{k}d_{k}=-\nabla f(x_{k})\cdot H^{-1}(f(x_{k}))\nabla f(x_{k})<0\!\,$

這意味著

$\nabla f(x_{k})^{T}H^{-1}(f(x_{k}))\nabla f(x_{k})>0\!\,$

因此 $H^{-1}(f(x_{k}))\!\,$ 是正定的，因此 $H(f(x_{k}))\!\,$ 是正定的。

問題 4c

如果我們用矩陣 $H(f(x))+\gamma _{k}I\!\,$ 替換 Hessian，其中 $\gamma _{k}\geq 0\!\,$ 且 $I$ 是單位矩陣，我們得到一個擬牛頓法。求 $\gamma _{k}\!\,$ 的條件，它會導致 (2)。

解 4c

我們現在需要 ${\tilde {H}}(f(x_{k}))=H(f(x_{k}))+\gamma _{k}I\!\,$ 是正定的。

令 $\lambda _{i}\!\,$ ， $i=1,2,\ldots ,n\!\,$ 是 $H(f(x_{k}))\!\,$ 的特徵值。

然後 $\lambda _{i}+\gamma _{k}\cdot 1\!\,$ ， $i=1,2,\ldots ,n\!\,$ 是 ${\tilde {H}}(f(x_{k}))\!\,$ 的特徵值。

由於我們希望 ${\tilde {H}}(f(x_{k}))\!\,$ 為正定，等價於對 $i=1,2,\ldots ,n\!\,$

$\lambda _{i}+\gamma _{k}>0\!\,$

即

$\gamma _{k}>-\lambda _{i}\quad i=1,2,\ldots ,n\!\,$

問題 5

考慮以下在 $R$ 中的非線性自治初值問題，其中 $f\in C^{2}$ 。

y'=f(y)\quad \quad y(0)=y_{0}

問題 5a

將 ODE 寫成積分形式，並使用中點求積規則推匯出具有均勻時間步長 $h={\frac {T}{N}}$ 的中點法。

y_{n+1}=y_{n}+hf({\frac {y_{n+1}+y_{n}}{2}})

解答 5a

對於 $x\in [x_{n},x_{n+1}]\!\,$ ，

$y(x_{n+1})-y(x_{n})=\int _{x_{n}}^{x_{n+1}}f(y(x))dx\approx h\cdot f\left({\frac {y_{n+1}+y_{n}}{2}}\right)\!\,$

問題 5b

定義截斷誤差 $T_{n}\!\,$ . 假設 $T_{n}=O(h^{3})\!\,$ , 證明誤差 $|y(t_{N})-y_{N}|\!\,$ 的估計值。該方法的階數是多少？（提示：利用 $f\!\,$ 是 Lipschitz 連續的）。

解 5b

${\begin{aligned}|e_{n+1}|&=|y(t_{n+1})-y_{n+1}|\\&\leq |y(t_{n})-y_{n}|+h\underbrace {\left|f\left({\frac {y(t_{n+1})-y(t_{n})}{2}}\right)-f\left({\frac {y_{n+1}-y_{n}}{2}}\right)\right|} _{\leq {\frac {\gamma }{2}}|y(t_{n+1})-y(t_{n})-y_{n+1}+y_{n}|}+{\mathcal {O}}(h^{3})\\&\leq |e_{n}|+{\frac {h\gamma }{2}}\left(|e_{n+1}|+|e_{n}|\right)+{\mathcal {O}}(h^{3})\end{aligned}}$

其中 $\gamma \!\,$ 是 $f\!\,$ 的 Lipschitz 常數。重新排列項，我們得到

$|e_{n+1}|\leq \underbrace {\frac {1+{\frac {h\gamma }{2}}}{1-{\frac {h\gamma }{2}}}} _{C}|e_{n}|+{\mathcal {O}}(h^{3})\!\,$

特別是， $|e_{1}|\leq C\underbrace {|e_{0}|} _{0}+{\mathcal {O}}(h^{3})\!\,$

那麼 $e_{N}\!\,$ 由下式給出

${\begin{aligned}e_{N}&=\left(C^{N-1}+C^{N-2}+\cdots +C+1\right){\mathcal {O}}(h^{3})\\&={\frac {C^{N}-1}{C-1}}{\mathcal {O}}(h^{3})\\&\leq K{\mathcal {O}}(h^{2})\end{aligned}}\!\,$

問題 5c

證明 $T_{n}=O(h^{3})\!\,$ 對於此方法。(提示：首先展開 $y(t_{n+1})\!\,$ 和 $y(t_{n})\!\,$ 在 $\tau _{n}=t_{n}+{\frac {h}{2}}\!\,$ 附近，然後展開 $f({\frac {1}{2}}(y(t_{n+1})+y(t_{n}))).\!\,$ 也展開 $y'(t)\!\,$ 在 $\tau _{n}\!\,$ 附近。）

解 5c

中點法可以改寫如下

$y(t_{n+1})=y(t_{n})+{\frac {h}{2}}y'(t_{n+1})+{\frac {h}{2}}y'(t_{n})+T_{n}\!\,$

這意味著

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

將每項在 $\tau _{n}=t_{n}+{\frac {h}{2}}\!\,$ 附近展開，得到 $T_{n}\!\,$ .

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

問題 6

考慮以下邊界為兩點的邊值問題，在 $(0,1)\!\,$ 內，且 $\epsilon <<1\leq b:\!\,$

-\epsilon u_{xx}+bu_{x}=1,\quad u(0)=u(1)=0\!\,

問題 6a

寫出有限元方法，其中分段線性元素在 $(0,1)\!\,$ 上形成一個均勻網格，網格尺寸為 $h\!\,$ 。如果 $U={U_{i}}_{i=0}^{I+1}\!\,$ 是有限元解的節點值向量，找到（剛度）矩陣 $A\!\,$ 和右手邊 $F\!\,$ ，使得 $AU=F\!\,$ 。 $A\!\,$ 是否對稱？ $A\!\,$ 是否正定？

解答 6a

弱變分公式

用測試函式 $v\in H_{0}^{1}[0,1]\!\,$ 乘以給定方程，並從 0 到 1 進行積分，得到等效的弱變分公式

找到 $u\in H_{0}^{1}[0,1]\!\,$ ，使得對於所有 $v\in H_{0}^{1}[0,1]\!\,$ ，以下成立

\underbrace {\epsilon \int _{0}^{1}u'v'dx+b\int _{0}^{1}u'vdx} _{a(u,v)}=\underbrace {\int _{0}^{1}vdx} _{f(v)}\!\,

離散變分公式

令 $V_{h}=\{v\in H_{0}^{1}[0,1]:\left.v_{h}\right|_{[x_{i-1},x_{i}]}{\mbox{ linear }}\!\,$ 當 $i=1,2,\ldots ,n\}\!\,$

那麼我們有離散變分公式，它是弱變分公式的近似。

尋找 $u_{h}\in V_{h}\!\,$ 使得對於所有的 $v_{h}\in V_{h}\!\,$

a(u_{h},v_{h})=f(v_{h})\!\,

定義 V_h 的基底

令 $\{\phi _{i}\}_{i=1}^{n}\!\,$ 是線性“帽”函式，它定義了 $V_{h}\!\,$ 的基底。

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

然後計算得到以下結果：（畫圖）

$\int _{0}^{1}\phi _{i}(x)dx=h\!\,$

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

$\int _{0}^{1}\phi _{i}'(x)\phi _{j}'(x)dx={\begin{cases}{\frac {2}{h}}&{\mbox{ if }}i=j\\-{\frac {1}{h}}&{\mbox{ if }}|i-j|=1\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

$\int _{0}^{1}\phi _{i}(x)\phi _{j}'(x)dx={\begin{cases}0&{\mbox{ if }}i=j\\{\frac {1}{2}}&{\mbox{ if }}i-j=1\\-{\frac {1}{2}}&{\mbox{ if }}i-j=-1\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

矩陣形式的離散變分公式

由於 $\{\phi _{i}\}_{i=1}^{n}\!\,$ 是 $V_{h}\!\,$ 的一個基，

u_{h}=\sum _{i=1}^{n}u_{hi}\phi _{i}\!\,

此外，離散變分公式也可以表示為

\epsilon \sum _{i=1}^{n}u_{hi}\int _{0}^{1}\phi _{i}'(x)\phi _{j}'(x)dx+b\sum _{i=1}^{n}u_{hi}\int _{0}^{1}\phi _{i}'(x)\phi _{j}(x)dx=\int _{0}^{1}\phi _{j}(x)dx{\mbox{ for }}j=1,2,\ldots ,n\!\,

其矩陣形式為

$\underbrace {\begin{bmatrix}2{\frac {\epsilon }{h}}&-{\frac {\epsilon }{h}}+{\frac {b}{2}}&0&\cdots &\cdots &0\\-{\frac {\epsilon }{h}}-{\frac {b}{2}}&2{\frac {\epsilon }{h}}&-{\frac {\epsilon }{h}}+{\frac {b}{2}}&0&\cdots &0\\0&\ddots &\ddots &\ddots &\cdots &0\\0&\cdots &\cdots &0&-{\frac {\epsilon }{h}}-{\frac {b}{2}}&2{\frac {\epsilon }{h}}\end{bmatrix}} _{A}{\begin{bmatrix}u_{1}\\u_{2}\\\vdots \\u_{n}\end{bmatrix}}={\begin{bmatrix}h\\h\\\vdots \\h\end{bmatrix}}\!\,$

$A\!\,$ 不是對稱矩陣。 $A\!\,$ 如果滿足以下條件，則為正定矩陣

{\frac {\epsilon }{h}}>{\frac {b}{2}}\!\,

問題 6b

找出三個引數 $h,\epsilon ,b\!\,$ 之間的關係，使得 $A\!\,$ 為 $M-\!\,$ 矩陣，即當 $i\neq j\!\,$ 時，有 $a_{ii}>0,a_{ij}\leq 0\!\,$ ，以及 $a_{ii}\geq -\sum _{i\neq j}a_{ij}\!\,$

解 6b

第一行、第二行和最後一行都得出了關於 $A\!\,$ 為 $M\!\,$ - 矩陣的相同不等式。

{\frac {\epsilon }{h}}>{\frac {b}{2}}\!\,

問題 6c

考慮常微分方程的迎風修改

-(\epsilon +{\frac {b}{2}}h)u_{xx}+bu_{x}=1\!\,

證明由此產生的矩陣 $A\!\,$ 是一個 M 矩陣，不受 $h,\epsilon \!\,$ 和 $b\!\,$ 的限制。

解 6c

將 $\epsilon +{\frac {b}{2}}h\!\,$ 代入 $\epsilon \!\,$ 得到以下矩陣 $A\!\,$

${\begin{bmatrix}2{\frac {\epsilon }{h}}+b&-{\frac {\epsilon }{h}}&0&\cdots &\cdots &0\\-{\frac {\epsilon }{h}}-b&2{\frac {\epsilon }{h}}+b&-{\frac {\epsilon }{h}}&0&\cdots &0\\0&\ddots &\ddots &\ddots &\cdots &0\\0&\cdots &\cdots &0&-{\frac {\epsilon }{h}}-b&2{\frac {\epsilon }{h}}+b\end{bmatrix}}\!\,$