Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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


By posting your answer, you agree to the privacy policy and terms of service.

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