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

问题 4

人们希望通过以下一种或多种迭代方法来求解方程 $x+\ln x=0\!\,$ ，其根为 $r\approx 0.5\!\,$

(i) $x_{k+1}=-\ln x_{k}\!\,$

(ii) $x_{k+1}=e^{-x_{k}}\!\,$

(iii) $x_{k+1}={\frac {x_{k}+e^{-x_{k}}}{2}}\!\,$

问题 4a

这三种方法中哪一种可以使用？

解答 4a

方法 {ii} 和 {iii} 是 $x+\ln(x)=0\!\,$ 的合适的不动点迭代。

{i} 不是一个不动点迭代

为了成为合适的不动点迭代，每次迭代的范围必须在下次迭代的域内。在 {i} 的情况下， $x_{k+1}=-\ln x_{k}\!\,$ 可以返回 $(-\infty ,\infty )\!\,$ 中的值，但只能接受 $(0,\infty )\!\,$ 中的 x 值。

{ii} 和 {iii} 是不动点迭代

令 $f(x):=e^{-x}\!\,$ 和 $g(x):={\frac {x+e^{-x}}{2}}\!\,$

很明显

$f:(-\infty ,\infty )\to (0,\infty )\!\,$

以及

$g:(-\infty ,\infty )\to (0,\infty )\!\,$

同时注意到给定域 $D=(0,1)$

$|f(x)-f(y)|\leq |f'(\eta )||x-y|\!\,$ 对于某些 $\eta \in D\!\,$

其中 $\max _{\eta \in D}|f'(\eta )|=\max _{\eta \in D}|e^{-x}|\leq 1\!\,$

以及

$|g(x)-g(y)|\leq |g'(\eta )||x-y|\!\,$ 对于某些 $\eta \in D\!\,$

其中 $\max _{\eta \in D}|g'(\eta )|=\max _{\eta \in D}|{\frac {1}{2}}(1-e^{-x})|\approx 0.316060279\!\,$

也就是说，f、g 都是压缩映射。

问题 4b

应该使用哪种方法？

解决方案 4b

对于区间 (0,1)，{iii} 比 {ii} 更好的不动点迭代，因为它的 Lipschitz 常数更小。

问题 4c

给出更好的迭代公式。

解决方案 4c

牛顿法给出的迭代公式具有二次收敛性，相比之下，{iii} 的收敛性是线性的。

问题 5

考虑以下边界值问题：

${\begin{cases}-u''+e^{u}=0&0<x<1\\u(0)=u(1)=0&\end{cases}}\!\,$

使用在等距网格上连续分段线性函数的有限元方法离散该问题。积分采用梯形法则。将该方法写成以下形式：

$AU_{h}+F_{h}(U_{h})=0\!\,$

其中 $U_{h}\in \mathbb {R} ^{m}\!\,$ 表示近似解的未知节点值向量， $A\!\,$ 是一个 $m\times m\!\,$ 矩阵，其元素与离散参数 $h\!\,$ 无关，并且 $F_{h}:\mathbb {R} ^{m}\rightarrow \mathbb {R} ^{m}\!\,$ 是一个非线性的向量值函数。

解决方案 5

寻找弱形式

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

用测试函数 $v\in V\!\,$ 乘以原方程并进行分部积分，我们得到

\int _{0}^{1}(-u''v)dx=\int _{0}^{1}u'v'dx-\left.u'v\right|_{0}^{1}=\int _{0}^{1}u'v'dx\!\,

因此变分形式为：寻找 $u\in V\!\,$ 使得

a(u,v)=\int _{0}^{1}u'v'dx+\int _{0}^{1}e^{u}vdx=l(v)=0\!\,

对所有的

v\in V\!\,

定义分段线性基函数

考虑区间 $[0,1]\!\,$ 的一个划分，

{\mathcal {\tau }}_{h}:0=x_{0}<x_{1}<\dots <x_{m+1}=1\!\,

.

将我们的有限元空间设为

V_{h}=\{v\in V:\left.v\right|_{[x_{i-1},x_{i}]}\in {\mathcal {P}}_{1}([x_{i-1},x_{i}]),i=1,\dots ,m+1,v(0)=v(1)=0\}\!\,

.

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

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

因此，

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

因此离散公式变为：求解 $u_{h}\in V_{h}\!\,$ 使得

a(u_{h},v_{h})=\int _{0}^{1}u_{h}'v_{h}'dx+\int _{0}^{1}e^{u_{h}}v_{h}dx=0,\forall v_{h}\in V_{h}\!\,

.

由于 $\{\phi _{j}\}_{j=1}^{m}\!\,$ 是 $V_{h}\!\,$ 的一个基，我们有

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

.

然后，我们得到以下等价的离散问题：求解 $u_{h}=(u_{h1},\ldots ,u_{hm})^{t}\!\,$ 使得

a(u_{h},\phi _{i})=\sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0{\mbox{ for }}i=1,\dots ,m\!\,

.

将问题改写成矩阵形式

针对 $i=1,2,\ldots ,m\!\,$ 的等价离散问题

$\sum _{j=1}^{m}u_{hj}\int _{x_{i-1}}^{x_{i+1}}\phi _{j}'\phi _{i}'dx+\int _{x_{i-1}}^{x_{i+1}}e^{\sum _{j=1}^{m}u_{hj}\phi _{j}}\phi _{i}dx=0\!\,$

可以改写成以下矩阵形式

$\underbrace {\begin{bmatrix}{\frac {2}{h}}&-{\frac {1}{h}}&&\ldots \\\ddots &\ddots &\ddots &\\&-{\frac {1}{h}}&{\frac {2}{h}}&-{\frac {1}{h}}\\&&-{\frac {1}{h}}&{\frac {2}{h}}\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{h1}\\\vdots \\\vdots \\u_{hm}\end{bmatrix}} _{U_{h}}+\underbrace {h{\begin{bmatrix}e^{u_{h1}}\\e^{u_{h2}}\\\vdots \\e^{u_{hm}}\end{bmatrix}}} _{F_{h}(U_{h})}\!\,$

第一个积分可以计算如下

${\begin{aligned}\int _{0}^{1}\phi _{j}'\phi _{i}'&={\begin{cases}{\frac {2}{h}}&{\mbox{for }}i=j\\-{\frac {1}{h}}&{\mbox{for }}|i-j|=1\\0&{\mbox{otherwise}}\end{cases}}\end{aligned}}\!\,$

第二个积分可以使用梯形法则近似，即

${\begin{aligned}\int _{x_{i-1}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)&=\int _{x_{i-1}}^{x_{i}}e^{u_{h}}\phi _{i}(x)+\int _{x_{i}}^{x_{i+1}}e^{u_{h}}\phi _{i}(x)\\&\approx \left({\frac {e^{u_{h}(x_{i-1})}\overbrace {\phi _{i}(x_{i-1})} ^{0}+e^{u_{h}(x_{i})}\phi _{i}(x_{i})}{2}}\right)h+\left({\frac {e^{u_{h}(x_{i})}\phi _{i}(x_{i})+e^{u_{h}(x_{i+1})}\overbrace {\phi _{i}(x_{i+1})} ^{0}}{2}}\right)h\\&=he^{u_{h}(x_{i})}\overbrace {\phi _{i}(x_{i})} ^{1}\\&=he^{u_{h}(x_{i})}\\&=he^{\sum _{j=1}^{m}u_{hj}\phi _{j}(x_{i})}\\&=he^{u_{hi}}\end{aligned}}\!\,$

注意到边界条件规定 $u_{h0}=u_{h(m+1)}=0\!\,$ 。

问题 6

确定两步格式的局部精度阶数和稳定性性质

$x_{i+2}-3x_{i+1}+2x_{i}=\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]\!\,$

作为常微分方程 $x'(t)=f(t,x)\!\,$ 的近似方法。其收敛速度是多少？

解题 6

局部精度阶

请注意 $x_{i}\approx x(t_{i})\!\,$ 。另外，我们将均匀步长 $\Delta t\!\,$ 记作 h。因此，

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

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

因此，给定方程可以写成

$x(t_{i}+2h)-3x(t_{i}+h)+2x(t_{i})\approx h\left[{\frac {13}{12}}x'(t_{i}+2h)-{\frac {5}{3}}x'(t_{i}+h)-{\frac {5}{12}}x'(t_{i})\right]\!\,$

使用泰勒展开式展开左手边

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

${\begin{array}{|c|c|c|c|c|}{\mbox{Order}}&x(t_{i}+2h)&-3x(t_{i}+h)&2x(t_{i})&\Sigma \\\hline &&&&\\0&x(t_{i})&-3x(t_{i})&2x(t_{i})&0\\&&&&\\1&2x'(t_{i})h&-3x'(t_{i})h&0&-x'(t_{i})h\\&&&&\\2&{\frac {4}{2!}}x''(t_{i})h^{2}&-{\frac {3}{2!}}x''(t_{i})h^{2}&0&{\frac {1}{2}}x''(t_{i})h^{2}\\&&&&\\3&{\frac {8}{3!}}x'''(t_{i})h^{3}&-{\frac {3}{3!}}x'''(t_{i})h^{3}&0&{\frac {5}{6}}x'''(t_{i})h^{3}\\&&&&\\4&{\mathcal {O}}(h^{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}}$

比较项以确定阶数

对左右两边泰勒展开式求差，可以看出该二步方程是二阶的，因为直到二阶项为止都匹配上了。

$x_{i+2}-3x_{i+1}+2x_{i}-\Delta t\cdot \left[{\frac {13}{12}}f(t_{i+2},x_{i+2})-{\frac {5}{3}}f(t_{i+1},x_{i+1})-{\frac {5}{12}}f(t_{i},x_{i})\right]={\mathcal {O}}(\Delta t^{3})\!\,$