Worked examples — QR decomposition

4.5.36 · D3 · Maths › Linear Algebra (Full) › QR decomposition

Scenario matrix

Examples kaam karne se pehle, chalte hain har alag cheez list karte hain jo ek QR problem tumpe throw kar sakti hai. Har row ek case class hai; last column uss example ka naam hai jo use cover karta hai.

Ab hum inhe order mein walk karenge. Gram-Schmidt process ke steps yaad rakho — har example wahi process hai, bas alag inputs ke saath.

Geometry ka ek-figure reminder

Har example physically same move karta hai: pehla arrow rakho, phir agli arrow ka shadow phenk do taaki sirf perpendicular part bache.

Example 1 — Case 1: clean tall matrix

1. Pehli axis. ${\mathbf{u}}_1={\mathbf{a}}_1=(1,1,0)$, $\Vert {\mathbf{u}}_1\Vert =\sqrt{1^2+1^2+0^2}=\sqrt{2}$. Toh $r_{11}=\sqrt{2}$ aur ${\mathbf{q}}_1=\frac{1}{\sqrt{2}}(1,1,0)$. Yeh step kyun? Pehli clean direction bas pehla column hai, length 1 tak shrunk karo — koi earlier direction nahi hai jiske perpendicular rehna ho.
2. Shadow coefficient. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\frac{1}{\sqrt{2}}(1\cdot 2+1\cdot 1+0\cdot 1)=\frac{3}{\sqrt{2}}$. Yeh step kyun? $r_{12}$ measure karta hai ${\mathbf{a}}_2$ ka kitna hissa already ${\mathbf{q}}_1$ ke along point karta hai — woh part jo hume remove karna hai.
3. Shadow hatao. ${\mathbf{u}}_2={\mathbf{a}}_2-r_{12}{\mathbf{q}}_1=(2,1,1)-\frac{3}{\sqrt{2}}\cdot \frac{1}{\sqrt{2}}(1,1,0)=(2,1,1)-\frac{3}{2}(1,1,0)=(\frac{1}{2},-\frac{1}{2},1)$. Yeh step kyun? Jo bachta hai woh ${\mathbf{a}}_2$ ka woh piece hai jo ${\mathbf{q}}_1$ ke perpendicular hai — ek bilkul naya direction.
4. Doosri axis. $\Vert {\mathbf{u}}_2\Vert =\sqrt{\frac{1}{4}+\frac{1}{4}+1}=\sqrt{\frac{3}{2}}=r_{22}$, aur ${\mathbf{q}}_2=\frac{1}{\sqrt{3/2}}(\frac{1}{2},-\frac{1}{2},1)$. Yeh step kyun? Normalize karo taaki ${\mathbf{q}}_2$ ki length 1 ho; ab $\{{\mathbf{q}}_1,{\mathbf{q}}_2\}$ orthonormal hai.

Verify: ${\mathbf{q}}_1^{\top }{\mathbf{q}}_2=\frac{1}{\sqrt{2}}\cdot \frac{1}{\sqrt{3/2}}(\frac{1}{2}-\frac{1}{2}+0)=0$ ✓ (perpendicular), har $\mathbf{q}$ ki length 1 hai, aur $QR=A$. Saare diagonal entries positive hain → yeh the unique QR hai.

Example 2 — Case 2: backwards-pointing first column (sign convention)

1. Pehli axis. $\Vert {\mathbf{a}}_1\Vert =\sqrt{(-3{)}^2+(-4{)}^2}=\sqrt{25}=5$, toh $r_{11}=5$ (length hamesha $\ge 0$ hoti hai — minus signs square hoke khatam ho gaye). ${\mathbf{q}}_1=\frac{1}{5}(-3,-4)$. Yeh step kyun? Ek norm negative nahi ho sakta; sign direction ${\mathbf{q}}_1$ mein rehta hai, $r_{11}$ mein nahi. Isliye QR fix karta hai $r_{kk}>0$: sign $Q$ mein force ho jaata hai.
2. Shadow coefficient. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\frac{1}{5}(-3\cdot 0+-4\cdot 5)=\frac{-20}{5}=-4$. Yeh step kyun? $r_{12}$ negative ho sakta hai — matlab sirf yeh hai ki ${\mathbf{a}}_2$ ${\mathbf{q}}_1$ ke against lean karta hai. Off-diagonal signs unconstrained hain.
3. Shadow hatao. ${\mathbf{u}}_2=(0,5)-(-4)\cdot \frac{1}{5}(-3,-4)=(0,5)-(\frac{12}{5},\frac{16}{5})=(-\frac{12}{5},\frac{9}{5})$. Yeh step kyun? Shadow subtract karo taaki ${\mathbf{a}}_2$ ka sirf woh part bache jo ${\mathbf{q}}_1$ ke perpendicular hai; yahan shadow ka khud negative sign hai, toh subtract karne se add back hota hai — wahi rule jaise hamesha, bas signed coefficient ke saath.
4. Doosri axis. $\Vert {\mathbf{u}}_2\Vert =\sqrt{\frac{144}{25}+\frac{81}{25}}=\sqrt{\frac{225}{25}}=3=r_{22}$. ${\mathbf{q}}_2=\frac{1}{3}(-\frac{12}{5},\frac{9}{5})=(-\frac{4}{5},\frac{3}{5})$. Yeh step kyun? Perpendicular leftover ko length 1 tak normalize karo taaki $\{{\mathbf{q}}_1,{\mathbf{q}}_2\}$ orthonormal ho; diagonal entry $r_{22}=3$ phir se ek positive length hai.

Verify: diagonal $5,3>0$ ✓. $Q^{\top }Q=I$ ✓ (compute: $(-\frac{3}{5}{)}^2+(-\frac{4}{5}{)}^2=1$, cross term $(-\frac{3}{5})(-\frac{4}{5})+(-\frac{4}{5})(\frac{3}{5})=\frac{12}{25}-\frac{12}{25}=0$). $QR=A$ ✓. Data ki negativity puri tarah $Q$ mein gayi, $R$ ke diagonal mein kabhi nahi.

Example 3 — Case 3: already-orthogonal matrix (limiting case)

1. Pehli axis. $\Vert {\mathbf{a}}_1\Vert =\sqrt{\frac{1}{2}+\frac{1}{2}}=1$, toh $r_{11}=1$, ${\mathbf{q}}_1={\mathbf{a}}_1$. Yeh step kyun? Column 1 already length 1 hai — normalize karne se kuch nahi badlega.
2. Shadow coefficient. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\frac{1}{\sqrt{2}}\cdot (-\frac{1}{\sqrt{2}})+\frac{1}{\sqrt{2}}\cdot \frac{1}{\sqrt{2}}=-\frac{1}{2}+\frac{1}{2}=0$. Yeh step kyun? Zero shadow matlab ${\mathbf{a}}_2$ already ${\mathbf{q}}_1$ ke perpendicular hai — subtract karne ke liye kuch nahi.
3. Doosri axis. ${\mathbf{u}}_2={\mathbf{a}}_2-0={\mathbf{a}}_2$, $\Vert {\mathbf{u}}_2\Vert =1=r_{22}$, ${\mathbf{q}}_2={\mathbf{a}}_2$. Yeh step kyun? Zero shadow remove karne ke baad, leftover hi ${\mathbf{a}}_2$ hai, aur woh already unit length hai, toh ${\mathbf{q}}_2={\mathbf{a}}_2$ with $r_{22}=1$ — Gram–Schmidt confirm karta hai frame already clean tha.

Verify: $QR=A\cdot I=A$ ✓. Yeh parent note mein predicted "QR kuch nahi karta" limit hai: orthogonal $A$ ke liye, har $r_{kk}=1$ aur har off-diagonal $=0$.

Example 4 — Case 4: already upper-triangular matrix

1. Pehli axis. $\Vert {\mathbf{a}}_1\Vert =\Vert (2,0)\Vert =2=r_{11}$, ${\mathbf{q}}_1=(1,0)$. Yeh step kyun? Column 1 exactly pehle coordinate axis ke along hai, toh uski clean direction hai $(1,0)$ aur length hai $r_{11}=2$.
2. Shadow coefficient. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=(1,0)\cdot (5,3)=5$. Yeh step kyun? $r_{12}$ measure karta hai ${\mathbf{a}}_2$ ${\mathbf{q}}_1$ ke along kitna pahunchta hai — horizontal part $5$ jo hume strip off karna hai.
3. Shadow hatao. ${\mathbf{u}}_2=(5,3)-5(1,0)=(0,3)$, $\Vert {\mathbf{u}}_2\Vert =3=r_{22}$, ${\mathbf{q}}_2=(0,1)$. Yeh step kyun? Horizontal shadow subtract karne se sirf vertical part $(0,3)$ bachta hai, jo normalize hokar second axis $(0,1)$ banta hai — yeh dikhata hai columns already coordinate axes ke along point kar rahe the.

Verify: $QR=I\cdot A=A$ ✓. Key insight: ek already-upper-triangular matrix positive diagonal ke saath apna khud ka $R$ hota hai aur $Q=I$. (Agar diagonal mein negative entry hoti, toh us column ka sign $Q$ mein move ho jaata, exactly Example 2 ki tarah — toh $Q$ diagonal pe $\pm 1$ hota, $I$ nahi.)

Example 5 — Case 5: DEGENERATE, dependent columns (QR breaks)

1. Pehli axis. $\Vert {\mathbf{a}}_1\Vert =\sqrt{1+4}=\sqrt{5}=r_{11}$, ${\mathbf{q}}_1=\frac{1}{\sqrt{5}}(1,2)$. Yeh step kyun? Wahi pehla move jaise hamesha — pehle column ko normalize karo pehli clean direction ke liye; abhi kuch galat nahi hai.
2. Shadow coefficient. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\frac{1}{\sqrt{5}}(1\cdot 2+2\cdot 4)=\frac{10}{\sqrt{5}}=2\sqrt{5}$. Yeh step kyun? Measure karo ${\mathbf{a}}_2$ ka kitna ${\mathbf{q}}_1$ ke along hai; yahan bada coefficient pehla hint hai ki ${\mathbf{a}}_2$ almost entirely ${\mathbf{q}}_1$ ke along point karta hai.
3. Shadow hatao — collapse. ${\mathbf{u}}_2=(2,4)-2\sqrt{5}\cdot \frac{1}{\sqrt{5}}(1,2)=(2,4)-2(1,2)=(0,0)$. Yeh kyun important hai: ${\mathbf{a}}_2$ pura shadow tha — woh exactly ${\mathbf{q}}_1$ ke along lie karta hai. Shadow remove karne ke baad, kuch nahi bacha. $\Vert {\mathbf{u}}_2\Vert =0$, toh $r_{22}=0$.
4. The break. ${\mathbf{q}}_2={\mathbf{u}}_2/\Vert {\mathbf{u}}_2\Vert =(0,0)/0$ undefined hai — division by zero.

Verify: $\det A=1\cdot 4-2\cdot 2=0$, toh columns dependent hain (rank 1). Parent note mein QR theorem ne linearly independent columns assume kiya tha precisely taaki har $\Vert {\mathbf{u}}_k\Vert >0$ ho. Yahan woh assumption fail hoti hai, $r_{22}=0$, aur positive diagonal ke saath thin QR simply exist nahi karta. (Rank-revealing QR with column pivoting yeh handle karta hai, lekin plain algorithm ruk jaata hai.)

Example 6 — Case 6: nearly dependent columns (limiting behaviour)

1. Pehli axis. $\Vert {\mathbf{a}}_1\Vert =1=r_{11}$, ${\mathbf{q}}_1=(1,0)$. Yeh step kyun? Pehla column already ek unit vector hai, toh woh apni clean direction khud hai.
2. Shadow coefficient. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=(1,0)\cdot (1,\epsilon )=1$. Yeh step kyun? ${\mathbf{a}}_2$ ka along-${\mathbf{q}}_1$ part measure karo; ${\mathbf{a}}_2$ ka almost sab kuch yahi shadow hai.
3. Shadow hatao. ${\mathbf{u}}_2=(1,\epsilon )-1\cdot (1,0)=(0,\epsilon )$, toh $r_{22}=\Vert {\mathbf{u}}_2\Vert =\epsilon$. Yeh step kyun? Shadow strip karo; tiny leftover $(0,\epsilon )$ hi woh cheez hai jo column 2 ko column 1 se alag karti hai.
4. Limit lo. Jab $\epsilon \to 0^{+}$, $r_{22}=\epsilon \to 0$. Yeh step kyun? Bachne wala perpendicular part kuch nahi ban jaata — columns ek line mein merge ho rahe hain, Example 5 ke collapse ki tarah.

Verify: $\det A=1\cdot \epsilon -1\cdot 0=\epsilon =r_{11}{r}_{22}$ ✓ (dekho Example 9 — $R$ ke diagonal ka product determinant hai). $\epsilon =10^{-8}$ ke liye, $r_{22}=10^{-8}$: $10^{-8}$ size ka koi bhi rounding error ise daba dega, toh ${\mathbf{q}}_2$ garbage ban jaata hai. Yahi reason hai classical Gram–Schmidt dependence ke paas unstable hai, aur isliye practitioners Householder reflections ya modified Gram–Schmidt switch karte hain.

Example 7 — Case 7: WIDE matrix (rows se zyada columns)

1. Pehli axis. $\Vert {\mathbf{a}}_1\Vert =\Vert (1,0)\Vert =1=r_{11}$, ${\mathbf{q}}_1=(1,0)$. Yeh step kyun? Column 1 normalize karo pehli clean direction ke liye — abhi kaafi room hai.
2. Doosri axis. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=(1,0)\cdot (0,1)=0$, toh ${\mathbf{u}}_2=(0,1)$, $r_{22}=1$, ${\mathbf{q}}_2=(0,1)$. Yeh step kyun? Column 2 already ${\mathbf{q}}_1$ ke perpendicular hai; ab $\{{\mathbf{q}}_1,{\mathbf{q}}_2\}$ pura plane span karta hai — room full hai.
3. Teesri axis — collapse. ${\mathbf{a}}_3=(2,3)$ ke liye: $r_{13}={\mathbf{q}}_1^{\top }{\mathbf{a}}_3=2$, $r_{23}={\mathbf{q}}_2^{\top }{\mathbf{a}}_3=3$. Phir ${\mathbf{u}}_3={\mathbf{a}}_3-r_{13}{\mathbf{q}}_1-r_{23}{\mathbf{q}}_2=(2,3)-2(1,0)-3(0,1)=(0,0)$. Yeh kyun important hai: $\{{\mathbf{q}}_1,{\mathbf{q}}_2\}$ already poore ${\mathbb{R}}^2$ ko span kar chuka hai, toh ${\mathbf{a}}_3$ puri tarah pehle ke directions se bana hai. Har shadow hatane ke baad kuch nahi bachta: $\Vert {\mathbf{u}}_3\Vert =0$, $r_{33}=0$.
4. The break. ${\mathbf{q}}_3=(0,0)/0$ undefined hai. Yeh step kyun? Do directions se perpendicular teesra direction nahi bana sakte jo already plane fill kar chuke hain — geometry forbid karta hai.

Verify: ek $2\times 3$ matrix ke columns teen vectors hain ${\mathbb{R}}^2$ mein, toh woh hamesha linearly dependent hain (tum $2$ dimensions mein $3$ independent vectors nahi rakh sakte). Isliye QR theorem mein $m\ge n$ required hai; ek wide matrix ($n>m$) ka kabhi thin QR nahi ho sakta positive diagonal ke saath — dimension overflow karne wala pehla column $\Vert {\mathbf{u}}_k\Vert =0$ deta hai.

Example 8 — Case 8: least-squares word problem

Over-determined system $Ax=b$ set up karo ek column of ones ($x_1$ ke liye) aur ek column of $t$ ($x_2$ ke liye) ke saath: $A=\left[\begin{array}{cc}1& 0\\ 1& 1\\ 1& 2\end{array}\right],b=\left[\begin{array}{c}1\\ 2\\ 2\end{array}\right].$

1. $A$ ka QR. $\Vert {\mathbf{a}}_1\Vert =\sqrt{3}=r_{11}$, ${\mathbf{q}}_1=\frac{1}{\sqrt{3}}(1,1,1)$. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=\frac{1}{\sqrt{3}}(0+1+2)=\frac{3}{\sqrt{3}}=\sqrt{3}$. ${\mathbf{u}}_2=(0,1,2)-\sqrt{3}\cdot \frac{1}{\sqrt{3}}(1,1,1)=(0,1,2)-(1,1,1)=(-1,0,1)$. $r_{22}=\Vert {\mathbf{u}}_2\Vert =\sqrt{2}$, ${\mathbf{q}}_2=\frac{1}{\sqrt{2}}(-1,0,1)$. Yeh step kyun? QR messy least-squares ko ek triangular solve mein badal deta hai; dekho Least squares and normal equations.
2. $Q^{\top }b$ form karo. ${\mathbf{q}}_1^{\top }b=\frac{1}{\sqrt{3}}(1+2+2)=\frac{5}{\sqrt{3}}$. ${\mathbf{q}}_2^{\top }b=\frac{1}{\sqrt{2}}(-1\cdot 1+0\cdot 2+1\cdot 2)=\frac{1}{\sqrt{2}}$. Yeh step kyun? $\Vert Ax-b\Vert$ ka minimizer $Rx=Q^{\top }b$ satisfy karta hai (parent note) — $Q^{\top }b$ hai $b$ expressed in the clean frame.
3. Back-substitute $\left[\begin{array}{cc}\sqrt{3}& \sqrt{3}\\ 0& \sqrt{2}\end{array}\right]x=\left[\begin{array}{c}5/\sqrt{3}\\ 1/\sqrt{2}\end{array}\right]$. Row 2: $\sqrt{2}{x}_2=\frac{1}{\sqrt{2}}\Rightarrow x_2=\frac{1}{2}$. Row 1: $\sqrt{3}{x}_1+\sqrt{3}{x}_2=\frac{5}{\sqrt{3}}\Rightarrow x_1+x_2=\frac{5}{3}\Rightarrow x_1=\frac{5}{3}-\frac{1}{2}=\frac{7}{6}$. Yeh step kyun? Triangular systems bottom-up solve hote hain bina matrix inversion ke — exact aur numerically stable, yahi QR use karne ka poora point hai.

Verify (units + sanity): intercept $\frac{7}{6}\approx 1.17$ sales at $t=0$ (observed $1$ ke kareeb), slope $\frac{1}{2}$ sale per hour. Predictions $(1.17,1.67,2.17)$ vs data $(1,2,2)$ — residuals $(0.17,-0.33,0.17)$ ka sum $\approx 0$ hai, jaisa least squares demand karta hai (fit data ke centroid $(\bar{t},\bar{s})=(1,\frac{5}{3})$ se guzarta hai: $\frac{7}{6}+\frac{1}{2}\cdot 1=\frac{5}{3}$ ✓). Slope $\frac{1}{2}$, forecast option se match.

Example 9 — Case 9: exam twist, $R$ se $|\det A|$ padho

1. $A$ ka QR. ${\mathbf{a}}_1=(0,1)$, $\Vert {\mathbf{a}}_1\Vert =1=r_{11}$, ${\mathbf{q}}_1=(0,1)$. Yeh step kyun? Column 1 normalize karo pehli diagonal entry $r_{11}$ ke liye — hume sirf yahi $R$ values chahiye, yeh diagonal norms.
2. Shadow + second axis. $r_{12}={\mathbf{q}}_1^{\top }{\mathbf{a}}_2=(0,1)\cdot (1,1)=1$; ${\mathbf{u}}_2=(1,1)-1\cdot (0,1)=(1,0)$; $r_{22}=\Vert {\mathbf{u}}_2\Vert =1$. Yeh step kyun? ${\mathbf{a}}_2$ ka shadow strip karo perpendicular leftover paane ke liye, jiski length doosri diagonal entry $r_{22}$ hai.
3. Diagonal multiply karo. $\det R=r_{11}{r}_{22}=1\cdot 1=1$. Yeh step kyun? Triangular matrix ke liye determinant diagonal ka product hota hai — off-diagonal entries kabhi contribute nahi karti.
4. Orthogonality use karo. $|\det A|=|\det Q||\det R|=1\cdot 1=1$. Yeh step kyun? Ek orthogonal $Q$ volume preserve karta hai, toh $|\det Q|=1$; $A$ ki saari "stretch" $R$ ke diagonal mein rehti hai.

Verify: direct expansion $\det \left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]=0\cdot 1-1\cdot 1=-1$, toh $|\det A|=1$ ✓. Ek general rule jo exam mein quote kar sakte ho: $|\det A|={\prod }_k{r}_{kk}$. (Yahi trick Eigenvalues and the QR algorithm mein kaam aati hai aur mirror karti hai LU decomposition ka us triangular factor se $\det$ padhna.)

Active recall

Connections

• QR decomposition — woh parent note jise yeh page drill karta hai.
• Gram-Schmidt process — har example iska ek run hai.
• Orthonormal bases and projections — shadow ${\mathbf{q}}^{\top }\mathbf{a}$ ek projection hai.
• Least squares and normal equations — Example 8 ka engine.
• Householder reflections — Case 6 ke liye stable fix.
• Eigenvalues and the QR algorithm — $|\det |=\prod r_{kk}$ idea use karta hai.
• LU decomposition — sibling factorization jo ek triangle se bhi $\det$ padhti hai.