Can someone explain in details what every step in the modified gram Schmidt algorithm is doing?

MGS algorithm

Excerpts: Gram-Schmidt Algorithm gs

Modified Gram-Schmidt Algorithm mgs

This is what I think could someone correct me if I am wrong?

We are using a series of temporary vectors to build columns of Q and the non-zero elements of R. We iterate over the columns of A, completing a full run through of algorithm for each column of A. In modified GS instead of computing all the dot products from the original vectors, perform the projections one by one, using the result of the previous projections as the input to the next. By doing this we don't suffer from numerical instability as the round off errors in CGS can accumulate and destroy the orthogonality of the resulting vectors.


Gram-Schmidt in pictures

Perhaps pictorials will help. For simplicity, use only two vectors.

Step 1: Definition

Shown are two random vectors $u_{1}$ and $u_{2}$ against the unit circle.


Step 2: Projection

Normalize the first vector $u_{1}$ and call it $\hat{v}_{1}$. Compute the projection of the vector $u_{2}$ onto the vector $\hat{v}_{1}$. The projection is the red segment. 2

Step 3: Subtraction

Subtract the projection (red arrow) from $u_{2}$. This removes the $u_{2}$ components in the span of $\hat{v}_{1}$. The new vector, $v_{2}$, is orthogonal to $\hat{v}_{1}$. 3

Step 4: Normalization

$$\hat{v}_{2} = \frac{v_{2}}{\Vert v_{2} \Vert_{2}}$$ 4

Step 5: Final Result


Modified Gram-Schmidt is a more robust form of the process. If interested, details can be added.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.