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

问题 1

令 $a=x_{0}<x_{1}<\cdots <x_{n}=b\!\,$ 是区间 $[a,b]\!\,$ 的任意固定分区。函数 $q(x)\!\,$ 是一个二次样条函数，如果 (i) $q\in C^{1}[a,b]\!\,$ (ii) 在每个子区间 $[x_{i},x_{i+1}]\!\,$ 上，$q\!\,$ 是一个二次多项式。 问题是构造一个二次样条 $q(x)\!\,$ 来插值数据点 $(x_{0},y_{0}),(x_{1},y_{1}),\ldots ,(x_{n},y_{n})\!\,$。该构造类似于三次样条的构造，但要容易得多。

问题 1a

证明如果我们知道 $z_{i}\equiv q'(x_{i}),i=0,\ldots ,n\!\,$，我们可以构造 $q\!\,$。

解答 1a

考虑区间 $[x_{i},x_{i+1}]\!\,$. 由于 $q'_{i}(x)\!\,$ 在此区间上是线性的，使用点斜式，我们有

$q_{i}'(x)={\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}(x-x_{i})+z_{i}\!\,$

积分，我们有

$q_{i}(x)=z_{i}x+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+K_{i}\!\,$

或者，用更方便的形式，

$q_{i}(x)=z_{i}(x-x_{i})+{\frac {z_{i+1}-z_{i}}{x_{i+1}-x_{i}}}{\frac {(x-x_{i})^{2}}{2}}+y_{i}\!\,$

问题 1b

找到能够确定 $z_{i}\!\,$ 的方程。你应该发现其中一个 $z_{i}\!\,$ 可以任意指定，例如 $z_{0}=0\!\,$

解 1

由于 $q\!\,$ 在 $[a,b]\!\,$ 上是连续的，

$q_{i-1}(x_{i})=q_{i}(x_{i})=y_{i}\!\,$

即

$z_{i-1}(x_{i}-x_{i-1})+{\frac {z_{i}-z_{i-1}}{x_{i}-x_{i-1}}}{\frac {(x_{i}-x_{i-1})^{2}}{2}}+y_{i-1}=y_{i}\!\,$

简化并重新排列项，得到递归公式

$z_{i}=-z_{i-1}+{\frac {2(y_{i}-y_{i-1})}{x_{i}-x_{i-1}}}\quad i=1,\ldots n\!\,$

问题 2a

给出$QR\!\,$ 算法的定义，该算法用于寻找矩阵 $A\!\,$ 的特征值。 定义无移位版本和带有移位 $\chi _{0},\chi _{1},\chi _{2},\ldots \!\,$ 的版本。

解答 2a

无移位版本

$Q_{k}R_{k}=A_{k}\!\,$

$A_{k+1}=R_{k}Q_{k}\!\,$

移位版本

$Q_{k}R_{k}=A_{k}-\chi _{k}I\!\,$

$A_{k+1}=R_{k}Q_{k}+\chi _{k}I\!\,$

问题 2b

证明在每种情况下，由 $QR\!\,$ 算法生成的矩阵 $A_{1},A_{2}\!\,$ 与 $A\!\,$ 酉等价（即 $A_{i}=U_{i}AU_{i}^{H},U_{i}\!\,$ 为酉矩阵）。

解 2b

假设存在某个酉矩阵 $U$，使得 $A_{m}=U^{T}AU$。由于 $R_{m}=Q_{m}^{T}A_{m}$，我们有

$A_{m+1}=R_{m}Q_{m}=Q_{m}^{T}A_{m}Q_{m}=Q_{m}^{T}U^{T}AUQ_{m}$

这符合我们的预期，因为 $Q_{m}U$ 是酉矩阵。

对于移位的情况，使用 $R_{m}=Q_{m}^{T}(A_{m}-\chi _{m}I)$ 这个事实，相同的论证也成立。

问题 2c

设 $A={\begin{pmatrix}3&1\\1&2\end{pmatrix}}\!\,$ 使用平面旋转（Givens 旋转）对 $QR\!\,$ 算法执行一步操作，首先不进行平移，然后使用平移 $\chi _{0}=1\!\,$。 哪个方法效果更好？ $A\!\,$ 的特征值为 $\lambda _{1}=1.382,\lambda _{2}=3.618\!\,$。 （回想一下，平面旋转是一个形式为 $Q={\begin{pmatrix}c&-s\\s&c\end{pmatrix}}\!\,$ 的矩阵，其中 $c^{2}+s^{2}=1\!\,$

解决方案 2c

平移迭代似乎效果更好，因为它的对角线元素比未平移迭代的对角线元素更接近实际特征值。

未平移迭代

$A_{1}={\begin{pmatrix}3.5&.5\\.5&1.5\end{pmatrix}}\!\,$

平移迭代

$A_{1}={\begin{pmatrix}3.6&.2\\.2&1.4\end{pmatrix}}\!\,$

问题 3

设 $A\!\,$ 是一个 $N\times N\!\,$ 对称正定矩阵。那么我们知道求解 $Ax=b\!\,$ 等价于最小化泛函 $F(x)={\frac {1}{2}}\langle x,Ax\rangle -\langle b,x\rangle \!\,$，其中 $\langle \cdot ,\cdot \rangle \!\,$ 表示 $R^{N}\!\,$ 中的标准内积。为了通过最小化 $F\!\,$ 来解决问题，我们考虑一般的迭代方法 $x_{v+1}=x_{v}+\alpha _{v}d_{v}\!\,$

问题 3a

当 $x_{v}\!\,$ 和 $d_{v}\!\,$ 给定，证明最小化 $F(x_{v}+\alpha d_{v})\!\,$（作为 $\alpha \!\,$ 的函数）的 $\alpha _{v}\!\,$ 值可以用残差 $r_{v}\!\,$ 表示为 $\alpha _{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }},\quad r_{v}=b-Ax_{v}\!\,$

解决方案 3a

有用的关系

由于 $A\!\,$ 是对称的

$(Ax,y)=(x,A^{T}y)=(x,Ay)\!\,$

此关系将在整个解决方案中使用。

代入泛函

${\begin{aligned}F(x_{v}+\alpha d_{v})&={\frac {1}{2}}\langle x_{v}+\alpha d_{v},Ax_{v}+\alpha Ad_{v}\rangle -\langle b,x_{v}+\alpha d_{v}\rangle \\&={\frac {\langle d_{v},Ad_{v}\rangle }{2}}\alpha ^{2}+\alpha \langle d_{v},Ax_{v}\rangle -\alpha \langle b,d_{v}\rangle +{\frac {1}{2}}\langle x_{v},Ax_{v}\rangle -\langle b,x_{v}\rangle \end{aligned}}\!\,$

对 alpha 求导数

$F'(x_{v}+\alpha d_{v})=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}\rangle -\langle b,d_{v}\rangle \!\,$

将导数设为零

$0=\langle d_{v},Ad_{v}\rangle \alpha +\langle d_{v},Ax_{v}-b\rangle \!\,$

这意味着

$\alpha ={\frac {\langle d_{v},r_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,$

问题 3b

令 $\{d_{j}\}_{j=1}^{N}\!\,$ 是 $A\!\,$-正交基于 $R^{N}\!\,$，$\langle d_{j},Ad_{k}\rangle =0,j\neq k\!\,$。考虑解 $x\!\,$ 在此基下的展开式 $x=\sum _{j=1}^{N}{\hat {x_{j}}}d_{j}\!\,$ 利用 $A-\!\,$正交性来计算 ${\hat {x}}_{j}\!\,$ 关于解 $x\!\,$ 和 $d_{j}\!\,$ 的表达式

解 3b

${\begin{aligned}\langle x,Ad_{k}\rangle &=\langle \sum _{j=1}^{n}{\hat {x}}_{j}d_{j},Ad_{k}\rangle \\&=\sum _{j=1}^{N}{\hat {x}}_{j}\langle d_{j},Ad_{k}\rangle \\&={\hat {x}}_{k}\langle d_{k},Ad_{k}\rangle \end{aligned}}\!\,$

这意味着

${\hat {x}}_{k}={\frac {\langle x,Ad_{k}\rangle }{\langle d_{k},Ad_{k}\rangle }}\!\,$

问题 3c

令 $x_{v}\!\,$ 表示部分和 $x_{v}=\sum _{j=1}^{v-1}{\hat {x}}_{j}d_{j},\quad v=2,3,\ldots \!\,$ 使得 $x_{v+1}=x_{v}+{\hat {x}}_{v}d_{v}\!\,$ 其中 ${\hat {x}}_{v}\!\,$ 是在 (b) 中找到的系数。利用 $x_{v}\in {\mbox{span}}\{d_{1},d_{2},\ldots ,d_{v-1}\}\!\,$ 以及 $A\!\,$-正交性的 $d_{j}\!\,$ 推断出系数 ${\hat {x}}_{v}\!\,$ 由最优 $\alpha _{v}\!\,$ 给出，即 ${\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}=\alpha _{v}\!\,$

解 3c

${\begin{aligned}\langle r_{v},d_{v}\rangle &=\langle b-Ax_{v},d_{v}\rangle \\&=\langle Ax-Ax_{v},dv\rangle \\&=\langle Ax,d_{v}\rangle -\langle Ax_{v},d_{v}\rangle \\&=\langle x,Ad_{v}\rangle -\underbrace {\langle x_{v},Ad_{v}\rangle } _{0}\\&={\hat {x}}_{v}\langle d_{v},Ad_{v}\rangle \end{aligned}}\!\,$

这意味着

${\hat {x}}_{v}={\frac {\langle r_{v},d_{v}\rangle }{\langle d_{v},Ad_{v}\rangle }}\!\,$