Exercises — Gram-Schmidt orthogonalization — algorithm

$c=\frac{⟨v,u⟩}{⟨u,u⟩}.$ Kyun: hum demand karte hain ki $⟨v-cu,u⟩=0$. Expand karo: $⟨v,u⟩-c⟨u,u⟩=0$, $c$ ke liye solve karo. Yeh value guess nahi hai — yeh zero leftover overlap require karne se force hoti hai. Upar wali figure mein right triangle dekho: $cu$ base (shadow) hai aur $v-cu$ vertical leg hai jo right angle pe milti hai.

$u_1=v_1=(4,0)$. Kyun: pehle vector ke pehle kuch nahi hota jiske saath perpendicular hona ho, toh koi overlap subtract karne ko nahi hai. Gram–Schmidt hamesha $v_1$ copy karke shuru karta hai.

$⟨v,u⟩=2\cdot 3+2\cdot 1=8$. $⟨u,u⟩=3\cdot 3+1\cdot 1=10$. Yahi do numbers hain jo tum coefficient $c=8/10=0.8$ mein daalo.

$u_1=(2,0)$. $⟨v_2,u_1⟩=1\cdot 2+1\cdot 0=2$; $⟨u_1,u_1⟩=4$; toh $c=2/4=\frac{1}{2}$. $u_2=(1,1)-\frac{1}{2}(2,0)=(1,1)-(1,0)=(0,1).$ Check: $⟨u_1,u_2⟩=2\cdot 0+0\cdot 1=0$ ✅. Leftover seedha upar point karta hai, horizontal $u_1$ ke perpendicular.

$\Vert u_1\Vert =\sqrt{4}=2$, toh $e_1=\frac{1}{2}(2,0)=(1,0)$. $\Vert u_2\Vert =\sqrt{1}=1$, toh $e_2=(0,1)$. Orthonormal set standard basis $\{(1,0),(0,1)\}$ hai — clean aur unit length.

$u_1=(0,5)$. $⟨v_2,u_1⟩=0\cdot 0+4\cdot 5=20$; $⟨u_1,u_1⟩=25$; $c=20/25=0.8$. $u_2=(4,4)-0.8(0,5)=(4,4)-(0,4)=(4,0).$ Check: $⟨u_1,u_2⟩=0\cdot 4+5\cdot 0=0$ ✅. Normalize: $\Vert u_1\Vert =5\Rightarrow e_1=(0,1)$; $\Vert u_2\Vert =4\Rightarrow e_2=(1,0)$.

$u_1=(1,1,1)$, $⟨u_1,u_1⟩=3$. $⟨v_2,u_1⟩=1+1+0=2$; $c=\frac{2}{3}$: $u_2=(1,1,0)-\frac{2}{3}(1,1,1)=\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right).$ $⟨u_2,u_2⟩=\frac{1}{9}+\frac{1}{9}+\frac{4}{9}=\frac{6}{9}=\frac{2}{3}$. Ab $u_3$: dono $u_1$ aur $u_2$ ke saath overlaps subtract karo. $⟨v_3,u_1⟩=1$, coefficient $=1/3$. $⟨v_3,u_2⟩=1\cdot \frac{1}{3}+0+0=\frac{1}{3}$, coefficient $=\frac{1/3}{2/3}=\frac{1}{2}$. $u_3=(1,0,0)-\frac{1}{3}(1,1,1)-\frac{1}{2}\left(\frac{1}{3},\frac{1}{3},-\frac{2}{3}\right).$ $=(1,0,0)-\left(\frac{1}{3},\frac{1}{3},\frac{1}{3}\right)-\left(\frac{1}{6},\frac{1}{6},-\frac{1}{3}\right)=\left(\frac{1}{2},-\frac{1}{2},0\right).$ Check: $⟨u_3,u_1⟩=\frac{1}{2}-\frac{1}{2}+0=0$ ✅; $⟨u_3,u_2⟩=\frac{1}{6}-\frac{1}{6}+0=0$ ✅.

Jab hum $u_k$ banate hain toh use har already-settled vector $u_1,\dots ,u_{k-1}$ ke perpendicular banana hota hai. $u_2$ ke liye ek earlier vector hai ($u_1$) → ek subtraction. $u_3$ ke liye do hain ($u_1,u_2$) → do subtractions. Har subtraction ek clean direction ke saath overlap ko exactly kill karta hai, aur kyunki woh clean directions already mutually orthogonal hain, subtractions interfere nahi karte (isliye hum $u_j$ pe project karte hain, raw $v_j$ pe nahi — dekho Orthogonal projection).

$u_1=(1,0,0)$. $v_2=(2,0,0)$ ke liye: $c=⟨v_2,u_1⟩/⟨u_1,u_1⟩=2/1=2$, toh $u_2=(2,0,0)-2(1,0,0)=(0,0,0)$. $u_2=0$ kyunki $v_2$ sirf $2v_1$ hai — yeh puri tarah $u_1$ ke span mein hai, zero leftover chhodta hai. Yeh signal karta hai ki input set linearly independent nahi hai (dekho Linear independence). Zero vector ko normalize nahi kar sakte (division by zero).

Parent se: $u_1=(3,1)$, $u_2=(-0.4,1.2)$. $\Vert u_1\Vert =\sqrt{10}$, $\Vert u_2\Vert =\sqrt{1.6}$. $e_1=\frac{1}{\sqrt{10}}(3,1),e_2=\frac{1}{\sqrt{1.6}}(-0.4,1.2).$ $R$ entries projection/length data hain: $R_{11}=\Vert u_1\Vert =\sqrt{10}$, $R_{22}=\Vert u_2\Vert =\sqrt{1.6}$, aur $R_{12}=⟨v_2,e_1⟩=\frac{⟨v_2,u_1⟩}{\Vert u_1\Vert }=\frac{8}{\sqrt{10}}$. $Q=\left(\begin{array}{cc}3/\sqrt{10}& -0.4/\sqrt{1.6}\\ 1/\sqrt{10}& 1.2/\sqrt{1.6}\end{array}\right),R=\left(\begin{array}{cc}\sqrt{10}& 8/\sqrt{10}\\ 0& \sqrt{1.6}\end{array}\right).$ Sanity: $R$ upper-triangular hai (diagonal ke neeche zero) aur $R_{11}{R}_{22}=\sqrt{10}\cdot \sqrt{1.6}=4$, jo $|\det A|=|3\cdot 2-1\cdot 2|=4$ ke equal hai ✅.

$e_1=(1,0)$ already unit length hai. $⟨v_2,e_1⟩=1$. Phir $u_2=(1,1)-1\cdot (1,0)=(0,1)$, already unit hai, toh $e_2=(0,1)$. Kyun koi denominator nahi: jab hum ek unit vector $e_j$ pe project karte hain, toh coefficient $\frac{⟨v,e_j⟩}{⟨e_j,e_j⟩}=\frac{⟨v,e_j⟩}{1}=⟨v,e_j⟩$ hota hai. Self-inner-product $1$ hai, toh division disappear ho jaata hai.

$⟨p_1,p_1⟩={\int }_{-1}^{1}1dx=2$, toh $e_1=\frac{1}{\sqrt{2}}$. $p_2$ ka $p_1$ ke saath overlap: $⟨p_2,p_1⟩={\int }_{-1}^{1}xdx=0$ (odd function). Toh $u_2=x-0=x$. $⟨x,x⟩={\int }_{-1}^1{x}^{2}dx=\frac{2}{3}$, toh $\Vert u_2\Vert =\sqrt{2/3}$ aur $e_2=\sqrt{\frac{3}{2}}x$. Insight: machine bilkul identical hai — dot products sirf integrals ban gaye. Yeh $e_1,e_2$ pehle do (normalized) Legendre polynomials hain.

Maano $v_k\in \mathrm{span}(v_1,\dots ,v_{k-1})=\mathrm{span}(u_1,\dots ,u_{k-1})$ (spans construction se match karte hain). Likho $v_k={\sum }_{j<k}{\alpha }_j{u}_j$. Gram–Schmidt formula precisely us span pe projection subtract karta hai: $u_k=v_k-{\sum }_{j<k}\frac{⟨v_k,u_j⟩}{⟨u_j,u_j⟩}{u}_j.$ Kyunki $u_j$ orthogonal hain, $\frac{⟨v_k,u_j⟩}{⟨u_j,u_j⟩}={\alpha }_j$, toh sum exactly $v_k$ reconstruct karta hai, giving $u_k=v_k-v_k=0$. Zero residual matlab "kuch naya nahi" — koi perpendicular leftover exist nahi karta kyunki $v_k$ ne koi naya direction add nahi kiya. Isliye zero $u_k$ Gram–Schmidt ka built-in dependence detector hai.

$e_1$ ke along coordinate: $⟨b,e_1⟩=3$. $e_2$ ke along: $⟨b,e_2⟩=5$. Toh $b=3e_1+5e_2$. Kyun itna easy: general basis mein tum linear system solve karte. Orthonormal basis ke saath, har coordinate decouple ho jaata hai: $b={\sum }_k⟨b,e_k⟩e_k$, har axis ke liye ek independent dot product. Isliye least squares Gram–Schmidt use karta hai — normal equations diagonal ban jaate hain (koi cross-terms nahi), toh har best-fit coefficient directly padha jaata hai.

Har settled vector ko apna denominator chahiye ::: $⟨u_j,u_j⟩$, har baar recompute karo. Zero residual $u_k=0$ ka matlab ::: input set linearly dependent tha. Orthonormal basis mein coordinates hain ::: single dot products $⟨b,e_k⟩$. $2\times 2$ QR mein $R_{11}{R}_{22}$ equal hota hai ::: $|\det A|$ ke.