主題
Search

最小殘差法

共軛梯度法可以被看作是蘭索斯方法對於正定對稱系統的特殊變體。最小殘差法 (MINRES) 和 對稱 LQ 方法 (SYMMLQ) 是可以應用於對稱不定系統的變體。

共軛梯度法中的向量序列對應於類似於係數矩陣的三對角矩陣的分解。因此，如果矩陣是不定的，則可能發生演算法崩潰，對應於零主元。此外，對於不定矩陣，共軛梯度法的最小化性質不再明確定義。MINRES 方法是共軛梯度法的一種變體，它避免了 LU 分解，並且不會發生崩潰。MINRES 最小化 2-範數中的殘差。Paige 等人 (1995) 分析了共軛梯度法和 MINRES 方法對於不定系統的收斂行為。

當 A 不是正定的，而是對稱的時，我們仍然可以透過三項遞推關係為克雷洛夫子空間構造一個正交基。消除共軛梯度法方程中的搜尋方向得到一個遞推式

Ar^((i))=r^((i+1))t_(i+1,i)+r^((i))t_(i,i)+r^((i-1))t_(i-1,i),
(1)

它可以寫成矩陣形式為

AR_i=R_(i+1)T^__i,
(2)

其中 T^__i 是一個 (i+1)×i 三對角矩陣。

在這種情況下，我們遇到 (·,·)_(A) 不再定義內積的問題。然而，我們仍然可以嘗試透過獲得以下內容來最小化 2-範數中的殘差

x^((i)) in {r^((0)),Ar^((0)),...,A^(i-1)r^((0))}, x^((i))=R_iy^_
(3)

從而最小化

||Ax^((i))-b||_2=||AR_iy^_-b||_2
(4)
=||R_(i+1)T^__iy-b||_2.
(5)

現在我們利用以下事實，如果

D_(i+1)=diag(||r^((0))||_2,||r^((1))||_2,...,||r^((i))||_2),
(6)

那麼 R_(i+1)D_(i+1)^(-1) 是相對於當前克雷洛夫子空間的正交變換

||Ax^((i))-b||_2=||D_(i+1)T^__iy-||r^((0))||_2e^((1))||_2,
(7)

並且這個最終表示式可以簡單地看作是一個最小范數最小二乘問題。

T^__i 的 (i+1,i) 位置的元素可以透過簡單的吉文斯旋轉來消去，並且得到的上雙對角系統（其他次對角元素已在之前的迭代步驟中移除）可以簡單地求解，這導致了 MINRES 方法 (Paige and Saunders 1975)。

另請參閱

雙共軛梯度法, 切比雪夫迭代, 正規方程上的共軛梯度法 共軛梯度法, 共軛梯度平方方法, 靈活的廣義最小殘差法, 廣義最小殘差法, 線性方程組, 非平穩迭代法, 預處理器, 準最小殘差法 平穩迭代法, 對稱 LQ 方法, 無轉置準最小殘差法

此條目由 Noel Black 和 Shirley Moore 貢獻，改編自 Barrett 等人 (1994) (作者連結)

使用 探索

參考文獻

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; and van der Vorst, H. 線性系統求解模板：迭代方法構建塊，第二版 Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.html.Paige, C.; Parlett, B.; and van der Vorst, H. "來自克雷洛夫子空間的近似解和特徵值界限。" Numer. Lin. Alg. Appl. 29, 115-134, 1995.Paige, C. and Saunders, M. "稀疏不定線性方程組的解。" SIAM J. Numer. Anal. 12, 617-629, 1975.

在 中引用

最小殘差法

以此引用

Black, Noel 和 Moore, Shirley. "最小殘差法。" 來自 —— 資源，由 Eric W. Weisstein 建立。 https://mathworld.tw/MinimalResidualMethod.html

主題分類