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

# Conjugate gradient method and algorithm

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

- Asked in: 2079 Shrawan, 5 marks; 2071 Bhadra, 3 marks (asked 2 times)
- Video: [ALGORITHM OF CONJUGATE GRADIENT METHOD](https://www.youtube.com/watch?v=77pmiYjau_w) — Civil Engineer
- 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-method-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_8/computational_techniques_in_civil_engineering/chapter-2

## Question

Explain the conjugate gradient method and its algorithm for solving a system of linear equations.

## Short answer

Conjugate gradient solves symmetric positive definite systems by minimising energy along A-conjugate directions, converging in at most n steps. Algorithm: set initial residual r0=b-Ax0, direction d0=r0; for each step compute alpha=(r_k^T r_k)/(d_k^T A d_k), update x and r, then beta=(r_{k+1}^T r_{k+1})/(r_k^T r_k) to update direction.

## Answer

#### Conjugate gradient method
The conjugate gradient (CG) method solves $Ax = b$ for a **symmetric, positive definite** matrix $A$. It is equivalent to minimising the quadratic energy
$$
\Pi(x) = \tfrac{1}{2}x^T A x - b^T x
$$
whose minimum is exactly the solution of $Ax=b$. The minimum is searched along directions $d_k$ that are **A-conjugate**, i.e. $d_i^T A d_j = 0$ for $i \ne j$. Each step minimises $\Pi$ along one direction without spoiling the earlier ones, so in exact arithmetic the solution is reached in at most $n$ steps for an $n \times n$ system. The residual $r = b - Ax$ is the negative gradient of $\Pi$.

Compared with direct elimination, CG needs only matrix-vector products, so it stores only the non-zero terms of $A$. It is good for large sparse systems, and rounding errors do not accumulate in a long elimination.

#### 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.

Convergence is faster if $A$ has clustered eigenvalues, and preconditioning is used to improve this.

## Check yourself

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

1. For what matrices does CG apply?
   A. Symmetric positive definite
   B. Any square matrix
   C. Diagonally dominant only
   D. Banded unsymmetric only
   Answer: A. CG minimises a quadratic energy which needs symmetric positive definite A. (Key point: CG requirement)

2. The CG solution of Ax = b is the minimum of which function?
   A. x^T x - b
   B. (1/2) x^T b
   C. ||Ax||
   D. (1/2)x^T A x - b^T x
   Answer: D. Its gradient is Ax - b = -r, so the minimum is the solution. (Key point: CG as minimisation)

3. What does A-conjugate directions mean?
   A. d_i^T d_j = 0
   B. d_i = r_i
   C. d_i^T A d_j = 0 for i not equal j
   D. A d_i = 0
   Answer: C. Conjugate directions let each step minimise without spoiling earlier ones. (Key point: A-conjugate)

4. What is the step length alpha_k?
   A. (d_k^T A d_k)/(r_k^T r_k)
   B. (r_k^T r_k)/(d_k^T A d_k)
   C. (r_{k+1}^T r_{k+1})/(r_k^T r_k)
   D. r_k^T d_k
   Answer: B. The last ratio is beta, not alpha. (Key point: Step length)

## Related in Computational Techniques in Civil Engineering

- [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×
- [Conjugate gradient numerical (3,0,2 system)](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-numerical-3-0-2) — Computational Techniques in Civil Engineering, chapter 2, asked 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
- [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
- [Solution methods of linear equations with examples](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Asolution-methods-linear-examples) — Computational Techniques in Civil Engineering, chapter 2
- [Why conjugate gradient over Gaussian methods](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-vs-gaussian) — Computational Techniques in Civil Engineering, chapter 2

## Related in other subjects

- [Consistency of a linear system](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aconsistency-of-a-linear-system-nine) — Mathematics III, chapter 1
- [Two-mass system equations, X2/F, F-I and F-V analogies](https://www.bctengineer.com/question.md?key=semester_3%2Fcontrol_systems%3Ade-tf-fi-fv-m1-m2) — Control Systems, chapter 2
- [Consistency of a linear system](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aconsistency-of-a-linear-system-three) — Mathematics III, chapter 1, asked 9×
- [Consistency of a linear system](https://www.bctengineer.com/question.md?key=semester_3%2Fmathematics_iii%3Aconsistency-of-a-linear-system-two) — Mathematics III, chapter 1, asked 8×