$x_{n+1}=x_n-{f(x_n)\over f'(x_0)}$. Find $C$ and $s$ such that $e_{n+1}=C{e_n}^s$.

Question

Consider a variation of Newton's Method in which only one derivative is needed; that is, $x_{n+1}=x_n-{f(x_n)\over f'(x_0)}$. Find $C$ and $s$ such that $e_{n+1}=C{e_n}^s$.

I know that $e_{n+1}=x_{n+1}-r=x_n-{f(x_n)\over f'(x_0)}-r=e_n-{f(x_n)\over f'(x_0)}=e_n-{f(x_n)\over f'(x_n)}+{f(x_n)\over f'(x_n)}-{f(x_n)\over f'(x_0)}$. I'm not sure how to proceed and show the $C$ and $s$ equality. Any solutions/hints are greatly appreciated

Answer 1

Start with the original Newton's method recurrence:

$$x_{n+1}=x_n - \frac{f(x_n)}{f'(x_n)} $$

and write $x_n=r+e_n$, where $r$ is the root $f(r)=0$ and we assume $e_n$ is small in the sense that we may perform Taylor expansions, viz.

$$\begin{align}e_{n+1} &= e_n - \frac{f(r)+e_n f'(r) + \frac12 e_n^2 f''(r)+\cdots}{f'(r)+e_n f''(r)+\frac12 e_n^2 f'''(r)+\cdots}\\ &= e_n \left (1-\frac{f'(r)+\frac12 e_n f''(r)+\cdots}{f'(r) + e_nf''(r)+\cdots} \right ) \\ &= \frac{f''(r)}{2 f'(r)} e_n^2 + O \left (e_n^3 \right )\end{align}$$

Of course we assumed that $f'(r) \ne 0$ in the above. I leave it to the reader to derive expressions for such a case and other odd cases.

This is of course the well-known result of quadratic convergence of Newton's method (so long as you made a good initial guess).

The question is what happens if the recurrence becomes

$$x_{n+1}=x_n - \frac{f(x_n)}{f'(x_0)} $$

Define $x_0 = r+e_0$. That is, $e_0$ is the error in the first guess. Using the same technique as above, I find that

$$e_{n+1}=\frac{f''(r)}{f(r)}e_n (e_0-e_n) +O \left (e_n^2 \right )$$

Now, $e_0$ is fixed. Thus we may write

$$e_{n+1}=\frac{f''(r) e_0}{f(r)}e_n+O \left (e_n^2 \right )$$

Thus $s=1$ and $C=\frac{f''(r) e_0}{f(r)}$.

Answer 2

Take $e_{n+1} = x_{n+1} - r = x_n - r - \frac{f'(x_n)}{ f(x_0)} = \frac{e_nf'(x_0) - f(x_n)}{f'(x_0)}$.

And note that $e_0 = x_0 - r$.

By Taylor's theorem:

$0 = f(r) = f(x_n - e_n) = f(x_n) - e_nf'(x_n) + \frac{1}{2}e_n^2f''(\xi_n)$.

$0 = f(r) = f(x_0 - e_0) = f(x_0) - e_0f'(x_0) + \frac{1}{2}e_0^2f''(\xi_0)$.

Then $e_nf'(x_0) = \frac{e_nf(x_0)}{e_0} + \frac{e_ne_0}{2}f''(\xi_0)$

We can plug our expression for $e_nf'(x_0)$ into our original equation for $e_{n+1}$ to get:

$e_{n+1} = \frac{(e_nf(x_0)/e_0 + [(e_ne_0)/2]f''(\xi_0) - f(x_n)}{f'(x_0)}$.

Now, we assume that our initial point $x_0$ is close to the root and that our $x_n$ values are also close to the root.

Then $e_{n+1} \approx \frac{e_ne_0 f''(r)}{2f'(r)}$.

$s = 1$ and $C = \frac{f''(r)e_0}{2f'(r)}$.