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

问题 4a

描述牛顿法寻找光滑函数 $f:R\rightarrow R\!\,$ 的根的方法。

解答 4a

牛顿法

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

问题 4b

假设 $f:R\rightarrow R\!\,$ 是一个光滑函数，满足 $f'(x)>0,\quad f''(x)>0,\quad {\mbox{ for all }}x\in R\!\,$ 并且有一个根 $x^{*}\!\,$。绘制一张几何图，说明该方法的收敛性，并给出牛顿法对于任何初始猜测 $x_{0}\in R\!\,$ 收敛到 $x^{*}\!\,$ 的解析证明。

解答 4b

从图中可以看出，如果 $x_{k}<x_{*}\!\,$，则经过一步后 $x_{k+1}\!\,$ 将大于 $x_{*}\!\,$。这是因为根据假设，该函数始终递增且向上凹。

然后不妨假设 $x_{k}>x_{*}\!\,$。

从牛顿法的两边减去 $x_{*}\!\,$，得到了连续误差之间关系的表达式。

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

将$f(x_{k})\!\,$在$f(x_{*})\!\,$处展开，使用泰勒展开得到

$f(x_{k})=\underbrace {f(x_{*})} _{0}+f'(\xi )\underbrace {(x_{k}-x_{*})} _{e_{k}}\!\,$

其中$\xi \in [x_{*},x_{k}]\!\,$

将这个表达式代入 (*)，得到

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

由于$f'(x)>0\!\,$且始终递增（根据假设），$M\!\,$是一个小于 1 的正数。因此，随着$k\!\,$的增加，误差会减小，这意味着该方法始终收敛。

问题 5

这个问题的目标是在合适的有限元空间中求解边值问题 $-u''=f{\mbox{ on }}(0,1),\quad u(0)=0,u(1)=0\!\,$ 在合适的有限元空间中。

问题 5a

对于 $N\in \mathbb {N} \!\,$，令 $x_{i}=i/N,i=0,\ldots ,N\!\,$。定义一个合适的 $N-1\!\,$ 维子空间 $V_{N}\!\,$ 在 $H_{0}^{1}\!\,$ 中与点 $x_{i}\!\,$ 相关联。令 $\phi _{1},\ldots ,\phi _{N-1}\!\,$ 是 $V_{N}\!\,$ 中的任意基。解释如何确定系数 $u_{i}\!\,$ 在表示元素解中的 $u_{N}=\sum _{i=1}^{N-1}u_{i}\phi _{i}\!\,$ 通过解线性方程组。证明存在唯一解

解 5a

定义合适的子空间

$V_{N}=\{v\in H_{0}^{1}[0,1]:v{\mbox{ piecewise linear}}\}\!\,$

它有一个基函数，即帽子函数 $\{\phi _{i}\}_{i=1}^{N-1}\!\,$，定义如下

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

如何确定系数

离散弱变分形式给出如下

找到 $u_{N}\in V_{N}\!\,$ 使得对于所有的 $v\in V_{N}\!\,$

$\underbrace {\int _{0}^{1}u_{N}'v_{N}'} _{a(u_{N},v_{N})}=\underbrace {\int _{0}^{1}fv_{N}} _{F(v_{N})}\!\,$

由于我们有一个基 $\{\phi _{i}\}_{i=1}^{N-1}\!\,$，我们有一个方程组（可以用矩阵形式表示）

对于 $j=1,2,\ldots ,N-1\!\,$

$\sum _{i=1}^{N-1}u_{i}\int _{0}^{1}\phi _{i}\phi _{j}=\int _{0}^{1}f\phi _{j}\!\,$

唯一解的存在性

唯一解的存在性来自 Lax-Milgram 定理。

注意以下几点

• 双线性形式连续（有界）例如 $a(u_{N},v_{N})\leq \|u_{N}\|_{1}\|v_{N}\|_{1}\!\,$

${\begin{aligned}a(u,v)&=\int u'v'\\&\leq |u|_{1}|v|_{1}{\mbox{ Cauchy Schwartz in L2 }}\\&\leq \|u\|_{1}\|v\|_{1}{\mbox{ dominance of spaces }}\end{aligned}}\!\,$

• 双线性形式强制性，例如 $a(u_{N},u_{N})\geq C\|u_{N}\|_{1}^{2}\!\,$

${\begin{aligned}a(v,v)&=\int v'^{2}\\&=|v|_{1}^{2}\\&\geq C\|v\|_{1}^{2}{\mbox{ Poincare inequality}}\end{aligned}}\!\,$

Poincare 不等式：$\|v\|_{0}\leq \|v\|_{1}\leq C|v|_{1}\!\,$

• $F(v_{N})\leq C\|v_{N}\|_{1}\!\,$

${\begin{aligned}\int fv&\leq \|f\|_{0}\|v\|_{0}\\&\leq \|f\|_{1}\|v\|_{1}\end{aligned}}\!\,$

问题 5b

证明 $a(u,v)=\int _{0}^{1}u'v'dx\!\,$ 在 $H_{0}^{1}\!\,$ 上定义了一个内积，因此在 $H_{0}^{1}\!\,$ 中定义了一个正交的概念。

问题 5b 的解答

• $a(u,v)=a(v,u)\!\,$

• $a(\alpha u,v)=\int \alpha u'v'=\alpha \int u'v'=\alpha a(u,v)\!\,$

• $a(u+w,v)=\int (u'+w')v'=\int u'v'+\int w'v'=a(u,v)+a(w,v)\!\,$

• $a(u,u)=\int u'^{2}\neq 0{\mbox{ if }}u\neq 0\!\,$

问题 5c

令 $\phi _{1}=1-2|x-{\frac {1}{2}}|\!\,$ 是 一维空间 $V_{2}\!\,$ 的基函数。在 $V_{4}\!\,$ 中找到包含基函数 $\phi _{1}\!\,$ 的正交基。绘制基函数。说明你将如何构建包含 $V^{2^{n-1}}\!\,$ 基函数的 $V_{2^{n}}\!\,$ 基。

Solution 5c

$\phi _{1}={\begin{cases}2x&{\mbox{ for }}x\in [0,{\frac {1}{2}}]\\2-2x&{\mbox{ for }}x\in [{\frac {1}{2}},1]\end{cases}}\!\,$

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

$\phi _{3}={\begin{cases}8(x-{\frac {1}{2}})&{\mbox{ for }}x\in [{\frac {1}{2}},{\frac {3}{4}}]\\-8(x-1)&{\mbox{ for }}x\in [{\frac {1}{4}},1]\\0&{\mbox{ otherwise }}\end{cases}}\!\,$

在每个新相邻子区间上定义一个新的帽子函数。这些帽子函数的高度应该与前一个基底的帽子函数相同。

问题 5d

对于这个特殊的基底，(a) 中线性方程组的结构是什么？

解答 5d

对于我们在 (a) 中的系统，该系统产生一个对角矩阵。

问题 6

为了求解方程 $y'=f(x,y)\!\,$，考虑如下方案 $y_{n+1}=y_{n}+{\frac {h}{2}}(y_{n}'+y'_{n+1})+{\frac {h^{2}}{12}}(y''_{n}-y''_{n+1})\!\,$ 其中 $y_{n}'=f(x_{n},y_{n})\!\,$ 且 $y_{n}''=f_{x}(x_{n},y_{n})+f(x_{n},y_{n})f_{y}(x_{n},y_{n})\!\,$

问题 6a

证明该方案是四阶精度的。

解答 6a

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

问题 6b

为了进行稳定性分析，我们令 $f(x,y)=\lambda y\!\,$。说明对于该方案，${\overline {\lambda }}=h\lambda \!\,$ 属于绝对稳定区域的含义，并证明该方案的绝对稳定区域包含整个负实轴。

解 6b

$y_{n}''={\frac {d}{dx}}\lambda y+\lambda y{\frac {d}{dy}}\lambda y=\lambda ^{2}y\!\,$

$y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h^{2}}{12}}[\lambda ^{2}y_{n}-\lambda ^{2}y_{n+1}]\!\,$

令 $z=h\lambda \!\,$ 并重新排列项得到

$y_{n+1}=\underbrace {\left({\frac {1+{\frac {z}{2}}+{\frac {z^{2}}{12}}}{1-{\frac {z}{2}}+{\frac {z^{2}}{12}}}}\right)} _{M}y_{n}\!\,$

如果 $z\!\,$ 是负实数，则 $M<1\!\,$