Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
1  
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
add comment

2 Answers

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|improve this answer
add comment

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|improve this answer
add comment

Your Answer

 
discard

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.