How to find the convergence rate of the Newton method for the function $f(x)=x^a$?

Question

The Newton method is $x_n=x_{n-1}-f(x_{n-1})/f'(x_{n-1})$? But in the function $f(x)$ there is no $n$ component for substitution, so I am unsure how to go about this?

Answer 1

In this formula for Newton's method, $n$ enumerates the iterations of the method. You start with some initial guess $x_0$ (as the zeroth iteration), and then proceed by calculating subsequent iterations: $$x_1=x_0-f(x_0)/f'(x_0);$$ $$x_2=x_1-f(x_1)/f'(x_1);$$ $$x_3=x_2-f(x_2)/f'(x_2);$$ and so on.

Then the next question will be how to find a good initial iteration, and what the rate of convergence will be (or whether the method will converge at all, for that matter).

Answer 2

For a sequence generated by iteration of some function $f(x)$ near one of its root $r$ $$x_n = f(x_{n-1})\quad\text{ for } n > 0\quad\text{ and }\quad x_0 \approx a$$ If $f(x)$ is nice enough around $r$ and $f'(r) \ne 0$, then for small $\epsilon$, we have

$$f(r + \epsilon) = f'(r) \epsilon + \frac12 f''(r) \epsilon^2 + o(\epsilon^2) \quad\text{ and }\quad f'(r+\epsilon) = f'(r) + f''(r)\epsilon + o(\epsilon)$$

If we write $x_n$ as $r + \epsilon_n$, then Newton iteration give us

$$\begin{align}r + \epsilon_{n+1} &= x_{n+1} = x_n - \frac{f'(x_n)}{f(x_n)} = r + \epsilon_n - \epsilon_n\frac{f'(r) + \frac12 f''(r)\epsilon_n + o(\epsilon_n)}{f'(r) + f''(r)\epsilon_n + o(\epsilon_n)}\\ &= r + \epsilon_n - \epsilon_n\left(1 - \frac12\frac{f''(r)}{f'(r)}\epsilon_n + o(\epsilon_n)\right)\\ &= \frac12\frac{f''(r)}{f'(r)}\epsilon_n^2 + o(\epsilon_n^2) \end{align} $$ This means whenever $x_n$ is close enough to $r$, $$\epsilon_{n+1} \approx \frac12 \frac{f''(r)}{f'(r)}\epsilon_{n}^2$$ The error $\epsilon_n$ will be squared down after each iteration of Newton method. The convergence rate is exponential, the number of correct digits of the root essentially get doubled in each iteration.

As an example, let us use Newton's method to find the square root of $r^2$ for some $r > 0$. The corresponding $f(x)$ is $x^2 - r^2$. Under Newton's iteration, we have following recurrence relation for the approximation value of $r$:

$$x_{n+1} = x_n - \frac{x_n^2 - r^2}{2x_n} = \frac12\left(x_n + \frac{r^2}{x_n}\right)$$ If we construct an auxiliary sequence $y_n = \frac{x_n - r}{x_n + r}$, it is easy to check $$y_{n+1} = \frac{x_{n+1}-r}{x_{n+1}+r} = \frac{x_n + \frac{r^2}{x_n} -2r }{ x_n + \frac{r^2}{x_n} + 2r} = \left(\frac{x_n-r}{x_n+r}\right)^2 = y_n^2 $$ Solving this give us a closed form for $y_n$ and hence one for $x_n$.

$$y_n = y_0^{2^n}\quad\implies\quad x_n = r\left(\frac{1+y_n}{1-y_n}\right) = r \left(\frac{1+y_0^{2^n}}{1-y_0^{2^n}}\right)$$

When $x_0$ is close to $r$ (in the case $x_0 > 0$ is enough), we have $|y_0| < 1$, For large $n$, $y_n$ become very small and

$$\epsilon_n \approx 2r y_0^{2^n}\quad\implies\quad |\log_{10}\epsilon_n| \approx 2^n |\log(y_0)|$$ As one can see, the number of correct digits do essentially get doubled in each iteration.

Finally, if $f'(r) = 0$, the convergence rate can be even faster. It is still exponential but instead of doubled, the number of correct digits can get tripled or something like that...