115 年 國立成功大學人工智慧科技碩士學位學程《計算機數學（含線性代數、離散數學）》

核心觀念

本題考查離散數學中的標號圖計數（Labeled Graph Counting）、連通分支（Connected Components）與排容原理（Inclusion-Exclusion Principle）。

1. 無孤立點限制（No Isolated Vertices）：

   • 頂點集合 $V = \{1, 2, 3, 4, 5\}$，頂點數 $n = 5$。
   • 頂點 $v$ 若為孤立點，代表其度數 $\deg(v) = 0$。
   • 題目設定「沒有孤立點」（$\deg(v) \ge 1, \forall v \in V$），這意味著每一個連通分支（Connected Component）包含的頂點數量至少為 $2$。

2. 連通分支的大小分拆（Component Partition）：
   在頂點總數 $n = 5$ 且每個連通分支大小 $\ge 2$ 的限制下，分支大小的加總分拆只有兩種可能：

   • 1 個連通分支：分支大小為 $5$。
   • 2 個連通分支：分支大小為 $3 + 2 = 5$（若為 $4 + 1$ 則含有大小為 $1$ 的分支，即孤立點，不合題意）。
   • 3 個或更多連通分支：若有 $c \ge 3$ 個分支，總頂點數至少需要 $2c \ge 6 > 5$，故不可能存在。

3. 標號連通圖數量的遞迴公式：
   設 $G_n = 2^{\binom{n}{2}}$ 為 $n$ 個標號頂點的所有簡單圖總數，$C_n$ 為 $n$ 個標號頂點的連通圖總數。利用固定某一特定頂點所在連通分支大小的推導，可得以下標準遞迴關係式：
   $G_n = \sum_{k=1}^n \binom{n-1}{k-1} C_k G_{n-k} \implies C_n = G_n - \sum_{k=1}^{n-1} \binom{n-1}{k-1} C_k G_{n-k}$

---

解題方法

(a) 恰有 1 個連通分支（即連通圖）數量

由於當圖只有 1 個連通分支時，該分支涵蓋全部 5 個頂點（大小為 5），每個頂點的度數自動滿足 $\deg(v) \ge 1$，因此所有 5 個頂點的標號連通圖都天然符合「無孤立點」的條件。
本小題即為求 5 個標號頂點的連通圖數量 $C_5$。

依序計算 $n = 1, 2, 3, 4, 5$ 的 $G_n$ 與 $C_n$：

1. $n = 1$：
   $G_1 = 2^{\binom{1}{2}} = 1, \quad C_1 = 1$
2. $n = 2$：
   $G_2 = 2^{\binom{2}{2}} = 2, \quad C_2 = G_2 - \binom{1}{0} C_1 G_1 = 2 - (1 \times 1 \times 1) = 1$
3. $n = 3$：
   $G_3 = 2^{\binom{3}{2}} = 8$
   $C_3 = G_3 - \left[ \binom{2}{0} C_1 G_2 + \binom{2}{1} C_2 G_1 \right] = 8 - (1 \times 1 \times 2 + 2 \times 1 \times 1) = 8 - 4 = 4$
4. $n = 4$：
   $G_4 = 2^{\binom{4}{2}} = 64$
   $C_4 = G_4 - \left[ \binom{3}{0} C_1 G_3 + \binom{3}{1} C_2 G_2 + \binom{3}{2} C_3 G_1 \right] = 64 - (1 \times 1 \times 8 + 3 \times 1 \times 2 + 3 \times 4 \times 1) = 64 - 26 = 38$
5. $n = 5$：
   $G_5 = 2^{\binom{5}{2}} = 1024$

核心觀念

1. 平面圖（Planar Graph）與平面嵌入（Planar Embedding）：
   若一個圖形可以畫在平面上且邊與邊之間沒有交叉（non-intersecting edges），則稱該圖為平面圖。在 PCB（印刷電路板）單層佈線問題中，無交叉佈線等價於該網路圖 $H$ 為平面圖。
2. 頂點數與邊數關係（握手定理, Handshaking Lemma）：
   對於簡單圖 $G = (V, E)$，所有頂點的度數之和等於邊數的兩倍，即 $\sum_{v \in V} \deg(v) = 2e$。
3. 圖的圍長（Girth, $g$）：
   無向圖中最短圈（cycle）的長度稱為圍長 $g$。
4. 歐拉公式（Euler's Formula）與圍長邊數上界定理：
   對任何連通平面圖，頂點數 $v$、邊數 $e$、面數 $f$ 滿足歐拉公式：
   $v - e + f = 2$
   若圖的圍長為 $g$（其中 $g \ge 3$），由於每個面至少由 $g$ 條邊圍成，且每條邊至多被 2 個面共用，可得面數與邊數的限制關係 $2e \ge g \cdot f \implies f \le \frac{2e}{g}$。
   將 $f = 2 - v + e$ 代入前式，可推導出含圍長條件之平面圖邊數上界公式：
   $e \le \frac{g}{g - 2} (v - 2)$

---

解題方法

步驟一：計算網路圖 $H$ 的頂點數 $v$ 與邊數 $e$

• 頂點數 $v$：
  網路由 $4 \times 5$ 的圓柱網格組成，共有 4 層、每層 5 個路由器，因此頂點總數為：
  $v = 4 \times 5 = 20$
• 邊數 $e$：
  題目給定每個路由器度數皆為 4（即 4-正則圖, 4-regular graph）。依據握手定理：
  $2e = \sum_{v \in V} \deg(v) = 20 \times 4 = 80 \implies e = 40$

步驟二：確定圖 $H$ 的圍長（Girth, $g$）

• 水平方向之環圈長度為 5（$C_5$）。
• 垂直方向之環圈長度為 4（$C_4$）。
• 網格中相鄰兩層與相鄰兩欄對應的 4 個頂點可構成長度為 4 的矩形圈。
• 圖中不存在長度為 3 的圈（三角形），故最短圈長度（圍長）為：
  $g = 4$

步驟三：運用圍長邊數上界進行平面性推導

假設圖 $H$ 可嵌入於平面而不交叉（即 $H$ 為平面圖），則必須滿足圍長 $g = 4$ 之平面圖邊數上界公式：
$e \le \frac{g}{g - 2} (v - 2)$

將 $v = 20$ 與 $g = 4$ 代入公式右端計算最大許容邊數：
$e \le \frac{4}{4 - 2} (20 - 2) = 2 \times 18 = 36$

核心觀念

本題考查**離散數學（Discrete Mathematics）中的鴿籠原理（Pigeonhole Principle / Dirichlet's Box Principle）與同餘關係（Congruence Relation）**之綜合應用。

1. 中點為晶格點的充要條件：
   三維空間中兩整數點 $A_i = (x_i, y_i, z_i)$ 與 $A_j = (x_j, y_j, z_j)$ 的中點座標為 $\left(\frac{x_i + x_j}{2}, \frac{y_i + y_j}{2}, \frac{z_i + z_j}{2}\right)$。此中點為整數晶格點（Lattice Point）之充要條件為三個分量和皆為偶數：
   $x_i + x_j \equiv 0 \pmod{2}, \quad y_i + y_j \equiv 0 \pmod{2}, \quad z_i + z_j \equiv 0 \pmod{2}$
   等價於兩點的各對應座標分量具有相同的奇偶性（Parity）：
   $x_i \equiv x_j \pmod{2}, \quad y_i \equiv y_j \pmod{2}, \quad z_i \equiv z_j \pmod{2}$

2. 座標總和為偶數的充要條件：
   兩點座標總和為偶數：$(x_i + y_i + z_i) + (x_j + y_j + z_j) \equiv 0 \pmod{2}$，其充要條件為兩點各自的座標總和同為偶數或同為奇數，即：
   $(x_i + y_i + z_i) \equiv (x_j + y_j + z_j) \pmod{2}$

3. 鴿籠原理（Pigeonhole Principle）：
   若將 $k+1$ 個物件放入 $k$ 個盒子（同餘類別）中，則至少有一個盒子包含至少 2 個物件。

---

解題方法

(a) 子題 (a) 推導過程

• 步驟一：建立等價類（鴿籠）
  根據三維整數座標各分量的奇偶性（奇數以 $1$ 表示，偶數以 $0$ 表示），每一個整數點 $A_i = (x_i, y_i, z_i)$ 可以唯一映射至模 2（$\mathbb{Z}_2^3$）下的三元組奇偶模式 $(x_i \bmod 2, y_i \bmod 2, z_i \bmod 2)$。
  由於每個座標分量只有奇數（1）或偶數（0）兩種可能，故三維空間中共有 $2 \times 2 \times 2 = 2^3 = 8$ 種不同的奇偶型態（鴿籠）：
  $\mathcal{S} = \{ (0,0,0), (0,0,1), (0,1,0), (0,1,1), (1,0,0), (1,0,1), (1,1,0), (1,1,1) \}$

• 步驟二：證明充分性（$N = 9$ 必定存在安全鏈結）
  當衛星數量 $N = 9$ 時，由於鴿籠數量為 8，根據鴿籠原理，至少有 2 顆衛星 $A_i$ 與 $A_j$ 會落入同一個奇偶型態的鴿籠中。
  當 $A_i$ 與 $A_j$ 具有相同的奇偶型態時：
  $x_i \equiv x_j \pmod{2} \implies x_i + x_j \equiv 0 \pmod{2} \implies \frac{x_i + x_j}{2} \in \mathbb{Z}$
  $y_i \equiv y_j \pmod{2} \implies y_i + y_j \equiv 0 \pmod{2} \implies \frac{y_i + y_j}{2} \in \mathbb{Z}$
  $z_i \equiv z_j \pmod{2} \implies z_i + z_j \equiv 0 \pmod{2} \implies \frac{z_i + z_j}{2} \in \mathbb{Z}$
  因此，$A_i A_j$ 的中點必定為整數晶格點，即安全鏈結必然存在。

• 步驟三：證明必要性（$N = 8$ 可能無法建立安全鏈結）
  若衛星數量為 8 顆，我們可以從 8 種奇偶型態中各挑選 1 顆衛星放置。例如：
  $A_1 = (0,0,0), \, A_2 = (0,0,1), \, A_3 = (0,1,0), \, A_4 = (0,1,1)$
  $A_5 = (1,0,0), \, A_6 = (1,0,1), \, A_7 = (1,1,0), \, A_8 = (1,1,1)$

核心觀念

本題考查**二階常係數非齊次線性遞迴關係式（Non-homogeneous Linear Recurrence Relation）**的求解與指數級數估算。主要使用的數學觀念與公式包含：

1. 齊次解（Homogeneous Solution）：利用特徵方程式（Characteristic Equation）求得二重根（Repeated Root）狀況下的齊次解形式。
2. 特解（Particular Solution）：利用**待定係數法（Method of Undetermined Coefficients）**針對指數項與一次多項式項設出對應特解形式。當非齊次項的底數與特徵根重複（二重根，重數 $m=2$）時，特解須額外乘以 $n^2$。
3. 通解與初始條件：通解為齊次解與特解之和（$E_n = E_n^{(h)} + E_n^{(p)}$），利用初始條件求出待定常數。
4. 數量級估算：利用指數函數 $2^n$ 的成長速度進行精確邊界判定。

---

解題方法

步驟一：求解齊次解 $E_n^{(h)}$

考慮對應的齊次遞迴關係式：
$E_n - 4E_{n-1} + 4E_{n-2} = 0$

其特徵方程式為：
$r^2 - 4r + 4 = 0 \implies (r-2)^2 = 0$
解得特徵根為 $r = 2$（二重根）。

故齊次解的形式為：
$E_n^{(h)} = (c_1 + c_2 n) 2^n$

步驟二：求解特解 $E_n^{(p)}$

非齊次項分為兩部分：$f_1(n) = 2^n$ 與 $f_2(n) = 3n$。

1. 針對 $f_1(n) = 2^n$ 的特解 $E_n^{(p1)}$：
   因為底數 $2$ 為二重特徵根，特解形式需設定為：
   $E_n^{(p1)} = A n^2 2^n$
   代回原遞迴關係式中非齊次項 $2^n$ 的部分：
   $A n^2 2^n - 4 A (n-1)^2 2^{n-1} + 4 A (n-2)^2 2^{n-2} = 2^n$
   兩邊同除以 $2^{n-2}$：
   $4 A n^2 - 8 A (n-1)^2 + 4 A (n-2)^2 = 4$
   展開並整理：
   $4 A \left[ n^2 - 2(n^2 - 2n + 1) + (n^2 - 4n + 4) \right] = 4$
   $4 A \cdot 2 = 4 \implies 8A = 4 \implies A = \frac{1}{2}$
   得 $E_n^{(p1)} = \frac{1}{2} n^2 2^n$。

2. 針對 $f_2(n) = 3n$ 的特解 $E_n^{(p2)}$：
   此項為一次多項式，底數 $1$ 非特徵根，設特解為：
   $E_n^{(p2)} = B n + C$
   代回原遞迴關係式中非齊次項 $3n$ 的部分：
   $(B n + C) - 4\left[B(n-1) + C\right] + 4\left[B(n-2) + C\right] = 3n$
   展開整理得：
   $B n + (C - 4B) = 3n$
   對比係數可得：
   $B = 3$
   $C - 4B = 0 \implies C = 12$
   得 $E_n^{(p2)} = 3n + 12$。

綜合以上，總特解為：
$E_n^{(p)} = \frac{1}{2} n^2 2^n + 3n + 12$

步驟三：求通解並帶入初始條件

將齊次解與特解相加得到通解：
$E_n = (c_1 + c_2 n) 2^n + \frac{1}{2} n^2 2^n + 3n + 12$

帶入初始條件 $E_0 = 2, E_1 = 10$：

• 當 $n = 0$：
  $E_0 = c_1 + 12 = 2 \implies c_1 = -10$
• 當 $n = 1$：

(a) 標準「 Header-Trailer 」協定規範 (Standard "Header-Trailer" Protocol Specification)

觀念說明

採用 Moore Machine 模型的狀態設計：

• $S_0$：初始狀態 (Start State)。
• $S_1$：接收到第 1 個訊號 1。
• $S_2$：成功驗證 Header 11，進入監控/等待狀態 (Monitoring)。
• $S_3$：接收到 0（準備解鎖的中介狀態）。
• $S_4$：成功接收到 Trailer 00，進入解鎖狀態 (Unlock)（雙圓圈）。
• $S_L$：永久鎖定狀態 (Permanent Lockout)。

狀態轉移邏輯與表單

1. Header 檢查 ($S_0 \to S_1 \to S_2$)：
   • $S_0$: 輸入 1 轉至 $S_1$；輸入 0 轉至 $S_L$。
   • $S_1$: 輸入 1 轉至 $S_2$；輸入 0 轉至 $S_L$。
2. 監控與解鎖 ($S_2 \to S_3 \to S_4$)：
   • $S_2$: 輸入 0 轉至 $S_3$；輸入 1 保持在 $S_2$。
   • $S_3$: 輸入 0 轉至 $S_4$ (Unlock)；輸入 1 回到 $S_2$。
   • $S_4$ (Unlock): 輸入 0 保持在 $S_4$ (繼續保持 00 結尾)；輸入 1 破壞 00 結尾，退回 $S_2$ 重新監控 (Relocking)。
3. 永久鎖定 ($S_L$)：
   • $S_L$: 忽略所有後續輸入，輸入 0 或 1 皆保持在 $S_L$。

$$\begin{array}{c|c|c|c} \text{目前狀態 } S_i & \text{輸入 } 0 & \text{輸入 } 1 & \text{輸出 (Output)} \\ \hline \to S_0 & S_L & S_1 & \text{Lock} \\ S_1 & S_L & S_2 & \text{Lock} \\ S_2 & S_3 & S_2 & \text{Lock} \\ S_3 & S_4 & S_2 & \text{Lock} \\ ((S_4)) & S_4 & S_2 & \text{Unlock} \\ S_L & S_L & S_L & \text{Lock} \\ \end{array}$$

狀態轉移圖 (State Transition Diagram)

stateDiagram-v2
    direction LR
    [*] --> S0
    S0 --> S1: 1
    S0 --> SL: 0
    S1 --> S2: 1
    S1 --> SL: 0
    S2 --> S2: 1
    S2 --> S3: 0
    S3 --> S2: 1
    S3 --> S4: 0
    S4 --> S4: 0
    S4 --> S2: 1
    SL --> SL: 0, 1

    classDef unlock fill:#e6ffe6,stroke:#00aa00,stroke-width:3px;
    class S4 unlock;

---

(b) 進階「 Strict Rhythm 」協定規範 (Advanced "Strict Rhythm" Protocol Specification)

觀念說明

依據題目三項修改要求：

1. 交替節奏：Header 11 之後，資料必須嚴格遵守 0, 1, 0, 1... 之交替順序。
2. 違規即鎖：若破壞交替節奏（例如出現連續 11），直接轉至永久鎖定狀態 $S_L$。
3. 單次存取 (One-Time Access)：一旦輸入 00 進入解鎖狀態 $S_4$，後續任何輸入（0 或 1）皆視為違規，直接進入 $S_L$。

狀態意義調整：

• $S_0, S_1, S_2$：Header 11 驗證與 (a) 相同。
• $S_3$：交替資料中，最後一個輸入為 0 的狀態。
• $S_4$：成功接收 00 結尾，進入解鎖狀態 (Unlock)（雙圓圈）。
• $S_5$：交替資料中，最後一個輸入為 1 的狀態。

核心觀念

1. LU 分解（LU Decomposition）與 Doolittle 演算法：
   將 $n \times n$ 可逆矩陣 $A$ 分解為下三角矩陣 $L$（對角線元素皆為 $1$ 的單位下三角矩陣）與上三角矩陣 $U$ 的乘積 $A = LU$。利用 LU 分解，可將求解 $A \mathbf{x} = \mathbf{b}$ 拆解為前向替換（Forward Substitution）$L \mathbf{y} = \mathbf{b}$ 與後向替換（Backward Substitution）$U \mathbf{x} = \mathbf{y}$ 兩個階段，使大型線性方程組的求解效率大幅提升。

2. 古典 LU 分解複雜度（Scalar-oriented LU）：
   傳統逐個元素求解的 LU 分解（如 Doolittle 演算法）包含三重迴圈，其時間複雜度由浮點運算次數（FLOPs: Floating Point Operations，包含乘法與加減法）決定。

3. 分塊 LU 分解（Block LU Decomposition）與分治法（Divide-and-Conquer）：
   將矩陣分割為 $2 \times 2$ 個大小為 $\frac{n}{2} \times \frac{n}{2}$ 的子矩陣，利用分治遞迴求解。其關鍵運算包括：

   • 遞迴分解子矩陣
   • 解下／上三角矩陣方程組
   • 計算 Schur 補集（Schur Complement）$S = A_{22} - L_{21} U_{12}$

4. 快取區域性與硬體加速（Cache Locality & BLAS-3）：
   分塊 LU 分解能將純量運算轉化為塊矩陣乘法（BLAS Level 3 運算），大幅提高 Cache 重用率與記憶體頻寬利用率；若搭配快速矩陣乘法（如 Strassen 演算法），亦可降低理論時間複雜度。

---

解題方法

(a) 古典 LU 分解演算法（Algorithm 1）的時間複雜度推導

分析 Algorithm 1 的迴圈運算量：
外層迴圈 $k$ 從 $1$ 執行至 $n$：

1. 第 3–5 行（計算 $U$ 的第 $k$ 列）：
   $j$ 從 $k$ 執行至 $n$，共 $(n - k + 1)$ 次疊代。
   每次內層求和 $\sum_{l=1}^{k-1} L_{kl} U_{lj}$ 包含 $(k-1)$ 次乘法與 $(k-1)$ 次減法，共 $2(k-1)$ 次浮點運算。
2. 第 6–8 行（計算 $L$ 的第 $k$ 行）：
   $i$ 從 $k+1$ 執行至 $n$，共 $(n - k)$ 次疊代。
   每次包含 $(k-1)$ 次乘法、$(k-1)$ 次減法及 $1$ 次除法，共 $2(k-1) + 1$ 次浮點運算。

總運算量求和：
$W(n) = \sum_{k=1}^{n} \left[ (n - k + 1) \cdot 2(k - 1) + (n - k) \cdot (2(k - 1) + 1) \right]$

展開最高次項（$n^3$ 項）：

$$\begin{aligned} W(n) &\approx \sum_{k=1}^{n} 4(n - k)(k - 1) \\ &= 4 \int_{0}^{n} (nk - k^2) \, dk = 4 \left( \frac{n^3}{2} - \frac{n^3}{3} \right) = \frac{2}{3} n^3 \text{ FLOPs} \end{aligned}$$

其中包含 $\frac{1}{3} n^3$ 次乘法與 $\frac{1}{3} n^3$ 次加減法。
因此，古典 LU 分解的時間複雜度為 $\Theta(n^3)$（或 $O(n^3)$）。

---

(b) 改進型分塊 LU 分解演算法（Algorithm 2）的時間複雜度推導

設大小為 $n \times n$ 矩陣的分塊 LU 分解時間複雜度為 $T(n)$。分析 Algorithm 2 各步驟之複雜度：

1. 第 7 行：呼叫 SPEEDIMPROVEDBLOCKLU(A11)，子矩陣大小為 $\frac{n}{2} \times \frac{n}{2}$，耗時 $T(n/2)$。
2. 第 8 行：解 $L_{11} U_{12} = A_{12}$（三角方程組求解），大小為 $\frac{n}{2} \times \frac{n}{2}$，耗時 $\Theta((n/2)^3)$。
3. 第 9 行：解 $L_{21} U_{11} = A_{21}$（三角方程組求解），大小為 $\frac{n}{2} \times \frac{n}{2}$，耗時 $\Theta((n/2)^3)$。
4. 第 10 行：計算 Schur 補集 $S = A_{22} - L_{21} U_{12}$，包含一次 $\frac{n}{2} \times \frac{n}{2}$ 的矩陣乘法與一次矩陣減法。
5. 第 11 行：呼叫 SPEEDIMPROVEDBLOCKLU(S)，子矩陣大小為 $\frac{n}{2} \times \frac{n}{2}$，耗時 $T(n/2)$。

複雜度分析與遞迴關係式：

• 情況一：採用標準矩陣乘法
  矩陣乘法與三角求解的時間複雜度均為 $\Theta(n^3)$。遞迴關係式為：
  $T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(n^3)$
  根據主定理（Master Theorem），其中 $a = 2, b = 2$，$\log_b a = \log_2 2 = 1$。
  因為 $f(n) = \Theta(n^3) = \Omega(n^{\log_2 2 + \epsilon})$（取 $\epsilon = 2 > 0$），故時間複雜度為：
  $T(n) = \Theta(n^3)$
  (註：此方法稱為 Speed-Improved 是因為將純量運算改為塊矩陣運算後，大幅減少記憶體存取瓶頸與 Cache Miss，實際執行速度比古典 LU 分解快數倍。)

• 情況二：結合快速矩陣乘法（如 Strassen 演算法）
  若矩陣乘法與三角求解採用複雜度為 $\Theta(n^\omega)$ 的快速演算法（其中 $\omega = \log_2 7 \approx 2.807$），則遞迴關係式為：
  $T(n) = 2 T\left(\frac{n}{2}\right) + \Theta(n^\omega)$
  由主定理可得整體理論時間複雜度降低為：
  $T(n) = \Theta(n^\omega) = \Theta(n^{\log_2 7}) \approx \Theta(n^{2.807})$

---

(c) 實例計算：求解 $A = \begin{bmatrix} 4 & 3 \\ 6 & 3 \end{bmatrix}$ 之 LU 分解

按照 Algorithm 2 步驟詳細推導：

1. 矩陣分塊（第 6 行）：
   $n = 2$。將 $A$ 拆分為四個 $1 \times 1$ 的塊：
   $A_{11} = [4], \quad A_{12} = [3], \quad A_{21} = [6], \quad A_{22} = [3]$

核心觀念

1. 正定矩陣（Positive Definite Matrix）定義與性質：
   對於實對稱矩陣 $M \in \mathbb{R}^{n \times n}$，若對所有非零向量 $x \in \mathbb{R}^n$（$x \neq 0$），二次形式均滿足 $x^T M x > 0$，則稱 $M$ 為正定矩陣。正定矩陣的所有特徵值皆為嚴格正數，且必為可逆矩陣（Non-singular）。
2. 正半定矩陣（Positive Semi-Definite Matrix）：
   對任意矩陣 $A \in \mathbb{R}^{m \times n}$，$A^T A$ 必為實對稱矩陣，且對任意向量 $x \in \mathbb{R}^n$，滿足 $x^T A^T A x = (Ax)^T (Ax) = \|Ax\|^2 \ge 0$，故 $A^T A$ 為正半定矩陣。
3. 脊回歸（Ridge Regression / Tikhonov Regularization）：
   當矩陣 $A$ 秩虧（Rank-deficient，即 $\text{rank}(A) < n$）時，$A^T A$ 為奇異矩陣不可逆，傳統最小平方法（Least Squares）無唯一解。加入 $L_2$ 正則化項 $\lambda \|x\|^2$（$\lambda > 0$）後，能保證海森矩陣嚴格正定，從而導出唯一的閉形式解（Closed-form Solution）。
4. 向量微分與嚴格凸函數極值條件：
   多元二次目標函數的梯度（Gradient）為零向量且海森矩陣（Hessian Matrix）正定時，對應的臨界點（Critical Point）必為全域唯一最小值。

---

解題方法

• (a) 小題切入點：
  依據正定矩陣的兩大要素進行證明：

  1. 證明 $A^T A + \lambda I$ 為實對稱矩陣。
  2. 對任意非零向量 $x \neq 0$，展開二次形式 $x^T (A^T A + \lambda I) x$，利用範數非負性 $\|Ax\|^2 \ge 0$ 以及 $\lambda \|x\|^2 > 0$，證明其結果必大於零。

• (b) 小題切入點：
  將範數展開為向量內積形式 $J(x) = (Ax - b)^T (Ax - b) + \lambda x^T x$。對向量 $x$ 計算梯度並令其為零向量 $\nabla_x J(x) = 0$。結合 (a) 小題所得 $A^T A + \lambda I$ 為正定矩陣（故逆矩陣存在且目標函數為嚴格凸函數），即可解出唯一的閉形式解 $x^*$。

---

選項分析

（本題為計算推導題，以下針對 (a)、(b) 兩小題進行詳細的數學推導與分析）

(a) 證明矩陣 $A^T A + \lambda I$ 為正定矩陣

1. 驗證對稱性：
   $(A^T A + \lambda I)^T = (A^T A)^T + (\lambda I)^T = A^T (A^T)^T + \lambda I = A^T A + \lambda I$
   證明 $A^T A + \lambda I$ 為實對稱矩陣。

2. 驗證二次形式（Quadratic Form）正定性：
   任取一非零向量 $x \in \mathbb{R}^n$（即 $x \neq 0$）：
   $x^T (A^T A + \lambda I) x = x^T A^T A x + \lambda x^T I x = (Ax)^T (Ax) + \lambda x^T x = \|Ax\|^2 + \lambda \|x\|^2$

   • 根據向量範數性質，對任意向量 $Ax$ 均有 $\|Ax\|^2 \ge 0$。
   • 因為 $x \neq 0$，其歐式範數平方 $\|x\|^2 > 0$；又題目給定 $\lambda > 0$，故 $\lambda \|x\|^2 > 0$。
     將兩項相加可得：
     $x^T (A^T A + \lambda I) x = \|Ax\|^2 + \lambda \|x\|^2 > 0$

3. 結論：
   由實對稱性與對所有 $x \neq 0$ 皆滿足二次形式大於零之定義，矩陣 $A^T A + \lambda I$ 必為正定矩陣。（證畢）

---

(b) 推導 $x^* = \arg \min_{x \in \mathbb{R}^n} \|Ax - b\|^2 + \lambda \|x\|^2$ 的閉形式解