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

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?

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.

• Thanks. Sorry for not being clear. I ask if each $u_i$ is normalized, immediately after it is created by orthgonalization, or after all $u_i$'s are created by orthogonalization – Tim Nov 6 '14 at 19:43
• @Tim You cannot compute the orthogonal component of a vector $u$ w.r.t. $v$ without knowing the norm of $v$. If the $u_i$'s are not normalized immediately, you will have to normalize them explicitly every time they appear later in the Gram-Schmidt procedure. As far as I can tell, there's no confusion, I answered the question you meant to ask. – Kirill Nov 6 '14 at 19:47

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.$$

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

• How does this address the question? – Kirill Nov 6 '14 at 19:32
• It doesn't, and it also doesn't add any context. Householder transformations yield a $Q$ factor in a $QR$ decomposition that has tighter error bounds than modified Gram-Schmidt, but Householder transformations can't be used to generate orthonormal bases in iterative methods like Arnoldi, so modified Gram-Schmidt is more useful in that case. – Geoff Oxberry Nov 6 '14 at 20:08
• The question is about GS. The author did not state that he was using anything like Arnoldi. So it seems very reasonable to suggest a method that performs the desired task (i.e. full orthogonalization) more stably. I think my answer is legitimate. – Yair Daon Nov 8 '14 at 3:09
• @YairDaon: Don't worry it is typical for SE moderators to behave like this to bully new users. – timur Feb 10 '18 at 3:46