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

问题 1

令 $A\!\,$ 为 n 阶实对称矩阵，且 $n\!\,$ 个特征值互不相同，令 $v_{1}\in R^{n}\!\,$ 使得 $\|v_{1}\|_{2}=1\!\,$ 且内积 $(v_{1},u)\neq 0\!\,$ 对 $A\!\,$ 的每个特征向量 $u\!\,$ 都成立。

问题 1a

令 $P_{n}\!\,$ 表示次数最多为 $n-1\!\,$ 的多项式空间。证明 $\langle p,q\rangle \equiv (p(A)v_{1},q(A)v_{1})\!\,$ 定义了 $P_{n}\!\,$ 上的内积，其中上面的右侧表达式是 $R^{n}\!\,$ 中的欧几里得内积。

解 1a

对称性

${\begin{aligned}\langle p,q\rangle &=(p(A)v_{1},q(A)v_{1})\\&=(q(A)v_{1},p(A)v_{1})\\&=\langle q,p\rangle \end{aligned}}\!\,$

第一个参数的线性

令 $\alpha \in \mathbb {R} \!\,$

${\begin{aligned}\langle \alpha p,q\rangle &=(\alpha p(A)v_{1},q(A)v_{1})\\&=\alpha (p(A)v_{1},q(A)v_{1})\\&=\alpha \langle p,q\rangle \end{aligned}}\!\,$

${\begin{aligned}\langle p+r,q\rangle &=((p(A)+r(A))v_{1},q(A)v_{1})\\&=(p(A)v_{1},q(A)v_{1})+(r(A)v_{1},q(A)v_{1})\\&=\langle p,q\rangle +\langle r,q\rangle \end{aligned}}\!\,$

正定性

${\begin{aligned}\langle p,p\rangle &=(\underbrace {p(A)v_{1}} _{\hat {v}},\underbrace {p(A)v_{1})} _{\hat {v}}{\mbox{ where }}{\hat {v}}\in R^{n}\\&=({\hat {v}},{\hat {v}})\\&=\sum _{i=1}^{n}({\hat {v}}_{i})^{2}\geq 0\end{aligned}}\!\,$

“零性”

我们还需要证明 $\langle p,p\rangle =0\!\,$ 当且仅当 $p=0\!\,$.

前向方向（alt）

假设 $p\neq 0$。为了证明 $\langle p,p\rangle \neq 0$ 就足够了。然而，这是一个显而易见的结果，因为 $p(A)v_{1}\neq 0$（从 $p(A)\neq 0$ 对于 $p\neq 0$ 且度数小于 $n$，以及 $v_{i}$ 不在 $n$ 个不同的 $A$ 特征向量的正交补中）。

前向方向

断言：如果 $\langle p,p\rangle =0\!\,$，则 $p=0\!\,$.

根据假设

$v_{1}=\sum _{i=1}^{n}\alpha _{i}u_{i}\!\,$

其中 $u_{i}\!\,$ 是 $A\!\,$ 的正交特征向量，所有 $\alpha _{i}\!\,$ 都不为零。

${\begin{aligned}\langle p,p,\rangle &=(p(A)v_{1},p(A)v_{1})\\&=(p(A)\sum _{i=1}^{n}\alpha _{i}u_{i},p(A)\sum _{i=1}^{n}\alpha _{i}u_{i})\\&=(\sum _{i=1}^{n}\beta _{i}u_{i},\sum _{i=1}^{n}\beta u_{i}){\mbox{ (since }}u_{i}{\mbox{ are eigenvectors )}}\\&=0{\mbox{ (by hypothesis) }}\end{aligned}}\!\,$

注意 $\beta _{i}\!\,$ 是 $\alpha _{i}\!\,$ 的线性组合，多项式 $A\!\,$ 的系数，以及特征向量缩放系数 $m_{i}\!\,$ 例如 $Au_{i}=m_{i}u_{i}\!\,$

由于 $u_{i}\neq 0\forall i\!\,$ 且 $\alpha _{i}\neq 0\!\,$，这意味着 $p=0\!\,$.

反向

如果 $p=0\!\,$，则 $\langle p,p\rangle =(\underbrace {p(A)} _{0}v_{1},\underbrace {p(A)} _{0}v_{1})=0\!\,$

问题 1b

考虑以下递归关系 $\beta _{j+1}v_{j+1}=Av_{j}-\alpha _{j}v_{j}-\beta _{j}v_{j-1}\!\,$ 其中 $\alpha _{j}\!\,$ 和 $\beta _{j}\!\,$ 是标量，而 $v_{0}\equiv 0\!\,$。证明 $v_{j}=p_{j-1}(A)v_{1}\!\,$，其中 $p_{j-1}(t)\!\,$ 是一个 $j-1\!\,$ 次多项式

解 1b

使用数学归纳法。

基本情况

${\begin{aligned}\beta _{2}v_{2}&=Av_{1}-\alpha _{1}v_{1}-\beta _{1}\underbrace {v_{0}} _{0}\\v_{2}&={\frac {1}{\beta _{2}}}[Av_{1}-\alpha _{1}v_{1}]\\v_{2}&=p_{1}(A)v_{1}\quad p_{1}(t)={\frac {1}{\beta _{2}}}[t-\alpha _{1}]\end{aligned}}\!\,$

${\begin{aligned}\beta _{3}v_{3}&=Av_{2}-\alpha _{2}v_{2}-\beta _{2}v_{1}\\v_{3}&={\frac {1}{\beta _{3}}}[\underbrace {Av_{2}} _{\in p_{2}(A)v_{1}}-\underbrace {\alpha _{2}v_{2}} _{\in p_{1}(A)v_{1}}-\underbrace {\beta _{2}v_{1}} _{\in p_{0}(A)v_{1}}]\\&\in p_{2}(A)v_{1}\end{aligned}}\!\,$

归纳步骤

断言: $v_{j}=p_{j-1}(A)v_{1}\!\,$

假设

假设

$v_{j}=p_{j-1}(A)v_{1}\!\,$

$v_{j-1}=p_{j-2}(A)v_{1}\!\,$

其中 $p_{j-1}$（分别为 $p_{j-2}$）的度数为 $j-1$（分别为 $j-2$）。那么对于 $\beta _{j+1}\neq 0$

$v_{j+1}={\frac {Ap_{j-1}(A)-\alpha _{j}p_{j-1}(A)-\beta _{j}p_{j-2}(A)}{\beta _{j+1}}}v_{1}$

如预期那样。

问题 1c

假设上述标量使得 $\alpha _{j}=(Av_{j},v_{j})\!\,$ 且 $\beta _{j+1}\!\,$ 被选择以使得 $\|v_{j+1}\|_{2}=1\!\,$。利用此结果证明 (b) 部分中的多项式关于 (a) 部分中的内积是正交的。

解 1c

由于 $v_{j}=p_{j-1}(A)v_{1}\!\,$ 且 $\langle p,q\rangle \equiv (p(A)v_{1},q(A)v_{1})\!\,$，等价于证明 $(v_{i},v_{j})=0\!\,$ 对于 $i\neq j\!\,$.

由于

$v_{j+1}={\frac {1}{\beta _{j+1}}}Av_{j}-{\frac {\alpha _{j}}{\beta _{j}}}v_{j}-{\frac {\beta _{j+1}}{\beta _{j}}}v_{j-1}\!\,$,

那么，只需要证明

$(v_{j+1},v_{j})=(v_{j+1},v_{j-1})=0\!\,$

断言 $(v_{j+1},v_{j})=0\quad \forall j\!\,$

使用数学归纳法。

基本情况

${\begin{aligned}v_{2}&={\frac {1}{\beta _{2}}}(Av_{1}-\alpha _{1}v_{1})\\(v_{2},v_{1})&={\frac {1}{\beta _{2}}}[(Av_{1},v_{1})-\underbrace {\alpha _{1}} _{(Av_{1},v_{1})}\underbrace {(v_{1},v_{1})} _{1}]\\&=0\end{aligned}}\!\,$

归纳步骤

假设: $(v_{j},v_{j-1})=0\!\,$

断言: $(v_{j+1},v_{j})=0\!\,$

${\begin{aligned}v_{j+1}&={\frac {1}{\beta _{j+1}}}[Av_{j}-\alpha _{j}v_{j}-\beta _{j}v_{j-1}]\\(v_{j+1},v_{j})&={\frac {1}{\beta _{j+1}}}[(Av_{j},v_{j})-\underbrace {\alpha _{j}} _{(Av_{j},v_{j})}\underbrace {(v_{j},v_{j})} _{1}-\beta _{j}\underbrace {(v_{j-1},v_{j})} _{0}]\\&=0\end{aligned}}\!\,$

断言 $(v_{j+1},v_{j-1})=0\!\,$

使用数学归纳法。

基本情况

${\begin{aligned}v_{3}&={\frac {1}{\beta _{3}}}[Av_{2}-\alpha _{2}v_{2}-\beta _{2}v_{1}]\\(v_{3},v_{1})&={\frac {1}{\beta _{3}}}[(Av_{2},v_{1})-\alpha _{2}\underbrace {(v_{2},v_{1})} _{0}-\beta _{2}\underbrace {(v_{1},v_{1})} _{1}]\\&={\frac {1}{\beta _{3}}}[(Av_{2},v_{1})-\beta _{2}]\\&={\frac {1}{\beta _{3}}}[(v_{2},Av_{1})-\beta _{2}]{\mbox{ (因为 A 对称) }}\\&={\frac {1}{\beta _{3}}}[\beta _{2}-\beta _{2}]=0{\mbox{ (见下文) }}\end{aligned}}\!\,$

${\begin{aligned}\beta _{2}v_{2}&=Av_{1}-\alpha _{1}v_{1}\\\beta _{2}\underbrace {(v_{2},v_{2})} _{1}&=(Av_{1},v_{2})-\alpha _{1}\underbrace {(v_{1},v_{2})} _{0}\\\beta _{2}&=(Av_{1},v_{2})\end{aligned}}\!\,$

归纳步骤

假设： $(v_{j},v_{j-2})=0\!\,$

断言： $(v_{j+1},v_{j-1})=0\!\,$

${\begin{aligned}(v_{j+1},v_{j-1})&={\frac {1}{\beta _{j+1}}}[(Av_{j},v_{j-1}-\alpha _{j}\underbrace {(v_{j},v_{j-1})} _{0}-\beta _{j}\underbrace {(v_{j-1},v_{j-1})} _{1}\\&={\frac {1}{\beta _{j+1}}}[(Av_{j},v_{j-1})-\beta _{j})]\\&={\frac {1}{\beta _{j+1}}}[(v_{j},Av_{j-1})-\beta _{j}]{\mbox{ (因为 A 对称)}}\\&={\frac {1}{\beta _{j+1}}}[\beta _{j}-\beta _{j}]=0{\mbox{ (见下文) }}\end{aligned}}\!\,$

${\begin{aligned}\beta _{j}v_{j}&=Av_{j-1}-\alpha _{j-1}v_{j-1}-\beta _{j-1}v_{j-2}\\\beta _{j}\underbrace {(v_{j},v_{j})} _{1}&=(Av_{j-1},v_{j})-\alpha _{j-1}\underbrace {(v_{j-1},v_{j})} _{0}-\beta _{j-1}\underbrace {(v_{j-2},v_{j})} _{0}\\\beta _{j}&=(Av_{j-1},v_{j})\end{aligned}}\!\,$

问题 2

考虑 n-面板梯形法则 $I_{n}(f)\!\,$ 用于计算连续函数 $f\in C[0,1]\!\,$ 的积分 $\int _{0}^{1}f(x)dx\!\,$, $I_{n}(f)=\sum _{k=0}^{n-1}\left({\frac {t_{k+1}-t_{k}}{2}}\right)(f(t_{k})+f(t_{k+1}))\!\,$ 其中 $0=t_{0}<t_{1}<...<t_{n}=1\!\,$

问题 2a

找到一个分段线性函数 $G\!\,$ 使得 $I_{n}(f)-\int _{0}^{1}f(t)dt=\int _{0}^{1}G(t)f'(t)dt\!\,$ 对于任何连续函数 $f\!\,$ 使得 $f'\!\,$ 在 [0,1] 上可积。提示：求 $G\!\,$，将微积分基本定理应用于 $\int _{t_{k}}^{t_{k+1}}(f(t)G(t))'dt\!\,$.

解法 2a

重写给定方程在特定区间上的形式

对于特定区间 $[t_{k},t_{k+1}]\!\,$，根据假设我们有

$({\frac {t_{k+1}-t_{k}}{2}})(f(t_{k})+f(t_{k+1}))-\int _{t_{k}}^{t_{k+1}}f(t)=\int _{t_{k}}^{t_{k+1}}G(t)f'(t)dt\!\,$.

分配和重新排列项得到

$(1)\qquad ({\frac {t_{k+1}-t_{k}}{2}})f(t_{k})+({\frac {t_{k+1}-t_{k}}{2}})f(t_{k+1}))-\int _{t_{k}}^{t_{k+1}}f(t)=\int _{t_{k}}^{t_{k+1}}G(t)f'(t)\!\,$

应用提示

从提示开始，应用乘积法则，得到

$\int _{t_{k}}^{t_{k+1}}(f(t)G(t))'dt=\int _{t_{k}}^{t_{k+1}}f'(t)G(t)dt+\int _{t_{k}}^{t_{k+1}}f(t)G'(t)dt\!\,$.

此外，我们知道微积分基本定理

$\int _{t_{k}}^{t_{k+1}}(f(t)G(t))'dt=f(t_{k+1})G(t_{k+1})-f(t_{k})G(t_{k})\!\,$.

将以上两个等式设为相等，并解出 $\int _{t_{k}}^{t_{k+1}}f'(t)G(t)\!\,$，得到

$(2)\qquad -G(t_{k})f(t_{k})+G(t_{k+1})f(t_{k+1})-\int _{t_{k}}^{t_{k+1}}G'(t)f(t)dt=\int _{t_{k}}^{t_{k+1}}G(t)f'(t)\!\,$

选择 G'(t)

令 $G'(t)=1\!\,$。因此，由于 $G(t)\!\,$ 是线性的

$(3)\qquad G(t)=t+b\!\,$

通过比较等式 (1) 和 (2)，我们看到

$G(t_{k+1})={\frac {t_{k+1}-t_{k}}{2}}\!\,$ 并且

$G(t_{k})=-{\frac {t_{k+1}-t_{k}}{2}}\!\,$.

将 $G(t_{k})\!\,$ 或 $G(t_{k+1})\!\,$ 代入等式 (3)，我们得到

$b=-{\frac {t_{k+1}+t_{k}}{2}}\!\,$

因此

$G(t)=t-{\frac {t_{k+1}+t_{k}}{2}}\!\,$

问题 2b

将先前结果应用于 $f(x)=x^{\alpha }\!\,$, $0<\alpha <1\!\,$，以获得收敛速度。

问题 3

令 $C[a,b]\!\,$ 表示在闭区间 $[a,b]\!\,$ 上定义的所有实值连续函数的集合，在 $[a,b]\!\,$ 中处处为正。令 $\{Q_{n}\}_{n=0}^{\infty }\!\,$ 是一个多项式系统，对于每个 $n\!\,$ 都有 $deg\,Q_{n}=n\!\,$，关于内积正交 $\langle g,h\rangle =\int _{a}^{b}\rho (x)g(x)h(x)dx,\quad \forall g,h\in C[a,b]\!\,$ 对于固定的整数 $n\geq 2\!\,$，令 $x_{1},\ldots ,x_{n}\!\,$ 为 $n\!\,$ 个不同的根 $Q_{n}\!\,$ 在 $(a,b)\!\,$ 中。令 $r_{k}(x)={\frac {(x-x_{1})\cdots (x-x_{k-1})(x-x_{k+1})\cdots (x-x_{n})}{(x_{k}-x_{1})\cdots (x_{k}-x_{k-1})(x_{k}-x_{k+1})\cdots (x_{k}-x_{n})}},\quad k=1,2,\ldots ,n\!\,$ 是 $n-1\!\,$ 次多项式。证明 $\int _{a}^{b}\rho (x)r_{j}(x)r_{k}(x)dx=0,\forall j\neq k\!\,$ 以及 $\sum _{k=1}^{n}\int _{a}^{b}\rho (x)(r_{k}(x))^{2}dx=\int _{a}^{b}\rho (x)dx\!\,$ 提示：使用正交性来简化 $\int _{a}^{b}\rho (x)(\sum _{k=1}^{n}r_{k}(x))^{2}dx\!\,$

解 3a

${\begin{aligned}&\quad \int _{a}^{b}\rho (x)r_{j}(x)r_{k}(x)dx\\&=\int _{a}^{b}\rho (x)\prod _{i\neq j}{\frac {x-x_{i}}{x_{j}-x_{i}}}\prod _{i\neq k}{\frac {x-x_{i}}{x_{k}-x_{i}}}dx\\&=\int _{a}^{b}\overbrace {\frac {\prod _{i\neq k,i\neq j}^{n}x-x_{i}}{\prod _{i\neq j}^{n}x_{j}-x_{i}}} ^{Q_{n-2}}\overbrace {\frac {\prod _{i=1}^{n}x-x_{i}}{\prod _{i\neq k}^{n}x_{k}-x_{i}}} _{n}^{Q}dx\\&=0\end{aligned}}\!\,$

解法 3b

${\begin{aligned}&\quad \sum _{k=1}^{n}\int _{a}^{b}\rho (x)(r_{k}(x))^{2}dx\\&=\int _{a}^{b}\rho (x)\sum _{k=1}^{n}(r_{k}(x))^{2}dx\\&=\int _{a}^{b}\rho (x)(\sum _{k=1}^{n}r_{k}(x))^{2}dx{\mbox{ (from part a) }}\\&=\int _{a}^{b}\rho (x)(1)^{2}dx{\mbox{ (from claim) }}\\&=\int _{a}^{b}\rho (x)dx\end{aligned}}\!\,$

断言

$\sum _{k=1}^{n}r_{k}(x)=1\!\,$

证明

由于 $r_{k}\!\,$ 对所有 $k\!\,$ 都是 $n-1\!\,$ 次的多项式，$\sum _{k=1}^{n}r_{k}(x)\!\,$ 也是一个 $n-1\!\,$ 次的多项式。

注意，$\sum _{k=1}^{n}r_{k}(x_{i})=1\!\,$ 对 $i=1,2,\ldots ,n\!\,$ 成立，其中 $x_{i}\!\,$ 是 $n\!\,$ 个不同的 $Q_{n}\!\,$ 的根。由于 $\sum _{k=1}^{n}r_{k}(x)\!\,$ 是一个 $n-1\!\,$ 次的多项式，并且它在 $n\!\,$ 个不同的点处取值为 1。

$\sum _{k=1}^{n}r_{k}(x)=1\!\,$