Question: A method to orthogonalize a set of vectors (vectors of unit length that are mutually orthogonal) is the Gram-Schmidt process:
<http://en.wikipedia.org/wiki/Gram%E2%80%93Schmidt_process>

Note that the the nested *for* loops imply that the difference is between vector $v\_i$ and vectors $\{v\_1, \dots, v\_{i-1}\}$.

However, I wonder about the behavior of the process in case the set of input vectors is linearly dependent. Namely, suppose the process is initialized on vectors $\{v\_1, v\_2, v\_3, v\_4, v\_5\}$. In case $v\_4$ can be expressed as a linear combination of $\{v\_1, v\_2, v\_3\}$, the process will set $v\_4=0\_n$ (i.e, zero vector).

Now suppose that $v\_2$ can be expressed as a linear combination of $\{v\_3, v\_4, v\_5\}$. Would such *ordering* of vectors imply that the Gram-Schmidt process will fail to set $v\_2=0\_n$ (fail to report linear dependence)? If so, what is the common way to ensure that Gram-Schmidt would yield orthonormal vectors and report linearly dependent ones?

Answer: 
This is a damped Richardson method. Since one step of this operation, $x\_k \mapsto x\_{k+1}$ is not a linear operation, it is not a stationary iteration. The presence of the extra matrix multiply and extra reduction per iteration make the method very unattractive compared to Krylov subspace methods which need onyl one operator application and have better convergence properties.
It is easy to verify that $x=A^{-1}b$ is indeed a fixed point of the iteration. The question is whether the iteration operator
$$
 I - \alpha A
$$
is a contraction. If $A$ is SPD, this is the case if $\alpha$ were less than or equal $\frac{1}{\lambda\_{\textrm{max}}}$.

On the other hand, we can only infer with simple arguments that $\alpha\le\frac{1}{\lambda\_{\textrm{min}}(A)}$. This is not enough to guarantee convergence using the usual arguments of linear iterations. In other words, it is the nonlinearity of the iteration that ensures that this actually converges, if in fact it does. One would need a more sophisticated analysis to then prove convergence.