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