Skip to main content
forgot the exponent $k$ in the formula, oops
Source Link
Federico Poloni
  • 20.2k
  • 2
  • 82
  • 120

The standard error bound for (non-preconditioned) CG is given in terms of the condition number $\kappa$ only, and it is $$ \left\Vert x-x_k\right\Vert_A \leq 2 \left\Vert x-x_0\right\Vert_A\left(\frac{\kappa^{1/2}-1}{\kappa^{1/2}+1}\right) $$$$ \left\Vert x-x_k\right\Vert_A \leq 2 \left\Vert x-x_0\right\Vert_A\left(\frac{\kappa^{1/2}-1}{\kappa^{1/2}+1}\right)^k $$ (see e.g. Golub and Van Loan, thm 10.2.6). The norm is the energy norm $\left\Vert x\right\Vert_A:=(x^TAx)^{1/2}$.

So the method should converge no matter what the preconditioner is. To have better convergence, you need to ensure that the matrix after preconditioning is "as close to the identity as possible". Partial guesses on the shape its spectrum, deriving e.g. from lower-dimensional versions of the same problem, or on previous knowledge, can help, but there is no one-size-fits-all solution AFAIK.

The standard error bound for (non-preconditioned) CG is given in terms of the condition number $\kappa$ only, and it is $$ \left\Vert x-x_k\right\Vert_A \leq 2 \left\Vert x-x_0\right\Vert_A\left(\frac{\kappa^{1/2}-1}{\kappa^{1/2}+1}\right) $$ (see e.g. Golub and Van Loan, thm 10.2.6). The norm is the energy norm $\left\Vert x\right\Vert_A:=(x^TAx)^{1/2}$.

So the method should converge no matter what the preconditioner is. To have better convergence, you need to ensure that the matrix after preconditioning is "as close to the identity as possible". Partial guesses on the shape its spectrum, deriving e.g. from lower-dimensional versions of the same problem, or on previous knowledge, can help, but there is no one-size-fits-all solution AFAIK.

The standard error bound for (non-preconditioned) CG is given in terms of the condition number $\kappa$ only, and it is $$ \left\Vert x-x_k\right\Vert_A \leq 2 \left\Vert x-x_0\right\Vert_A\left(\frac{\kappa^{1/2}-1}{\kappa^{1/2}+1}\right)^k $$ (see e.g. Golub and Van Loan, thm 10.2.6). The norm is the energy norm $\left\Vert x\right\Vert_A:=(x^TAx)^{1/2}$.

So the method should converge no matter what the preconditioner is. To have better convergence, you need to ensure that the matrix after preconditioning is "as close to the identity as possible". Partial guesses on the shape its spectrum, deriving e.g. from lower-dimensional versions of the same problem, or on previous knowledge, can help, but there is no one-size-fits-all solution AFAIK.

Source Link
Federico Poloni
  • 20.2k
  • 2
  • 82
  • 120

The standard error bound for (non-preconditioned) CG is given in terms of the condition number $\kappa$ only, and it is $$ \left\Vert x-x_k\right\Vert_A \leq 2 \left\Vert x-x_0\right\Vert_A\left(\frac{\kappa^{1/2}-1}{\kappa^{1/2}+1}\right) $$ (see e.g. Golub and Van Loan, thm 10.2.6). The norm is the energy norm $\left\Vert x\right\Vert_A:=(x^TAx)^{1/2}$.

So the method should converge no matter what the preconditioner is. To have better convergence, you need to ensure that the matrix after preconditioning is "as close to the identity as possible". Partial guesses on the shape its spectrum, deriving e.g. from lower-dimensional versions of the same problem, or on previous knowledge, can help, but there is no one-size-fits-all solution AFAIK.