---
title: "CG algorithm and its limitations"
subject: "Computational Techniques in Civil Engineering"
chapter: 2
key: "semester_8/computational_techniques_in_civil_engineering:cg-algorithm-limitations"
source: https://www.bctengineer.com/q/semester_8/computational_techniques_in_civil_engineering/cg-algorithm-limitations
site: BCT Engineering
---

# CG algorithm and its limitations

Computational Techniques in Civil Engineering · Chapter 2: Solutions of linear equations

- Asked in: 2077 Chaitra, 3+2 marks
- Answer checked by Claude Opus 5.5 (high effort) on 2026-10-14
- Page: https://www.bctengineer.com/q/semester_8/computational_techniques_in_civil_engineering/cg-algorithm-limitations
- Whole chapter: https://www.bctengineer.com/md/semester_8/computational_techniques_in_civil_engineering/chapter-2

## Question

Write down the algorithm for solving a set of linear equations by the conjugate gradient method 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.

## Answer

#### Algorithm
1. Choose a starting vector $x_0$ (usually $0$). Compute the residual $r_0 = b - Ax_0$ and set the first search direction $d_0 = r_0$.
2. For $k = 0, 1, 2, \dots$ repeat:
   - Step length: $\alpha_k = \dfrac{r_k^T r_k}{d_k^T A d_k}$
   - Update the solution: $x_{k+1} = x_k + \alpha_k d_k$
   - Update the residual: $r_{k+1} = r_k - \alpha_k A d_k$
   - Check convergence: stop if $\|r_{k+1}\| <$ tolerance.
   - Direction factor: $\beta_k = \dfrac{r_{k+1}^T r_{k+1}}{r_k^T r_k}$
   - New direction: $d_{k+1} = r_{k+1} + \beta_k d_k$
3. The last $x_{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 $n$ 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.

## Check yourself

The answer's key points as multiple-choice questions, with the correct option and why.

1. What is beta_k?
   A. (r_{k+1}^T r_{k+1})/(r_k^T r_k)
   B. (r_k^T r_k)/(d_k^T A d_k)
   C. r_{k+1} - r_k
   D. d_k^T A d_k
   Answer: A. d_{k+1} = r_{k+1} + beta_k d_k. (Key point: Beta)

2. CG is limited to which matrices?
   A. Diagonally dominant only
   B. Any matrix
   C. Sparse only
   D. Symmetric positive definite
   Answer: D. Not for general or indefinite systems. (Key point: Limitation matrices)

3. How is slow convergence of ill-conditioned systems handled?
   A. Using more right-hand sides
   B. Smaller tolerance
   C. Preconditioning
   D. Using unsymmetric matrices
   Answer: C. Preconditioning improves eigenvalue clustering. (Key point: Ill-conditioning)

## Related in Computational Techniques in Civil Engineering

- [Conjugate gradient method and algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-method-algorithm) — Computational Techniques in Civil Engineering, chapter 2, asked 2×
- [Linear solution techniques; CG algorithm](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-techniques-cg-algorithm) — Computational Techniques in Civil Engineering, chapter 2
- [Linear solution techniques; CG two iterations](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-techniques-cg-numerical-two-iter) — Computational Techniques in Civil Engineering, chapter 2
- [CG algorithm; Gauss-Seidel numerical](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-algorithm-gauss-seidel-numerical) — Computational Techniques in Civil Engineering, chapter 2
- [Conjugate gradient three iterations (10,-6,0)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-three-iterations-a) — Computational Techniques in Civil Engineering, chapter 2
- [Conjugate gradient numerical (2,-1 system)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-numerical-three-unknowns-a) — Computational Techniques in Civil Engineering, chapter 2, asked 2×

## Related in other subjects

- [Tractive effort up and down a gradient](https://www.bctengineer.com/question.md?key=semester_7%2Futilization_of_electrical_energy%3Atractive-effort-gradient) — Utilization of Electrical Energy, chapter 4
- [Quadrilateral speed-time curve on down gradient](https://www.bctengineer.com/question.md?key=semester_7%2Futilization_of_electrical_energy%3Aquadrilateral-curve-down-gradient-energy) — Utilization of Electrical Energy, chapter 4
- [Conditions for solving problems recursively](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecursion-conditions) — Data Structure and Algorithm, chapter 5
- [Methods for solving recurrences](https://www.bctengineer.com/question.md?key=semester_4%2Fdata_structure_and_algorithm%3Arecurrence-solving-methods) — Data Structure and Algorithm, chapter 9