Convergence conditions for $x^{(k+1)} \leftarrow x^{(k)} + \alpha f(x^{(k)})$

Question

Problem

Specify the conditions that the following iteration converges to $x^\ast$, the root of $f$, i.e. $f(x^\ast)=0$,

$$ x^{(k+1)} \leftarrow x^{(k)} + \alpha f(x^{(k)}) $$

where $f:(a,b) \to \mathbb{R}$, $\exists f'$ on $(a,b)$, and $\{x \in (a,b):f(x)=0\} \neq \emptyset$.

---

Try

It seems to me that the above iteration is very similar to

$$ x^{(k+1)} \leftarrow x^{(k)} - [f'(x^{(k)})]^{-1} f(x^{(k)}) $$

which is basically the Newton-Raphson algorithm, so the conditions for the NR to converge may be applied here. However, I'm not sure how to proceed when $\alpha$ is not updated.

Any hint will be appreciated.

Answer 1

This is fixed point iteration with $$g(x)=x+\alpha (f(x))$$ Condition for convergence is $$g'(x)<1$$ i.e. $$1+\alpha f'(x)<1\forall x\in X$$ where $X$ is the set where the iterates and root lies.

Hope it helps:)