Worked examples — LU decomposition (numerical)

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

Shuru karne se pehle, woh vocabulary jo hum baar baar use karte hain (sab parent mein bani hui hai): $A=LU$ ka matlab hai ki hum ek square number-grid $A$ ko lower-triangular $L$ (diagonal ke upar zeros, diagonal par 1's) aur upper-triangular $U$ (diagonal ke neeche zeros) mein tod dete hain. Hum $A\mathbf{x}=\mathbf{b}$ solve karte hain pehle neeche chalke ($L\mathbf{y}=\mathbf{b}$, forward substitution) phir upar ($U\mathbf{x}=\mathbf{y}$, back substitution). Agar in shabdon par aapki pakad kamzor hai, toh pehle Gaussian Elimination aur Forward and Back Substitution dobara padh lo.

---

The scenario matrix

Har LU problem jo aap dekhenge woh in cells mein se kisi ek mein aati hai. Hum ek worked example se har ek ko cover karenge.

Cell	Case class	Kya khaas hai	Example
C1	Clean $2\times 2$, nonzero pivots	Textbook ka happy path	Ex 1
C2	Clean $3\times 3$	Sums ko badhte dekho	Ex 2
C3	Zero pivot, matrix phir bhi invertible	$u_{11}=0$, pivot karna zaroori ($PA=LU$)	Ex 3
C4	Tiny pivot vs. big pivot	Pivoting ke bina rounding bigad jaati hai	Ex 4
C5	Multiple right-hand sides	Poora point yehi hai: ek baar factor karo, do baar solve karo	Ex 5
C6	Singular matrix	Ek pivot $0$ ho jaata hai aur swap karne ko kuch nahi	Ex 6
C7	Determinant via LU (swap ke saath)	Permutation se sign flip	Ex 7
C8	Word problem (real world)	Ek kahaani se $A\mathbf{x}=\mathbf{b}$ setup karo	Ex 8

---

C1 — Clean $2\times 2$: the happy path

Forecast: compute karne se pehle dono answers ka sign guess karo. (Hint: doosri equation zyada "bhaari" hai.)

1. $u_{11}=4,u_{12}=3$. Yeh step kyun? $L$ ki Row 1 $(1,0)$ hai, isliye multiply karne par $U$ ki top row = $A$ ki top row bilkul waise hi milti hai.
2. ${\ell }_{21}=a_{21}/u_{11}=8/4=2$. Kyun? Yeh Gaussian multiplier hai — "row 1 ko kitna multiply karke row 2 se subtract karun taaki $8$ khatam ho jaye?"
3. $u_{22}=a_{22}-{\ell }_{21}{u}_{12}=11-2\cdot 3=5$. Kyun? Column-1 elimination ne position $(2,2)$ mein jo daala tha, use subtract karo.

$L=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right),U=\left(\begin{array}{cc}4& 3\\ 0& 5\end{array}\right).$

4. Forward solve $L\mathbf{y}=\mathbf{b}$: $y_1=10$; phir $2y_1+y_2=30\Rightarrow y_2=30-20=10$. Top-first kyun? $L$ ki pehli row mein sirf ek unknown hai.
5. Back solve $U\mathbf{x}=\mathbf{y}$: $5x_2=10\Rightarrow x_2=2$; phir $4x_1+3\cdot 2=10\Rightarrow 4x_1=4\Rightarrow x_1=1$. Bottom-first kyun? $U$ ki aakhri row mein sirf ek unknown hai.

$\boxed{\mathbf{x}=(1,2{)}^{\top }}$

Verify: $A\mathbf{x}=(4\cdot 1+3\cdot 2,8\cdot 1+11\cdot 2)=(10,30)=\mathbf{b}$ ✓. Aur $LU=A$ ✓.

---

C2 — Clean $3\times 3$: sums ko badhte dekho

Forecast: kya teeno pivots $u_{11},u_{22},u_{33}$ positive niklenge? Abhi guess karo.

1. $U$ ki Row 1: $u_{11}=2,u_{12}=4,u_{13}=-2$. Kyun? C1 wali wajah — top row waise hi copy ho jaati hai.
2. $L$ ka Column 1: ${\ell }_{21}=4/2=2$, ${\ell }_{31}=-2/2=-1$. Kyun? Pehle pivot ke neeche ke dono entries zero karne ke liye multipliers.
3. $U$ ki Row 2: $u_{22}=9-{\ell }_{21}{u}_{12}=9-2\cdot 4=1$; $u_{23}=-3-{\ell }_{21}{u}_{13}=-3-2\cdot (-2)=1$. Kyun? Doolittle sum ${\sum }_k{\ell }_{ik}{u}_{kj}$ use karke row-1 ka contribution subtract karo.
4. $L$ ka Column 2: ${\ell }_{32}=\frac{a_{32}-{\ell }_{31}{u}_{12}}{u_{22}}=\frac{-3-(-1)\cdot 4}{1}=\frac{-3+4}{1}=1$. Kyun? Column-1 clear hone ke baad entry $(3,2)$ ko zero karne ka multiplier.
5. $U$ ki Row 3: $u_{33}=a_{33}-{\ell }_{31}{u}_{13}-{\ell }_{32}{u}_{23}=7-(-1)(-2)-1\cdot 1=7-2-1=4$. Kyun? Aakhri pivot woh hai jo bach jaata hai jab dono pehle columns apna hissa le chuke hote hain.

$L=\left(\begin{array}{ccc}1& 0& 0\\ 2& 1& 0\\ -1& 1& 1\end{array}\right),U=\left(\begin{array}{ccc}2& 4& -2\\ 0& 1& 1\\ 0& 0& 4\end{array}\right).$

Verify: $LU$ multiply karo — row 2 deta hai $(2,9,-3)$ ✓, row 3 deta hai $(-2,-3,7)$ ✓. Pivots $2,1,4$ sab positive hain, jaise is acchi symmetric-dikhne wali matrix ke liye forecast kiya tha.

---

C3 — Zero pivot, lekin $A$ invertible hai: pivot karna ZAROORI hai

Forecast: kya LU yahan simply fail ho jaata hai, ya koi rescue hai?

1. Naive attempt: $u_{11}=a_{11}=0$, phir ${\ell }_{21}=3/0$ — division by zero. Yeh step important kyun hai? Yeh dikhata hai ki ek bilkul invertible matrix ($\det A=-6\ne 0$) bhi plain Doolittle ko tod sakti hai.
2. Partial pivoting: dono rows swap karo taaki sabse bada first-column entry ($3>0$) pivot par aa jaye. Ise ek permutation matrix $P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ mein record karo. Kyun? $A$ ki rows swap karna = $P$ se multiply karna; ab hum $PA=LU$ factor karte hain.
3. $PA=\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right)$ factor karo: yeh already upper-triangular hai, isliye $u_{11}=3,u_{12}=4$, ${\ell }_{21}=0/3=0$, $u_{22}=2$.

$P=\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right),L=\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),U=\left(\begin{array}{cc}3& 4\\ 0& 2\end{array}\right).$

4. Solve — $\mathbf{b}$ ko permute karna yaad rakhna! $LU\mathbf{x}=P\mathbf{b}$ solve karo, jahan $P\mathbf{b}=(11,8{)}^{\top }$. Forward: $L$ identity hai isliye $\mathbf{y}=P\mathbf{b}=(11,8)$. Back: $2x_2=8\Rightarrow x_2=4$; $3x_1+4\cdot 4=11\Rightarrow 3x_1=-5\Rightarrow x_1=-5/3$.

$\boxed{\mathbf{x}=(-5/3,4{)}^{\top }}$

Verify: $A\mathbf{x}=(0\cdot (-5/3)+2\cdot 4,3\cdot (-5/3)+4\cdot 4)=(8,-5+16)=(8,11)=\mathbf{b}$ ✓. Poori swapping rule ke liye Partial Pivoting dekho.

---

C4 — Tiny pivot vs. big pivot: accuracy matters

Forecast: dono routes ek hi exact answer tak pahunchti hain. Rounding mein kaun si route survive karegi?

1. No-pivot factor: $u_{11}=0.001$, ${\ell }_{21}=1/0.001=1000$, $u_{22}=1-1000\cdot 1=-999$. Yeh note kyun karein? Multiplier $1000$ bahut bada hai — yahi danger sign hai.
2. No-pivot solve (3 sig figs tak round kiya): $y_1=1$, $y_2=2-1000\cdot 1=-998\approx -1.00\times 10^3$. Back: $x_2=(-998)/(-999)\approx 0.999$; phir $0.001x_1=1-0.999=0.001\Rightarrow x_1\approx 1.00$. $2-1000=-998$ ko 3 figures mein round karne se $-1.00\times 10^3$ milta hai, toh $x_2\to 1.00$, aur phir $x_1\to (1-1)/0.001=0$ — catastrophically galat ($x_1$ hona chahiye $\approx 1$). Kyun? Ek bade number se subtract karne par chhota $1$ dab gaya; asli information kho gayi.
3. Pivot ke saath: rows swap karo (sabse bada first-column entry $1$ hai). $PA=\left(\begin{array}{cc}1& 1\\ 0.001& 1\end{array}\right)$, toh ${\ell }_{21}=0.001$, $u_{22}=1-0.001=0.999\approx 1.00$. Multiplier chota hai — safe hai.
4. Pivoted solve: $P\mathbf{b}=(2,1)$. $y_1=2$, $y_2=1-0.001\cdot 2=0.998$. Back: $x_2=0.998/0.999\approx 0.999$; $x_1=2-x_2\approx 1.00$. Sahi hai.

$\text{Exact answer: }\mathbf{x}=\left(\frac{1000}{999},\frac{998}{999}\right)\approx (1.001,0.999).$

Verify: exact arithmetic se, $A\mathbf{x}=(0.001\cdot \frac{1000}{999}+\frac{998}{999},\frac{1000}{999}+\frac{998}{999})=(\frac{1+998}{999},\frac{1998}{999})=(1,2)=\mathbf{b}$ ✓. Moral: bada pivot, chhoti error — Condition Number and Numerical Stability dekho.

---

C5 — Multiple right-hand sides: LU ka asli reason

Forecast: har right-hand side ke liye kitna naya kaam hai? (Jawab: koi factoring nahi, sirf do substitutions.)

Yaad karo $L=\left(\begin{array}{cc}1& 0\\ 2& 1\end{array}\right),U=\left(\begin{array}{cc}4& 3\\ 0& 5\end{array}\right)$.

1. ${\mathbf{b}}_1$ — forward: $y_1=7$, $y_2=14-2\cdot 7=0$. Back: $5x_2=0\Rightarrow x_2=0$; $4x_1+0=7\Rightarrow x_1=7/4$. Re-factoring kyun nahi? $A$ nahi badla, sirf $\mathbf{b}$ badla; elimination steps $L,U$ mein freeze hain.
2. ${\mathbf{b}}_2$ — forward: $y_1=0$, $y_2=20-2\cdot 0=20$. Back: $5x_2=20\Rightarrow x_2=4$; $4x_1+3\cdot 4=0\Rightarrow 4x_1=-12\Rightarrow x_1=-3$.

$\boxed{{\mathbf{x}}_1=(7/4,0{)}^{\top },{\mathbf{x}}_2=(-3,4{)}^{\top }}$

Verify: $A{\mathbf{x}}_1=(4\cdot \frac{7}{4}+0,8\cdot \frac{7}{4}+0)=(7,14)$ ✓; $A{\mathbf{x}}_2=(-12+12,-24+44)=(0,20)$ ✓. Do solves, zero re-factoring — yahi toh fayda hai.

---

C6 — Singular matrix: ek pivot khatam ho jaata hai aur koi rescue nahi

Forecast: doosri row bilkul pehli row ki aadhi hai. Doosra pivot kya hona chahiye?

1. $U$ ki Row 1: $u_{11}=2,u_{12}=4$. Kyun? Top row hamesha ki tarah copy ho jaati hai.
2. ${\ell }_{21}=a_{21}/u_{11}=1/2$. Kyun? Standard multiplier.
3. $u_{22}=a_{22}-{\ell }_{21}{u}_{12}=2-\frac{1}{2}\cdot 4=0$. Yeh fatal kyun hai? $u_{22}=0$ aakhri pivot hai; neeche koi row nahi jo swap ki ja sake. Back substitution ko $0\cdot x_2=y_2$ chahiye hoga, jo solve nahi ho sakti (ya infinite solutions hongi).

$L=\left(\begin{array}{cc}1& 0\\ 1/2& 1\end{array}\right),U=\left(\begin{array}{cc}2& 4\\ 0& 0\end{array}\right).$

Verify: factorization abhi bhi valid hai ($LU=A$ ✓), lekin $\det A=u_{11}{u}_{22}=2\cdot 0=0$, jo confirm karta hai ki $A$ singular hai. Aakhri position par zero pivot ka matlab hai ki koi unique solution nahi hai — pivoting yahan aapko nahi bacha sakta. Yeh honest signal hai ki $A\mathbf{x}=\mathbf{b}$ ka koi unique answer nahi hai.

---

C7 — Determinant via LU (swap ke saath)

Forecast: row 1 mein hume row swap chahiye tha (kyunki $a_{11}=0$). Kya yeh $\det$ ka sign flip karega?

1. Swap zaroori hai: $a_{11}=0$, isliye sabse bade first-column entry par pivot karo, jo hai $2$ row 3 mein. Ek swap → $(-1{)}^1$ factor. Rows 1 aur 3 swap karne ke baad: $PA=\left(\begin{array}{ccc}2& 1& 0\\ 1& 2& 1\\ 0& 1& 2\end{array}\right),P=\left(\begin{array}{ccc}0& 0& 1\\ 0& 1& 0\\ 1& 0& 0\end{array}\right).$ Kyun? Determinants har row swap par sign flip karte hain; hume swaps count karne honge.
2. $PA$ factor karo. $u_{11}=2$. ${\ell }_{21}=1/2$, ${\ell }_{31}=0$. $u_{22}=2-\frac{1}{2}\cdot 1=\frac{3}{2}$; $u_{23}=1-\frac{1}{2}\cdot 0=1$. ${\ell }_{32}=\frac{1-0}{3/2}=\frac{2}{3}$. $u_{33}=2-0-\frac{2}{3}\cdot 1=\frac{4}{3}$. Kyun? Pivoted matrix par seedhe Doolittle sums.
3. Determinant assemble karo: $\det A=(-1{)}^{\#\text{swaps}}\prod u_{ii}=(-1{)}^1\cdot 2\cdot \frac{3}{2}\cdot \frac{4}{3}=(-1)\cdot 4=-4.$ Minus kyun? Ek swap = ek sign flip.

$\boxed{\det A=-4}$

Verify: $A$ ko top row ke along seedha expand karo: $0\cdot (\dots )-1\cdot (1\cdot 0-1\cdot 2)+2\cdot (1\cdot 1-2\cdot 2)=-1\cdot (-2)+2\cdot (1-4)=2+2\cdot (-3)=2-6=-4$ ✓.

---

C8 — Word problem: ek real setup

Forecast: dono counts positive hone chahiye (aap negative batches nahi bana sakte) — akhir mein check karo.

1. $A$ factor karo. $u_{11}=2,u_{12}=1$; ${\ell }_{21}=1/2$; $u_{22}=3-\frac{1}{2}\cdot 1=\frac{5}{2}$. Kyun? Standard Doolittle; numbers recipe grid hain.
2. Forward $L\mathbf{y}=\mathbf{b}$: $y_1=8$; $y_2=14-\frac{1}{2}\cdot 8=14-4=10$. Kyun? $L$ lower-triangular hai, top-down solve karo.
3. Back $U\mathbf{x}=\mathbf{y}$: $\frac{5}{2}{x}_B=10\Rightarrow x_B=4$; $2x_A+1\cdot 4=8\Rightarrow 2x_A=4\Rightarrow x_A=2$. Kyun? $U$ upper-triangular hai, bottom-up solve karo.

$\boxed{x_A=2\text{ units},x_B=4\text{ units}}$

Verify (units!): apple $=2\cdot 2+1\cdot 4=8$ L ✓; mango $=1\cdot 2+3\cdot 4=14$ L ✓. Dono counts positive hain — physically sensible hai.

---

Upar ki figure hamare scenario matrix ke har cell ko ek map par rakhti hai: green cells "LU bas kaam karta hai", yellow cells "kaam karta hai lekin pehle pivot karo", pink cells "LU aapko kuch galat ya khaas bata raha hai". Yeh mental map apne paas rakho jab koi nayi matrix aapke samne aaye.

---

Recall Answers

Zero pivot ka matlab hai ki uske neeche ka multiplier $0$ se divide karta hai; skip karna allowed nahi hai, aapko ek nonzero row swap karni hi padegi ::: — lekin sirf tab jab koi ho. Pivoting ne multiplier ko chota rakha taaki finite-precision rounding ne asli digits na mitaye ::: (stability, exactness nahi). Bilkul nahi — $L$ aur $U$ reuse kiye gaye; sirf do substitutions chali ::: (LU ka poora point). Zero aakhri pivot tha jiske neeche swap karne ke liye koi row nahi thi — matrix singular hai ::: ($\det A=0$). Ek row swap ne ek factor $(-1{)}^1$ contribute kiya ::: $\det A=(-1{)}^{\#\text{swaps}}\prod u_{ii}$ mein.

---

Connections

• Parent: LU decomposition — woh machinery jo yeh examples exercise karti hai.
• Gaussian Elimination · Forward and Back Substitution — woh do engines jo har solve mein use hote hain.
• Partial Pivoting · Permutation Matrices — C3, C4, C7 mein rescue.
• Determinants — C7 mein sign-counting.
• Condition Number and Numerical Stability — C4 important kyun hai.
• Crout Decomposition · Cholesky Decomposition — doosri matrix shapes ke liye sibling factorizations.