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

# Linear solution techniques; CG algorithm

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

- Asked in: 2072 Asoj, 5+3 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/solution-techniques-cg-algorithm
- Whole chapter: https://www.bctengineer.com/md/semester_8/computational_techniques_in_civil_engineering/chapter-2

## Question

Explain different solution techniques of linear equations. Write the algorithm for the conjugate gradient method.

## Short answer

Linear systems are solved by direct methods such as Gauss elimination, LU and Cholesky, which factor the matrix, or by iterative methods such as Jacobi, Gauss-Seidel, SOR and CG, which refine a guess without fill-in. CG minimizes (1/2)x^T A x - b^T x using A-conjugate search directions and converges in at most n steps for symmetric positive definite A.

## Answer

Linear system $[A]\{x\}=\{b\}$ is solved by:
1. **Direct methods** (finite number of steps, exact apart from round-off): Gauss elimination (reduce to upper triangular form, back-substitute), Gauss-Jordan, LU decomposition, Cholesky decomposition $A=LL^T$ for symmetric positive definite $A$, and the matrix inverse. In FEM they use banded or skyline storage.
2. **Iterative methods** (start from a guess and improve): Jacobi, Gauss-Seidel, successive over-relaxation, and the conjugate gradient method. They suit very large sparse systems since the matrix is never changed and no fill-in occurs. Jacobi and Gauss-Seidel need diagonal dominance for convergence; CG needs a symmetric positive definite matrix.

| Direct | Iterative |
|---|---|
| Fixed operation count | Number of iterations depends on tolerance |
| Fill-in within band/skyline | Keeps sparsity |
| Good for many load cases (factor once) | Good for very large systems |

#### Algorithm of the 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$.

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.

## Check yourself

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

1. Which list contains only iterative methods for solving [A]{x} = {b}?
   A. Gauss elimination, LU decomposition, Cholesky
   B. Jacobi, Gauss-Seidel, successive over-relaxation, conjugate gradient
   C. Gauss-Jordan, Jacobi, matrix inverse
   D. Cholesky, Gauss-Seidel, LU decomposition
   Answer: B. Jacobi, Gauss-Seidel, SOR and CG start from a guess and improve it. Gauss elimination, Gauss-Jordan, LU, Cholesky and the inverse are direct methods. (Key point: Direct vs iterative methods)

2. Why are iterative methods preferred for very large sparse systems?
   A. They always need fewer operations than direct methods for any size
   B. They never need a convergence condition
   C. The matrix is never changed, so no fill-in occurs and sparsity is kept
   D. They give an exact answer in a fixed number of steps
   Answer: C. Iterative methods only use matrix-vector products with the original matrix, so sparsity is kept with no fill-in. Direct methods fill in the band or skyline. (Key point: When iterative methods suit)

3. What does the conjugate gradient method actually minimise?
   A. The quadratic energy 1/2 x^T A x - b^T x, whose minimum solves Ax = b
   B. The determinant of A
   C. The sum of the diagonal terms of A
   D. The condition number of A at each step
   Answer: A. CG minimises Pi(x) = 1/2 x^T A x - b^T x; its minimum is exactly the solution of Ax = b. The residual is the negative gradient of Pi. (Key point: CG as energy minimisation)

4. Why does CG reach the solution in at most n steps in exact arithmetic?
   A. Each step uses a fresh random direction
   B. Search directions are A-conjugate (d_i^T A d_j = 0), so each step minimises along one direction without spoiling earlier ones
   C. The matrix is reduced to triangular form in n steps
   D. The step length is always 1
   Answer: B. A-conjugate directions let each line minimisation keep the earlier ones valid, so after n independent directions the minimum is reached. (Key point: A-conjugate directions)

## Related in Computational Techniques in Civil Engineering

- [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
- [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×
- [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
- [CG algorithm and its limitations](https://www.bctengineer.com/question.md?key=semester_8%2Fcomputational_techniques_in_civil_engineering%3Acg-algorithm-limitations) — 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
- [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