Gram-Schmidt orthogonalization — algorithm

4.5.35 · Maths › Linear Algebra (Full)

What it does

Deriving the algorithm from scratch (HOW + WHY)

Poori machine ek hi tool par tiki hai: projection of a vector onto another vector.

Step 1 — $v$ ko $u$ par project karo. Hum ek scalar $c$ chahte hain jisse $c u$ , $v$ ka shadow ho $u$ ke along, aur bacha hua $r = v - c u$ , $u$ ke orthogonal ho. Orthogonality impose karo: $⟨ v - c u, u ⟩ = 0 ⟹ ⟨ v, u ⟩ - c ⟨ u, u ⟩ = 0 ⟹ c = \frac{⟨ v , u ⟩}{⟨ u , u ⟩} .$

Step 2 — Orthogonal set ko ek ek vector karke build karo.

$u_{1} = v_{1}$ (pehla vector already "clean" hai; abhi kuch remove nahi karna).
Har naye $v_{k}$ ke liye, uska overlap subtract karo har already-built $u_{1}, \dots, u_{k - 1}$ se:

Saare pichle $u_{j}$ se subtract kyun karte hain? Har $u_{j}$ already mutually orthogonal hai, isliye har ek se overlap alag alag remove karne par $u_{k}$ saare ke perpendicular ho jaata hai ek saath. Chaliye key claim prove karte hain.

Figure — Gram-Schmidt orthogonalization — algorithm

Worked Example 1 (in $R^{2}$ )

$v_{1} = (3, 1), v_{2} = (2, 2)$ ko orthonormalize karo.

Step A: $u_{1} = v_{1} = (3, 1)$ . Kyun? Pehla vector as-is liya jaata hai.

Step B: $⟨ v_{2}, u_{1} ⟩ = 2 \cdot 3 + 2 \cdot 1 = 8$ , aur $⟨ u_{1}, u_{1} ⟩ = 9 + 1 = 10$ . $u_{2} = (2, 2) - \frac{8}{10} (3, 1) = (2, 2) - (2.4, 0.8) = (- 0.4, 1.2) .$ Kyun? Humne $v_{2}$ ka woh hissa remove kiya jo $u_{1}$ ke along lean kar raha tha.

Check: $⟨ u_{1}, u_{2} ⟩ = 3 (- 0.4) + 1 (1.2) = - 1.2 + 1.2 = 0.$ ✅

Step C — normalize: $∥ u_{1} ∥ = 10$ , $∥ u_{2} ∥ = 0.16 + 1.44 = 1.6$ . $e_{1} = \frac{1}{10} (3, 1), e_{2} = \frac{1}{1.6} (- 0.4, 1.2) .$

Worked Example 2 (in $R^{3}$ )

$v_{1} = (1, 1, 0), v_{2} = (1, 0, 1), v_{3} = (0, 1, 1)$ ko orthogonalize karo.

$u_{1} = (1, 1, 0)$ .
$⟨ v_{2}, u_{1} ⟩ = 1$ , $⟨ u_{1}, u_{1} ⟩ = 2$ : $u_{2} = (1, 0, 1) - \frac{1}{2} (1, 1, 0) = (\frac{1}{2}, - \frac{1}{2}, 1) .$
$u_{3}$ ke liye dono $u_{1}$ aur $u_{2}$ ke saath overlaps subtract karo. $⟨ v_{3}, u_{1} ⟩ = 1, ⟨ u_{1}, u_{1} ⟩ = 2$ . $⟨ v_{3}, u_{2} ⟩ = 0 - \frac{1}{2} + 1 = \frac{1}{2}, ⟨ u_{2}, u_{2} ⟩ = \frac{1}{4} + \frac{1}{4} + 1 = \frac{3}{2}$ . $u_{3} = (0, 1, 1) - \frac{1}{2} (1, 1, 0) - \frac{1/2}{3/2} (\frac{1}{2}, - \frac{1}{2}, 1) = (0, 1, 1) - (\frac{1}{2}, \frac{1}{2}, 0) - (\frac{1}{6}, - \frac{1}{6}, \frac{1}{3}) .$ $u_{3} = (- \frac{2}{3}, \frac{2}{3}, \frac{2}{3}) .$ Yeh step kyun? Do subtractions isliye kyunki do pehle ke orthogonal vectors ko clear karna tha. Check: $⟨ u_{3}, u_{1} ⟩ = - \frac{2}{3} + \frac{2}{3} + 0 = 0$ , $⟨ u_{3}, u_{2} ⟩ = - \frac{1}{3} - \frac{1}{3} + \frac{2}{3} = 0$ . ✅

Common mistakes

Recall Feynman: explain to a 12-year-old

Socho tumhare dost ek wall par shadow daalte hain. Tum chahte ho ki sab log aise directions mein khade hon jahan unke shadows bilkul overlap na karen. Pehle dost ko reference lo. Doosre dost ke liye dekho ki woh pehle ki direction se kitna overlap karta hai, aur use side mein slide karo jab tak overlap zero na ho jaaye. Har naye dost ke liye, already place ho chuke sabhi ke saath overlap remove karo. Uske baad, saare dost poori alag (right-angle) directions mein point karte hain, aur tum har ek ko same height (unit length) par shrink kar sakte ho. Yahi hai Gram–Schmidt: overlap hatao, baaki bachao.

Flashcards

Gram–Schmidt ka woh single operation kya hai jo building block hai?

Projection of a vector onto another:

proj_{u} (v) = \frac{⟨ v , u ⟩}{⟨ u , u ⟩} u

Projection subtract karne se residual orthogonal kyun ho jaata hai?

Hum scalar

c = \frac{⟨ v , u ⟩}{⟨ u , u ⟩}

exactly isliye choose karte hain taaki

⟨ v - c u, u ⟩ = 0

ho.

Gram–Schmidt recursion state karo.

u_{k} = v_{k} - \sum_{j < k} \frac{⟨ v _{k} , u _{j} ⟩}{⟨ u _{j} , u _{j} ⟩} u_{j}

v_{j}

se nahi,

u_{j}

se subtract kyun karte hain?

Sirf

u_{j}

already mutually orthogonal hain, isliye cross terms vanish ho jaate hain;

v_{j}

use karne par nonzero overlaps bach jaate hain.

Process mein koi

u_{k} = 0

ho jaaye toh kya matlab hai?

v_{k}

pehle wale vectors par linearly dependent tha; input set independent nahi thi.

Orthogonal set se orthonormal set kaise banaate hain?

Har

u_{k}

ko uske norm se divide karo:

e_{k} = u_{k} / ∥ u_{k} ∥

Agar already-normalized

e_{j}

use karo, toh recursion kaise simplify hoti hai?

u_{k} = v_{k} - \sum_{j < k} ⟨ v_{k}, e_{j} ⟩ e_{j}

(denominators 1 ho jaate hain).

Gram–Schmidt kis matrix factorization ke equivalent hai?

A = QR

, jahan

Q

ke columns orthonormal

e_{k}

hain aur

R

upper-triangular hai jisme projection coefficients hain.

Connections

Inner product spaces — woh $⟨ \cdot, \cdot ⟩$ jis par Gram–Schmidt rely karta hai
Orthogonal projection — woh single primitive operation jo baar baar use hoti hai
QR decomposition — Gram–Schmidt ek tarika hai $Q$ aur $R$ compute karne ka
Linear independence — input set ke liye required hai
Orthonormal basis — output object
Least squares — orthogonal bases use karta hai normal equations decouple karne ke liye