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

问题1

给定 $f\in C[a,b]\!\,$ ，令 $p_{n}^{*}\!\,$ 表示对 $f\!\,$ 在度数为 $\leq n\!\,$ 的多项式中的最佳一致逼近，即

\max _{x\in [a,b]}|f(x)-p_{n}(x)|\!\,

通过选择 $p_{n}=p_{n}^{*}\!\,$ 最小化。令 $e(x)=f(x)-p_{n}^{*}(x)\!\,$ 。证明至少存在两个点 $x_{1},x_{2}\in [a,b]\!\,$ ，使得

|e(x_{1})|=|e(x_{2})|=\max _{x\in [a,b]}|f(x)-p_{n}^{*}(x)|\!\,

并且 $e(x_{1})=-e(x_{2})\!\,$

解答1

由于 $f(x)\!\,$ 和 $p_{n}^{*}(x)\!\,$ 都是连续函数，因此函数

e(x)=f(x)-p_{n}^{*}(x)\!\,

也是连续函数，因此 $e(x)\!\,$ 在区间 $[a,b]\!\,$ 上存在最大值和最小值。

设 $M=\max _{x\in [a,b]}e(x)\!\,$ 和 $m=\min _{x\in [a,b]}e(x)\!\,$

如果 $M\neq -m\!\,$ ，则存在一个多项式 $q(x)=p_{n}^{*}(x)+{\frac {M+m}{2}}\!\,$ （假设的最佳逼近 $p_{n}^{*}(x))\!\,$ 的垂直平移），它是对 $f(x)\!\,$ 更好的逼近。

${\begin{aligned}f(x)-q(x)&=f(x)-p_{n}^{*}(x)-{\frac {M+m}{2}}\\&\leq M-{\frac {M+m}{2}}\\&={\frac {M-m}{2}}\\\\\\f(x)-q(x)&\geq m-{\frac {M+m}{2}}\\&={\frac {m-M}{2}}\end{aligned}}\!\,$

因此，

$\|f(x)-q(x)\|\leq {\frac {M-m}{2}}\leq \|f-p_{n}^{*}\|=M\!\,$

当且仅当 $m=-M\!\,$ 时，等式成立。

问题 2a

求节点 $x_{1}\!\,$ 和权重 $w_{1}\!\,$ ，使得积分规则

$I=\int _{0}^{1}x^{-{\frac {1}{2}}}f(x)dx\approx w_{1}f(x_{1})\!\,$

对线性函数精确。（不需要正交多项式的知识。）

解 2a

令 $f(x)=1\!\,$ 。则

$\int _{0}^{1}{\frac {1}{x^{\frac {1}{2}}}}=w_{1}\cdot 1\!\,$

计算后得到

$w_{1}=2\!\,$

令 $f(x)=x\!\,$ 。则

$\int _{0}^{1}{\frac {x}{x^{\frac {1}{2}}}}=w_{1}\cdot x_{1}=2x_{1}\!\,$

计算后得到

$x_{1}={\frac {1}{3}}\!\,$

问题 2b

证明对于近似 $I\!\,$ ，不存在任何一点规则可以对二次函数精确。

解 2b

假设存在一个用于近似 $I\!\,$ 的一点规则，该规则对二次函数精确。

令 $f(x)=x^{2}\!\,$ 。

然后，

$\int _{0}^{1}{\frac {x^{2}}{x^{\frac {1}{2}}}}={\frac {2}{5}}\!\,$

但是

$w_{1}x_{1}^{2}=2({\frac {1}{3}})^{2}={\frac {2}{9}}\!\,$ ,

这是一个矛盾。

问题 2c

事实上

$I-w_{1}f(x_{1})=cf''(\xi ){\mbox{ for some }}\xi \in [0,1]\!\,$

求 $c\!\,$ 。

解答 2c

令 $f(x)=x^{2}\!\,$ 。则 $f''(x)=2\!\,$

利用在(b)部分计算的值，我们有

${\frac {2}{5}}-{\frac {2}{9}}=c\cdot 2\!\,$

这意味着

$c={\frac {4}{45}}\!\,$

问题 2d

令 $f(x)\!\,$ 和 $g(x)\!\,$ 为两个次数小于等于 $3\!\,$ 的多项式。假设 $f\!\,$ 和 $g\!\,$ 在 $x=a\!\,$ ， $x=b\!\,$ 和 $x=(a+b)/2\!\,$ 处相等。证明

$\int _{a}^{b}f(x)dx=\int _{a}^{b}g(x)dx\!\,$

解法 2d

存在 $w_{1},w_{2},w_{3}\!\,$ 使得如果 $f(x)\!\,$ 是一个次数小于等于 $3\!\,$ 的多项式

$\int _{a}^{b}f(x)dx=w_{1}f(a)+w_{2}f(b)+w_{3}f({\frac {a+b}{2}})\!\,$

因此，

${\begin{aligned}\int _{a}^{b}f(x)dx&=w_{1}f(a)+w_{2}f(b)+w_{3}f({\frac {a+b}{2}})\\&=w_{1}g(a)+w_{2}g(b)+w_{3}g({\frac {a+b}{2}})\\&=\int _{a}^{b}g(x)dx\end{aligned}}\!\,$

问题 3

设 $A\in R^{n\times n}\!\,$ 为非奇异矩阵，且 $b\in R^{n}\!\,$ 。考虑以下用于求解 $Ax=b\!\,$ 的迭代：

$x_{k+1}=x_{k}+\alpha (b-Ax_{k})\!\,$

问题 3a

证明如果 $A\!\,$ 的所有特征值都具有正实部，则存在某个实数 $\alpha \!\,$ 使得对于任何起始向量 $x_{0}\!\,$ ，迭代都收敛。讨论在 $A\!\,$ 为对称矩阵的情况下如何最优地选择 $\alpha \!\,$ ，并确定收敛速度。

解答 3a

任何起始向量的收敛性

使用迭代 $\,\!x_{k+1}=x_{k}+\alpha (b-Ax_{k})$ ，我们得到

${\begin{aligned}e_{k+1}&=x_{k+1}-x^{*}\\&=x_{k}-x^{*}+\alpha (b-Ax_{k})\\&=x_{k}-x^{*}+\alpha (Ax^{*}-Ax_{k})\\&=e_{k}-\alpha Ae_{k}\\&=(I-\alpha A)e_{k}\end{aligned}}$

然后，计算范数得到

$\,\!\|e_{k+1}\|\leq \|I-\alpha A\|\|e_{k}\|$ .

特别是，考虑 $\,\!\|\cdot \|_{2}$ ，我们有

$\,\!\|e_{k+1}\|_{2}\leq \|I-\alpha A\|_{2}\|e_{k}\|_{2}$ .

现在，为了研究该方法的收敛性，我们需要分析 $\,\!\|I-\alpha A\|_{2}$ 。我们使用以下特征

${\begin{aligned}\|I-\alpha A\|_{2}^{2}&=\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)\\&=\rho \left(I-\alpha A^{*}-\alpha A+|\alpha |^{2}AA^{*}\right)\end{aligned}}$

让我们用 $\,\!\lambda$ 表示矩阵 $\,\!A$ 的一个特征值。然后 $\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)<1\,\!$ 意味着

$1-2\alpha Re(\lambda )+\alpha ^{2}|\lambda |^{2}<1\!\,$

即

$-2\alpha Re(\lambda )+\alpha ^{2}|\lambda |^{2}<0\!\,$

上述方程关于 $\alpha \!\,$ 是二次的，且开口向上。因此，使用二次公式，我们可以找到方程的根为

$\alpha _{1}=0\quad \alpha _{2}=2{\frac {Re(\lambda )}{|\lambda |^{2}}}\!\,$

然后，如果矩阵 $\,\!A$ 的所有特征值的 $\,\!Re(\lambda )$ 都大于0，我们可以找到一个 $\,\!\alpha$ ，使得 $\,\!\rho \left((I-\alpha A)(I-\alpha A)^{*}\right)<1$ ，即该方法收敛。

如果A是对称矩阵，则选择alpha

另一方面，如果矩阵 $\,\!A$ 是对称的，则有 $\,\!\|I-\alpha A\|_{2}=\rho \left(I-\alpha A\right)$ 。然后使用舒尔分解，我们可以找到一个酉矩阵 $\,\!U$ 和一个对角矩阵 $\,\!\Lambda$ ，使得 $\,\!A=U^{*}\Lambda U$ ，因此，

${\begin{aligned}\|I-\alpha A\|_{2}&=\|I-\alpha \Lambda \|_{2}\\&=\rho (I-\alpha \Lambda )\\&=\max _{i=1,\dots ,n}(1-\alpha \lambda _{i})\\\end{aligned}}$

最后一个表达式在 $\,\!(1-\alpha \lambda _{1})=-(1-\alpha \lambda _{n})$ 时最小化，即当 $\,\!\alpha _{opt}=2/(\lambda _{1}+\lambda _{n})$ 时最小化。使用 $\,\!\alpha$ 的这个最优值，我们得到

$\,\!(I-\alpha _{opt}\Lambda )_{i,i}=1-{\frac {2}{\lambda _{1}+\lambda _{n}}}\lambda _{i},$

这意味着

$\,\!\|I-\alpha _{opt}\Lambda \|_{2}={\frac {\lambda _{n}-\lambda _{1}}{\lambda _{1}+\lambda _{n}}}$ .

最后，我们得到

$\,\!\|e_{k+1}\|_{2}\leq {\frac {\lambda _{n}-\lambda _{1}}{\lambda _{1}+\lambda _{n}}}\|e_{k}\|_{2}$ .

问题 3b

证明如果 $A\!\,$ 的一些特征值具有负实部，而另一些具有正实部，则不存在实数 $\alpha \!\,$ 使得迭代收敛。

解答 3b

如果对于 $i=1,2,\ldots ,n\!\,$ ， $Re(\lambda _{i})>0\!\,$ ，则当

$\alpha \in (0,2{\frac {Re(\lambda )}{|\lambda |^{2}}})\!\,$

因此 $\alpha >0\!\,$ 。

类似地，如果 $Re(\lambda _{i})<0\!\,$ 对于 $i=1,2,\ldots ,n\!\,$ ，则当以下条件满足时，会发生收敛：

$\alpha \in (2{\frac {Re(\lambda )}{|\lambda |^{2}}},0)\!\,$

因此 $\alpha <0\!\,$ 。

如果一些特征值是正数，一些是负数，则不存在一个实数 $\alpha \!\,$ 使迭代收敛，因为 $\alpha \!\,$ 不能同时为正数和负数。

问题 3c

令 $p=\|I-\alpha A\|<1\!\,$ 为与向量范数相关的矩阵范数。证明误差可以用连续迭代之间的差来表示，即

\|x-x_{k+1}\|\leq {\frac {\rho }{1-\rho }}\|x_{k}-x_{k+1}\|\!\,

（此证明简短但略微棘手）

解答 3c

${\begin{aligned}\|x-x_{k+1}\|&\leq p\|x-x_{k+1}+x_{k+1}-x_{k}\|\\&\leq p\|x-x_{k+1}\|+p\|x_{k+1}-x_{k}\|\\(1-p)\|x-x_{k+1}\|&\leq p\|x_{k+1}-x_{k}\|\\\|x-x_{k+1}\|&\leq {\frac {p}{1-p}}\|x_{k+1}-x_{k}\|\end{aligned}}\!\,$