109 年 國立清華大學生命科學院聯招：分子與細胞生物研究所、分子醫學研究所、生物資訊與結構生物研究所、生物科技研究所、系統神經科學研究所丙組《計算機概論(演算法與計算機數學)》

核心觀念

本題考查矩陣與向量乘法、特徵值、譜分解，以及奇異值。

• 矩陣乘法：直接以矩陣的每一列與向量做內積。
• 特徵值：解特徵方程
  $\det(A-\lambda I)=0$
• 譜分解：若 $A$ 為實對稱矩陣，則可寫成
  $A=Q\Lambda Q^{T}=\sum_i \lambda_i\vec{u}_i\vec{u}_i^{T}$
  其中 $\vec{u}_i$ 為單位正交特徵向量。
• 奇異值：奇異值是 $A^{T}A$ 特徵值的平方根。若 $A$ 為實對稱矩陣，且特徵值為實數，則奇異值為特徵值的絕對值。

---

解題方法

（a）計算 $A\vec{c}$

將矩陣的每一列分別與 $\vec{c}$ 做內積：

$$A\vec{c} = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} 3\\ 0\\ 1 \end{bmatrix}$$

因此

$$A\vec{c} = \begin{bmatrix} 2(3)+(-1)(0)+0(1)\\ (-1)(3)+2(0)+0(1)\\ 0(3)+0(0)+2(1) \end{bmatrix} = \begin{bmatrix} 6\\ -3\\ 2 \end{bmatrix}$$

---

（b）計算 $A$ 的特徵值

先求特徵方程。由於 $A$ 的第三列、第三行與前兩維分離，行列式可直接分塊計算：

$$A-\lambda I = \begin{bmatrix} 2-\lambda & -1 & 0\\ -1 & 2-\lambda & 0\\ 0 & 0 & 2-\lambda \end{bmatrix}$$

所以

$$\det(A-\lambda I) = (2-\lambda) \det \begin{bmatrix} 2-\lambda & -1\\ -1 & 2-\lambda \end{bmatrix}$$ $$= (2-\lambda)\left[(2-\lambda)^2-1\right]$$

利用平方差：

$$\det(A-\lambda I) = (2-\lambda)(1-\lambda)(3-\lambda)$$

令特徵方程等於零：

$$(2-\lambda)(1-\lambda)(3-\lambda)=0$$

因此 $A$ 的特徵值為

$$\boxed{\lambda=1,\ 2,\ 3}$$

---

（c）求 $A$ 的譜分解

特徵值 $\lambda=1$

解

$$(A-I)\vec{x}=0$$ $$A-I= \begin{bmatrix} 1 & -1 & 0\\ -1 & 1 & 0\\ 0 & 0 & 1 \end{bmatrix}$$

可得 $x=y$ 且 $z=0$，因此特徵向量可取

$$\begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix}$$

其單位化結果為

$$\vec{u}_1= \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ 1\\ 0 \end{bmatrix}$$

特徵值 $\lambda=3$

解

$$(A-3I)\vec{x}=0$$ $$A-3I= \begin{bmatrix} -1 & -1 & 0\\ -1 & -1 & 0\\ 0 & 0 & -1 \end{bmatrix}$$

可得 $x=-y$ 且 $z=0$，因此單位特徵向量可取

$$\vec{u}_3= \frac{1}{\sqrt{2}} \begin{bmatrix} 1\\ -1\\ 0 \end{bmatrix}$$

特徵值 $\lambda=2$

解

$$(A-2I)\vec{x}=0$$ $$A-2I= \begin{bmatrix} 0 & -1 & 0\\ -1 & 0 & 0\\ 0 & 0 & 0 \end{bmatrix}$$

可得 $x=y=0$，而 $z$ 任意，因此單位特徵向量為

$$\vec{u}_2= \begin{bmatrix} 0\\ 0\\ 1 \end{bmatrix}$$

三個單位特徵向量彼此正交。令

本題考查 LU 分解（特別是 Doolittle 或 Crout 方法的一種變體）在矩陣上的具體實現過程，以及如何追蹤矩陣元素在演算法執行過程中的變化。

核心觀念：

1. LU 分解： 將一個方陣 $A$ 分解為一個下三角矩陣 $L$ 和一個上三角矩陣 $U$ 的乘積，即 $A = LU$。
2. 高斯消去法與 LU 分解的關係： LU 分解的過程與高斯消去法類似，消去過程中的乘數（或稱因子）可以記錄在 $L$ 矩陣中，而消去後得到的上三角矩陣就是 $U$。
3. 原地儲存： 演算法將 $L$ 和 $U$ 的結果儲存在原始矩陣 $A$ 的空間中。通常，對角線元素保留給 $U$（或 $L$），對角線以下的元素儲存 $L$ 的元素，對角線以上的元素儲存 $U$ 的元素。然而，本題提供的演算法是將 $L$ 的元素（乘數 $r$）直接寫入 $A(k,i)$，然後在 $j$ 迴圈中更新 $A(k,j)$。這意味著，最終的矩陣 $A$ 將包含 $U$ 的上三角部分和 $L$ 的下三角部分（不含對角線）。

演算法分析：
該演算法實際上是在進行高斯消去法，並將消去過程中的乘數（$r$）直接存入矩陣的下三角位置。
對於 $A(i,i)$，它在 $i$ 迴圈開始時是原始矩陣的對角線元素，但在 $k$ 迴圈中，如果 $k>i$，那麼 $A(i,i)$ 可能會被更新。
然而，仔細觀察演算法：

• 外層迴圈 for i = 1, 2, ..., n-1 控制了主元（pivot）的行。
• 中間迴圈 for k = i + 1, i + 2, ..., n 遍歷需要被消去的行。
• r = A(k, i)/A(i,i)：計算乘數。這裡的 A(i,i) 是在當前 i 迴圈開始時的對角線元素。
• A(k,i) = r：將乘數存入 $A(k,i)$。這意味著 $A$ 的下三角部分（不含對角線）將被 $L$ 的元素覆蓋。
• 內層迴圈 for j = i + 1, i + 2, ..., n 對當前行 $k$ 的剩餘元素進行更新。
• A(k, j) = A(k, j) - r * A(i, j)：這是高斯消去的核心步驟，將 $A(i,j)$ 的倍數從 $A(k,j)$ 中減去。

這個演算法實際上是直接在 $A$ 矩陣上進行高斯消去，並將消去因子存入下三角位置。最終的矩陣 $A$ 將包含：

• 對角線元素 $A(i,i)$：這些是 $U$ 矩陣的對角線元素。
• 下三角元素 $A(k,i)$ (其中 $k>i$)：這些是 $L$ 矩陣的元素（即乘數 $r$）。
• 上三角元素 $A(k,j)$ (其中 $j>k$)：這些是 $U$ 矩陣的元素。

矩陣 $A$ 為：

$$A = \begin{bmatrix} 2 & 1 & 1 \\ 4 & -6 & 0 \\ -2 & 7 & 2 \end{bmatrix}$$

$n=3$。

Step 1: i = 1

• A(1,1) = 2。
• k = 2:
  • r = A(2,1) / A(1,1) = 4 / 2 = 2.
  • A(2,1) = r = 2.
  • j = 2: A(2,2) = A(2,2) - r * A(1,2) = -6 - 2 * 1 = -6 - 2 = -8.
  • j = 3: A(2,3) = A(2,3) - r * A(1,3) = 0 - 2 * 1 = -2.

本題主要考查級數求和、二項式定理的應用。

核心觀念：

1. 階乘： $n! = n \times (n-1) \times \dots \times 1$。
2. 二項式定理： $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$。
3. 組合數性質： $\sum_{k=0}^n \binom{n}{k} = 2^n$。

(a) 計算 $\sum_{k=0}^4 k!$
我們需要計算從 $k=0$ 到 $k=4$ 的階乘之和。
$0! = 1$
$1! = 1$
$2! = 2 \times 1 = 2$
$3! = 3 \times 2 \times 1 = 6$
$4! = 4 \times 3 \times 2 \times 1 = 24$
所以，

$$\sum_{k=0}^4 k! = 0! + 1! + 2! + 3! + 4! = 1 + 1 + 2 + 6 + 24 = 34$$

【答案】34

(b) 計算 $\sum_{k=0}^4 \binom{4}{k} 2^k$
這是一個二項式定理的形式。二項式定理是 $(x+y)^n = \sum_{k=0}^n \binom{n}{k} x^{n-k} y^k$。
我們的級數是 $\sum_{k=0}^4 \binom{4}{k} 2^k$。
我們可以將其與二項式定理對比。令 $n=4$。
我們需要將級數寫成 $\binom{4}{k} x^{4-k} y^k$ 的形式。

本題考查指數分佈的性質、期望值、變異數、動差生成函數以及和的分配。

核心觀念：

1. 指數分佈 (Exponential Distribution)： 具有機率密度函數 $f(x; \lambda) = \lambda e^{-\lambda x}$，用於描述發生時間的間隔。其期望值為 $E(X) = 1/\lambda$，變異數為 $Var(X) = 1/\lambda^2$。動差生成函數為 $M_X(t) = \frac{\lambda}{\lambda-t}$。
2. 獨立同分佈 (i.i.d.) 隨機變數的和： 若 $X_1, \ldots, X_n$ 是獨立同分佈的隨機變數，且 $Y = \sum_{i=1}^n X_i$，則 $E(Y) = \sum_{i=1}^n E(X_i)$，$Var(Y) = \sum_{i=1}^n Var(X_i)$。若它們具有動差生成函數 $M_X(t)$，則 $Y$ 的動差生成函數為 $(M_X(t))^n$。
3. Gamma 分佈： 指數分佈是 Gamma 分佈的一種特殊情況 (當形狀參數 $k=1$ 時)。$n$ 個獨立同分佈的指數分佈隨機變數的和服從 Gamma 分佈。

給定的指數分佈的機率密度函數是 $f(x) = \frac{1}{2}e^{-x/2}$，其中 $x \ge 0$。
這對應於標準形式 $f(x; \lambda) = \lambda e^{-\lambda x}$，所以我們可以看到 $\lambda = \frac{1}{2}$。

(a) 計算 $E(X_1)$ 和 $Var(X_1)$
對於具有參數 $\lambda = \frac{1}{2}$ 的指數分佈：
期望值 $E(X_1) = \frac{1}{\lambda} = \frac{1}{1/2} = 2$。
變異數 $Var(X_1) = \frac{1}{\lambda^2} = \frac{1}{(1/2)^2} = \frac{1}{1/4} = 4$。

【答案】$E(X_1) = 2$, $Var(X_1) = 4$。

(b) $X_n$ 的動差生成函數
由於 $X_1, X_2, \ldots, X_n$ 是獨立同分佈的，它們具有相同的機率密度函數，因此也具有相同的動差生成函數。
對於一個指數分佈，其動差生成函數為 $M_X(t) = \frac{\lambda}{\lambda-t}$。
在這裡，$\lambda = \frac{1}{2}$。
所以，對於 $X_n$ (以及任何 $X_i$)，動差生成函數為：
$M_{X_n}(t) = \frac{1/2}{1/2 - t}$。

【答案】$M_{X_n}(t) = \frac{1/2}{1/2 - t}$。

本題考查標準常態分佈的性質，以及線性變換對隨機變數期望值、變異數、機率密度函數和動差生成函數的影響。

核心觀念：

1. 標準常態分佈 (Standard Normal Distribution)： 期望值 $E(Z)=0$，變異數 $Var(Z)=1$。動差生成函數 $M_Z(t) = e^{t^2/2}$。
2. 線性變換： 對於隨機變數 $Z$ 和常數 $a, b$，令 $Y = aZ + b$。
   • 期望值：$E(Y) = aE(Z) + b$。
   • 變異數：$Var(Y) = a^2 Var(Z)$。
   • 動差生成函數：$M_Y(t) = E(e^{tY}) = E(e^{t(aZ+b)}) = E(e^{atZ} e^{bt}) = e^{bt} E(e^{(at)Z}) = e^{bt} M_Z(at)$。
   • 機率密度函數 (PDF)：可通過變數變換法求得。若 $Y=aZ+b$，則 $f_Y(y) = \frac{1}{|a|} f_Z\left(\frac{y-b}{a}\right)$。

給定的標準常態分佈的 PDF 是 $f_Z(x) = \frac{1}{\sqrt{2\pi}}e^{-x^2/2}$。
我們知道 $E(Z)=0$ 和 $Var(Z)=1$。
新隨機變數 $Y = 2Z + 3$。這裡 $a=2$, $b=3$。

(a) 計算 $E(Y)$ 和 $Var(Y)$
使用線性變換的性質：
$E(Y) = aE(Z) + b = 2 \cdot 0 + 3 = 3$。
$Var(Y) = a^2 Var(Z) = 2^2 \cdot 1 = 4 \cdot 1 = 4$。

【答案】$E(Y) = 3$, $Var(Y) = 4$。

(b) $Y$ 的機率密度函數
使用變數變換法。令 $y = 2z+3$。則 $z = \frac{y-3}{2}$。
所以 $a=2$, $b=3$。
$f_Y(y) = \frac{1}{|a|} f_Z\left(\frac{y-b}{a}\right) = \frac{1}{|2|} f_Z\left(\frac{y-3}{2}\right)$。