附錄 C 計算數學中的關鍵符號與公理體系#
計算數學的符號大多沿用自十九世紀的分析學與線性代數，但其中一些記號——尤其是範數 \(\|x\|\)、梯度 \(\nabla\) 與漸進記號 \(\mathcal{O}\)——有著各自的歷史。另一方面，計算數學在實數公理之外，另有一套「浮點數公理」：IEEE 754 標準（1985 年首版，主導者 William Kahan 獲 1989 年圖靈獎）定義的算術並不滿足實數的結合律與分配律，理解這套「公理」的邊界，是本書貫穿始終的主題。本附錄先列出關鍵符號表，再說明浮點數與數值分析的基礎假設。
C.1 關鍵符號表#
| 符號 | 讀法 / 名稱 | 意義 | 常見出現場合 |
|---|---|---|---|
| \(\|x\|_p\) | \(p\)-範數 | $(\sum_i | x_i |
| \(\|A\|_F\) | Frobenius 範數 | \(\sqrt{\sum_{ij} a_{ij}^2}\) | 矩陣逼近、PCA 誤差 |
| \(\|A\|_2\) | 譜範數 | \(A\) 的最大奇異值 \(\sigma_1\) | 矩陣擾動分析 |
| \(\kappa(A)\) | 條件數 | \(\kappa(A) = \|A\| \|A^{-1}\| = \sigma_1/\sigma_n\)（譜範數下） | 捨入誤差放大、CG 收斂率 |
| \(\mathcal{O}(f)\) | 大 O（Landau 記號） | $ | g |
| \(\Omega(f)\) | 大 Omega | $ | g |
| \(\Theta(f)\) | Theta | 同時為 \(\mathcal{O}\) 與 \(\Omega\) | 緊確複雜度 |
| \(o(f)\) | 小 o | \(g/f \to 0\) | 漸近比較 |
| \(\nabla f\) | 梯度（gradient） | \(\left(\frac{\partial f}{\partial x_1}, \dots, \frac{\partial f}{\partial x_n}\right)^\top\) | 最佳化、微分方程 |
| \(\nabla^2 f\) 或 \(H_f\) | Hessian | 二階偏導數矩陣 | 牛頓法 |
| \(J_F\) | Jacobian | \([J]_{ij} = \partial F_i / \partial x_j\) | 非線性系統、座標變換 |
| \(\mathbb{R}^n, \mathbb{C}^n\) | — | 實／複 \(n\) 維向量空間 | 各處 |
| \(A^\top, A^*, A^{-1}\) | — | 轉置、共軛轉置、反矩陣 | 線性代數 |
| \(A^\dagger\) | Moore–Penrose 偽反矩陣 | 滿足四個 Penrose 條件的廣義反矩陣 | 最小平方、SVD |
| \(\sigma_i(A), \lambda_i(A)\) | — | 奇異值、特徵值 | SVD、譜分析 |
| \(\langle x, y \rangle\) | 內積 | 滿足正定性、線性、對稱（或共軛對稱）的雙線性形式 | CG、正交性 |
| \(\approx, \simeq\) | — | 近似等於 | 數值結果 |
| \(\varepsilon\) | epsilon | 精度參數或機器 epsilon | 收斂準則 |
| \(\mathrm{fl}(x)\) | 浮點化 | \(x\) 經捨入後的浮點表示 | 誤差分析 |
C.2 浮點數的「公理」——IEEE 754#
IEEE 754 定義的浮點數不是實數：它是一個有限集合 \(\mathbb{F}\) 加上一組特定的捨入規則。以下性質可視為浮點算術的「公理」，並與實數公理對照：
| 性質 | 實數 | IEEE 754 浮點數 |
|---|---|---|
| 封閉性 | \(\mathbb{R}\) 對四則運算封閉（除以 0 除外） | 溢出得 \(\pm\infty\)，下溢得次正規數或 0；運算結果總是被捨入回 \(\mathbb{F} \cup \{\pm\infty, \text{NaN}\}\) |
| 加法結合律 \((a+b)+c = a+(b+c)\) | 成立 | 一般不成立（捨入順序影響結果） |
| 分配律 \(a(b+c) = ab+ac\) | 成立 | 一般不成立 |
| 加法交換律 | 成立 | 成立（捨入是對稱的） |
| 存在單位元素 0 與 1 | 成立 | 成立（但 \(-0 \ne 0\) 依比較、\(-0 = 0\) 依相等判斷，微妙） |
| 稠密性 | 任意兩實數間有第三實數 | 不成立；相鄰浮點數之間有間距 \(\mathrm{ulp}\) |
| 基本保證 | — | 每次加、減、乘、除、開根號的結果等於精確結果經捨入（正確捨入，correctly rounded）；IEEE 754 (2008) 亦將 FMA（fused multiply-add）納入標準 |
| 特殊值 | — | \(\pm\infty\)、\(\pm 0\)、NaN（Not a Number）；NaN 與任何值比較皆為 false |
推論：因為結合律不成立，平行求和的順序會改變結果；因為單次運算正確捨入，誤差分析才能以 \(\mathrm{fl}(a \oplus b) = (a \oplus b)(1+\delta)\)，\(|\delta| \le u\)（\(u\) 為單位捨入誤差）這一「標準模型」展開——這是本書誤差分析章節的基礎。
C.3 數值分析的基本定理假設#
數值分析的幾乎所有收斂定理，都建立在對函數光滑性或凸性的假設上。下表列出常用假設與其扮演的角色：
| 假設 | 定義 | 典型用途 |
|---|---|---|
| 連續性 | \(f(x_k) \to f(x)\) 當 \(x_k \to x\) | 中間值定理、根的存在性 |
| 可微性（\(C^1\)、\(C^2\)） | 一階／二階導數存在且連續 | 梯度法、牛頓法收斂 |
| Lipschitz 連續 | \(\|f(x)-f(y)\| \le L\|x-y\|\) | Picard 迭代、ODE 解的存在唯一性（Lipschitz–Picard 定理）、梯度法速率 |
| 強凸性 | \(\langle \nabla f(x)-\nabla f(y), x-y\rangle \ge \mu \|x-y\|^2\) | 梯度法線性收斂率中的 \(\mu\)、唯一最小值 |
| 對稱正定（SPD） | \(A = A^\top\) 且 \(x^\top A x > 0\)（\(x \ne 0\)） | Cholesky 分解、CG 的適用條件 |
| 對角佔優 | $ | a_{ii} |
| 壓縮映射 | \(T\) 為 Lipschitz 常數 \(< 1\) 的映射 | 不動點迭代、Banach 不動點定理 |
C.4 收斂速度的定義#
設迭代序列 \(\{x_k\} \to x^\ast\)，令誤差 \(e_k = \|x_k - x^\ast\|\)。
- 線性收斂（linear）：\(e_{k+1} \le C e_k\)，\(0 < C < 1\)。\(C\) 越小越快；CG 的收斂率 \(\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^k\) 屬於此類。
- 超線性收斂（superlinear）：\(\lim_{k\to\infty} e_{k+1}/e_k = 0\)；擬牛頓法（BFGS）通常屬此類。
- 二次收斂（quadratic）：\(e_{k+1} \le C e_k^2\)；牛頓法在良好初始點附近屬此類（誤差位數每步翻倍）。
- \(p\) 階收斂：\(e_{k+1} \le C e_k^p\)；\(p=1\) 需 \(C<1\)，\(p>1\) 時 \(C\) 只需有限即可。
注意「收斂速度」是迭代法誤差遞減的性質，與附錄 B 的「計算複雜度」互為表裡：達到精度 \(\varepsilon\) 的總成本等於每步成本乘以迭代數，而迭代數由收斂率決定。
C.5 符號的歷史#
Landau 記號#
大 O 記號由德國數學家 Edmund Landau 於 1894 年在解析數論論文中首次使用（以符號 \(\mathcal{O}\) 表示「Ordnung」，即階），並在其 1909 年的質數分佈著作中系統化；\(\Omega\) 與 \(\Theta\) 則是後人（Knuth 1976 年的文章推廣了這套記號）為了區分上界、下界與緊確界而補充的。這套記號從數論傳入演算法分析，成為今日計算機科學的通用語言。
範數記號 \(\|\cdot\|\)#
雙豎線記號的普及與泛函分析的發展同步：Banach（1932）與 Wiener（同時代）在建立賦範空間理論時都使用了某種範數記號，現代通用的 \(\|x\|\) 寫法經 Riesz 等人的教科書而標準化。\(p\)-範數家族則源自 Hölder 與 Minkowski 不等式的研究（十九世紀末至二十世紀初），Minkowski 於 1896 年的幾何數論工作中已使用 \(\ell_p\) 距離的幾何詮釋。
梯度記號 \(\nabla\)：Nabla 與蘇格蘭豎琴#
倒三角記號 \(\nabla\) 因形似古希臘—希伯來的豎琴 nabla 而得名。Hamilton 在四元數理論（1837 年前後）中使用了這個記號的錐形；其推廣主要歸功於 Oliver Heaviside 在 1880 年代發展向量分析時的用法，他將 \(\nabla\) 同時用於梯度、散度（\(\nabla \cdot\)）與旋度（\(\nabla \times\)）。Heaviside 的寫法起初受到 Maxwell 學派部分人士的質疑，但向量記法最終勝出；「nabla」這個暱稱據說出自 1890 年代愛丁堡的 Peter Guthrie Tait 等蘇格蘭數學家的玩笑——nabla 是古代西亞的豎琴名稱，而 Tait 正是蘇格蘭人。今日我們讀 \(\nabla f\) 為「nabla f」或「grad f」，正是這段歷史的痕跡。
條件數 \(\kappa\)#
條件數的概念在 Turing（1948 年關於矩陣過程的論文）與 von Neumann–Goldstine（1947 年誤差分析）中已現雛形，名稱「condition number」由 Turing 提出。希臘字母 \(\kappa\) 的使用則隨 Wilkinson 的著作（1960 年代）而標準化。它把「問題本身的病態」與「演算法的好壞」分開，是數值穩定性理論的基石。