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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.