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

问题4a

给定一个光滑函数$f(x)\!\,$，说明割线法用于求解$\mathbb {R} \!\,$ 中非线性方程的近似解。 $f(x)=0\!\,$

解答4a

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

问题4b

说明此方法的收敛阶数，并解释如何推导出它。

解答4b

如果$f''(x)\!\,$ 有界且 $x_{0}\!\,$ 接近 $x_{*}\!\,$，则割线法的收敛阶数为$\phi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.6180339887\!\,$（黄金分割率）。

部分证明可以在这里找到。

问题4c

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

问题5

考虑初始值问题 $y'=f(t,y),\quad y(0)=y_{0}\!\,$

问题 5a

将 ODE 写成积分形式，并解释如何使用梯形求积公式推导出具有均匀时间步长 $h={\frac {T}{N}}\!\,$ 的梯形方法。 $y_{n+1}=y_{n}+{\frac {h}{2}}(f(t_{n+1},y_{n+1})+f(t_{n},y_{n}))\!\,$

解 5a

$y(t_{n+1})-y(t_{n})=\int _{t_{n}}^{t_{n+1}}y'=\int _{t_{n}}^{t_{n+1}}f(t,y)\approx {\frac {h}{2}}(f(t_{n+1},y_{n+1})+f(t_{n},y_{n}))\!\,$

问题 5b

定义绝对稳定性的概念。也就是说，考虑将该方法应用于 $f(t,y)=\lambda y\!\,$，其中 $\lambda \!\,$ 为实数。证明绝对稳定区域包含复数 $h\lambda \!\,$ 平面的整个负实轴。

解 5b

令 $f(t,y)=\lambda y\!\,$，我们有

$y_{n+1}=y_{n}+{\frac {h}{2}}\lambda y_{n+1}+{\frac {h}{2}}\lambda y_{n}\!\,$

如果我们令 $h\lambda =z\!\,$，并对该方程进行重新排列，我们得到

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

我们需要 $M<1\!\,$。如果 $\lambda \!\,$ 是一个负实数，则该条件成立。

问题 5c

假设 $f(t,y)=Ay\!\,$，其中 $A\in R^{n\times n}\!\,$ 是一个对称矩阵，并且 $y\in R^{n}\!\,$。检验 $A\!\,$ 的哪些属性保证了该方法是绝对稳定的（提示：研究 $A\!\,$ 的特征值）。

解答 5

我们现在希望得到的是

$\left\|{\frac {1+{\frac {h}{2}}A}{1-{\frac {h}{2}}A}}\right\|<1\!\,$

即

$\|1+{\frac {h}{2}}A\|<\|1-{\frac {h}{2}}A\|\!\,$

或者（由于 $A\!\,$ 是对称的）

$\rho (I+{\frac {h}{2}}Q\Lambda Q^{T})<\rho (I-{\frac {h}{2}}Q\Lambda Q^{T})\!\,$

或者（由于乘以正交矩阵不会影响范数）

$\rho (I+{\frac {h}{2}}\Lambda )<\rho (I-{\frac {h}{2}}\Lambda )\!\,$

或者（根据定义）

$\max _{i}\{1+{\frac {h}{2}}\lambda _{i}\}<\max _{i}\{1-{\frac {h}{2}}\lambda _{i}\}\!\,$

如果 $A\!\,$ 是负定的（所有特征值都为负），上述不等式成立。

问题 6

考虑在 $(0,1):\!\,$ 中的以下两点边值问题： $(1)\qquad -u_{xx}+u=1,\quad u'(0)=u'(1)=0\!\,$

问题 6a

给出 (1) 的变分形式，即将其表达为 $(2)\qquad u\in H:a(u,v)=F(v),{\mbox{ for all }}v\in H\!\,$ 定义函数空间 $H\!\,$、双线性形式 $a\!\,$ 和线性泛函 $F\!\,$ 并说明 $(1)\!\,$ 和 $(2)\!\,$ 之间的联系。证明解 $u\!\,$ 是唯一的。

解 6a

变分形式

通过用测试函数 $v\in H\!\,$ 乘以并从 0 到 1 积分来推导出变分形式。使用分部积分并代入初始条件，则有

找到 $u\in H=\{v\in H^{1}(0,1)\}\!\,$ 使得对于所有 $v\in H\!\,$

$\underbrace {\int _{0}^{1}u'v'+\int _{0}^{1}uv} _{a(u,v)}=\underbrace {\int _{0}^{1}v} _{F(v)}\!\,$

（1）和（2）之间的关系

（2）是（1）的等效公式，但它不涉及二阶导数。

唯一解的存在性

根据 Lax-Milgram 定理，我们有唯一解的存在性。

• 双线性形式连续/有界：$a(u,v)\leq C\|u\|_{1}\|v\|_{1}\!\,$

• 双线性形式强制性：$a(u,u)\geq 1\cdot \|u\|_{1}^{2}\!\,$

• 泛函有界：$F(v)\leq \|v\|_{1}\!\,$

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

问题 6b

使用分段线性元素在均匀划分 $P=\{x_{i}=(i-1)h\}_{i=1}^{N}\!\,$ 上写出有限元方法，网格大小为 $h={\frac {1}{N-1}}\!\,$。如果 $U=(u_{i})_{i=1}^{N}\!\,$ 是有限元解的节点值向量，求刚度矩阵 $A\!\,$ 和右端项 $F\!\,$，使得 $AU=F\!\,$。证明 $A\!\,$ 是对称正定的。证明解 $U\!\,$ 是唯一的。

解 6b

定义帽子函数 $\{\phi _{i}\}_{i=1}^{N}\!\,$ 作为离散空间的基。注意 $\phi _{0}\!\,$ 和 $\phi _{n}\!\,$ 的支撑范围只有其他基函数的一半。使用此基，我们有

$\underbrace {\begin{bmatrix}{\frac {h}{3}}+{\frac {1}{h}}&{\frac {h}{6}}-{\frac {1}{h}}&&&&&\\{\frac {h}{6}}-{\frac {1}{h}}&{\frac {2}{3}}h+{\frac {2}{h}}&{\frac {h}{6}}-{\frac {1}{h}}&&&&\\&\ddots &\ddots &\ddots &&&\\&&&&&{\frac {h}{6}}-{\frac {1}{h}}&{\frac {h}{3}}+{\frac {1}{h}}\end{bmatrix}} _{A}\underbrace {\begin{bmatrix}u_{1}\\u_{2}\\\vdots \\u_{n}\end{bmatrix}} _{U}=\underbrace {\begin{bmatrix}{\frac {h}{2}}\\h\\\vdots \\{\frac {h}{2}}\end{bmatrix}} _{F}\!\,$

观察到 $A\!\,$ 是对称的。根据格尔欣定理，它是正定的。解 $U\!\,$ 是唯一的，因为 $A\!\,$ 是对角占优的。

问题 6c

考虑 $[0,1]\!\,$ 的两个划分 $P_{1}\!\,$ 和 $P_{2}\!\,$，其中 $P_{2}\!\,$ 是 $P_{1}\!\,$ 的细化。令 $V_{1}\!\,$ 和 $V_{2}\!\,$ 为相应的分段线性有限元空间。证明 $V_{1}\!\,$ 是 $V_{2}\!\,$ 的子空间。

解 6c

如果 $v\in V_{1}\!\,$，那么它也在 $V_{2}\!\,$ 中，因为 $P_{2}\!\,$ 是 $P_{1}\!\,$ 的细化。换句话说，由于 $V_{1}\!\,$ 在每个区间上是分段线性的，它在细化后的区间上也是分段线性的。

问题 6d

令 $u_{1}\in V_{1}\!\,$ 和 $u_{2}\in V_{2}\!\,$ 是有限元解。证明正交性等式。 $\|u-u_{1}\|_{H^{1}}^{2}=\|u-u_{2}\|_{H^{1}}^{2}+\|u_{1}-u_{2}\|_{H^{1}}^{2}\!\,$

解答 6

从误差的正交性，我们有

$a(u-u_{h},v_{h})=0\!\,$ 对于所有 $v\in V_{h}\!\,$

具体来说，

$a(u-u_{2},u_{1}-u_{2})=0\!\,$

然后

$\underbrace {a(u-u_{1},u-u_{1})} _{\|u-u_{1}\|_{H^{1}}^{2}}+2\underbrace {a(u-u_{2},u_{1}-u_{2})} _{0}=\underbrace {a(u-u_{2},u-u_{2})} _{\|u-u_{2}\|_{H^{1}}^{2}}+\underbrace {a(u_{1}-u_{2},u_{1}-u_{2})} _{\|u_{1}-u_{2}\|_{H^{1}}^{2}}\!\,$