Iterative methods — Jacobi, Gauss-Seidel, convergence

4.8.20 · Maths › Numerical Methods

1. Splitting: sab kuch iske peeche hai

Error recurrence ki derivation (scratch se). Maano $x^{*}$ sahi solution hai, toh $M x^{*} = N x^{*} + b$ . Ise $M x^{(k + 1)} = N x^{(k)} + b$ se subtract karo: $M (x^{(k + 1)} - x^{*}) = N (x^{(k)} - x^{*}) .$ Error define karo $e^{(k)} = x^{(k)} - x^{*}$ . Tab $e^{(k + 1)} = M^{- 1} N e^{(k)} = T e^{(k)} \Rightarrow e^{(k)} = T^{k} e^{(0)} .$ Toh error har step par $T$ se multiply hoti hai. Ye kyun important hai: convergence ( $e^{(k)} \to 0$ ) kisi bhi starting guess ke liye tab hogi jab $T^{k} \to 0$ .

2. Standard split: $A = D - L - U$

Jacobi

Choose karo $M = D$ , $N = L + U$ . Tab $M x^{(k + 1)} = N x^{(k)} + b$ component-wise deta hai: $x_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - \sum_{j \neq = i} a_{ij} x_{j}^{(k)}) .$

Gauss-Seidel

Choose karo $M = D - L$ (lower triangular, forward-solve karna aasaan), $N = U$ : $x_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - \sum_{j < i} a_{ij} x_{j}^{(k + 1)} - \sum_{j > i} a_{ij} x_{j}^{(k)}) .$

3. Convergence — WHY aur WHEN

WHY $ρ < 1$ ? $T = P Λ P^{- 1}$ diagonalize karo (eigenvalues $λ_{i}$ ). Tab $T^{k} = P Λ^{k} P^{- 1}$ aur $Λ^{k} = diag (λ_{i}^{k})$ . Jab $k \to \infty$ , $λ_{i}^{k} \to 0$ saare $i$ ke liye tab hoga jab har $∣ λ_{i} ∣ < 1$ , yaani $ρ (T) < 1$ . Kyunki $e^{(k)} = T^{k} e^{(0)}$ , error bilkul isi condition mein khatam hoti hai.

Worked example Worked example 1 — haath se

$2 \times 2$ system solve karo ${4 x + y = 6 x + 3 y = 7, exact: x = \frac{11}{11} = 1, y = 2.$ Yahan $a_{11} = 4 > 1$ , $a_{22} = 3 > 1$ : SDD ✓, toh dono converge karte hain. Start karo $x^{(0)} = (0, 0)$ se.

Jacobi $x = \frac{6 - y}{4}, y = \frac{7 - x}{3}$ (hamesha purani values):

$k = 1$ : $x = \frac{6 - 0}{4} = 1.5, y = \frac{7 - 0}{3} = 2.333$ . Kyun? dono purane $(0, 0)$ use karte hain.
$k = 2$ : $x = \frac{6 - 2.333}{4} = 0.917, y = \frac{7 - 1.5}{3} = 1.833$ . Kyun? $k = 1$ ki values use karo.
$k = 3$ : $x = \frac{6 - 1.833}{4} = 1.042, y = \frac{7 - 0.917}{3} = 2.028$ . $(1, 2)$ ke paas aa rahe hain.

Gauss-Seidel (naya $x$ andar $y$ mein use karo):

$k = 1$ : $x = \frac{6 - 0}{4} = 1.5$ ; phir $y = \frac{7 - 1.5}{3} = 1.833$ . Ye step kyun? $y$ abhi-compute kiya hua $x = 1.5$ use karta hai, $0$ nahi.
$k = 2$ : $x = \frac{6 - 1.833}{4} = 1.042$ ; $y = \frac{7 - 1.042}{3} = 1.986$ .
$k = 3$ : $x = \frac{6 - 1.986}{4} = 1.004$ ; $y = \frac{7 - 1.004}{3} = 1.999$ . Faster — $(1, 2)$ tak pahunchne mein kam steps.

4. Common mistakes (Steel-manned)

5. Stopping & cost

Flashcards

What is the iteration matrix

T

for a splitting

A = M - N

T = M^{- 1} N

; iteration hai

x^{(k + 1)} = T x^{(k)} + M^{- 1} b

Error recurrence of a stationary iteration?

e^{(k + 1)} = T e^{(k)}

, toh

e^{(k)} = T^{k} e^{(0)}

Exact necessary-and-sufficient condition for convergence from any start?

Spectral radius

ρ (T) < 1

Splitting

M, N

for Jacobi?

M = D, N = L + U

, jisse

T_{J} = D^{- 1} (L + U)

milta hai.

Splitting

M, N

for Gauss-Seidel?

M = D - L, N = U

, jisse

T_{GS} = (D - L)^{- 1} U

milta hai.

Component formula for Jacobi?

x_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - \sum_{j \neq = i} a_{ij} x_{j}^{(k)})

Component formula for Gauss-Seidel?

x_{i}^{(k + 1)} = \frac{1}{a _{ii}} (b_{i} - \sum_{j < i} a_{ij} x_{j}^{(k + 1)} - \sum_{j > i} a_{ij} x_{j}^{(k)})

Key practical difference Jacobi vs Gauss-Seidel?

GS usi sweep mein naye update kiye components use karta hai (in-place); Jacobi sirf purana vector use karta hai (parallelisable).

A simple sufficient condition guaranteeing both converge?

Strict diagonal dominance:

∣ a_{ii} ∣ > \sum_{j \neq = i} ∣ a_{ij} ∣

saare

i

ke liye.

Is diagonal dominance necessary for convergence?

Nahi — ye sirf sufficient hai; asli criterion

ρ (T) < 1

hai.

Asymptotic error reduction factor per step?

Approximately

ρ (T)

Why iterative over direct methods for large sparse

A

Har sweep ka cost

O (nnz) \approx O (n)

hai, jabki elimination

O (n^{3})

ka hai, aur memory sparse rehti hai.

Recall Feynman: explain it to a 12-year-old

Socho tum ek class mein sabki height guess kar rahe ho, phir ek aisi rule se har guess fix karte ho jo sab ki heights ko ek doosre se jodti hai. Jacobi: sablog apni guess ek saath update karte hain pichhli round ke numbers se. Gauss-Seidel: tum ek ek karke jaate ho, aur har banda apne se pehle walo ke abhi-correct numbers use karta hai — toh corrections zyada jaldi phailti hain. Agar rule guesses ko dheere dheere sach ki taraf "kheenchti" hai (numbers blow up nahi karte — yahi $ρ < 1$ hai), toh kuch rounds baad sabki guess basically sahi ho jaati hai. Agar rule over-react karti hai ( $ρ > 1$ ), toh guesses explode ho jaate hain aur tum kabhi finish nahi kar paate.

Connections

Gaussian Elimination — ye wahi direct $O (n^{3})$ alternative hai jo ye methods sparse systems ke liye replace karte hain.
Eigenvalues and Eigenvectors — convergence poori tarah $ρ (T)$ par depend karti hai.
Spectral Radius — yahan ka master quantity.
Fixed-Point Iteration — ye $x = g (x)$ iteration ka matrix version hain.
SOR — Successive Over-Relaxation — Gauss-Seidel ko relaxation factor $ω$ se accelerate karta hai.
Sparse Matrices — isliye per-sweep cost sasti hoti hai.
Finite Difference Methods for PDEs — huge sparse systems ka main source.

Method	$M$	$N$	$T = M^{- 1} N$
Jacobi	$D$	$L + U$	$D^{- 1} (L + U)$
Gauss-Seidel	$D - L$	$U$	$(D - L)^{- 1} U$