为什么 Krylov 子空间迭代方法比经典迭代更快?

计算科学 线性求解器 迭代法 克雷洛夫法 线性系统
2021-12-20 19:01:18

这个学期,我一直在研究最流行的迭代方法,即Krylov子空间迭代方法。对于大型稀疏系统线性 其中是非奇异的,我知道直接方法不适用于此。因此提出了许多迭代方法,例如经典的平稳迭代方法,如Jacobi、Gauss-Seidel、SOR等。但当系统规模变大时,收敛速度变慢,SOR的最优参数难以找到选择。

Ax=b,
A

然后需要 Krylov 子空间方法,如CG、GMRES、MINRES等,这些方法比那些经典的迭代方法要快。此外,我在MATLAB中做了数值例子,结果确实证明了Krylov方法的收敛速度更快。

我的问题是,虽然 Krylov 子空间方法确实比经典迭代方法快,但为什么呢?我的意思是,从哪里可以看出 Krylov 方法比那些经典方法更快?我只知道 Krylov 方法必须在次迭代内收敛,对于阶矩阵并且它不需要选择最佳参数。但是我还是不知道为什么 Krylov 方法比经典迭代方法快?有什么建议?NNA

1个回答

我必须承认我自己从来没有真正检查过所有的细节,但我认为这是一个总体思路的草图。

  1. Richardson 迭代产生的第次迭代位于 Krylov 子空间中。kxkKk(A,b)
  2. 由 Krylov 方法产生的第次迭代通常会最小化同一 Krylov 空间内的某些目标函数,因此它比 Richardson“更好”。kxk
  3. Jacobi 等价于带有diag(A)作为预条件子的 Richardson,因此它比带有相同预条件子的 Krylov 方法差。
  4. Gauss-Seidel 等价于 Richardsontril(A)作为预条件子。