[Math] $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$.

calculusnewton raphsonnumerical methodssequences-and-series

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

Best Answer

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)}$.

Related Question