主題
Search

擬極小殘差法


雙共軛梯度法通常表現出相當不規則的收斂行為。此外,約化三對角系統的隱式LU分解可能不存在,導致演算法崩潰。擬極小殘差法(Freund 和 Nachtigal 1991)是一種相關的演算法,旨在克服這些問題。

擬極小殘差 (QMR) 方法演算法背後的主要思想是以最小二乘意義求解約化的三對角系統,類似於廣義極小殘差法 (GMRES) 中採用的方法。由於為 Krylov 子空間構建的基是雙正交的,而不是像 GMRES 中那樣是正交的,因此獲得的解被視為擬極小殘差解,這解釋了名稱的由來。此外,QMR 使用前瞻技術來避免底層 Lanczos 過程中的崩潰,這使其比雙共軛梯度法更穩健。

QMR 的收斂行為通常比雙共軛梯度法 (BCG) 更平滑。 Freund 和 Nachtigal (1991) 提出了相當一般的誤差界限,表明 QMR 的預期收斂速度可能與廣義極小殘差法大致相同。從 BCG 和 QMR 中殘差之間的關係(Freund 和 Nachtigal 1991,關係式 5.10)可以推斷出,在迭代過程中 BCG 取得重大進展的階段,QMR 已經獲得了 x^^ 的大致相同的近似值。另一方面,當 BCG 根本沒有進展時,QMR 可能仍然表現出緩慢的收斂速度。

此版本 QMR 方法中的前瞻步驟可以防止所有情況下的崩潰,除了所謂的“不可治癒的崩潰”,即任何實際數量的前瞻步驟都無法產生下一個迭代。

上面給出了使用預處理器 M=M_1M_2 的預處理擬極小殘差方法的虛擬碼。該演算法遵循不帶前瞻的兩項遞迴版本(Freund 和 Nachtigal 1994,演算法 7.1)。此版本的 QMR 比帶有前瞻的完整 QMR 方法更易於實現,但它容易受到底層 Lanczos 過程崩潰的影響。(其他實現變體包括是否縮放 Lanczos 向量,或者是否使用三項遞迴而不是耦合的兩項遞迴。這些決策通常對演算法的穩定性和效率有影響。)

殘差的計算是為了收斂性測試。如果使用右(或後)預處理,即 M_1=I,那麼在每次迭代中都可以計算出 |r^((i))| 的廉價上限,從而避免了 r^((i)) 的遞迴(Freund 和 Nachtigal 1991,命題 4.1)。這個上限可能過於悲觀,最多相差 sqrt(i+1) 倍。

QMR 在向量和並行實現方面與雙共軛梯度法大致存在相同的問題。每次迭代的標量開銷略高於 BCG。在所有稍便宜的 BCG 方法收斂不規則(但足夠快)的情況下,出於穩定性原因,QMR 可能是首選。


另請參閱

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

此條目由 Noel Black 和 Shirley Moore 貢獻,改編自 Barrett et al. (1994) (作者連結)

使用 探索

參考文獻

Barrett, R.; Berry, M.; Chan, T. F.; Demmel, J.; Donato, J.; Dongarra, J.; Eijkhout, V.; Pozo, R.; Romine, C.; 和 van der Vorst, H. 線性系統求解模板:迭代方法的構建塊,第 2 版。 Philadelphia, PA: SIAM, 1994. http://www.netlib.org/linalg/html_templates/Templates.htmlFreund, R. 和 Nachtigal, N. "QMR: 非 Hermitian 線性系統的擬極小殘差法。" Numer. Math. 60, 315-339, 1991.Freund, R. 和 Nachtigal, N. "基於耦合兩項遞迴的 QMR 方法的實現。" SIAM J. Sci. Statist. Comput. 15, 313-337, 1994.

在 上被引用

擬極小殘差法

請引用為

Black, NoelMoore, Shirley. "擬極小殘差法。" 來自 —— 資源,由 Eric W. Weisstein 建立。 https://mathworld.tw/Quasi-MinimalResidualMethod.html

學科分類