Least squares — normal equations, QR approach: Exercises

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

Do master equations ka quick reminder jo tum baar baar use karoge:

Level 1 — Recognition

Problem 1.1

Inn systems $A x = b$ mein se konsa zarurat hai least squares ki (exact solution guaranteed nahi), aur konsa ordinary square solve hai? Reason bhi batao.

(a) $A$ hai $5 \times 2$ . (b) $A$ hai $3 \times 3$ invertible. (c) $A$ hai $4 \times 4$ lekin rank $2$ .

Recall Solution

Kya decide karta hai: least squares tall systems ke liye hai — unknowns se zyada equations — jahan $b$ column space mein nahi ho sakta.

(a) $5 \times 2$ : tall ( $m = 5 > n = 2$ ). Overdetermined → least squares use karo.
(b) $3 \times 3$ invertible: square with an inverse → ordinary solve $x = A^{- 1} b$ , exact.
(c) $4 \times 4$ rank $2$ : square hai lekin rank-deficient (columns dependent hain). Koi unique inverse nahi; least squares phir bhi apply hota hai lekin $\hat{x}$ unique nahi hoga — tum Pseudoinverse (Moore-Penrose) use karte. Toh: generalised sense mein least squares, minimum-norm solution.

Problem 1.2

Full-column-rank $A$ ke liye, bina derive kiye, normal equations aur projection matrix $P$ onto $Col (A)$ likh do.

Recall Solution

Normal equations: $A^{⊤} A \hat{x} = A^{⊤} b$ . Explicit solution: $\hat{x} = (A^{⊤} A)^{- 1} A^{⊤} b$ . Projection matrix: $P = A (A^{⊤} A)^{- 1} A^{⊤}$ , jo satisfy karta hai $P^{2} = P$ (do baar project karna = ek baar project karna) aur $P^{⊤} = P$ (symmetric).

Level 2 — Application

Problem 2.1

Data $y$ -values $4, 2, 3$ ke liye best horizontal line $y = c$ (ek constant, koi slope nahi) fit karo. Normal equations use karke $\overset{c}{^}$ nikalo.

Recall Solution

Setup. Har point ko single constant $c$ se predict karna matlab $A x = b$ jahan ek column of ones hai: $A = 111, b = 423, x = (c) .$ Compute. $A^{⊤} A = 1^{2} + 1^{2} + 1^{2} = 3$ , aur $A^{⊤} b = 4 + 2 + 3 = 9$ . Solve. $3 c = 9 \Rightarrow \overset{c}{^} = 3$ . Matlab: best constant fit bas data ka average hai — ones ke column ke saath least squares mean hi hota hai. Yeh sabse simple Linear Regression hai.

Problem 2.2

Points $(1, 1), (2, 2), (3, 2)$ ke liye $y = c + d t$ fit karo. $\overset{c}{^}, \hat{d}$ nikalo.

Recall Solution

Setup. Row $i$ kehti hai $c + d t_{i} = y_{i}$ : $A = 111123, b = 122 .$ $A^{⊤} A$ compute karo (entries columns $1 = (1, 1, 1)$ aur $t = (1, 2, 3)$ ke dot products hain): $A^{⊤} A = (1 \cdot 1 t \cdot 1 1 \cdot t t \cdot t) = (36614), A^{⊤} b = (1 + 2 + 2 1 + 4 + 6) = (511) .$ Solve $(36614) (d c) = (11 5)$ . Row 1 ko $2 \times$ karke row 2 se subtract karo: $(14 - 12) d = 11 - 10 \Rightarrow 2 d = 1 \Rightarrow \hat{d} = \frac{1}{2}$ . Phir $3 c + 6 (\frac{1}{2}) = 5 \Rightarrow 3 c = 2 \Rightarrow \overset{c}{^} = \frac{2}{3}$ . Best line: $y = \frac{2}{3} + \frac{1}{2} t$ . Figure dekho — miss-arrows line se seedha upar/neeche point karte hain.

Figure — Least squares — normal equations, QR approach

Level 3 — Analysis

Problem 3.1

Problem 2.2 ke liye, residual $r = b - A \hat{x}$ compute karo aur verify karo ki $A^{⊤} r = 0$ . Geometrically explain karo ki $A^{⊤} r = 0$ kya kehta hai.

Recall Solution

Predictions $\hat{b} = A \hat{x}$ with $c = \frac{2}{3}, d = \frac{1}{2}$ : $\hat{b}_{1} = \frac{2}{3} + \frac{1}{2} (1) = \frac{7}{6}, \hat{b}_{2} = \frac{2}{3} + \frac{1}{2} (2) = \frac{5}{3}, \hat{b}_{3} = \frac{2}{3} + \frac{1}{2} (3) = \frac{13}{6} .$ Residual $r = b - \hat{b}$ : $r_{1} = 1 - \frac{7}{6} = - \frac{1}{6}, r_{2} = 2 - \frac{5}{3} = \frac{1}{3}, r_{3} = 2 - \frac{13}{6} = - \frac{1}{6} .$ Orthogonality check karo: $1 \cdot r = - \frac{1}{6} + \frac{1}{3} - \frac{1}{6} = 0, t \cdot r = 1 (- \frac{1}{6}) + 2 (\frac{1}{3}) + 3 (- \frac{1}{6}) = - \frac{1}{6} + \frac{2}{3} - \frac{1}{2} = 0.$ Dono zero hain, toh $A^{⊤} r = 0$ . ✓ Geometry: residual arrow $A$ ke har column ke perpendicular hai, isliye poore plane $Col (A)$ ke bhi perpendicular hai. Yahi Orthogonal Projection condition hai — $\hat{b}$ us plane par $b$ ka shadow hai, aur $r$ seedha bahar jaane wala gap hai.

Problem 3.2

Condition number $κ$ measure karta hai ki ek matrix input errors ko kitna amplify karta hai. Ek matrix diya hai jis mein $κ (A) = 1 0^{4}$ hai, normal equations aur QR se solve karne mein error-amplification compare karo. Kisi par zyada trust karte ho aur kyun?

Recall Solution

Key fact: $A^{⊤} A$ banane se condition number square ho jaata hai: $κ (A^{⊤} A) = κ (A)^{2}$ .

Normal equations ek aisa system solve karte hain jahan $κ (A^{⊤} A) = (1 0^{4})^{2} = 1 0^{8}$ govern karta hai.
QR seedha $R$ ke saath kaam karta hai, jiska conditioning $κ (A) = 1 0^{4}$ se match karta hai.

Digits mein: double precision mein kareeban $16$ significant digits hote hain. $lo g_{10} (1 0^{8}) = 8$ digits kho dena (normal equations) matlab $\approx 8$ achhe digits bache; $lo g_{10} (1 0^{4}) = 4$ digits kho dena (QR) matlab $\approx 12$ bache. QR par trust karo — yeh kabhi $A^{⊤} A$ nahi banata, isliye squaring se bachta hai. Condition Number aur QR Factorization dekho.

Level 4 — Synthesis

Problem 4.1

Problem 2.2 ko dobara solve karo, lekin is baar QR se. Columns $a_{1} = (1, 1, 1), a_{2} = (1, 2, 3)$ par Gram-Schmidt Process se $Q, R$ banao, phir $R \hat{x} = Q^{⊤} b$ solve karo. Confirm karo ki $\overset{c}{^} = \frac{2}{3}, \hat{d} = \frac{1}{2}$ milte hain.

Recall Solution

Step 1 — pehla column normalise karo. $∥ a_{1} ∥ = 1 + 1 + 1 = 3$ , toh $q_{1} = \frac{1}{3} (1, 1, 1) .$ Step 2 — $a_{2}$ ka shadow $q_{1}$ ke along hatao. Overlap hai $q_{1}^{⊤} a_{2} = \frac{1}{3} (1 + 2 + 3) = \frac{6}{3} = 23$ . Subtract karo: $a_{2} - (23) q_{1} = (1, 2, 3) - 23 \cdot \frac{1}{3} (1, 1, 1) = (1, 2, 3) - (2, 2, 2) = (- 1, 0, 1) .$ Iska length hai $1 + 0 + 1 = 2$ , toh $q_{2} = \frac{1}{2} (- 1, 0, 1)$ . Step 3 — $R = Q^{⊤} A$ padho (construction se upper triangular): $R = (∥ a_{1} ∥ 0 q_{1}^{⊤} a_{2} ∥ (- 1, 0, 1) ∥) = (30232) .$ Step 4 — $Q^{⊤} b$ compute karo $b = (1, 2, 2)$ ke saath: $q_{1}^{⊤} b = \frac{1}{3} (1 + 2 + 2) = \frac{5}{3}, q_{2}^{⊤} b = \frac{1}{2} (- 1 + 0 + 2) = \frac{1}{2} .$ Step 5 — $R \hat{x} = Q^{⊤} b$ back-substitute karo. Pehle neeche wali row: $2 \hat{d} = \frac{1}{2} \Rightarrow \hat{d} = \frac{1}{2} .$ Upar wali row: $3 \overset{c}{^} + 23 (\frac{1}{2}) = \frac{5}{3}$ , matlab $3 \overset{c}{^} = \frac{5}{3} - 3 = \frac{5 - 3}{3} = \frac{2}{3}$ , toh $\overset{c}{^} = \frac{2}{3}$ . Wahi answer $\overset{c}{^} = \frac{2}{3}, \hat{d} = \frac{1}{2}$ — $A^{⊤} A$ kabhi banaya hi nahi. ✓

Problem 4.2

Algebraically show karo ki $R \hat{x} = Q^{⊤} b$ same equation hai jaise normal equations jab $A = QR$ aur $R$ invertible ho.

Recall Solution

Normal equations se shuru karo aur $A = QR$ substitute karo: $(QR)^{⊤} (QR) \hat{x} = (QR)^{⊤} b .$ Product ka transpose order reverse karta hai: $(QR)^{⊤} = R^{⊤} Q^{⊤}$ . Toh left side hai $R^{⊤} Q^{⊤} QR \hat{x}$ . Kyunki $Q$ ke orthonormal columns hain, $Q^{⊤} Q = I$ (identity), jo drop ho jaata hai: $R^{⊤} R \hat{x} = R^{⊤} Q^{⊤} b .$ $R$ invertible hai (full rank), toh $R^{⊤}$ bhi invertible hai; dono sides ko left mein $(R^{⊤})^{- 1}$ se multiply karo: $R \hat{x} = Q^{⊤} b .$ Yeh algebraically identical hain — QR bas usi $\hat{x}$ tak pahunchne ka numerically safer raasta hai.

Level 5 — Mastery

Problem 5.1

Ek rank-deficient case. Maano $A = 111222, b = 102 .$ (a) Show karo ki $A^{⊤} A$ invertible nahi hai. (b) Explain karo ki $\hat{x} = (A^{⊤} A)^{- 1} A^{⊤} b$ mein kya gadbad hoti hai. (c) Projection $\hat{b} = A \hat{x}$ phir bhi nikalo — yeh abhi bhi unique hai — aur minimum-norm $\hat{x}$ bhi do.

Recall Solution

(a) Column 2 exactly $2 \times$ column 1 hai, toh rank $= 1$ hai (columns dependent). Compute karo: $A^{⊤} A = (36612), det = 3 \cdot 12 - 6 \cdot 6 = 36 - 36 = 0.$ Zero determinant ⇒ invertible nahi. (b) $(A^{⊤} A)^{- 1}$ exist nahi karta, toh formula meaningless hai; normal equations ke infinitely many solutions $\hat{x}$ hain (poori ek line), kyunki dependency direction $(2, - 1)$ ke along koi bhi shift $A \hat{x}$ ko unchanged chhod deta hai. (c) Column space single direction $u = (1, 1, 1)$ hai (kyunki dono columns uske multiples hain). $b$ ko $u$ par project karo: $\hat{b} = \frac{u ^{⊤} b}{u ^{⊤} u} u = \frac{1 + 0 + 2}{3} (1, 1, 1) = 1 \cdot (1, 1, 1) = (1, 1, 1) .$ Yeh projection unique hai chahe $\hat{x}$ nahi. Ek $\hat{x}$ choose karne ke liye: koi bhi $(c, d)$ jahan $c + 2 d = 1$ hoga. Minimum-norm choice (via Pseudoinverse (Moore-Penrose)) $c^{2} + d^{2}$ minimise karta hai subject to $c + 2 d = 1$ ; $\hat{x} = \frac{1}{5} (1, 2)$ use karna $c = \frac{1}{5}, d = \frac{2}{5}$ deta hai, aur indeed $\frac{1}{5} + 2 \cdot \frac{2}{5} = \frac{1}{5} + \frac{4}{5} = 1$ . ✓

Problem 5.2

Weighted least squares. Maano measurement 2, measurements 1 aur 3 se do baar reliable hai, toh tum residuals ko $w = (1, 2, 1)$ se weight karte ho aur $\sum_{i} w_{i}^{2} r_{i}^{2}$ minimise karte ho. Show karo ki yeh $W A$ aur $W b$ par ordinary least squares hai jahan $W = diag (1, 2, 1)$ , aur modified normal equations likho.

Recall Solution

Objective rewrite karo. $r = b - A x$ ke saath, $\sum_{i} w_{i}^{2} r_{i}^{2} = ∥ W (b - A x) ∥^{2} = ∥ W b - W A x ∥^{2},$ kyunki $W = diag (1, 2, 1)$ har component ko scale karta hai aur $∥ \cdot ∥^{2}$ squares sum karta hai. Yeh exactly ordinary least squares hai data matrix $\tilde{A} = W A$ aur target $\tilde{b} = W b$ ke saath. Normal equations $\tilde{A}, \tilde{b}$ par apply karo: $\tilde{A}^{⊤} \tilde{A} \hat{x} = \tilde{A}^{⊤} \tilde{b} ⟹ (W A)^{⊤} (W A) \hat{x} = (W A)^{⊤} W b .$ Kyunki $W$ diagonal hai (symmetric), $(W A)^{⊤} = A^{⊤} W$ , toh $W^{⊤} W = W^{2} = diag (1, 4, 1)$ ke saath: $A^{⊤} W^{2} A \hat{x} = A^{⊤} W^{2} b .$ Matlab: trustworthy points ( $w_{2} = 2$ , toh $w_{2}^{2} = 4$ ) fit ko apni taraf char guna zyada khainchte hain. Yeh weighted Linear Regression ka bridge hai.

Recall Pure page ke liye ek-line self-check

Kya tum memory se (1) ek line fit ke liye $A, b$ setup kar sakte ho, (2) normal equations se solve kar sakte ho, (3) usi problem ko QR se solve kar sakte ho, (4) $A^{⊤} r = 0$ verify kar sakte ho, aur (5) explain kar sakte ho kyun QR normal equations se conditioning mein better hai? Agar sab paanch ke liye haan, toh yeh topic tumhara hai.