Intuition The ONE core ideaTo solve a big system A x = b guess an answer, then repeatedly clean it up — each cleanup step is cheap, and if the matrix is "nice" the guess crawls toward the true answer. Everything in the parent topic is just spelling out how to clean up and when the cleaning is guaranteed to work.
This page assumes nothing . If a smart 12-year-old has never seen a matrix, a vector, or the Greek letter ρ
x vector is just a list of numbers stacked in a column . We write it bold: x x = x 1 x 2 x 3 . x i i i
A matrix is a rectangle of numbers arranged in rows and columns. We name entries a ij row i j . Row first, column second — always.
Intuition Why a grid at all?A system of linear equations like
4 x + y = 6 , x + 3 y = 7 coefficients (the 4 , 1 , 1 , 3 unknowns in one column, all its right-hand-side numbers in another column. Packing them into A x = b
The multiplication rule A x = b row i A x b i Look at figure s01: the highlighted row times the column produces one number of b
The parent note writes A = D − L − U
Definition Diagonal, lower, upper pieces
The diagonal entries are a 11 , a 22 , a 33 , … D
The strictly lower part = entries below the diagonal. The parent stores their negatives in L − L
The strictly upper part = entries above the diagonal, negatives stored in U A = D − L − U
Intuition WHY split it this way?Diagonal-only matrices are absurdly easy to "undo" (divide each row by its own number). Lower-triangular ones are easy too (solve top row first, feed it down). The whole trick of iteration is to keep the easy part on the left and shove the awkward part to the right. Figure s02 colours the three regions so you can see there is no overlap: every entry of A
Common mistake Sign confusion inL U Why it feels right: you'd expect L be the lower entries. The flaw: the parent's convention stores their negatives , so A = D − L − U Fix: whenever you read L − L
A x = b A b find the list x that makes the multiplication land exactly on b x true solution , written x ∗
Intuition Does a true answer even exist (and is it unique)?Everything below chases a single target x ∗ A x = b exactly one solution precisely when A invertible (also called non-singular): its determinant is nonzero, no row is a combination of the others. Then x ∗ = A − 1 b A We assume A
The classic exact recipe is Gaussian Elimination — cancel variables row by row until you can read the answer off. It always works but costs about 3 2 n 3 n × n n = 1 0 6 Finite Difference Methods for PDEs ) that is ∼ 1 0 17 why iteration exists.
Intuition Sparse = mostly zeroGrids from real problems are usually sparse : almost every entry is 0 A x the number of nonzeros — near O ( n ) O ( n 2 ) A x
x ( k ) counter, not a power . x ( 0 ) x ( 1 ) x ( k ) k hope x ( k ) x ∗ k
x ( k ) x k Why it feels right: superscripts usually mean powers. The flaw: the parentheses flag it as a step-number. Fix: parentheses ⇒ iteration count; no parentheses (like λ k
e ( k ) error at step k e ( k ) = x ( k ) − x ∗ .
∥ ⋅ ∥ norm ∥ e ∥ length of the arrow. The everyday choice is
∥ e ∥ = e 1 2 + e 2 2 + ⋯ + e n 2 , e ( k ) → 0 means the single number ∥ e ( k ) ∥ 0 ε
Figure s03 shows a chain of guesses spiralling toward x ∗ ∥ e ( k ) ∥ entire goal — this whole subject is the study of when it happens and how fast.
A = M − N cut A and name them M N A = M − N M easy to invert (diagonal, or lower-triangular) and dump everything left over into N
Jacobi picks M = D N = L + U Gauss–Seidel picks M = D − L N = U M − N = D − ( L + U ) = A
M − 1 inverse of a matrix M undoes it: M − 1 M = I I identity (ones on the diagonal, zeros elsewhere — the "do-nothing" grid). M − 1 M chose M a ii = 0
T M x ∗ = N x ∗ + b M x ( k + 1 ) = N x ( k ) + b b M e ( k + 1 ) = N e ( k ) e ( k + 1 ) = M − 1 N e ( k ) = T e ( k ) ⟹ e ( k ) = T k e ( 0 ) . T k Fixed-Point Iteration in matrix clothing. Whether the error dies is entirely a question about powers of T — which the next section cracks open.
λ v T stretches or shrinks them without turning: T v = λ v λ eigenvalue ; v eigenvector . Along such a direction, applying T k λ k
Intuition Why eigenvalues decide everythingBreak the starting error into eigenvector directions. Along each, one cleanup multiplies by λ ∣ λ ∣ < 1 ∣ λ ∣ > 1 ∣ λ ∣ = 0.5 ∣ λ ∣ = 1.4 worst direction rules the fate of the whole error.
Definition Spectral radiusρ ( T ) ρ ( T ) = max i ∣ λ i ∣ largest absolute eigenvalue — the "worst-case" stretch. See Spectral Radius .
Definition Strictly diagonally dominant (SDD)Row i all the others in that row combined :
∣ a ii ∣ > ∑ j = i ∣ a ij ∣. every row passes, A sufficient (guaranteed-to-work) but not necessary stamp of convergence — computing ρ
∑ j = i ∑ ∣ a ij ∣ i except the diagonal one." The big Greek Σ
Read the map top-to-bottom: each box is a concept this page built, and each arrow means "you need the box above before the box below makes sense." We start from raw vectors and matrices , notice that solving A x = b iterate — which forces us to split A = M − N T D , L , U
Solve Ax equals b, A invertible
Gaussian Elimination is costly
Iterate instead: sequence x superscript k
Norm measures error length
Splitting A equals M minus N
Iteration matrix T equals M inverse N
Error e superscript k equals T to the k
Convergence rho less than 1
Diagonal dominance quick test
What does a ij The entry in row i j row first, column second .
Is the k x ( k ) No — the parentheses make it a step counter ; x ( 0 )
Write the error at step k e ( k ) = x ( k ) − x ∗
What is a norm ∥ e ∥ The length of the vector,
e 1 2 + ⋯ + e n 2 ; "goes to zero" means this single number shrinks below any tolerance.
When does A x = b When A x ∗ = A − 1 b
In the split A = M − N M , N Jacobi: M = D N = L + U M = D − L N = U M
Derive the iteration from A = M − N ( M − N ) x = b ⇒ M x = N x + b ⇒ M x ( k + 1 ) = N x ( k ) + b ⇒ x ( k + 1 ) = M − 1 N x ( k ) + M − 1 b
Why must M The step multiplies by M − 1 M a ii = 0
What is M − 1 M − 1 M It undoes M M − 1 M = I
In A = D − L − U − L negatives of the below-diagonal entries in L
Define an eigenvalue λ T A stretch factor for a special direction v T v = λ v T k λ k
What is ρ ( T ) The spectral radius — the largest absolute eigenvalue , the worst-case stretch.
Exact necessary-and-sufficient convergence condition? ρ ( T ) < 1
What does strictly diagonal dominant mean, and is it necessary? ∣ a ii ∣ > ∑ j = i ∣ a ij ∣ sufficient but not necessary .
Why do we iterate instead of using Gaussian elimination on huge sparse systems? Elimination costs ∼ 3 2 n 3 ∼ O ( n )