Gaussian elimination — forward elimination, back substitution

4.5.9 · Maths › Linear Algebra (Full)

Hum actually kya solve kar rahe hain?

Forward elimination — staircase banana

HOW (multiplier formula). Entry $a_{ik}$ jo pivot $a_{k k}$ ke neeche hai use clear karne ke liye, multiplier chuno: $m_{ik} = \frac{a _{ik}}{a _{k k}}$ phir karo $R_{i} \to R_{i} - m_{ik} R_{k}$ .

Figure — Gaussian elimination — forward elimination, back substitution

Back substitution — wapas upar chadna

Worked Example 1 — ek clean $3 \times 3$

Solve karo: $2 x + y - z - 3 x - y + 2 z - 2 x + y + 2 z = 8 = - 11 = - 3$

Augmented matrix: $2 - 3 - 2 1 - 1 1 - 1 22 8 - 11 - 3$

Step A. Pivot $a_{11} = 2$ . Column 1 clear karo.

$m_{21} = - 3/2$ , toh $R_{2} \to R_{2} - (- \frac{3}{2}) R_{1}$ . Kyun? Isse $- 3$ zero ho jaata hai.
$m_{31} = - 2/2 = - 1$ , toh $R_{3} \to R_{3} - (- 1) R_{1} = R_{3} + R_{1}$ . Kyun? $- 2$ ko khatam karta hai.

$200 1 \frac{1}{2} 2 - 1 \frac{1}{2} 1 815$

Step B. Pivot $a_{22} = \frac{1}{2}$ . Uske neeche clear karo.

$m_{32} = 2/ (1/2) = 4$ , toh $R_{3} \to R_{3} - 4 R_{2}$ . Kyun? Column 2 mein $2$ ko zero banata hai.

$200 1 \frac{1}{2} 0 - 1 \frac{1}{2} - 1 811$ Ab yeh upper-triangular hai — forward elimination ho gayi.

Back substitution.

Row 3: $- z = 1 \Rightarrow z = - 1$ . Yeh step kyun? Aakhri row mein ek hi unknown hai.
Row 2: $\frac{1}{2} y + \frac{1}{2} z = 1 \Rightarrow \frac{1}{2} y - \frac{1}{2} = 1 \Rightarrow y = 3$ . Kyun? $z$ ab known hai, sirf $y$ bacha.
Row 1: $2 x + y - z = 8 \Rightarrow 2 x + 3 + 1 = 8 \Rightarrow x = 2$ . Kyun? Sirf $x$ baki hai.

Answer: $x = 2, y = 3, z = - 1$ . (Row 2 original check karo: $- 6 - 3 - 2 = - 11$ ✓.)

Worked Example 2 — pivoting zaroori hai

Solve karo: $[012345]$ Step. Pivot position $(1, 1)$ hai $0$ — zero se division! Swap kyun force hota hai? Pivot nonzero hona chahiye. Swap $R_{1} \leftrightarrow R_{2}$ : $[103254]$ Already triangular hai. Back-sub: $2 y = 4 \Rightarrow y = 2$ ; $x + 3 (2) = 5 \Rightarrow x = - 1$ .

Worked Example 3 — no/infinite solutions

$[122437] R_{2} \to R_{2} - 2 R_{1} [102031]$ Row 2 kehti hai $0 = 1$ — impossible, toh system inconsistent hai (koi solution nahi). Elimination yeh kyun reveal karta hai? Yeh $0 =$ nonzero tabhi produce karta hai jab equations contradict hoti hain. Agar aakhri entry $0$ hoti (row $00 ∣ 0$ ), toh hame ek free variable milta aur infinitely many solutions hote.

Common mistake Steel-manned common errors

1. RHS column par operation apply karna bhool jaana. Kyun sahi lagta hai: tum " $A$ ko triangularise karne" par focus karte ho. Fix: hamesha augmented matrix par operate karo; $b$ entry har row ke saath chalti hai.

2. Multiplier mein galat sign. Log $R_{i} \to R_{i} + m R_{k}$ likhte hain $m = a_{ik} / a_{k k}$ ke saath aur galat result paate hain. Kyun sahi lagta hai: "combine karne ke liye add karo." Fix: safe template hai $R_{i} \to R_{i} - \frac{a _{ik}}{a _{k k}} R_{k}$ — minus, kyunki hum unwanted part ko subtract kar rahe hain.

3. Zero pivot se divide karna. Kyun sahi lagta hai: algorithm "sirf columns mein march karta hai." Fix: agar pivot $0$ hai, toh swap karo neeche ki row se; agar us column mein koi nahi, toh agale column par jao (free variable).

4. Back-substitution top-down karna. Kyun sahi lagta hai: hum upar se neeche padhte hain. Fix: triangular structure sirf neeche ek variable isolate karta hai — wahan se shuru karo aur upar chado.

Recall Feynman: ek 12-saal ke bacche ko explain karo

Socho teen dost hain jo riddles ke zariye tumhara secret number jaante hain, lekin har riddle saare clues mix karti hai. Tum pehli riddle rewrite karte ho aur ise doosri se subtract karte ho taaki doosri riddle ab pehle clue ka mention na kare, aur aage bhi aisa karte raho — jab tak aakhri riddle mein sirf ek clue na bache aur tum use seedha padh sako. Phir tum wapas upar jao: "Ab mujhe aakhri number pata hai, main ise plug in karta hun aur pichli riddle agla number reveal karti hai." Chadte raho jab tak sab pata na chal jaye. Bas yahi hai.

Recall checkpoint

Forward elimination kaun si shape produce karta hai?

Upper-triangular matrix

U

(diagonal ke neeche sab zeros).

Pivot

a_{k k}

ke neeche entry

a_{ik}

eliminate karne ka multiplier?

m_{ik} = a_{ik} / a_{k k}

, phir

R_{i} \to R_{i} - m_{ik} R_{k}

R_{i} \to R_{i} - m R_{j}

ek legal operation kyun hai?

Yeh solution set preserve karta hai aur reversible hai (ek sach equation ka multiple add karne se woh sach rehti hai).

Elimination ke dauran row swap kyun force hoti hai?

Zero pivot (isse divide nahi kar sakte); partial pivoting numerical accuracy ke liye bhi badi entry swap karta hai.

x_{i}

ke liye back-substitution formula?

x_{i} = \frac{1}{u _{ii}} (c_{i} - \sum_{j > i} u_{ij} x_{j})

Back substitution mein pehle kaun sa variable solve hota hai?

Aakhri wala,

x_{n} = c_{n} / u_{nn}

, bottom row se.

Elimination ke baad ek row

00 \dots ∣ d

padh rahi hai jahan

d \neq = 0

. Iska kya matlab hai?

System inconsistent hai — koi solution nahi.

Elimination ke baad ek row bilkul zero hai (

0 \dots 0 ∣ 0

). Iska kya matlab hai?

Ek free variable exist karta hai — infinitely many solutions.

Augmented matrix

[A ∣ b]

par operate kyun karte hain?

Taaki row operations right-hand side ko coefficients ke saath consistently transform karein.

Connections

LU Decomposition — multipliers $m_{ik}$ store karne se $A = LU$ milta hai.
Row Echelon Form / Reduced Row Echelon Form — elimination ke goal shapes.
Pivoting and Numerical Stability — practice mein rows kyun swap karte hain.
Rank of a Matrix — pivots ki sankhya = rank.
Determinant — pivots ka product (swaps se sign ke saath) $det A$ deta hai.
Solving Linear Systems — Consistency — no/one/infinite solutions ko interpret karna.