bounds of convergence $\delta$ for newton method?

Question

I'm very confused as to how to go about finding the bounds at which a function will converge to a root under the newton method?

Assume we have a function f(x) = $\sin(x)$ and we want to find the maximum bounds (-$\delta$,$\delta$) where if we apply newtons method on f(x) = $\sin(x)$ = 0 and we have a root at x_* = 0 our initial guess x₀ will converge...

any help with this? I am utterly confused?

Answer 1

The Newton step for $f(x)=\sin x$ is $$ N(x)=x-\frac{\sin x}{\cos x}=x-\tan x. $$ To guarantee convergence towards zero, you want that the distance to the root steadily decreases, that is, that $|N(x)|=|x−\tan x|<|x|$ in some interval around $x=0$. The boundary for that condition is at $\tanδ=2δ$. This can only be solved numerically, one finds $δ≈1.16556118520721$.

That this indeed is the boundary demonstrates the following table of iterations started closely around that boundary. As the sine is convex above and concave below the $x$ axis, the Newton step will always overshoot the root. This expected alternation of the sign can also be seen in the table.

$$\scriptsize \begin{array}{c|*{7}{c}} 0 & 1.14000000 & 1.15000000 & 1.16000000 & 1.17000000 & 1.18000000 & 1.19000000 & 1.20000000 \\ 1 & -1.03587513 & -1.08449695 & -1.13579854 & -1.18998109 & -1.24726636 & -1.30789939 & -1.37215162 \\ 2 & 0.65175523 & 0.80713512 & 1.01620172 & 1.30778141 & 1.73503399 & 2.40783378 & 3.59557218 \\ 3 & -0.11122247 & -0.23731194 & -0.59814707 & -2.40620572 & 7.76892661 & 3.30954346 & 3.10759952 \\ 4 & 0.00046090 & 0.00455759 & 0.08327300 & -3.31087155 & -3.95980344 & 3.13999547 & 3.14160575 \\ 5 & -0.00000000 & -0.00000003 & -0.00019302 & -3.13995699 & -2.89192662 & 3.14159265 & 3.14159265 \\ 6 & 0.00000000 & 0.00000000 & 0.00000000 & -3.14159266 & -3.14691283 & 3.14159265 & 3.14159265 \\ 7 & 0.00000000 & 0.00000000 & 0.00000000 & -3.14159265 & -3.14159260 & 3.14159265 & 3.14159265 \\ \end{array} $$

The plots below demonstrate that the boundary has a fractal nature, in a very short interval one can find initial points where the Newton method converges to any other root of the function. The first plot is close to $δ$, the second is for the full interval $[δ,\pi-δ]$ between the basins of attraction of the roots $0$ and $\pi$.

N(k,x)=(k==0)?x:N(k-1,x-tan(x)) is the Newton iteration with $k$ steps starting at $x$.