2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Tim Nov 6 '14 at 19:43
  • $\begingroup$ @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. $\endgroup$ – Kirill Nov 6 '14 at 19:47
2
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ How does this address the question? $\endgroup$ – Kirill Nov 6 '14 at 19:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoff Oxberry Nov 6 '14 at 20:08
  • 1
    $\begingroup$ 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. $\endgroup$ – Yair Daon Nov 8 '14 at 3:09
  • $\begingroup$ @YairDaon: Don't worry it is typical for SE moderators to behave like this to bully new users. $\endgroup$ – timur Feb 10 '18 at 3:46

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.