Exercises — Solving linear systems — Gaussian elimination with partial pivoting

Partial pivoting kya poochhta hai: column 1 mein current row se neeche tak ke entries mein se, sabse bada absolute value wala dhundho. Column-1 entries hain $2,-5,3$. Inke absolute values hain $|2|=2$, $|-5|=5$, $|3|=3$. Sabse bada $5$ hai, jo row 2 mein hai. Absolute value kyun, value itself kyun nahi? Badi magnitude (positive ya negative) hi divisor ke roop mein multiplier ko chhota rakhti hai; sign is baat se irrelevant hai ki number kitna "bada" hai. Answer: row 2 ko row 1 mein swap karo.

Multiplier kya hota hai: woh number $m_{31}$ jo is tarah choose kiya jaata hai ki $a_{31}-m_{31}{a}_{11}=0$. Solve karne par, $m_{31}=\frac{a_{31}}{a_{11}}=\frac{-2}{4}=-0.5$. Yeh kaisa dikhta hai: hum row 3 se $-0.5\times (\text{pivot row})$ subtract karte hain, yaani hum pivot row ka aadha add karte hain. Kyunki $|-0.5|\le 1$, yeh ek well-behaved (stable) step hai — exactly wahi jo pivoting guarantee karta hai.

"Upper-triangular" ka matlab: main diagonal ke neeche har entry zero ho. $P$: below-diagonal entries hain $(2,1)=0,(3,1)=0,(3,2)=0$ — sab zero. ✅ $Q$: entry $(3,2)=1\ne 0$ — abhi ek variable aur kill karna hai. ❌ Answer: sirf $P$. Back-substitution ke liye zaruri hai ki har row (bottom-up) exactly ek naya unknown expose kare; $Q$ ki bottom two rows abhi bhi $x_2$ aur $x_3$ ko aapas mein ulajhati hain.

Augmented matrix: $\left[\begin{array}{ccc}2& 4& 10\\ 4& 3& 15\end{array}\right]$. Step 1 — column 1 pivot. $|2|$ vs $|4|$ → biggest hai $4$ (row 2). Swap karo: $\left[\begin{array}{ccc}4& 3& 15\\ 2& 4& 10\end{array}\right]$ Step 2 — eliminate. $m_{21}=\frac{2}{4}=0.5$ (note karo $|m_{21}|\le 1$ — pivot ne kaam kiya). Row${}_2\leftarrow$ Row${}_2-0.5\cdot$Row${}_1$: $a_{22}=4-0.5(3)=2.5$, $b_2=10-0.5(15)=2.5$. $\left[\begin{array}{ccc}4& 3& 15\\ 0& 2.5& 2.5\end{array}\right]$ Step 3 — back-substitute (bottom-up). $x_2=\frac{2.5}{2.5}=1$; $x_1=\frac{15-3(1)}{4}=\frac{12}{4}=3$. Answer: $x_1=3,x_2=1$. Eq 2 check karo: $4(3)+3(1)=15$ ✅.

Column 1: $|1|$ vs $|-4|$ → biggest magnitude hai $4$ (row 2). Swap karo: $\left[\begin{array}{ccc}-4& 1& 5\\ 1& -2& -3\end{array}\right]$ Negative pivot bilkul theek hai — pivoting magnitude ki parwah karta hai, sign ki nahi. $m_{21}=\frac{1}{-4}=-0.25$. Row${}_2\leftarrow$Row${}_2-(-0.25)$Row${}_1=$Row${}_2+0.25$Row${}_1$: $a_{22}=-2+0.25(1)=-1.75$, $b_2=-3+0.25(5)=-1.75$. $\left[\begin{array}{ccc}-4& 1& 5\\ 0& -1.75& -1.75\end{array}\right]$ Back-sub: $x_2=\frac{-1.75}{-1.75}=1$; $x_1=\frac{5-1(1)}{-4}=\frac{4}{-4}=-1$. Answer: $x_1=-1,x_2=1$. Eq 1 check karo: $-1-2(1)=-3$ ✅.

Naive pivot $a_{11}=0$ zero se divide karne par majboor kar deta. Yahi woh emergency hai jiske liye pivoting bana hai. Column 1: $|0|$ vs $|3|$ → biggest hai $3$ (row 2). Swap karo: $\left[\begin{array}{ccc}3& 1& 5\\ 0& 2& 4\end{array}\right]$ System already upper-triangular hai — koi elimination ki zarurat nahi! Back-sub: $x_2=\frac{4}{2}=2$; $x_1=\frac{5-1(2)}{3}=1$. Answer: $x_1=1,x_2=2$. Diagonal par zero dead end nahi hai jab tak ki uske neeche ke saare entries bhi zero na hon.

Column 1. $|1|,|2|,|-1|$ → biggest $2$ (row 2). Rows 1,2 swap karo: $\left[\begin{array}{cccc}2& -1& 3& 9\\ 1& 1& 1& 6\\ -1& 2& 1& 2\end{array}\right]$ $m_{21}=\frac{1}{2}=0.5$, $m_{31}=\frac{-1}{2}=-0.5$. Row${}_2\leftarrow$Row${}_2-0.5$Row${}_1$: $(0,1-0.5(-1),1-0.5(3)|6-0.5(9))=(0,1.5,-0.5|1.5)$. Row${}_3\leftarrow$Row${}_3+0.5$Row${}_1$: $(0,2+0.5(-1),1+0.5(3)|2+0.5(9))=(0,1.5,2.5|6.5)$. $\left[\begin{array}{cccc}2& -1& 3& 9\\ 0& 1.5& -0.5& 1.5\\ 0& 1.5& 2.5& 6.5\end{array}\right]$ Column 2 (rows 2,3): $|1.5|$ vs $|1.5|$ — tie hai. Tie hone par hum current row rakh sakte hain (stability ke liye swap zaruri nahi). $m_{32}=\frac{1.5}{1.5}=1$. Row${}_3\leftarrow$Row${}_3-1\cdot$Row${}_2$: $(0,0,2.5-(-0.5)|6.5-1.5)=(0,0,3|5)$. $\left[\begin{array}{cccc}2& -1& 3& 9\\ 0& 1.5& -0.5& 1.5\\ 0& 0& 3& 5\end{array}\right]$ Back-sub. $x_3=\frac{5}{3}\approx 1.6667$; $x_2=\frac{1.5-(-0.5)x_3}{1.5}=\frac{1.5+0.5(5/3)}{1.5}=\frac{1.5+0.8333}{1.5}=1.5556$; $x_1=\frac{9-(-1)x_2-3x_3}{2}=\frac{9+1.5556-3(1.6667)}{2}=\frac{9+1.5556-5}{2}=2.7778$. Answer: $x_1\approx 2.7778,x_2\approx 1.5556,x_3\approx 1.6667$ (exactly $\frac{25}{9},\frac{14}{9},\frac{5}{3}$).

Multiplier kya hota hai: $m_{ik}=\frac{a_{ik}}{a_{kk}}$ rows $i>k$ ke liye. Pivoting kya guarantee karta hai: humne woh row swap ki jiske column-$k$ entry ka absolute value rows $k\dots n$ mein sabse bada tha. Isliye pivot satisfy karta hai $|a_{kk}|={\max }_{i\ge k}|a_{ik}|\ge |a_{ik}|\text{for every }i>k.$ Dono sides ko $|a_{kk}|>0$ se divide karo: $\frac{|a_{ik}|}{|a_{kk}|}\le 1⟹|m_{ik}|=\left|\frac{a_{ik}}{a_{kk}}\right|\le 1.$ Yeh kyun matter karta hai: chhote multipliers ka matlab hai ki elimination step har row mein existing round-off ko badhaata nahi balki ghataata hai — stability ka numerical dil yahi hai. Dekho Condition Number and Numerical Stability.

Column 1: $|0.001|$ vs $|1.00|$ → biggest $1.00$ (row 2). Swap — yahi toh poora point hai: $\left[\begin{array}{ccc}1.00& 2.00& 3.00\\ 0.001& 1.00& 1.00\end{array}\right]$ $m_{21}=\frac{0.001}{1.00}=0.001$ (tiny, $|m|\le 1$ ✅). $a_{22}=1.00-0.001(2.00)=1.00-0.002=0.998$ (3 s.f.). $b_2=1.00-0.001(3.00)=1.00-0.003=0.997$. Back-sub: $x_2=\frac{0.997}{0.998}=0.999$; $x_1=\frac{3.00-2.00(0.999)}{1.00}=3.00-1.998=1.00$. Answer (3 s.f.): $x_1\approx 1.00,x_2\approx 0.999$ — exact $1.001,0.999$ se poori displayed precision tak match karta hai. Contrast: swap ke bina, $m_{21}=1/0.001=1000$, aur $a_{22}=1.00-1000(2.00)\approx -2000$ useful digits ko daba deta. Pivoting ne accuracy bachali. Dekho Round-off Error in Floating Point.

Permutation ne rows 1,2 swap kiye, isliye $P=\left[\begin{array}{cc}0& 1\\ 1& 0\end{array}\right]$ aur $PA=\left[\begin{array}{cc}4& 3\\ 2& 4\end{array}\right].$ Ek hi multiplier tha $m_{21}=0.5$. LU form mein, $L$ apne unit diagonal ke neeche multipliers rakhta hai, $U$ eliminated (upper-triangular) result rakhta hai: $L=\left[\begin{array}{cc}1& 0\\ 0.5& 1\end{array}\right],U=\left[\begin{array}{cc}4& 3\\ 0& 2.5\end{array}\right].$ Check $LU$: $\left[\begin{array}{cc}1& 0\\ 0.5& 1\end{array}\right]\left[\begin{array}{cc}4& 3\\ 0& 2.5\end{array}\right]=\left[\begin{array}{cc}4& 3\\ 2& 4\end{array}\right]=PA$ ✅. Yeh same computation kyun hai: partial-pivoted Gaussian elimination wahi algorithm hai jo $PA=LU$ produce karta hai. Dekho LU Decomposition; solve karna phir Back-substitution and Forward-substitution mein split ho jaata hai.

KEY fact: "ek row ka multiple doosri mein add karo" type ke row operations determinant nahi badlaate; har row swap sign flip karta hai. Elimination ke baad hum upper-triangular mein pahunche: $U=\left[\begin{array}{ccc}2& -1& 3\\ 0& 1.5& -0.5\\ 0& 0& 3\end{array}\right].$ Upper-triangular matrix ka determinant uske diagonal ka product hota hai: $\det U=2\cdot 1.5\cdot 3=9.$ Humne ek row swap kiya (column 1), isliye $\det A=(-1{)}^1\det U=-9.$ Check (direct expansion): $\det A=1(-1-6)-1(2+3)+1(4-1)=-7-5+3=-9$ ✅. Dekho Determinants.

$\det A=2(3)-4(4)=6-16=-10.$ Column 1 ko $\mathbf{b}=(10,15)$ se replace karo: $\det A_1=\left|\begin{array}{cc}10& 4\\ 15& 3\end{array}\right|=10(3)-4(15)=30-60=-30.$ Column 2 replace karo: $\det A_2=\left|\begin{array}{cc}2& 10\\ 4& 15\end{array}\right|=2(15)-10(4)=30-40=-10.$ $x_1=\frac{\det A_1}{\det A}=\frac{-30}{-10}=3,x_2=\frac{\det A_2}{\det A}=\frac{-10}{-10}=1.$ Answer match karta hai ✅. Bade $n$ ke liye elimination kyun prefer karte hain: Cramer's Rule ko $n+1$ determinants chahiye ($\sim n\cdot n!$ kaam); elimination $\sim \frac{2}{3}{n}^3$ hai — $n$ badhne par bahut sasta.

Column 1: $|1|,|2|,|1|$ → biggest $2$ (row 2). Rows 1,2 swap karo: $\left[\begin{array}{cccc}2& 4& 6& 12\\ 1& 2& 3& 6\\ 1& 1& 1& 3\end{array}\right]$ $m_{21}=0.5,m_{31}=0.5$. Row${}_2\leftarrow$Row${}_2-0.5$Row${}_1$: $(0,2-2,3-3|6-6)=(0,0,0|0)$. Row${}_3\leftarrow$Row${}_3-0.5$Row${}_1$: $(0,1-2,1-3|3-6)=(0,-1,-2|-3)$. $\left[\begin{array}{cccc}2& 4& 6& 12\\ 0& 0& 0& 0\\ 0& -1& -2& -3\end{array}\right]$ Column 2 (rows 2,3): candidates $0$ aur $-1$ → biggest $|-1|$ (row 3). Swap karo: $\left[\begin{array}{cccc}2& 4& 6& 12\\ 0& -1& -2& -3\\ 0& 0& 0& 0\end{array}\right]$ Last pivot $0$ hai — column 3, row 3, entry $0$, aur neeche swap karne ke liye kuch nahi. $A$ singular hai. Iska matlab: bottom row padhti hai $0\cdot x_3=0$ — hamesha sach, isliye system ke infinitely many solutions hain (equations linearly dependent thiin: row 2, row 1 ka $2\times$ tha). $0=0$ (na ki $0=\text{nonzero}$) batata hai consistent-but-not-unique, "no solution" nahi. Zero pivot hamesha $\det A=0$ signal karta hai.

Design idea: pehle pivot wali jagah ek tiny number rakho. Lo $\{\begin{array}{l}0.00100x_1+1.00x_2=1.00\\ 1.00x_1+1.00x_2=2.00\end{array}$ Exact solution: subtract karo — $(1-0.001)x_1=2-1$, $x_1=\frac{1}{0.999}=1.001\approx 1$, $x_2=2-1.001=0.999\approx 1$. Theek hai. Route A — NO pivoting (3 s.f.): $m_{21}=\frac{1.00}{0.00100}=1000$. $a_{22}=1.00-1000(1.00)=-999$; $b_2=2.00-1000(1.00)=-998$. $x_2=\frac{-998}{-999}=0.999$; phir $x_1=\frac{1.00-1.00(0.999)}{0.00100}=\frac{0.001}{0.001}$. Lekin 3 s.f. mein, $1.00-0.999$ round ho ke $\approx 0.00$ (catastrophic cancellation) → $x_1\approx \frac{0}{0.001}=0$. Galat ($x_1=0$ instead of $1$). Route B — WITH pivoting. Swap karo (row 2 mein $|1.00|>|0.001|$): $\left[\begin{array}{cccc}1& 1& |& 2\\ 0.001& 1& |& 1\end{array}\right]$, $m_{21}=0.001$, $a_{22}=1-0.001=0.999$, $b_2=1-0.002=0.998$. $x_2=\frac{0.998}{0.999}=0.999$; $x_1=\frac{2-0.999}{1}=1.00$. Correct ✅. Moral: tiny pivot back-substitution mein do near-equal numbers ka subtraction force karta hai — pivoting reorder karta hai taaki divisor $O(1)$ ho aur cancellation kabhi ho hi na sake.

Column 1 magnitudes: $|0.2|=0.2,|7|=7,|-3|=3$. Biggest hai $7$ → row 2 pivot row ban jaati hai (rows 1,2 swap karo). Swap ke baad, pivot hai $a_{11}=7$; remaining column-1 entries hain $0.2$ (old row 1, ab row 2) aur $-3$ (row 3). $m_{21}=\frac{0.2}{7}\approx 0.02857,m_{31}=\frac{-3}{7}\approx -\mathrm{0.42857.}$ Dono $|m|\le 1$ satisfy karte hain ✅ — exactly L3.2 ki guarantee. Agar hum pivot nahi karte, to divisor $0.2$ hota, jisse $m_{21}=35$ aur $m_{31}=-15$ milte: monster multipliers, unstable.

• Deeper stability theory → Condition Number and Numerical Stability
• Jab elimination bahut slow ho → Iterative Methods (Jacobi, Gauss-Seidel)
• Factorization view → LU Decomposition aur Back-substitution and Forward-substitution