定常迭代法和松弛法

定常迭代法通过矩阵分裂并重复应用固定的更新规则来求解线性系统；经典的雅可比法、高斯-赛德尔法和逐次超松弛法是其基础示例。

Definition

定常迭代法是指在每一步都应用相同的迭代矩阵的迭代方法，该迭代矩阵来源于将系数矩阵分解为易于求逆的部分和余项；收敛性由所得迭代矩阵的谱半径决定。

Scope

本主题涵盖矩阵分裂框架、雅可比迭代和高斯-赛德尔迭代、逐次超松弛法及最优松弛参数的选择、收敛的谱半径判据，以及这些简单迭代法在多重网格中作为平滑器和作为预处理器的作用。

Core questions

• 矩阵分裂如何产生线性系统的定点迭代？
• 雅可比法和高斯-赛德尔法有何不同，为什么高斯-赛德尔法通常更快？
• 超松弛如何加速收敛，以及如何选择最优参数？
• 在矩阵的什么条件下这些迭代会收敛？

Key theories

矩阵分裂和谱半径判据

将矩阵写成一个易于求逆的部分减去一个余项，定义了一个定常迭代，其误差在每一步都被一个迭代矩阵相乘；当且仅当该迭代矩阵的谱半径小于1时，迭代对每个起始猜测都收敛。

逐次超松弛

通过使用松弛因子对高斯-赛德尔校正进行过冲，逐次超松弛可以大大减小谱半径；对于某些结构化矩阵，最优松弛参数是解析已知的，并能带来显著的速度提升。

Mechanisms

雅可比法同时更新所有未知数，仅使用前一次迭代的值，这等同于分离出对角线部分。高斯-赛德尔法在同一次迭代中利用最新更新的值，分离出下三角部分，通常收敛速度更快。逐次超松弛法通过一个松弛参数对旧值和高斯-赛德尔更新值进行加权平均；对于合适的矩阵，选择大于1的松弛参数可以加速收敛。对于严格对角占优或对称正定矩阵等类别，这三种方法的收敛性均有保证，并通过迭代矩阵的谱半径进行量化。

Clinical relevance

尽管对于大型系统而言，定常方法作为独立的求解器通常速度太慢而缺乏竞争力，但它们作为多重网格核心的平滑器、Krylov 方法的简单预处理器以及易于并行化的构建块仍然很重要；特别是高斯-赛德尔法和加权雅可比法在现代多级求解器中无处不在。

History

雅可比迭代和高斯-赛德尔迭代可追溯到19世纪，而逐次超松弛法及其严格的收敛理论由 David Young 和 Richard Varga 在20世纪50年代提出；尽管后来被 Krylov 方法和多重网格方法作为主要求解器所超越，但这些迭代法作为多级和预处理方案的基本组成部分得以复兴。

Key figures

• Carl Friedrich Gauss
• Philipp Ludwig von Seidel
• David M. Young
• Richard S. Varga

Seminal works

• saad2003
• varga2000

Frequently asked questions

为什么高斯-赛德尔法通常比雅可比法快？

高斯-赛德尔法在同一次迭代中立即使用更新后的值，因此信息在未知数中传播得更快，通常与仅使用前一次迭代值的雅可比法相比，迭代次数减少一半。

如果这些方法很慢，为什么它们仍然被研究？

它们是优秀的平滑器和简单的预处理器。在多重网格内部，几次高斯-赛德尔或加权雅可比迭代可以有效地消除振荡误差，这正是多重网格所需要的，因此这些经典迭代作为现代快速求解器的组成部分得以延续。