The Stable Solution: The Gram-Schmidt Process

The constructive algorithm that takes a 'bad' basis and straightens it out into a perfect orthonormal basis.

In our last lesson, we discovered the potential dangers of the Normal Equations. The act of computing `AᵀA` can lead to numerical instability, especially when the columns of our matrix `A` are nearly parallel.

The root of the problem is that the columns of `A` can be "badly behaved." They can point in similar directions, creating a skewed and unstable coordinate system.

What if we could fix this? What if we could take any set of basis vectors (like the columns of `A`) and convert them into a perfect basis—one where every vector is orthogonal to every other vector, and every vector has a length of 1?

This is the goal of the Gram-Schmidt Process. It is a beautiful, constructive algorithm that takes a "bad" basis and systematically straightens it out into a "good" orthonormal basis.

The Goal: Orthonormal Bases

A set of vectors

\{q_1, q_2, ..., q_n\}

is orthonormal if they are mutually orthogonal (dot product is 0) and all have a length of 1.

Working with an orthonormal basis is a dream. Projections become trivial, and matrices whose columns are orthonormal (our **Orthogonal Matrices, `Q`**) are numerically perfect, with a condition number of 1.

The Algorithm: Step-by-Step Purification

The process takes a set of independent vectors

\{v_1, v_2, ...\}

and generates an orthonormal set

\{q_1, q_2, ...\}

that spans the same space.

Step 1: The First Vector (The Anchor)

Take the first vector $v_1$ , which becomes our first orthogonal vector $u_1$ . Then, normalize it.

q_1 = \frac{v_1}{\|v_1\|}

Step 2: The Second Vector (The Subtraction Trick)

Take the second vector $v_2$ and subtract its projection onto the first new vector $q_1$ . This removes any component of $v_2$ that is parallel to $q_1$ , leaving only the orthogonal part $u_2$ .

u_2 = v_2 - (q_1^T v_2) q_1

Then normalize $u_2$ to get $q_2$ .

q_2 = \frac{u_2}{\|u_2\|}

Step 3: The Third Vector and Beyond...

The pattern continues. To find $u_3$ , take $v_3$ and subtract its projections onto *all* previously found orthonormal vectors ( $q_1$ and $q_2$ ).

u_3 = v_3 - (q_1^T v_3) q_1 - (q_2^T v_3) q_2

Then normalize.

A Concrete Example

Let's orthonormalize the basis

v_1 = [3, 4]

and

v_2 = [1, 5]

Step 1: Process $v_1$

$\|v_1\| = \sqrt{3^2 + 4^2} = 5$

$q_1 = \frac{1}{5}[3, 4] = [0.6, 0.8]$

Step 2: Process $v_2$

Subtract the projection of $v_2$ onto $q_1$ :

$q_1^T v_2 = (0.6)(1) + (0.8)(5) = 4.6$

$u_2 = [1, 5] - 4.6 \cdot [0.6, 0.8] = [1, 5] - [2.76, 3.68] = [-1.76, 1.32]$

Normalize $u_2$ :

$\|u_2\| = \sqrt{(-1.76)^2 + (1.32)^2} = \sqrt{3.0976 + 1.7424} = \sqrt{4.84} = 2.2$

$q_2 = \frac{1}{2.2}[-1.76, 1.32] = [-0.8, 0.6]$

Result

Our new orthonormal basis is $\{ q_1=[0.6, 0.8], q_2=[-0.8, 0.6] \}$ .

**Up Next:** We will assemble these new orthonormal vectors into a matrix `Q` to form the QR Decomposition.