Category Archives: 數值線性代數

從滿正交法 (FOM) 推導共軛梯度法 (CG)

本文的閱讀等級:高級 考慮線性方程 ,其中 是 階可逆實矩陣, 是非零向量。在線性方程的迭代解法中,滿正交法 (full orthogonalization method,簡稱 FOM) 適用於一般非對稱矩陣,共軛梯度法 (conjugate gradient method,簡稱 CG) 則限定於實對稱正定矩陣。令 為初始猜測解, 為對應近似解 的殘差 (residual),以及 Krylov 子空間 。FOM 與 CG 同屬 Krylov 子空間法,而且有同樣的定義條件: 本文從 FOM 推導 CG,證明 CG 是 FOM 的一種簡約表達。關於 FOM 與 CG 的介紹,請參閱“Krylov … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , | Leave a comment

Krylov 子空間法──線性方程的數值解法 (三):共軛梯度法

本文的閱讀等級:高級 共軛梯度法 (conjugate gradient method) 是一個適用於實對稱正定矩陣的線性方程數值解法。顧名思義,共軛梯度法的核心是共軛 (conjugacy) 和梯度 (一階導數)。共軛能夠加快收斂,梯度則提供正交基底。因為這兩個特性,共軛梯度法的結構簡單優美,儲存量及運算量少,並且無須設定參數。對於大尺寸矩陣,我們往往無法使用直接法求解,譬如 Cholesky 分解 (見“Cholesky 分解”),這時候可以採用以迭代方式計算的共軛梯度法。此外,對於大型非線性最佳化問題,共軛梯度法也是最有效的數值算法之一。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 1 Comment

Krylov 子空間法──線性方程的數值解法 (二):GMRES 與 FOM

本文的閱讀等級:高級 令 為一 階實矩陣。對於非零向量 , 稱為 Krylov 子空間。設 是次數最小的多項式使得 ,稱為 相對 的最小多項式。Krylov 子空間應用於線性方程的數值解法建立於下列基礎 (見“Krylov 子空間法──線性方程的數值解法 (一):Arnoldi 與 Lanczos 算法”): 令 。若 ,則 Krylov 序列 為一線性獨立集,就有 。若 ,則 。 當 ,Arnoldi 算法可求得 Krylov 子空間 的一組單範正交基底 (orthonormal basis) 。 Arnoldi 算法給出 Arnoldi … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 8 Comments

Krylov 子空間法──線性方程的數值解法 (一):Arnoldi 與 Lanczos 算法

本文的閱讀等級:高級 令 為一 階複矩陣, 為一非零向量。向量序列 稱為 Krylov 序列,此序列所生成的子空間稱為 Krylov 子空間 (見“Krylov 子空間法”),記為 。 因為 是有限維空間 的一個子空間,當 不斷增大時,Krylov 序列 最終會是一個線性相關集。設 為最小的正整數使得 ,也就是說 為一個線性獨立集且 。因此,存在唯一數組 滿足 。 定義 次多項式 。 因為 ,我們稱 為 相對於 的最小 (消滅) 多項式 (minimal polynomial)。以下考慮 為可逆矩陣。我們可以斷定 ,否則有 ,即存在次數小於 … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , , , , , | 3 Comments

Jacobi 特徵值算法

本文的閱讀等級:中級 給定一 階實矩陣 ,使用 Householder 變換可求得一正交矩陣 (orthogonal matrix) ,,使得 為三對角 (tridiagonal) 矩陣,其中 , (見“特殊矩陣 (19):Hessenberg 矩陣”)。此外,如果 是實對稱矩陣,利用旋轉矩陣可求出一正交矩陣 使得 為對角矩陣。因為 正交相似於 , 的主對角元即為 的特徵值。德國數學家雅可比 (Carl Gustav Jacob Jacobi) 於1846年公開這個對角化實對稱矩陣的計算方法,後人稱之為 Jacobi 特徵值算法。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 2 Comments

Cesàro 矩陣序列

本文的閱讀等級:高級 給定一數列 ,Cesàro 數列定義為 ,其中 是 的前 項的平均數,如下: 。 Cesàro 數列因義大利數學家切薩羅 (Ernesto Cesàro) 而得名。若 ,我們說數列 是可累加的 (summable), 稱為 Cesàro 極限。若數列 收斂至 ,則對應的 Cesàro 數列 也收斂至 (證明見附註[1])。收斂性蘊含可累加性,但可累加性未必有收斂性。例如,震盪數列 不收斂,但對應的 Cesàro 數列收斂至 。Cesàro 數列可以推廣至矩陣序列。令 為一 階矩陣。若 存在,則稱 為可累加矩陣。(如果不取平均, 稱為 Neumann 無窮級數[2]。) 若 ,我們稱 … Continue reading

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , , , | Leave a comment

高斯消去法與高斯─約當法的運算量

本文的閱讀等級:初級 高斯消去法 (Gaussian elimination) 是當今普遍用於解線性聯立方程組的演算法。高斯─約當法 (Gauss-Jordan method) 是高斯消去法的一種變形,主要應用於計算逆矩陣。關於這兩個算法的詳細介紹,請見“高斯消去法”和“高斯─約當法”,本文僅討論它們耗費的運算量。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , | 2 Comments

別再算逆矩陣了

本文的閱讀等級:初級 不知道從甚麼時候開始,“三階逆矩陣公式”經常雄踞本站「近期最多人點閱」表單的榜首,每日點閱該文的次數少則幾十,多則上百,下圖是過去一年以來的瀏覽次數統計 (主要的峰值所在的日期大致與台灣高等院校春秋二季期中和期末考試相吻合)。對於所見的逆矩陣風潮,我感到相當困惑:究竟出於甚麼樣的動機眾多年輕讀者願意不辭勞苦求算 (三階) 逆矩陣?如果尋覓逆矩陣公式的行動單純源於人類天生想要探索未知世界的好奇心,那我沒甚麼意見。不過,倘若只因為要解線性方程而計算逆矩陣,我可就忍不住要奉勸諸位:「省點力氣,別再算逆矩陣了!」

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , | 9 Comments

Kaczmarz 算法

本文的閱讀等級:中級 Kaczmarz 算法是線性方程 的一種迭代解法,1937年由波蘭數學家科區馬茲 (Stefan Kaczmarz) 所提出[1]。1970年,戈登 ( Richard Gordon)、本德爾 (Robert Bender) 和赫爾曼 (Gabor Herman) 三人重新發現此法,稱之為代數重建技術 (algebraic reconstruction technique),主要應用於電腦斷層掃描的影像重建[2]。我們以包含兩個未知數和兩個方程式的線性方程組 說明 Kaczmarz 算法的基本原理。考慮 , 其中係數 和常數 是實數。當係數矩陣可逆時,線性方程的解為下列兩個超平面 (此例為 平面的二直線) 的交點: 見下圖,給定任一初始點 ,連續交互正交投影至超平面 和 可得一向量序列 ,。當 ,,此即 的解。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , | 3 Comments

矩陣的數值秩

本文的閱讀等級:高級 1879年,德國數學家弗羅貝尼烏斯 (Ferdinand Georg Frobenius) 提出秩 (rank) 作為矩陣所攜帶訊息量的一種測度。一矩陣 的秩,記作 ,定義為最大可逆子陣的階數,即最大非零餘子式 (minor) 的行列式階數,因此也稱為行列式秩。近代線性代數已捨棄行列式定義,改用較富幾何意義的向量空間定義:秩是矩陣的行空間 (column space) 維數,同樣也是列空間 (row space) 維數,換句話說,秩是最大的線性獨立行 (列) 向量數 (見“你不能不知道的矩陣秩”)。一般基礎線性代數教科書多以高斯消去法揭示矩陣秩 (見“利用行列式計算矩陣秩”),但實際數值計算卻不採用高斯消去法,原因在於 並非 的連續函數。舉例來說,。若 ,則 。若 ,則 。這個例子顯示極微小的擾動量便足以造成矩陣秩的跳躍。由於計算機的浮點運算難免引入誤差,我們必須審慎處理矩陣秩的數值計算問題。本文介紹奇異值分解在矩陣秩的擾動分析以及數值計算的應用,原因無他,奇異值分解是現今最可靠的數值秩算法 (另一個有效的算法是計算成本較低的 QR 分解[1])。

Posted in 線性代數專欄, 數值線性代數 | Tagged , , , , , | Leave a comment