數值方法資格考試問題及解答（馬里蘭大學）/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\!\,$