Skip to main content

CG algorithm and its limitations

Short answer

CG algorithm: start with x0, r0=b−Ax0, d0=r0; iterate αk=(r_k·r_k)/(d_k·Ad_k), x_{k+1}=x_k+αk d_k, r_{k+1}=r_k−αk A d_k, if small stop; βk=(r_{k+1}·r_{k+1})/(r_k·r_k), d_{k+1}=r_{k+1}+βk d_k. Limitations: only for symmetric positive-definite A; ill-conditioning slows convergence; round-off errors may degrade conjugacy; ineffective for many right-hand sides.

Write down the algorithm for solving a set of linear equations by the conjugate gradient method and its limitations.

Algorithm

  1. Choose a starting vector x0x_0 (usually 00). Compute the residual r0=b−Ax0r_0 = b - Ax_0 and set the first search direction d0=r0d_0 = r_0.
  2. For k=0,1,2,…k = 0, 1, 2, \dots repeat:
    • Step length: αk=rkTrkdkTAdk\alpha_k = \dfrac{r_k^T r_k}{d_k^T A d_k}
    • Update the solution: xk+1=xk+αkdkx_{k+1} = x_k + \alpha_k d_k
    • Update the residual: rk+1=rk−αkAdkr_{k+1} = r_k - \alpha_k A d_k
    • Check convergence: stop if ∥rk+1∥<\|r_{k+1}\| < tolerance.
    • Direction factor: βk=rk+1Trk+1rkTrk\beta_k = \dfrac{r_{k+1}^T r_{k+1}}{r_k^T r_k}
    • New direction: dk+1=rk+1+βkdkd_{k+1} = r_{k+1} + \beta_k d_k
  3. The last xk+1x_{k+1} is the solution.

Limitations

  • Applies only to symmetric, positive definite matrices (not to general or indefinite systems without modification).
  • Convergence slows for ill-conditioned matrices (large ratio of largest to smallest eigenvalue), so preconditioning is often needed.
  • Round-off errors destroy the conjugacy of the directions, so more than nn iterations may be required in practice.
  • Gives one right-hand side at a time; a direct (factored) solver is more efficient for many load cases.
  • Needs a good stopping criterion; residual may fall while the error is still large.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Computational Techniques in Civil Engineering chapter 2 questions →