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

问题 1

一组函数 $\{g_{1},\ldots ,g_{n}\}\subset C[a,b]\!\,$ 是一个切比雪夫系统，如果

(i) 该集合是线性无关的。

(ii) 如果

g\!\,

是

\{g_{1},\ldots ,g_{n}\}\!\,

的一个线性组合，它不恒等于零，则

g\!\,

在

[a,b]\!\,

中最多有

n-1\!\,

个不同的零点。

问题 1a

证明 $\{g_{1},\ldots ,g_{n}\}\!\,$ 是切比雪夫系统当且仅当对于任何 $n\!\,$ 个不同的点 $x_{1},\ldots ,x_{n}\in [a,b]\!\,$ ，矩阵 $A\!\,$ 是非奇异的，其中 $a_{i,j}=g_{j}(x_{i}),1\leq i,j\leq n\!\,$ 。

解 1a

正向

我们要证明以下结论

如果 $\{g_{1},\ldots ,g_{n}\}\!\,$ 是切比雪夫系统，那么对于任何 $n\!\,$ 个不同的点 $x_{1},\ldots ,x_{n}\in [a,b]\!\,$ ，矩阵 $A\!\,$ 是非奇异的，其中 $a_{i,j}=g_{j}(x_{i}),1\leq i,j\leq n\!\,$ 。

写出矩阵 $A\!\,$ 得到

$A={\begin{pmatrix}g_{1}(x_{1})&g_{2}(x_{1})&\cdots &g_{n}(x_{1})\\g_{1}(x_{2})&g_{2}(x_{2})&\cdots &g_{n}(x_{2})\\\vdots &\vdots &\ddots &\vdots \\g_{1}(x_{n})&g_{2}(x_{n})&\cdots &g_{n}(x_{n})\end{pmatrix}}$

由于集合 $\{g_{1},\ldots ,g_{n}\}\!\,$ 线性无关，所以不存在任何非零常数集 $\alpha _{i}\!\,$ 使得 $\sum _{i=1}^{n}\alpha _{i}g_{i}(x)=0\!\,$ 对任意 $x\in [a,b]\!\,$ 成立。因此，矩阵 $A\!\,$ 的列线性无关，这意味着 $A\!\,$ 是非奇异的。

反向推导

(i) 的证明

假设 $A\!\,$ 是非奇异的。

这意味着

A={\begin{pmatrix}g_{1}(x_{1})&g_{2}(x_{1})&\cdots &g_{n}(x_{1})\\g_{1}(x_{2})&g_{2}(x_{2})&\cdots &g_{n}(x_{2})\\\vdots &\vdots &\ddots &\vdots \\g_{1}(x_{n})&g_{2}(x_{n})&\cdots &g_{n}(x_{n})\end{pmatrix}}

的列线性无关。由于 $A\!\,$ 对任意 $\{x_{1},x_{2},\ldots ,x_{n}\}\!\,$ 的选择是非奇异的， $\{g_{1},g_{2},\dots ,g_{n}\}\!\,$ 是一个线性无关的集合，我们证明了 $(i)\!\,$ 。

(ii) 的证明

根据假设， $g(x)\!\,$ 是 $\{g_{1},g_{2},\dots ,g_{n}\}\!\,$ 的线性组合，即

g(x)=\alpha _{1}g_{1}(x)+\alpha _{2}g_{2}(x)+\cdots +\alpha _{n}g_{n}(x)\!\,

对于 $\alpha _{i}\!\,$ 并非全为零。

假设为了反证， $g(x)\!\,$ 在 ${\hat {x_{1}}},{\hat {x_{2}}},\ldots ,{\hat {x_{n}}}\!\,$ 有 $n\!\,$ 个零点。

这意味着以下 $n\!\,$ 个方程

${\begin{aligned}g({\hat {x_{1}}})&=0=\alpha _{1}g_{1}({\hat {x_{1}}})+\alpha _{2}g_{2}({\hat {x_{1}}})+\cdots +\alpha _{n}g_{n}({\hat {x_{1}}})\\g({\hat {x_{2}}})&=0=\alpha _{1}g_{1}({\hat {x_{2}}})+\alpha _{2}g_{2}({\hat {x_{2}}})+\cdots +\alpha _{n}g_{n}({\hat {x_{2}}})\\&\vdots \\g({\hat {x_{n}}})&=0=\alpha _{1}g_{1}({\hat {x_{n}}})+\alpha _{2}g_{2}({\hat {x_{n}}})+\cdots +\alpha _{n}g_{n}({\hat {x_{n}}})\end{aligned}}$

将这些方程改写成矩阵形式，得到

${\begin{pmatrix}g_{1}({\hat {x_{1}}})&g_{2}({\hat {x_{1}}})&\cdots &g_{n}({\hat {x_{1}}})\\g_{1}({\hat {x_{2}}})&g_{2}({\hat {x_{2}}})&\cdots &g_{n}({\hat {x_{2}}})\\\vdots &\vdots &\ddots &\vdots \\g_{1}({\hat {x_{n}}})&g_{2}({\hat {x_{n}}})&\cdots &g_{n}({\hat {x_{n}}})\end{pmatrix}}{\begin{pmatrix}\alpha _{1}\\\alpha _{2}\\\vdots \\\alpha _{n}\end{pmatrix}}={\begin{pmatrix}0\\0\\\vdots \\0\end{pmatrix}}$

由于 $\alpha _{i}\!\,$ 不全为零，这意味着 $A\!\,$ 的列向量 $\{g_{1},g_{2},\ldots ,g_{n}\}$ 线性相关，矛盾。

因此， $g\!\,$ 最多有 $n-1\!\,$ 个零点，我们已经证明了 $(ii)\!\,$ 。

问题 1b

假设 $f\in C^{m+1}[a,b]\!\,$ ，使得对于所有 $x\in [a,b]\!\,$ 有 $f^{(m+1)}(x)\neq 0\!\,$ 。假设 $g_{j}(x)=x^{j-1},j=1,\ldots ,m+1\!\,$ 。证明 $\{g_{1},\ldots ,g_{m+1},f\}\!\,$ 是一个切比雪夫系统。为此，您可以使用多项式插值的结论，无需证明。

解 1b

我们需要证明

(i) $\{1,x,x^{2},\dots ,f\}\!\,$ 是一个线性无关集

(ii)该集合的任何线性组合最多具有 $m\!\,$ 个零点。

(i) 的证明

如果我们在 $m+1\!\,$ 个不同的点， $\{x_{1},x_{2},\ldots ,x_{m+1}\}$ 上评估 $g_{1},g_{2},\dots ,g_{m+1}\!\,$ ，我们得到以下范德蒙德矩阵，其行列式不为零。

${\begin{pmatrix}1&1&\cdots &1\\x_{1}&x_{1}^{2}&\cdots &x_{1}^{m}\\\vdots &\vdots &\ddots &\vdots \\x_{m+1}&\cdots &\cdots &x_{m+1}^{m}\end{pmatrix}}$

因此， $g_{1},g_{2},\dots ,g_{m+1}\!\,$ 线性无关。

为了反证，假设 $f\!\,$ 是 $g_{1},g_{2},\dots ,g_{m+1}\!\,$ 的线性组合，即

${\begin{aligned}f(x)&=\beta _{0}g_{1}(x)+\beta _{1}g_{2}(x)+\dots +\beta _{m}g_{m+1}(x)\\&=\beta _{0}\cdot 1+\beta _{1}x+\beta _{2}x^{2}+\dots +\beta _{m}x^{m}\end{aligned}}$ .

因此， $f(x)\!\,$ 是一个 $m\!\,$ 次多项式。对 $f(x)\!\,$ 求 $m+1\!\,$ 阶导数，得到

f^{(m+1)}(x)=0\!\,

这与假设矛盾。因此， $\{1,x,x^{2},\dots ,f\}\!\,$ 是线性无关的集合。

(ii) 的证明

令 $h(x)=\beta _{0}g_{1}(x)+\beta _{1}g_{2}(x)+\dots +\beta _{m}g_{m+1}(x)+\beta _{m+1}f(x)\!\,$ 。

假设 $h\!\,$ 在 $[a,b]\!\,$ 有 $m+2\!\,$ 个（或更多）零点。根据罗尔定理，f 的（n+1）阶导数在给定区间上消失，这与假设矛盾。

(i) 和 (ii) 表明 $\{1,x,x^{2},\dots ,f\}\!\,$ 是一个切比雪夫系统。

问题 2

令

I_{n}(f)=\sum _{k=1}^{n}w_{n,k}f(x_{n},k),\quad \quad a\leq x_{n,k}\leq b\quad \quad (0)

是一系列积分规则。

问题 2a

假设

\lim _{n\rightarrow \infty }I_{n}(x^{k})=\int _{a}^{b}x^{k}dx,\quad \quad k=0,1,\ldots \quad \quad (1)

并且

\sum _{k=1}^{n}|w_{n,k}|\leq M,\quad \quad n=1,2,\ldots \quad \quad (2)

对于某个常数 $M\!\,$ 。证明

\lim _{n\rightarrow \infty }I_{n}(f)=\int _{a}^{b}f(x)dx

对于所有 $f\in C[a,b]\!\,$

解决方案 2a

根据魏尔斯特拉斯逼近定理，对于给定的 $\epsilon >0\!\,$ ，存在多项式 $p(x)\!\,$ 使得

\max _{a\leq x\leq b}|f(x)-p(x)|\leq \min\{{\frac {\epsilon }{2}}\cdot {\frac {1}{M}},{\frac {\epsilon }{2}}\cdot {\frac {1}{b-a}}\}\quad \quad (3)

令

I(f)=\int _{a}^{b}f(x)dx

分别添加和减去 $I(p)\!\,$ 和 $I_{n}(p)\!\,$ ，得到，

I(f)-I_{n}(f)=[I(f)-I(p)]+[I(p)-I_{n}(p)]+[I_{n}(p)-I_{n}(f)]\!\,

根据三角不等式和公式 (2) 和 (3)，

${\begin{aligned}|I(f)-I_{n}(f)|&\leq |I(f-p)|+|I(p)-I_{n}(p)|+|I_{n}(p-f)|\\&\leq \int _{a}^{b}|f(x)-p(x)|dx+|I(p)-I_{n}(p)|+\sum _{k=1}^{n}|w_{n,k}||f(x_{n},k)-p(x_{n},k)|\\&\leq {\frac {\epsilon }{2(b-a)}}\int _{a}^{b}dx+|I(p)-I_{n}(p)|+{\frac {\epsilon }{2M}}\sum _{k=1}^{n}|w_{n,k}|\\&\leq {\frac {\epsilon }{2(b-a)}}(b-a)+|I(p)-I_{n}(p)|+{\frac {\epsilon }{2M}}M\\&=\epsilon +|I(p)-I_{n}(p)|\end{aligned}}$

根据公式 (1)，当 $n\rightarrow \infty \!\,$ 时，

|I(p)-I_{n}(p)|=0\!\,

因此，对于任意小的 $\epsilon >0\!\,$ ，当 $n\rightarrow \infty \!\,$ 时，

|I(f)-I_{n}(f)|\leq \epsilon

即

I(f)=\lim _{n\rightarrow \infty }I_{n}(f)\!\,

问题 2b

证明如果所有 $w_{n,k}>0\!\,$ 则 (1) 意味着 (2)。

解 2b

对于 $k=0\!\,$ ，等式 (1) 给出：

${\begin{aligned}\lim _{n\rightarrow \infty }I_{n}(x^{0})&=\int _{a}^{b}x^{0}dx\\\lim _{n\rightarrow \infty }I_{n}(1)&=\int _{a}^{b}1\cdot dx\\&=(b-a)\end{aligned}}$

令 $f(x)\!\,$ 在等式 (0) 中给出：

I_{n}(1)=\sum _{k=1}^{n}w_{n,k}\cdot 1=\sum _{k=1}^{n}w_{n,k}

将以上两个结果结合起来，得到：

${\begin{aligned}\lim _{n\rightarrow \infty }I_{n}(1)&=\lim _{n\rightarrow \infty }\sum _{k=1}^{n}w_{n,k}\\&=(b-a)\\&\leq M\end{aligned}}$

由于 $(b-a)\!\,$ 是有限的，存在一个数 $M\!\,$ 使得 $(b-a)\leq M$ .

由于 $w_{n,k}>0\!\,$ ,

\lim _{n\rightarrow \infty }\sum _{k=1}^{n}|w_{n,k}|\leq M

即方程式 (2)。

问题 3

考虑实数线性方程组

Ax=b\quad \quad (1)\,\!

其中 $A\,\!$ 为非奇异矩阵，且满足

(v,Av)>0\,\!

对于所有实数 $v\,\!$ ，这里使用欧几里得内积。

问题 3a

证明对于所有实数 $v\,\!$ ，有 $(v,Av)=(v,Mv)\,\!$ ，其中 $M={\frac {1}{2}}(A+A^{T})\,\!$ 是 $A\,\!$ 的对称部分。

解 3a

将 $M\!\,$ 代入 $(v,Mv)\!\,$ 并展开内积，我们有，

${\begin{aligned}(v,Mv)&=(v,{\frac {1}{2}}(A+A^{T})v)\\&=(v,{\frac {1}{2}}Av+{\frac {1}{2}}A^{T}v)\\&=(v,{\frac {1}{2}}Av)+(v,{\frac {1}{2}}A^{T}v)\\&={\frac {1}{2}}(v,Av)+{\frac {1}{2}}(v,A^{T}v)\end{aligned}}$

根据内积的性质，我们有，

(v,A^{T}v)=(Av,v)=(v,Av)\!\,

因此，

${\begin{aligned}(v,Mv)&={\frac {1}{2}}(v,Av)+{\frac {1}{2}}(v,A^{T}v)\\&={\frac {1}{2}}(v,Av)+{\frac {1}{2}}(v,Av)\\&=(v,Av)\end{aligned}}$

问题 3b

证明

{\frac {(v,Av)}{(v,v)}}\geq \lambda _{\min }(M)>0\,\!

其中 $\lambda _{\min }(M)\,\!$ 是 $M\,\!$ 的最小特征值。

解决方案 3b

第一个不等式

{\frac {(v,Av)}{(v,v)}}={\frac {(v,Mv)}{(v,v)}}={\frac {v^{T}Mv}{v^{T}v}}

由于 $M\,\!$ 是对称的，它有一个特征值分解

M=Q^{T}\Lambda Q\!\,

其中 $Q\,\!$ 是正交的，而 $\Lambda \,\!$ 是一个对角矩阵，包含所有特征值。

代入得，

{\frac {(v,Av)}{(v,v)}}={\frac {v^{T}Q^{T}\Lambda Qv}{v^{T}v}}

令

Qv=x\!\,

这意味着以下三个关系

{\begin{aligned}v&=Q^{T}x\\v^{T}Q^{T}&=x^{T}\\v^{T}&=x^{T}Q\end{aligned}}

代入，

{\begin{aligned}{\frac {v^{T}Q^{T}\Lambda Qv}{v^{T}v}}&={\frac {x^{T}\Lambda x}{x^{T}QQ^{T}x}}\\&={\frac {x^{T}\Lambda x}{x^{T}x}}\end{aligned}}

展开分子，我们有，

${\begin{aligned}x^{T}\Lambda x&={\begin{bmatrix}x_{1}x_{2}\ldots x_{n}\end{bmatrix}}{\begin{bmatrix}\lambda _{1}&&&\\&\lambda _{2}&&\\&&\ddots &\\&&&\lambda _{n}\end{bmatrix}}{\begin{bmatrix}x_{1}\\x_{2}\\\vdots \\x_{n}\end{bmatrix}}\\&={\begin{bmatrix}x_{1}x_{2}\ldots x_{n}\end{bmatrix}}{\begin{bmatrix}\lambda _{1}x_{1}\\\lambda _{2}x_{2}\\\vdots \\\lambda _{n}x_{n}\\\end{bmatrix}}\\&=\lambda _{1}x_{1}^{2}+\lambda _{2}x^{2}+\ldots +\lambda _{n}^{2}x_{n}^{2}\\&=\sum _{i=1}^{n}\lambda _{i}x_{i}^{2}\end{aligned}}$

展开分母得到

x^{T}x=\sum _{i=1}^{n}x_{i}^{2}

代入，

{\begin{aligned}{\frac {x^{T}\Lambda x}{x^{T}x}}&={\frac {\sum _{i=1}^{n}\lambda _{i}x_{i}^{2}}{\sum _{i=1}^{n}x_{i}^{2}}}\\&\geq \lambda _{\min }(M){\frac {\sum _{i=1}^{n}x_{i}^{2}}{\sum _{i=1}^{n}x_{i}^{2}}}\\&=\lambda _{\min }(M)\end{aligned}}

第二个不等式

从第(a)部分

(v,Av)=(v,Mv)>0\!\,

对于所有实数 $v\!\,$ .

因此 $M\!\,$ 是正定的，这意味着它所有的特征值都是正的。特别是，

\lambda _{\min }(M)>0\!\,

问题 3c

现在考虑迭代以计算一系列对 (1) 的近似解，

x_{k+1}=x_{k}+\alpha r_{k}\!\,

其中 $r_{k}=b-Ax_{k}\!\,$ 以及 $\alpha \!\,$ 被选择为最小化 $\|r_{k+1}\|_{2}\!\,$ 作为 $\alpha \!\,$ 的函数。证明

{\frac {\|r_{k+1}\|_{2}}{\|r_{k}\|_{2}}}\leq \left(1-{\frac {\lambda _{\min }(M)^{2}}{\lambda _{\max }(A^{T}A)}}\right)^{\frac {1}{2}}\!\,

解 3c

首先，我们想将 $\|r_{k+1}\|^{2}$ 写成 $\alpha \!\,$ 的函数，即

f(\alpha )=\|r_{k+1}\|^{2}\!\,

将方程 $r_{k}\!\,$ 的下标从 $k\!\,$ 更改为 $k+1\!\,$ ，用 $b-Ax_{k}\!\,$ 代入，并应用范数的定义得到，

${\begin{aligned}\|r_{k+1}\|^{2}&=\|b-Ax_{k+1}\|^{2}\\&=\|b-Ax_{k}-\alpha Ar_{k}\|^{2}\\&=\|r_{k}-\alpha Ar_{k}\|^{2}\\&=(r_{k}-\alpha Ar_{k},r_{k}-\alpha Ar_{k})\\&=(r_{k},r_{k})-\alpha (Ar_{k},r_{k})-\alpha (r_{k},Ar_{k})+\alpha ^{2}(Ar_{k},Ar_{k})\end{aligned}}$

根据内积的一个性质，以及因为 $A\!\,$ 是对称的，

(r_{k},Ar_{k})=(A^{T}r_{k},r_{k})=(Ar_{k},r_{k})\!\,

因此，

f(\alpha )=\|r_{k+1}\|^{2}=(r_{k},r_{k})-2\alpha (Ar_{k},r_{k})+\alpha ^{2}(Ar_{k},Ar_{k})\!\,

接下来我们要最小化 $f(\alpha )\!\,$ 作为 $\alpha \!\,$ 的函数。对其求 $\alpha \!\,$ 的导数，得到：

f^{\prime }(\alpha )=-2(Ar_{k},r_{k})+2\alpha (Ar_{k},Ar_{k})\!\,

令 $f^{\prime }(\alpha )=0$ 并解出 $\alpha \!\,$ ，得到

${\begin{aligned}0&=-2(Ar_{k},r_{k})+2\alpha (Ar_{k},Ar_{k})\\0&=-(Ar_{k},r_{k})+\alpha (Ar_{k},Ar_{k})\\(Ar_{k},r_{k})&=\alpha (Ar_{k},Ar_{k})\\\alpha &={\frac {(Ar_{k},r_{k})}{(Ar_{k},Ar_{k})}}\end{aligned}}$

将 $\alpha \!\,$ 代入 $\|r_{k+1}\|^{2}\!\,$ ，得到：

${\begin{aligned}\|r_{k+1}\|^{2}&=(r_{k},r_{k})-2\alpha (Ar_{k},r_{k})+\alpha ^{2}(Ar_{k},Ar_{k})\\&=(r_{k},r_{k})-2{\frac {(Ar_{k},r_{k})}{(Ar_{k},Ar_{k})}}(Ar_{k},r_{k})+{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})^{2}}}(Ar_{k},Ar_{k})\\&=(r_{k},r_{k})-2{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})}}+{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})}}\\&=(r_{k},r_{k})-{\frac {(Ar_{k},r_{k})^{2}}{(Ar_{k},Ar_{k})}}\end{aligned}}$