Order of convergence of the recurrence to find the root of $f(x)$.

Question

The recurrence is given below.

$$x_{n+1} = \frac{x_{0}f(x_{n}) - x_{n}f(x_{0})}{f(x_{n}) - f(x_{0})}$$ for any $$n = 1, 2, \dots$$

I recall that the order of convergence of the recurrence or the iterative root-finding method is found by

$$\lim_{x \rightarrow \infty} \frac{e_{n+1}}{(e_{n})^{p}} = c$$

Where $c$ is any constants and $e_i$ is the difference (error) between $x_i$ and the root $r$ for any $i$. Then $p$ is the order of convergence of the method. Yet I am stuck during the following progress, would somebody please tell me what should I do next. Thank you forward for your response.

Answer 1

Let's assume that the sequence $x_{n+1} = g(x_n) := \dfrac{x_0 f(x_n)-x_nf(x_0)}{f(x_n)-f(x_0)}$ actually converges to a point $z$ satisfying $f(z)=0$ (or $g(z)=z$).Using Taylor's formula on $g$, we see that $$ g(x_n) = g(z) + g'(z)(z-x_n) + \frac 12 g''(z)(z-x_n)^2 + \cdots $$

Noting that $g(x_n)=x_{n+1}$ and that $g(z) = z$, the previous relation is implies that $$ |z-x_{n+1}| \leq |g'(z)||z-x_n| + \frac 12 |g''(z)| |z-x_n|^2 + \cdots $$

so, if $g'(z) = \cdots = g^{(k-1)}(z)=0$ and $g^{(k)}(z)\ne 0$, the method will converge with order $k$. In this particular case, since \begin{align*} g'(z) = & \dfrac{(x_0f'(z)-f(x_0))(f(z)-f(x_0))-f'(z)(x_0f(z)-z f(x_0))}{(f(z)-f(x_0))^2}\\ = & \dfrac{-f(x_0)(f'(z)-f(x_0))+z f'(z)f(x_0)}{f(x_0)^2}=\dfrac{-f'(z)+f(x_0)+zf'(z)}{f(x_0)}\\ \end{align*}

we can see that the method converges with order 1, unless $f(x_0)=f'(z)(1-z)$.

Answer 2

Next you use the Taylor expansion of $f$ around $r$, at least for $f(x_n)$.

Or apply the mean value theorem (twice) to the last factor in $$ e_{n+1}=e_ne_0·\frac{\frac{f(x_n)}{x_n-r}-\frac{f(x_0)}{x_0-r}}{f(x_n)-f(x_0)}. $$