QR decomposition — Hinglish notes

4.5.36 · Maths › Linear Algebra (Full)

QR decomposition HAI KYA?

YEH CHAHIYE KYU?

Least squares solve karna $min ∥ A x - b ∥$ trivial ho jaata hai: $R x = Q^{⊤} b$ (sirf back-substitution, koi normal-equation squaring nahi jo numerical accuracy bigaad de).
Orthonormal columns ka matlab hai lengths aur angles preserve hote hain — $Q$ ek rotation/reflection hai.
Yeh QR algorithm ka engine hai eigenvalues ke liye.

KAISE: QR ko Gram–Schmidt se derive karo (first principles)

Maano $A = [a_{1} ∣ a_{2} ∣ \dots ∣ a_{n}]$ (columns).

Step 1 — pehla axis banao. Humein ek unit vector chahiye jo $a_{1}$ ki taraf point kare: $u_{1} = a_{1}, q_{1} = \frac{u _{1}}{∥ u _{1} ∥} .$ Kyun? $q_{1}$ hamaari pehli orthonormal direction hai; baaki sab cheezein iske against measure ki jaayengi.

Step 2 — jo already explain ho chuka hai use hataao. $a_{2}$ ke liye, uska shadow (projection) $q_{1}$ par subtract karo: $u_{2} = a_{2} - (q_{1}^{⊤} a_{2}) q_{1}, q_{2} = \frac{u _{2}}{∥ u _{2} ∥} .$ Kyun? Bacha hua $u_{2}$ , $a_{2}$ ka woh hissa hai jo $q_{1}$ ke perpendicular hai, isliye $q_{2} ⊥ q_{1}$ .

Step k — saare pehle ke shadows subtract karo. $u_{k} = a_{k} - \sum_{i < k} (q_{i}^{⊤} a_{k}) q_{i}, q_{k} = \frac{u _{k}}{∥ u _{k} ∥} .$

Step — $R$ padho. Har relation ko invert karo taaki original $a_{k}$ ko $q_{i}$ ke terms mein express kiya ja sake: $a_{k} = r_{k k} ∥ u_{k} ∥ q_{k} + \sum_{i < k} r_{ik} (q_{i}^{⊤} a_{k}) q_{i} .$

Toh $a_{k}$ mein $q_{i}$ ka coefficient hai $r_{ik} = q_{i}^{⊤} a_{k} (i < k), r_{k k} = ∥ u_{k} ∥, r_{ik} = 0 (i > k) .$

$a_{k} = \sum_{i} r_{ik} q_{i}$ ko saare $k$ ke liye stack karna exactly matrix equation $A = QR$ hai. ∎

Worked Example 1 — ek saaf $2 \times 2$

$A = 101110 .$

Column 1. $u_{1} = a_{1} = (1, 0, 1)$ , $∥ u_{1} ∥ = 2$ . $q_{1} = \frac{1}{2} (1, 0, 1)$ . Yeh step kyun? Pehla axis = normalized pehla column.

Projection coefficient. $r_{12} = q_{1}^{⊤} a_{2} = \frac{1}{2} (1 \cdot 1 + 0 \cdot 1 + 1 \cdot 0) = \frac{1}{2}$ . Kyun? Yeh measure karta hai ki $a_{2}$ ka kitna hissa $q_{1}$ ke along already hai.

Column 2. $u_{2} = a_{2} - r_{12} q_{1} = (1, 1, 0) - \frac{1}{2} \cdot \frac{1}{2} (1, 0, 1) = (\frac{1}{2}, 1, - \frac{1}{2}) .$ $∥ u_{2} ∥ = \frac{1}{4} + 1 + \frac{1}{4} = \frac{3}{2}$ , isliye $r_{22} = 3/2$ . $q_{2} = \frac{1}{3/2} (\frac{1}{2}, 1, - \frac{1}{2})$ .

Result. $Q = \frac{1}{2} 0 \frac{1}{2} \frac{1/2}{3/2} \frac{1}{3/2} \frac{- 1/2}{3/2}, R = [20 \frac{1}{2} 3/2] .$ Check: $Q^{⊤} Q = I$ aur $QR = A$ .

Worked Example 2 — least squares via QR

$min ∥ A x - b ∥$ solve karo upar wale $A$ ke saath aur $b = (1, 2, 3)$ .

QR kyun help karta hai. $∥ A x - b ∥^{2} = ∥ QR x - b ∥^{2}$ . Kyunki $Q$ length preserve karta hai, andar $Q^{⊤}$ se multiply karo (full $Q$ tak extend karo): minimizer satisfy karta hai $R x = Q^{⊤} b .$ Kyun? $A = QR \Rightarrow A^{⊤} A x = A^{⊤} b \Rightarrow R^{⊤} Q^{⊤} QR x = R^{⊤} Q^{⊤} b \Rightarrow R^{⊤} R x = R^{⊤} Q^{⊤} b$ . Invertible $R^{⊤}$ cancel karo: $R x = Q^{⊤} b$ . $A$ ki koi squaring nahi → numerically stable.

Compute $Q^{⊤} b$ :

$(q_{1}^{⊤} b) = \frac{1}{2} (1 + 0 + 3) = \frac{4}{2} = 22 .$
$(q_{2}^{⊤} b) = \frac{1}{3/2} (\frac{1}{2} \cdot 1 + 1 \cdot 2 - \frac{1}{2} \cdot 3) = \frac{1}{3/2} \cdot 1 = 2/3 .$

Back-substitute $R x = Q^{⊤} b$ : Row 2: $3/2 x_{2} = 2/3 \Rightarrow x_{2} = \frac{2/3}{3/2} = \frac{2}{3} .$ Row 1: $2 x_{1} + \frac{1}{2} x_{2} = 22 \Rightarrow x_{1} = 2 - \frac{1}{2} x_{2} = 2 - \frac{1}{3} = \frac{5}{3} .$

Toh $x = (\frac{5}{3}, \frac{2}{3})$ . Baar pe trust kyun karein? Triangular solve exact hota hai aur $A^{⊤} A$ form karne se bachta hai.

Forecast-then-Verify

Common Mistakes

Active Recall

Recall Test yourself (hidden)

$R$ upper triangular kyun hai? → kyunki $a_{k}$ sirf $q_{1} \dots q_{k}$ use karta hai.
Least-squares shortcut kya hai? → $R x = Q^{⊤} b$ .
$Q$ kya property guarantee karta hai? → $Q^{⊤} Q = I$ (length/angle preserving).
QR unique kya banata hai? → $r_{k k} > 0$ .

Recall Feynman: 12 saal ke bacche ko samjhao

Socho tumhare paas teen thode tedhe arrows hain kaagaz par. Tum unhe ek saaf set of perpendicular arrows se describe karna chahte ho (jaise ek room ka corner: upar, daayein, aage). Pehle arrow 1 ko rakho, bas use length 1 tak shrink karo — yeh tumhari pehli clean direction hai. Arrow 2 ke liye, woh hissa mitao jo arrow 1 ki taraf point karta hai, aur jo bacha hua hai woh ek brand-new perpendicular direction mein point karta hai — use length 1 tak clean karo. Repeat karo. Saaf perpendicular arrows Q ke columns hain. "Har clean arrow ka kitna use kiya" ki instructions R banati hain. Unhe wapas multiply karo aur original tedhe arrows rebuild ho jaate hain: $A = QR$ .

Connections

Gram-Schmidt process — woh algorithm jo QR package karta hai.
Orthonormal bases and projections — projections $= q_{i}^{⊤} a_{k}$ , $R$ ke entries hain.
Least squares and normal equations — QR stable solver hai.
Householder reflections — production-grade tarika QR paane ka.
Eigenvalues and the QR algorithm — $A_{k + 1} = R_{k} Q_{k}$ iterate karna.
LU decomposition — sibling factorization (triangular but not orthogonal).

QR decomposition

A

ko kya factor karta hai?

A = QR

jisme

Q

ke orthonormal columns (

Q^{⊤} Q = I

) aur

R

upper-triangular with positive diagonal.

R

upper-triangular kyun hai?

Kyunki har

a_{k}

sirf

q_{1}, \dots, q_{k}

ka combination hai, isliye coefficients

r_{ik} = 0

jab

i > k

R

ke off-diagonal entries ka formula?

r_{ik} = q_{i}^{⊤} a_{k}

jab

i < k

R

ke diagonal entries ka formula?

r_{k k} = ∥ u_{k} ∥

, orthogonalized

k

-th column ka norm.

QR ke saath least squares kaise solve karte hain?

R x = Q^{⊤} b

ko back-substitution se solve karo.

Thin aur full QR mein difference?

Thin:

Q

m \times n

hai (sirf

Q^{⊤} Q = I

). Full:

Q

m \times m

orthogonal hai.

QR decomposition unique kya banata hai?

r_{k k} > 0

require karna (positive diagonal).

Ek orthogonal matrix

A

ka QR?

Q = A

R = I

QR kis algorithm se bana hai?

Gram–Schmidt process se.

Normal equations

A^{⊤} A x = A^{⊤} b

ke upar QR kyun prefer karte hain?

A^{⊤} A

form karne se bachta hai, jo condition number square kar deta hai; QR numerically stable hai.