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 known as the steepest descent method, which converges for any symmetric and positive definite matrix (with a linear rate that depends on its condition number) independent of the initialization; see chapter 5.3.1 of Saad's [Iterative Methods for Sparse Linear Systems](http://www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf).

It is a nonlinear iterative method, since the new iterate $x\_{k+1}$ is not a linear function of $x\_k$ (as, e.g., in the Jacobi or Gauss-Seidel iteration) since it appears (by way of $g\_k$) in the definition of $\alpha\_k$. It should be pointed out that the conjugate gradient method (see top of page 200 in Saad's book) needs essentially the same amount of work and has (in practice much) 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.