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

问题 4

考虑用隐式方法求解非线性常微分方程组问题 $y'=f(t,y)\!\,$ 第 $n\!\,$ 步包括求解未知数 $y\!\,$，其形式为非线性代数方程组 $y=\alpha hf(t_{n},y)+g_{n-1}\quad (1)\!\,$ 其中 $g_{n-1}\in \mathbb {R} ^{n}\!\,$ 已知，$\alpha >0\!\,$ 且 $h\!\,$ 是步长。令 $f\in C^{1}\!\,$

问题 4a

将 $(1)\!\,$ 写成不动点迭代，并找到 $h\!\,$ 和 $f(t_{n},y)\!\,$ 的条件，使得该迭代在

ononon

解答 4a

不动点迭代

等式 $(1)\!\,$ 非常适合用固定点迭代法求解。

$y_{n}^{j+1}=\underbrace {\alpha hf(t_{n},y_{n}^{j})+g_{n-1}} _{\phi (y_{n}^{j})}\!\,$

注意，等式右侧仅是 $y_{n}^{j}\!\,$ 的函数，因为 $\alpha ,h,t_{n},g_{n-1}\!\,$ 在求解固定点 $y_{n}^{*}\!\,$ 时是固定的，其中 $\phi (y_{n}^{*})=y_{n}^{*}\!\,$

还要注意，$j\!\,$ 是固定点迭代的索引。

局部收敛条件

当 $\phi \!\,$ 的雅可比矩阵的范数小于 1 时，固定点迭代将收敛，即

$\|D(\phi )\|<1\!\,$

由于 $\|D(\phi )\|=\|\alpha hD(f)\|\!\,$，我们等效地得到条件

$\|D(f)\|<{\frac {1}{\alpha h}}\!\,$

问题 4b

写出$(1)\!\,$ 的牛顿迭代，并给出关于$h\!\,$ 和 $f(t_{n},y)\!\,$ 的条件，以保证该迭代的局部收敛。给出关于$f\!\,$ 的精确附加假设，以保证二次收敛。

解 4b

牛顿迭代

牛顿迭代用来求解$\psi (y)=0\!\,$，迭代公式为

$y_{i+1}=y_{i}-D(\psi (y_{i}))^{-1}\psi (y_{i})\!\,$

设 $\psi (y)=y-\phi (y)\!\,$

局部收敛条件

如果$D(\psi (y))^{-1}\!\,$ 存在，即$D(\psi (y))\!\,$ 可逆，或等价地是非奇异的，那么局部收敛就得到了保证。

注意

$D(\psi (y))=I-D(\phi (y))\!\,$

二次收敛的条件

如果$D(\psi (y))\!\,$ 是 Lipschitz 连续的，那么我们有二次收敛，并且$\psi (y)\!\,$ 在根的邻域内是两次连续可微的。

问题 5

这个问题是关于为求解 ODE 选择特定的单步法和特定的多步法。 $y'=f(t,y)\!\,$

问题 5a

写出梯形法，定义其局部截断误差并估计它。

解 5a

梯形方法（隐式，Adams-Moulton）

$y_{n+1}=y_{n}+{\tfrac {1}{2}}h{\big (}f(t_{n+1},y_{n+1})+f(t_{n},y_{n}){\big )}\!\,$

定义局部截断误差

局部截断误差如下所示

${\mbox{error}}=(y(t_{n+1})-y(t_{n}))-{\tfrac {1}{2}}h{\big (}f(t_{n+1},y(t_{n+1}))+f(t_{n},y_{n}){\big )}\!\,$

使用泰勒展开式求局部截断误差

注意 $y_{i}\approx y(t_{i})\!\,$. 均匀步长为 $h\!\,$. 因此，

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

因此，给定方程可以写成

$y(t_{i}+h)-y(t_{i})\approx {\frac {1}{2}}h(y'(t_{i}+h)+y'(t_{n}))\!\,$

展开左边

关于 $t_{n}\!\,$ 展开，我们得到

${\begin{array}{|c|c|c|c|}{\mbox{Order}}&y(t_{n}+h)&-y(t_{n})&\Sigma \\\hline &&&\\0&y(t_{n})&-y(t_{n})&0\\&&&\\1&y'(t_{n})h&0&y'(t_{n})h\\&&&\\2&{\frac {1}{2!}}y''(t_{n})h^{2}&0&{\frac {1}{2}}y''(t_{n})h^{2}\\&&&\\3&{\frac {1}{3!}}y'''(t_{n})h^{3}&0&{\frac {1}{6}}y'''(t_{n})h^{3}\\&&&\\4&{\mathcal {O}}(h^{4})&0&{\mathcal {O}}(h^{4})\\&&&\\\hline \end{array}}$

展开右手边

同样地，关于 $t_{n}\!\,$ 展开得到

${\begin{array}{|c|c|c|c|}{\mbox{Order }}h&{\frac {1}{2}}hy'(t_{n}+h)&{\frac {1}{2}}hy'(t_{n})&\Sigma \\\hline &&&\\0&0&0&0\\&&&\\1&{\frac {1}{2}}h\cdot y'(t_{n})&{\frac {1}{2}}hy'(t_{n})&y'(t_{n})h\\&&&\\2&{\frac {1}{2}}h\cdot y''(t_{n})h&0&{\frac {1}{2}}y''(t_{n})h^{2}\\&&&\\3&{\frac {1}{2}}h\cdot {\frac {y'''}{2}}(t_{n})h^{2}&0&{\frac {y'''}{4}}(t_{n})h^{3}\\&&&\\4&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})&{\mathcal {O}}(h^{4})\\\hline \end{array}}$

计算局部截断误差

由于 $h\!\,$ 的 3 阶项不一致 (${\frac {y'''(t_{n})}{6}}h^{3}\neq {\frac {y'''(t_{n})}{4}}h^{3}\!\,$)，误差为 $h^{2}\!\,$ 阶。

问题 5b

证明以下多步法的截断误差与 (a) 中的截断误差同阶 $y_{n+1}=2y_{n}-y_{n-1}-hf(t_{n-1},y_{n-1})+hf(t_{n},y_{n})\!\,$

解 5b

我们需要证明 $y(t_{n+1})-2y(t_{n})+y(t_{n-1})+hy'(t_{n-1})-hy'(t_{n})={\mathcal {O}}(h^{3})\!\,$

再次注意，${\begin{aligned}t_{n+1}&=t_{n}+h\\t_{n-1}&=t_{n}-h\end{aligned}}\!\,$

${\begin{array}{|c|c|c|c|c|c|c|}{\mbox{Order of }}h&y(t_{n}+h)&-2y(t_{n})&y(t_{n}-h)&hy'(t_{n}-h)&-hy'(t_{n})&\Sigma \\\hline 0&y(t_{n})&-2y(t_{n})&y(t_{n})&0&0&0\\&&&&&&\\1&y'(t_{n})h&0&-y'(t_{n})h&y'(t_{n})h&-y'(t_{n})&0\\&&&&&&\\2&{\frac {1}{2}}y''(t_{n})h^{2}&0&{\frac {1}{2}}y''(t_{n})h^{2}&-y''(t_{n})h^{2}&0&0\\&&&&&&\\3&{\frac {1}{6}}y'''(t_{n})h^{3}&0&-{\frac {1}{6}}y'''(t_{n})h^{3}&{\frac {1}{2}}y'''(t_{n})h^{3}&0&{\frac {1}{2}}y'''(t_{n})h^{3}\\&&&&&&\\\hline \end{array}}$

因此，该方法也是二阶一致的。

问题 5c

对于这两种方法，我们可以说些什么关于全局收敛速度？证明您的结论。

解决方案 5c

梯形法是稳定的，因为它满足根条件。（特征方程的根为 1，并且只有一个简单根。）

第二种方法不稳定，因为特征方程有一个 1 的二重根。

梯形法和第二种方法都与 $h^{2}\!\,$ 一致。

注意，收敛发生当且仅当方法既稳定又一致。

因此，梯形法一般情况下会收敛，而第二种方法不会。mkmkmkmlmklml

问题 6

考虑边界值问题 $L(u)=-u''+bu=f,\;\;x\in I\equiv [0,1],\;\;u(0)=u(1)=0\qquad (2)\!\,$ 其中 $b\geq 0\!\,$ 是常数。 令 $\{0=x_{0}<x_{1}<\dots <x_{n}=1\}\!\,$ 是一个具有均匀网格间距 $h\!\,$ 的网格。 令 $V_{h}=\{v\in C[0,1]:\left.v\right|_{[x_{i-1},x_{i}]}{\mbox{ is linear for each i, }}v(0)=v(1)=0\}\!\,$ 为相应的有限元空间，令 $u_{h}=R_{h}(u)\!\,$ 为 (2) 的相应有限元解。 注意， $R_{h}\!\,$ 是一个投影算子，即瑞兹投影，投影到有限维空间 $V_{h}\!\,$ 上，该空间相对于由问题 (2) 诱导的元素标量积 $a(\cdot ,\cdot )\!\,$。

问题 6a

令 $|\cdot |_{1}\!\,$ 为 $H^{1}\!\,$-半范数，即对所有 $v\in H_{0}^{1}(I)\!\,$，有 $|v|_{1}^{2}=\int _{I}|v'|^{2}\!\,$。求常数 $\Lambda \!\,$，用参数 $b\!\,$ 表示，使得 $|u_{h}|_{1}\leq \Lambda |u|_{1}\!\,$ 提示：回顾 Poincaré 不等式 $\|v\|_{0}\leq {\frac {1}{2}}|v|_{1}\!\,$ 对所有 $v\in H_{0}^{1}(I)\!\,$ 成立，其中 $\|\cdot \|_{0}\!\,$ 表示 $L^{2}\!\,$-范数

解 6a

弱形式

对所有 $v\in V\!\,$，用分部积分得到

$\int u'v'+b\int uv=\int fv\!\,$

具体来说，

$\int u'u_{h}'+b\int uu_{h}=\int fu_{h}\!\,$

离散形式（有限元公式）

类似地，有限元公式是找到$u_{h}\in V_{h}\!\,$ 使得对于所有 $v_{h}\in V_{h}\!\,$

$\int u_{h}'v_{h}'+b\int u_{h}v_{h}=\int fv_{h}\!\,$

具体来说，

$\int u_{h}'u_{h}'+b\int u_{h}u_{h}=\int fu_{h}\!\,$

等式两边并应用不等式

${\begin{aligned}\int _{0}^{1}u_{h}'u_{h}'+b\int _{0}^{1}u_{h}u_{h}&=\int _{0}^{1}u'u_{h}'+b\int _{0}^{1}uu_{h}\\&\leq |u|_{1}|u_{h}|_{1}+b\|u\|_{0}\|u_{h}\|_{0}{\mbox{ Cauchy-Schwartz}}\\&\leq |u|_{1}|u_{h}|_{1}+b{\frac {1}{2}}|u|_{1}{\frac {1}{2}}|u_{h}|_{1}{\mbox{ Poincare}}\\&=|u_{h}|_{1}(1+{\frac {b}{4}})|u|_{1}\end{aligned}}$

因此我们有：

${\begin{aligned}|u_{h}|_{1}^{2}\leq |u_{h}|_{1}^{2}+b\|u_{h}\|_{0}^{2}&\leq |u_{h}|_{1}(1+{\frac {b}{4}})|u|_{1}\\|u_{h}|_{1}^{2}&\leq |u_{h}|_{1}(1+{\frac {b}{4}})|u|_{1}\\|u_{h}|_{1}&\leq (1+{\frac {b}{4}})|u|_{1}\end{aligned}}$

问题 6b

如果 $I_{h}u\in V_{h}\!\,$ 是 $u\!\,$ 的拉格朗日插值，证明 $R_{h}(I_{h}u)=I_{h}u\!\,$。推断 $|u_{h}-I_{h}u|_{1}\leq \Lambda |u-I_{h}u|_{1}\!\,$

解答 6b

证明等式

对于所有 $v\in H_{0}^{1}(0,1)\!\,$

$a(u,v)=\int u'v'dx+b\int uvdx=\int fv\!\,$

特别地，对于所有 $v_{h}\in V_{h}\!\,$

$a(u,v_{h})=\int u'v_{h}'dx+b\int uv_{h}dx=\int fv_{h}\quad \quad (1)\!\,$

能量标积的离散形式对所有 $u_{h},v_{h}\in V_{h}\!\,$

$a(u_{h},v_{h})=\int u_{h}'v_{h}'dx+b\int u_{h}v_{h}dx=\int fv_{h}\quad \quad (2)\!\,$

从公式(1)中减去公式(2), 我们有

$a(u-u_{h},v_{h})=0\!\,$

令 $R_{h}(I_{h}u)={\overline {u_{h}}}\in V_{h}\!\,$. 注意根据假设 $I_{h}u\in V_{h}\!\,$. 然后,

$a(I_{h}u-{\overline {u_{h}}},I_{h}u-{\overline {u_{h}}})=0\!\,$

根据椭圆性,

$0=a(I_{h}u-{\overline {u_{h}}},I_{h}u-{\overline {u_{h}}})\geq \alpha \|I_{h}u-{\overline {u_{h}}}\|^{2}\!\,$

这意味着

$I_{h}u-{\overline {u_{h}}}=0\!\,$

即

$I_{h}u={\overline {u_{h}}}\!\,$

推导出不等式

因此我们有

$R_{h}(u-I_{h}u)=u_{h}-I_{h}u\!\,$

与 (a) 部分类似，我们有

$|u_{h}-I_{h}u|_{1}\leq \Lambda |u-I_{h}u|_{1}\!\,$

问题 6c

利用 (b) 推导出误差估计 $|u-u_{h}|_{1}\leq (1+\Lambda )|u-I_{h}u|_{1}\!\,$ 并用 $h\!\,$ 的适当幂来对右端进行限制。明确说明 $u\!\,$ 所需的正则性。

解 6c

证明不等式

${\begin{aligned}|u-u_{h}|_{1}&=|u-I_{h}u+I_{h}u-u_{h}|_{1}\\&\leq |u-I_{h}u|_{1}+|I_{h}u-u_{h}|_{1}\\&\leq |u-I_{h}u|_{1}+\Lambda |u-I_{h}u|_{1}\\&=(1+\Lambda )|u-I_{h}u|_{1}\end{aligned}}$

限制右端

对于 $x\in [x_{i-1},x_{i}]\!\,$，牛顿多项式插值误差给出了某个 $\xi _{i}\in [x_{i-1},x_{i}]\!\,$

${\begin{aligned}|u-I_{h}u|_{1}^{2}&=\left|{\frac {u^{(2)}(\xi _{i})}{2}}(x-x_{i})(x-x_{i-1})\right|_{1}^{2}dx\\&=\int _{0}^{1}\left(\left[{\frac {u^{(2)}(\xi _{i})}{2}}(x-x_{i})(x-x_{i-1})\right]'\right)^{2}\\&=\left({\frac {u^{(2)}(\xi _{i})}{2}}\right)^{2}\int _{0}^{1}[\underbrace {(x-x_{i-1})} _{\leq h}\underbrace {(x-x_{i})} _{\leq h}]dx\\&\leq (u^{(2)}(\xi _{i})h)^{2}\end{aligned}}\!\,$

因此，整个区间上的误差由下式给出：

${\begin{aligned}|u-I_{h}u|_{1}^{2}&\leq \sum _{i=1}^{n}(u^{(2)}(\xi _{i})h)^{2}\\&\leq \max _{0<\xi <1}(u^{(2)}(\xi )h)^{2}\cdot n\end{aligned}}\!\,$

这意味着

$|u-I_{h}u|_{1}\leq \max _{0<\xi <1}u^{(2)}(\xi _{i}){\sqrt {n}}h\!\,$

$u\!\,$ 需要二阶可微。