Worked examples — Least squares — normal equations, QR approach

4.5.41 · D3 · Maths › Linear Algebra (Full) › Least squares — normal equations, QR approach

Shuru karne se pehle, vocabulary ki ek reminder taaki koi symbol anjaan na rahe:

Ek aur symbol jis par hum baad mein lean karenge:

Scenario matrix

Har least-squares question jo tum miloge woh in cells mein se ek (ya blend) hogi. Last column us example ka naam deta hai jo use clear karta hai.

Hum inhe order mein karte hain. Cells C1, C2, C6, C7 ko ek figure milti hai kyunki geometry kaam kar rahi hai.

Example 1 — Overdetermined, full rank (cell C1)

Neeche ki figure mein chaar coral data points aur lavender best-fit line plot ki gayi hai jo hum abhi compute karne wale hain; mint verticals residuals hain — woh upar-neeche ki misses jo least squares jitni ho sake utni chhoti banata hai.

Step 1 — $A$ aur $\mathbf{b}$ banao. $A=\left(\begin{array}{cc}1& -1\\ 1& 0\\ 1& 1\\ 1& 2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}1\\ 0\\ 0\\ -3\end{array}\right).$ Yeh step kyun? Har row kehti hai "predict $y_i$ by $c\cdot 1+d\cdot t_i$". Column one all-ones hai (intercept $c$); column two mein $t_i$ hain (slope $d$).

Step 2 — $A^{\top }A$ aur $A^{\top }\mathbf{b}$ banao. $A^{\top }A=\left(\begin{array}{cc}4& 2\\ 2& 6\end{array}\right),A^{\top }\mathbf{b}=\left(\begin{array}{c}-2\\ -7\end{array}\right).$ Yeh step kyun? $A^{\top }A$ ki entries column dot products hain: $1\cdot 1=4$, $1\cdot \mathbf{t}=(-1+0+1+2)=2$, $\mathbf{t}\cdot \mathbf{t}=(1+0+1+4)=6$. $A^{\top }\mathbf{b}$ har column ko $\mathbf{b}$ se dot karta hai.

Step 3 — $2\times 2$ system solve karo. $\left(\begin{array}{cc}4& 2\\ 2& 6\end{array}\right)\left(\genfrac{}{}{0ex}{}{c}{d}\right)=\left(\genfrac{}{}{0ex}{}{-2}{-7}\right).$ Determinant $=4\cdot 6-2\cdot 2=20$. Cramer se: $c=\frac{(-2)(6)-(2)(-7)}{20}=\frac{2}{20}=0.1,d=\frac{(4)(-7)-(2)(-2)}{20}=\frac{-24}{20}=-\mathrm{1.2.}$ Yeh step kyun? $A^{\top }A$ invertible hai (full column rank), toh $\hat{\mathbf{x}}=(A^{\top }A{)}^{-1}{A}^{\top }\mathbf{b}$ unique hai.

Best line: $y=0.1-1.2t$. Slope negative hai — forecast confirm hua. Figure mein lavender line wakai neechay tilt hai.

Verify: $t=-1,0,1,2$ par predictions $1.3,0.1,-1.1,-2.3$ hain; residual $\mathbf{r}=(-0.3,-0.1,1.1,-0.7)$. Orthogonality check karo: $1\cdot \mathbf{r}=0$ aur $\mathbf{t}\cdot \mathbf{r}=0$. ✓ (Dono VERIFY mein check kiye gaye hain.)

Example 2 — Consistent system, zero residual (cell C2)

Figure mein teen coral points lavender line par dead-on baithe hain, toh koi bhi mint residual sticks draw nahi hain — zero residual ki picture.

Step 1 — setup karo. $A=\left(\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}2\\ 5\\ 8\end{array}\right).$ Yeh step kyun? Bilkul pehle jaisa, har row encode karti hai "predict $y_i$ by $c+d{t}_i$": all-ones pehla column intercept $c$ carry karta hai, doosra column inputs $t_i=0,1,2$ slope $d$ ke liye carry karta hai. Sirf $\mathbf{b}$ (measured $y$-values) Ex 1 se badlate hain.

Step 2 — normal equations. $A^{\top }A=\left(\begin{array}{cc}3& 3\\ 3& 5\end{array}\right)$, $A^{\top }\mathbf{b}=\left(\begin{array}{c}15\\ 21\end{array}\right)$. Yeh step kyun? Hum $\mathbf{b}$ ko $\text{Col}(A)$ par project karte hain residual ko dono columns ke perpendicular force karke; entries phir se column dot products hain ($1\cdot 1=3$, $1\cdot \mathbf{t}=3$, $\mathbf{t}\cdot \mathbf{t}=5$) aur $A^{\top }\mathbf{b}$ har column ko $\mathbf{b}$ se dot karta hai.

Step 3 — solve karo. $3c+3d=15$ aur $3c+5d=21$ se: subtract karo → $2d=6\Rightarrow d=3$, phir $c=2$. Yeh step kyun? Do do unknowns mein do linear equations; pehli ko doosri se subtract karne par $c$ cancel hota hai (dono ka coefficient $3$ hai), ek equation $d$ mein bacha rehta hai. $d$ ko pehle mein back-substitute karo $c$ nikalne ke liye — wohi elimination jo tum kisi bhi $2\times 2$ system par karte ho.

Line: $y=2+3t$ — exact line, jaise forecast tha.

Verify: predictions $(2,5,8)=\mathbf{b}$, toh $\mathbf{r}=0$. Jab $\mathbf{b}\in \text{Col}(A)$, projection hi $\mathbf{b}$ hai aur least squares ordinary solve mein degenerate ho jaata hai. ✓

Example 3 — Same data QR se (cell C3)

Step 1 — orthonormalise karo. ${\mathbf{q}}_1=\frac{1}{\sqrt{3}}(1,1,1)$ kyunki $\Vert {\mathbf{a}}_1\Vert =\sqrt{3}$. Projection coefficient ${\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\frac{0+1+2}{\sqrt{3}}=\sqrt{3}$. Remove karo: ${\mathbf{a}}_2-\sqrt{3}{\mathbf{q}}_1=(0,1,2)-(1,1,1)=(-1,0,1)$. Normalise karo: ${\mathbf{q}}_2=\frac{1}{\sqrt{2}}(-1,0,1)$. Yeh step kyun? Orthonormal columns projection ko simple dot products mein turn kar dete hain — koi matrix inverse nahi chahiye.

Step 2 — $R=Q^{\top }A$ padho. $R=\left(\begin{array}{cc}\sqrt{3}& \sqrt{3}\\ 0& \sqrt{2}\end{array}\right).$ Yeh step kyun? $R_{11}=\Vert {\mathbf{a}}_1\Vert =\sqrt{3}$, $R_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\sqrt{3}$, $R_{22}=\Vert (-1,0,1)\Vert =\sqrt{2}$.

Step 3 — $Q^{\top }\mathbf{b}$ compute karo aur back-substitute karo. $Q^{\top }\mathbf{b}=\left(\begin{array}{c}\frac{2+5+8}{\sqrt{3}}\\ \frac{-2+0+8}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}\frac{15}{\sqrt{3}}\\ \frac{6}{\sqrt{2}}\end{array}\right)=\left(\begin{array}{c}5\sqrt{3}\\ 3\sqrt{2}\end{array}\right).$ $R\hat{\mathbf{x}}=Q^{\top }\mathbf{b}$ bottom-up solve karo: $\sqrt{2}d=3\sqrt{2}\Rightarrow d=3$; phir $\sqrt{3}c+\sqrt{3}(3)=5\sqrt{3}\Rightarrow c=2$. Yeh step kyun? $R$ upper triangular hai toh last equation mein ek unknown hai — back-substitution fast hai aur condition number ko square nahi karta.

Verify: $c=2,d=3$, Ex 2 se exactly match. ✓

Example 4 — Rank-deficient: infinitely many solutions (cell C4)

Step 1 — rank spot karo. $\text{Col}(A)$ $(1,1,1)$ se spanned ek single line hai; rank $=1$, $2$ nahi. Yeh step kyun? Agar columns do independent directions span nahi karte, toh hum do coordinates pin down nahi kar sakte.

Step 2 — normal equations. $A^{\top }A=\left(\begin{array}{cc}3& 6\\ 6& 12\end{array}\right),\det =3\cdot 12-6\cdot 6=0.$ Singular — koi inverse nahi. $A^{\top }\mathbf{b}=\left(\genfrac{}{}{0ex}{}{6}{12}\right)$. Yeh step kyun? Normal equations $A^{\top }A\hat{\mathbf{x}}=A^{\top }\mathbf{b}$ tab bhi sahi machinery hain jab columns dependent hon — hum inhe exactly usual tarah form karte hain (entries column dot products hain, $A^{\top }\mathbf{b}$ har column ko $\mathbf{b}$ se dot karta hai). Determinant compute karna humein pehle hi bata deta hai ki yeh $A^{\top }A$ invert nahi ho sakta, jo is case ka poora point hai.

Step 3 — SAARE solutions describe karo. System $3x_1+6x_2=6$ (doosri row bas $2\times$ yahi hai) deta hai $x_1+2x_2=2$. $s$ koi bhi real number ho aur $x_2=s$ set karo; phir $x_1=2-2s$, toh har $\hat{\mathbf{x}}=(2-2s,s)$ jahan $s\in \mathbb{R}$ ek valid least-squares solution hai. Yeh step kyun? Ek equation, do unknowns → doosra unknown free hai, toh answers ki poori ek line, free parameter $s$ se indexed.

Step 4 — projection phir bhi unique hai. Kisi bhi aise $\hat{\mathbf{x}}$ ke liye, $A\hat{\mathbf{x}}=(x_1+2x_2)(1,1,1)=2(1,1,1)=(2,2,2)$. Yeh step kyun? Ambiguous direction ke along alag-alag $\hat{\mathbf{x}}$ sab $\text{Col}(A)$ ke same point par map hote hain — $\mathbf{b}$ ka projection. Pseudoinverse minimum-norm representative choose karta hai.

Verify: residual $\mathbf{r}=\mathbf{b}-(2,2,2)=(-1,0,1)$; check $1\cdot \mathbf{r}=0$. Minimum-norm choice $\Vert (2-2s,s){\Vert }^2$ minimize karta hai: derivative $2(2-2s)(-2)+2s=0\Rightarrow 10s=8\Rightarrow s=0.8$, deta hai $\hat{\mathbf{x}}=(0.4,0.8)$. ✓

Example 5 — Word problem real units ke saath (cell C5)

Step 1 — one-column $A$. $A=\left(\begin{array}{c}1\\ 2\\ 3\\ 4\end{array}\right),\mathbf{b}=\left(\begin{array}{c}1.9\\ 4.1\\ 5.8\\ 8.2\end{array}\right).$ Yeh step kyun? Model mein ek unknown $k$ hai aur yeh origin se pass karta hai, toh koi all-ones column nahi — bas $x$ values. Yeh origin se regression hai.

Step 2 — scalar normal equation. Ek column ke saath, $A^{\top }A$ aur $A^{\top }\mathbf{b}$ scalars hain: $A^{\top }A=1+4+9+16=30,A^{\top }\mathbf{b}=1.9+8.2+17.4+32.8=\mathrm{60.3.}$ Yeh step kyun? Dot product $\mathbf{x}\cdot \mathbf{x}$ bade stretches ko zyada weight deta hai — unke paas zyada "leverage" hota hai.

Step 3 — solve karo. $k=\frac{60.3}{30}=2.01$ N/cm. Yeh step kyun? Sirf ek unknown ke saath normal equation ek single scalar equation $30k=60.3$ mein collapse ho jaati hai; dono sides ko scalar $A^{\top }A$ se divide karne par $k$ isolate ho jaata hai — "invert $A^{\top }A$" ka one-dimensional version.

Verify: units check — $(\text{N⋅cm})/({\text{cm}}^2)=$ N/cm. ✓ Predicted forces $(2.01,4.02,6.03,8.04)$ data ko hug karte hain; residuals chhote hain. ✓ ($k=2.01$ VERIFY mein checked hai.)

Example 6 — Degenerate limit: coincident data (cell C6)

Figure mein do clashing coral points $t=2$ par stacked hain ($y=4$ aur $y=6$); butter dot wahan mark karta hai jahan lavender fit-line actually pass karti hai — right unke beech $y=5$ par, mint stick se dikhaya gaya vertical average.

Step 1 — setup karo. $A=\left(\begin{array}{cc}1& 0\\ 1& 2\\ 1& 2\end{array}\right),\mathbf{b}=\left(\begin{array}{c}0\\ 4\\ 6\end{array}\right).$ Yeh step kyun? Do rows same $t$ share karti hain; design phir bhi full column rank hai (columns $(1,1,1)$ aur $(0,2,2)$ independent hain), toh ek unique line exist karta hai.

Step 2 — normal equations. $A^{\top }A=\left(\begin{array}{cc}3& 4\\ 4& 8\end{array}\right)$, $A^{\top }\mathbf{b}=\left(\begin{array}{c}10\\ 20\end{array}\right)$, $\det =24-16=8$. $c=\frac{10\cdot 8-4\cdot 20}{8}=\frac{0}{8}=0,d=\frac{3\cdot 20-4\cdot 10}{8}=\frac{20}{8}=\mathrm{2.5.}$

Step 3 — interpret karo. Line $y=0+2.5t$. $t=2$ par yeh $5$ predict karta hai — exactly do clashing readings $4$ aur $6$ ka average, jaise forecast tha. Yeh step kyun? Jab kai rows same input share karti hain, least squares wahan sirf ek output choose kar sakta hai, aur distance-minimising choice unka mean hota hai.

Verify: predictions $(0,5,5)$, residual $(0,-1,1)$; $1\cdot \mathbf{r}=0$, $\mathbf{t}\cdot \mathbf{r}=0$. ✓

Example 7 — Projection matrix, $\mathbf{b}$ split karo (cell C7)

Figure ek 2D schematic hai: lavender line $\text{Col}(A)$ hai, coral arrow $\mathbf{b}$ hai, mint arrow line par uski shadow $P\mathbf{b}$ hai, aur dashed slate segment residual hai — line se right angle par milta hai (marked), jo exactly woh orthogonality hai jo least squares enforce karta hai.

Step 1 — definition se $P$ banao. Recall $P=A(A^{\top }A{)}^{-1}{A}^{\top }$. Yahan $A$ single column $(1,1,1{)}^{\top }$ hai, toh $A^{\top }A=1+1+1=3$ (ek scalar) hai, iska inverse $\frac{1}{3}$ hai, aur $A{A}^{\top }$ $3\times 3$ all-ones matrix hai. Substitute karne par, $P=A(A^{\top }A{)}^{-1}{A}^{\top }=\frac{A{A}^{\top }}{3}=\frac{1}{3}\left(\begin{array}{ccc}1& 1& 1\\ 1& 1& 1\\ 1& 1& 1\end{array}\right).$ Yeh step kyun? Ek column ke saath, general formula $P=A(A^{\top }A{)}^{-1}{A}^{\top }$ collapse ho kar $\frac{A{A}^{\top }}{\Vert A{\Vert }^2}$ ban jaata hai — us line par orthogonal projection. $P$ ki har row $(\frac{1}{3},\frac{1}{3},\frac{1}{3})$ hai, yaani "teen entries ka average lo" — exactly wohi jo $(1,1,1)$ par projecting karna chahiye.

Step 2 — idempotence check. $P^2=P$ kyunki already-constant vector ko average karna kuch nahi badalta, aur $P^{\top }=P$ kyunki all-ones matrix symmetric hai. Yeh step kyun? Do baar project karna = ek baar; yeh do identities ($P^2=P$, $P^{\top }=P$) kisi bhi projection matrix ki defining fingerprints hain, confirm karte hain ki hum ne $P$ sahi banaya.

Step 3 — $\mathbf{b}$ ko fit + residual mein split karo. $\hat{\mathbf{b}}=P\mathbf{b}=\left(\frac{1+2+3}{3}\right)(1,1,1)=(2,2,2),\mathbf{r}=\mathbf{b}-\hat{\mathbf{b}}=(-1,0,1).$ Yeh step kyun? $\hat{\mathbf{b}}$ line mein hai (fit — yeh $(1,1,1)$ ka multiple hai), $\mathbf{r}$ us par perpendicular hai (miss); do pieces milke $\mathbf{b}$ bante hain, ise "explained" aur "leftover" mein split karte hain.

Verify: ${\hat{\mathbf{b}}}^{\top }\mathbf{r}=(2,2,2)\cdot (-1,0,1)=0$ ✓; $\Vert \mathbf{b}{\Vert }^2=14=\Vert \hat{\mathbf{b}}{\Vert }^2+\Vert \mathbf{r}{\Vert }^2=12+2$ (Pythagoras). ✓

Example 8 — Exam twist: fit ek fixed point se force kiya gaya (cell C8)

Step 1 — model reduce karo. $c=0$ force karna intercept column remove kar deta hai, ek single column of $t$-values chhodta hai: $A=\left(\begin{array}{c}1\\ 2\\ 3\end{array}\right),\mathbf{b}=\left(\begin{array}{c}3\\ 5\\ 8\end{array}\right).$ Yeh step kyun? "Origin se pass karo" ki hard constraint ek extra equation bolt karne ki baat nahi — yeh unknown $c$ ko delete karta hai, $A$ ko do columns se shrink karke ek mein laata hai. Kam unknowns, same least-squares machinery.

Step 2 — scalar solve. Ek column ke saath, $A^{\top }A=1+4+9=14$ aur $A^{\top }\mathbf{b}=3+10+24=37$, toh $d=\frac{A^{\top }\mathbf{b}}{A^{\top }A}=\frac{37}{14}\approx \mathrm{2.643.}$ Yeh step kyun? Ex 5 wala wohi origin-regression scalar formula: ek unknown matlab normal equation ek single scalar equation $14d=37$ hai, divide karke solve hoti hai.

Step 3 — interpret karo. Best origin line: $y=\frac{37}{14}t$, slope forecast band $2.5$–$2.67$ ke andar.

Verify: $d=37/14=2.6428\dots$; predictions $(2.64,5.29,7.93)$, residual $(0.36,-0.29,0.07)$, check $\mathbf{t}\cdot \mathbf{r}=0$. ✓

Active Recall