Conjugate Gradient Step Explained with Worked Examples

In the conjugate gradient method for (with symmetric positive definite) the step length along the search direction is , where is the residual.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

This page is easier if you are comfortable with:

What Conjugate gradient step means

The method minimises by moving along directions that are conjugate (orthogonal in the -inner product). The first step is the same as steepest descent: . For , , : , , , , so and .

In exact arithmetic the method reaches the exact solution in at most steps for an matrix; for a system , and at once. For a diagonal matrix and : . The products use matrix multiplication and the scalar product.

The convergence rate depends on the condition number of , and the method is far faster than gradient descent for large sparse systems, which are also treated by Jacobi and Gauss–Seidel iterations. Newton-type methods are in Newton's method for optimisation. The slow rate of plain gradient descent that this method avoids is analysed in the gradient descent rate.

What is it used for?

The conjugate gradient method solves large linear systems with one step size per direction, which is the exact minimum along that line.

How to use conjugate gradient step

  1. Start with , compute and set .
  2. Compute .
  3. Update and .
  4. Update the direction by and repeat.

Graph

Along the first direction the quadratic is 10α² − 5α, minimised at α = 0.25minimum at α = 0.2500.10.20.30.40.50.6-0.6-0.4-0.200.20.40.60.81Along the first direction the quadratic is 10α² − 5α, minimised at α = 0.25αff along p0Graph with x from 0 to 0.6 and y from -0.7 to 1. Shows the curve f along p0; point minimum at α = 0.25 at (0.25, -0.625).

The formula for α finds the lowest point of this parabola exactly.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: first step, 2 × 2

For , , , find and .

Worked example
Answer
α0=0.25, x1=(0.25,0.5)\alpha_0=0.25,\ \mathbf x_1=(0.25,0.5)
  1. r₀ = p₀
  2. p₀ᵀAp₀
  3. α₀
  4. x₁

Example 2: diagonal matrix

For , , , find .

Worked example
Answer
518≈0.2778\dfrac{5}{18}\approx0.2778
  1. r₀ᵀr₀
  2. p₀ᵀAp₀
  3. α₀

Example 3: one variable

Solve from with one CG step.

Worked example
Answer
α0=0.2, x1=2 (exact)\alpha_0=0.2,\ x_1=2\ (\text{exact})
  1. r₀
  2. α₀
  3. x₁

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

r = (2, 0), A = diag(2, 1), p = r

rᵀr

4.

same

pᵀAp

8.

same

α

0.5.

r = (1, 2), A = (4 1; 1 3), p = r

α = 5/20

0.25.

Word problems

α_k = rₖᵀrₖ / pₖᵀApₖ. The first direction is p₀ = r₀ = b − Ax₀.

rᵀr

r = (2, 0).

  1. 4 + 0
  2. Check: ✓4

pᵀAp

p = (2, 0), A = diag(2, 1).

  1. 2 × 4
  2. Check: ✓8

α Higher

4/8.

  1. 0.5
  2. Check: ✓0.5

Second case Higher

r = (1, 2): rᵀr = 5, pᵀAp = 20.

  1. 5/20
  2. Check: ✓0.25

Common mistakes

α = pᵀp / rᵀr

wrong ✗

rᵀr / pᵀAp ✓

Formula.

Forgetting A

pᵀp ✗

pᵀAp ✓

Energy norm.

Non-symmetric A

any A ✗

SPD A ✓

Condition.

Reusing old r

old ✗

update each step ✓

Iteration.

Exam tips

  1. p₀ = r₀.
  2. α = rᵀr / pᵀAp.
  3. A must be SPD.
  4. Update r = r − αAp.
  5. Converges in ≤ n steps exactly.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. α: r = (3, 0), A = diag(3, 1) Foundation

0.3333

2. α: r = (0, 2), A = diag(1, 4) Foundation

0.25

3. rᵀr for r = (3, 4) Foundation

25

4. α: r = (1, 1), A = diag(2, 2) Higher

0.5

5. α: r = (2, 0), A = diag(4, 1) Higher

0.25

6. pᵀAp: p = (1, 1), A = diag(3, 5) Higher

8

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Conjugate gradient
Iterative solver.
Residual (r)
b − Ax.
Search direction (p)
Step direction.
Step length (α)
Distance along p.
SPD matrix
Symmetric positive definite.
A-conjugate
pᵢᵀApⱼ = 0.

Frequently asked questions

What is the CG step length?

α = rᵀr / pᵀAp.

What is the first direction?

The residual r₀.

What must A satisfy?

Symmetric positive definite.

How many steps does it need?

At most n in exact arithmetic.

Which page covers gradient descent?

gradient descent.

Which page covers the condition number?

condition number.

More in Numerical methods and optimisation and the formula sheets.