111 年 國立成功大學工程科學系碩士班丙組《計算機數學》

題目辨識說明

掃描圖中的矩陣為

$$A=\begin{pmatrix}1&-1\\1&-\frac32\end{pmatrix},$$

與文字所列的矩陣不一致。以下依照掃描圖中的實際內容作答。

核心觀念

求特徵值使用特徵方程式

$$\det(A-\lambda I)=0。$$

若矩陣可對角化為 $A=PDP^{-1}$，則

$$A^k=PD^kP^{-1},$$

可藉由觀察特徵值的絕對值判斷矩陣冪的極限。

(a) 特徵值與特徵向量

先求特徵方程式：

$$\det(A-\lambda I) = \det\begin{pmatrix} 1-\lambda&-1\\ 1&-\frac32-\lambda \end{pmatrix}.$$

因此

$$\det(A-\lambda I) =(1-\lambda)\left(-\frac32-\lambda\right)+1.$$

整理得

$$\det(A-\lambda I) =\lambda^2+\frac12\lambda-\frac12 =\left(\lambda-\frac12\right)(\lambda+1).$$

所以特徵值為

$$\lambda_1=\frac12,\qquad \lambda_2=-1。$$

當 $\lambda_1=\frac12$

解

$$\left(A-\frac12I\right) \begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}.$$

即

$$\begin{pmatrix} \frac12&-1\\ 1&-2 \end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}.$$

由 $\frac12x-y=0$ 得 $x=2y$，可取

$$\mathbf v_1=\begin{pmatrix}2\\1\end{pmatrix}.$$

當 $\lambda_2=-1$

解

$$(A+I) \begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}.$$

即

$$\begin{pmatrix} 2&-1\\ 1&-\frac12 \end{pmatrix} \begin{pmatrix}x\\y\end{pmatrix} = \begin{pmatrix}0\\0\end{pmatrix}.$$

由 $2x-y=0$ 得 $y=2x$，可取

$$\mathbf v_2=\begin{pmatrix}1\\2\end{pmatrix}.$$

核心觀念

本題考查遞迴式展開與遞迴深度分析。基本形式為

$$f(n)=2f(\sqrt n)+\log_2 n.$$

每遞迴一次，輸入變為原來的平方根，且遞迴項前的係數乘以 $2$。

---

(a) 計算 $f(30)$

題目明確規定遞迴式只在「$n$ 為大於 $1$ 的完全平方數」時成立。

然而，

$$30$$

不是完全平方數，因此不能直接使用

$$f(30)=2f(\sqrt{30})+\log_2 30.$$

而且題目只提供 $f(2)=1$，未提供 $f(30)$ 或 $f(\sqrt{30})$ 的定義。因此 $f(30)$ 無法由題目條件唯一決定。

---

(b) Big-O 估計

若依一般遞迴分析的標準假設，將遞迴式視為對所有足夠大的 $n$ 皆成立，並在遞迴縮小至 $2$ 時停止，展開 $k$ 次可得

$$\begin{aligned} f(n) &=2f(n^{1/2})+\log_2 n\\ &=4f(n^{1/4})+2\log_2 n\\ &=8f(n^{1/8})+3\log_2 n\\ &\;\;\vdots\\ &=2^k f\left(n^{1/2^k}\right)+k\log_2 n. \end{aligned}$$

當遞迴終止於 $2$ 時，

$$n^{1/2^k}=2.$$

取 $\log_2$ 得

本題考查線性常係數齊次遞迴關係式的求解。

給定的遞迴關係式為 $T_n = 3 T_{n-1} - 3 T_{n-2}$。
這是二階線性常係數齊次遞迴關係式。
其特徵方程式為：
$r^2 = 3r - 3$
$r^2 - 3r + 3 = 0$

我們需要求解這個二次方程式的根。
使用二次公式 $r = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$：
$r = \frac{-(-3) \pm \sqrt{(-3)^2 - 4(1)(3)}}{2(1)}$
$r = \frac{3 \pm \sqrt{9 - 12}}{2}$
$r = \frac{3 \pm \sqrt{-3}}{2}$
$r = \frac{3 \pm i\sqrt{3}}{2}$
所以，特徵根是兩個複數：
$r_1 = \frac{3}{2} + i\frac{\sqrt{3}}{2}$
$r_2 = \frac{3}{2} - i\frac{\sqrt{3}}{2}$

這兩個複數根可以寫成極座標形式 $r = \rho (\cos \theta + i \sin \theta)$。
其中，$\rho = |r| = \sqrt{(\frac{3}{2})^2 + (\frac{\sqrt{3}}{2})^2} = \sqrt{\frac{9}{4} + \frac{3}{4}} = \sqrt{\frac{12}{4}} = \sqrt{3}$。
而 $\theta$ 滿足 $\cos \theta = \frac{3/2}{\sqrt{3}} = \frac{3}{2\sqrt{3}} = \frac{\sqrt{3}}{2}$，且 $\sin \theta = \frac{\sqrt{3}/2}{\sqrt{3}} = \frac{1}{2}$。
所以，$\theta = \frac{\pi}{6}$ (或 30 度)。

因此，特徵根可以寫成：
$r_1 = \sqrt{3} \left( \cos\left(\frac{\pi}{6}\right) + i \sin\left(\frac{\pi}{6}\right) \right)$
$r_2 = \sqrt{3} \left( \cos\left(-\frac{\pi}{6}\right) + i \sin\left(-\frac{\pi}{6}\right) \right) = \sqrt{3} \left( \cos\left(\frac{\pi}{6}\right) - i \sin\left(\frac{\pi}{6}\right) \right)$

當特徵根是共軛複數 $r_{1,2} = \rho (\cos \theta \pm i \sin \theta)$ 時，遞迴關係式的通解形式為：
$T_n = \rho^n (C_1 \cos(n\theta) + C_2 \sin(n\theta))$
在這裡，$\rho = \sqrt{3}$ 且 $\theta = \frac{\pi}{6}$。
$T_n = (\sqrt{3})^n \left( C_1 \cos\left(\frac{n\pi}{6}\right) + C_2 \sin\left(\frac{n\pi}{6}\right) \right)$

現在我們需要使用邊界條件來求解常數 $C_1$ 和 $C_2$。
給定 $T_1 = 6$ 和 $T_2 = 20$。

對於 $n=1$:
$T_1 = (\sqrt{3})^1 \left( C_1 \cos\left(\frac{\pi}{6}\right) + C_2 \sin\left(\frac{\pi}{6}\right) \right) = 6$
$\sqrt{3} \left( C_1 \frac{\sqrt{3}}{2} + C_2 \frac{1}{2} \right) = 6$
$\frac{3}{2} C_1 + \frac{\sqrt{3}}{2} C_2 = 6$
兩邊乘以 2/3：
$C_1 + \frac{\sqrt{3}}{3} C_2 = 4$
$C_1 + \frac{1}{\sqrt{3}} C_2 = 4 \quad (*)$

對於 $n=2$:
$T_2 = (\sqrt{3})^2 \left( C_1 \cos\left(\frac{2\pi}{6}\right) + C_2 \sin\left(\frac{2\pi}{6}\right) \right) = 20$
$3 \left( C_1 \cos\left(\frac{\pi}{3}\right) + C_2 \sin\left(\frac{\pi}{3}\right) \right) = 20$
$3 \left( C_1 \frac{1}{2} + C_2 \frac{\sqrt{3}}{2} \right) = 20$
$\frac{3}{2} C_1 + \frac{3\sqrt{3}}{2} C_2 = 20$
兩邊乘以 2/3：

本題考查矩陣的對角化，包括求解特徵值、特徵向量，以及利用對角化計算矩陣的冪次。

(a) 計算對角化矩陣 $P$：
首先，我們需要找到矩陣 $A$ 的特徵值。特徵值 $\lambda$ 滿足 $\det(A - \lambda I) = 0$。
$\det \begin{pmatrix} 4-\lambda & -2 \\ 1 & 1-\lambda \end{pmatrix} = (4-\lambda)(1-\lambda) - (-2)(1) = 0$
$4 - 4\lambda - \lambda + \lambda^2 + 2 = 0$
$\lambda^2 - 5\lambda + 6 = 0$
因式分解得到：
$(\lambda - 2)(\lambda - 3) = 0$
所以，特徵值為 $\lambda_1 = 2$ 和 $\lambda_2 = 3$。

接下來，我們計算對應於每個特徵值的特徵向量。
對於特徵值 $\lambda_1 = 2$:
我們需要解 $(A - 2I)v = 0$。
$\begin{pmatrix} 4-2 & -2 \\ 1 & 1-2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 2 & -2 \\ 1 & -1 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$
從第一行得到 $2x - 2y = 0 \implies x = y$。
令 $y=1$，則特徵向量為 $v_1 = \begin{pmatrix} 1 \\ 1 \end{pmatrix}$。

對於特徵值 $\lambda_2 = 3$:
我們需要解 $(A - 3I)v = 0$。
$\begin{pmatrix} 4-3 & -2 \\ 1 & 1-3 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 1 & -2 \\ 1 & -2 \end{pmatrix} \begin{pmatrix} x \\ y \end{pmatrix} = \begin{pmatrix} 0 \\ 0 \end{pmatrix}$
從第一行得到 $x - 2y = 0 \implies x = 2y$。
令 $y=1$，則特徵向量為 $v_2 = \begin{pmatrix} 2 \\ 1 \end{pmatrix}$。

矩陣 $P$ 的列向量是 $A$ 的線性獨立的特徵向量。
$P = \begin{pmatrix} 1 & 2 \\ 1 & 1 \end{pmatrix}$

【答案】$P = \begin{pmatrix} 1 & 2 \\ 1 & 1 \end{pmatrix}$。

(b) 計算 $P^{-1}AP$:
由於 $P$ 的列向量是 $A$ 的特徵向量，根據對角化定理，$P^{-1}AP$ 是一個對角矩陣 $D$，其對角線上的元素是 $A$ 的特徵值，順序與 $P$ 的列向量對應。
$D = \begin{pmatrix} \lambda_1 & 0 \\ 0 & \lambda_2 \end{pmatrix} = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}$
所以，$P^{-1}AP = \begin{pmatrix} 2 & 0 \\ 0 & 3 \end{pmatrix}$。

我們也可以實際計算 $P^{-1}$ 並驗證。
對於 $P = \begin{pmatrix} 1 & 2 \\ 1 & 1 \end{pmatrix}$，其行列式為 $\det(P) = (1)(1) - (2)(1) = 1 - 2 = -1$。

核心觀念

本題考查整數的奇偶性：

• 奇數加奇數為偶數。
• 偶數加奇數為奇數。
• 若 $n$ 為偶數，則 $n^3$ 也是偶數；若 $n$ 為奇數，則 $n^3$ 也是奇數。
• $5$ 是奇數。

解題方法

以模 $2$ 判斷。因為 $5\equiv 1\pmod 2$，題設條件

$$n^3+5\text{ 為奇數}$$

等價於

$$n^3+1\equiv 1\pmod 2.$$

因此

$$n^3\equiv 0\pmod 2,$$

表示 $n^3$ 為偶數，進而 $n$ 必為偶數。

也可直接設 $n=2k$，其中 $k\in\mathbb Z$，則

$$n^3+5=(2k)^3+5=8k^3+5.$$

其中 $8k^3$ 是偶數，$5$ 是奇數，所以 $n^3+5$ 確實為奇數。

核心觀念

從 $1$ 到 $10$ 中選出 $4$ 個不同整數，每一組選取結果等可能。樣本總數為組合數

$$\binom{10}{4}=210.$$

若選出的數由小到大排列後，第二小的數是 $6$，則必須恰有一個數小於 $6$，並且選入 $6$。

解題方法

小於 $6$ 的數有 $1,2,3,4,5$，從中選 $1$ 個，共 $\binom{5}{1}$ 種。

第二小的數固定為 $6$。另外兩個數必須大於 $6$，可從 $7,8,9,10$ 中選 $2$ 個，共 $\binom{4}{2}$ 種。

核心觀念

7 顆球彼此不同，4 個箱子也彼此不同，因此每種放法都可視為一個把球指派到箱子的函數。題目要求每個箱子至少有一顆球，也就是計算「滿射」的個數。

解題方法

先不限制箱子是否為空，7 顆球各有 4 個箱子可選，共有 $4^7$ 種放法。再用排容原理扣除至少有一個空箱子的放法：

• 指定 1 個箱子為空：其餘 3 個箱子可放球，共有 $\binom{4}{1}3^7$ 種。
• 指定 2 個箱子為空：其餘 2 個箱子可放球，共有 $\binom{4}{2}2^7$ 種；這部分加回。

核心觀念

關係 $R$ 為傳遞關係，定義為：

$$aRb \land bRc \implies aRc。$$

三次關係合成 $R^3$ 定義為：

$$aR^3b \iff \exists x,y,\; aRx,\; xRy,\; yRb。$$

要證明 $R^3$ 傳遞，須證明：

$$aR^3b \land bR^3c \implies aR^3c。$$

解題方法與證明

假設 $aR^3b$ 且 $bR^3c$。則存在 $x,y,u,v$，使得

$$aRx,\quad xRy,\quad yRb$$

以及

$$bRu,\quad uRv,\quad vRc。$$

因為 $R$ 是傳遞關係，由 $xRy$ 與 $yRb$ 可得

$$xRb。$$