

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer

Let $f: \mathbb R \rightarrow \mathbb R \in C^\infty$ and assume $0 < \alpha \leq f' \leq \beta $. Let $x_{k+1} := x_k - \lambda f(x_k)$ with $x_0 \in \mathbb R$,$\lambda > 0$ and $\lambda \beta <2$. Then $(x_k)_{k=0}^\infty$ converges to $x_*$ with $f(x_*) =0 $. We assume that $x_*$ exists.

My approach:

We have $|x_{k+1}-x_*| = |x_k - \lambda f(x_k) -x_*| \leq |x_k - x_*| + \lambda |f(x_k)|$ but $$ |f(x_k)| = \left | f(x_*) + \int_{x_*}^{x_k} f'(u) du \right| \leq \beta|x_k-x_*| $$ which gives $$ |x_{k+1}-x_*| \leq |x_k-x_*| + \lambda \beta |x_k -x_*| = |x_k-x_*|(1+\lambda \beta) $$ By induction $$ |x_k -x_*| \leq |x_0-x_*|(1+\lambda \beta)^n $$ which tells me that $|1+\lambda\beta| < 1$ should be true in order to converge ??? What am I doing wrong here ?

share|cite|improve this question
you mean $f'\leq\beta$ right?I can't edit cos it is just 1 letter... – Lost1 Mar 26 '13 at 19:38
In a sense your bound is a too wasteful and not taking the full advantage of the fact that $f$ is increasing. – Lost1 Mar 26 '13 at 20:06
up vote 0 down vote accepted

we assume without the loss of generality that $x>y$

consider the map $g(x) = x- \lambda f(x)$

Then $|g(x)-g(y)| = |(x-y) - \lambda (f(x)-f(y))|$

Notice $f(x)-f(y)\leq\beta(x-y)$ by the derivative condition. It is positive and so is $(x-y)$. so we must have

$|g(x)-g(y)|\leq|1-\lambda\beta||x-y|$ But this means $g$ is a contraction map, hence by contraction mapping theorem, it has a unique fixed point.

i.e. a unique $x^* = x^* - \lambda f(x^*)$ so $f(x^*)=0$

share|cite|improve this answer

You have lost to much in the first application of the triangle inequality: \begin{align*}|x_{k+1} - x_*| &= \left|x_k - x_* - \lambda \, \int_0^1 f'(x_* + t\, (x_k - x_*) ) \, (x_k - x_*) \, du \right| \\ &= \left|\int_0^1 \big( 1-\lambda \, f'(x_* + t\, (x_k - x_*) )\big) \, (x_k - x_*) \, du \right| \\ &\le \max(|\lambda\,\beta-1|,|1-\lambda\,\alpha|) \, |x_k - x_*| \end{align*} Using $\max(|\lambda\,\beta-1|,|1-\lambda\,\alpha|) <1$ yields convergence.

By the way: Did you have noticed, that this is some kind of simplified Newton method?

share|cite|improve this answer

Your Answer


