Chapter map

1. 1. System
2. 2. Start
3. 3. First numerator
4. 4. First denominator
5. 5. Alpha zero
6. 6. First iterate
7. 7. Residual
8. 8. Beta
9. 9. New direction
10. 10. Second alpha
11. 11. Second iterate
12. 12. Residual check
13. 13. Conditioning
14. 14. Conclusion

Visit the How Mathematics Works hub for the wider series and its connections to education, reasoning, science, computing, design and careers.

---

1. System

The central mathematical idea is concrete. Set A=diag(1,4), b=(1,4).

A concrete situation

Solution is (1,1).

What the mathematics does not license

A is SPD. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record system. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

2. Start

Here the geometry becomes operational. Use x0=(0,0).

A concrete situation

r0=p0=(1,4).

What the mathematics does not license

Compute b-Ax. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record vectors. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

3. First numerator

This step deserves a careful pause. Compute r0 dot r0.

A concrete situation

It is 17.

What the mathematics does not license

Use Euclidean dot. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record 17. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

4. First denominator

The useful question is not only how to calculate, but what the calculation assumes. Compute p0 dot A p0.

A concrete situation

It is 65.

What the mathematics does not license

Multiply A first. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record 65. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

5. Alpha zero

A small example makes the mechanism visible. Divide numerator by denominator.

A concrete situation

alpha0=17/65.

What the mathematics does not license

Keep fraction. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record alpha. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

6. First iterate

This is where modelling choices begin to affect evidence. Add alpha0 p0.

A concrete situation

x1=(17/65,68/65).

What the mathematics does not license

Check both entries. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record x1. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

7. Residual

The central mathematical idea is concrete. Subtract alpha0 A p0.

A concrete situation

r1=(48/65,-12/65).

What the mathematics does not license

Check orthogonality to r0. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record r1. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

8. Beta

Here the geometry becomes operational. Divide new residual norm squared by old.

A concrete situation

beta0=144/4225.

What the mathematics does not license

Simplify carefully. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record beta. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

9. New direction

This step deserves a careful pause. Set p1=r1+beta0 p0.

A concrete situation

Directions are A-conjugate.

What the mathematics does not license

Verify p0^T A p1=0. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record p1. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

10. Second alpha

The useful question is not only how to calculate, but what the calculation assumes. Apply the same quotient.

A concrete situation

alpha1=65/68.

What the mathematics does not license

Use exact values. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record alpha. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

11. Second iterate

A small example makes the mechanism visible. Add alpha1 p1.

A concrete situation

x2=(1,1).

What the mathematics does not license

Exact arithmetic. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Record x2. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

12. Residual check

This is where modelling choices begin to affect evidence. Compute b-Ax2.

A concrete situation

It is zero.

What the mathematics does not license

Floating point may show roundoff. Evidence becomes stronger when the limitation is tested instead of hidden.

Try it, check it, transfer it

Record residual. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

13. Conditioning

The central mathematical idea is concrete. Use eigenvalues 1 and 4.

A concrete situation

Condition number is 4.

What the mathematics does not license

State norm. Keeping this boundary clear makes the result easier to audit and transfer.

Try it, check it, transfer it

Record kappa. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

14. Conclusion

Here the geometry becomes operational. State SPD,preconditioner,tolerance and residual.

A concrete situation

Two dimensions finish in two exact steps.

What the mathematics does not license

Do not promise finite precision termination. A trustworthy workflow records the choice before seeing the final test result.

Try it, check it, transfer it

Write conclusion. Then explain the result to someone who has not seen the formula. If the explanation needs a hidden assumption, add that assumption to the model record.

---

A seven-day practice lab

1. Day 1: define the decision, observation unit, X variables and Y or reference condition.
2. Day 2: reproduce the smallest worked example and check every dimension, unit and sign.
3. Day 3: build a transparent baseline and write what it assumes.
4. Day 4: fit the main method inside a training-only pipeline; record every parameter.
5. Day 5: challenge one assumption with a deliberately difficult dataset or operating regime.
6. Day 6: compare validation metrics with the practical workload created by errors.
7. Day 7: present one supported conclusion, one unresolved uncertainty and one safe next experiment.

Questions for a student, parent or mentor

• Which part of the model is a mathematical definition, and which part is a choice?
• What small calculation would catch a sign, scale or dimension error?
• What evidence comes from training, validation and the untouched test?
• What benign condition could look like a fault or prediction failure?
• How would the answer change for another response, asset, school project or time period?
• What should a human review before acting on the score?

A method-specific audit before deployment

The conjugate gradient method solves a symmetric positive definite linear system Ax=b by building approximations in nested Krylov subspaces. It uses matrix-vector products and short vector recurrences rather than forming a dense factorization.

For A=diag(1,4), b=(1,4) and x0=(0,0), the exact solution is (1,1). The initial residual and search direction are r0=p0=(1,4).

The first step length is alpha0=(r0 dot r0)/(p0 dot A p0)=17/65. Therefore x1=(17/65,68/65), approximately (0.2615,1.0462).

The new residual is r1=(48/65,-12/65). Its squared norm is 2448/4225, and beta0=(r1 dot r1)/(r0 dot r0)=144/4225.

The next direction is p1=r1+beta0 p0. The second step length is 65/68, and exact arithmetic gives x2=(1,1), with a zero residual up to floating-point rounding.

Finite termination in at most n steps is an exact-arithmetic result for an n-dimensional symmetric positive definite problem. Rounding can destroy perfect conjugacy, so large computations use residual checks, preconditioning and sometimes restarts.

Krylov subspace K_k(A,r0) is spanned by r0, A r0, through A^{k-1}r0. Conjugate gradient chooses the approximation that minimizes the quadratic energy over the current affine Krylov space.

Did You Know? The search directions are A-conjugate: p_i transpose A p_j equals zero for different directions in exact arithmetic. This geometry prevents later steps from undoing earlier progress in the same way as steepest descent can zigzag.

Positive definiteness matters because it makes the quadratic strictly convex and the A-inner product valid. Applying textbook CG to an indefinite or nonsymmetric matrix can break the reasoning even if the code still returns numbers.

The convergence rate depends on eigenvalue distribution and condition number. Two matrices with the same dimension can require very different iteration counts, while clustered eigenvalues can make actual convergence faster than a worst-case bound.

A residual is computable from b-Ax, but a small residual and a small solution error are linked through matrix conditioning. Reporting only an iteration count hides both scale and accuracy.

Sparse matrix-vector products make CG attractive for discretised differential equations, graphs and inverse problems. The solver can converge accurately to the wrong scientific answer if the model, boundary conditions or data are wrong.

Students can reproduce the two-dimensional example with fractions, then perturb one diagonal entry. They should plot Euclidean error, A-norm error and residual norm because these quantities need not fall at identical rates.

A preconditioner changes coordinates so that the transformed spectrum is more favourable. Preconditioned CG needs a symmetric positive definite preconditioner applied consistently with the algorithm.

For parents and students, the transferable lesson is to choose each new direction so it contributes fresh information under the problem’s own geometry. Good directions reduce repeated work.

A responsible report gives matrix symmetry and positive-definiteness evidence, dimensions, sparsity, starting vector, preconditioner, matrix-vector precision, stopping tolerance, iteration count, final residual and relevant error estimate.

---

Frequently asked questions

What systems suit textbook CG?

Real symmetric positive definite systems, with analogous Hermitian conditions in complex arithmetic.

What is a Krylov subspace?

The span of a residual and successive matrix powers applied to it.

Why are directions conjugate?

They are orthogonal under the A-inner product.

Does CG always finish in n computer steps?

Finite termination is an exact-arithmetic result; rounding changes practice.

Why use preconditioning?

To improve spectral geometry and reduce iteration work.

What must be reported?

Matrix checks, size, sparsity, start, preconditioner, tolerance, iterations, precision and residual.

---

Primary source and fact-check note

Magnus R. Hestenes and Eduard Stiefel, “Methods of Conjugate Gradients for Solving Linear Systems,” Journal of Research of the National Bureau of Standards 49, 1952. Definitions and core claims in this article were checked against this primary publication. Calculations shown here were independently recomputed. Examples are educational illustrations; they are not reported industrial performance results.

Useful next reading

• Incomplete Cholesky preconditioning
• Randomized Kaczmarz
• Randomized least squares
• How Mathematics Works
• Study and learning methods

Keep the options open. Mathematics education supports clearer questions, transferable problem-solving skills and informed choices across science, engineering, computing, AI, statistics, design and many other careers. It does not guarantee intelligence, income, admission or employment; those outcomes depend on far more than one subject or model.

Method audit: assumptions, geometry and numerical evidence

Matrix audit

Verify symmetry and positive definiteness.

Recurrence audit

Check alpha, beta, residual and conjugacy.

Spectrum audit

Estimate conditioning and clusters.

Residual audit

Evaluate the original system at the end.

Mechanism workshop: calculate, challenge and transfer

Manual reconstruction

Build the smallest example for Krylov search directions. Label every vector, matrix, probability, unit and assumption.

Assumption map

Place convexity, unbiasedness, positive definiteness or sparsity conditions beside the step they permit.

Counterexample

Remove one condition and locate the first conclusion that fails.

Sensitivity

Change a coordinate constant, learning rate, eigenvalue or drop rule one at a time.

Independent verification

Recompute gradients, residuals, factors and spectra by a second route.

Simulation

Repeat random samples or coordinate choices and separate observed frequency from proof.

Engineering transfer

Count memory traffic, sparse operations, setup work and stopping checks.

AI transfer

Explain an optimization use without promising generalisation, fairness or safety.

Parent explanation

Describe local updates and structural approximations in plain language.

Limit statement

Write one supported claim, one overclaim and one repaired conclusion.

Evidence notebook: reconstruct every step

Evidence notebook 1: System

Step 1 isolates system. Set A=diag(1,4), b=(1,4). The checked result is: Solution is (1,1). Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: A is SPD. Record system. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 2: Start

Step 2 isolates start. Use x0=(0,0). The checked result is: r0=p0=(1,4). Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Compute b-Ax. Record vectors. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 3: First numerator

Step 3 isolates first numerator. Compute r0 dot r0. The checked result is: It is 17. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Use Euclidean dot. Record 17. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 4: First denominator

Step 4 isolates first denominator. Compute p0 dot A p0. The checked result is: It is 65. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Multiply A first. Record 65. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 5: Alpha zero

Step 5 isolates alpha zero. Divide numerator by denominator. The checked result is: alpha0=17/65. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Keep fraction. Record alpha. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 6: First iterate

Step 6 isolates first iterate. Add alpha0 p0. The checked result is: x1=(17/65,68/65). Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Check both entries. Record x1. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 7: Residual

Step 7 isolates residual. Subtract alpha0 A p0. The checked result is: r1=(48/65,-12/65). Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Check orthogonality to r0. Record r1. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 8: Beta

Step 8 isolates beta. Divide new residual norm squared by old. The checked result is: beta0=144/4225. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Simplify carefully. Record beta. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 9: New direction

Step 9 isolates new direction. Set p1=r1+beta0 p0. The checked result is: Directions are A-conjugate. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Verify p0^T A p1=0. Record p1. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 10: Second alpha

Step 10 isolates second alpha. Apply the same quotient. The checked result is: alpha1=65/68. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Use exact values. Record alpha. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 11: Second iterate

Step 11 isolates second iterate. Add alpha1 p1. The checked result is: x2=(1,1). Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Exact arithmetic. Record x2. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 12: Residual check

Step 12 isolates residual check. Compute b-Ax2. The checked result is: It is zero. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Floating point may show roundoff. Record residual. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 13: Conditioning

Step 13 isolates conditioning. Use eigenvalues 1 and 4. The checked result is: Condition number is 4. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: State norm. Record kappa. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Evidence notebook 14: Conclusion

Step 14 isolates conclusion. State SPD,preconditioner,tolerance and residual. The checked result is: Two dimensions finish in two exact steps. Preserve objective definitions, dimensions, probabilities, scaling, sparsity, matrix properties and units beside every number. The safeguard is: Do not promise finite precision termination. Write conclusion. Change one input while holding the others fixed, recalculate the update, residual, objective gap, factor reconstruction or spectrum, and explain whether the difference comes from sampling, curvature, conditioning, dropping, rounding or a changed target. Ask a second reader to reproduce the calculation. Finish with the narrow conclusion and the evidence still missing.

Failure cases and responsible recovery

Nonsymmetric use

Textbook CG assumptions fail. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

Indefinite use

The A-inner product is invalid. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

n-step promise

Roundoff breaks exact termination. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

Residual-equals-error

Conditioning links them. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

No preconditioner record

Transformed geometry matters. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

Iteration-only report

Accuracy and cost are missing. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

Dense factor claim

CG mainly uses matrix-vector products. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

Model validation

A solved system can encode a bad model. Build a small counterexample, restore the missing condition and state the evidence before calculating again.

Transfer checks: from a worked example to trustworthy use

Definition check

Explain conjugate directions without relying on software names. Identify the mathematical object, the update and the quantity the method is trying to improve. Then compare the explanation with the displayed formula and repair any word that claims more than the formula proves.

Units check

Attach units to inputs, parameters, gradients, residuals and tolerances. Rescale one variable and repeat the calculation. State which numbers change because the problem changed and which change only because the numerical representation changed.

Baseline check

Compare the method with a simple full update, direct solve or unpreconditioned iteration on the same small example. Use the same starting point, stopping rule and accuracy measure so the comparison answers a real question.

Cost check

Count matrix-vector products, partial derivatives, sampled examples, triangular solves, memory reads and stored nonzeros. Report setup separately from repeated application and distinguish arithmetic counts from elapsed time.

Precision check

Repeat the worked arithmetic after rounding intermediate values. Measure the effect on objective, residual, conjugacy, factor reconstruction or spectrum, and explain why exact-arithmetic theorems need numerical safeguards on computers.

Stopping check

Write the actual condition that ends the algorithm. Test it on a deliberately misleading state where one local quantity looks small but the global objective, residual or validation evidence remains poor.

Reproducibility check

Record data order, coordinate or sample seed, matrix ordering, initialization, parameter schedule, software precision and all transformations. Another reader should be able to reconstruct both the intended mathematics and the realised path.

Communication check

Write a student explanation, a parent explanation and a technical report sentence. Keep the mathematical conclusion identical while changing vocabulary. Each version should name the main limit and avoid guaranteed performance claims.

Boundary check

Construct one input at the edge of the assumptions: a nearly zero coordinate constant, a highly variable sampled gradient, a nearly singular positive definite matrix or a marginal incomplete pivot. Do not run blindly. Predict which calculation becomes sensitive, choose a safeguard and record how the conclusion narrows.

Decision check

Turn the analysis into a practical choice. State when the method is suitable, when a simpler baseline is sufficient, what evidence would make you change method, and which result must be reviewed by a teacher, engineer or domain expert before real-world use.