本文的閱讀等級:中級
高斯消去法是當今最常被使用的線性方程解法 (見“高斯消去法”),它是一種直接法,即一次性地解決問題。對於一個 階方陣,高斯消去法耗用的運算量是 。如果我們面對的是一個大型的稀疏矩陣,這時可用迭代法來求解。所謂迭代法是指從一個初始估計值出發,尋找一系列近似解以期解決問題的方法。大致上,應用於解線性方程的迭代法可區分為兩類:定常迭代法 (stationary iterative method) 和 Krylov 法。定常迭代法相對古老,容易瞭解與實現,惟效果通常不佳。Krylov 法相對年輕,雖然較不易理解分析,但效果普遍優異。本文介紹定常迭代法,並討論其中三種主要方法。
考慮線性方程 ,其中 是一個 階係數矩陣, 是 維常數向量。分解 ,其中 可逆。令 且 。對於一個 維初始向量 ,定常迭代法的算式如下:
我們稱 為迭代矩陣,迭代程序的收斂性完全由 的特徵值決定。令 為 的所有相異特徵值所形成的集合,稱為矩陣譜 (spectrum),並令 為 的最大絕對特徵值,即 ,稱為譜半徑。定常迭代法的收斂條件如下:若 為一個收斂矩陣,即 ,則 存在,且對於任何一個初始向量 ,
。
證明引用下列收斂矩陣性質:若 ,則 且 存在 (見“譜半徑與矩陣範數”,定理一)。寫出 ,立知 是可逆的。逐次迭代可得
使用收斂矩陣性質,
。
既然定常迭代法的收斂性由 決定,我們也預期 的大小影響收斂率。為方便說明,假設 ,其中 。在多數應用中, 是一個可對角化矩陣,其譜分解可表示為
,
其中 是對應特徵值 的投影矩陣,稱為譜投影算子 (spectral projector),具有以下性質:(1) ,;(2) 若 ,;(3) (見“可對角化矩陣的譜分解”)。令 表示第 次迭代後的估計誤差。因為 是差分方程 的一個不動點 (fixed point),即 ,將兩式相減可得
。
當 增大時,,即有
。
譜半徑 的數值越小,收斂的速度越快。設 ,,且 。將設定數值代入前式,
,
故每次迭代的精確度改善量是 。因為這個緣故,我們定義漸近收斂率 (asymptotic rate of convergence) 為 。綜合以上結果,定常迭代法的設計要領是在容易算得 和 的前提下,找出迭代矩陣 使其 越小越好。
Jacobi 法
考慮線性方程 的第 個式子
。
若 ,固定 ,,可解得 ,如下:
。
上式提示一個迭代公式,稱為 Jacobi 法:
。
Jacobi 法獨立看待每一個方程式,我們得以同時更新估計值,因此也稱為同時取代法 (method of simultaneous displacements)。如以矩陣表示,分解 ,其中 是 的主對角部分, 是 的非主對角部分。假設每一 ,即 可逆,以矩陣表達的 Jacobi 法如下:
。
明顯地, 和 僅耗費少量的計算。
若 是一個對角佔優矩陣 (見“特殊矩陣 (12):對角佔優矩陣”),則對於任意 和 ,Jacobi 法必定收斂。因為對角佔優矩陣 滿足 ,,且不論何種矩陣範數都有 (見“譜半徑與矩陣範數”),故可推論
。
上面使用了 ,,。
Gauss-Seidel 法
在 Jacobi 法中,如果我們按照順序計算 ,並使用最新產生的 ,,即得 Gauss-Seidel 法:
。
Gauss-Seidel 法按照既定的順序調整,因此也稱為逐次取代法 (method of successive displacements)。若以矩陣表示,分解 ,其中 是 的主對角部分, 和 分別是 的嚴格下三角部分 (上三角扣除主對角) 和嚴格上三角部分。直接乘開可驗證 Gauss-Seidel 法的矩陣表達式:
,
即 且 。
類似 Jacobi 法,若 是一個對角佔優矩陣,Gauss-Seidel 法總能收斂。考慮特徵方程 ,即 ,或寫為 。假設 。將前一式乘開,第 個式子可表示為 ,其中
。
對角佔優矩陣 滿足 ,可得
故 。使用反向三角不等式 ,
,
證明 ,確定收斂性成立[1]。
SOR 法
考慮 Gauss-Seidel 法,將迭代公式改寫為 ,其中 可視為修正項:
。
如果我們調整或「鬆弛」修正項,以 取代 ,其中 稱為鬆弛參數 (relaxation parameter),迭代公式變成
,
稱為 SOR (successive overrelaxation) 法。以矩陣表達,分解 ,其中 且 。如前, 是 的主對角部分, 和 分別是 的嚴格下三角部分和嚴格上三角部分。因為
,
迭代矩陣為
SOR 法的矩陣表達式如下:
。
SOR 法引進鬆弛參數 ,因此較 Gauss-Seidel 法更具彈性。當 ,SOR 法即為 Gauss-Seidel 法。若 ,稱為過鬆弛 (overrelaxation);若 ,則稱為欠鬆弛 (underrelaxation)。顯然,鬆弛參數 影響 SOR 法的收斂性。下面我們證明:若 ,則 。使用行列式性質,
另一方面,,其中 是 的特徵值。比較上面兩式,可得 ,故知必存在至少一 使得 。所以,,這意味 。反過來說,若 為一個 Hermitian 正定矩陣,則 可推得 [2]。
一般而言,除了少數特例,找尋使 最小化的鬆弛參數 是一個相當困難的工作。為了近似最佳的 ,我們必須另外引進適應性 (adaptive) 計算程序,即便如此,SOR 法的表現也常令人失望。1950年誕生的 SOR 法雖然比其他定常迭代法往前邁出了一大步,但終究還是逐漸被二十世紀後半期發展起來的 Krylov 法所取代。
註解:
[1] 對角佔優矩陣雖保證 Jacobi 法和 Gauss-Seidel 法具備收斂性,但對角佔優是一個嚴苛的條件,並不常出現於現實應用。
[2] 證明見 Richard S. Varga 所著 Matrix Iterative Analysis,第二版,Springer,2000,頁83-84。
周老師您好 想請教 解線性方程Ax=b
自己在做數值 要收斂 一般都是 疊代次數>自訂次數 或 誤差<自訂誤差 時結束
想請教的是自訂誤差部分 要算向量的norm
我到的自訂誤差 為 ||b-A Xk||/||b-AX0|| 其中 X0為起始值 Xk為第K次疊代結果
要怎這解釋這個誤差
norm的計算是F (||.||F)
令 且 。所以相對殘量為
很多算法都採用上面的定義,不過,這個定義不適用於 接近零的情況。