Gram-Schmidt orthogonalization — algorithm: Question bank

4.5.35 · D5 · Maths › Linear Algebra (Full) › Gram-Schmidt orthogonalization — algorithm

Questions se pehle, teen chhote reminders taaki har symbol samajh aa sake:

Sahi hai ya galat — justify karo

Order matter karta hai:

v_{1}

aur

v_{2}

ko swap karne se resulting orthogonal set badal sakta hai.

Sahi —

u_{1}

hamesha pehla input untouched hota hai, isliye alag pehla vector ek alag chain seed karta hai aur generally alag (lekin phir bhi orthogonal, same-span) results deta hai.

Gram–Schmidt har stage par span preserve karta hai:

span (u_{1}, \dots, u_{k}) = span (v_{1}, \dots, v_{k})

Sahi — har

u_{k}

v_{k}

minus earlier vectors ka combination hai, jo ek invertible triangular change of basis hai, isliye koi direction kabhi gain ya lose nahi hoti.

Agar inputs pehle se mutually orthogonal hain, toh Gram–Schmidt unhe unchanged chhod deta hai (normalization tak).

Sahi — har projection coefficient

⟨ v_{k}, u_{j} ⟩

pehle se zero hai, isliye kuch subtract nahi hota aur

u_{k} = v_{k}

rehta hai.

Output

u_{k}

sirf turant pehle waale

u_{j}

ke liye nahi, balki sab previous

u_{j}

ke liye orthogonal hai.

Sahi — hum har settled

u_{j}

par shadow ek saath subtract karte hain, aur kyunki wo

u_{j}

mutually orthogonal hain, cross terms cancel ho jaate hain, jo ek saath sabse overlap khatam kar deta hai.

Nonzero vectors ka ek orthogonal set automatically linearly independent hota hai.

Sahi — agar koi combination zero mein sum ho, toh kisi bhi

u_{i}

se dot karne par uska coefficient times

⟨ u_{i}, u_{i} ⟩ \neq = 0

isolate ho jaata hai, jo har coefficient ko zero hone par majboor karta hai.

Pehle normalize karna (

e_{j}

use karke) aur baad mein normalize karna same final orthonormal basis dete hain.

Sahi — dono routes same orthogonal directions produce karte hain; farq sirf yeh hai ki aap lengths se kab divide karte ho, aur wo kabhi vector ko rotate nahi karta.

Gram–Schmidt ko vectors ka

R^{n}

mein usual dot product ke saath rehna zaroori hai.

Galat — ye kisi bhi inner product space mein kaam karta hai (jaise functions ke saath

⟨ f, g ⟩ = \int f g

); sirf

⟨ \cdot, \cdot ⟩

ka matlab badalta hai.

Agar koi

u_{k}

zero vector nikle, toh arithmetic mein galti hui hai.

Galat — zero

u_{k}

algorithm ka sahi tarike se report karna hai ki

v_{k}

earlier vectors par linearly dependent tha; problem tumhari arithmetic mein nahi, inputs mein tha.

Resulting QR decomposition mein

R

ke diagonal par zeros ho sakte hain.

Independent inputs ke liye Galat — ek diagonal zero ka matlab hoga ki koi

∥ u_{k} ∥ = 0

hai, yaani ek dependent vector, jo exactly wahi hai jo independence forbid karta hai.

Error dhundo

"Main

v_{2}

u_{1}

ki jagah

v_{1}

par uski projection subtract karke orthogonalize karunga." — kahan galat hai?

Yahan

u_{1} = v_{1}

hai isliye doosre vector ke liye ye theek ho jaata hai, lekin ye adat

v_{3}

se fail ho jaati hai: raw

v_{2}

(jo

v_{1}

ke orthogonal nahi hai) par project karne se cross terms

⟨ v_{j}, v_{i} ⟩ \neq = 0

reh jaate hain aur perpendicularity ka proof toot jaata hai.

u_{1}

find karne ke baad, maine use

e_{1}

mein normalize kiya, phir

u_{2} = v_{2} - \frac{⟨ v _{2} , e _{1} ⟩}{⟨ e _{1} , e _{1} ⟩} e_{1}

compute kiya." — kya redundant hai?

Denominator: jab

e_{1}

ek unit vector hai toh

⟨ e_{1}, e_{1} ⟩ = 1

, isliye ye sirf

u_{2} = v_{2} - ⟨ v_{2}, e_{1} ⟩ e_{1}

hona chahiye; denominator rakhna galat nahi hai, sirf conventions ko carelessly mix karna galat hai.

"Mera set orthogonal nikla lekin main check karna bhool gaya ki ye original space ko span karta hai ya nahi." — kya ye sach mein fikar ki baat hai?

Nahi — recursion same vectors ka ek triangular, invertible reshuffle hai, isliye span guaranteed preserved rehta hai; span ko re-verify karne ki zaroorat kabhi nahi, sirf orthogonality check karo agar arithmetic slips ka dar ho.

"Mujhe

⟨ u_{2}, u_{1} ⟩ = 0.0001

mila exactly 0 ki jagah, toh mera method kharab hai." — diagnosis?

Method exact hai; ek tiny nonzero finite-precision arithmetic ka rounding error hai, jo classical Gram–Schmidt ki jaani-mani weakness hai aur numerically zyada stable modified variant ko motivate karta hai.

"Orthonormalize karne ke liye maine har

u_{k}

⟨ u_{k}, u_{k} ⟩

se divide kiya." — theek karo.

Tumne squared length se divide kiya; norm

∥ u_{k} ∥ = ⟨ u_{k}, u_{k} ⟩

hota hai, isliye

e_{k} = u_{k} / ⟨ u_{k}, u_{k} ⟩

use karo warna resulting vectors unit length nahi honge.

"Maine

v_{3}

u_{1}

aur

u_{2}

par project kiya lekin ek denominator mein

⟨ v_{3}, u_{2} ⟩

ki jagah

⟨ v_{3}, v_{2} ⟩

use kiya." — kya toot gaya?

Denominator

⟨ u_{j}, u_{j} ⟩

hona chahiye, settled vector khud se dot kiya hua;

v

's ya alag terms ke numerators mix karne se shadow galat scale ho jaata hai aur orthogonality khatam ho jaati hai.

Why questions

u_{j}

par shadow subtract kyon karte hain aur

v_{j}

par kabhi nahi?

Sirf

u_{j}

mutually orthogonal hain, isliye unka overlap independent hai aur har ek ko alag hataane se ek clean residual milta hai;

v_{j}

abhi bhi ek doosre se overlap karte hain, isliye unki shadows subtract karne se dobara overlap aa jaata hai.

Projection scalar exactly

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

kyun hona chahiye?

Ye unique value hai jo leftover ko perpendicular banata hai:

⟨ v - c u, u ⟩ = 0

impose karne aur

c

ke liye solve karne se koi freedom nahi bachti, isliye orthogonality

c

choose karta hai, hamari marzi nahi.

Input vectors linearly independent kyun hone chahiye?

Ek dependent

v_{k}

poori tarah earlier vectors ke span mein hota hai, isliye uski saari shadows subtract karne se sab kuch hat jaata hai, giving

u_{k} = 0

jo normalize nahi ho sakta (zero se division).

Orthogonality coordinates ko "decouple" kyun karta hai?

Ek orthonormal basis mein

e_{k}

along vector ka coordinate sirf

⟨ v, e_{k} ⟩

hota hai, jo doosron se independent compute ho sakta hai — koi simultaneous equations nahi, aur exactly isliye Least squares orthogonal bases ko pasand karta hai.

Gram–Schmidt QR decomposition ke "equivalent" kyun hai?

Orthonormal outputs

Q

ke columns banate hain, aur raaste mein compute kiye gaye projection coefficients exactly upper-triangular

R

ke entries hain jo original vectors rebuild karta hai.

Agar hmare paas pehle se perpendicular vectors hain toh normalize kyon karna?

Perpendicularity direction handle karta hai; normalizing length handle karta hai, aur sirf unit vectors clean formulas

⟨ v, e_{k} ⟩

coordinates ke liye aur ek actual Orthonormal basis dete hain.

Perpendicularity ka proof induction par kyun depend karta hai?

Har step assume karta hai ki earlier

u_{j}

pehle se mutually orthogonal hain taaki sum collapse ho sake; wo assumption pehle ke vectors ke liye establish ki jaani chahiye, jo exactly ek inductive chain hai.

Edge cases

Agar tum sirf ek vector

v_{1}

feed karo toh kya hoga?

Hataane ke liye kuch nahi —

u_{1} = v_{1}

, aur normalization

e_{1} = v_{1} / ∥ v_{1} ∥

deta hai; algorithm trivially complete hai.

Agar do input vectors identical hain,

v_{2} = v_{1}

Overlap total hai, isliye

u_{2} = v_{1} - proj_{u_{1}} (v_{1}) = 0

, jo sahi tarike se flag karta hai ki pair dependent hai.

Agar koi input vector zero vector hai?

Uski koi direction nahi hai, uski norm zero hai, isliye ye immediately independence fail karta hai aur normalize nahi ho sakta — input set shuru se hi invalid thi.

Agar do inputs pehle se perpendicular hain lekin unit length nahi?

Gram–Schmidt kuch subtract nahi karta (unka projection coefficient zero hai) aur sirf final normalization step unhe unit length tak rescale karta hai.

Ek infinite-dimensional inner product space mein (jaise polynomials), kya Gram–Schmidt terminate hota hai?

Inputs ki kisi bhi finite list ke liye, haan — recursion exactly

k

baar chalta hai; space ka infinite-dimensional hona kabhi matter nahi karta jab tak tumhara input set finite hai.

Agar sab inputs

R^{3}

ke andar ek 2-D plane mein hain, toh teesra output kaisa dikhta hai?

Teesra vector pehle do par dependent hai, isliye uska residual

u_{3} = 0

hai; algorithm sirf ek 2-D orthogonal set produce karta hai, jo unke span ki true dimension se match karta hai.

Recall Ek-line survival summary

Is page ke har trap ka ek sentence mein hal hai. The single mantra ::: "Har settled $u_{j}$ par shadow subtract karo, leftover rakho, aur zero leftover ko dependence ka sign samjho."

Connections

Orthogonal projection — shadow operation jiske around har trap ghoomta hai
Linear independence — zero $u_{k}$ actually kya report kar raha hai
Inner product spaces — kyun ye method ordinary dot product se aage kaam karta hai
QR decomposition — jahan coefficients aur $Q$ columns end up hote hain
Orthonormal basis — wo object jo normalization deliver karta hai
Least squares — decoupled orthogonal coordinates ka payoff