Worked examples — Solving linear systems — Gaussian elimination with partial pivoting

4.8.18 · D3 · Maths › Numerical Methods › Solving linear systems — Gaussian elimination with partial p

Shuru karne se pehle, teen words jo tumhare paas hone chahiye (har ek parent mein banaya gaya, yahan repeat kiya gaya taaki pehli line akele khari rahe):

• Pivot — wo number jo diagonal par baitha hai aur jisse hum divide karte hain. Us block ke top-left corner ko imagine karo jise hum abhi clear kar rahe hain.
• Multiplier $m_{ik}=a_{ik}/a_{kk}$ — pivot row ki kitni copies hum row $i$ se subtract karte hain taaki position $(i,k)$ par zero punch ho sake.
• Augmented matrix $[A|\mathbf{b}]$ — coefficient grid jisme right-hand side ek extra column ki tarah staple ki gayi hai, taaki har row operation answer column ko bhi touch kare.

---

The scenario matrix

Is topic se aane wali har linear-system problem in cells mein se exactly ek mein land hoti hai. Hamaara kaam hai sabhi ko hit karna.

Cell	Kya special hai	Kaunsa danger probe karta hai	Kahan milega
C1 Clean unique	sabse bada pivot already upar, saaf numbers	kuch nahi — yeh baseline hai	Ex 1
C2 Swap needed	sabse bada entry diagonal ke neeche hai	pivoting bhoolo mat	Ex 2
C3 Tiny pivot	ek near-zero would-be pivot	round-off blow-up	Ex 3
C4 Negative pivots & signs	negative diagonal, negative multipliers	$m_{ik}$ mein sign slip	Ex 4
C5 Zero pivot, but fixable	diagonal par ek literal $0$ jo swap se bach jaata hai	"divide by zero" ka dar	Ex 5
C6 Singular — no solution	poori row collapse ho jaati hai $0=c$, $c\ne 0$ par	failure ko pehchaanna	Ex 6
C6′ Singular — infinitely many	poori row collapse ho jaati hai $0=0$ par	free variables	Ex 6′
C7 Word problem (real units)	mixture / circuit ko $A\mathbf{x}=\mathbf{b}$ ki tarah model kiya	words → matrix mein translate karna	Ex 7
C8 Exam twist (parameter)	ek unknown $t$ solvability decide karta hai	limiting behaviour	Ex 8

---

Ex 1 — Cell C1: clean baseline

Forecast: column 1 mein $|4|>|2|$ hai, toh koi swap nahi. Guess hai ki answer chhote positive numbers hain.

1. Pivot check karo. Yeh step kyun? Partial pivoting pehle column 1, rows 1–2 ko dekhta hai: $|4|$ vs $|2|$. Sabse bada already upar hai, toh koi swap nahi.
2. Multiplier. Yeh step kyun? Hume position $(2,1)$ mein $0$ chahiye. $m_{21}=a_{21}/a_{11}=2/4=0.5$.
3. Eliminate karo. Yeh step kyun? $0.5\times$row 1 subtract karne se $a_{21}$ khatam hota hai aur baaki row update hoti hai (RHS bhi): $a_{22}=5-0.5(3)=3.5,b_2=11-0.5(10)=6.$ $\left[\begin{array}{cccc}4& 3& |& 10\\ 0& 3.5& |& 6\end{array}\right].$
4. Back-substitute karo. Bottom-up kyun? Last row ab ek hi unknown ke saath hai: $x_2=\frac{6}{3.5}=\frac{12}{7}\approx 1.7143,x_1=\frac{10-3x_2}{4}=\frac{10-36/7}{4}=\frac{34/7}{4}=\frac{17}{14}\approx \mathrm{1.2143.}$

Verify karo: eq 2: $2(1.2143)+5(1.7143)=2.4286+8.5714=11✓$.

---

Ex 2 — Cell C2: swap forced ho jaata hai

Forecast: column 1 mein $|3|>|1|$ hai, toh hume zaroor swap karna padega. Guess: pehle swap, phir clean elimination.

1. Column 1 scan karo. Yeh step kyun? Rows 1–2 mein, $|3|>|1|$; sabse bada row 2 mein baitha hai. Rows 1 aur 2 swap karo — poori rows, RHS bhi. $\left[\begin{array}{cccc}3& 2& |& 7\\ 1& 4& |& 9\end{array}\right].$
2. Multiplier. Yeh step kyun? Ab pivot ek safe $3$ hai. $m_{21}=1/3\approx 0.3333$.
3. Eliminate karo. Kyun: zero punch karo aur update karo: $a_{22}=4-\frac{1}{3}(2)=\frac{10}{3}\approx 3.3333,b_2=9-\frac{1}{3}(7)=\frac{20}{3}\approx \mathrm{6.6667.}$
4. Back-substitute karo. Bottom-up kyun? Eliminate hua row 2 ab sirf $x_2$ rakhta hai, toh hum usse pehle solve karte hain, phir wo value row 1 mein feed karte hain: $x_2=\frac{20/3}{10/3}=2,x_1=\frac{7-2(2)}{3}=1.$

Verify karo: eq 1 (original): $1(1)+4(2)=9✓$; eq 2: $3(1)+2(2)=7✓$.

Figure dikhata hai kyun pivoting ek geometric idea hai: har equation ek line hai, solution unka crossing point hai, aur rows swap karna us crossing ko kabhi move nahi karta — bas yeh relabel karta hai ki hum pehle kaunsi line clear karte hain.

---

Ex 3 — Cell C3: tiny-pivot trap (ke saath aur bina)

Forecast: exact answer (do equations solve karke) hai $x_1\approx 1.6668,x_2\approx 1.9992$. Guess hai ki no-pivot route $x_1$ ko corrupt kar dega.

Route A — WITHOUT pivoting (cautionary tale).

1. Tiny pivot $0.002$ rakho. Yeh kyun dikhaayen? Uss failure ko expose karne ke liye jo parent ne warn kiya tha. $m_{21}=3/0.002=1500$. Ek monster multiplier har rounding error ko magnify karta hai.
2. Har result ko 4 sig figs par round karo. Kyun: hamaara imaginary calculator sirf 4 digits rakhta hai. $a_{22}=1-1500(4)=1-6000=-5999\to -5999,$ $b_2=7-1500(8)=7-12000=-11993\to -11990(\text{4 sig figs}).$
3. $x_2=-11990/-5999=1.999$. Phir $x_1=(8-4(1.999))/0.002$. Kyun toot jaata hai: $4(1.999)=7.996$, aur $8-7.996=0.004$ — near-equal 4-digit numbers ki subtraction sirf ek achha digit rakhti hai. Toh $x_1=0.004/0.002=2.000$, bilkul galat (true value $1.667$).

Route B — WITH pivoting.

1. Pehle swap karo. Yeh step kyun? Partial pivoting column 1, rows 1–2 scan karta hai: $|3|>|0.002|$, toh sabse bada upar aata hai. Yahi baat hai — tiny entry se kabhi divide mat karo. $\left[\begin{array}{cccc}3& 1& |& 7\\ 0.002& 4& |& 8\end{array}\right].$
2. Multiplier. Kyun: $(2,1)$ entry ko zero karne ke liye. $m_{21}=0.002/3=0.0006667$ (tiny magnitude ⇒ tiny error amplification).
3. Eliminate karo, 4 sig figs par round karte hue. $a_{22}=4-0.0006667(1)=3.999$; $b_2=8-0.0006667(7)=7.995$.
4. Back-substitute karo. Bottom-up kyun: row 2 ab ek hi unknown hai. $x_2=7.995/3.999=1.999$; $x_1=(7-1(1.999))/3=5.001/3=1.667$.

Verify karo: exact solution mein $x_1\approx 1.6668$ hai. Numerically, eq 1 with $(1.667,1.999)$: $0.002(1.667)+4(1.999)=0.003334+7.996=7.999\approx 8✓$. Pivoting ne $x_1$ bachaya; no-pivoting ne use barbaad kar diya. Dekho Round-off Error in Floating Point aur Condition Number and Numerical Stability.

---

Ex 4 — Cell C4: negative pivots aur negative multipliers

Forecast: $|-4|>|3|$, toh koi swap nahi; pivot negative hai — signs dekho.

1. Scan karo. Kyun: $|-4|=4>3=|3|$, sabse bada already upar. Koi swap nahi. Pivot $-4$ hai; negative theek hai — sirf small magnitude buri hoti hai.
2. Multiplier. $m_{21}=a_{21}/a_{11}=3/(-4)=-0.75$. Minus kyun matter karta hai: ek negative multiple subtract karne ka matlab hai hum effectively add kar rahe hain. Sign attached rakho.
3. Eliminate karo. Row${}_2\leftarrow$Row${}_2-(-0.75)\cdot$Row${}_1$: $a_{22}=-5-(-0.75)(2)=-5+1.5=-3.5,b_2=-1-(-0.75)(2)=-1+1.5=\mathrm{0.5.}$
4. Back-substitute karo. $x_2=\frac{0.5}{-3.5}=-\frac{1}{7}\approx -0.1429,x_1=\frac{2-2x_2}{-4}=\frac{2-2(-1/7)}{-4}=\frac{2+2/7}{-4}=\frac{16/7}{-4}=-\frac{4}{7}\approx -\mathrm{0.5714.}$

Verify karo: eq 2: $3(-4/7)-5(-1/7)=-12/7+5/7=-7/7=-1✓$.

---

Ex 5 — Cell C5: ek literal zero pivot jo swap se bach jaata hai

Forecast: $a_{11}=0$ — tum isse divide nahi kar sakte. Lekin neeche ek nonzero entry hai, toh swap bachata hai. Pivoting yeh automatically handle karta hai.

1. Column 1 scan karo. Yeh step kyun? Rows 1–2 dete hain $|0|$ vs $|3|$. Sabse bada $3$ row 2 mein hai — swap karo. Wo rule jo hamesha sabse badi magnitude chunti hai kabhi nahi diagonal par $0$ chhodti jab neeche koi nonzero ho. $\left[\begin{array}{cccc}3& 1& |& 5\\ 0& 2& |& 4\end{array}\right].$
2. Lucky elimination. $m_{21}=0/3=0$: row 2 already clear hai. Kyun: swap ne saara kaam kar diya.
3. Back-substitute karo. $x_2=\frac{4}{2}=2,x_1=\frac{5-1(2)}{3}=1.$

Verify karo: original eq 1: $0(1)+2(2)=4✓$; eq 2: $3(1)+1(2)=5✓$.

---

Ex 6 — Cell C6: genuinely singular (no solution)

Forecast: row 2 row 1 ka lagbhag aadha hai — left sides proportional hain lekin right sides nahi. Guess: no solution (parallel lines).

1. Scan / no swap. $|2|>|1|$, pivot $=2$.
2. Eliminate karo. $m_{21}=1/2=0.5$: $a_{22}=2-0.5(4)=0,b_2=5-0.5(6)=2.$ $\left[\begin{array}{cccc}2& 4& |& 6\\ 0& 0& |& 2\end{array}\right].$
3. Bottom row padho. Yeh step kyun? Last row kehti hai $0\cdot x_1+0\cdot x_2=2$, yaani $0=2$ — impossible. Poora column-2 sub-block zero ho gaya, toh koi pivot nahi aur RHS nonzero hai ⇒ koi solution nahi.

Verify karo: $\det A=2\cdot 2-4\cdot 1=0$, singularity confirm karta hai — dekho Determinants aur kyun Cramer's Rule bhi yahan fail hota hai (woh $\det A=0$ se divide karta hai).

Do lines parallel hain aur alag — kabhi cross nahi karti, yahi "$0=2$" ka geometric chehra hai.

---

Ex 6′ — Cell C6′: singular with infinitely many solutions

Forecast: ab row 2 row 1 ka exactly aadha hai — ek hi line do baar. Guess: ek line par infinitely many solutions.

1. Scan / no swap. Kyun: column 1 mein $|2|>|1|$ hai, pivot $=2$ already upar.
2. Eliminate karo. Yeh step kyun? $(2,1)$ mein zero punch karo. $m_{21}=1/2=0.5$: $a_{22}=2-0.5(4)=0,b_2=3-0.5(6)=0.$ $\left[\begin{array}{cccc}2& 4& |& 6\\ 0& 0& |& 0\end{array}\right].$
3. Bottom row padho. Yeh step kyun? Ab kehti hai $0=0$ — hamesha sach, koi information nahi. Toh $x_2$ ek free variable hai: koi bhi value choose karo $x_2=s$.
4. Free variable ke saath back-substitute karo. Kyun: row 1 abhi bhi $x_1$ ko $s$ ke terms mein constrain karta hai. $2x_1+4s=6$ se: $x_1=\frac{6-4s}{2}=3-2s,x_2=s,s\in \mathbb{R}.$ Infinitely many solutions, har $s$ ke liye ek.

Verify karo: $s=0$ rakho: $(3,0)$ deta hai $2(3)+4(0)=6✓$ aur $1(3)+2(0)=3✓$. $s=1$ rakho: $(1,1)$ deta hai $2(1)+4(1)=6✓$ aur $1(1)+2(1)=3✓$. Dono ek hi shared line par lie karte hain.

---

Ex 7 — Cell C7: ek real word problem (mixtures, units ke saath)

Forecast: total volume 10 L, toh guess hai A bada share hai (32% 20% ke kareebi hai).

1. System mein translate karo. Yeh step kyun? $x_1$ = litres of A, $x_2$ = litres of B. Volume balance aur acid balance dete hain $\{\begin{array}{l}{x}_1+x_2=10\\ 0.20x_1+0.50x_2=0.32\times 10=3.2\end{array}\Rightarrow \left[\begin{array}{cccc}1& 1& |& 10\\ 0.2& 0.5& |& 3.2\end{array}\right].$
2. Pivot check karo. Yeh step kyun? Column 1, rows 1–2 scan karo: $|1|>|0.2|$, toh sabse bada already upar hai — koi swap nahi, pivot $=1$.
3. Eliminate karo. Yeh step kyun? Hume position $(2,1)$ mein $0$ chahiye taaki row 2 sirf ek unknown rakhe. $m_{21}=0.2/1=0.2$; phir $a_{22}=0.5-0.2(1)=0.3$, $b_2=3.2-0.2(10)=1.2$.
4. Back-substitute karo. Bottom-up kyun: row 2 ab sirf $x_2$ hai. $x_2=\frac{1.2}{0.3}=4\text{ L (B)},x_1=10-4=6\text{ L (A)}.$

Verify karo (units + acid): total $6+4=10$ L $✓$. Acid: $0.2(6)+0.5(4)=1.2+2.0=3.2$ L, aur $3.2/10=32\%✓$. Forecast ke anusaar, A bada share hai.

---

Ex 8 — Cell C8: parameter ke saath exam twist (limiting behaviour)

Forecast: elimination ke baad ek special $t$ ke liye zero pivot appear hoga. Guess $t=4$.

1. Pivot honestly karo — swap forced hai. Yeh step kyun? Column 1, rows 1–2 scan karo: har $t$ ke liye $|2|>|1|$ (column 1 mein $t$ nahi hai). Partial pivoting isliye kuch karne se pehle rows 1 aur 2 swap karta hai — hum $1$ ka pivot assume nahi kar sakte. $\left[\begin{array}{cccc}2& t& |& 7\\ 1& 2& |& 3\end{array}\right].$
2. Symbolically eliminate karo. Yeh step kyun? $(2,1)$ mein $0$ punch karo; resulting $(2,2)$ entry batata hai kab method ruk jaata hai. Pivot $=2$, toh $m_{21}=1/2$: $a_{22}=2-\frac{1}{2}t=2-\frac{t}{2},b_2=3-\frac{1}{2}(7)=-\frac{1}{2}.$ $\left[\begin{array}{cccc}2& t& |& 7\\ 0& 2-\frac{t}{2}& |& -\frac{1}{2}\end{array}\right].$
3. Failure dhundho. Yeh step kyun? Back-substitution $a_{22}=2-\frac{t}{2}$ se divide karta hai. Yeh zero hota hai jab $2-\frac{t}{2}=0$, yaani $\boxed{t=4}$. Tab bottom row kehti hai $0=-\frac{1}{2}$ ⇒ koi unique solution nahi. Yahi parameter ki limiting value hai (aur wakai $\det A=1\cdot t-2\cdot 2=t-4$ wahin vanish hota hai).
4. $t=6$ ke liye solve karo. Yeh step kyun? Concrete value ko eliminated system mein plug karo taaki dono unknowns follow ho sakein. Yahan $a_{22}=2-\frac{6}{2}=-1$: $x_2=\frac{-1/2}{-1}=\frac{1}{2}=0.5,x_1=\frac{7-6x_2}{2}=\frac{7-3}{2}=2.$

Verify karo: $t=6$ par, original eq 2: $2(2)+6(0.5)=4+3=7✓$; eq 1: $1(2)+2(0.5)=3✓$. $t=4$ par, $\det A=t-4=0$ — bilkul predict ke anusaar singular.

---

Recall Poora matrix ek saansi mein

Baseline (C1) ::: sabse bada pivot already upar, bas eliminate karo aur wapas chadho. Forced swap (C2) ::: sabse bada entry neeche hai — pehle poori rows swap karo. Tiny pivot (C3) ::: pivoting ek monster multiplier se bachata hai jo round-off barbaad kar deta. Negative pivot (C4) ::: negative theek hai; sirf small magnitude dushman hai — multiplier ka sign rakho. Zero pivot, fixable (C5) ::: neeche nonzero tumhe bachata hai; pivoting yeh automatically karta hai. Singular, no solution (C6) ::: last row $0=c$ ban jaati hai with $c\ne 0$ ($\det A=0$). Singular, infinitely many (C6′) ::: last row $0=0$ ban jaati hai ⇒ free variable. Word problem (C7) ::: unknowns name karo, har balance law ke liye ek equation likho, phir solve karo. Parameter twist (C8) ::: forced swap ke baad pivot-2 entry $2-t/2$ hai; $t=4$ par vanish hoti hai.

Dekho bhi LU Decomposition (elimination ek factorisation ki tarah yaad kiya jaata hai), Back-substitution and Forward-substitution, aur Iterative Methods (Jacobi, Gauss-Seidel) jab $n$ bahut bada ho.