Home / Courses / Numerical Methods / Iterative Methods

Numerical Methods · Module 5 of 10

Iterative Methods and Conditioning

Large sparse systems are solved not by elimination but by repeated improvement. Gauss-Seidel converges when the matrix is diagonally dominant, and the condition number warns when even a perfect solver will struggle.

Readiness check

This module solves systems by iteration. Tick only what you can do closed-notes.

Solve one equation for one unknown.
Recall the approximate relative error and a tolerance.
Compare a diagonal entry with the sum of the others in its row.
Recall how to invert a 2 by 2 matrix.
Recall a matrix norm as a row sum.

0 or 1 weak itemsContinue with this module.

2 weak itemsRevisit Gauss elimination in Module 4.

3 or more weak itemsReview matrices in Mathematics, Module 8.

The core idea

Iterative methods improve a guess until it stops changing. Gauss-Seidel solves each equation for its diagonal unknown and cycles, converging when the matrix is diagonally dominant. The condition number measures how much a system magnifies error.

x_i = (b_i − Σ a_ijx_j)/a_iiconverges if |a_ii| > Σ |a_ij|cond(A) = ‖A‖ ‖A⁻¹‖

For large, sparse systems, the cubic cost of Gauss elimination becomes prohibitive, and iterative methods take over. Each solves equation i for its diagonal unknown, x_i = (b_i − Σ_j≠i a_ijx_j)/a_ii, and sweeps through the equations repeatedly. The Jacobi method uses the previous sweep's values throughout; Gauss-Seidel uses each new value as soon as it is computed, which usually converges faster. Convergence is guaranteed when the matrix is diagonally dominant, each diagonal entry larger in magnitude than the sum of the others in its row. Separately, the condition number cond(A) = ‖A‖ ‖A⁻¹‖ measures how sensitive the solution is to small changes in the data: a large condition number marks an ill-conditioned system whose answer is unreliable no matter how it is solved. Together these ideas govern when iteration works and when any method is trustworthy.

The skill works when: you check diagonal dominance before iterating and the condition number before trusting the answer.

The skill breaks down when: a non-dominant system is iterated and diverges, or an ill-conditioned answer is reported as precise.

The concept. Gauss-Seidel improves every unknown each sweep, and a diagonally dominant matrix makes the approximate error shrink steadily toward the solution.

The skills, taught in order

Five skills build the iterative methods, their convergence condition, and the conditioning of a system.

5.1 The Jacobi and Gauss-Seidel iterations

Both solve equation i for its diagonal unknown and cycle through the system. Jacobi updates all unknowns from the previous sweep; Gauss-Seidel uses each freshly computed value immediately, so it usually converges in fewer sweeps. Each sweep is cheap, ideal for large sparse matrices.

5.2 Diagonal dominance and convergence

Iteration converges when the matrix is diagonally dominant: in every row the magnitude of the diagonal entry exceeds the sum of the magnitudes of the others. This sufficient condition is easy to check and tells you in advance whether the iteration will settle.

Method	Uses	Convergence
Jacobi	all old values	needs diagonal dominance
Gauss-Seidel	newest values at once	usually faster than Jacobi
Direct (Gauss)	elimination	always, but order n³

Iteration trades the guaranteed finish of elimination for cheap sweeps that converge when the matrix is dominant.

5.3 The stopping criterion

Each sweep produces a new estimate; the iteration stops when the approximate relative error of every unknown falls below a tolerance. As with root finding, ε_a signals convergence without knowing the true solution.

5.4 The condition number

The condition number cond(A) = ‖A‖ ‖A⁻¹‖ measures how much a system magnifies relative error from the data to the solution. A value near one is well conditioned; a large value means small input changes cause large solution changes.

5.5 Ill-conditioning

An ill-conditioned matrix is nearly singular: its rows are almost dependent and its determinant is small relative to its entries. The solution then loses significant figures regardless of the method, so the condition number is a warning to reformulate or use higher precision.

Engineering connection: iterative solvers power large CFD and FEM meshes, and the condition number flags a stiffness or coefficient matrix whose results cannot be trusted.

Worked example 1: Gauss-Seidel iteration

Solve 5x + y = 6 and x + 4y = 5 by Gauss-Seidel, starting from x = 0, y = 0. The system is diagonally dominant. Carry out three sweeps.

Figure 1. Each sweep uses the newest values at once. Because the matrix is diagonally dominant, the estimates close quickly on the exact solution (1, 1).

ProblemSolve the system in Figure 1 by Gauss-Seidel for three sweeps.
Given / find5x + y = 6, x + 4y = 5, start x = y = 0. Find x and y after three sweeps.
AssumptionsThe matrix is diagonally dominant (5 > 1 and 4 > 1), so the iteration converges.
Modelx = (6 − y)/5 and y = (5 − x)/4, using the newest values each time.
Equationsx = (6 − y)/5y = (5 − x)/4
SolveSweep 1: x = 6/5 = 1.2, y = (5 − 1.2)/4 = 0.95. Sweep 2: x = (6 − 0.95)/5 = 1.01, y = (5 − 1.01)/4 = 0.9975. Sweep 3: x = (6 − 0.9975)/5 = 1.0005, y = 0.99988.
CheckThe estimates approach (1, 1), which satisfies both equations exactly (5 + 1 = 6, 1 + 4 = 5). The error falls by roughly a factor of twenty each sweep, the dominance ratio.
ConclusionThree sweeps reach four-figure accuracy. Diagonal dominance guaranteed the convergence before the first sweep was run.

Result. After three sweeps, x = 1.0005, y = 0.99988, converging to (1, 1).

Worked example 2: the condition number of a near-singular matrix

Find the condition number of A = [[1, 1], [1, 1.001]] using the row-sum (infinity) norm, and interpret it.

Figure 2. The two rows are nearly identical, so the determinant is tiny and the inverse is enormous. The condition number near four thousand flags an ill-conditioned system.

ProblemFind cond(A) for the matrix in Figure 2 and say what it means.
Given / findA = [[1, 1], [1, 1.001]]. Find ‖A‖, ‖A⁻¹‖, and cond(A).
AssumptionsUse the infinity norm, the largest absolute row sum.
ModelA⁻¹ = (1/det)[[1.001, −1], [−1, 1]] with det = 1.001 − 1 = 0.001; cond = ‖A‖ ‖A⁻¹‖.
Equationsdet A = 0.001‖A‖_∞ = max row sumcond = ‖A‖ ‖A⁻¹‖
Solve‖A‖_∞ = max(2, 2.001) = 2.001. A⁻¹ = 1000·[[1.001, −1], [−1, 1]], so ‖A⁻¹‖_∞ = 1000·max(2.001, 2) = 2001. cond = 2.001 × 2001 ≈ 4004.
CheckThe condition number is about four thousand, far above one, so a relative input change can be magnified roughly four-thousand-fold, costing about three or four significant figures.
ConclusionThe matrix is ill-conditioned: nearly dependent rows make the answer unreliable. The condition number warns of this before any solution is trusted.

Result. cond(A) ≈ 4004: strongly ill-conditioned.

Misconceptions and diagnostics

Mistake	Symptom	Diagnostic question	Correction
Iterating a non-dominant system	Estimates grow without bound	"Is the matrix diagonally dominant?"	Reorder rows for dominance or use a direct method.
Jacobi where Gauss-Seidel fits	Slow convergence	"Am I using the newest values?"	Gauss-Seidel reuses fresh values and converges faster.
Trusting an ill-conditioned answer	Precise-looking but wrong solution	"What is the condition number?"	A large cond(A) means few reliable digits.
No stopping check	Iterating forever or too few sweeps	"Is ε_a below tolerance for all unknowns?"	Stop when every unknown's error is small.

Practice ladder

Level 1 · Direct skill

Is the matrix [[8, 3], [2, 5]] diagonally dominant?

Show answer

Row 1: |8| > |3|. Row 2: |5| > |2|. Yes, it is diagonally dominant, so Gauss-Seidel converges.

Level 2 · Mixed concept

Do one Gauss-Seidel sweep of 8x + 3y = 13, 2x + 5y = 9 from x = y = 0.

Show answer

x = 13/8 = 1.625; y = (9 − 2·1.625)/5 = (9 − 3.25)/5 = 1.15. (Solution is x = 1, y = 1.4.)

Level 3 · Independent problem

Estimate the condition number of [[2, 0], [0, 0.001]] using the infinity norm.

Show answer

‖A‖_∞ = 2. A⁻¹ = [[0.5, 0], [0, 1000]], ‖A⁻¹‖_∞ = 1000. cond = 2 × 1000 = 2000: ill-conditioned from the disparate scales.

Transfer task | Real engineering

A large CFD mesh produces a sparse system. Argue why an iterative solver suits it and what you would check before trusting the result.

What good work looks like

Sparse systems make cheap iterative sweeps far more efficient than dense elimination, and diagonal dominance (often from the discretisation) ensures convergence; before trusting the result, check the residual and the condition number to confirm the answer is well determined.

Working with AI, and proving it yourself

Use AI as an examiner, not a solver

"Check that this matrix is diagonally dominant before I iterate."

"Give me three matrices; I will judge whether each is well conditioned."

"Iterate this system for me." Sweeping it yourself is the skill.

"Is my answer trustworthy?" Computing the condition number is the point.

Portfolio task

Solve a real sparse system by Gauss-Seidel, confirm diagonal dominance first, and report the condition number alongside the solution.

Must include: a dominance check, an iteration with a stopping criterion, and a condition number.

Retrieval and spaced review

Closed notes. Answer out loud, then reveal.

1. How does Gauss-Seidel differ from Jacobi?

It uses each newly computed value immediately, so it usually converges faster.

2. What guarantees convergence?

Diagonal dominance: each diagonal entry exceeds the sum of the others in its row.

3. Define the condition number.

cond(A) = ‖A‖ ‖A⁻¹‖, the magnification of relative error.

4. What does a large condition number mean?

The system is ill-conditioned; the solution loses significant figures.

5. When are iterative methods preferred?

For large, sparse systems where elimination is too costly.

TodayFinish this quiz and Levels 1 and 2 of the ladder.

+1 dayRe-run three Gauss-Seidel sweeps from a blank page.

+3 daysCheck dominance and conditioning for three matrices.

+7 daysTurn from solving systems to fitting data, Module 6.

+30 daysReuse the condition number to vet a large simulation matrix.

Textbook mapping

This module follows Chapra and Canale, Numerical Methods for Engineers, 7th edition. Use these references to read further.

Topic in this module	Where to read more
The Gauss-Seidel method	Chapra & Canale, Chapter 11
Diagonal dominance and convergence	Chapra & Canale, Chapter 11
Matrix condition number	Chapra & Canale, Chapter 10

Chapter numbers refer to the 7th edition. The iterative methods and conditioning are standard, so any recent edition will align closely.