DEFINITION (QUADRATIC CONVERGENCE) : Let $\left\{x_k\right\}$ be a sequence of real numbers and $\xi \in \mathbb{R}$. We say that $x_k \to \xi$ quadratically if and only if
\begin{align*}
&(i) \lim_{k \to \infty} \left\lvert x_k-\xi \right\rvert=0\\
&(ii) \lim_{k \to \infty} \frac{\left\lvert x_{k+1}-\xi \right\rvert}{\left\lvert x_k-\xi \right\rvert^2}=c, \,\text{ for some } c>0
\end{align*}
THE PROBLEM : Consider the iteration
$$x_{k+1}=x_k-\frac{\left\{f\left(x_k\right)\right\}^2}{f\left(x_k+f\left(x_k\right)\right)-f\left(x_k\right)}, \,\,\,\,k=0,1,2,\dots,$$
for the solution of $f\left(x\right)=0$. Explain the connection with Newton-Raphson method, and show that $\left(x_k\right)$ converges quadratically if $x_0$ is sufficiently close to the solution.
My problem is that I do not know what $\xi$ is. Without that information, how can I verify the conditions of the definition of quadratic convergence? I do not see any connection with Newton-Raphson method. Thanks in advance.
Best Answer
Notations for convergence (in normed spaces)
The first condition, $\lim_{k\to\infty} \|x_k-\xi\|=0$ is the same as $\lim_{k\to\infty} x_k=\xi$ (with the given norm on the Banach space), which expresses the same as the first used $x_k\to \xi$ (for $k\to\infty$).
Roots of functions
In the application to Steffensen's method, $ξ$ is the solution of the equation $f(x)=0$, that is $ξ$ is a root, $f(ξ)=0$, and the sequence is, from the start, assumed to converge to this root.
Connection to Newton's method
You can consider $$ \frac{f(x+f(x))-f(x)}{f(x)} $$ as a special case of a difference quotient $$ \frac{f(x+h)-f(x)}{h}=f'(x)+O(h) $$ with $h=f(x)$. This means that the method is reasonably close to Newton's method. The distance to the root of the Newton step at $x$ is $O(f(x)^2)$. The difference of Steffensen's method to Newton's method is likewise $O(f(x)^2)$, so that the quadratic convergence is preserved, only constants in it may change.
Connection to Aitken's acceleration of fixed-point processes
Why this choice is sometimes sensible can be seen in the Aitken delta-squared process where $f(x)=g(x)-x$ is used to speed up the convergence of the fixed-point iteration $x_{k+1}=g(x_k)$. Then $f(x+f(x))=g(g(x))-x$ so that the formula involves the three elements $x, g(x), g(g(x))$ of the original iteration.