MAT 102 Linear Algebra · DSE · Intake 2/1 · Dr. Ronobir Chandra Sarker

Orthogonality — Part 3: Least squares and orthonormal bases

Lecture notes on sections 4.3 and 4.4 of Strang, Introduction to Linear Algebra. Read with pen and paper beside you, work each example yourself before reading its solution, and do every exercise before opening the answer.

The chapter in three parts: Part 1 · Orthogonal vectors and subspaces  |  Part 2 · Projections  |  Part 3 · Least squares and orthonormal bases

⬇ Download Part 3 as PDF 🎯 Practice page
Contents
  1. Before you start
  2. Least squares
  3. Orthonormal bases and Gram–Schmidt
  4. Question types and model answers
  5. Practice test
  6. Formula sheet

0Before you start

Why we study this

What you need

Notation

SymbolMeaning
\((t_i, b_i)\), \(m\)the data points (time, measurement) and how many there are
\(C\), \(D\)the intercept and slope of the line \(b = C + Dt\)
\(\sum t_i\)\(t_1 + t_2 + \cdots + t_m\)
\(p_i\), \(e_i\), \(E\)height of the line at \(t_i\); error \(b_i - p_i\); total squared error \(\sum e_i^2\)
\(\vb q_1, \vb q_2, \dots\); \(Q\)orthonormal vectors; the matrix with them as columns
\(\vb A, \vb B, \vb C\); \(R\)the orthogonal (not yet unit) vectors in Gram–Schmidt; the triangular factor in \(A = QR\)

1Least squares (4.3)

Suppose we measure a quantity \(b\) at several times \(t\) and we believe that \(b\) grows along a straight line \(b = C + Dt\). Because of measurement noise no line passes through all the points. Which line is best? This is the least-squares problem, and we will see that it is a projection in disguise.

Historical note. In 1801 the newly discovered asteroid Ceres was lost behind the Sun after only forty days of observations. The 24-year-old Gauss used least squares on those noisy observations to predict where it would reappear, and it reappeared exactly there. Today the same method is called linear regression; it is the first method taught in statistics and machine learning, and a GPS receiver solves a least-squares problem every second.

Why there is no exact solution

With \(m\) data points \((t_i, b_i)\) the line \(b = C + Dt\) must satisfy \(m\) equations in only two unknowns: \[ C + Dt_1 = b_1,\quad C + Dt_2 = b_2,\quad \dots,\quad C + Dt_m = b_m, \] that is \(A\vb x = \vb b\) with \[ A = \begin{bmatrix} 1 & t_1 \\ 1 & t_2 \\ \vdots & \vdots \\ 1 & t_m \end{bmatrix}, \qquad \vb x = \begin{bmatrix} C \\ D \end{bmatrix}. \] The first column is all ones because it multiplies \(C\); the second column holds the times because they multiply \(D\). The matrix is tall and thin, its two columns span only a plane inside \(\R^m\), and a noisy \(\vb b\) lies outside that plane. So \(A\vb x = \vb b\) has no solution. We cannot make the error \(\vb e = \vb b - A\vb x\) zero, but we can make it as short as possible.

Definition 1.1. The least-squares solution \(\hat{\vb x}\) of \(A\vb x = \vb b\) is the vector that makes the squared length of the error as small as possible: \[ E = \nrm{A\vb x - \vb b}^2 = e_1^2 + e_2^2 + \cdots + e_m^2 \quad\text{is minimised at } \vb x = \hat{\vb x}. \] For a line fit, \(e_i = b_i - (C + Dt_i)\) is the vertical distance from the \(i\)-th point to the line, and \(E\) is the sum of their squares.
Theorem 1.2. The least-squares solution satisfies the normal equations \[ A\T A\,\hat{\vb x} = A\T\vb b. \]
Proof. As \(\vb x\) varies, \(A\vb x\) runs through every point of the column space \(\mathbf C(A)\). Minimising \(\nrm{A\vb x - \vb b}\) therefore means finding the point of \(\mathbf C(A)\) closest to \(\vb b\). By Part 2 (projection onto a subspace) that point is the projection \(\vb p = A\hat{\vb x}\), and the error \(\vb e = \vb b - A\hat{\vb x}\) is perpendicular to every column of \(A\): \(A\T(\vb b - A\hat{\vb x}) = \vb 0\), which is \(A\T A\hat{\vb x} = A\T\vb b\). ∎

Remark. Calculus gives the same equations: setting the partial derivatives \(\partial E/\partial C\) and \(\partial E/\partial D\) equal to zero produces exactly the two normal equations. The book shows both arguments.

Fitting a straight line

The normal equations for \(b = C + Dt\). \[ A\T A = \begin{bmatrix} m & \sum t_i \\ \sum t_i & \sum t_i^2 \end{bmatrix}, \qquad A\T\vb b = \begin{bmatrix} \sum b_i \\ \sum t_i b_i \end{bmatrix}, \qquad \begin{bmatrix} m & \sum t_i \\ \sum t_i & \sum t_i^2 \end{bmatrix}\begin{bmatrix} C \\ D \end{bmatrix} = \begin{bmatrix} \sum b_i \\ \sum t_i b_i \end{bmatrix}. \] Only five numbers are needed: \(m\), \(\sum t_i\), \(\sum t_i^2\), \(\sum b_i\), \(\sum t_i b_i\).
Method 1.1.
  1. Write the \(m\) equations \(C + Dt_i = b_i\), and so \(A\) and \(\vb b\).
  2. Compute the five sums and write \(A\T A\) and \(A\T\vb b\).
  3. Solve the normal equations by elimination: this gives \(C\) and \(D\), hence the best line.
  4. Compute the heights on the line \(p_i = C + Dt_i\), the errors \(e_i = b_i - p_i\), and the minimum \(E = \sum e_i^2\).
  5. Check: \(\sum e_i = 0\) and \(\sum t_i e_i = 0\) (the error is perpendicular to both columns of \(A\)).

Example 1.1 (book). Find the closest line to the points \((0, 6)\), \((1, 0)\), \((2, 0)\).

  1. The equations \(C + 0D = 6\), \(C + 1D = 0\), \(C + 2D = 0\) give \[ A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix}, \qquad \vb b = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix}. \] No line passes through all three points, so we look for the least-squares solution.
  2. \(m = 3\), \(\sum t = 0 + 1 + 2 = 3\), \(\sum t^2 = 0 + 1 + 4 = 5\), \(\sum b = 6 + 0 + 0 = 6\), \(\sum tb = 0 + 0 + 0 = 0\): \[ A\T A = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad A\T\vb b = \begin{bmatrix} 6 \\ 0 \end{bmatrix}. \]
  3. Elimination and back substitution: \[ \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 3 & 5 & 0 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 0 & 2 & -6 \end{array}\right] \qquad \begin{aligned} 2D &= -6 &&\Rightarrow\ D = -3 \\ 3C + 3(-3) &= 6 &&\Rightarrow\ C = 5 \end{aligned} \] The best line is \(b = 5 - 3t\).
  4. Heights \(p_i = 5 - 3t_i\): \(\vb p = (5, 2, -1)\). Errors \(e_i = b_i - p_i\): \(\vb e = (6 - 5,\ 0 - 2,\ 0 + 1) = (1, -2, 1)\). Minimum \(E = 1 + 4 + 1 = 6\).
  5. Checks: \(\sum e_i = 1 - 2 + 1 = 0\) and \(\sum t_i e_i = 0 - 2 + 2 = 0\). \(\checkmark\)

Figure 1.1 — the least-squares line of Example 1.1. Black dots: the data \(b_i\). Teal dots: the heights \(p_i = 5 - 3t_i\) on the best line. Red: the vertical errors \(e_i = b_i - p_i\). No line passes through all three data points; this line makes \(E = e_1^2 + e_2^2 + e_3^2 = 6\) as small as possible.

Example 1.2 (book, Problem Set 4.3). Fit \(b = C + Dt\) to \(b = 0, 8, 8, 20\) at \(t = 0, 1, 3, 4\).

  1. \(A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 3 \\ 1 & 4 \end{bmatrix}\), \(\vb b = (0, 8, 8, 20)\).
  2. \(m = 4\), \(\sum t = 8\), \(\sum t^2 = 0 + 1 + 9 + 16 = 26\), \(\sum b = 36\), \(\sum tb = 0 + 8 + 24 + 80 = 112\): \[ A\T A = \begin{bmatrix} 4 & 8 \\ 8 & 26 \end{bmatrix}, \qquad A\T\vb b = \begin{bmatrix} 36 \\ 112 \end{bmatrix}. \]
  3. The multiplier is \(8 \div 4 = 2\): \[ \left[\begin{array}{cc|c} 4 & 8 & 36 \\ 8 & 26 & 112 \end{array}\right] \xrightarrow{\ R_2 - 2R_1\ } \left[\begin{array}{cc|c} 4 & 8 & 36 \\ 0 & 10 & 40 \end{array}\right] \qquad \begin{aligned} 10D &= 40 &&\Rightarrow\ D = 4 \\ 4C + 8(4) &= 36 &&\Rightarrow\ C = 1 \end{aligned} \] The best line is \(b = 1 + 4t\).
  4. Heights \(\vb p = (1, 5, 13, 17)\). Errors \(\vb e = (0 - 1,\ 8 - 5,\ 8 - 13,\ 20 - 17) = (-1, 3, -5, 3)\). \(E = 1 + 9 + 25 + 9 = 44\).
  5. Checks: \(\sum e_i = -1 + 3 - 5 + 3 = 0\) and \(\sum t_i e_i = 0 + 3 - 15 + 12 = 0\). \(\checkmark\)

Example 1.3 (a horizontal line). Fit \(b = C\) (no slope) to measurements \(b_1, \dots, b_m\).

Now \(A\) is a single column of ones, so \(A\T A = m\) and \(A\T\vb b = \sum b_i\). The normal equation \(mC = \sum b_i\) gives \[ C = \frac{b_1 + b_2 + \cdots + b_m}{m}, \] the average of the measurements. The mean is a least-squares fit, and therefore also a projection.

Exercise 1. Find the least-squares line through \((1, 2)\), \((2, 0)\), \((3, 4)\). Give \(C\) and \(D\), the heights, the errors, \(E\), and the checks.

Show answer
Answer
  1. \(A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 3 \end{bmatrix}\), \(\vb b = (2, 0, 4)\).
  2. \(m = 3\), \(\sum t = 6\), \(\sum t^2 = 1 + 4 + 9 = 14\), \(\sum b = 6\), \(\sum tb = 2 + 0 + 12 = 14\): \(A\T A = \begin{bmatrix} 3 & 6 \\ 6 & 14 \end{bmatrix}\), \(A\T\vb b = \begin{bmatrix} 6 \\ 14 \end{bmatrix}\).
  3. Multiplier \(6 \div 3 = 2\): \(\left[\begin{array}{cc|c} 3 & 6 & 6 \\ 6 & 14 & 14 \end{array}\right] \xrightarrow{\ R_2 - 2R_1\ } \left[\begin{array}{cc|c} 3 & 6 & 6 \\ 0 & 2 & 2 \end{array}\right]\), so \(D = 1\) and \(3C + 6(1) = 6\), \(C = 0\). Best line \(b = t\).
  4. Heights \(p_i = t_i\): \((1, 2, 3)\). Errors \((2 - 1,\ 0 - 2,\ 4 - 3) = (1, -2, 1)\). \(E = 1 + 4 + 1 = 6\).
  5. Checks: \(\sum e_i = 0\) and \(\sum t_i e_i = 1 - 4 + 3 = 0\). \(\checkmark\)

2Orthonormal bases and Gram–Schmidt (4.4)

The coordinate axes \((1,0,0)\), \((0,1,0)\), \((0,0,1)\) are perpendicular to each other and have length \(1\). That is why coordinates are so easy to read off: the component of \(\vb b\) along an axis is a single dot product. This section shows that every subspace has a basis of this kind, how to construct it, and why it makes least squares easy.

Definition 2.1. Vectors \(\vb q_1, \dots, \vb q_n\) are orthonormal when they are perpendicular to each other and each has length \(1\): \[ \vb q_i\T\vb q_j = \begin{cases} 0 & i \ne j \quad\text{(orthogonal)} \\ 1 & i = j \quad\text{(unit length)} \end{cases} \] If \(Q\) is the matrix with the \(\vb q\)'s as columns, these \(n^2\) conditions are the single matrix equation \[ Q\T Q = I, \] because the \((i, j)\) entry of \(Q\T Q\) is exactly \(\vb q_i\T\vb q_j\).
Definition 2.2. A square matrix with orthonormal columns is called an orthogonal matrix. For such a matrix \(Q\T Q = I\) says that \(Q\T\) is the inverse: \[ Q^{-1} = Q\T. \]

Example 2.1. Three orthogonal matrices.

Example 2.2 (book, 4.4 #1). Classify each pair as independent only, orthogonal, or orthonormal: \((1,0)\) and \((-1,1)\); \((.6,.8)\) and \((.4,-.3)\); \((\cos\theta, \sin\theta)\) and \((-\sin\theta, \cos\theta)\).

Theorem 2.1. Multiplying by a matrix with orthonormal columns does not change lengths: \(\nrm{Q\vb x} = \nrm{\vb x}\) for every \(\vb x\).
Proof. \(\nrm{Q\vb x}^2 = (Q\vb x)\T(Q\vb x) = \vb x\T Q\T Q\vb x = \vb x\T I\vb x = \nrm{\vb x}^2\). ∎

Rotations and reflections are orthogonal matrices; this theorem is why computer graphics is full of them.

Caution. \(Q\T Q = I\) holds for every matrix with orthonormal columns, but \(QQ\T = I\) only when \(Q\) is square. For example \(Q = \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{bmatrix}\) has \(Q\T Q = I_2\) but \(QQ\T \ne I_3\).

Least squares with orthonormal columns

If the columns of \(A = Q\) are orthonormal, the normal equations \(Q\T Q\hat{\vb x} = Q\T\vb b\) collapse because \(Q\T Q = I\):

Projection with orthonormal columns. \[ \begin{aligned} \hat{\vb x} &= Q\T\vb b && (\hat x_i = \vb q_i\T\vb b) \\ \vb p &= QQ\T\vb b = (\vb q_1\T\vb b)\,\vb q_1 + (\vb q_2\T\vb b)\,\vb q_2 + \cdots \end{aligned} \]

There is nothing to solve: every coefficient is a single dot product.

Example 2.3. Project \(\vb b = (3, 0, 3)\) onto the plane spanned by \(\vb q_1 = \tfrac13(1,2,2)\) and \(\vb q_2 = \tfrac13(2,1,-2)\).

\[ \begin{aligned} \hat x_1 &= \vb q_1\T\vb b = \tfrac13(3 + 0 + 6) = 3, \qquad \hat x_2 = \vb q_2\T\vb b = \tfrac13(6 + 0 - 6) = 0 \\ \vb p &= 3\vb q_1 + 0\vb q_2 = (1, 2, 2), \qquad \vb e = \vb b - \vb p = (2, -2, 1) \\ \text{checks: } \vb q_1\T\vb e &= \tfrac13(2 - 4 + 2) = 0, \qquad \vb q_2\T\vb e = \tfrac13(4 - 2 - 2) = 0 \quad\checkmark \end{aligned} \]

Gram–Schmidt: making a basis orthonormal

Start with independent vectors \(\vb a, \vb b, \vb c\). We want orthonormal vectors \(\vb q_1, \vb q_2, \vb q_3\) that span the same space. The idea is one projection at a time: keep \(\vb a\); from \(\vb b\) subtract its projection onto \(\vb a\), because what is left over is an error vector and error vectors are perpendicular; from \(\vb c\) subtract its projections onto the first two; finally divide each vector by its length.

Figure 2.1 — one Gram–Schmidt step is one projection. Project \(\vb b\) onto the line through \(\vb A = \vb a\) to get \(\vb p\). What is left, \(\vb B = \vb b - \vb p\), is the error of that projection, so it is automatically orthogonal to \(\vb A\). Dividing \(\vb A\) and \(\vb B\) by their lengths gives \(\vb q_1\) and \(\vb q_2\).

Method 2.1 (Gram–Schmidt).
  1. \(\vb A = \vb a\).
  2. \(\vb B = \vb b - \dfrac{\vb A\T\vb b}{\vb A\T\vb A}\,\vb A\).   Check \(\vb A\T\vb B = 0\).
  3. \(\vb C = \vb c - \dfrac{\vb A\T\vb c}{\vb A\T\vb A}\,\vb A - \dfrac{\vb B\T\vb c}{\vb B\T\vb B}\,\vb B\).   Check \(\vb A\T\vb C = 0\) and \(\vb B\T\vb C = 0\).
  4. \(\vb q_1 = \dfrac{\vb A}{\nrm{\vb A}}\), \(\vb q_2 = \dfrac{\vb B}{\nrm{\vb B}}\), \(\vb q_3 = \dfrac{\vb C}{\nrm{\vb C}}\).

Example 2.4 (book). Apply Gram–Schmidt to \(\vb a = (1, -1, 0)\), \(\vb b = (2, 0, -2)\), \(\vb c = (3, -3, 3)\).

  1. \(\vb A = (1, -1, 0)\), with \(\vb A\T\vb A = 2\).
  2. \(\vb A\T\vb b = 2 + 0 + 0 = 2\), so \[ \vb B = \vb b - \frac{2}{2}\vb A = \begin{bmatrix} 2 \\ 0 \\ -2 \end{bmatrix} - \begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix}. \] Check: \(\vb A\T\vb B = 1 - 1 + 0 = 0\). \(\checkmark\)   Also \(\vb B\T\vb B = 1 + 1 + 4 = 6\).
  3. \(\vb A\T\vb c = 3 + 3 + 0 = 6\) and \(\vb B\T\vb c = 3 - 3 - 6 = -6\), so \[ \vb C = \vb c - \frac{6}{2}\vb A - \frac{-6}{6}\vb B = \begin{bmatrix} 3 \\ -3 \\ 3 \end{bmatrix} - \begin{bmatrix} 3 \\ -3 \\ 0 \end{bmatrix} + \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}. \] Checks: \(\vb A\T\vb C = 1 - 1 + 0 = 0\) and \(\vb B\T\vb C = 1 + 1 - 2 = 0\). \(\checkmark\)
  4. Lengths \(\nrm{\vb A} = \sqrt2\), \(\nrm{\vb B} = \sqrt6\), \(\nrm{\vb C} = \sqrt3\): \[ \vb q_1 = \frac{1}{\sqrt2}\begin{bmatrix} 1 \\ -1 \\ 0 \end{bmatrix}, \qquad \vb q_2 = \frac{1}{\sqrt6}\begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix}, \qquad \vb q_3 = \frac{1}{\sqrt3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}. \]

Example 2.5 (book, 4.4 #17). Apply Gram–Schmidt to \(\vb a = (1, 1, 1)\) and \(\vb b = (1, 3, 5)\).

  1. \(\vb A = (1, 1, 1)\), \(\vb A\T\vb A = 3\).
  2. \(\vb A\T\vb b = 1 + 3 + 5 = 9\), so \(\vb B = \vb b - \dfrac93\vb A = (1, 3, 5) - (3, 3, 3) = (-2, 0, 2)\). Check: \(\vb A\T\vb B = -2 + 0 + 2 = 0\). \(\checkmark\)
  3. \(\nrm{\vb A} = \sqrt3\) and \(\nrm{\vb B} = \sqrt8 = 2\sqrt2\): \[ \vb q_1 = \frac{1}{\sqrt3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \qquad \vb q_2 = \frac{1}{2\sqrt2}\begin{bmatrix} -2 \\ 0 \\ 2 \end{bmatrix} = \frac{1}{\sqrt2}\begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix}. \]

The factorization \(A = QR\)

The original vectors are combinations of the \(\vb q\)'s, and each one uses only the earlier \(\vb q\)'s: \(\vb a\) is a multiple of \(\vb q_1\); \(\vb b\) is a combination of \(\vb q_1, \vb q_2\); \(\vb c\) uses all three. So the matrix connecting them is upper triangular.

\(A = QR\). With \(A = [\,\vb a\ \ \vb b\ \ \vb c\,]\) and \(Q = [\,\vb q_1\ \ \vb q_2\ \ \vb q_3\,]\), \[ A = QR, \qquad R = Q\T A = \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b & \vb q_1\T\vb c \\ 0 & \vb q_2\T\vb b & \vb q_2\T\vb c \\ 0 & 0 & \vb q_3\T\vb c \end{bmatrix}. \] The diagonal of \(R\) holds the lengths \(\nrm{\vb A}, \nrm{\vb B}, \nrm{\vb C}\).

Example 2.6. Write \(A = QR\) for the vectors of Example 2.4.

\[ \begin{bmatrix} 1 & 2 & 3 \\ -1 & 0 & -3 \\ 0 & -2 & 3 \end{bmatrix} = \begin{bmatrix} 1/\sqrt2 & 1/\sqrt6 & 1/\sqrt3 \\ -1/\sqrt2 & 1/\sqrt6 & 1/\sqrt3 \\ 0 & -2/\sqrt6 & 1/\sqrt3 \end{bmatrix}\begin{bmatrix} \sqrt2 & \sqrt2 & \sqrt{18} \\ 0 & \sqrt6 & -\sqrt6 \\ 0 & 0 & \sqrt3 \end{bmatrix} \] The entries of \(R\) are dot products, for example \(\vb q_1\T\vb b = \dfrac{2 + 0 + 0}{\sqrt2} = \sqrt2\), \(\vb q_1\T\vb c = \dfrac{3 + 3 + 0}{\sqrt2} = \dfrac{6}{\sqrt2} = \sqrt{18}\), \(\vb q_2\T\vb c = \dfrac{3 - 3 - 6}{\sqrt6} = -\sqrt6\).

Remark (why computers use \(QR\)). With \(A = QR\) the normal equations become \(R\T R\hat{\vb x} = R\T Q\T\vb b\), that is \(R\hat{\vb x} = Q\T\vb b\): a triangular system solved by back substitution, with much smaller rounding errors than forming \(A\T A\). Every serious least-squares program works this way.

Exercise 2.

  1. Is \(\dfrac{1}{\sqrt2}\begin{bmatrix} 1 & -1 \\ 1 & 1 \end{bmatrix}\) an orthogonal matrix? If so, write its inverse.
  2. Apply Gram–Schmidt to \(\vb a = (1, 1, 0)\), \(\vb b = (2, 0, 2)\), and write \(R\).
Show answer
Answer
  1. The columns are \(\frac{1}{\sqrt2}(1, 1)\) and \(\frac{1}{\sqrt2}(-1, 1)\). Dot product \(\frac12(-1 + 1) = 0\); squared lengths \(\frac12(1 + 1) = 1\) each. Orthonormal columns in a square matrix, so yes, it is an orthogonal matrix and \(Q^{-1} = Q\T = \dfrac{1}{\sqrt2}\begin{bmatrix} 1 & 1 \\ -1 & 1 \end{bmatrix}\).
  2. \(\vb A = (1,1,0)\), \(\vb A\T\vb A = 2\), \(\vb A\T\vb b = 2 + 0 + 0 = 2\), so \(\vb B = \vb b - \frac22\vb A = (2,0,2) - (1,1,0) = (1, -1, 2)\); check \(\vb A\T\vb B = 1 - 1 + 0 = 0\). \(\checkmark\) Lengths \(\nrm{\vb A} = \sqrt2\), \(\nrm{\vb B} = \sqrt{1 + 1 + 4} = \sqrt6\), so \(\vb q_1 = \frac{1}{\sqrt2}(1,1,0)\) and \(\vb q_2 = \frac{1}{\sqrt6}(1,-1,2)\). Then \(R = \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b \\ 0 & \vb q_2\T\vb b \end{bmatrix} = \begin{bmatrix} \sqrt2 & 2/\sqrt2 \\ 0 & 6/\sqrt6 \end{bmatrix} = \begin{bmatrix} \sqrt2 & \sqrt2 \\ 0 & \sqrt6 \end{bmatrix}\).

3Question types and model answers

Almost every question on this part is one of the four types below. Each model answer is written out the way I expect to see it on paper: the formula first, then the numbers, the arithmetic, the check, and a one-line conclusion.

Type 1 — Least-squares line

Question. Find the least-squares line \(b = C + Dt\) through \((0, 6), (1, 0), (2, 0)\). Give the heights, the errors and \(E\).

\[ \begin{aligned} &C + 0D = 6,\quad C + 1D = 0,\quad C + 2D = 0 \qquad A = \begin{bmatrix} 1 & 0 \\ 1 & 1 \\ 1 & 2 \end{bmatrix},\quad \vb b = \begin{bmatrix} 6 \\ 0 \\ 0 \end{bmatrix} \\ &m = 3,\quad \textstyle\sum t = 3,\quad \sum t^2 = 5,\quad \sum b = 6,\quad \sum tb = 0 \\ &A\T A = \begin{bmatrix} 3 & 3 \\ 3 & 5 \end{bmatrix}, \qquad A\T\vb b = \begin{bmatrix} 6 \\ 0 \end{bmatrix} \\ &\left[\begin{array}{cc|c} 3 & 3 & 6 \\ 3 & 5 & 0 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 0 & 2 & -6 \end{array}\right] \\ &2D = -6 \ \Rightarrow\ D = -3, \qquad 3C + 3(-3) = 6 \ \Rightarrow\ C = 5 \\ &\text{best line: } b = 5 - 3t \\ &\vb p = (5, 2, -1), \qquad \vb e = \vb b - \vb p = (1, -2, 1), \qquad E = 1 + 4 + 1 = 6 \\ &\text{checks: } \textstyle\sum e_i = 1 - 2 + 1 = 0, \quad \sum t_i e_i = 0 - 2 + 2 = 0 \ \checkmark \end{aligned} \]

Type 2 — Orthogonal matrix

Question. Is \(Q = \dfrac15\begin{bmatrix} 3 & -4 \\ 4 & 3 \end{bmatrix}\) an orthogonal matrix? If so, write \(Q^{-1}\).

\[ \begin{aligned} &\text{columns } \vb q_1 = \tfrac15(3, 4),\ \vb q_2 = \tfrac15(-4, 3) \\ &\vb q_1\T\vb q_2 = \tfrac{1}{25}(-12 + 12) = 0 \\ &\nrm{\vb q_1}^2 = \tfrac{9 + 16}{25} = 1, \qquad \nrm{\vb q_2}^2 = \tfrac{16 + 9}{25} = 1 \\ &\text{orthonormal columns, and } Q \text{ is square: } Q \text{ is an orthogonal matrix} \\ &Q^{-1} = Q\T = \frac15\begin{bmatrix} 3 & 4 \\ -4 & 3 \end{bmatrix} \end{aligned} \]

Type 3 — Projection with orthonormal vectors

Question. Project \(\vb b = (3, 0, 3)\) onto the plane spanned by the orthonormal vectors \(\vb q_1 = \tfrac13(1,2,2)\) and \(\vb q_2 = \tfrac13(2,1,-2)\).

\[ \begin{aligned} \hat x_1 &= \vb q_1\T\vb b = \tfrac13(3 + 0 + 6) = 3 \\ \hat x_2 &= \vb q_2\T\vb b = \tfrac13(6 + 0 - 6) = 0 \\ \vb p &= \hat x_1\vb q_1 + \hat x_2\vb q_2 = 3\cdot\tfrac13(1,2,2) + 0 = (1, 2, 2) \\ \vb e &= \vb b - \vb p = (2, -2, 1) \\ \text{checks: } \vb q_1\T\vb e &= \tfrac13(2 - 4 + 2) = 0, \qquad \vb q_2\T\vb e = \tfrac13(4 - 2 - 2) = 0 \ \checkmark \end{aligned} \]

Type 4 — Gram–Schmidt and \(A = QR\)

Question. Apply Gram–Schmidt to \(\vb a = (1,1,1)\), \(\vb b = (1,3,5)\) and write \(A = QR\).

\[ \begin{aligned} \vb A &= \vb a = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \qquad \vb A\T\vb b = 1 + 3 + 5 = 9, \qquad \vb A\T\vb A = 3 \\ \vb B &= \vb b - \frac{9}{3}\vb A = \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} - \begin{bmatrix} 3 \\ 3 \\ 3 \end{bmatrix} = \begin{bmatrix} -2 \\ 0 \\ 2 \end{bmatrix}, \qquad \text{check: } \vb A\T\vb B = -2 + 0 + 2 = 0 \ \checkmark \\ \nrm{\vb A} &= \sqrt3, \qquad \nrm{\vb B} = \sqrt8 = 2\sqrt2, \qquad \vb q_1 = \frac{1}{\sqrt3}\begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \qquad \vb q_2 = \frac{1}{\sqrt2}\begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix} \\ R &= \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b \\ 0 & \vb q_2\T\vb b \end{bmatrix} = \begin{bmatrix} \sqrt3 & 9/\sqrt3 \\ 0 & 4/\sqrt2 \end{bmatrix} = \begin{bmatrix} \sqrt3 & 3\sqrt3 \\ 0 & 2\sqrt2 \end{bmatrix}, \qquad A = QR \end{aligned} \]

4Practice test

Six questions, about sixty minutes of work. Write full answers on paper first and open each answer only afterwards. Question 6 is theory.

Q1. Find the least-squares line through \((0, 2)\), \((1, 0)\), \((2, 4)\). Give \(C\), \(D\), the heights, the errors and \(E\).

Show answer
Answer
\(m = 3\), \(\sum t = 0 + 1 + 2 = 3\), \(\sum t^2 = 0 + 1 + 4 = 5\), \(\sum b = 2 + 0 + 4 = 6\), \(\sum tb = 0 + 0 + 8 = 8\).
\(\left[\begin{array}{cc|c} 3 & 3 & 6 \\ 3 & 5 & 8 \end{array}\right] \xrightarrow{\ R_2 - R_1\ } \left[\begin{array}{cc|c} 3 & 3 & 6 \\ 0 & 2 & 2 \end{array}\right]\), so \(D = 1\) and \(3C + 3(1) = 6\), \(C = 1\). Best line \(b = 1 + t\).
Heights \(p_i = 1 + t_i\): \((1, 2, 3)\). Errors \(e_i = b_i - p_i\): \((1, -2, 1)\). \(E = 1 + 4 + 1 = 6\).
Checks: \(\sum e_i = 0\) and \(\sum t_i e_i = 0 - 2 + 2 = 0\). \(\checkmark\)

Q2. Fit \(b = C + Dt\) to \(b = 1, 3, 4, 4\) at \(t = 0, 1, 2, 3\). Give the line, the heights, the errors and \(E\).

Show answer
Answer
\(m = 4\), \(\sum t = 6\), \(\sum t^2 = 0 + 1 + 4 + 9 = 14\), \(\sum b = 12\), \(\sum tb = 0 + 3 + 8 + 12 = 23\).
Multiplier \(6 \div 4 = 1.5\): \(\left[\begin{array}{cc|c} 4 & 6 & 12 \\ 6 & 14 & 23 \end{array}\right] \xrightarrow{\ R_2 - 1.5R_1\ } \left[\begin{array}{cc|c} 4 & 6 & 12 \\ 0 & 5 & 5 \end{array}\right]\), so \(D = 1\) and \(4C + 6(1) = 12\), \(C = 1.5\). Best line \(b = 1.5 + t\).
Heights \((1.5, 2.5, 3.5, 4.5)\). Errors \((1 - 1.5,\ 3 - 2.5,\ 4 - 3.5,\ 4 - 4.5) = (-0.5, 0.5, 0.5, -0.5)\). \(E = 4 \times 0.25 = 1\).
Checks: \(\sum e_i = 0\) and \(\sum t_i e_i = 0 + 0.5 + 1 - 1.5 = 0\). \(\checkmark\)

Q3. Is \(Q = \dfrac15\begin{bmatrix} 3 & -4 \\ 4 & 3 \end{bmatrix}\) an orthogonal matrix? Write \(Q^{-1}\) without elimination.

Show answer
Answer
Columns \(\vb q_1 = \frac15(3, 4)\), \(\vb q_2 = \frac15(-4, 3)\). Dot product \(\frac{1}{25}(-12 + 12) = 0\); squared lengths \(\frac{9 + 16}{25} = 1\) and \(\frac{16 + 9}{25} = 1\). Orthonormal columns in a square matrix, so \(Q\) is an orthogonal matrix and \(Q^{-1} = Q\T = \dfrac15\begin{bmatrix} 3 & 4 \\ -4 & 3 \end{bmatrix}\). (Check: \(Q\T Q = \frac{1}{25}\begin{bmatrix} 25 & 0 \\ 0 & 25 \end{bmatrix} = I\).)

Q4. Project \(\vb b = (1, 1, 1)\) onto the plane spanned by the orthonormal vectors \(\vb q_1 = \tfrac13(1, 2, 2)\) and \(\vb q_2 = \tfrac13(2, -2, 1)\). Give \(\vb p\), \(\vb e\) and the checks.

Show answer
Answer
\(\hat x_1 = \vb q_1\T\vb b = \frac13(1 + 2 + 2) = \frac53\), \(\hat x_2 = \vb q_2\T\vb b = \frac13(2 - 2 + 1) = \frac13\).
\(\vb p = \frac53\vb q_1 + \frac13\vb q_2 = \frac59(1,2,2) + \frac19(2,-2,1) = \left(\frac79, \frac89, \frac{11}{9}\right)\).
\(\vb e = \vb b - \vb p = \left(\frac29, \frac19, -\frac29\right)\).
Checks: \(\vb q_1\T\vb e = \frac{1}{27}(2 + 2 - 4) = 0\) and \(\vb q_2\T\vb e = \frac{1}{27}(4 - 2 - 2) = 0\). \(\checkmark\)

Q5. Apply Gram–Schmidt to \(\vb a = (1, 1, 0)\), \(\vb b = (2, 0, 2)\): find \(\vb q_1\), \(\vb q_2\) and \(R\).

Show answer
Answer
\(\vb A = \vb a = (1,1,0)\), \(\vb A\T\vb A = 2\). \(\vb A\T\vb b = 2 + 0 + 0 = 2\), so \(\vb B = \vb b - \frac22\vb A = (2,0,2) - (1,1,0) = (1, -1, 2)\); check \(\vb A\T\vb B = 1 - 1 + 0 = 0\). \(\checkmark\)
Lengths \(\nrm{\vb A} = \sqrt2\), \(\nrm{\vb B} = \sqrt{1 + 1 + 4} = \sqrt6\), so \(\vb q_1 = \frac{1}{\sqrt2}(1,1,0)\), \(\vb q_2 = \frac{1}{\sqrt6}(1,-1,2)\).
\(R = \begin{bmatrix} \vb q_1\T\vb a & \vb q_1\T\vb b \\ 0 & \vb q_2\T\vb b \end{bmatrix} = \begin{bmatrix} \sqrt2 & 2/\sqrt2 \\ 0 & 6/\sqrt6 \end{bmatrix} = \begin{bmatrix} \sqrt2 & \sqrt2 \\ 0 & \sqrt6 \end{bmatrix}\).

Q6 (theory). (a) Explain why the least-squares solution satisfies \(A\T A\hat{\vb x} = A\T\vb b\). (b) Prove that \(\nrm{Q\vb x} = \nrm{\vb x}\) when \(Q\) has orthonormal columns. (c) Why do the normal equations become \(\hat{\vb x} = Q\T\vb b\) when \(A = Q\)?

Show answer
Answer
(a) As \(\vb x\) varies, \(A\vb x\) runs through the column space, so minimising \(\nrm{A\vb x - \vb b}\) means finding the point of \(\mathbf C(A)\) closest to \(\vb b\). That point is the projection \(\vb p = A\hat{\vb x}\), whose error \(\vb b - A\hat{\vb x}\) is perpendicular to every column: \(A\T(\vb b - A\hat{\vb x}) = \vb 0\), i.e. \(A\T A\hat{\vb x} = A\T\vb b\).
(b) \(\nrm{Q\vb x}^2 = (Q\vb x)\T(Q\vb x) = \vb x\T Q\T Q\vb x = \vb x\T I\vb x = \nrm{\vb x}^2\). \(\blacksquare\)
(c) With \(A = Q\) the normal equations read \(Q\T Q\hat{\vb x} = Q\T\vb b\), and \(Q\T Q = I\) because the columns are orthonormal, so \(\hat{\vb x} = Q\T\vb b\): each coefficient is one dot product \(\vb q_i\T\vb b\).

5Formula sheet

TopicFormulas
Least squares\(\hat{\vb x}\) minimises \(E = \nrm{A\vb x - \vb b}^2 = e_1^2 + \cdots + e_m^2\)
solve the normal equations \(A\T A\hat{\vb x} = A\T\vb b\)
Best line \(b = C + Dt\)\(A = \begin{bmatrix} 1 & t_1 \\ \vdots & \vdots \\ 1 & t_m \end{bmatrix}\),   \(A\T A = \begin{bmatrix} m & \sum t_i \\ \sum t_i & \sum t_i^2 \end{bmatrix}\),   \(A\T\vb b = \begin{bmatrix} \sum b_i \\ \sum t_i b_i \end{bmatrix}\)
\(p_i = C + Dt_i\),   \(e_i = b_i - p_i\),   \(E = \sum e_i^2\)
checks \(\sum e_i = 0\), \(\sum t_i e_i = 0\)
Orthonormal columns\(\vb q_i\T\vb q_j = 0\) for \(i \ne j\), \(\vb q_i\T\vb q_i = 1\);   \(Q\T Q = I\)
square \(Q\) (orthogonal matrix): \(Q^{-1} = Q\T\);   \(\nrm{Q\vb x} = \nrm{\vb x}\)
least squares: \(\hat{\vb x} = Q\T\vb b\),   \(\vb p = QQ\T\vb b = (\vb q_1\T\vb b)\vb q_1 + (\vb q_2\T\vb b)\vb q_2 + \cdots\)
Gram–Schmidt\(\vb A = \vb a\)
\(\vb B = \vb b - \dfrac{\vb A\T\vb b}{\vb A\T\vb A}\vb A\)
\(\vb C = \vb c - \dfrac{\vb A\T\vb c}{\vb A\T\vb A}\vb A - \dfrac{\vb B\T\vb c}{\vb B\T\vb B}\vb B\)
\(\vb q_1 = \vb A/\nrm{\vb A}\), \(\vb q_2 = \vb B/\nrm{\vb B}\), \(\vb q_3 = \vb C/\nrm{\vb C}\)
\(A = QR\)\(R = Q\T A\), upper triangular, diagonal entries \(\nrm{\vb A}, \nrm{\vb B}, \nrm{\vb C}\)
least squares via \(R\hat{\vb x} = Q\T\vb b\)