5.6 Gram–Schmidt · Linear Algebra Refresher

Orthonormal bases are wonderful; the problem is getting one. Gram–Schmidt manufactures an orthonormal basis from any basis by repeatedly subtracting projections — and its bookkeeping is the QR factorization.

Theorem 5.6.1 · Gram–Schmidt

Let

{x_{1}, \dots, x_{n}}

be a basis for an inner product space

S

. Define

u_{1} = (\frac{1}{∥ x _{1} ∥}) x_{1}

and, recursively,

p_{k} = i = 1 \sum k ⟨ x_{k + 1}, u_{i} ⟩ u_{i}, u_{k + 1} = \frac{x _{k + 1} - p _{k}}{∥ x _{k + 1} - p _{k} ∥} .

Then ${u_{1}, \dots, u_{n}}$ is an orthonormal basis for $S$ , and each $u_{k + 1}$ is orthogonal to everything built before it.

→Shortcut

By hand, don't normalise as you go. Compute the un-normalised

v_{k} = x_{k} - \sum \frac{⟨ x _{k} , v _{j} ⟩}{⟨ v _{j} , v _{j} ⟩} v_{j}

first — everything stays rational and the square roots only appear at the very end.

Theorem 5.6.2 · Gram–Schmidt QR

A

m \times n

with rank

n

, then

A = QR

where

Q

m \times n

with orthonormal columns and

R

n \times n

upper triangular with positive diagonal entries.

r_{ii} = ∥ x_{i} - p_{i - 1} ∥, r_{ij} = ⟨ x_{j}, u_{i} ⟩ (i < j) .

$R$ is upper triangular precisely because $u_{i}$ is built only from $x_{1}, \dots, x_{i}$ , so it has no component along later inputs.

Theorem 5.6.3 · Least squares via QR

With

A = QR

of rank

n

, the unique least squares solution of

A x = b

solves

R x^= Q^{T} b,

Substituting into the normal equations: $A^{T} A = R^{T} Q^{T} QR = R^{T} R$ and $A^{T} b = R^{T} Q^{T} b$ , then cancel the nonsingular $R^{T}$ . $R$ is triangular, so finish with back substitution — no inverse anywhere.

Worked example

Gram–Schmidt and QR on a $4 \times 3$ matrix

0/5 steps

Apply Gram–Schmidt to the columns of

A

and write

A = QR

A = 1111 - 1 44 - 1 4 - 2 20

Check your work

Gram–Schmidt & QR

Columns of the matrix are the input vectors. The un-normalised vectors stay exact; Q and R are shown numerically because norms bring in square roots.

Matrix (vectors are its columns)

v₁ = x₁

‖v₁‖² = 4 , ‖v₁‖ = 2

v₂ = x₂ − (3/2)v₁

-5/2

5/2

-5/2

‖v₂‖² = 25 , ‖v₂‖ = 5

v₃ = x₃ − (1)v₁ − (-2/5)v₂

-2

‖v₃‖² = 16 , ‖v₃‖ = 4

Q (orthonormal columns)

0.5	-0.5	0.5
0.5	0.5	-0.5
0.5	0.5	0.5
0.5	-0.5	-0.5

R (upper triangular, positive diagonal)

2	3	2
0	5	-2
0	0	4

Check yourself

In Gram–Schmidt, the next vector is

u_{k + 1} = \frac{1}{∥ x _{k + 1} - p _{k} ∥} (x_{k + 1} - p_{k})

. What is

p_{k}

T / F

A

m \times n

of rank

n

and

A = QR

is its Gram–Schmidt factorization, then the least squares solution of

A x = b

satisfies

R x = Q^{T} b

T / F

Gram–Schmidt can be applied to any spanning set, independent or not, and always returns an orthonormal basis of the same size.

5.6Gram–Schmidt

What you must be able to do

Gram–Schmidt and QR on a $4 \times 3$ matrix

Gram–Schmidt & QR

Check yourself

5.6Gram–Schmidt

What you must be able to do

Gram–Schmidt and QR on a 4×3 matrix

Gram–Schmidt & QR

Check yourself

Gram–Schmidt and QR on a $4 \times 3$ matrix