Is it better to do normalization after all orthogonalization in Gram-Schmidt process?

Question

In Gram-Schmidt process, is it better to do normalization after orthogonalization of all the vectors in a basis, or to normalize each new vector immediately after it is created, from computational point of view?

Answer 1

When you consider the orthogonalization procedure, if $u$ and $v$ are vectors, then the orthogonal component of $u$ is either $$ u - (u,v)v $$ if $v$ has length $1$, or $$ u - \frac{(u,v)v}{\|v\|^2} = u - \left(u,\frac{v}{\|v\|}\right)\frac{v}{\|v\|} $$ if $v$ has some other length.

So if $v$ has not been normalized somewhere earlier in the procedure, its every appearance will be normalized anyway. So it shouldn't matter: either you normalize it immediately or you normalize it every time it appears later.

Answer 2

The short answer is yes, you should normalize the orthogonal projection of $u$ immediately after it is computed so that the orthogonalization algorithm may continue to generate the basis.

However, it deserves mention that when one computes an orthogonal basis with the Gram-Schmidt process in finite precision (i.e. numerically) it is possible to create a basis that is no longer orthogonal. As a maliciously chosen example, consider the vectors $$ u_1 = (1,\epsilon,0,0)^T,\quad u_2 = (1,0,\epsilon,0)^T, \quad u_3=(1,0,0,\epsilon)^T, $$ where we assume that $1 + \epsilon^2\approx 1$. Then the classical Gram-Schmidt process creates the "orthogonal" basis vectors $$ q_1 = (1,\epsilon,0,0)^T,\quad q_2=\frac{1}{\sqrt{2}}(0,-1,1,0)^T,\quad q_3 = \frac{1}{\sqrt{2}}(0,-1,0,1)^T. $$ But a quick check of orthogonality yields, for example, $$ q_2^Tq_3 = \frac{1}{2}. $$

This loss of orthogonality comes from the accumulation of roundoff errors in the classical Gram-Schmidt process. That is, in classical Gram-Schmidt we compute (signed) lengths of the orthogonal projections of $u_i$ onto the previous basis vectors $q_1, q_2,\ldots,q_{i-1}$, subtract these projections (and the rounding errors) from $u_i$ to obtain the new projection $w$, normalize, and obtain the next piece of the basis $q_i$. This projection (in exact arithmetic) is compactly written $$ w = \left(I-Q_{i-1}Q_{i-1}^T\right)u_i, $$ where the columns of $Q_{i-1}$ are the previously computed basis vectors $q_k$, $k=1,\ldots,i-1$. But numerically, because of rounding errors, the matrix $Q_{i-1}$ does not have truly orthogonal columns.

To stabilize the approximation and help guarantee that the numerical procedure will create an orthonormal basis in finite precision we use the modified Gram-Schmidt process. The difference is subtle but stabilizes the computation such that the vectors created will be "much more" orthogonal than those from classical Gram-Schmidt. The key is to ensure that the computation projects and orthogonalizes with respect to the computed version of the vector $w$. The spirit of the algorithm is the same, this is just a reordering of the computation to look like $$ w = \left(I - q_{i-1}q_{i-1}^T\right)\ldots\left(I-q_1q_1^T\right)u_i. $$ Notice that in exact arithmetic the two formulations will generate identical output. If we consider the same example as before, modified Gram-Schmidt will compute the orthonormal basis $$ q_1 = (1,\epsilon,0,0)^T,\quad q_2=\frac{1}{\sqrt{2}}(0,-1,1,0)^T,\quad q_3 = \frac{1}{\sqrt{6}}(0,-1,-1,2)^T, $$ for which we have discrete orthogonality (in finite precision as $\epsilon$ is assumed on the order of unit roundoff) $$ q_1^Tq_2 = -\frac{\epsilon}{\sqrt{2}},\quad q_1^Tq_3 = -\frac{\epsilon}{\sqrt{6}},\quad q_2^Tq_3 = 0. $$

Answer 3

It is best to use Housholder Transofrmations. http://en.wikipedia.org/wiki/Householder_transformation