# Convergence of the gradient descent and linear vs non-linear fixed point iteration

Suppose a system $$Ax=b$$ is given, with $A\in\mathbb{R}^{n\times n}$ being a symmetric positive-definite matrix, and some non-zero $b\in\mathbb{R}^n$. The gradient method with optimum step length can be written as $$x_{k+1}=x_k-\alpha_k\cdot g_k,$$ with $g_k=Ax_k-b$ and $\alpha_k=\frac{g_k^Tg_k}{g_k^TAg_k}$.

Can it be proven that the above iterative procedure converges to $\bar{x}=A^{-1}b$, regardless of the initialization?

Can the above iterative scheme be regarded as a linear fixed-point iteration? In fact, what is the precise meaning of linear in the term linear fixed-point iteration?

• Hi usero, is this a homework question? – Aron Ahmadia Sep 11 '12 at 18:47
• @AronAhmadia I'm a bit too old for homeworks. – usero Sep 11 '12 at 19:04
• If $A$ is spd, why not use conjugate gradient methods. They are guaranteed to converge in at most $n$ iterations (in exact arithmetic). – Daryl Sep 11 '12 at 21:28

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.

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.

• So, as I assumed, the presence of $\alpha_k$ makes the iterate non-linear (in case $\alpha_k=1$, it would be a linear iteration?). – usero Sep 13 '12 at 10:27
• Indeed -- this is called Richardson iteration. (It's virtually never used except when teaching iterative methods, since it only converges if $\|I-A\|<1$, i.e., when $A$ is "close" to the identity.) – Christian Clason Sep 13 '12 at 10:38

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.

• Ok, so you're saying that the above update is not linear fixed-point iteration (I guess because of $\alpha_k$, or?) Given that $\alpha_k$ is an optimal step length, it should be the case that the above iterative process converges to $\bar{x}=A^{-1}b$. – usero Sep 12 '12 at 11:23

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.

• According to www-users.cs.umn.edu/~saad/IterMethBook_2ndEd.pdf , Sect. 3.1, convergence is guaranteed if $A$ is symmetric positive definite matrix (which is what I stated). – usero Sep 13 '12 at 10:25
• OK, but then I don't understand your first question where you ask whether it can be proven that the iteration converges? – Wolfgang Bangerth Sep 14 '12 at 0:46