数值方法资格考试问题及解答（马里兰大学）/2008 年 1 月 667

问题 4

考虑以下系统 $x=1+h{\frac {e^{-x^{2}}}{1+y^{2}}}{\mbox{,}}\qquad y=.5+h\arctan(x^{2}+y^{2})\!\,$.

问题 4a

证明如果参数 $h>0\!\,$ 选择得足够小，那么该系统在某个矩形区域内有唯一解 $(x^{*},y^{*})\!\,$。

解答 4a

方程组可以用矩阵表示。

$f(x,y)={\begin{bmatrix}1+h{\frac {e^{-x^{2}}}{1+y^{2}}}\\\\.5+h\arctan(x^{2}+y^{2})\end{bmatrix}}\!\,$

$f(x,y)\!\,$ 的雅可比矩阵，$J(f)\!\,$，可以使用偏导数计算

$J(f)={\begin{bmatrix}{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)&{\frac {-h2ye^{-x^{2}}}{(1+y^{2})^{2}}}\\h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}\end{bmatrix}}\!\,$

如果 $h\!\,$ 足够小，并且 $x,y\!\,$ 限制在有界区域 $B\!\,$ 内，

$\underbrace {\|J(f)\|} _{C}<1\!\,$

根据中值定理，对于 ${\vec {x_{1}}},{\vec {x_{2}}}\in B\!\,$，存在 ${\vec {\xi }}\!\,$ 使得

$f({\vec {x_{1}}})-f({\vec {x_{2}}})=J(f({\vec {\xi }}))({\vec {x_{1}}}-{\vec {x_{2}}})\!\,$

由于 $\|J(f)\|\!\,$ 在区域 $B\!\,$ 内是有界的，给定足够小的 $h\!\,$

$\|f({\vec {x_{1}}})-f({\vec {x_{2}}})\|\leq C\|{\vec {x_{1}}}-{\vec {x_{2}}}\|\!\,$

因此，$f\!\,$ 是一个压缩映射，根据压缩映射定理，在矩形区域内存在唯一的固定点（解）。

问题 4b

推导出求解该系统的固定点迭代方案，并证明其收敛性。$\!\,$

解答 4b

使用牛顿法

为了解决这个问题，我们可以使用牛顿法。事实上，我们想要找到以下函数的零点

$g(x,y)={\begin{bmatrix}x\\\\y\end{bmatrix}}-{\begin{bmatrix}1+h{\frac {e^{-x^{2}}}{1+y^{2}}}\\\\.5+h\arctan(x^{2}+y^{2})\end{bmatrix}}\!\,$

$g(x,y)\!\,$ 的雅可比矩阵，$J(g)\!\,$，可以使用偏导数计算

$J(g)={\begin{bmatrix}1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)&{\frac {-he^{-x^{2}}}{1+y^{2}}}\\h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}\end{bmatrix}}\!\,$

然后，求解这个线性方程组的牛顿法由以下公式给出

${\begin{bmatrix}x_{k+1}\\\\y_{k+1}\end{bmatrix}}={\begin{bmatrix}x_{k}\\\\y_{k}\end{bmatrix}}-\underbrace {{\frac {1}{det(J(g))}}{\begin{bmatrix}1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}&{\frac {he^{-x^{2}}}{1+y^{2}}}\\-h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)\end{bmatrix}}} _{J(g)^{-1}}g(x_{k},y_{k})\!\,$

通过验证牛顿假设成立来证明收敛性

g 的雅可比矩阵是 Lipschitz 连续的

我们想证明 $J(g)\!\,$ 是一个 Lipschitz 函数。事实上，

${\begin{aligned}\|J(g)({\vec {x_{1}}})-J(g)({\vec {x_{2}}})\|&=\|(I-J(f))({\vec {x_{1}}})-(I-J(f))({\vec {x_{2}}})\|\\&=\|{\vec {x_{1}}}-{\vec {x_{2}}}-J(f){\vec {x_{1}}}+J(f){\vec {x_{2}}}\|\\&\leq \|{\vec {x_{1}}}-{\vec {x_{2}}}\|+\|J(f){\vec {x_{2}}}-J(f){\vec {x_{1}}}\|\end{aligned}}\!\,$

现在，利用 $J(f)\!\,$ 是 Lipschitz 连续的，我们得到

$\|J(g)({\vec {x_{1}}})-J(g)({\vec {x_{2}}})\|\leq (1+C)\|({\vec {x_{1}}})-({\vec {x_{2}}})\|\!\,$

g 的雅可比矩阵是可逆的

由于 $J(f)\!\,$ 是一个压缩映射，$f\!\,$ 的雅可比矩阵的谱半径小于 1，即

$\rho (J(f))<1\!\,$.

另一方面，我们知道 $J(g)\!\,$ 的特征值为 $\lambda (J(g))=1-\lambda (J(f))\!\,$.

因此，可以得到 $det(I-(J(g)))\neq 0\!\,$，或者等效地 $J(g)\!\,$ 是可逆的。

g 的雅可比矩阵的逆矩阵是有界的

$\underbrace {{\frac {1}{det(J(g))}}{\begin{bmatrix}1-h\cdot {\frac {2y}{1+(x^{2}+y^{2})^{2}}}&{\frac {he^{-x^{2}}}{1+y^{2}}}\\-h\cdot {\frac {2x}{1+(x^{2}+y^{2})^{2}}}&1-{\frac {h}{1+y^{2}}}e^{-x^{2}}(-2x)\end{bmatrix}}} _{J(g)^{-1}}\!\,$

由于 $J(g)^{-1}\!\,$ 存在，${\mbox{det}}(J(g))\neq 0\!\,$。给定一个有界区域（有界 $x,y\!\,$），上述矩阵的每个元素都是有界的。因此，范数是有界的。

(g 的雅可比矩阵)^-1(x_0) * g(x_0) 的范数是有界的

$\|J(g)^{-1}(x_{0})*g(x_{0})\|<\infty \!\,$，因为 $J(g)^{-1}\!\,$ 和 $g(x)\!\,$ 都是有界的。

然后，使用一个足够好的近似值 $(x_{0},y_{0})\!\,$，我们可以得到牛顿法至少是二次收敛的，即：

$\|(x_{k-1},y_{k+1})-(x^{*},y^{*})\|\leq K\|(x_{k},y_{k})-(x^{*},y^{*})\|^{2}.\!\,$

问题 5a

概述用于数值求解初值问题 $y'=f(x,y){\mbox{, }}y(x_{0})=y_{0}\!\,$ 的 Adams-Bashforth 方法的推导。

解 5a

我们想要解以下初值问题：$y'=f(x,y){\mbox{, }}y(x_{0})=y_{0}\!\,$。

首先，我们将该表达式在 $[t_{n},t_{n+1}]\!\,$ 上积分，得到

$y(t_{n+1})=y(t_{n})+\int _{t_{n}}^{t_{n+1}}f(t,y(t))dt\!\,$,

为了近似右侧的积分，我们使用一个适当的 p 次插值多项式来近似它的被积函数 $f(t,y(t))\!\,$，在 $t_{n},t_{n-1},...,t_{n-p}\!\,$ 上。

这个想法产生了 Adams-Bashforth 方法。

$y_{n+1}=y_{n}+\int _{t_{n}}^{t_{n-1}}\sum _{k=0}^{p}g(t_{n-k})l_{k}(t)dt\!\,$,

其中，$y_{n}\!\,$ 表示近似解，$g(t)\equiv f(t,y)\!\,$，以及 $l_{k}(t)\!\,$ 表示相关的拉格朗日多项式。

问题 5b

推导 Adams-Bashforth 公式 $y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\qquad \qquad (1)\!\,$

解答 5b

从 (a) 我们得到

$y_{i+1}=y_{i}+\int _{x_{i}}^{x_{i+1}}fdx\!\,$ 其中 $\int _{x_{i}}^{x_{i+1}}fdx\approx \int _{x_{i}}^{x_{i+1}}\left[{\frac {x-x_{i}}{x_{i-1}-x_{i}}}f_{i-1}+{\frac {x-x_{i-1}}{x_{i}-x_{i-1}}}f_{i}\right]dx\!\,$

然后，如果我们令 $x=x_{i}+sh\!\,$，其中 h 是固定步长，我们可以得到

${\begin{aligned}dx&=hds\\x-x_{i}&=sh\\x-x_{i-1}&=(1+s)h\\x_{i}-x_{i-1}&=h\end{aligned}}$

$h\int _{0}^{1}\left[{\frac {sh}{-h}}f_{i-1}+{\frac {(1+s)h}{h}}f_{i}\right]ds=h\left[-{\frac {1}{2}}f_{i-1}+{\frac {3}{2}}f_{i}\right]\!\,$

所以，我们得到了所需的 Adams-Bashforth 方法

$y_{i+1}=y_{i}+h\left[-{\frac {1}{2}}f(x_{i-1},y_{i-1})+{\frac {3}{2}}f(x_{i},y_{i})\right]\!\,$

问题 5c

分析方法 (1)。具体来说，求局部截断误差，证明收敛性，并求收敛阶。

解答 5c

使用泰勒展开式求局部截断误差

注意 $y_{i}\approx y(t_{i})\!\,$。另外，用 h 表示均匀步长 $\Delta t\!\,$。因此，

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

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

因此，给定方程可以写成

$y(t_{i}+h)-y(t_{i})\approx h\left[-{\frac {1}{2}}y'(t_{i}-h)+{\frac {3}{2}}y'(t_{i})\right]\!\,$

展开左侧

在 $t_{i}\!\,$ 附近展开，我们得到

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

展开右侧

同样在 $t_{i}\!\,$ 附近展开得到

${\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&{\frac {13}{12}}hx'(t_{i}+2h)&-{\frac {5}{3}}hx'(t_{i}+h)&-{\frac {5}{12}}hx'(t_{i})&\Sigma \\\hline &&&&\\0&0&0&0&0\\&&&&\\1&{\frac {13}{12}}hx'(t_{i})&-{\frac {5}{3}}hx'(t_{i})&-{\frac {5}{12}}hx'(t_{i})&-1\cdot hx'(t_{i})\\&&&&\\2&{\frac {13}{12}}(2h)hx''(t_{i})&-{\frac {5}{3}}hhx''(t_{i})&0&{\frac {1}{2}}h^{2}x''(t_{i})\\&&&&\\3&{\frac {13}{12}}(2h)^{2}{\frac {hx'''(t_{i})}{2}}&-{\frac {5}{3}}h^{2}{\frac {hx'''(t_{i})}{2}}&0&{\frac {4}{3}}h^{3}x'''(t_{i})\\&&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\\hline \end{array}}$

收敛性证明：稳定性和一致性

一个方法收敛当且仅当它既稳定又一致。

稳定性

很容易证明该方法是零稳定，因为它满足根条件。因此，它稳定。

一致性

截断误差是二阶的。当 h 趋于零时，截断误差趋于零。所以该方法是一致的。

收敛阶数

Dahlquist 原理：一致性 + 稳定性 = 收敛。收敛阶数为 2。

问题 6

考虑问题 $-u''+u=f(x),\;\;0\leq x\leq 1,\;\;u(0)=u(1)=0.\qquad \qquad (2)$

问题 6a

给出 (2) 的变分公式，即用以下形式表达 (2)： $u\in H,\;\;B(x,y)=F(v),\;\;\forall v\in H\qquad \qquad (3)\!\,$ 定义空间 H、双线性形式 B 和线性泛函 F，并说明 (2) 和 (3) 之间的关系。

解 6a

将 (2) 乘以一个测试函数，并使用分部积分法得到

$-\int _{0}^{1}u''vdx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx\!\,$

$\underbrace {\left.-u'v\right|_{0}^{1}} _{0}+\int _{0}^{1}u'v'dx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx\!\,$

因此，与问题 (2) 相关的弱形式或变分形式如下：找到 $u\in H\!\,$ 使得

$B(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}uvdx=\int _{0}^{1}fvdx=F(v)\!\,$ 对于所有 $v\in H,\!\,$

其中 $H:=H_{0}^{1}(0,1)=\{v:v\in H^{1},v(0)=v(1)=0\}\!\,$.

问题 6b

设 $0=x_{0}<x_{1}<\cdots <x_{n}=1\!\,$ 是 $[0,1]\!\,$ 上的一个网格，其中 $h=\max _{j=0,1,\dots ,n-1}(x_{j+1}-x_{j})\!\,$，设 $V_{h}=\left\{u:u{\mbox{ continuous on }}[0,1],u|_{[x_{j},x_{j+1}]}{\mbox{ is linear for each }}j,u(0)=u(1)=0\right\}\!\,$. 定义有限元逼近，$u_{h}{\mbox{ to }}u\!\,$ 基于逼近空间 $V_{h}\!\,$。关于$\|u-u_{h}\|_{1}\!\,$ 在$H^{1}(0,1)\!\,$ 上的 Sobolev 范数误差能说什么？

解 6b

定义分段线性基

对于我们的$V_{h}\!\,$ 的基底，我们使用一组帽子函数$\{\phi _{j}\}_{j=1}^{n-1}\!\,$，即对于$j=1,2,\ldots ,n-1\!\,$

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

定义 u_h

由于$\{\phi _{j}\}_{j=1}^{n-1}\!\,$ 是$V_{h}\!\,$ 的基底，并且$u_{h}\in V_{h}\!\,$，我们有

$u_{h}=\sum _{j=1}^{n-1}u_{hj}\phi _{j}\!\,$.

离散问题

现在，我们可以写下离散问题：找到 $u_{h}\in V_{h}\!\,$ 使得

$B(u_{h},v_{h})=F(v_{h})\!\,$ 对于所有 $v_{h}\in V_{h}.\!\,$

如果我们认为 $\{\phi _{j}\}_{j=1}^{n-1}\!\,$ 是 $V_{h}\!\,$ 的一个基底，以及双线性形式 $B\!\,$ 和泛函 $F\!\,$ 的线性，我们得到等价的问题

找到 $u_{h}=(u_{h,1},\dots ,u_{h,{n-1}})\in \mathbb {R} ^{n-1}\!\,$ 使得

$\sum _{j=1}^{n-1}u_{h,j}\left\{\int _{0}^{1}\phi _{j}'\phi _{i}'dx+\int _{0}^{1}\phi _{j}\phi _{i}dx\right\}=\int _{0}^{1}f\phi _{i}dx,\quad i=1,\dots ,n-1.\!\,$

最后一个问题可以表述为矩阵问题，如下所示

找到 $u_{h}=(u_{h,1},\dots ,u_{h,{n-1}})\in \mathbb {R} ^{n-1}\!\,$ 使得

$Au_{h}=F,\!\,$

其中 $A_{ij}=\int _{0}^{1}\phi _{j}'\phi _{i}'dx+\int _{0}^{1}\phi _{j}\phi _{i}dx\!\,$ 且 $F_{j}=\int _{0}^{1}f\phi _{i}dx\!\,$.

边界误差

一般来说，我们可以使用 Cea 引理得到

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

特别是，我们可以考虑$v_{h}\!\,$ 作为拉格朗日插值，记为 $v_{I}\!\,$。那么，

$\|u-u_{h}\|_{1}\leq C\|u-v_{I}\|_{1}\leq Ch\|u\|_{H^{2}(0,1)}$.

很容易证明有限元解在节点上是精确的。那么它就与拉格朗日插值一致，我们有以下的点估计

$\|u(x)-u_{h}(x)\|_{L^{\infty }([x_{i-1},x_{i}])}\leq \max _{x\in [x_{i-1},x_{i}]}{\frac {u^{(2)}(x)}{(2)!}}\left({\frac {h}{2}}\right)^{2}$

问题 6c

推导出 $\|u-u_{h}\|_{0}\!\,$ 的估计，即 $L_{2}(0,1)\!\,$ 中的误差。提示：令 w 为以下方程的解 (#) :${\begin{cases}-w''+w=u-u_{h},\\w(0)=w(1)=0.\end{cases}}$ 我们用变分方法来刻画 $w\!\,$: $w\in H_{0}^{1},\;\;B(w,v)=\int (u-u_{h})vdx,\forall v\in H_{0}^{1}\!\,$. 令 $v=u-u_{h}\!\,$，得到 $B(w,u-u_{h})=\int (u-u_{h})^{2}dx=\|u-u_{h}\|_{L_{2}}^{2}.\qquad \qquad (4)\!\,$ 使用公式 (4) 估计 $\|u-u_{h}\|_{L_{2}}\!\,$.

解 6c

双线性形式的连续性

${\begin{aligned}B(u,v)&=\int uv+\int u'v'\\&\leq \|u\|_{0}\|v\|_{0}+\|u'\|_{0}\|v'\|_{0}{\mbox{ (Cauchy-Schwarz in L2) }}\\&\leq (\|u\|_{0}^{2}+\|u'\|_{0}^{2})^{\frac {1}{2}}(\|v\|_{0}^{2}+\|v'\|^{2})^{\frac {1}{2}}{\mbox{ ( Cauchy-Schwarz in R2 ) }}\\&=\|u\|_{1}\cdot \|v\|_{1}\end{aligned}}\!\,$

误差的正交性

$B(u-u_{h},v_{h})=0,\quad \forall v_{h}\in V_{h}\!\,$.

w 的 L2 范数的界

${\begin{aligned}\|w\|_{0}^{2}&\leq \|w\|_{1}^{2}\\&=B(w,w)\\&=\int (u-u_{h})w\\&\leq \|u-u_{h}\|_{0}\|w\|_{0}{\mbox{ (Cauchy-Schwarz in L2 ) }}\end{aligned}}\!\,$

因此，

$(*)\qquad \|w\|_{0}\leq \|u-u_{h}\|_{0}\!\,$

w 的 L2 范数的界

从 $(\#)\!\,$，我们有

$-w''+w=u-u_{h}\!\,$

那么，

${\begin{aligned}\|w''\|_{0}&\leq \|w\|_{0}+\|u-u_{h}\|_{0}{\mbox{ (triangle inequality) }}\\&\leq \|u-u_{h}\|_{0}+\|u-u_{h}\|_{0}{\mbox{ (by (*) ) }}\\&=2\|u-u_{h}\|_{0}\end{aligned}}\!\,$

L2 误差界限

${\begin{aligned}\|u-u_{h}\|_{L^{2}}^{2}&=B(w,u-u_{h}){\mbox{ ( from equation (4) ) }}\\&=B(w,u-u_{h})-\underbrace {B(w_{h},u-u_{h})} _{0}\\&=B(w-w_{h},u-u_{h})\\&\leq \|w-w_{h}\|_{H^{1}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}{\mbox{ (Continuity of Bilinear Form) }}\\&\leq Ch\|w\|_{H^{2}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}{\mbox{ (Cea Lemma and Polynomial Interpolation Error) }}\end{aligned}}$

最后，从 (#)，我们有 $\|w\|_{H^{2}(0,1)}\leq C\|u-u_{h}\|_{L_{2}(0,1)}\!\,$。然后，

$\|u-u_{h}\|_{L^{2}(0,1)}^{2}\leq Ch\|u-u_{h}\|_{L_{2}(0,1)}\|u-u_{h}\|_{H^{1}(0,1)}\!\,$,

或者等效地，

$\|u-u_{h}\|_{L^{2}(0,1)}\leq Ch\|u-u_{h}\|_{H^{1}(0,1)}\leq Ch^{2}\|u\|_{H^{2}(0,1)}\!\,$.

问题 6d

假设 $\{\phi _{1}^{h},\dots ,\phi _{N_{h}}^{h}\}\!\,$ 是 $V_{h}{\mbox{ where }}N_{h}=\dim V_{h}{\mbox{, so }}u_{h}=\sum _{j=1}^{N_{h}}c_{j}^{h}\phi _{j}^{h}{\mbox{, for appropriate coefficients }}c_{j}^{h}.\!\,$ 的一个基底。证明 $\|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-C^{T}AC\!\,$ 其中 $C=[c_{1}^{h},\dots ,c_{N_{h}}^{h}]^{T}{\mbox{ and }}A\!\,$ 是刚度矩阵。

解 6d

我们知道

${\begin{aligned}\|u-u_{h}\|_{1}^{2}&=\langle u-u_{h},u-u_{h}\rangle _{H^{1}(0,1)}\\&=\langle u-u_{h},u\rangle _{H^{1}(0,1)}-\underbrace {\langle u-u_{h},u_{h}\rangle _{H^{1}(0,1)}} _{0}\\&=\|u\|_{H^{1}(0,1)}^{2}-\langle u_{h},u\rangle _{H^{1}(0,1)}\\&=\|u\|_{H^{1}(0,1)}^{2}-\|u_{h}\|_{H^{1}(0,1)}^{2}\end{aligned}}$

其中最后两行的替换来自于误差的正交性。

现在，$\|u_{h}\|_{H^{1}(0,1)}^{2}=\sum _{j=1}^{n-1}\sum _{i=1}^{n-1}u_{h,j}u_{h,i}\left(\int _{0}^{1}\phi _{i}'\phi _{j}'dx+\int _{0}^{1}\phi _{i}\phi _{j}dx\right)=\sum _{j=1}^{n-1}\sum _{i=1}^{n-1}u_{h,j}A_{ij}u_{h,i}=C^{t}AC.\!\,$

然后，我们得到

$\|u-u_{h}\|_{1}^{2}=\|u\|_{H^{1}(0,1)}^{2}-C^{t}AC.\!\,$