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

问题 1

令 $f\!\,$ 在 $[0,1]\!\,$ 上连续。一个次数不超过 $n\!\,$ 的多项式 $p\!\,$ 称为 $f\!\,$ 的最佳（或切比雪夫）逼近，如果 $p\!\,$ 使表达式最小化 $E(p)=\max _{x\in [0,1]}|f(x)-p(x)|\!\,$

问题 1a

证明 $p\!\,$ 是最佳逼近的一个充分条件是存在点 $x_{0}<x_{1}<\cdots <x_{n+1}\;{\mbox{in}}\;[0,1]\!\,$ 使得 $f(x_{i})-p(x_{i})=-[f(x_{i+1})-p(x_{i+1})]=\pm E(p),\qquad i=0,1,2,\dots ,n\!\,$.

解答 1a

假设存在 $q\in \Pi ^{n}\!\,$ 使得

$E(q)<E(p)\!\,$

那么对于 $i=0,1,\ldots ,n\!\,$

$|f(x_{i})-q(x_{i})|\leq |f(x_{i})-p(x_{i})|\!\,$

令 $e(q)=f(x)-q(x)\!\,$ 以及 $e(p)=f(x)-p(x)\!\,$.

那么 $e\equiv e(q(x))-e(p(x))\!\,$ 取决于 $e(p)\!\,$ 的符号，因为

$|e(p(x_{i}))|\geq |e(q(x_{i}))|\!\,$

由于 $e(p)\!\,$ 在 $n+1\!\,$ 次（假设）改变符号，$e\!\,$ 有 $n+1\!\,$ 个零点。

然而 $e=p-q\!\,$，因此最多只有 $n\!\,$ 个零点。 因此 $e\equiv 0\!\,$ 且 $p=q\!\,$

问题 1b

计算对 $x^{2}\;{\mbox{in}}\;[0,1]\!\,$ 的最佳线性逼近。 [提示：在抛物线上画一条线将让你推测出两个振荡点的位置。 使用 (a) 中的条件来确定第三个点和 $p\!\,$ 的系数。]

解 1b

首先，我们需要在 [0,1] 中找到 $T_{2}(x)\!\,$ 的根，它们由下式给出

$x_{k}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {2k-1}{4}}\pi )\!\,$

因此，我们的插值点为

$x_{1}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {\pi }{4}})\!\,$

$x_{2}={\frac {1}{2}}+{\frac {1}{2}}\cos({\frac {3\pi }{4}})={\frac {1}{2}}-{\frac {1}{2}}\cos({\frac {\pi }{4}})\!\,$

我们的线性插值函数经过点 $(x_{1},x_{1}^{2})\!\,$ 和 $(x_{2},x_{2}^{2})\!\,$，使用点斜式得到方程

$y-x_{1}^{2}={\frac {x_{2}^{2}-x_{1}^{2}}{x_{2}-x_{1}}}(x-x_{1})\!\,$

或者

$y=x-{\frac {1}{8}}\!\,$

问题 2

我们将关注最小化以下最小二乘问题的： $\rho ^{2}(x)=\|b-Ax\|^{2}\!\,$. 这里 $A\!\,$ 是一个 $m\times n\!\,$ 矩阵，秩为 $n\!\,$ （这意味着 $m\geq n\!\,$），$\|\cdot \|\!\,$ 是欧几里得向量范数。令 $A={\begin{pmatrix}Q_{1}&Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}\!\,$ 是 $A\!\,$ 的 QR 分解。这里 $Q_{1},Q_{2}\;{\mbox{and}}\;R\!\,$ 分别是 $m\times n,m\times (m-n),\;{\mbox{and}}\;n\times n\!\,$。

问题 2a

证明最小二乘问题的解满足 QR 方程$Rx=Q_{1}^{T}b\!\,$，并且解是唯一的。进一步证明$\rho (x)=\|Q_{2}^{T}b\|\!\,$.

解 2a

这两个问题是等价的

首先注意到

$A={\begin{pmatrix}Q_{1}Q_{2}\end{pmatrix}}{\begin{pmatrix}R\\0\end{pmatrix}}=Q_{1}R$

那么我们可以写成

${\begin{aligned}\|b-Ax\|&=\|b-Q_{1}Rx\|\\&=\|Q_{1}^{T}b-Q_{1}^{T}Q_{1}Rx\|\\&=\|Q_{1}^{T}b-Rx\|\end{aligned}}$

注意，乘以正交矩阵不会影响范数。

那么求解$\min _{x}\|b-Ax\|^{2}\!\,$等价于求解$\min _{x}\|Q_{1}^{T}b-Rx\|^{2}\!\,$，这等价于求解$Rx=Q_{1}^{T}b\!\,$。注意，解存在且唯一，因为$R\!\,$是 n×n 且非奇异的。

证明$\rho (x)=\|Q_{2}^{T}b\|$

类似地

${\begin{aligned}\|b-Ax\|&=\|b-Q_{1}Rx\|\\&=\|Q_{2}^{T}b-\underbrace {Q_{2}^{T}Q_{1}} _{0}Rx\|\\&=\|Q_{2}^{T}b\|\end{aligned}}$

那么

$\rho ^{2}(x)=\|b-Ax\|^{2}=\|Q_{2}^{T}b\|^{2}$，或者简化为 $\rho (x)=\|Q_{2}^{T}b\|$，如预期那样。

问题 2b

利用 QR 方程证明最小二乘解满足正规方程 $(A^{T}A)x=A^{T}b\!\,$。

解 2b

${\begin{aligned}A^{T}Ax&=(Q_{1}R)^{T}Q_{1}Rx\\&=R^{T}Q_{1}^{T}Q_{1}Rx\\&=R^{T}Rx\\\\A^{T}b&=(Q_{1}R)^{T}b\\&=R^{T}\underbrace {Q_{1}^{T}b} _{Rx}\\&=R^{T}Rx\end{aligned}}\!\,$

问题 3

$\!\,$ 令 $\!\,A$ 为实对称矩阵，令 $u_{0}\neq 0\!\,$ 为给定值。对于 $k=1,2,\ldots \!\,$，定义 $u_{k+1}\!\,$ 为向量 $Au_{k},u_{k},\ldots ,u_{0}\!\,$ 的线性组合，其中 $Au_{k}\!\,$ 的系数为 1 且与向量 $u_{k},\ldots ,u_{0}\!\,$ 正交；即 $u_{k+1}=Au_{k}-\alpha _{k}u_{k}-\beta _{k}u_{k-1}-\gamma _{k}u_{k-2}-\cdots \!\,$

问题 3a

求 $\alpha _{k}\!\,$ 和 $\beta _{k}\!\,$ 的公式。

解 3a

使用 Gram-Schmidt 正交化，我们有

${\begin{aligned}\alpha _{k}&={\frac {(Au_{k},u_{k})}{\|u_{k}\|^{2}}}\\\beta _{k}&={\frac {(Au_{k},u_{k-1})}{\|u_{k-1}\|^{2}}}\end{aligned}}$

问题 3b

证明 $\gamma _{k}=\delta _{k}=\ldots =0\!\,$ 在哪里你使用了 $A\!\,$ 的对称性？

解 3b

因为

$\gamma _{k}={\frac {(Au_{k},u_{k-2})}{\|u_{k-2}\|^{2}}}$

, 如果 $\gamma _{k}=0\!\,$，那么

$(Au_{k},u_{k-2})=0\!\,$

因为 $A\!\,$ 是对称的，

$(Au_{k},u_{k-2})=(u_{k},A^{T}u_{k-2})=(u_{k},Au_{k-2})\!\,$

根据假设，$(u_{i},u_{j})={\begin{cases}1&{\mbox{if }}i=j\\0&{\mbox{if }}i\neq j\end{cases}}$

同样根据假设，

${\begin{aligned}Au_{k}&=u_{k+1}+\alpha _{k}u_{k}+\beta _{k}u_{k-1}+\gamma _{k}u_{k-2}+\ldots \\Au_{k-2}&=u_{k-1}+\alpha _{k-2}u_{k-2}+\beta _{k-2}u_{k-3}+\gamma _{k-2}u_{k-4}+\ldots \end{aligned}}$

使用上述结果，我们有，

${\begin{aligned}(Au_{k},u_{k-2})&=(u_{k},Au_{k-2})\\&=(u_{k},u_{k-1}+\alpha _{k-2}u_{k-2}+\beta _{k-2}u_{k-3}+\gamma _{k-2}u_{k-4}+\ldots )\\&=(u_{k},u_{k-1})+\alpha _{k-2}(u_{k},u_{k-2})+\beta _{k-2}(u_{k},u_{k-3})+\gamma _{k-2}(u_{k},u_{k-4})+\ldots )\\&=0\end{aligned}}$

问题 3c

对于哪些非零向量 $u_{0}\!\,$，$u_{1}=0\!\,$ 成立？

解 3c

对于 $k=0\!\,$，

$u_{1}=Au_{0}-\alpha _{0}u_{0}\!\,$

如果 $u_{1}=0\!\,$，那么

$Au_{0}=\alpha _{0}u_{0}\!\,$

由于 $\alpha _{0}\!\,$ 是一个标量，$u_{0}\!\,$ 是 $A\!\,$ 的特征向量。