Gram-Schmidt Orthogonalization - Introduction to Scientific Computing

Big Idea

The Gram-Schmidt algorithm transforms any basis into an orthonormal basis—and in doing so, computes the QR factorization. Just as Gaussian elimination organized as matrix operations gives LU, Gram-Schmidt organized as matrix operations gives QR.

Prerequisite: Math 235

You learned the Gram-Schmidt process in linear algebra (Math 235). Here we revisit it with two new perspectives: (1) understanding it as computing a matrix factorization, and (2) analyzing its numerical behavior.

The Problem¶

Given linearly independent vectors $a_1, \ldots, a_n$ , find an orthonormal basis $q_1, \ldots, q_n$ for the same subspace.

The Algorithm¶

The idea is simple: process vectors one at a time, subtracting off their projections onto previously computed orthonormal vectors.

Algorithm 1 (Classical Gram-Schmidt)

Input: Linearly independent vectors $a_1, \ldots, a_n$

Output: Orthonormal vectors $q_1, \ldots, q_n$

for $j = 1, 2, \ldots, n$ :
$\qquad v_j = a_j$
$\qquad$ for $i = 1, 2, \ldots, j-1$ :
$\qquad\qquad v_j = v_j - \langle a_j, q_i \rangle \, q_i$ $\quad$ (subtract projection)
$\qquad q_j = v_j / \|v_j\|$ $\quad$ (normalize)

Example 1 (Step-by-Step Gram-Schmidt)

From Gram-Schmidt to QR Factorization¶

Gram-Schmidt is actually computing a QR factorization! Rearranging the algorithm:

a_j = \sum_{i=1}^{j-1} \langle a_j, q_i \rangle \, q_i + \|v_j\| \, q_j

(6)

This means $a_j$ is a linear combination of $q_1, \ldots, q_j$ .

In matrix form:

\underbrace{\begin{pmatrix} | & | & & | \\ a_1 & a_2 & \cdots & a_n \\ | & | & & | \end{pmatrix}}_A = \underbrace{\begin{pmatrix} | & | & & | \\ q_1 & q_2 & \cdots & q_n \\ | & | & & | \end{pmatrix}}_Q \underbrace{\begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \end{pmatrix}}_R

(7)

where:

$r_{ij} = \langle a_j, q_i \rangle$ for $i < j$ (the projection coefficients)
$r_{jj} = \|v_j\|$ (the normalization factor)

Numerical Problems with Classical Gram-Schmidt¶

Despite its elegance, classical Gram-Schmidt has serious numerical issues.

When the columns of $A$ are nearly linearly dependent, the subtraction $v_j = a_j - \sum \langle a_j, q_i \rangle q_i$ involves subtracting nearly equal vectors. This catastrophic cancellation means the computed $v_j$ is dominated by rounding errors, and the resulting $\hat{q}_j$ is not orthogonal to the previous vectors.

The loss of orthogonality scales with the condition number of $A$ : the computed vectors satisfy $|\langle \hat{q}_i, \hat{q}_j \rangle| = \mathcal{O}(\kappa(A) \cdot \varepsilon_{\text{mach}})$ . For ill-conditioned matrices, this can be unacceptably large.

Example 2 (Loss of Orthogonality)

This motivates the Householder approach: instead of orthogonalizing columns by subtraction (which cancels), we triangularize $A$ by multiplication with orthogonal matrices, which preserves norms and avoids cancellation entirely.