数值方法资格考试问题及解答 (马里兰大学) / 2004 年 8 月

问题 1

为了计算 ${\sqrt {2}}\!\,$ ，我们考虑以下欧多克斯迭代：从 $x_{0}=y_{0}=1\!\,$ 开始，我们设置 $x_{n+1}=x_{n}+y_{n}\!\,$ ，然后是 $y_{n+1}=x_{n+1}+x_{n}\!\,$ 。然后 $y_{n}/x_{n}\rightarrow {\sqrt {2}}\!\,$

问题 1a

用幂法解释欧多克斯方法。

解答 1a

迭代可以用矩阵形式表示如下

${\begin{aligned}x_{n+1}&=x_{n}+y_{n}\\y_{n+1}&=x_{n+1}+x_{n}=2x_{n}+y_{n}\end{aligned}}\!\,$

它可以写成

$\underbrace {\begin{bmatrix}1&1\\2&1\end{bmatrix}} _{A}{\begin{bmatrix}x_{n}\\y_{n}\end{bmatrix}}={\begin{bmatrix}x_{n+1}\\y_{n+1}\end{bmatrix}}\!\,$

因此，迭代只是幂法，因为每一步都由矩阵 $A\!\,$ 的乘法表示。

幂法收敛于最大特征值的特征向量。

矩阵 $A\!\,$ 的特征值计算为 $1\pm {\sqrt {2}}\!\,$ 。因此，最大特征值为 $1+{\sqrt {2}}\!\,$

对应的特征向量是

${\begin{bmatrix}{\sqrt {2}}\\2\end{bmatrix}}\!\,$

那么 $y_{n}/x_{n}\rightarrow {\sqrt {2}}\!\,$ ，如预期的那样。

问题 1b

为了使误差 $|y_{n}/x_{n}-{\sqrt {2}}|\leq 10^{-6}\!\,$ ，需要多少次迭代？

解决方案 1b

由于收敛是线性的，因此需要 7 步才能达到误差界限。

问题 2

令 $\{p_{n}(x)\}\!\,$ 是关于 $[a,b]\!\,$ 的一组正权重函数 $w(x)\!\,$ （ $p_{n}\!\,$ 的度数为 $n\!\,$ ）的正交单项式序列。证明 $p_{n}\!\,$ 满足以下形式的三项递推公式：

$p_{n}(x)=(x-a_{n})p_{n-1}(x)-b_{n}p_{n-2}(x)\!\,$

给出系数 $a_{n}\!\,$ 和 $b_{n}\!\,$ 的表达式。

解决方案 2a

首先注意到 $p_{n}-xp_{n-1}\in \Pi ^{n-1}\!\,$ ，因此我们可以将其表示为度数为 $n-1\!\,$ 或更低的单项式线性组合，即

$p_{n}-xp_{n-1}=-a_{n}p_{n-1}-b_{n}p_{n-2}+\sum _{i=0}^{n-3}\alpha _{i}p_{i}\qquad (*)\!\,$

将 $(*)\!\,$ 两边的内积与 $p_{n-1}\!\,$ 进行计算，根据多项式的正交性，可以得到

$-\langle xp_{n-1},p_{n-1}\rangle =-a_{n}\langle p_{n-1},p_{n-1}\rangle \!\,$

然后，重新排列项可得

$a_{n}={\frac {\langle xp_{n-1},p_{n-1}\rangle }{\langle p_{n-1},p_{n-1}\rangle }}\!\,$

类似地，将 $(*)\!\,$ 两边的内积与 $p_{n-2}\!\,$ 进行计算，根据多项式的正交性，可以得到

$b_{n}={\frac {\langle xp_{n-1},p_{n-2}\rangle }{\langle p_{n-2},p_{n-2}\rangle }}\!\,$

注意

${\begin{aligned}\langle xp_{n-1},p_{n-2}\rangle &=\langle p_{n-1},xp_{n-2}\rangle \\&=\langle p_{n-1},p_{n-1}+\sum _{i=0}^{n-2}\alpha _{i}p_{i}\rangle \\&=\langle p_{n-1},p_{n-1}\rangle \end{aligned}}\!\,$