数值方法资格考试试题及解答 (马里兰大学)/Aug08 667

问题 4a

证明二步法 $y_{n+1}=2y_{n-1}-y_{n}+h[{\frac {5}{2}}f(x_{n},y_{n})+{\frac {1}{2}}f(x_{n-1},y_{n-1})]\qquad (1)\!\,$ 是二阶的，但不满足根条件。

解答 4a

二阶方法

方法 $(1)\!\,$ 找到 $y\!\,$ 的近似值，使得 $y'=f(x,y)\!\,$.

令 $x_{n}=a_{0}+hn\!\,$ 为第 $n\!\,$ 个评估点，其中 $a_{0}\!\,$ 是起点，$h\!\,$ 是步长。

关于 a_0 的 y' 的泰勒展开

${\begin{aligned}y'(x_{n})&=y'(a_{0}+hn)\\&=y'(a_{0})+hny''(a_{0})+h^{2}n^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y'(x_{n-1})&=y'(a_{0}+h(n-1))\\&=y'(a_{0})+h(n-1)y''(a_{0})+h^{2}(n-1)^{2}y'''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}$

将上述结果代入公式 $(1)\!\,$ 右侧的第二项，并简化得到

${\begin{aligned}h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]&={\frac {5}{2}}[hy'(a_{0})+h^{2}ny''(a_{0})+{\mathcal {O}}(h^{3})]+{\frac {1}{2}}[hy'(a_{0})+h^{2}(n-1)y''(a_{0})+{\mathcal {O}}(h^{3})]\\&=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\end{aligned}}\!\,$

y 关于 a_0 的泰勒展开

由于 $y_{n}\approx y(x_{n})\!\,$，我们也对 $y\!\,$ 关于 $a_{0}\!\,$ 进行泰勒展开

${\begin{aligned}y(x_{n+1})&=y(a_{0})+h(n+1)y'(a_{0})+h^{2}(n+1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n})&=y(a_{0})+hny'(a_{0})+h^{2}n^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\\\\\\y(x_{n-1})&=y(a_{0})+h(n-1)y'(a_{0})+h^{2}(n-1)^{2}y''(a_{0})/2+{\mathcal {O}}(h^{3})\end{aligned}}$

代入并简化得到，

$y_{n+1}+y_{n}-2y_{n-1}=3hy'(a_{0})+{\frac {1}{2}}(6n-1)y''(a_{0})+{\mathcal {O}}(h^{3})\!\,$

取泰勒展开式的差

因此 $y_{n+1}+y_{n}-2y_{n-1}-h[{\frac {5}{2}}y'(x_{n})+{\frac {1}{2}}y'(x_{n-1})]={\mathcal {O}}(h^{3})\!\,$ 表明 (1) 是一种二阶方法。

不满足根条件

方程 (1) 的特征方程为

$\lambda ^{2}+\lambda -2=0\!\,$

得到根

$\lambda _{1}=1\!\,$

$\lambda _{2}=-2\!\,$

$\lambda _{2}\!\,$ 显然不满足 $|\lambda _{j}|\leq 1\!\,$

问题 4b

举例说明方法 (1) 在求解 $y'=f(x,y)\!\,$ 时，可能不会收敛。

解题 4b

令 $f(x,y)=0,y(0)=y_{0}=1\!\,$。则 $y(t)=1\!\,$。我们得到差分方程

$y_{n+1}+y_{n}-2y_{n-1}=0\!\,$

它的通解为（使用根）：

$y_{n}=C_{1}(-2)^{n}+C_{2}\cdot 1^{n}\!\,$

如果 $C_{1}\neq 0\!\,$，那么 $y_{n}\rightarrow \infty \!\,$ 当 $n\rightarrow \infty \!\,$

$y_{0}=C_{1}+C_{2}\!\,$

$y_{1}=-2C_{1}+C_{2}\!\,$

因此， ${\frac {y_{0}-y_{1}}{3}}=C_{1}\!\,$。因此，如果 $y_{0}\neq y_{1}\!\,$，那么 $C_{1}\neq 0\!\,$。

问题 5

考虑边界值问题 $-u''+(1+x)u=x^{2}\quad u'(0)=1,u(1)=1\qquad (2)\!\,$

问题 5a

证明 $(2)\!\,$ 最多只有一个解

解 5a

令 $u_{1}\!\,$ 和 $u_{2}\!\,$ 为解。令 $u\equiv u_{1}-u_{2}\!\,$.

通过减去两个方程及其条件，我们有

$-u''+(1+x)u=0\quad u'(0)=0,u(1)=0\!\,$

用测试函数 $v\in V=\{v\in H^{1}:v(1)=0\}\!\,$ 乘，并从 0 到 1 进行分部积分，我们需要找到 $u\in V\!\,$ 使得对于所有 $v\in V\!\,$

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

令 $v=u\!\,$。然后，我们有

$\int _{0}^{1}(u')^{2}+\int _{0}^{1}(1+x)u^{2}=0\!\,$

由于 $(u')^{2}\!\,$，$(1+x)\!\,$ 以及 $u^{2}\!\,$ 都为 $>0\!\,$，$u^{2}=0\!\,$。因此 $u_{1}=u_{2}\!\,$.

问题 5b

将问题离散化。对 $[0,1]:\!\,$ 进行均匀划分 $x_{i}=ih,i=0,1,2,\ldots ,n,\quad h={\frac {1}{n}}\!\,$ 使用三点差分公式计算 $u''\!\,$，并使用最简单的差分公式计算 $x=0\!\,$ 处的边界条件。将所得系统写成矩阵向量方程 $Ax=b\!\,$，其中 $x=(u_{1},u_{2},\cdots ,u_{n-1})^{T}\!\,$

解题 5b

三点差分公式计算 $u''\!\,$ 为

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

i=2,...,n-2 的方程

将差分公式代入 $(2)\!\,$，在矩阵形式中，我们得到

${\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+ih)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{i-1}\\u_{i}\\u_{i+1}\end{bmatrix}}=(ih)^{2}$

i = 1 时的方程

我们可以使用近似值消除 $u_{0}\!\,$ 变量

$u'(0)={\frac {u_{1}-u_{0}}{h}}=1\!\,$

这意味着

$u_{0}=u_{1}-h\!\,$

使用这种关系和三个差分公式，我们有

${\begin{bmatrix}{\frac {1}{h^{2}}}+(1+h)&&&-{\frac {1}{h^{2}}}\end{bmatrix}}{\begin{bmatrix}u_{1}\\u_{2}\end{bmatrix}}=h^{2}-{\frac {1}{h}}\!\,$

i = n - 1 时的方程

由于 $u(1)=u_{n}=1\!\,$，我们可以通过代入到 n-1 方程中来消除 $u_{n}\!\,$ 变量。

${\begin{bmatrix}-{\frac {1}{h^{2}}}&&&{\frac {2}{h^{2}}}+(1+(n-1)h)\end{bmatrix}}{\begin{bmatrix}u_{n-2}\\u_{n-1}\end{bmatrix}}=h^{2}-((n-1)h)^{2}+{\frac {1}{h^{2}}}$

问题 5c

证明在 $(b)\!\,$ 中找到的方程有一个唯一解

解决方案 5c

由于矩阵 $A\!\,$ 是对角占优的，所以系统 $Ax=b\!\,$ 有唯一的解。

问题 5d

将问题 $(2)\!\,$ 转化为具有齐次边界条件的等价问题。

解 5d

令 $u\!\,$ 是边界值问题的解，表示为两个不同边界值问题的解之和，即

$u=w+v\!\,$ 其中

$-w''+(1+x)w=f(x)\quad w'(0)=0,w(1)=0\!\,$

$-v''+(1+x)v=g(x)\quad v'(0)=1,v(1)=1\qquad (*)\!\,$

$-u''+(1+x)u=x^{2}=f(x)+g(x)\quad u'(0)=1,u(1)=1\!\,$

假设 $v(x)=ax+b\!\,$。然后

$v'(0)=a=1\!\,$ 以及 $v(1)=1+b=1\!\,$，这意味着 $b=0\!\,$，因此

$v(x)=x\!\,$

代入 $(*)\!\,$，我们有

$-0+(1+x)x=g(x)\!\,$

这意味着

$g(x)=x^{2}+x\!\,$

由于 $f(x)+g(x)=x^{2}\!\,$，我们有 $f(x)=-x\!\,$

因此，一个具有齐次边界条件的等效边值问题由下式给出：

$-w''+(1+x)w=-x\quad w'(0)=0,w(1)=0\!\,$

问题 5e

获得在 $(d)\!\,$ 中制定的问题的变分公式。指定所涉及的索伯列夫空间 $H\!\,$。证明此问题具有唯一解，我们用 $v\!\,$ 表示。

解答 5e

变分公式和索伯列夫空间

使用问题的符号，我们要找到 $v\in H=\{w\in H^{1}:w(1)=0\}\!\,$，使得对于所有 $w\in H\!\,$，我们有：

$a(v,w)=\int _{0}^{1}v'w'+\int _{0}^{1}(1+x)vw=-\int _{0}^{1}xw=F(w)\!\,$

上述结果来自分部积分和应用边界条件。

唯一解

为了表明 $v\!\,$ 是唯一的，我们证明 Lax-Milgram 定理的假设得到满足。

a(v,w) 有界且连续

${\begin{aligned}a(v,w)&=\int _{0}^{1}v'w'+\int _{0}^{1}\underbrace {(1+x)} _{\leq 2}vw\\&\leq 2\left[\int _{0}^{1}v'w'+\int _{0}^{1}vw\right]\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}\right]^{\frac {1}{2}}+\left[\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]\quad {\mbox{ Cauchy-Schwartz in L2 }}\\&\leq 2\left[\left[\int _{0}^{1}v'^{2}+\int _{0}^{1}v^{2}\right]^{\frac {1}{2}}\left[\int _{0}^{1}w'^{2}+\int _{0}^{1}w^{2}\right]^{\frac {1}{2}}\right]{\mbox{ Cauchy-Schwartz in R2 }}\\&=2\|w\|_{1}\|v\|_{1}\end{aligned}}\!\,$

a(v,v) 协ercive

${\begin{aligned}a(v,v)&=\int _{0}^{1}v'^{2}+\int _{0}^{1}\underbrace {(1+v)} _{\geq 1}v^{2}\\&\geq \int _{0}^{1}v'^{2}+\int v^{2}\\&=\|v\|_{1}^{2}\end{aligned}}$

F(v) 有界

$|F(v)|=|-\int _{0}^{1}xv|\leq |\int _{0}^{1}v|\leq \|v\|_{1}^{2}\!\,$

问题 5f

考虑使用分段线性有限元逼近 $v\!\,$。精确地定义分段线性有限元子空间（使用分区 (3)）。证明有限元问题有唯一解。

问题 5g

证明 $\|v-v_{h}\|_{H}\leq Ch\!\,$，并指出常数 $C\!\,$ 如何依赖于 $v\!\,$ 的导数。

问题 6

令 $f:\mathbb {R} \to \mathbb {R} \!\,$ 为一个非线性函数，零点为 $x_{*}\!\,$ $f(x,y)={\begin{bmatrix}x^{2}-2x+y\\2x-y^{2}-1\end{bmatrix}}\!\,$，$x_{*}={\begin{bmatrix}1\\1\end{bmatrix}}\!\,$. 考虑迭代 $x_{n+1}=x_{n}-Af(x_{n})\!\,$，$A={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}\qquad (4)\!\,$.

问题 6a

证明 (4) 是局部收敛的。

解答 6a

$\phi (x_{n}):=x_{n+1}=x_{n}-Af(x_{n})\!\,$ 是一个不动点迭代。根据压缩映射定理，如果 $\phi (x)\!\,$ 在 $x_{*}\!\,$ 的某个邻域内是压缩映射，则该迭代至少线性收敛。

我们需要证明存在一个$\gamma <1\!\,$，使得$\|\phi (x)-\phi (y)\|\leq \gamma \|x-y\|\!\,$。

根据中值定理，我们有$\|\phi (x)-\phi (y)\|\leq \|D\phi (\xi )\|\|x-y\|\!\,$，即$\gamma =D\phi (\xi )\!\,$，其中$\xi \!\,$ 在$x_{*}\!\,$ 的邻域内。

特别地，$\|D\phi (x_{*})\|=\|I-AD\phi (x_{*})\|=0<1\!\,$，这意味着$\phi (x)\!\,$ 是一个压缩映射，并且迭代方法至少以线性速度收敛。

计算雅可比矩阵

$D\phi =Dx-ADf\!\,$

$Dx=I\!\,$

$Df={\begin{pmatrix}2x-2&1\\2&-2y\end{pmatrix}}\!\,$

${\begin{aligned}D\phi (x_{*})&=I-AD\phi (x_{*})\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&{\frac {1}{2}}\\1&0\end{pmatrix}}{\begin{pmatrix}2(1)-2&1\\2&-2(1)\end{pmatrix}}\\&={\begin{pmatrix}1&0\\0&1\end{pmatrix}}-{\begin{pmatrix}1&0\\0&1\end{pmatrix}}\\&={\begin{pmatrix}0&0\\0&0\end{pmatrix}}\\\|D\phi (x_{*})\|&=0\end{aligned}}$

$\!\,$

问题 6b

证明收敛速度至少为二次。

解题 6b

${\begin{aligned}e_{n+1}&=x_{n+1}-x_{*}\\&=\underbrace {x_{n}-Af(x_{n})} _{\phi (x_{n})}-x_{*}\\&=\phi (x_{n})-x_{*}\\&=\left(\phi (x_{*})+(x_{n}-x_{*})^{T}\underbrace {D_{\phi }(x_{*})} _{0}+(x_{n}-x_{*})^{T}{\frac {H_{\phi }(x_{*})}{2!}}(x_{n}-x_{*})+R(x_{n},x_{*})\right)-x_{*}\\&=\left(x_{*}+A\underbrace {f(x_{*})} _{0}+{\frac {H_{\phi }(x_{*})}{2!}}\underbrace {(x_{n}-x_{*})^{T}(x_{n}-x_{*})} _{e_{n}^{2}}+R(x_{n},x_{*})\right)-x_{*}\\&\leq Ce_{n}^{2}+R(x_{n},x_{*})\end{aligned}}\!\,$

其中 $R(x_{n},x_{*})\!\,$ 满足 ${\frac {\|R(x_{n},x_{*})\|}{\|x_{n}-x_{*}\|}}\rightarrow 0\!\,$ 当 $\|x_{n}-x_{*}\|\rightarrow 0\!\,$.

然后，我们得到 $\|e_{n+1}\|\leq C\|e_{n}\|^{2}\!\,$.

问题 6c

写出牛顿迭代并将其与 (4) 进行比较。

解答 6c

牛顿迭代如下所示

$x_{n+1}=x_{n}-B(x_{n})f(x_{n})\!\,$

${\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}={\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}-\underbrace {{\begin{bmatrix}2x_{n}-2&1\\2&-2y_{n}\end{bmatrix}}^{-1}} _{B}{\begin{bmatrix}x_{n}^{2}-2x_{n}+y_{n}\\2x_{n}-y_{n}^{2}-1\end{bmatrix}}$

其中 B 是 f 的雅可比矩阵的逆矩阵。

$B(x_{*})={\begin{bmatrix}2(1)-2&1\\2&-2(1)\end{bmatrix}}^{-1}={\begin{bmatrix}0&1\\2&-2\end{bmatrix}}^{-1}={\begin{bmatrix}1&{\frac {1}{2}}\\1&0\end{bmatrix}}=A$

也就是说，$B(x_{*})\!\,$ 在牛顿迭代中给出 (4)。