Solving linear systems — Gaussian elimination with partial pivoting

4.8.18 · Maths › Numerical Methods

1. Hum kaunsa problem solve kar rahe hain?

2. Forward elimination — scratch se derive kiya

Hum column $k$ ki diagonal ke neeche zeros chahte hain. Column $k$ , rows $k + 1, \dots, n$ dekho.

HOW entry $a_{ik}$ ko zero karein (jab $i > k$ ho) bina solution badlaaye? Pivot row $k$ ka multiple row $i$ se subtract karo: $Row_{i} \leftarrow Row_{i} - m_{ik} Row_{k} .$

Humein naya $(i, k)$ entry $0$ chahiye: $a_{ik} - m_{ik} a_{k k} = 0 ⟹ m_{ik} = \frac{a _{ik}}{a _{k k}} .$

WHY partial pivoting? Multiplier mein $a_{k k}$ denominator mein hai. Agar $a_{k k}$ tiny hai, toh $m_{ik}$ bahut bada ho jaata hai, aur bade multipliers har doosri entry ke floating-point error ko amplify karte hain.

3. Back-substitution — derive kiya

Forward elimination ke baad humaare paas upper-triangular system $U x = c$ hai:

u_{nn} x_{n} u_{n - 1, n - 1} x_{n - 1} + u_{n - 1, n} x_{n} = c_{n}, = c_{n - 1}, \dots

Last equation mein sirf ek unknown hai — use solve karo. Upar ki taraf substitute karo.

Figure — Solving linear systems — Gaussian elimination with partial pivoting

4. Worked example (pura)

Solve karo ${0.0003 x_{1} + 3.0000 x_{2} = 2.0001 1.0000 x_{1} + 1.0000 x_{2} = 1.0000$ Exact answer: $x_{1} = \frac{1}{3}, x_{2} = \frac{2}{3}$ (≈ $0.33333, 0.66667$ ).

Step 1 — Partial pivoting. Column 1 entries: $∣0.0003∣$ vs $∣1.0000∣$ . Yeh step kyon? $1.0000$ bada hai → rows swap karo taaki tiny $0.0003$ se kabhi divide na karna pade. $[1 0.0003 13 ∣ ∣ 1 2.0001] .$

Step 2 — Eliminate. $m_{21} = 0.0003/1 = 0.0003$ . Kyon: yeh woh multiplier hai jo $a_{21}$ ko zero karta hai. Row $_{2} \leftarrow$ Row $_{2} - 0.0003 \cdot$ Row $_{1}$ : $a_{22} = 3 - 0.0003 (1) = 2.9997, b_{2} = 2.0001 - 0.0003 (1) = 1.9998.$ $[10 1 2.9997 ∣ ∣ 1 1.9998] .$

Step 3 — Back-substitute. $x_{2} = \frac{1.9998}{2.9997} = 0.66667, x_{1} = \frac{1 - x _{2}}{1} = 0.33333. ✓$

Worked example Ek clean

$3 \times 3$ $2 - 3 - 2 1 - 1 1 - 1 22 ∣ ∣ ∣ 8 - 11 - 3$ Col 1: sabse bada $∣ - 3 ∣$ row 2 mein hai → rows 1,2 swap karo. $- 3 2 - 2 - 1 11 2 - 1 2 ∣ ∣ ∣ - 11 8 - 3$ $m_{21} = 2/ - 3 = - 0.667$ , $m_{31} = - 2/ - 3 = 0.667$ . Column 1 eliminate karo: $- 3 00 - 1 0.333 1.667 2 0.333 0.667 ∣ ∣ ∣ - 11 0.667 4.333$ Col 2 diagonal ke neeche: $∣0.333∣$ vs $∣1.667∣$ → rows 2,3 swap karo. $- 3 00 - 1 1.667 0.333 2 0.667 0.333 ∣ ∣ ∣ - 11 4.333 0.667$ $m_{32} = 0.333/1.667 = 0.2$ : $a_{33} = 0.333 - 0.2 (0.667) = 0.2$ , $b_{3} = 0.667 - 0.2 (4.333) = - 0.2$ . Back-sub: $x_{3} = - 0.2/0.2 = - 1$ ; $x_{2} = (4.333 - 0.667 (- 1)) /1.667 = 3$ ; $x_{1} = (- 11 - (- 1) (3) - 2 (- 1)) / - 3 = 2$ . Solution $(2, 3, - 1)$ . Sahi kyon hai? Eq 1 check karo: $2 (2) + 3 - (- 1) = 8 ✓$ .

5. Common mistakes

6. Cost aur kab fail hota hai

Recall Feynman: ek 12-saal ke bacche ko samjhao

Ek equations ki staircase imagine karo. Tum pehle variable ko har equation se hatana chahte ho sivaaye top wali ke — jaise $x$ ko pehli row chhod ke baaki sab se erase karna. Use cleanly erase karne ke liye tum top equation ka sahi multiple baaki sab se subtract karte ho. Lekin agar top equation mein $x$ ke aage bahut chota number hai, toh us se divide karna monster numbers bana deta hai aur tumhara calculator confuse ho jaata hai. Isliye pehle woh equation dhundho jisme $x$ -coefficient SABSE BADA ho aur use top par le jao — yahi pivoting hai. Agla variable ke liye repeat karo, aur aise hi karte raho, jab tak last equation mein sirf ek unknown na reh jaaye. Use solve karo, phir staircase par upar chadhte hue answers plug in karo.

Flashcards

Gaussian elimination mein forward elimination ka goal kya hai?

A

ko ek upper-triangular matrix

U

mein transform karna (diagonal ke neeche zeros) row operations use karke.

Hum partial pivoting kyon use karte hain?

Tiny/zero pivots se divide karne se bachne ke liye; yeh saare multipliers

∣ m_{ik} ∣ \leq 1

rakhta hai, round-off error control karta hai (numerical stability).

Column

k

ke liye partial-pivoting rule kya hai?

Rows

k \dots n

mein, column

k

mein sabse badi absolute value wali entry dhundho aur us row ko position

k

par swap karo.

Multiplier

m_{ik}

ka formula?

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

— isliye choose kiya taaki

a_{ik} - m_{ik} a_{k k} = 0

ho.

Elimination ke dauran row update?

a_{ij} \leftarrow a_{ij} - m_{ik} a_{k j}

aur

b_{i} \leftarrow b_{i} - m_{ik} b_{k}

(poori augmented row par apply karo).

Back-substitution formula?

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

i = n

1

tak compute kiya jaata hai.

Back-substitution bottom-up kyon?

Last equation mein sirf ek unknown hai; har pehle wale

x_{i}

ko already-known

x_{j}

(

j > i

) chahiye.

Gaussian elimination ka approximate flop count?

\sim \frac{2}{3} n^{3}

(forward elimination dominate karta hai; back-sub

O (n^{2})

hai).

Unavoidable zero pivot kya indicate karta hai?

Matrix singular hai — koi unique solution nahi.

Partial aur complete pivoting mein kya fark hai?

Partial: sirf current column search karo (rows

k .. n

). Complete: poori remaining submatrix search karo (zyada stable, zyada costly).

Connections

LU Decomposition — Gaussian elimination hi ek LU factorization hai; pivoting $P A = LU$ deta hai.
Back-substitution and Forward-substitution
Condition Number and Numerical Stability
Round-off Error in Floating Point
Determinants — pivots ka product ( $\times (- 1)^{#swaps}$ ) $det A$ deta hai.
Cramer's Rule — exact lekin $O (n!)$ , impractical contrast.
Iterative Methods (Jacobi, Gauss-Seidel) — large sparse systems ke liye alternative.