2
$\begingroup$

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?

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

3 Answers 3

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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?). $\endgroup$
    – usero
    Sep 13, 2012 at 10:27
  • $\begingroup$ 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.) $\endgroup$ Sep 13, 2012 at 10:38
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$
    – usero
    Sep 12, 2012 at 11:23
1
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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). $\endgroup$
    – usero
    Sep 13, 2012 at 10:25
  • $\begingroup$ OK, but then I don't understand your first question where you ask whether it can be proven that the iteration converges? $\endgroup$ Sep 14, 2012 at 0:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.