Steffensen's method. Consider the iteration formula
$$x_{n+1}=x_n-f(x_n)/g(x_n)$$
where
$$g(x)=[f(x+f(x))-f(x)]/f(x)$$
Show that this quadratically convergent, under suitable hypotheses.
I have to prove that there is a $C>0$ such that $|x_{n+1}-r|\leq C|x_n-r|^2$ where $r$ is the root I want to find, in other words I want $|e_{n+1}|\leq C|e_n|^2$, where $e_n=x_n-r$. I have tried to do the following $e_{n+1}=x_{n+1}-r=x_n-f(x_n)/g(x_n)-r=e_n-f(x_n)/g(x_n)$, but I do not know what else to follow. Could anyone help me, please? Thank you very much.
You start with $x_n=r+\epsilon$ where $f(r)=0$. Then $$f(x_n)=f(r+\epsilon)=f(r)+\epsilon f^{\prime}(r)+\frac12\epsilon^2f^{\prime\prime}(r)+O(\epsilon^3)=\epsilon f^{\prime}(r)+\frac12\epsilon^2f^{\prime\prime}(r)+O(\epsilon^3)$$ And on to $$\begin{align}f(x_n+f(x_n))&=f(r+\epsilon+f(r+\epsilon))=f\left(r+\epsilon(1+f^{\prime}(r))+\frac12\epsilon^2f^{\prime\prime}(r)+O(\epsilon^3)\right)\\ &=f(r)+\epsilon(1+f^{\prime}(r))f^{\prime}(r)+\frac12\epsilon^2f^{\prime\prime}(r)f^{\prime}(r)+\frac12\epsilon^2f^{\prime\prime}(r)(1+f^{\prime}(r))^2+O(\epsilon^3)\\ &=\epsilon(1+f^{\prime}(r))f^{\prime}(r)+\frac12\epsilon^2f^{\prime\prime}(r)(1+3f^{\prime}(r)+(f^{\prime}(r))^2)+O(\epsilon^3)\end{align}$$ EDIT: It seems the easier path at this point is to dispense with intermediate expressions and attack the final result directly: $$\begin{align}x_{n+1}&=x_n-\frac{\left(f(x_n)^2\right)}{f\left(x_n+f(x_n)\right)-f(x_n)}\\ &=r+\epsilon\\ &\quad-\frac{\left(\epsilon f^{\prime}(r)+\frac12\epsilon^2f^{\prime\prime}(r)+O(\epsilon^3)\right)^2}{\epsilon\left(1+f^{\prime}(r)\right)f^{\prime}(r)+\frac12\epsilon^2\left(1+3f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)+O(\epsilon^3)-\epsilon f^{\prime}(r)-\frac12\epsilon^2f^{\prime\prime}(r)+O(\epsilon^3)}\\ &=r+\epsilon-\frac{\epsilon^2\left(f^{\prime}(r)\right)^2+\epsilon^3f^{\prime}(r)f^{\prime\prime}(r)+O(\epsilon^4)}{\epsilon\left(f^{\prime}(r)\right)^2+\frac12\epsilon^2\left(3f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)+O(\epsilon^3)}\\ &=r\\ &\quad+\frac{\epsilon^2\left(f^{\prime}(r)\right)^2+\frac12\epsilon^3\left(3f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)+O(\epsilon^4)-\epsilon^2\left(f^{\prime}(r)\right)^2-\epsilon^3f^{\prime}(r)f^{\prime\prime}(r)+O(\epsilon^4)}{\epsilon\left(f^{\prime}(r)\right)^2+\frac12\epsilon^2\left(3f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)+O(\epsilon^3)}\\ &=r+\frac{\frac12\epsilon^3\left(f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)+O(\epsilon^4)}{\epsilon\left(f^{\prime}(r)\right)^2+\frac12\epsilon^2\left(3f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)+O(\epsilon^3)}\\ &=r+\frac{\frac12\epsilon^3\left(f^{\prime}(r)+\left(f^{\prime}(r)\right)^2\right)f^{\prime\prime}(r)\left(1+O(\epsilon)\right)}{\epsilon\left(f^{\prime}(r)\right)^2\left(1+O(\epsilon)\right)}\\ &=r+\frac12\epsilon^2\frac{f^{\prime\prime}(r)}{f^{\prime}(r)}\left(1+f^{\prime}(r)\right)+O(\epsilon^3)\end{align}$$
So there you have it: $$|x_{n+1}-r|=\frac12|x_n-r|^2\frac{f^{\prime\prime}(r)}{f^{\prime}(r)}(1+f^{\prime}(r))+O(|x_n-r|^3)$$ With assumptions like: $x_n$ is close enough to $r$ that a linear approximation is not too bad and also that $f(x)$ has a continuous second derivative in some neighborhood of $x=r$.