QR Decomposition: Worked Examples

We apply QR decomposition to two least squares problems. The first is the polynomial fitting problem solved in the Normal Equations section, so both methods must produce identical answers, which serves as a useful consistency check. The second is a larger overdetermined system fitted with a quadratic, which exercises the full three step Gram-Schmidt process.

---

Example 1

Problem Setup

Problem: Given the data $f(-3) = 0$, $f(0) = 0$, $f(6) = 2$, find the least squares polynomial $P_1(x) = a_0 + a_1 x$ using QR decomposition.

The coefficient matrix and right-hand side are:

$$A = \begin{bmatrix} 1 & -3 \\ 1 & 0 \\ 1 & 6 \end{bmatrix}, \qquad b = \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix}$$

$A$ has two columns, so the Gram-Schmidt process will run for $k = 1$ and $k = 2$.

Label the columns: $u_1 = \begin{bmatrix}1\\1\\1\end{bmatrix}$ and $u_2 = \begin{bmatrix}-3\\0\\6\end{bmatrix}$.

---

Step 1 — Gram-Schmidt: $k = 1$

For $k = 1$, the sum is empty, so:

$$p_1 = u_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$$ $$|p_1| = \sqrt{1^2 + 1^2 + 1^2} = \sqrt{3}$$ $$q_1 = \frac{p_1}{|p_1|} = \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}$$

---

Step 2 — Gram-Schmidt: $k = 2$

$$p_2 = u_2 - (u_2^T q_1)\,q_1$$

First, compute the projection coefficient $u_2^T q_1$:

$$u_2^T q_1 = \begin{bmatrix} -3 & 0 & 6 \end{bmatrix} \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{\sqrt{3}}(-3 + 0 + 6) = \frac{3}{\sqrt{3}} = \sqrt{3}$$

Now subtract the projection:

$$p_2 = \begin{bmatrix} -3 \\ 0 \\ 6 \end{bmatrix} - \sqrt{3} \cdot \frac{1}{\sqrt{3}}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -3 \\ 0 \\ 6 \end{bmatrix} - \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} -4 \\ -1 \\ 5 \end{bmatrix}$$

Normalize:

$$|p_2| = \sqrt{(-4)^2 + (-1)^2 + 5^2} = \sqrt{16 + 1 + 25} = \sqrt{42}$$ $$q_2 = \frac{p_2}{|p_2|} = \frac{1}{\sqrt{42}}\begin{bmatrix} -4 \\ -1 \\ 5 \end{bmatrix}$$

---

Step 3 — Assemble $Q$ and $Q^T$

$$Q = \begin{bmatrix} q_1 & q_2 \end{bmatrix} = \begin{bmatrix} \dfrac{1}{\sqrt{3}} & \dfrac{-4}{\sqrt{42}} \\[8pt] \dfrac{1}{\sqrt{3}} & \dfrac{-1}{\sqrt{42}} \\[8pt] \dfrac{1}{\sqrt{3}} & \dfrac{5}{\sqrt{42}} \end{bmatrix}$$ $$Q^T = \begin{bmatrix} \dfrac{1}{\sqrt{3}} & \dfrac{1}{\sqrt{3}} & \dfrac{1}{\sqrt{3}} \\[8pt] \dfrac{-4}{\sqrt{42}} & \dfrac{-1}{\sqrt{42}} & \dfrac{5}{\sqrt{42}} \end{bmatrix}$$

---

Step 4 — Compute $R$

Using $R_{ij} = u_j^T q_i$ for $i \leq j$:

$$u_1^T q_1 = \begin{bmatrix}1 & 1 & 1\end{bmatrix} \frac{1}{\sqrt{3}}\begin{bmatrix}1\\1\\1\end{bmatrix} = \frac{3}{\sqrt{3}} = \sqrt{3}$$ $$u_2^T q_1 = \sqrt{3} \quad \text{(computed in Step 2)}$$ $$u_2^T q_2 = \begin{bmatrix}-3 & 0 & 6\end{bmatrix} \frac{1}{\sqrt{42}}\begin{bmatrix}-4\\-1\\5\end{bmatrix} = \frac{1}{\sqrt{42}}(12 + 0 + 30) = \frac{42}{\sqrt{42}} = \sqrt{42}$$

Therefore:

$$R = \begin{bmatrix} \sqrt{3} & \sqrt{3} \\ 0 & \sqrt{42} \end{bmatrix}$$

---

Step 5 — Compute the right-hand side $Q^T b$

$$Q^T b = \begin{bmatrix} \dfrac{1}{\sqrt{3}} & \dfrac{1}{\sqrt{3}} & \dfrac{1}{\sqrt{3}} \\[8pt] \dfrac{-4}{\sqrt{42}} & \dfrac{-1}{\sqrt{42}} & \dfrac{5}{\sqrt{42}} \end{bmatrix} \begin{bmatrix} 0 \\ 0 \\ 2 \end{bmatrix} = \begin{bmatrix} \dfrac{2}{\sqrt{3}} \\[8pt] \dfrac{10}{\sqrt{42}} \end{bmatrix}$$

---

Step 6 — Solve $Rx = Q^T b$ by back substitution

The system to solve:

$$\begin{bmatrix} \sqrt{3} & \sqrt{3} \\ 0 & \sqrt{42} \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \end{bmatrix} = \begin{bmatrix} \dfrac{2}{\sqrt{3}} \\[8pt] \dfrac{10}{\sqrt{42}} \end{bmatrix}$$

From row 2:

$$\sqrt{42}\,a_1 = \frac{10}{\sqrt{42}} \implies a_1 = \frac{10}{\sqrt{42} \cdot \sqrt{42}} = \frac{10}{42} = \frac{5}{21}$$

From row 1:

$$\sqrt{3}\,a_0 + \sqrt{3}\,a_1 = \frac{2}{\sqrt{3}} \implies \sqrt{3}\,a_0 = \frac{2}{\sqrt{3}} - \sqrt{3} \cdot \frac{5}{21} = \frac{2}{\sqrt{3}} - \frac{5\sqrt{3}}{21}$$ $$\sqrt{3}\,a_0 = \frac{2}{\sqrt{3}} - \frac{5}{7\sqrt{3}} = \frac{14}{7\sqrt{3}} - \frac{5}{7\sqrt{3}} = \frac{9}{7\sqrt{3}}$$ $$a_0 = \frac{9}{7\sqrt{3} \cdot \sqrt{3}} = \frac{9}{21} = \frac{3}{7}$$

---

Result

$$\boxed{a_0 = \frac{3}{7}, \qquad a_1 = \frac{5}{21}}$$

The least squares polynomial is:

$$P_1(x) = \frac{3}{7} + \frac{5}{21}\,x$$

Note

This matches the result from the normal equations in the previous section. Both approaches are mathematically equivalent — they minimize the same sum of squared residuals. QR decomposition avoids squaring the condition number of $A$ (which happens when forming $A^T A$), making it preferable for ill-conditioned problems.

---

Example 2

Problem Setup

Problem: Solve the following system in the least squares sense using QR decomposition.

$$\begin{aligned} a_0 + a_1 + a_2 &= 2 \\ a_0 + 2a_1 + 4a_2 &= 3 \\ a_0 + 3a_1 + 9a_2 &= 6 \\ a_0 + 4a_1 + 16a_2 &= 4 \end{aligned}$$

In matrix form $Ax = b$:

$$\begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \\ 1 & 4 & 16 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} 2 \\ 3 \\ 6 \\ 4 \end{bmatrix}$$

$A$ is a $4 \times 3$ matrix, so this is an overdetermined system with four equations and three unknowns. It is the quadratic fit $P_2(x) = a_0 + a_1 x + a_2 x^2$ through the data $f(1) = 2$, $f(2) = 3$, $f(3) = 6$, $f(4) = 4$.

$A$ has three columns, so the Gram-Schmidt process will run for $k = 1$, $k = 2$ and $k = 3$. There will be three steps.

Label the columns:

$$u_1 = \begin{bmatrix}1\\1\\1\\1\end{bmatrix}, \qquad u_2 = \begin{bmatrix}1\\2\\3\\4\end{bmatrix}, \qquad u_3 = \begin{bmatrix}1\\4\\9\\16\end{bmatrix}$$

---

Step 1 — Gram-Schmidt: $k = 1$

For $k = 1$, the sum is empty, so:

$$p_1 = u_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix}$$ $$|p_1| = \sqrt{1^2 + 1^2 + 1^2 + 1^2} = \sqrt{4} = 2$$ $$q_1 = \frac{p_1}{|p_1|} = \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{bmatrix}$$

---

Step 2 — Gram-Schmidt: $k = 2$

$$p_2 = u_2 - (u_2^T q_1)\,q_1$$

First, compute the projection coefficient $u_2^T q_1$:

$$u_2^T q_1 = \begin{bmatrix} 1 & 2 & 3 & 4 \end{bmatrix} \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{2}(1 + 2 + 3 + 4) = \frac{10}{2} = 5$$

Now subtract the projection:

$$p_2 = \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} - 5 \cdot \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \begin{bmatrix} 1 \\ 2 \\ 3 \\ 4 \end{bmatrix} - \begin{bmatrix} 2.5 \\ 2.5 \\ 2.5 \\ 2.5 \end{bmatrix} = \begin{bmatrix} -1.5 \\ -0.5 \\ 0.5 \\ 1.5 \end{bmatrix}$$

Normalize:

$$|p_2| = \sqrt{(-1.5)^2 + (-0.5)^2 + (0.5)^2 + (1.5)^2} = \sqrt{2.25 + 0.25 + 0.25 + 2.25} = \sqrt{5}$$ $$q_2 = \frac{p_2}{|p_2|} = \frac{1}{\sqrt{5}}\begin{bmatrix} -1.5 \\ -0.5 \\ 0.5 \\ 1.5 \end{bmatrix}$$

---

Step 3 — Gram-Schmidt: $k = 3$

With two orthonormal vectors already in hand, the sum now has two terms:

$$p_3 = u_3 - \left[(u_3^T q_1)\,q_1 + (u_3^T q_2)\,q_2\right]$$

Compute both projection coefficients:

$$u_3^T q_1 = \begin{bmatrix} 1 & 4 & 9 & 16 \end{bmatrix} \frac{1}{2}\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} = \frac{1}{2}(1 + 4 + 9 + 16) = \frac{30}{2} = 15$$ $$u_3^T q_2 = \begin{bmatrix} 1 & 4 & 9 & 16 \end{bmatrix} \frac{1}{\sqrt{5}}\begin{bmatrix} -1.5 \\ -0.5 \\ 0.5 \\ 1.5 \end{bmatrix} = \frac{1}{\sqrt{5}}(-1.5 - 2 + 4.5 + 24) = \frac{25}{\sqrt{5}} = 5\sqrt{5}$$

Now subtract both projections:

$$p_3 = \begin{bmatrix} 1 \\ 4 \\ 9 \\ 16 \end{bmatrix} - \left[\, 15 \begin{bmatrix} 0.5 \\ 0.5 \\ 0.5 \\ 0.5 \end{bmatrix} + 5\sqrt{5} \cdot \frac{1}{\sqrt{5}}\begin{bmatrix} -1.5 \\ -0.5 \\ 0.5 \\ 1.5 \end{bmatrix} \right]$$ $$p_3 = \begin{bmatrix} 1 \\ 4 \\ 9 \\ 16 \end{bmatrix} - \begin{bmatrix} 7.5 \\ 7.5 \\ 7.5 \\ 7.5 \end{bmatrix} - \begin{bmatrix} -7.5 \\ -2.5 \\ 2.5 \\ 7.5 \end{bmatrix} = \begin{bmatrix} 1 \\ -1 \\ -1 \\ 1 \end{bmatrix}$$

Normalize:

$$|p_3| = \sqrt{1^2 + (-1)^2 + (-1)^2 + 1^2} = \sqrt{4} = 2$$ $$q_3 = \frac{p_3}{|p_3|} = \frac{1}{2}\begin{bmatrix} 1 \\ -1 \\ -1 \\ 1 \end{bmatrix}$$

---

Step 4 — Assemble $Q$ and $Q^T$

$$Q = \begin{bmatrix} q_1 & q_2 & q_3 \end{bmatrix} = \begin{bmatrix} 0.5 & \dfrac{-1.5}{\sqrt{5}} & 0.5 \\[8pt] 0.5 & \dfrac{-0.5}{\sqrt{5}} & -0.5 \\[8pt] 0.5 & \dfrac{0.5}{\sqrt{5}} & -0.5 \\[8pt] 0.5 & \dfrac{1.5}{\sqrt{5}} & 0.5 \end{bmatrix}$$ $$Q^T = \begin{bmatrix} 0.5 & 0.5 & 0.5 & 0.5 \\[8pt] \dfrac{-1.5}{\sqrt{5}} & \dfrac{-0.5}{\sqrt{5}} & \dfrac{0.5}{\sqrt{5}} & \dfrac{1.5}{\sqrt{5}} \\[8pt] 0.5 & -0.5 & -0.5 & 0.5 \end{bmatrix}$$

---

Step 5 — Compute $R$

Using $R_{ij} = u_j^T q_i$ for $i \leq j$, the matrix has the structure:

$$R = \begin{bmatrix} u_1^T q_1 & u_2^T q_1 & u_3^T q_1 \\[6pt] 0 & u_2^T q_2 & u_3^T q_2 \\[6pt] 0 & 0 & u_3^T q_3 \end{bmatrix}$$

Three of these entries are already available from the Gram-Schmidt steps:

$$u_2^T q_1 = 5, \qquad u_3^T q_1 = 15, \qquad u_3^T q_2 = 5\sqrt{5}$$

The remaining entries are the diagonal terms, and each one equals the norm $|p_k|$ found in the corresponding step:

$$u_1^T q_1 = \begin{bmatrix}1 & 1 & 1 & 1\end{bmatrix} \frac{1}{2}\begin{bmatrix}1\\1\\1\\1\end{bmatrix} = \frac{4}{2} = 2$$ $$u_2^T q_2 = \begin{bmatrix}1 & 2 & 3 & 4\end{bmatrix} \frac{1}{\sqrt{5}}\begin{bmatrix}-1.5\\-0.5\\0.5\\1.5\end{bmatrix} = \frac{1}{\sqrt{5}}(-1.5 - 1 + 1.5 + 6) = \frac{5}{\sqrt{5}} = \sqrt{5}$$ $$u_3^T q_3 = \begin{bmatrix}1 & 4 & 9 & 16\end{bmatrix} \frac{1}{2}\begin{bmatrix}1\\-1\\-1\\1\end{bmatrix} = \frac{1}{2}(1 - 4 - 9 + 16) = \frac{4}{2} = 2$$

Therefore:

$$R = \begin{bmatrix} 2 & 5 & 15 \\ 0 & \sqrt{5} & 5\sqrt{5} \\ 0 & 0 & 2 \end{bmatrix}$$

---

Step 6 — Compute the right-hand side $Q^T b$

$$Q^T b = \begin{bmatrix} 0.5 & 0.5 & 0.5 & 0.5 \\[8pt] \dfrac{-1.5}{\sqrt{5}} & \dfrac{-0.5}{\sqrt{5}} & \dfrac{0.5}{\sqrt{5}} & \dfrac{1.5}{\sqrt{5}} \\[8pt] 0.5 & -0.5 & -0.5 & 0.5 \end{bmatrix} \begin{bmatrix} 2 \\ 3 \\ 6 \\ 4 \end{bmatrix}$$

Row by row:

$$\text{Row 1:} \quad \frac{1}{2}(2 + 3 + 6 + 4) = \frac{15}{2}$$ $$\text{Row 2:} \quad \frac{1}{\sqrt{5}}(-3 - 1.5 + 3 + 6) = \frac{4.5}{\sqrt{5}} = \frac{9\sqrt{5}}{10}$$ $$\text{Row 3:} \quad \frac{1}{2}(2 - 3 - 6 + 4) = -\frac{3}{2}$$ $$Q^T b = \begin{bmatrix} \dfrac{15}{2} \\[8pt] \dfrac{9\sqrt{5}}{10} \\[8pt] -\dfrac{3}{2} \end{bmatrix}$$

---

Step 7 — Solve $Rx = Q^T b$ by back substitution

The system to solve:

$$\begin{bmatrix} 2 & 5 & 15 \\ 0 & \sqrt{5} & 5\sqrt{5} \\ 0 & 0 & 2 \end{bmatrix} \begin{bmatrix} a_0 \\ a_1 \\ a_2 \end{bmatrix} = \begin{bmatrix} \dfrac{15}{2} \\[8pt] \dfrac{9\sqrt{5}}{10} \\[8pt] -\dfrac{3}{2} \end{bmatrix}$$

From row 3:

$$2\,a_2 = -\frac{3}{2} \implies a_2 = -\frac{3}{4} = -0.75$$

From row 2:

$$\sqrt{5}\,a_1 + 5\sqrt{5}\,a_2 = \frac{9\sqrt{5}}{10}$$

Dividing through by $\sqrt{5}$ and substituting $a_2$:

$$a_1 + 5\left(-\frac{3}{4}\right) = \frac{9}{10} \implies a_1 = \frac{9}{10} + \frac{15}{4} = \frac{18}{20} + \frac{75}{20} = \frac{93}{20} = 4.65$$

From row 1:

$$2\,a_0 + 5\,a_1 + 15\,a_2 = \frac{15}{2}$$ $$2\,a_0 + 5\left(\frac{93}{20}\right) + 15\left(-\frac{3}{4}\right) = \frac{15}{2} \implies 2\,a_0 + \frac{93}{4} - \frac{45}{4} = \frac{15}{2}$$ $$2\,a_0 + 12 = \frac{15}{2} \implies 2\,a_0 = -\frac{9}{2} \implies a_0 = -\frac{9}{4} = -2.25$$

---

Result

$$\boxed{a_0 = -\frac{9}{4}, \qquad a_1 = \frac{93}{20}, \qquad a_2 = -\frac{3}{4}}$$

The least squares polynomial is:

$$P_2(x) = -\frac{9}{4} + \frac{93}{20}\,x - \frac{3}{4}\,x^2$$

---

Verification

Two independent checks confirm the solution. First, the normal equations $A^T A\,x = A^T b$:

$$A^T A = \begin{bmatrix} 4 & 10 & 30 \\ 10 & 30 & 100 \\ 30 & 100 & 354 \end{bmatrix}, \qquad A^T b = \begin{bmatrix} 15 \\ 42 \\ 132 \end{bmatrix}$$

All three equations are satisfied exactly by the coefficients above.

Second, the residuals $r = b - Ax$ at the four data points:

$$\begin{aligned} P_2(1) &= 1.65, &\quad r_1 &= 0.35 \\ P_2(2) &= 4.05, &\quad r_2 &= -1.05 \\ P_2(3) &= 4.95, &\quad r_3 &= 1.05 \\ P_2(4) &= 4.35, &\quad r_4 &= -0.35 \end{aligned}$$

The residual vector is orthogonal to every column of $A$, since $\sum r_i = 0$, $\sum x_i r_i = 0$ and $\sum x_i^2 r_i = 0$. This orthogonality is the defining property of the least squares solution, so it is a reliable check on the arithmetic.

Note

The structure is identical in both examples. Only the column count changes. An $m \times n$ matrix $A$ gives $n$ Gram-Schmidt steps, an $m \times n$ matrix $Q$ with orthonormal columns and an $n \times n$ upper triangular matrix $R$ solved by back substitution from the bottom row upward. The number of steps is set by the columns of $A$, never by the rows.