Systems of linear equations · Lecture 14

Iterative Methods: Jacobi, Gauss–Seidel and SOR

When the matrix is huge and mostly zeros, stop eliminating and start iterating: Jacobi and Gauss–Seidel as fixed-point iteration with matrices, diagonal dominance, eigenvalues and the spectral radius, and over-relaxation (SOR).

Md Mahbub E Noor · Assistant Professor
CSE-3107 Numerical Methods · B.Sc. 3rd Year 1st Semester
Department of CSE, University of Barishal

Why this lecture

The problem: a plate with a million grid points

The plate from Lecture 12, now on a fine grid so that the temperature map is smooth.

A 100 × 100 grid: 10 000 unknowns; the full matrix has $10^8$ entries (800 MB) but only 5 per row are nonzero: 99.95% zeros
A 1000 × 1000 grid: $10^6$ unknowns; dense elimination needs 8 TB and about 21 years
Yet each equation is tiny: "each temperature is the average of its four neighbours"
Idea: guess all temperatures, then keep replacing each one by the average of its neighbours

One equation per grid point

T_{i,j} = \tfrac14\big(T_{i-1,j} + T_{i+1,j} + T_{i,j-1} + T_{i,j+1}\big)

The question

Does repeated averaging converge to the solution? How fast? Can we make it faster?

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

2 / 25

Today's goals

Derive Jacobi and Gauss–Seidel as fixed-point iteration $\mathbf{x} = T\mathbf{x} + \mathbf{c}$
Carry out both by hand and present the iteration table
Test convergence with diagonal dominance, and explain it with eigenvalues and the spectral radius $\rho(T)$
Speed up Gauss–Seidel with SOR and choose the relaxation factor $\omega$
Decide between direct and iterative solvers

Last time

LU, Cholesky, Thomas: exact after a fixed number of steps, but fill-in and $n^3$ for big 2-D problems.

Today

Guess, improve, repeat: the matrix version of Lecture 8.

Systems of linear equations · you are here

L11 · Linear Systems, Cramer's Rule and the Inverse→L12 · Gaussian and Gauss–Jordan Elimination→L13 · LU, Cholesky and Tridiagonal Systems→L14 · Iterative Methods

Builds on: L8, L12

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

3 / 25

Start here

The idea in one picture

A point on a heated plate, surrounded by four neighbours.We do not know its temperature yet: start with any guess.Rule: a point is the average of its neighbours.So replace the guess by that average.One "sweep" applies the rule at every point of the grid.Sweep again and again. The numbers settle to the solution of Ax = b.

In plain words

Guess the whole answer, then improve each unknown from its own equation
Sweep through all unknowns again and again
No elimination and no big matrix in memory: ideal for huge problems

New words today

sweep: one pass over all the unknowns
Jacobi: uses only the old values
Gauss–Seidel: uses new values at once
diagonally dominant: large diagonal entries
eigenvalue λ: a number with Ax = λx
spectral radius ρ: largest |λ|; need ρ < 1

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

4 / 25

The idea: solve each equation for its own unknown

Jacobi: every update uses only the old values

x_i^{(k+1)} = \frac{1}{a_{ii}}\Big(b_i - \sum_{j \ne i} a_{ij}\,x_j^{(k)}\Big), \qquad i = 1, \dots, n

Matrix form, with A = D + L + U (diagonal, strictly lower, strictly upper)

\mathbf{x}^{(k+1)} = \underbrace{-D^{-1}(L + U)}_{T_J}\,\mathbf{x}^{(k)} + D^{-1}\mathbf{b}

Exactly fixed-point iteration $\mathbf{x} = g(\mathbf{x})$ from Lecture 8, with vectors
Needs every $a_{ii} \ne 0$
One sweep costs about 2 × (number of nonzeros): the zeros are never touched
The order of the equations matters: each one is solved for its diagonal unknown

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

5 / 25

The method, step by step

Jacobi's method, step by step

Check (or arrange) that the system is diagonally dominant
Rewrite equation $i$ as $x_i = (b_i - \sum_{j\ne i} a_{ij}x_j)/a_{ii}$
Choose a start, usually $\mathbf{x}^{(0)} = \mathbf{0}$
Compute all new $x_i$ from the old vector
Stop when $\|\mathbf{x}^{(k+1)} - \mathbf{x}^{(k)}\|_\infty < \varepsilon$ ; otherwise repeat step 4

Pseudocode

input A, b, x (start), tol, N
repeat up to N times:
    for i = 1 … n:
        s ← b[i] − Σ_{j≠i} a[i][j]·x[j]
        x_new[i] ← s / a[i][i]
    if max |x_new − x| < tol:
        return x_new
    x ← x_new
stop: no convergence

Two vectors: old and new. Every $x_i$ can be updated at the same time, so Jacobi runs well in parallel (GPUs).

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

6 / 25

Problem 1: Jacobi iteration

Solve

4x - y + z = 7

,

\;4x - 8y + z = -21

,

\;-2x + y + 5z = 15

from

(0, 0, 0)

. Iterate

x = \frac{7 + y - z}{4}

,

\;y = \frac{21 + 4x + z}{8}

,

\;z = \frac{15 + 2x - y}{5}

.

$k$	$x^{(k)}$	$y^{(k)}$	$z^{(k)}$	largest change
1	1.750000	2.625000	3.000000	3.00
2	1.656250	3.875000	3.175000	1.25
3	1.925000	3.850000	2.887500	0.288
4	1.990625	3.948438	3.000000	0.112
5	1.987109	3.995313	3.006563	0.0469
6	1.997188	3.994375	2.995781	0.0108
7	1.999648	3.998066	3.000000	0.00422
8	1.999517	3.999824	3.000246	0.00176

Diagonally dominant, so it converges to $(2, 4, 3)$ : 11 iterations for a change below $10^{-4}$ , 15 for $10^{-6}$ . Every row uses only the row above it.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

7 / 25

The method, step by step

Gauss–Seidel, step by step

Use each new value as soon as it is computed: $\;x_i^{(k+1)} = \dfrac{1}{a_{ii}}\Big(b_i - \sum_{j<i} a_{ij}x_j^{(k+1)} - \sum_{j>i} a_{ij}x_j^{(k)}\Big)$

Arrange the system so that it is diagonally dominant
Start with $\mathbf{x}^{(0)}$ (often $\mathbf{0}$ )
Update $x_1$ ; then $x_2$ using the new $x_1$ ; then $x_3$ using the new $x_1, x_2$ ; …
Stop when the largest change in a sweep is below $\varepsilon$
Matrix form: $(D + L)\mathbf{x}^{(k+1)} = \mathbf{b} - U\mathbf{x}^{(k)}$

Pseudocode

input A, b, x (start), tol, N
repeat up to N times:
    change ← 0
    for i = 1 … n:
        s ← b[i] − Σ_{j≠i} a[i][j]·x[j]
        new ← s / a[i][i]
        change ← max(change, |new − x[i]|)
        x[i] ← new        # overwrite now
    if change < tol: return x
stop: no convergence

One vector, overwritten in place: less memory and usually about twice as fast as Jacobi.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

8 / 25

Problem 2: the same system by Gauss–Seidel

Same equations and start. Now each formula uses the newest values:

y

uses the new

x

;

z

uses the new

x

and

y

.

$k$	$x^{(k)}$	$y^{(k)}$	$z^{(k)}$	largest change
1	1.750000	3.500000	3.000000	3.50
2	1.875000	3.937500	2.962500	0.438
3	1.993750	3.992188	2.999063	0.119
4	1.998281	3.999023	2.999508	0.00683
5	1.999879	3.999878	2.999976	0.00160
6	1.999975	3.999985	2.999993	0.000107
7	1.999998	3.999998	3.000000	0.0000231

7 iterations for $10^{-4}$ (Jacobi: 11) and 9 for $10^{-6}$ (Jacobi: 15). Row 1: $x = 7/4$ ; $y = (21 + 4(1.75) + 0)/8 = 3.5$ ; $z = (15 + 2(1.75) - 3.5)/5 = 3$ .

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

9 / 25

Explore: Jacobi and Gauss–Seidel in pictures

Two equations, two lines; the solution is where they cross
Gauss–Seidel: move horizontally to line 1, then vertically to line 2: a staircase
Jacobi: both moves from the old point at once
Swap the rows: the same lines, but the iteration runs away

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

10 / 25

When does it converge?

Strict diagonal dominance in every row ⇒ Jacobi and Gauss–Seidel converge from any start

|a_{ii}| > \sum_{j \ne i} |a_{ij}|, \qquad i = 1, \dots, n

The real reason: the error is multiplied by T at every step

\mathbf{e}^{(k+1)} = T\,\mathbf{e}^{(k)} \;\Rightarrow\; \mathbf{e}^{(k)} = T^k\mathbf{e}^{(0)} \to \mathbf{0} \iff \rho(T) < 1

$\rho(T) = \max|\lambda_i(T)|$ , the spectral radius: the matrix version of $|g'(r)|$ in Lecture 8
Each iteration multiplies the error by about $\rho$ : about $d/(-\log_{10}\rho)$ iterations for $d$ digits
Diagonal dominance is sufficient, not necessary
For many matrices (including the plate): $\rho(T_{GS}) = \rho(T_J)^2$ , so Gauss–Seidel needs half as many iterations

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

11 / 25

Recap: eigenvalues and the spectral radius

Eigenvalue λ and eigenvector v

T\mathbf{v} = \lambda\mathbf{v}, \;\mathbf{v} \ne \mathbf{0} \quad\Longleftrightarrow\quad \det(T - \lambda I) = 0

2×2: the characteristic equation

\lambda^2 - (\operatorname{tr} T)\,\lambda + \det T = 0, \qquad \rho(T) = \max(|\lambda_1|, |\lambda_2|)

Along an eigenvector, $T^k\mathbf{v} = \lambda^k\mathbf{v}$ : it shrinks if $|\lambda| < 1$ , grows if $|\lambda| > 1$
Any error is a mix of eigenvectors, so the largest $|\lambda|$ wins in the end
$\rho < 1$ : the iteration is a contraction, like $|g'| < 1$
Eigenvalues return in ODE stability (Lecture 22) and in optimisation (Lecture 25)

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

12 / 25

Problem 3: predict the speed from ρ

For

4x - y = 3

,

\;-2x + 5y = 3

(solution

(1, 1)

), find

\rho(T_J)

and

\rho(T_{GS})

.

1

T_J = -D^{-1}(L + U) = \begin{pmatrix} 0 & 1/4 \\ 2/5 & 0\end{pmatrix}

:

\;\lambda^2 - 0\cdot\lambda - \tfrac{1}{10} = 0

, so

\lambda = \pm 0.3162

and

\rho(T_J) = 0.3162

2

Gauss–Seidel:

x_{new} = (3 + y)/4

, then

y_{new} = (3 + 2x_{new})/5 = \ldots + \tfrac{1}{10}y

, so

T_{GS} = \begin{pmatrix} 0 & 1/4 \\ 0 & 1/10\end{pmatrix}

with eigenvalues

0

and

0.1

3

\rho(T_{GS}) = 0.1 = \rho(T_J)^2

: each Gauss–Seidel step gains one digit; each Jacobi step half a digit

4

Prediction for 6 digits: Jacobi about 12 steps, Gauss–Seidel about 6. Observed (change

< 10^{-6}

): 13 and 8

Both converge (ρ < 1). Gauss–Seidel is twice as fast, as the spectral radii predict.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

13 / 25

Over-relaxation (SOR): push past the Gauss–Seidel value

SOR with relaxation factor ω; x̃ᵢ is the Gauss–Seidel value

x_i^{(k+1)} = (1 - \omega)\,x_i^{(k)} + \omega\,\tilde{x}_i

Best ω for the N × N plate

\omega_{opt} = \frac{2}{1 + \sin\big(\pi/(N+1)\big)}, \qquad \rho(T_{\omega_{opt}}) = \omega_{opt} - 1

$\omega = 1$ : Gauss–Seidel. $1 < \omega < 2$ : over-relaxation (go further in the same direction)
Converges only for $0 < \omega < 2$ (for SPD matrices: for all of them)
Same cost per sweep as Gauss–Seidel: one extra multiply per unknown
Plate, 10 × 10 grid: Gauss–Seidel 132 sweeps, SOR with $\omega = 1.56$ : 31 sweeps

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

14 / 25

Explore: the heat plate by Jacobi, Gauss–Seidel and SOR

Each curve: largest change per sweep (log scale)
Gauss–Seidel ≈ twice as fast as Jacobi; SOR with a good ω is much faster again
Increase N: Jacobi and Gauss–Seidel slow down sharply ( $\rho \to 1$ )
Press use best ω and compare

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

15 / 25

Classical vs numerical

Same plate, two approaches

Exact after fixed steps

Direct (Gaussian elimination)

4 unknowns: 62 operations, exact
$T = (43.75, 56.25, 18.75, 31.25)$
Stores and fills the whole matrix

vs

Improves a guess

Iterative (Gauss–Seidel)

4 unknowns: 11 sweeps to a change below $10^{-4}$
$T = (43.75, 56.25, 18.75, 31.25)$ to 4 decimals
Stores only the grid of temperatures

When the direct approach cannot work

A 1000 × 1000 grid: $10^6$ unknowns

Dense elimination: 8 TB of memory and $6.7\times10^{17}$ operations (21 years at $10^9$ per second). SOR with the best ω: about 2200 sweeps of $5\times10^6$ operations, about 11 seconds and 8 MB. Jacobi would need about 2.8 million sweeps (4 hours): the method and ω matter.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

16 / 25

Jacobi and Gauss–Seidel in Python and C

Same system as Problems 1 and 2
Jacobi keeps an old and a new vector
Gauss–Seidel overwrites in place
Both stop when the largest change is below $10^{-6}$

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

17 / 25

When iteration does not work

Limitations shown failing

Not diagonally dominant: the same system with rows swapped has $\rho = 3.16$ ; the iterates explode
Fix: reorder the equations so the largest coefficient of each row is on the diagonal
Slow when $\rho$ is close to 1: nearly parallel lines, fine grids (Jacobi needs millions of sweeps)
Accuracy only to the tolerance, and a small change is not always a small error when $\rho \approx 1$

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

18 / 25

Practice

Practice problem

Problem 4"Solve by the Gauss–Seidel method, correct to three decimal places:

x + y + 54z = 110

,

\;27x + 6y - z = 85

,

\;6x + 15y + 2z = 72

."

How to write a complete answer

As written the system is not diagonally dominant: reorder to $27x + 6y - z = 85$ , $6x + 15y + 2z = 72$ , $x + y + 54z = 110$ and say why
Write the three update formulas: $x = (85 - 6y + z)/27$ , $y = (72 - 6x - 2z)/15$ , $z = (110 - x - y)/54$
Table from $(0, 0, 0)$ : $(3.1481, 3.5407, 1.9132)$ , $(2.4322, 3.5720, 1.9258)$ , $(2.4257, 3.5729, 1.9260)$ , $(2.4255, 3.5730, 1.9260)$
Stop when two iterations agree to 3 decimals: $x = 2.426$ , $y = 3.573$ , $z = 1.926$

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

19 / 25

When to use it

Jacobi, Gauss–Seidel and SOR: method profile

Best case

Huge sparse systems from grids: memory and work proportional to the number of nonzeros
Diagonally dominant or SPD matrices: guaranteed convergence
A good starting guess (the previous time step): few sweeps needed

Worst case

Not diagonally dominant and $\rho(T) \ge 1$ : divergence
$\rho$ close to 1 (fine grids): Jacobi and Gauss–Seidel crawl
Small dense systems: elimination is faster and exact

Best suited for

Heat, flow and electrostatics on grids (Laplace and Poisson equations)
Jacobi: parallel hardware (GPUs); Gauss–Seidel: sequential code, less memory
Smoothers inside multigrid; PageRank-type ranking iterations

Avoid when

Dense matrices with $n$ in the thousands (use LU)
Problems needing many digits from a slowly converging iteration
Indefinite or non-dominant matrices (use Krylov methods such as GMRES)

Rule of thumb: sparse and huge → iterate (SOR or better); dense or small → factor. Always check dominance or $\rho < 1$ first.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

20 / 25

Comparative analysis: iterative and direct solvers

Method	Cost per sweep	Converges when	Plate $10\times10$	Plate $1000\times1000$	Parallel?
Jacobi	≈ 2·nonzeros	diag. dominant, $\rho(T_J) < 1$	245 sweeps	≈ 4 hours	yes
Gauss–Seidel	≈ 2·nonzeros	diag. dominant or SPD	132 sweeps	≈ 2 hours	partly (red–black)
SOR, best ω	≈ 2·nonzeros + n	SPD and $0 < \omega < 2$	31 sweeps	≈ 11 s	partly
Gaussian elimination (dense)	$\tfrac23 n^3$ once	nonsingular	0.7 ms	21 years, 8 TB	yes (blocks)
Banded LU (bandwidth $N$ )	≈ $2nN^2$ once	nonsingular	0.02 ms	≈ 33 min, 8 GB	partly

Times at $10^9$ operations per second; sweep counts from the plate tool (edges 100, 50, 0, 0; change below $10^{-4}$ ); the $1000\times1000$ estimates use $\rho$ and a $10^{-6}$ error reduction.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

21 / 25

Roadmap

End of Module 3: where linear systems appear next

We can now solve linear systems of any size and shape. They return all through the course:

What it does well (keep this)

Cramer and the inverse for 2×2 and 3×3 by hand
Elimination with pivoting, LU, Cholesky, Thomas
Jacobi, Gauss–Seidel, SOR for huge sparse systems
Norms, condition number, spectral radius

LimitationHow it is overcomeWhere

Splines need a tridiagonal solve

→

Thomas algorithm

Lecture 18 →

Implicit ODE methods solve a system each step; stability is about eigenvalues

→

LU reuse;

\rho

and

|\lambda h|

Lecture 22 →

Fitting a model to data: more equations than unknowns

→

Least squares: normal equations (Cholesky)

Lecture 23 →

Training ML models: minimise a loss

→

Gradient descent: an iterative method like these

Lecture 25 →

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

22 / 25

Applications

Where this method runs in the real world

Click a card to see an iterative linear solver inside a real system.

iteration	page 1	page 2	page 3	page 4
0	0.25	0.25	0.25	0.25
1	0.2500	0.1438	0.5688	0.0375
2	0.5209	0.1438	0.2978	0.0375
3	0.2906	0.2589	0.4130	0.0375
28	0.3725	0.1958	0.3941	0.0375

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

23 / 25

Checkpoint

Checkpoint · think, then discuss with your neighbourOne Gauss–Seidel step for

10x + y = 12

,

\;x + 10y = 21

from

(0, 0)

. What is

y^{(1)}

?

A

2.1

B

1.98

C

1.2

D

2.0

B.

x^{(1)} = 12/10 = 1.2

; then

y^{(1)} = (21 - 1.2)/10 = 1.98

(Gauss–Seidel uses the new

x

). Jacobi would give

y^{(1)} = 2.1

. The solution is

(1, 2)

.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

24 / 25

Summary

Key points

Jacobi: solve row $i$ for $x_i$ using old values; Gauss–Seidel: use new values at once
Both are fixed-point iterations $\mathbf{x} = T\mathbf{x} + \mathbf{c}$ ; they converge iff $\rho(T) < 1$ (diagonal dominance is enough)
Gauss–Seidel is usually about twice as fast; SOR with a good $\omega$ much faster
Use iteration for huge sparse systems; factorisation for small or dense ones

Opening problem: solved

The 4-point plate: Jacobi reaches $(43.75, 56.25, 18.75, 31.25)$ in 19 sweeps, Gauss–Seidel in 11 (change below $10^{-4}$ ). The million-point plate: SOR with the best ω in about 2200 sweeps, roughly 11 seconds, where elimination would need 8 TB.

Homework

Solve $10x + y + z = 12$ , $\;x + 10y + z = 12$ , $\;x + y + 10z = 12$ by Jacobi and by Gauss–Seidel to 4 decimals. Compare the number of iterations.
Rearrange $x + 8y - 3z = 6$ , $\;9x + y + z = 11$ , $\;2x - y + 7z = 8$ to be diagonally dominant, then do three Gauss–Seidel iterations.
Find $\rho(T_J)$ and $\rho(T_{GS})$ for $\begin{pmatrix} 5 & 2 \\ 3 & 6\end{pmatrix}$ . Predict how many iterations each needs for 6 digits.
With the plate tool, find the best ω for $N = 20$ by experiment and compare it with the formula.

Next lecture

Module 4: finite differences and interpolation. The operators $\Delta$ , $\nabla$ , $\delta$ , $E$ and how they generate every interpolation formula.

Md Mahbub E Noor

Lecture 14: Jacobi, Gauss–Seidel and SOR

University of Barishal

25 / 25

Iterative Methods: Jacobi, Gauss–Seidel and SOR

The problem: a plate with a million grid points

Today's goals

The idea in one picture

The idea: solve each equation for its own unknown

Jacobi's method, step by step

Problem 1: Jacobi iteration

Gauss–Seidel, step by step

Problem 2: the same system by Gauss–Seidel

Explore: Jacobi and Gauss–Seidel in pictures

When does it converge?

Recap: eigenvalues and the spectral radius

Problem 3: predict the speed from ρ

Over-relaxation (SOR): push past the Gauss–Seidel value

Explore: the heat plate by Jacobi, Gauss–Seidel and SOR

Same plate, two approaches

Direct (Gaussian elimination)

Iterative (Gauss–Seidel)

A 1000 × 1000 grid: $10^6$ unknowns

Jacobi and Gauss–Seidel in Python and C

Limitations shown failing

Practice problem

Jacobi, Gauss–Seidel and SOR: method profile

Comparative analysis: iterative and direct solvers

End of Module 3: where linear systems appear next

Where this method runs in the real world

🔎 Google PageRank

⚡ Power systems: Gauss–Seidel load flow

🖼️ Filling a hole in an image

🧠 Gradient descent is an iterative linear solver

Checkpoint

Summary

Iterative Methods: Jacobi, Gauss–Seidel and SOR

The problem: a plate with a million grid points

Today's goals

The idea in one picture

The idea: solve each equation for its own unknown

Jacobi's method, step by step

Problem 1: Jacobi iteration

Gauss–Seidel, step by step

Problem 2: the same system by Gauss–Seidel

Explore: Jacobi and Gauss–Seidel in pictures

When does it converge?

Recap: eigenvalues and the spectral radius

Problem 3: predict the speed from ρ

Over-relaxation (SOR): push past the Gauss–Seidel value

Explore: the heat plate by Jacobi, Gauss–Seidel and SOR

Same plate, two approaches

Direct (Gaussian elimination)

Iterative (Gauss–Seidel)

A 1000 × 1000 grid: 10610^6106 unknowns

Jacobi and Gauss–Seidel in Python and C

Limitations shown failing

Practice problem

Jacobi, Gauss–Seidel and SOR: method profile

Comparative analysis: iterative and direct solvers

End of Module 3: where linear systems appear next

Where this method runs in the real world

🔎 Google PageRank

⚡ Power systems: Gauss–Seidel load flow

🖼️ Filling a hole in an image

🧠 Gradient descent is an iterative linear solver

Checkpoint

Summary

A 1000 × 1000 grid: $10^6$ unknowns