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

问题 1

推导出单点、双点和三点高斯求积公式，使得 $\int _{-1}^{1}f(x)x^{4}dx\approx \sum _{j=1}^{n}f(x_{j})w_{j}\!\,$ 给出这些公式误差的界限。

解答 1

找到相对于权重函数的正交多项式

对于这个问题，我们需要前三个正交多项式 $P_{1},P_{2},{\mbox{ and }}P_{3}\!\,$ 相对于加权内积

$\left\langle f,g\right\rangle =\int _{-1}^{1}f(x)g(x)w(x)dx\!\,$

其中 $w(x)=x^{4}\!\,$ 在我们的例子中。这可以通过对基 $\left\{1,x,x^{2},x^{3}\right\}\!\,$ 使用 Gram-Schmidt 正交化来完成

零阶多项式

令 $P_{0}(x)=1\!\,$

一阶多项式

${\begin{aligned}P_{1}(x)&=x-{\frac {\left\langle 1,x\right\rangle }{\left\langle 1,1\right\rangle }}\cdot 1\\&=x-\underbrace {\frac {\int _{-1}^{1}x^{5}dx}{\int _{-1}^{1}x^{4}dx}} _{\frac {0}{2/5}}\\&=x\end{aligned}}$

二阶多项式

${\begin{aligned}P_{2}(x)&=x^{2}-{\frac {\left\langle 1,x^{2}\right\rangle }{\left\langle 1,1\right\rangle }}\cdot 1-{\frac {\left\langle x,x^{2}\right\rangle }{\left\langle x,x\right\rangle }}\cdot x\\&=x^{2}-{\frac {\int _{-1}^{1}x^{6}dx}{\int _{-1}^{1}x^{4}dx}}-x\cdot \underbrace {\frac {\int _{-1}^{1}x^{7}dx}{\int _{-1}^{1}x^{6}dx}} _{\frac {0}{2/7}}\\&=x^{2}-{\frac {5}{7}}\end{aligned}}$

三阶多项式

${\begin{aligned}P_{3}(x)&=x^{3}-{\frac {\left\langle 1,x^{3}\right\rangle }{\left\langle 1,1\right\rangle }}\cdot 1-{\frac {\left\langle x,x^{3}\right\rangle }{\left\langle x,x\right\rangle }}\cdot x-{\frac {\left\langle x^{2}-{\frac {5}{7}},x^{3}\right\rangle }{\left\langle x^{2}-{\frac {5}{7}},x^{2}-{\frac {5}{7}}\right\rangle }}\cdot (x^{2}-{\frac {5}{7}})\\&=x^{3}-0-{\frac {7}{2}}x\cdot {\frac {\int _{-1}^{1}x^{8}dx}{\int _{-1}^{1}x^{6}dx}}-0\\&=x^{3}-{\frac {7}{9}}x\end{aligned}}$

求多项式的根

这些多项式的根将用作高斯求积中的插值节点。

${\begin{array}{|c|c|}{\mbox{Polynomial}}&{\mbox{Roots}}\\\hline P_{1}(x)=x&0\\\\P_{2}(x)=x^{2}-{\frac {5}{7}}&\pm {\sqrt {\frac {5}{7}}}\\\\P_{3}(x)=x^{3}-{\frac {7}{9}}x&0,\pm {\sqrt {\frac {7}{9}}}\\\\\hline \end{array}}$

计算系数的公式

在高斯求积中，我们有

$w_{j}=\int _{-1}^{1}l_{i}(x)x^{4}dx\!\,$，其中

$l_{i}(x)=\prod _{j=1,j\neq i}^{n}{\frac {x-x_{j}}{x_{i}-x_{j}}}\!\,$

1点公式

$l_{1}(x)=1\!\,$

$w_{1}=\int _{-1}^{1}x^{4}dx={\frac {2}{5}}\!\,$

$\int _{-1}^{1}f(x)x^{4}dx\approx {\frac {2}{5}}f(x_{1})\!\,$

其中 $x_{1}\!\,$ 是 $P_{1}(x)\!\,$ 的根。

2 点公式

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

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

$w_{1}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{1}-x_{2}}}x^{4}dx={\frac {2x_{2}}{5(x_{2}-x_{1})}}\!\,$

$w_{2}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{2}-x_{1}}}x^{4}dx={\frac {2x_{1}}{5(x_{1}-x_{2})}}\!\,$

$\int _{-1}^{1}f(x)x^{4}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})\!\,$

其中 $x_{1}{\mbox{ and }}x_{2}\!\,$ 是 $P_{2}(x)\!\,$ 的根。

3 点公式

$l_{1}(x)={\frac {x-x_{2}}{x_{1}-x_{2}}}{\frac {x-x_{3}}{x_{1}-x_{3}}}\!\,$

$l_{2}(x)={\frac {x-x_{1}}{x_{2}-x_{1}}}{\frac {x-x_{3}}{x_{2}-x_{3}}}\!\,$

$l_{3}(x)={\frac {x-x_{1}}{x_{3}-x_{1}}}{\frac {x-x_{2}}{x_{3}-x_{2}}}\!\,$

$w_{1}=\int _{-1}^{1}{\frac {x-x_{2}}{x_{1}-x_{2}}}{\frac {x-x_{3}}{x_{1}-x_{3}}}x^{4}dx={\frac {1}{(x_{1}-x_{2})(x_{1}-x_{3})}}\left({\frac {2}{7}}+{\frac {2x_{2}x_{3}}{5}}\right)\!\,$

$w_{2}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{2}-x_{1}}}{\frac {x-x_{3}}{x_{2}-x_{3}}}x^{4}dx={\frac {1}{(x_{2}-x_{1})(x_{2}-x_{3})}}\left({\frac {2}{7}}+{\frac {2x_{1}x_{3}}{5}}\right)\!\,$

$w_{3}=\int _{-1}^{1}{\frac {x-x_{1}}{x_{3}-x_{1}}}{\frac {x-x_{2}}{x_{3}-x_{2}}}x^{4}dx={\frac {1}{(x_{3}-x_{1})(x_{3}-x_{2})}}\left({\frac {2}{7}}+{\frac {2x_{1}x_{2}}{5}}\right)\!\,$

$\int _{-1}^{1}f(x)x^{4}dx\approx w_{1}f(x_{1})+w_{2}f(x_{2})+w_{3}f(x_{3})\!\,$

其中 $x_{1}{\mbox{, }}x_{2}{\mbox{ and }}x_{3}\!\,$ 是 $P_{3}(x)\!\,$ 的根。

推导误差界

我们知道，这种求积公式对所有次数不超过 $2n-1\!\,$ 的多项式是精确的。

我们选择一个次数不超过 $2n-1\!\,$ 的多项式 $p\!\,$，它对 Hermite 插值，即

$p(x_{i})=f(x_{i})\quad p'(x_{i})=f'(x_{i})\quad (0\leq i\leq n-1)\!\,$

这种插值的误差是

$f(x)-p(x)={\frac {f^{(2n)}(\zeta (x))}{(2n)!}}\prod _{i=0}^{n-1}(x-x_{i})^{2}\!\,$

按照以下步骤计算求积公式的误差

${\begin{aligned}E&=\int _{-1}^{1}f(x)x^{4}dx-\sum _{i=0}^{n-1}w_{i}f(x_{i})\\&=\int _{-1}^{1}f(x)x^{4}dx-\sum _{i=0}^{n-1}w_{i}p(x_{i})\\&=\int _{-1}^{1}f(x)x^{4}dx-\int _{-1}^{1}p(x)x^{4}dx\\&=\int _{-1}^{1}(f(x)-p(x))x^{4}dx\\&=\int _{-1}^{1}{\frac {f^{(2n)}(\zeta (x))}{(2n)!}}\prod _{i=0}^{n-1}(x-x_{i})^{2}\cdot x^{4}dx\\&={\frac {f^{(2n)}(\xi )}{(2n)!}}\int _{-1}^{1}x^{4}\cdot \underbrace {\prod _{i=0}^{n-1}(x-x_{i})^{2}} _{(p_{n}(x))^{2}}dx\end{aligned}}\!\,$

其中最后一行来自积分的均值定理。

注意 $p_{n}(x)\!\,$ 仅仅是关于权重函数正交的多项式，因为 $x_{i}\!\,$ 是多项式的根。

因此，1点高斯求积的误差为

${\begin{aligned}E&={\frac {f^{(2)}(\xi )}{(2)!}}\int _{-1}^{1}x^{4}\cdot x^{2}dx\\&={\frac {f^{(2)}(\xi )}{7}}\end{aligned}}\!\,$

2点求积的误差

${\begin{aligned}E&={\frac {f^{(4)}(\xi )}{(4)!}}\int _{-1}^{1}x^{4}\cdot (x^{2}-{\frac {5}{7}})^{2}dx\end{aligned}}\!\,$

3点求积的误差

${\begin{aligned}E&={\frac {f^{(6)}(\xi )}{(6)!}}\int _{-1}^{1}x^{4}\cdot (x^{3}-{\frac {7}{9}}x)^{2}dx\end{aligned}}\!\,$

问题 2

我们希望用迭代方法求解 $Ax=b\!\,$，其中 $A={\begin{bmatrix}1&1&-1\\1&2&1\\1&1&1\end{bmatrix}}\!\,$ 证明对于该 $A\!\,$，雅可比迭代法和高斯-赛德尔迭代法都收敛。解释为什么对于该 $A\!\,$，其中一种方法比另一种方法更好。

解题 2

雅可比迭代法

将 $A\!\,$ 分解成对角、下三角和上三角部分，即

$A=D+(L+U)\!\,$

通过以下方式解出 x 来推导雅可比迭代法：

${\begin{aligned}Ax&=b\\(D+(L+U))x&=b\\Dx+(L+U)x&=b\\Dx&=b-(L+U)x\\x&=D^{-1}(b-(L+U)x)\end{aligned}}\!\,$

高斯-赛德尔迭代法

将 $A\!\,$ 分解成对角、下三角和上三角部分，即

$A=(D+L)+U\!\,$

通过以下方式解出 x 来推导高斯-赛德尔迭代法：

${\begin{aligned}Ax&=b\\((D+L)+U)x&=b\\(D+L)x+Ux&=b\\(D+L)x&=b-Ux\\x&=(D+L)^{-1}(b-Ux)\end{aligned}}\!\,$

雅可比收敛性

如果 $D^{-1}(L+U)\!\,$ 的谱半径小于 1，即雅可比迭代法收敛。

$\rho (D^{-1}(L+U))<1\!\,$

矩阵的特征值为

$D^{-1}(L+U)={\begin{bmatrix}0&1&-1\\{\frac {1}{2}}&0&{\frac {1}{2}}\\1&1&0\end{bmatrix}}\!\,$

是 $\lambda =0,0,0\!\,$，即特征值 $0\!\,$ 的阶数为 3。

因此，谱半径为 $\rho =0<1\!\,$.

高斯-赛德尔迭代收敛

如果 $(D+L)^{-1}U\!\,$ 的谱半径小于 1，则高斯-赛德尔迭代收敛，即

$\rho ((D+L)^{-1}U)<1\!\,$

矩阵的特征值为

$(D+L)^{-1}U={\begin{bmatrix}0&1&-1\\0&-{\frac {1}{2}}&1\\0&-{\frac {1}{2}}&0\end{bmatrix}}\!\,$

是 $\lambda =0,-{\frac {1}{4}}+{\frac {{\sqrt {7}}i}{4}},-{\frac {1}{4}}-{\frac {{\sqrt {7}}i}{4}}\!\,$

因此，谱半径为 $\rho ={\sqrt {{\frac {1}{16}}+{\frac {7}{16}}}}={\frac {\sqrt {2}}{2}}\approx .7<1\!\,$.

方法比较

通常，高斯-赛德尔迭代比雅可比迭代收敛更快，因为高斯-赛德尔迭代使用新的$x_{i}\!\,$ 分量，当它们可用时，但在这种情况下，$\rho _{Jacobi}<\rho _{Gauss-Seidel}\!\,$，因此雅可比迭代速度更快。

问题 3

考虑以下三项多项式递归 $p_{k+1}(x)=(x-\mu _{k})p_{k}(x)-\nu _{k}^{2}p_{k-1}(x)\quad {\mbox{ for }}k=1,2,\dots ,\!\,$ 由$p_{0}(x)=1{\mbox{ and }}p_{1}(x)=x-\mu _{0}\!\,$ 初始化，其中每个$\mu _{k}{\mbox{ and }}\nu _{k}\!\,$ 都是实数，每个$\nu _{k}\!\,$ 都不为零。

问题 3a

证明每个$p_{k}(x)\!\,$ 是一个首一多项式，其度数为$k\!\,$，并且对于每个$n=0,1,\dots \!\,$，有 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{n}(x)\right\}=\operatorname {span} \left\{1,x,x^{2},\dots ,x^{n}\right\}\!\,$

解 3a

我们通过归纳法证明该结论。

基本情况

$p_{0}(x)=1\!\,$ 是一个首一多项式，次数为零，且 $\operatorname {span} \left\{p_{0}(x)\right\}=\operatorname {span} \left\{1\right\}\!\,$。

$p_{1}(x)=x-\mu _{0}\!\,$ 是一个首一多项式，次数为一，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x)\right\}=\operatorname {span} \left\{1,x\right\}\!\,$。

$p_{2}(x)=(x-\mu _{0})(x-\mu _{1})-\nu _{1}^{2}\!\,$ 是一个首一多项式，次数为 2，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),p_{2}(x)\right\}=\operatorname {span} \left\{1,x,x^{2}\right\}\!\,$。

归纳步骤

假设 $p_{k-1}(x)\!\,$ 是一个首一多项式，次数为 $k-1\!\,$，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{k-1}(x)\right\}=\operatorname {span} \left\{1,x,\dots ,x^{k-1}\right\}\!\,$。

同时假设 $p_{k}(x)\!\,$ 是一个首一多项式，次数为 $k\!\,$，且 $\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{k}(x)\right\}=\operatorname {span} \left\{1,x,\dots ,x^{k}\right\}\!\,$。

然后从假设来看，$p_{k+1}(x)=(x-\mu _{k})p_{k}(x)-\nu _{k}^{2}p_{k-1}(x)\!\,$ 是一个首项系数为1，次数为 $k+1\!\,$ 的多项式。

同时，

$\operatorname {span} \left\{p_{0}(x),p_{1}(x),\dots ,p_{k+1}(x)\right\}=\operatorname {span} \left\{1,x,\dots ,x^{k+1}\right\}\!\,$

因为 $p_{k+1}(x)\!\,$ 只是 $x^{n+1}\!\,$ 加上在 $\operatorname {span} \left\{1,x,\dots ,x^{k}\right\}\!\,$ 中已经存在的低阶项的线性组合。

问题 3b

证明对每个 $k=0,1,\dots \!\,$，多项式 $p_{k}(x)\!\,$ 有 $k\!\,$ 个单根实根，它们与 $p_{k-1}(x)\!\,$ 的根交错排列。

解答 3b

我们通过数学归纳法来证明这个结论。

基本情况

让我们考虑 $k=2\!\,$ 的情况。我们知道

$p_{2}(x)=(x-\mu _{0})(x-\mu _{1})-\nu _{1}^{2}.\!\,$

二次方程公式表明 $p_{2}(x)\!\,$ 有两个简单的实根。

令 $r_{21}\!\,$ 和 $r_{22}\!\,$ 为 $p_{2}(x)\!\,$ 的零点。然后，我们有（因为符号变化）

$p_{2}(\mu _{0})=-\nu _{1}^{2}\!\,$ 和 $\lim _{x\rightarrow \infty }p_{2}(x)>0\!\,$ $\Rightarrow \!\,$ 存在 $r_{22}\in (\mu _{0},\infty )\!\,$ 使得 $p_{2}(r_{22})=0\!\,$。

$p_{2}(\mu _{0})=-\nu _{1}^{2}\!\,$ 和 $\lim _{x\rightarrow -\infty }p_{2}(x)>0\!\,$ $\Rightarrow \!\,$ 存在 $r_{21}\in (-\infty ,\mu _{0})\!\,$ 使得 $p_{2}(r_{21})=0\!\,$。

总之，$r_{21}<\underbrace {\mu _{0}} _{r_{11}}<r_{22}.\!\,$.

归纳步骤

设$r_{k-1,1},\dots ,r_{k-1,k-1}\!\,$ 和 $r_{k,1},\dots ,r_{k,k}\!\,$ 分别是$p_{k-1}(x)\!\,$ 和 $p_{k}(x)\!\,$ 的简单实根，使得$p_{k}\!\,$ 的根与$p_{k-1}\!\,$ 的根交错，即

$r_{k,1}<r_{k-1,1}<r_{k,2}<r_{k-1,2}<\dots <r_{k-1,k-1}<r_{k,k}.\!\,$

那么，我们有

$p_{k+1}(r_{k,1})=(r_{k,1}-\mu _{k})\underbrace {p_{k}(r_{k,1})} _{0}-\nu _{k}^{2}p_{k-1}(r_{k,1})=-\nu _{k}^{2}p_{k-1}(r_{k,1}),\!\,$

$p_{k+1}(r_{k,2})=(r_{k,2}-\mu _{k})\underbrace {p_{k}(r_{k,2})} _{0}-\nu _{k}^{2}p_{k-1}(r_{k,2})=-\nu _{k}^{2}p_{k-1}(r_{k,2}).\!\,$

根据归纳假设，$p_{k-1}(r_{k,1})\!\,$ 和 $p_{k-1}(r_{k,2})\!\,$ 具有不同的符号，因为 $r_{k,1}<r_{k-1,1}<r_{k,2}\!\,$。因此，存在一个 $r_{k+1,1}\in (r_{k,1},r_{k,2})\!\,$ 使得 $p_{k+1}(r_{k+1,1})=0\!\,$。

对所有区间 $(r_{k,j},r_{k,j+1})\!\,$ 以相同的方式进行，我们得到存在一个 $r_{k+1,j}\in (r_{k,j},r_{k,j+1})\!\,$ 使得 $p_{k+1}(r_{k+1,j})=0\!\,$ 对于 $j=1,\dots ,k-1.\!\,$

现在我们考虑 $p_{k+1}\!\,$ 最小的和最大的根，即 $r_{k+1,0},r_{k+1,k+1}\!\,$

因为对于 $k=0,1,2,\ldots \!\,$，$p_{k}\!\,$ 是一个首一多项式，

$\lim _{x\rightarrow \infty }p_{k}(x)=\infty \!\,$

因此，对于任何 $x>r_{k}\!\,$（任何大于 $p_{k}\!\,$ 最大根的 $x\!\,$）

$p_{k}(x)>0\!\,$

因此

$\lim _{x\rightarrow \infty }p_{k+1}(x)>0\!\,$ 和 $p_{k+1}(r_{k,k})=-\nu _{k}^{2}p_{k-1}(r_{k,k})<0,\!\,$

意味着存在 $r_{k+1,k}\in (r_{k,k},\infty )\!\,$ 使得 $p_{k+1}(r_{k+1,k})=0\!\,$.

如果 $k+1\!\,$ 是偶数，则根据类似的推理

$\lim _{x\rightarrow -\infty }p_{k+1}(x)>0\!\,$ 和 $p_{k+1}(r_{k,1})=-\nu _{k}^{2}p_{k-1}(r_{k,1})<0,\!\,$ $\Rightarrow \!\,$ 存在 $r_{k+1,0}\in (-\infty ,r_{k,1})\!\,$ 使得 $p_{k+1}(r_{k+1,0})=0\!\,$.

如果 $k+1\!\,$ 是奇数，

$\lim _{x\rightarrow -\infty }p_{k+1}(x)<0\!\,$ 并且 $p_{k+1}(r_{k,1})=-\nu _{k}^{2}p_{k-1}(r_{k,1})>0,\!\,$ $\Rightarrow \!\,$ 存在 $r_{k+1,0}\in (-\infty ,r_{k,1})\!\,$ 使得 $p_{k+1}(r_{k+1,0})=0\!\,$。

问题 3c

证明对于每个 $n=0,1,\dots \!\,$，$p_{k+1}(x)\!\,$ 的根是以下对称三对角矩阵的特征值 $T={\begin{pmatrix}\mu _{0}&\nu _{1}&0&\cdots &0\\\nu _{1}&\mu _{1}&\nu _{2}&\ddots &\vdots \\0&\nu _{2}&\nu _{2}&\ddots &0\\\vdots &\ddots &\ddots &\ddots &\nu _{n}\\0&\cdots &0&\nu _{n}&\mu _{n}\end{pmatrix}}$

解 3c

令 $T_{n+1}={\begin{pmatrix}\mu _{0}&\nu _{1}&0&\cdots &0\\\nu _{1}&\mu _{1}&\nu _{2}&\ddots &\vdots \\0&\nu _{2}&\nu _{2}&\ddots &0\\\vdots &\ddots &\ddots &\ddots &\nu _{n}\\0&\cdots &0&\nu _{n}&\mu _{n}\end{pmatrix}}$

那么 $\operatorname {det} (xI_{n+1}-T_{n+1})\!\,$ 是一个关于 $x\!\,$ 的首一多项式，其次数为 $n+1\!\,$。

沿着最后一行展开这个行列式，我们得到

$\operatorname {det} (xI_{n+1}-T_{n+1})=(x-\mu _{n})\operatorname {det} (xI_{n}-T_{n})-\nu _{n}^{2}\operatorname {det} (xI_{n-1}-T_{n-1})\qquad (1)\!\,$

其中 $\operatorname {det} (xI_{n}-T_{n})\!\,$ 和 $\operatorname {det} (xI_{n-1}-T_{n-1})\!\,$ 分别是次数为 $n\!\,$ 和 $n-1\!\,$ 的首一多项式。

注意 $\operatorname {det} (xI_{1}-T_{1})=x-\mu _{0}\equiv p_{1}(x)\!\,$，并且如果我们令 $p_{0}(x)\equiv 1\!\,$，那么 (1) 等价于问题中陈述的三项递推关系。

因此，$p_{n+1}(x)\equiv \operatorname {det} (xI_{n+1}-T_{n+1})=0\!\,$ 表明 $p_{n+1}(x)\!\,$ 的根是 $T_{n+1}\!\,$ 的特征值。