為甚麼要改變方程組?
有限元素網格細化可以改善近似,卻也可能令剛度矩陣的條件數變差。共軛梯度法(CG)只需矩陣向量乘法便可求解對稱正定方程組,但迭代次數仍可能隨特徵值的分散程度增長。預處理改變求解的幾何,使特徵值可能較集中;只有當變換本身的成本低於所節省的工作時,它才有實際價值。
設 對稱正定,,預處理矩陣 固定且對稱正定。寫 表示求解 ,無須構造逆矩陣。令 為 的解。下文恆等式和終止結論均採用精確算術;前文的 CG 結果使用能量範數 。
定義 1.5.1
(對稱預處理)
有對稱正定平方根。令
則 等價於 。對任何非零 ,有 ,故 亦對稱正定。
這是用來推導的變換;實作時只需作用 及求解與 相關的方程,無須形成 。矩陣 與 相似,因此特徵值都是正實數,但它一般並非歐氏(Euclidean)內積下的對稱矩陣。不改變內積便直接把普通 CG 遞推套於它,並無上述理論保證。
推導可實作的遞推
寫 、。若 ,初始向量已是解;否則設 、。當 ,計算
若 就停止;否則解 ,再設
這個遞推就是 的普通 CG,改用原變量寫出。
引理 1.5.2
(與變換後系統上的 CG 等價)
對 從 開始執行普通 CG,其殘差為 ,搜尋方向為 。則在終止前的每個 ,
兩種方法使用相同的 與 ,並在同一步終止。
證明
(對三個變換量作歸納)
當 ,,且 。設三個關係在第 步成立,則
所以普通 CG 的步長等於 (1) 中的 。於是 ,而 。由於 可逆, 當且僅當 ,故兩者的終止時刻相同。否則普通係數 等於 (2) 中的 ,並且 。
證明透視
遞推從何而來
歸納同時處理三個關係,而它們以兩種不同方式變換:迭代值與搜尋方向乘上 ,殘差則乘上 。正是這種不對稱使方法可以實作。普通 CG 需要的每個內積,即 與 ,都變成 或 ,其中平方根互相抵消;唯一新增的運算是為求 而解一次與 相關的方程。
的對稱正定性用了兩次:一是使實對稱平方根存在,二是使 時 為正,從而 有定義。論證能夠收結,是因為 可逆,兩個終止事件完全相同,所以等價性對整個計算成立,而不只是到某一步為止。
正定保證非零殘差有 ; 正定和 CG 的構造保證終止前 ,故上述除法有效。除向量運算和內積外,每個未終止步驟需要一次 乘法和一次 求解。稠密或昂貴的預處理可以抵消減少迭代的好處。
定理 1.5.3
(最小化、終止與條件數界)
固定的 均對稱正定且 時,預處理 CG 在終止前給出下列仿射空間中 的唯一最小值:
它至多 步到達 。設 ;若 ,則
若 ,一步便足夠。
證明
(先轉移,再用切比雪夫(Chebyshev)多項式)
上述等價性把普通 CG 的 Krylov 空間最小化和有限終止結果由 移到 ,因為 。為證 (3),CG 在所有 中最小化,其中 、。將 正交對角化,可用 乘初始 範數來估計誤差,這裏 、。取縮放的切比雪夫(Chebyshev)多項式
利用 上 ,以及 時分母等於 ,便得 (3)。若 ,則 ,首次直線最小化即得解。這個界只用到兩端的特徵值;特徵值集中時它可能偏悲觀,也不能保證總運算時間較短。
完整的兩步計算
例題 1.5.4
(對角預處理)
取 、、 和 。則 、、、。故 ,而
解 方程得 及 ,故 、。現在 ,所以 、。直接相乘確認 。此處 的條件數為 ,而 的為 。
初始搜尋方向一般不是初始殘差,而是預處理後的殘差。每步最小化的是誤差的 範數,一般不是殘差的歐氏範數。變換後條件數較小,本身並不說明 的求解成本。以下兩個例子說明條件數量度甚麼、不量度甚麼。
例題 1.5.5
(耦合矩陣的 Jacobi 縮放)
設 ,取對角(Jacobi)預處理矩陣 。 的特徵值為 與 ,所以 。由 得
(3) 中的因子由 降至 ,而作用 只需每個分量一次除法。由於 ,精確算術下兩種方法都至多兩步終止;能推廣到大型矩陣的是因子的比較。
例題 1.5.6
(兩個不同特徵值使上界失效)
取 、、、。此時 ,(3) 中的因子為 ,所以兩步後 (3) 只保證 ,毫無資訊。然而 。由定理, 在所有滿足 、次數不超過二的多項式上最小化 ;多項式 在兩個特徵值處均為零,所以 ,最小值為零。具體而言,,,,;第二步便到達 。上界只看到兩端的特徵值,因此看不見特徵值的集中。
常見錯誤
(以預處理殘差作停止測試會受 的尺度影響)
反正要計算,所以人們容易在 很小時便停止。但把 換成 ()時,每個迭代值 都不變, 卻除以 ;同一個迭代值能否通過固定容差,竟取決於一個任意的尺度。應以 為準檢驗 ,或只在已知 的有效下界時使用 ,如下面的殘差證書。
反例模式
預處理矩陣為何要正定
取 、、。雖然 ,卻有 。公式 (1) 已失去 CG 推導所依賴的正量; 可逆及對稱並不足夠。
練習與解答
快速檢查
(精確預處理:若 ,從任意 出發最多需要多少步?)
先計算 。
解答 · 答案
,故至多一步。也可見 ,而 ,所以 。這通常不划算,因為求解預處理方程就是原問題。
快速檢查
(縮放:以 代替 ,其中 。變換後的條件數和迭代值如何改變?)
追蹤 、 與 的變化。
解答 · 答案
變為 ,所有特徵值均乘 ,比值不變。精確算術下 的迭代值亦相同:新的 是原來的 倍, 除以 ,每個 是原來的 倍,所以 不變;每個 亦不變。
快速檢查
(殘差證書:證明 。)
用 變換誤差。
解答 · 答案
設 、,則左邊為 。由 ,又有 。對角化得 ,因為每個特徵值都滿足 。要得到實用的數值證書,必須有有效的最小特徵值下界。
快速檢查
(左乘的陷阱:若 、,計算 。)
把 的每一行除以 相應的對角元素。
解答 · 答案
結果是 ,不是對稱矩陣,儘管 都對稱正定。須使用對稱變換或等價的預處理遞推。
本分析假設固定對稱正定的 被精確作用,且使用精確算術。捨入誤差、不精確或變動的內層求解、實際停止規則、可擴展預處理的構造和實測性能均需另外分析。