4.8.20 · D1Iterative methods — Jacobi, Gauss-Seidel, convergence
Ek badi system A x = b pehle ek guess karte hain, phir baar baar usse clean up karte hain — har cleanup step sasta hai, aur agar matrix "achhi" ho toh guess sach ke kareeb khisakte rehta hai. parent topic mein sab kuch bas yahi explain karta hai ki kaise clean up karein aur kab cleaning guaranteed kaam karegi.
Ye page kuch bhi assume nahi karta . Agar ek samajhdar 12-saal ke bachche ne kabhi matrix, vector, ya Greek letter ρ
x Vector bas numbers ki ek list hai jo ek column mein stack hoti hai . Hum ise bold likhte hain: x x = x 1 x 2 x 3 . x i i i
A Matrix numbers ka ek rectangle hai jo rows aur columns mein arrange hota hai. Entries ko a ij row i j wala number. Pehle row, phir column — hamesha.
Intuition Grid kyun hoti hai?Linear equations ka ek system jaise
4 x + y = 6 , x + 3 y = 7 coefficients (4 , 1 , 1 , 3 unknowns ek column mein, aur saare right-hand-side numbers doosre column mein. Inhe A x = b
Multiplication rule A x = b A i x b i b
Parent note A = D − L − U
Definition Diagonal, lower, upper pieces
Diagonal entries hain a 11 , a 22 , a 33 , … D Strictly lower part = diagonal ke neeche wali entries. Parent inke negatives L − L Strictly upper part = diagonal ke upar wali entries, negatives U A = D − L − U
Intuition Aise kyun split karte hain?Sirf diagonal wali matrices ko "undo" karna bahut aasaan hota hai (har row ko uske apne number se divide karo). Lower-triangular wali bhi aasaan hoti hain (pehle top row solve karo, phir neeche feed karo). Iteration ki poori trick hai ki aasaan part ko left mein rakho aur mushkil part ko right mein dhakelo. Figure s02 teeno regions ko colour karta hai taaki tum dekh sako ki koi overlap nahi hai: A
L U Kyun sahi lagta hai: tumhe expect hoga ki L hi ho. Galti: parent ke convention mein unke negatives store hote hain, isliye A = D − L − U Fix: jab bhi L − L
A x = b A b list x jo multiplication ko exactly b x true solution hai, jise x ∗
Intuition Kya sach mein koi true answer exist karta hai (aur kya woh unique hai)?Neeche sab kuch ek single target x ∗ A x = b exactly ek solution hota hai jab A invertible ho (non-singular bhi kehte hain): uska determinant nonzero ho, koi row doosron ka combination na ho. Tab x ∗ = A − 1 b A Hum aage se assume karte hain ki A
Classic exact recipe Gaussian Elimination hai — variables ko row by row cancel karo jab tak answer directly padh na sako. Ye hamesha kaam karta hai lekin n × n 3 2 n 3 n = 1 0 6 Finite Difference Methods for PDEs se common) woh ∼ 1 0 17
Intuition Sparse = mostly zeroReal problems se bani grids zyaadatar sparse hoti hain: almost har entry 0 A x nonzeros ki sankhya hoti hai — near O ( n ) O ( n 2 ) A x
x ( k ) counter hai, power nahi . x ( 0 ) x ( 1 ) x ( k ) k ummed karte hain ki x ( k ) x ∗ k
x ( k ) x k Kyun sahi lagta hai: superscripts usually powers hote hain. Galti: parentheses ise step-number flag karte hain. Fix: parentheses ⇒ iteration count; bina parentheses ke (jaise baad mein λ k
e ( k ) k error yeh hai ki guess sach se kitna door hai:
e ( k ) = x ( k ) − x ∗ .
∥ ⋅ ∥ norm ∥ e ∥ length . Aam choice hai:
∥ e ∥ = e 1 2 + e 2 2 + ⋯ + e n 2 , e ( k ) → 0 ka matlab hai single number ∥ e ( k ) ∥ 0 ε
Figure s03 mein guesses ki ek chain dikhti hai jo x ∗ ∥ e ( k ) ∥ poora goal hai — yeh poora subject tab ka study hai jab yeh hota hai aur kitni tezi se.
A = M − N A M N A = M − N M invert karna aasaan banao (diagonal, ya lower-triangular) aur jo bacha woh N
Jacobi M = D N = L + U Gauss–Seidel M = D − L N = U M − N = D − ( L + U ) = A
M − 1 M inverse woh matrix hai jo use undo karta hai: M − 1 M = I I identity hai (diagonal par ones, baki jagah zeros — "kuch nahi karne wali" grid). M − 1 M M choose kiya jiska inverse sasta ho aur hamesha exist kare (jab tak uske diagonal entries 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 hai. Error marega ya nahi — yeh poori tarah T
λ v T sirf stretch ya shrink karta hai, ghoomata nahi: T v = λ v λ eigenvalue hai; v eigenvector hai. Aisi direction mein T k λ k
Intuition Eigenvalues kyun sab decide karte hainStarting error ko eigenvector directions mein toddo. Har ek mein, ek cleanup λ ∣ λ ∣ < 1 ∣ λ ∣ > 1 ∣ λ ∣ = 0.5 ∣ λ ∣ = 1.4 Sabse buri direction poore error ki kismat tay karti hai.
Definition Spectral radiusρ ( T ) ρ ( T ) = max i ∣ λ i ∣ sabse bada absolute eigenvalue — "worst-case" stretch. Dekho Spectral Radius .
Definition Strictly diagonally dominant (SDD)Row i us row ki baaki saari entries milaakar se badi ho:
∣ a ii ∣ > ∑ j = i ∣ a ij ∣. har row pass kare, toh A sufficient (guaranteed kaam karne wali) lekin necessary nahi condition hai — ρ
∑ j = i ∑ ∣ a ij ∣ i diagonal wali ke alawa ." Bada Greek Σ
Map ko top-to-bottom padho: har box ek concept hai jo is page ne build kiya, aur har arrow ka matlab hai "neeche wala box samajhne ke liye upar wala box chahiye." Hum raw vectors aur matrices se shuru karte hain, notice karte hain ki A x = b iterate karte hain — jo humein 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
a ij Row i j pehle row, phir column .
Kya x ( k ) k Nahi — parentheses ise ek step counter banate hain; x ( 0 )
Step k e ( k ) = x ( k ) − x ∗
Norm ∥ e ∥ Vector ki length,
e 1 2 + ⋯ + e n 2 ; "zero ho jaana" matlab yeh single number kisi bhi tolerance se neeche shrink ho jaaye.
A x = b Jab A x ∗ = A − 1 b
Split A = M − N M , N Jacobi: M = D N = L + U M = D − L N = U M
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
M Step M − 1 M a ii = 0
M − 1 M − 1 M Yeh M M − 1 M = I
A = D − L − U − L negatives L
T λ Ek khaas direction v T v = λ v T k λ k
ρ ( T ) Spectral radius — sabse bada absolute eigenvalue , worst-case stretch.
Exact necessary-and-sufficient convergence condition? ρ ( T ) < 1
Strictly diagonal dominant ka matlab kya hai, aur kya yeh necessary hai? Har row ke liye ∣ a ii ∣ > ∑ j = i ∣ a ij ∣ sufficient hai lekin necessary nahi .
Bade sparse systems par Gaussian elimination ki jagah iterate kyun karte hain? Elimination ∼ 3 2 n 3 ∼ O ( n )