Visual walkthrough — LU decomposition (numerical)

4.8.19 · D2 · Maths › Numerical Methods › LU decomposition (numerical)

Shuru karne se pehle, teen words jo hum baar baar use karenge, simple bhasha mein define kiye gaye hain aur pictures se jode gaye hain:

Diagonal khud positions $a_{11},a_{22},a_{33},\dots$ ka set hai — jahan row number aur column number barabar hon.

---

Step 1 — "Elimination se solve karna" grid par actually kya karta hai

KYA. Hum ek $3\times 3$ system se shuru karte hain. Elimination ka matlab hai: top-left number ka use karke uske seedha neeche ke numbers ko mita do, jisse left column $\left(\begin{array}{c}\bullet \\ 0\\ 0\end{array}\right)$ ban jaaye.

KYUN. Ek aisi grid jiske bottom-left mein sab zeros hain (upper triangular) ko back substitution se solve kiya ja sakta hai — sabse neeche ki equation padho, jisme sirf ek unknown hai, phir upar chadhte jao. Toh elimination ka poora goal uss zero-filled corner ko banana hai.

PICTURE. Neeche di gayi grid dekho. Amber cell $a_{11}$ pivot hai — woh number jisse hum divide karte hain. Uske neeche ke do cyan cells, $a_{21}$ aur $a_{31}$, woh hain jinhe hum $0$ banana chahte hain.

$a_{21}$ ko khatam karne ke liye hum row 2 mein se row 1 ki ek copy subtract karte hain. Kitni copies? Bilkul utni ki $a_{21}$ wali jagah zero ho jaaye. Copies ki woh sankhya hai:

${\ell }_{21}=\underset{\text{number to erase}}{\underbrace{a_{21}}}/\underset{\text{pivot underneath row 1}}{\underbrace{a_{11}}}$

${\ell }_{21}$ ko multiplier kehte hain: jitna row 1 ko row 2 mein mix kiya.

---

Step 2 — Multiplier ko rakhna worth it hai

KYA. Ordinary elimination mein hum ${\ell }_{21}=a_{21}/a_{11}$ compute karte hain, subtraction karte hain, aur phir ${\ell }_{21}$ ko bhool jaate hain. LU decomposition ki ek hi insight hai: use bhulo mat — use us khali slot mein likh do jise usne abhi clear kiya.

KYUN. Slot $(2,1)$ ab $0$ hai aur $0$ hi rahega — yeh spare storage hai. Agar hum ${\ell }_{21}$ wahan rakh den, toh grid yaad rakhti hai ki use kaise eliminate kiya gaya tha. Baad mein woh memory original $A$ ko reconstruct karti hai.

PICTURE. Amber arrow dikhata hai ${\ell }_{21}$ "jo kaam kiya usme se" naye-zero hue cell mein flow kar raha hai. Woh zeroed cell (ab ${\ell }_{21}$ hold kar raha hai) $L$ ki entry ban jaati hai; bachta hua top part $U$ ki entry ban jaata hai.

${\text{new row}}_2=\underset{\text{old}}{\underbrace{{\text{row}}_2}}-\underset{\text{how much}}{\underbrace{{\ell }_{21}}}\cdot \underset{\text{the pivot row}}{\underbrace{{\text{row}}_1}}$

Yahan har symbol apna kaam kar raha hai: ${\ell }_{21}$ kehta hai kitna, row${}_1$ kehta hai kiska, minus sign kehta hai hatao use.

---

Step 3 — Elimination ka ek step = elementary matrix se multiply karna

KYA. Single operation "row${}_2\leftarrow$ row${}_2-{\ell }_{21}$row${}_1$" khud ek matrix hai. Ise $E_{21}$ kaho. Yeh identity jaisi dikhti hai jisme position $(2,1)$ par $-{\ell }_{21}$ daala gaya hai.

KYUN. Agar ek step ek matrix hai, toh poora elimination aisi matrices ka product hai. Products ko invert aur re-order karna aasan hota hai — yahi hume saare multipliers ko ek saaf $L$ mein ikatha karne deta hai.

PICTURE. Identity matrix (ek "kuch mat karo" grid, diagonal par 1's) mein ek amber intruder $-{\ell }_{21}$ woh machine hai jo Step 2 perform karti hai.

$E_{21}=\left(\begin{array}{ccc}1& 0& 0\\ -{\ell }_{21}& 1& 0\\ 0& 0& 1\end{array}\right),E_{21}A=\text{(A with row 2 cleaned)}$

Term-by-term: $1$'s har doosri row ko unchanged copy karte hain; row 2 mein $-{\ell }_{21}$ inject karta hai "$-{\ell }_{21}\times$ row 1" ko row 2 mein — bilkul Step 2 ki tarah.

---

Step 4 — Saare steps stack karo: $U=(\text{all }E)A$

KYA. Har elimination karo order mein — column 1 clear karo, phir column 2. Har ek ek elementary matrix hai. Inhe sab $A$ par left se multiply karo. Result upper triangular hai; ise $U$ kaho.

KYUN. Jab grid upper triangular ho jaati hai, elimination khatam hai. Humne saara "downward mixing" $E$'s ke product mein factor out kar diya jo $A$ ke left par baitha hai.

PICTURE. Left se right padho: $A$ enter karta hai, har $E$ ek aur sub-diagonal cell shave karta hai, aur $U$ (saaf upper-triangular staircase) nikalta hai. Isi story ko bina matrix bookkeeping ke dekhne ke liye Gaussian Elimination dekho.

$\underset{\text{all elimination steps}}{\underbrace{E_{32}{E}_{31}{E}_{21}}}A=U$

Order matter karta hai: $E_{21}$ pehle act karta hai (woh $A$ ke sabse paas hai), phir $E_{31}$, phir $E_{32}$ — right-to-left, functions ki tarah.

---

Step 5 — Steps undo karo aur $L$ reveal karo

KYA. Saare $E$'s ko doosri taraf le jao. Pure product ka inverse $L$ hai: $A=(E_{32}{E}_{31}{E}_{21}{)}^{-1}U=LU.$

KYUN. Har $E$ ko invert karne par sirf uska ek off-diagonal sign flip hota hai ($-\ell \to +\ell$), aur — yahan ek chhoti si miracle hai — inverses ko multiply karne par simply har $+{\ell }_{ij}$ apni slot mein gir jaata hai bina kisi cross-contamination ke. Toh $L$ literally multipliers ki table hai, diagonal par $1$'s ke saath.

PICTURE. Amber $-\ell$ entries $+\ell$ mein flip hoti hain aur lower-triangular $L$ mein assemble ho jaati hain. Unke beech koi arithmetic nahi — har multiplier untouched land karta hai.

$L=\left(\begin{array}{ccc}1& 0& 0\\ {\ell }_{21}& 1& 0\\ {\ell }_{31}& {\ell }_{32}& 1\end{array}\right)$

Padho ise: diagonal $1$'s matlab "har row khud ko puri tarah rakhti hai"; ${\ell }_{21}$ neeche record karta hai ki row 1 ka kitna row 2 mein gaya; ${\ell }_{32}$ kitna (cleaned) row 2 ka row 3 mein gaya. Yeh bilkul Doolittle form hai. ($1$'s ko $U$ par le jao aur tumhe Crout Decomposition milegi.)

---

Step 6 — Degenerate case: ek zero pivot

KYA. Maan lo amber pivot $a_{11}=0$ hai. Tab ${\ell }_{21}=a_{21}/0$ — undefined. Elimination ruk jaata hai chahe $A$ perfectly invertible ho.

KYUN. Pivot se divide karna har multiplier mein baked in hai. Zero pivot ek divide-by-zero hai, aur ek tiny pivot almost utna hi bura hai — yeh rounding error ko magnify karta hai (yeh Condition Number and Numerical Stability se link hai).

PICTURE. Left grid stall dikhati hai: pivot seat mein ek red $0$. Right grid cure dikhati hai — do rows swap karo taki pivot par ek bada number aa jaaye. Woh swap ek permutation matrix $P$ hai, jisse $PA=LU$ milta hai. Yeh Partial Pivoting hai.

$PA=LU,\text{solve }L\mathbf{y}=P\mathbf{b},U\mathbf{x}=\mathbf{y}$

Term-by-term: $P$ $A$ ki rows reorder karta hai (aur wahi reorder $\mathbf{b}$ par bhi lagni chahiye); swap ke baad pivot nonzero hai aur Steps 1–5 normally chalte hain.

---

Step 7 — Do triangular solves kaam khatam karte hain

KYA. $A=LU$ haath mein aane par, $A\mathbf{x}=\mathbf{b}$ ban jaata hai $LU\mathbf{x}=\mathbf{b}$. Beech ke vector ko $\mathbf{y}=U\mathbf{x}$ naam do. $L\mathbf{y}=\mathbf{b}$ neeche ki taraf solve karo, phir $U\mathbf{x}=\mathbf{y}$ upar ki taraf.

KYUN. Ek triangular system mein "har line mein ek naya unknown" ki structure hoti hai: $L\mathbf{y}=\mathbf{b}$ ki pehli row mein sirf $y_1$ hai, doosri mein sirf $y_1,y_2$, aur aage bhi — koi algebra nahi, bas substitution. Dekho Forward and Back Substitution.

PICTURE. Green $L$ ki staircase se neeche flow karta hai (forward), phir $U$ ki staircase se upar flow karta hai (back). Dono directions do triangles ki shapes hain jo physical ho gayi hain.

$\underset{\text{top}\to \text{bottom}}{\underbrace{L\mathbf{y}=\mathbf{b}}}\text{then}\underset{\text{bottom}\to \text{top}}{\underbrace{U\mathbf{x}=\mathbf{y}}}$

Aur free bonus (Step 5 ki diagonal se): kyunki $\det L=1$ hai, determinant hai $\det A=(-1{)}^{\#\text{swaps}}{\prod }_i{u}_{ii}$ — bas $U$ ki diagonal multiply karo.

---

Ek-picture summary

Poora safar ek frame mein: $A$ left se enter karta hai; elimination ($E$'s) use shave karke upper-triangular $U$ banata hai jabki chupke se har multiplier ko lower-triangular $L$ mein file karta hai; reunion $L\cdot U$ $A$ ko exactly reproduce karta hai; aur koi bhi right-hand side $\mathbf{b}$ phir do sasti staircases (neeche, phir upar) par sawaar hokar answer $\mathbf{x}$ tak pahunchti hai.

Recall Feynman retelling — kisi dost ko batao

Tum equations ke ek system ko un-mix karna chahte ho. Toh tum ise column by column saaf karte ho: har pivot ke neeche ke number ke liye, pata karo ki pivot ki row ki kitni copies subtract karni hongi use zero karne ke liye, aur subtract karo. Woh "kitni copies" wala number ek multiplier hai. Normally tum use bhool jaate — lekin jo cell tumne abhi zero kiya woh ab khaali hai, isliye tum wahan multiplier store karte ho. Jab khatam ho, tumhari grid ka top-right cleaned-up upper matrix $U$ hai, aur bottom-left mein saare stored multipliers hain, jo (diagonal par 1's ke saath) $L$ banate hain. $L$ ko $U$ se multiply karo aur, jaadu se, tumhara original $A$ wapas aa jaata hai — kyunki $L$ literally tumhari har move yaad rakhta hai. Agar koi pivot zero nikle, tum usse divide nahi kar sakte, toh bas us row ko uss lower row se swap karo jisme wahan ek bada number ho, swap ko $P$ mein yaad karo, aur jaari raho. In sab ke baad, kisi bhi naye right-hand side ke liye solve karna trivial hai: $L$ se neeche slide karo (forward substitution), phir $U$ se upar chadho (back substitution). Ek baar factor karo, hamesha ke liye solve karo.

---

Connections

• 4.8.19 LU decomposition (numerical) (Hinglish) — parent topic (Hinglish).
• Gaussian Elimination — woh elimination jo Steps 1–4 photograph karte hain.
• Forward and Back Substitution — Step 7 ke do staircase solves.
• Partial Pivoting / Permutation Matrices — Step 6 mein cure.
• Crout Decomposition / Cholesky Decomposition — sibling factorizations ($U$ par 1's; symmetric case).
• Determinants — Step 7 ke end mein bonus.
• Condition Number and Numerical Stability — kyun ek tiny pivot dangerous hota hai.