为什么预处理CG比基础CG收敛得更快

Question

为什么预处理共轭梯度( CG )算法比基本CG算法收敛得更快，有什么直观的解释吗？

Answer 1

共轭梯度等价于预条件矩阵为单位矩阵的预条件共轭梯度。如果您可以使用矩阵本身作为预条件，那么PCG将在一次迭代中收敛。我们的希望是，通过使用一种预处理程序，它与单位矩阵“更相似”，但比矩阵本身更容易求解，那么PCG在求解同等质量的问题时将比CG更快。

Answer 2

我认为This link提供了一个令人满意的解释。

基本上，共轭梯度法的收敛速度取决于sqrt(kappa(A))，即要求解的矩阵的条件数。所以你要做的就是选择一个矩阵M，这样，kappa(inv(M) * A) < kappa(A)，然后求解系统inv(M) * A * x = inv(M) * b。这将花费较少的迭代来求解，因为要求解的矩阵的条件数比原始矩阵少。