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