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

问题 4

设 $\mathbf {f:} \mathbb {R} ^{n}\rightarrow \mathbb {R} ^{n}\!\,$ ，假设 $\mathbf {f} (x^{*})=0\!\,$ ，并假设 $\mathbf {f'} (x^{*})\!\,$ 是非奇异的。考虑以下迭代

$x_{k+1}=x_{k}-B_{k}^{-1}\mathbf {f} (x_{k}),\qquad (k\geq 0)\!\,$

问题 4a

推导出以下关于 $e_{k+1}=x_{k+1}-x^{*}\!\,$ 的误差方程

$e_{k+1}=B_{k}^{-1}\left((B_{k}-\mathbf {f'} (x^{*}))e_{k}-\int _{0}^{1}(\mathbf {f'} (sx_{k}+(1-s)x^{*})-\mathbf {f'} (x^{*}))e_{k}\,ds\right)\!\,$

解答 4a

注意以下恒等式

F(x)-F(y)=\int _{0}^{1}F'(sx+(1-s)y)(x-y)ds\qquad (*)\!\,

误差 $e_{k+1}\!\,$ 由下式给出

${\begin{aligned}e_{k+1}&=x_{k+1}-x_{*}\\&=\underbrace {x_{k}-x_{*}} _{e_{k}}-B_{k}^{-1}f(x_{k})\\&=e_{k}-B_{k}^{-1}(f(x_{k})-\underbrace {f(x_{*})} _{0})\\&=B_{k}^{-1}\left\{(B_{k}-f'(x_{*}))e_{k}-\int _{0}^{1}\left[f'(sx_{k}+(1-s)x_{*})-f'(x_{*})\right]e_{k}ds\right\}\\\end{aligned}}$

问题 4b

令 $B_{k}=B\in \mathbb {R} ^{n\times n}\!\,$ 是一个固定矩阵。找出关于 B 的条件，以保证局部收敛。你期望的收敛速度是多少，为什么？

解 4b

假设 $B\!\,$ 是可逆的， $\|B-f'(x_{*})\|\!\,$ 是有界的，并且 $f'\!\,$ 是 Lipschitz 连续的。

${\begin{aligned}\|e_{k+1}\|&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|\|e_{k}\|-\int _{0}^{1}\underbrace {\|f'(sx_{k}+(1-s)x_{*})-f'(x_{*})\|} _{\leq L\|sx_{k}+(1-s)x_{*}-x_{*}\|}\|e_{k}\|ds\right\}\\&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|\|e_{k}\|-\int _{0}^{1}L\|e_{k}\|^{2}sds\right\}\\&\leq \|B^{-1}\|\left\{\|B-f'(x_{*})\|-{\frac {L}{2}}\|e_{k}\|\right\}\|e_{k}\|\end{aligned}}$

这意味着局部超线性收敛。

问题 4c

找到关于 $\|B_{k}-\mathbf {f'} (x_{k})\|\!\,$ 的充分条件，使收敛变为超线性。选择哪个 $B_{k}\!\,$ 对应于牛顿法，你期望什么收敛速度？

解 4c

超线性收敛

${\frac {\|e_{k+1}\|}{\|e_{k}\|}}\rightarrow 0\!\,$ 当 $k\rightarrow \infty \!\,$

找到超线性收敛的条件

从部分 (b)

${\frac {\|e_{k+1}\|}{\|e_{k}\|}}\leq \|B_{k}^{-1}\|\{\|B_{k}-f'(x_{*})\|-{\frac {L}{2}}\|e_{k}\|\}\!\,$

由于 $\|e_{k}\|\rightarrow 0{\mbox{ as }}k\rightarrow \infty \!\,$ ，如果

$\|B_{k}-f'(x_{*})\|\rightarrow 0\!\,$

当 $k\rightarrow 0\!\,$ ，我们有超线性收敛，即

$B_{k}=f'(x_{k}){\mbox{ Newton Iteration form}}\!\,$

问题 5

令 $f(t,y)\!\,$ 关于 $y$ 一致 Lipschitz。令 $y(t)\!\,$ 是以下初值问题的解： $y'=f(t,y),\;y(0)=y_{0}\!\,$ 。考虑梯形法

$(1)\qquad y_{i+1}=y_{i}+{h \over 2}\left(f(t_{i},y_{i})+f(t_{i+1},y_{i+1})\right),\qquad (i\geq 0)\!\,$ .

问题 5a

找到关于步长 $h\!\,$ 的条件，以确保 (1) 可以关于 $y_{i+1}\!\,$ 唯一求解。

解 5a

该隐式方法可以看作是一个不动点迭代

$y_{i+1}=\underbrace {y_{i}+{\frac {h}{2}}(f(t_{i},y_{i})+f(t_{i+1},y_{i+1}))} _{g(y_{i+1})}\!\,$

我们需要 $\left|{\frac {\partial g(y_{i+1})}{\partial y_{i+1}}}\right|<1\!\,$

这意味着

$h<{\frac {2}{\left|{\frac {\partial f(t_{i+1},y_{i+1})}{\partial y_{i+1}}}\right|}}\!\,$

问题 5b

定义局部截断误差并进行估计。检查 $f\!\,$ 所需的额外正则性以进行此估计。

解决方案 5b

重写 (1) 并用 $y_{k}{\mbox{ with }}y(t_{k}){\mbox{ and }}f(t_{k},y_{k}){\mbox{ with }}y'(t_{k})\!\,$ 代替，我们得到阶为 p 的一致性公式

$y(t_{i+1})-y(t_{i})-{h \over 2}y'(t_{i})-{h \over 2}y(t_{i+1})={\mathcal {O}}(h^{p+1})\!\,$

对于均匀步长 h

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

关于 $t_{i}\!\,$ 的泰勒级数展开给出

问题 5c

证明 (1) 的全局误差估计

解决方案 5c

问题 6

考虑二点边值问题

$(2)\qquad -au''+bu=f(x),\quad 0<x<1,\qquad u(0)=u_{0},\,u(1)=u_{1}\!\,$ ,

其中 $a,b>0\!\,$ 为常数， $f\in C[0,1]\!\,$ 。令 ${\mathcal {P}}=\{x_{i}\}_{i=0}^{n+1}\!\,$ 是 [0,1] 的均匀划分，其网格大小为 $h\!\,$ 。

问题 6a

使用中心有限差分法对 (2) 进行离散化。将系统写成

$A\mathbf {U} =\mathbf {F} \!\,$

并确定 $A\in \mathbb {R} ^{n\times n}{\mbox{ and }}\mathbf {U} ,\mathbf {F} \in \mathbb {R} ^{n}\!\,$ 。证明 A 是非奇异的。

解答 6a

使用泰勒展开式，我们可以近似二阶导数如下

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

我们可以通过将初始条件 $u(0)=u_{0},u(1)=u_{1}\!\,$ 代入 $U_{1}\!\,$ 和 $U_{n}\!\,$ 的方程中，从 n+2 个方程中消去两个方程。

然后我们有系统

$\underbrace {\begin{bmatrix}{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&&&&\\-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&&&\\&-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b&-{\frac {a}{h^{2}}}&&\\&&\ddots &\ddots &\ddots &\\&&&&-{\frac {a}{h^{2}}}&{\frac {2a}{h^{2}}}+b\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}U_{1}\\U_{2}\\U_{3}\\\vdots \\U_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}f(x_{1})+{\frac {a}{h^{2}}}u_{0}\\f(x_{2})\\f(x_{3})\\\vdots \\f(x_{n})+{\frac {a}{h^{2}}}u_{1}\end{bmatrix}} _{F}\!\,$

矩阵 $A\!\,$ 是非奇异的，因为它是对角占优的。

问题 6b

定义截断误差，并根据 $h\!\,$ 推导出该方法的误差界限。不加证明地给出如下形式的误差估计

$\max _{1\leq i\leq n}|u(x_{i})-U_{i}|\leq Ch^{s}\!\,$

并指定阶数 s。

解答 6b

局部截断误差

$LTE={\frac {u(x_{i}+h)+u(x_{i}-h)-2u(x_{i})}{h^{2}}}-u''(x_{i})={\frac {u^{(4)}(\xi )}{12}}h^{2}\!\,$

局部截断误差的界限

${\frac {1}{12}}\|u^{(4)}\|_{\infty }h^{2}\!\,$

推导出最大误差的界限

令 $L=-a\partial _{xx}+b\!\,$ ， $L_{h}=A\!\,$ ，以及 $R_{h}\!\,$ 是局部截断误差。

然后

${\begin{aligned}Lu&=f\\L_{h}u&=f+R_{h}\\L_{h}U&=f\end{aligned}}\!\,$

减去最后两个方程得到

$L_{h}(u-U)=R_{h}\!\,$

因此，

$\|u-U\|_{\infty }\leq \|L_{h}^{-1}\|\|R_{h}\|\!\,$

$\|u-U\|_{\infty }\leq Ch^{2}\!\,$ ，也就是说误差是二阶的。

问题 6c

证明以下离散单调性：如果 $\mathbf {U} _{i}\!\,$ 是对应于强迫 $f_{i}\!\,$ 的解，对于 $i=1,2\!\,$ ，并且 $f_{1}\leq f_{2}\!\,$ ，则 $\mathbf {U} _{1}\leq \mathbf {U} _{2}\!\,$ 按成分排列。