Solving linear systems — Gaussian elimination with partial pivoting: Visual walkthrough

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

Definition Grid ke andar ek number ko hum kya kehte hain

Kisi bhi formula se pehle, naming rule ek baar ke liye fix kar lo. Numbers ki ek grid (ek matrix) ko ek capital letter se likha jaata hai jaise $A$ . Uske andar ek number ko $a_{ij}$ likha jaata hai jisme do chhote labels hote hain:

pehla label $i$ = kaun si row (upar se neeche ginne par, $1, 2, \dots, n$ ),
doosra label $j$ = kaun sa column (left se right ginne par, $1, 2, \dots, n$ ).

Toh $a_{21}$ ka matlab hai "row 2, column 1" (ek $2 \times 2$ block mein bottom-left). Letter $n$ = kitni rows hain, jo yahan columns ki sankhya aur unknowns ki sankhya ke barabar hai. Right-hand-side column ek list $b$ hai jiske entries mein ek label hota hai: $b_{i}$ = row $i$ ka answer-number. Yeh picture — row pehle, column baad mein — apne dimaag mein rakho har box ke liye neeche.

Step 1 — Equations ka system picture mein kaisa dikhta hai?

KYA HAI. Ek linear system equations ka ek set hota hai jahan har unknown akele appear karta hai, ek saadhe number se multiply hoke (koi squares nahi, unknowns ke products nahi). Hum do likhte hain:

coefficient of x_{1} 2 x_{1} + coefficient of x_{2} 1 x_{2} = right-hand side b_{1} 8

PICTURE KYUN ZAROORI HAI. Do unknowns wali har equation plane mein ek straight line hoti hai. System solve karne ka matlab hai woh single point $(x_{1}, x_{2})$ dhoondna jo dono lines par ek saath ho — jahan woh cross karti hain.

PICTURE. Do lines, ek blue, ek orange; green dot jahan woh milti hain woh solution $x$ hai. Woh crossing point hi woh ek cheez hai jo hum dhundh rahe hain.

Figure — Solving linear systems — Gaussian elimination with partial pivoting

Step 2 — Woh ek move jo answer kabhi nahi badalta

KYA HAI. Rows par exactly teen moves allowed hain, jinhein elementary row operations kehte hain: (1) do rows swap karo, (2) row ko ek nonzero number se scale karo, (3) ek row ka multiple doosri row mein add karo. Show ka star move (3) hai:

Row_{i} \leftarrow Row_{i} - m \cdot Row_{k} .

Ise zor se padho: "naya row $i$ hai purana row $i$ minus $m$ copies of row $k$ ." Yahan $m$ sirf koi number hai jo hum choose kar sakte hain.

YEH LEGAL KYUN HAI. Har row ek line hai. Move (3) line $i$ ko tilt karta hai lekin use usi crossing point se guzarta rakhta hai, kyunki solution par dono equations already hold karti hain, toh unka koi bhi combination wahan bhi hold karega.

PICTURE. Orange line rotate karti hai jab hum $m$ change karte hain, lekin woh green solution dot ke around pivot karti hai — intersection kabhi nahi hilta. Yahi invariance hai jo aage aane wali har cheez ka licence hai.

Step 3 — $m$ aise choose karna ki ek number zero ho jaaye

KYA HAI. Hum doosri equation se pehla unknown $x_{1}$ erase karna chahte hain — yaani bottom-left number ko $0$ banana chahte hain. Naming rule use karte hue, pivot (top-left) entry $a_{11}$ hai (row 1, column 1) aur jise hum kill karna chahte hain woh $a_{21}$ hai (row 2, column 1). Move ke baad, naya bottom-left entry hai:

what we want gone a_{21} - m \cdot the pivot a_{11} .

Ise zero set karo aur $m$ ke liye solve karo:

a_{21} - m a_{11} = 0 ⟹ m = \frac{a _{21}}{a _{11}} .

DIVIDE KYUN KARTE HAIN. $m$ ki woh ek hi value jo $a_{21}$ ko exactly cancel kare woh hai "pivot $a_{21}$ mein kitni baar fit hota hai" — yeh ek division hai. Is $m$ ko multiplier kehte hain.

PICTURE. $a_{21}$ ki height ka ek vertical bar $a_{11}$ ki height ke bar ke paas; fraction $m$ woh scaling factor hai jo $m \cdot a_{11}$ ko exactly $a_{21}$ ke saath line up karta hai, toh unka difference flush zero ho jaata hai.

Step 4 — Pivot tiny kyun nahi hona chahiye (pivoting ki poori wajah)

KYA HAI. $m = a_{21} / a_{11}$ ko phir se dekho. Pivot $a_{11}$ denominator mein hai. Agar $a_{11}$ ek tiny number ho jaise $0.0003$ , toh $m$ enormous ho jaata hai.

YEH DANGEROUS KYUN HAI. Ek bada $m$ subtract karne se pehle pivot row ki har entry ko multiply karta hai. Tumhara calculator sirf fixed number of digits rakhta hai (dekho Round-off Error in Floating Point), toh ek bada multiplier chhoti rounding smudges ko bade errors mein badal deta hai — answer kharab ho jaata hai. Yeh parent note ke cautionary $0.0003$ example ki kahani hai.

PICTURE. $m$ ki do curves pivot size ke against: jaise pivot zero ki taraf shrink hota hai, $m$ ek vertical wall par shoot karta hai. Red danger zone woh tiny-pivot region hai jise hum avoid karna chahte hain.

Definition Partial pivoting

Column $k$ erase karne se pehle, us column mein rows $k, k + 1, \dots, n$ mein neeche dekho aur woh entry dhundho jiska largest absolute value ho. Is search ko hum aise likhte hain: $p = ar g max_{i \geq k} ∣ a_{ik} ∣.$ $ar g max$ ko literally padho: "woh argument (yahan, row index $i$ ) jo baad wali cheez ko maximise karta hai." Toh $arg max$ biggest value $∣ a_{ik} ∣$ nahi return karta — yeh return karta hai kaun si row mein woh biggest value hai. Us jeetne wali row ko $p$ naam dete hain. Phir hum row $k$ ko row $p$ se swap karte hain, strong entry ko diagonal par le aate hain taaki woh pivot ban jaaye. Ab pivot available sabse bada number hai, toh har multiplier $∣ m_{ik} ∣ \leq 1$ satisfy karta hai — koi monster amplification nahi. "Partial" ka matlab hai hum sirf ek column mein neeche search karte hain, kabhi row ke across nahi.

Step 5 — Swap, ek picture mein

KYA HAI. System mein $[2 - 3 1 - 1 8 - 11]$ column 1 mein $∣2∣$ aur $∣ - 3∣$ hain. Badi magnitude $∣ - 3∣ = 3$ hai, jo row 2 mein hai. Toh yahan winning row $p = 2$ hai: partial pivoting kehta hai row $k = 1$ aur row $p = 2$ ko swap karo taaki strong pivot upar aa jaaye.

$[- 3 2 - 1 1 - 11 8] .$

POORI ROW KYUN. Ek row ek complete equation hoti hai. Agar tum sirf uska kuch hissa swap karo, tum do alag equations mix kar doge — garbage. Bar samet, hamesha.

PICTURE. Do horizontal row-blocks ek curved arrow ke saath places exchange karte hue; strong pivot $- 3$ (green) diagonal par utha, weak $2$ (gray) neeche aa gaya agle step mein eliminate hone ke liye.

Step 6 — Eliminate: zero appear hota dekho

KYA HAI. Pivot $a_{11} = - 3$ aur target $a_{21} = 2$ ke saath, multiplier hai $m_{21} = \frac{2}{- 3} = - \frac{2}{3} \approx - 0.667.$

Ab row 2 = row 2 $- m_{21} \cdot$ row 1 update karo, har column (pehle exact fractions, phir decimal):

a_{21} a_{22} b_{2} : 2 - (- \frac{2}{3}) (- 3) = 0 (the target zero), : 1 - (- \frac{2}{3}) (- 1) = \frac{1}{3} \approx 0.333, : 8 - (- \frac{2}{3}) (- 11) = \frac{2}{3} \approx 0.667.

$[- 3 0 - 1 \frac{1}{3} - 11 \frac{2}{3}] .$

YEH KYUN KAAM KARTA HAI. Construction se $m_{21}$ isi liye choose kiya gaya tha taaki pehli entry vanish ho; baaki entries bas saath aa jaati hain.

PICTURE. Bottom row pehle aur baad mein: leading number $0$ mein melt ho jaata hai (red → gray), aur row ek aisi equation ban jaati hai sirf $x_{2}$ mein akele. Woh staircase ban rahi hai.

Step 7 — Wapas upar chad (back-substitution)

KYA HAI. Bottom equation ab padhti hai $\frac{1}{3} x_{2} = \frac{2}{3}$ , jisme ek unknown hai. Ise solve karo, phir upar wali row mein jao aur jaani hui value plug in karo.

x_{2} = \frac{2/3}{1/3} = 2, x_{1} = \frac{b _{1} - a _{12} x _{2}}{a _{11}} = \frac{- 11 - ( - 1 ) ( 2 )}{- 3} = 3.

Yahan $a_{12} = - 1$ (row 1, column 2) top row mein already-known $x_{2}$ ka coefficient hai, toh bracket $b_{1} - a_{12} x_{2}$ pivot se divide karne se pehle ek pure number hai.

BOTTOM-UP KYUN. Sirf last row ek one-unknown equation hoti hai. Pehle use solve karo, phir har upar wali row mein exactly ek naya unknown bachta hai. Top-down jaane par unknowns bracket mein trapped rah jaate hain.

PICTURE. Ek literal staircase: bottom step solved hai ( $x_{2} = 2$ ), ek upar wala arrow woh value top step mein le jaata hai, jo phir $x_{1} = 3$ deta hai. Check karo: top equation $- 3 (3) - 1 (2) = - 11$ . ✓

Step 8 — Degenerate case: jab column saara zeros ho

KYA HAI. Maano kisi step par column $k$ mein har candidate entry (rows $k$ se $n$ tak) $0$ hai. Toh swap karne ke liye kuch nahi hai: available sabse badi magnitude $0$ hi hai, toh pivot unavoidably $0$ hai. Matrix $A$ tab singular hai — dekho Determinants aur Condition Number and Numerical Stability.

YEH DO PICTURES MEIN KYUN SPLIT HOTA HAI. Zero pivot ka matlab hamesha "koi answer nahi" nahi hota. Dekho ki offending row elimination ke baad kya kehti hai. Uske left mein all-zero coefficients hain, toh woh padhi jaati hai $0 = c_{i}$ kisi number $c_{i}$ ke liye. Do bahut alag cheezein ho sakti hain:

Coincident lines (infinitely many solutions): row ban gayi $0 = 0$ . Yeh ek sach-lekin-khali statement hai jo koi nayi information nahi deti. Do equations ek hi line thi. Woh unknown jisne apna pivot khoya woh ek free variable ban jaata hai — tum use koi bhi value $t$ set kar sakte ho, aur baaki unknowns follow karte hain. Answer points ki puri ek line hai, likha jaata hai jaise $x_{1} = 5 - t, x_{2} = t$ .
Inconsistent (no solution): row ban gayi $0 = (nonzero)$ , jaise $0 = 4$ . Yeh ek seedha jhooth hai — koi numbers ise sach nahi bana sakte. Lines parallel par alag hain aur kabhi cross nahi karti.

DETECT KAISE KAREIN. Forward elimination ke baad, koi bhi aisi row dhundho jiska left part all zeros ho: agar uska $c_{i} = 0$ hai toh yeh ek free variable signal karta hai (coincident); agar $c_{i} \neq = 0$ hai toh yeh inconsistency signal karta hai (no solution).

PICTURE. Left panel: do coincident lines ek doosre ke bilkul upar — har point ek solution hai, free variable unke saath slide karta hai. Right panel: do parallel lines alag alag — koi crossing nahi, " $0 =$ nonzero" ka contradiction.

Ek-picture summary

KYA HAI. Ek figure poori journey compress karti hui: ek full square block $[A ∣ b]$ se shuru karo; partial pivoting biggest entry ko diagonal par le aata hai (green); elimination below-diagonal region ko zeros se paint karta hai (gray triangle), $A$ ko triangular $U$ mein aur $b$ ko $c$ mein badal deta hai; back-substitution staircase par neeche se chadhta hai aur $x$ reveal karta hai. Yeh exactly woh machinery hai jo LU Decomposition aur Back-substitution and Forward-substitution ke twin routines ke peeche hai.

Recall Feynman: poora walkthrough saadhe shabdon mein

Socho ek stack of number-rows ka, har ek sach mein ek equation. Do equations paper par do lines hain, aur answer wahan hai jahan woh cross karti hain. Pehli trick: mujhe ek row doosri se jitni baar chahun subtract karne ki permission hai — yeh ek line ko tilt karta hai lekin use crossing point se guzarta rakhta hai, toh answer kabhi nahi hiltaa. Main us trick ka use karta hun neeche wali rows se pehla variable erase karne ke liye: main bilkul sahi amount subtract karta hun, aur exact amount hai "woh number jo mujhe hatana hai divided by diagonal par wala number." Lekin ek tiny diagonal number se divide karna ek giant multiplier banata hai, aur ek giant multiplier mere calculator ke thode se digits ko bade errors mein smear kar deta hai aur answer kharab kar deta hai — toh divide karne se pehle main column mein neeche dekhta hun, sabse bada number pakadta hun, aur uski poori row ko upar swap kar deta hun. Sabse bada pivot ka matlab hai multiplier kabhi ek se bada nahi hoga, toh kuch bhi explode nahi karta. Column by column repeat karo jab tak block ek triangle of numbers na ban jaaye jisme lower-left mein zeros hon — woh triangle $U$ hai, aur right-hand side jo woh saath kheench ke laaya woh $c$ hai. Ab bottom equation mein sirf ek unknown hai — use solve karo — phir ek row upar jao, abhi jo mila woh plug in karo, agla solve karo, aur chadhte raho. Agar kabhi diagonal ke neeche ka poora column all zeros ho, toh koi pivot nahi pakadna: agar bachi hui row $0 = 0$ kehti hai toh do lines same hain aur ek variable free hai (answers ki poori line); agar woh $0 =$ koi nonzero number kehti hai, toh lines parallel hain aur koi answer hi nahi. Yeh hai Gaussian elimination with partial pivoting, start se finish tak.

Recall

Forward elimination ke baad, matrix kis shape mein hoti hai, aur use hum kya kehte hain? ::: Upper-triangular — diagonal ke neeche har jagah zeros; us triangular block ko hum $U$ kehte hain aur uske transformed right-hand side ko $c$ . Pivot column mein largest-magnitude entry kyun honi chahiye? ::: Tiny pivot huge multiplier banata hai jo round-off error amplify karta hai; sabse bada pivot har $∣ m_{ik} ∣ \leq 1$ rakhta hai. Step 6 mein, kaun se multiplier ne pivot $- 3$ ke neeche entry $2$ ko zero kiya? ::: $m_{21} = 2/ (- 3) = - \frac{2}{3} \approx - 0.667$ (decimal rounded hai). $2 \times 2$ walkthrough ne kaun sa solution diya? ::: $x_{1} = 3, x_{2} = 2$ . Zero pivot ke saath leftover row $0 = 0$ ka matlab kya hai? ::: Coincident equations — ek free variable aur infinitely many solutions (ek poori line). Zero pivot ke saath leftover row $0 =$ nonzero ka matlab kya hai? ::: Ek inconsistent system — parallel lines, koi solution nahi.