Gaussian elimination — forward elimination, back substitution: Visual walkthrough

4.5.9 · D2 · Maths › Linear Algebra (Full) › Gaussian elimination — forward elimination, back substitutio

Hum is exact system ko poora solve karenge: $2 x + y - z - 3 x - y + 2 z - 2 x + y + 2 z = 8 = - 11 = - 3$

Isse chhune se pehle, chalte hain ensure karte hain ki har symbol samajh mein aaye.

Step 0 — Symbols ko padhna (kuch bhi assume nahi)

Figure dekho: left panel mein messy word-equations hain, right panel mein tidy grid hai. Wahi information, kam ink.

Step 1 — Target shape: zeros ki staircase

YEH shape hi kyun, koi aur nahi? Kyunki ek triangular system ek variable ek time par read ki ja sakti hai. Bottom row mein sirf $z$ hoga; middle row mein sirf $y$ aur $z$ ; top row mein teeno. Woh staircase hi poora payoff hai.

PICTURE. Figure mein amber staircase diagonal trace karti hai; cyan shaded region mein uske neeche sab kuch $0$ ho jaana chahiye. Agli steps mein hamara kaam us region ko zeros se bharna hai bina answer change kiye.

Step 2 — Column 1 mein pehle pivot ke neeche clear karo

Target $- 3$ (Row 2). Multiplier: $m_{21} = \frac{a _{21}}{a _{11}} = \frac{- 3}{2} = - \frac{3}{2} .$ $R_{2} \to R_{2} - (- \frac{3}{2}) R_{1} = R_{2} + \frac{3}{2} R_{1}$ karo. Naya pehla entry: $old target - 3 - m_{21} (- \frac{3}{2}) \cdot pivot 2 = - 3 + 3 = 0. ✓$

Target $- 2$ (Row 3). Multiplier: $m_{31} = \frac{- 2}{2} = - 1, R_{3} \to R_{3} - (- 1) R_{1} = R_{3} + R_{1} .$ Naya pehla entry: $- 2 - (- 1) (2) = - 2 + 2 = 0. ✓$

Grid ban jaata hai: $200 1 \frac{1}{2} 2 - 1 \frac{1}{2} 1 815$

YEH safe kyun hai: ek true equation ka multiple doosri mein add karna dono ko true rakhta hai aur reversible hai — solution set kabhi nahi hilta.

PICTURE. Figure mein do amber arrows pivot row se neeche Rows 2 aur 3 mein fire karte hain; red targets $0$ par snap ho jaate hain. Column 1 ab pivot ke neeche clean hai.

Step 3 — Column 2 mein doosre pivot ke neeche clear karo

Multiplier: $m_{32} = \frac{a _{32}}{a _{22}} = \frac{2}{\frac{1}{2}} = 4, R_{3} \to R_{3} - 4 R_{2} .$ Target check karo: $target 2 - m_{32} 4 \cdot pivot \frac{1}{2} = 2 - 2 = 0. ✓$

Poori row karo taaki RHS bhi saath chale:

column 3: $1 - 4 \cdot \frac{1}{2} = 1 - 2 = - 1$
RHS: $5 - 4 \cdot 1 = 1$

$200 1 \frac{1}{2} 0 - 1 \frac{1}{2} - 1 811$

Is baar sirf ek arrow kyun? Kyunki column 1 clear hone ke baad, Row 3 mein pehle se $0$ tha jahan uska purana $x$ -coefficient tha. Hum sirf un entries se ladte hain jo current pivot ke neeche abhi bhi nonzero hain.

PICTURE. Row 2 se Row 3 mein ek single amber arrow. Poora cyan under-diagonal region ab zeros hai — staircase ban gayi.

Recall Hum entries

diagonal ke upar kabhi kyun nahi chhute Forward elimination sirf pivots ke neeche zero karta hai. Upar ka hissa messy reh sakta hai — back substitution use handle karega. Upar bhi clear karna ek alag (zyada expensive) method hai jise Gauss–Jordan kehte hain, jo Reduced Row Echelon Form ki taraf jaata hai.

Step 4 — Bottom row padho: pehla unknown nikalta hai

Bottom row $00 - 1 ∣ 1$ ka matlab hai: $- 1 \cdot z = 1 ⟹ z = \frac{1}{- 1} = - 1.$

$- 1$ = pivot $u_{33}$ .
$1$ = RHS $c_{3}$ .
RHS ko pivot se divide karo: $z = c_{3} / u_{33}$ .

Yahan se kyun shuru karo? Koi aur row itni simple nahi hai. Upar ki har row ab bhi do ya teen unknowns mix karti hai. Bottom woh akela door hai jo ek key se khulta hai.

PICTURE. Bottom row amber glow karti hai; right par ek single value $z = - 1$ pop out karti hai. Rows upar dimmed hain — abhi unki baari nahi.

Step 5 — Ek row upar chadhho: known substitute karo, naya solve karo

Row 2 $0 \frac{1}{2} \frac{1}{2} ∣ 1$ padha jaata hai: $\frac{1}{2} y + \frac{1}{2} z = 1.$ $z = - 1$ substitute karo: $\frac{1}{2} y + \frac{1}{2} (- 1) = 1 ⟹ \frac{1}{2} y - \frac{1}{2} = 1 ⟹ \frac{1}{2} y = \frac{3}{2} ⟹ y = 3.$

$\frac{1}{2}$ = pivot $u_{22}$ .
$\frac{1}{2} z$ = already-known part; ise right side par push karo.
Jo bacha, $\frac{1}{2} y = \frac{3}{2}$ , seedha divide hoke $y = 3$ deta hai.

Upar jaate hue yeh hamesha kyun kaam karta hai: har step upar bilkul ek fresh unknown add karta hai, aur uske right ka sab kuch pichhle step mein solve ho chuka tha. Ek naya unknown, ek equation — hamesha solvable.

PICTURE. Value $z = - 1$ Step 4 se Row 2 mein slide hoti hai (amber trail), aur $y = 3$ emerge hota hai.

Step 6 — Top row: aakhri unknown

Row 1 $21 - 1 ∣ 8$ padha jaata hai: $2 x + y - z = 8.$ $y = 3, z = - 1$ substitute karo: $2 x + 3 - (- 1) = 8 ⟹ 2 x + 4 = 8 ⟹ 2 x = 4 ⟹ x = 2.$

Answer: $x = 2, y = 3, z = - 1$ .

Sanity check ek original equation par (jo humne sabse zyada change ki): $- 3 x - y + 2 z = - 3 (2) - 3 + 2 (- 1) = - 6 - 3 - 2 = - 11. ✓$

PICTURE. Teeno solved values top row mein feed hoti hain; $x = 2$ nikalta hai; ek final green tick check confirm karta hai.

Step 7 — Degenerate cases jinse tum kabhi hairan mat hona

Elimination sirf solve nahi karta — yeh diagnose bhi karta hai. Bottom row ke saath teen cheezein ho sakti hain.

Beech mein zero pivot swap kyun force karta hai. Agar pivot slot khud $0$ hai, toh multiplier $a_{ik} / a_{k k}$ zero se divide karega. Fix: ek lower row swap karo jo us column mein nonzero entry rakhti ho (yeh partial pivoting hai). Agar koi bhi lower row mein woh na ho, toh us column mein koi pivot nahi — uska variable free hai.

PICTURE. Teen mini-staircases side by side: unique (amber pivot, tick), inconsistent (amber $0 = d$ , cross), infinite (amber $0 = 0$ , ek arrow labelled "free variable").

Common mistake Trap: bottom row galat padhna

Zeros ki row jisme RHS $0$ ho woh "no solution" nahi hai — yeh ulta hai, infinitely many. Killer woh hai jisme zero row ka nonzero RHS ho. Loud bolke kaho: " $0 = d$ ? Impossible." Wahi akela inconsistency signal hai.

Recall Yeh cases kahan connect hote hain

Nonzero pivots ki count rank hai. $A$ ki rank ko $[A ∣ b]$ ki rank se compare karo ending decide karne ke liye — Solving Linear Systems — Consistency mein spell out hai. Aur pivots ka product Determinant deta hai (zero determinant ⇔ missing pivot ⇔ unique solution nahi).

Ek-picture summary

Upar sab kuch, ek single staircase par: NEECHE columns mein zeros plant karo (forward elimination), phir UPAR rows mein unknowns read karo (back substitution).

Recall Poore walkthrough ki Feynman retelling

Tumhare paas teen pahelia hain, har ek teen secret numbers mix karti hai. Pehle unhe ek grid mein tidy karo taaki baar baar $x, y, z$ likhna band ho. Phir neeche jao: top paheli lo, uski ek copy scale karo, aur neeche wali paheli se subtract karo taaki woh pehla secret bhool jaaye — column by column karo jab tak last paheli sirf ek secret mention kare. Woh bottom paheli tum sight par solve kar lete ho. Ab muddo aur upar jao: woh answer upar wali paheli mein plug karo, jo phir sirf ek naya secret mention karti hai — solve karo, chadhho, repeat karo. Top par pahunchte pahunchte teeno pata hain, aur unhe ek original paheli mein plug karo confirm karne ke liye. Agar kahin bottom paheli "zero equals five" ban jaaye, kisi ne jhooth bola — no solution. Agar "zero equals zero" ban jaaye, ek clue missing hai — infinitely many answers. Zeros plant karne ke liye neeche, answers padhne ke liye upar. Wahi poora trick hai.

Recall checkpoint

Back substitution bottom row se kyun shuru hoti hai?

Staircase ki sirf bottom row mein ek single unknown hota hai; upar ki har row ab bhi kai unknowns mix karti hai.

Step 3 mein

m_{32} = 4

kyun hai?

Kyunki

m_{32} = a_{32} / a_{22} = 2/ (1/2) = 4

, pivot rows ki woh number jo target

2

ko cancel karti hai.

Staircase ki last row

000 ∣ d

hai jahan

d \neq = 0

— matlab?

Inconsistent — no solution (yeh kehta hai

0 = d

Staircase ki last row sab zeros

000 ∣ 0

hai — matlab?

Ek free variable — infinitely many solutions.

Zero pivot ko kaunsa operation replace karta hai?

Ek row swap (partial pivoting) jo us column mein nonzero entry wali lower row upar laata hai.

Connections

LU Decomposition — Steps 2–3 mein humne jo multipliers $m_{ik}$ compute kiye woh hain $L$ ki entries.
Row Echelon Form / Reduced Row Echelon Form — woh staircase jo humne banai (aur woh tidier wali jo Gauss–Jordan banata hai).
Pivoting and Numerical Stability — Step 7 ka zero-pivot swap, generalised.
Rank of a Matrix — amber pivots gino.
Determinant — pivots multiply karo.
Solving Linear Systems — Consistency — Step 7 ke teen endings ke peeche poora logic.