seegongsik
engineering mathematics

Gram-Schmidt process explained

Build an orthonormal basis from a skewed one by subtracting off projections; this is exactly the Q of QR

Suppose two vectors lean against each other. They span the same plane, but they are not perpendicular and their lengths differ, so calculation is awkward. Gram-Schmidt is the procedure that straightens this skewed basis. Keep the first direction, and from the second vector subtract the shadow it casts on the first, the projection. Only the part perpendicular to the first remains. Finally match both lengths to 1 and you get a unit frame that meets at a right angle. The step picture walks through how the leaning pair becomes orthonormal. The frame you straighten is the Q of a QR factorization. Gold is the projection and orange is what remains after the subtraction. Green is the unit vector whose length was matched first. The order of the buttons is the order of the procedure, and the number board later shows those same two arrows as the columns of Q.

Step through with the buttons. Step 0 is the skewed input a1, a2 as it stands. Step 1 shortens a1 to length 1 and makes the first green unit vector u1. Step 2 draws in gold the shadow a2 casts on u1, the projection (a2·u1)u1. It shows how much of the u1 direction sits inside a2. Step 3 subtracts that projection from a2, paints the remaining perpendicular part w in orange, and matches its length to 1 to get the second unit vector u2. Now u1 and u2 meet at a right angle. The skewed pair has been straightened into one orthonormal pair.

Take only the central move of Gram-Schmidt. Fix u1 as the unit vector on the x-axis and drag the blue vector a2 freely. The gold arrow is the projection (a2·u1)u1 that a2 casts on u1. It is only the u1 part inside a2. The orange arrow is what remains, a2 minus the projection. Wherever you drag a2, that orange remainder stays exactly perpendicular to u1. Subtracting the projection removes the parallel part and leaves only the perpendicular part. That one subtraction is what stands the skewed second vector upright.

However skewed the input, the output stays straight. Fix a1 and turn the angle of a2 with the slider. The two faint vectors are the skewed input a1, a2, and the bright right-angled unit frame u1, u2 is the output Gram-Schmidt straightens. However you tilt the input, the output u1 and u2 stay at length 1 and perpendicular to each other. There is one dangerous place. Make a2 nearly parallel to a1 and the plane to span disappears, and the perpendicular part nears 0. At that moment no orthonormal frame can be built and a warning appears. A nearly parallel basis cannot be straightened. The warning appears where the two arrows lie on top of each other, because there is no second direction left to stand upright.

Gram-Schmidt gives a different result depending on which vector you start from. The direction of the first vector is kept as it is. A button changes the starting order. Start with a1 and u1 follows the direction of a1 while u2 stands perpendicular to it. Start with a2 and now u1 follows a2 while u2 is the perpendicular. The same two inputs span the same plane, and the orthonormal frames that come out are turned differently from each other. Both are correct orthonormal bases. The procedure anchors on the first direction, so which one you call first decides the answer.

Gather the two unit vectors into one matrix. Turn on u1 and u2 one at a time and each takes its place as column 1 and column 2 of the matrix Q. The number board below shows that 2×2 Q, the green column u1 and the orange column u2. The two columns of Q are perpendicular unit vectors, so Q is a rotation that touches neither length nor angle, an orthogonal matrix. Thus Qᵀ Q = I. The Q gathered this way is the Q of a QR factorization. Any matrix A splits as A = QR, where Q is these orthonormal columns straightened by Gram-Schmidt and R is the upper-triangular matrix of the projection coefficients removed along the way.

In PracticeGram-Schmidt straightens a skewed basis a1, a2, … into an orthonormal basis u1, u2, …. The first vector is only shortened to length 1 and used as u1, and each later vector has the projections onto all earlier u directions removed and is then matched in length. That one subtraction erases the parallel part and leaves the perpendicular part, building a unit frame that meets at right angles. The result depends on the starting vector, and the first direction is kept. If the two inputs are nearly parallel there is no dimension left to span and the procedure collapses. Gather the straightened u vectors as columns and you get an orthogonal matrix Q, that is Qᵀ Q = I, and that is the Q of a QR factorization. Least squares, the QR algorithm, and the stability of numerical linear algebra stand on this one procedure. A skewed basis can still be straightened.
← engineering mathematics
Was this helpful? Support seegongsik