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

问题 5a

说明牛顿法，用于近似求解

f(x)=0\!\,

其中 $f(x)\!\,$ 是实变量 $x\!\,$ 的实值函数

解答 5a

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}\!\,$

问题 5b

说明并证明该方法的收敛结果。

解答 5b

${\begin{aligned}x_{k+1}&=x_{k}-f'(x_{k})^{-1}f(x_{k})\\\underbrace {x_{k+1}-x_{*}} _{e_{k+1}}&=\underbrace {x_{k}-x_{*}} _{e_{k}}-f'(x_{k})^{-1}f(x_{k})\\&=f'(x_{k})^{-1}[f'(x_{k})e_{k}-(f(x_{k})-\underbrace {f(x_{*})} _{0}))\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-e_{k}\int _{0}^{1}f'(sx_{k}+(1-s)x_{*})ds\right]\\&=f'(x_{k})^{-1}\left[f'(x_{k})e_{k}-f'(x_{*})e_{k}-e_{k}\int _{0}^{1}(f'(sx_{k}+(1-s)x_{*})-f'(x_{*}))ds\right]\\\|e_{k+1}\|&\leq \|f'(x_{k})^{-1}\|\left[L\|e_{k}\|^{2}+{\frac {L}{2}}\|e_{k}\|^{2}\right]{\mbox{ where L is Lipschitz constant of }}f'\\&=\|f'(x_{k})^{-1}\|{\frac {3}{2}}L\|e_{k}\|^{2}\end{aligned}}\!\,$

问题 5c

典型的收敛阶数是多少？是否存在收敛阶数更高的情况？解释你的答案。

解答 5c

局部收敛的典型阶数是二次。

将牛顿法视为一个不动点迭代，即

$x_{k+1}=\underbrace {x_{k}-{\frac {f(x_{k})}{f'(x_{k})}}} _{g(x_{k})}\!\,$

那么

$g'(x_{k})=1-{\frac {f'(x_{k})^{2}-f'(x_{k})f(x_{k})}{f'(x_{k})^{2}}}\!\,$

$g'(x_{*})=0\!\,$

将 $g(x_{k})\!\,$ 在 $x_{*}\!\,$ 处展开得到误差表达式

$\underbrace {g(x_{k})} _{x_{k+1}}=\underbrace {g(x_{*})} _{x_{*}}+\underbrace {g'(x_{*})} _{0}e_{k}+{\frac {g''(x_{*})}{2}}e_{k}^{2}+{\frac {g'''(\xi )}{6}}e_{k}^{3}\!\,$

注意，如果 $g''(x_{*})=0\!\,$ ，那么我们得到比二次收敛更快的收敛速度。

问题 6

考虑边界值问题

{\begin{cases}-u''(x)+u(x)=f(x),0\leq x\leq 1\\u'(0)=2,u(1)=0\end{cases}}\qquad (1)\!\,

问题 6a

推导出 (1) 的变分公式。

解答 6a

求 $u\in H\!\,$ 使得对于所有 $v\in H=\{v\in H^{1}[0,1]:v(1)=0\}\!\,$

$\underbrace {\int _{0}^{1}u'v'dx+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}fv-2v(0)} _{f(v)}\!\,$

问题 6b

有限元近似指的是什么？ $u_{h}\!\,$ 对 $u\!\,$

解 6b

令 $P=\{x_{i}\}_{i=0}^{N}\!\,$ 是 $[0,1]\!\,$ 的一个划分。选择一个合适的离散子空间 $V_{h}\!\,$ 和基函数 $\{\phi _{i}\}_{i=0}^{N}\!\,$ 。然后

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

系数 $u_{hi}\!\,$ 可以通过求解以下方程组来找到

对于 $j=0,1,\ldots ,N\!\,$

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

问题 6c

给出并证明对以下内容的估计

$\|u-u_{h}\|_{1}\equiv \left(\int _{0}^{1}|u(x)-u_{h}(x)|^{2}dx+\int _{0}^{1}|u'(x)-u_{h}'(x)|^{2}dx\right)^{\frac {1}{2}}\!\,$

解 6c

Cea 引理

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

特别是选择 $v_{I}\!\,$ 为 $u\!\,$ 的线性插值。

然后,

$\|u-u_{h}\|\leq C\|u''\|_{\infty }h\!\,$

解 6c 的另一种解法

令 $\{x_{k}\}_{0}^{n}$ 为 $[0,1]$ 的离散网格，步长为 $h$ 。考虑以下积分

$\int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx$ .

对于某个 $\xi _{k}\in [x_{k},x_{k+1}]$ ， $u(x)-u_{h}(x)=u'(\xi _{k})*h$ 因为 $u_{h}$ 在此区间上只是一个线性插值。因此

$\int _{x_{k}}^{x_{k+1}}|u(x)-u_{h}(x)|^{2}dx=\int _{x_{k}}^{x_{k+1}}h^{2}u'(\xi _{k})^{2}dx=h^{3}u'(\xi _{k})^{2}\leq h^{3}||u'||_{\infty }$ .

类似地，我们可以用 $h^{3}||u''||_{\infty }$ 对导数误差的 $L_{2}(x_{k},x_{k}+h)$ 范数进行界定。当有 $n=1/h$ 个这样的区间时，我们有

$\ ||u-u_{h}\||^{2}\leq 2nh^{3}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2})=2h^{2}\max(||u'||_{\infty }^{2},||u''||_{\infty }^{2}).$

问题 6d

证明公式

$\|u-u_{h}\|_{1}^{2}=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\!\,$

解答 6d

${\begin{aligned}\underbrace {a(u-u_{h},u-u_{h})} _{\|u-u_{h}\|_{1}^{2}}+2\underbrace {a(u-u_{h},u_{h})} _{0}&=a(u,u)-2a(u,u_{h})+a(u_{h},u_{h})+2a(u,u_{h})-2a(u_{h},u_{h})\\&=a(u,u)-a(u_{h},u_{h})\\&=\|u\|_{1}^{2}-\|u_{h}\|_{1}^{2}\end{aligned}}\!\,$

问题 7

考虑初值问题

y'=f(t,y),\quad y(t_{0})=y_{0}\!\,

其中 $f\!\,$ 满足 Lipschitz 条件

|f(t,y)-f(t,z)|\leq L|y-z|\!\,

对于所有 $t,y,z\!\,$ 。用于求解此问题的称为中点规则的数值方法定义为

y_{n+1}=y_{n-1}+2hf(t_{n},y_{n})\!\,

其中 $h\!\,$ 是时间步长，而 $y_{n}\approx y(t_{n})\!\,$ 对于 $t_{n}=t_{0}+nh\!\,$ 。这里 $y_{0}\!\,$ 是给定的，而 $y_{1}\!\,$ 假设用其他方法计算。

问题 7a

假设问题在一个有限区间 $t_{0}\leq t\leq b\!\,$ 上提出，其中 $h={\frac {(b-t_{0})}{M}}\!\,$ 。直接证明，即不引用任何主要结果，中点法是稳定的。也就是说，证明如果 ${\hat {y_{0}}}\!\,$ 和 ${\hat {y_{1}}}\!\,$ 满足

|y_{0}-{\hat {y_{0}}}|\leq \epsilon ,\quad |y_{1}-{\hat {y_{1}}}|\leq \epsilon \!\,

那么存在一个常数 $C\!\,$ 与 $h\!\,$ 无关，使得

|y_{n}-{\hat {y_{n}}}|\leq C\epsilon \!\,

对于 $0\leq n\leq M\!\,$

解 7a

${\begin{aligned}y_{n+1}&=y_{n-1}+2hf(t_{n},y_{n})\\{\hat {y}}_{n+1}&={\hat {y}}_{n-1}+2hf(t_{n},{\hat {y}}_{n})\end{aligned}}$

将两个方程相减，令 $e_{n}\equiv y_{n}-{\hat {y}}_{n}\!\,$ ，并应用Lipschitz性质，得到：

${\begin{aligned}e_{n+1}&\leq e_{n-1}+2hLe_{n}\\&\leq (1+2hL)\max\{e_{n},e_{n-1}\}\end{aligned}}\!\,$

因此：

${\begin{aligned}e_{n}&\leq (1+2hL)^{n-1}\epsilon \\&\leq (1+2hL)^{n}\epsilon \\&\leq e^{2Lhn}\epsilon \\&\leq e^{2L(t_{n}-t_{0})}\epsilon \end{aligned}}\!\,$