Skip to content
Tutorials Center
My learning

Topics

Lesson 34 of 62 ยท Determinants and Orthogonality

Gram-Schmidt and QR Decomposition

Build orthonormal bases with the Gram-Schmidt process, compare classical and modified versions for stability, and use np.linalg.qr to factor and solve systems.

Orthonormal bases are wonderful to work with: coordinates are plain dot products, lengths are preserved and nothing needs inverting. But the bases we are handed are rarely orthonormal. The Gram-Schmidt process converts any set of independent vectors into an orthonormal set that spans the same space. Written as a matrix factorization, it becomes the QR decomposition A = QR, one of the workhorses of numerical computing.

This lesson derives Gram-Schmidt from projections, implements the classical and the modified versions, shows that they behave very differently in floating point, and then uses np.linalg.qr.

The Gram-Schmidt loop

Take a vector The next column of A.
Subtract projections Remove what earlier directions explain.
Normalize Divide by the length.
1 / 2

The idea

Start with independent columns a1, a2, a3, .... We build orthonormal vectors q1, q2, q3, ... one by one:

  1. q1 is just a1 scaled to length 1.
  2. Take a2 and subtract its projection onto q1. What remains is perpendicular to q1. Scale it to length 1 to get q2.
  3. Take a3, subtract its projections onto q1 and q2, and scale what remains to get q3.

In general:

TEXT
v_k = a_k โˆ’ (q1ยทa_k) q1 โˆ’ (q2ยทa_k) q2 โˆ’ โ€ฆ โˆ’ (q_{kโˆ’1}ยทa_k) q_{kโˆ’1}
q_k = v_k / |v_k|

Because the q's already have length 1, the projection coefficient is simply the dot product qแตขยทa_k. At every stage q1โ€ฆqk span exactly the same space as a1โ€ฆak, so the process finds an orthonormal basis for the column space. If some v_k comes out as zero, a_k was dependent on the earlier columns, which is the linear independence test in disguise.

Python Classical Gram-Schmidt from scratch

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Qแต€Q is the identity, so the columns are orthonormal. Each column of Q points the way the original column did, minus whatever the earlier directions already covered.

From Gram-Schmidt to QR

The same calculation records how to rebuild each original column from the q's. Since a_k equals its component along q_k plus its projections on earlier q's, we can write

TEXT
a_k = r_{1k} q1 + r_{2k} q2 + โ€ฆ + r_{kk} q_k

with r_{ik} = qแตขยทa_k and r_{kk} = |v_k|. Collect the coefficients into a matrix R and the equation becomes A = QR. R is upper triangular, because column k of A only involves q1 through qk.

Python Recording R while orthogonalizing

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Classical versus modified Gram-Schmidt

The version above is classical Gram-Schmidt (CGS): every projection coefficient is computed from the original a_k. On paper that is identical to a rearranged version called modified Gram-Schmidt (MGS), which updates the working vector after each subtraction and uses the current remainder:

Python
for i in range(k):
    R[i, k] = Q[:, i] @ v      # v, not A[:, k]
    v -= R[i, k] * Q[:, i]

In exact arithmetic the two give the same answer. In floating point they do not. When the columns are nearly parallel, CGS subtracts large nearly equal numbers and the rounding errors pile up, so the computed q's lose orthogonality. MGS corrects errors as it goes and keeps much better orthogonality. The Hilbert matrix, whose columns are almost parallel, makes a good torture test.

Python Loss of orthogonality: CGS vs MGS vs np.linalg.qr

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three errors differ by many orders of magnitude. Classical Gram-Schmidt produces vectors that are far from orthogonal, modified Gram-Schmidt does much better, and the library routine is accurate to machine precision. The takeaway: understand Gram-Schmidt to see what QR means, but call a library routine for real work.

np.linalg.qr

NumPy computes QR with Householder reflections, which are orthogonal transformations and therefore numerically very stable. The default "reduced" mode returns Q with the same shape as A (for tall matrices) and a square R. Use mode="complete" to get a full square Q.

Python np.linalg.qr on a tall matrix

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The signs of the diagonal of R returned by NumPy can be negative, so its Q may differ from a Gram-Schmidt result by flipping some columns. Both are valid: a QR factorization is unique only up to those signs. If you need a positive diagonal, multiply the matching column of Q and row of R by -1.

Solving systems with QR

If A = QR with Q square and orthogonal, then Ax = b becomes QRx = b, and multiplying by Qแต€ gives

TEXT
R x = Qแต€ b

An upper triangular system, solved by back substitution (see Gaussian Elimination). No inverse and no Aแต€A. For a tall A the same steps give the least squares solution, and the conditioning is far better than with the normal equations, because forming Aแต€A squares the condition number.

Python Solving Ax = b with QR

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does the Gram-Schmidt process do to the next vector a_k?

    Removing the components along the earlier orthonormal vectors leaves a vector perpendicular to all of them, which is then scaled to length 1.
  2. 2. In A = QR, what is special about R?

    Column k of A only involves q_1 through q_k, so entries of R below the diagonal are zero.
  3. 3. Why is modified Gram-Schmidt preferred over classical Gram-Schmidt in floating point?

    Both are equal in exact arithmetic, but MGS uses the current remainder for each projection, so rounding errors do not pile up as badly.
  4. 4. A tall matrix A (4 by 2) goes through np.linalg.qr with default settings. What shapes come back?

    The default reduced mode keeps only the columns of Q that span the column space, so Q has A's shape and R is square.

Summary

  • Gram-Schmidt turns independent columns into orthonormal ones by subtracting projections onto the earlier directions and normalizing.
  • Recording the coefficients gives A = QR: Q has orthonormal columns, R is upper triangular.
  • Classical Gram-Schmidt can lose orthogonality in floating point; modified Gram-Schmidt is better, and Householder-based np.linalg.qr is best.
  • Solve Ax = b by Rx = Qแต€b with back substitution; the same idea gives stable least squares.
  • QR factors are unique only up to column signs.

Next up: Least Squares, fitting a model to more equations than unknowns.