Numerical Methods – How to Solve for the Interval of Convergence in Newton’s Method

convergence-divergencenewton raphsonnumerical methods

How do I solve for $\delta$ in $[r−\delta,r+\delta]$ where Newton's method will surely converge? For example in:

Explain Newton’s method for
$$f(x) = x^3+x−2 = 0.$$
Show that Newton’s method converges if $$x_0 \in [1−1/30 , 1+1/30 ]$$ to a limit $L$. Find an error
estimate for the error $$e_n = |x_n−L|.$$
(Hint: $x^3 −3x^2 +2 = (x−1)(x^2 −2x−2)$ and $|x^2 − 2x − 2| ≤ 10$ if $0 ≤ x ≤ 2$.)

How was the $1/30$ obtained?

Best Answer

Following the theory explained in https://math.stackexchange.com/a/1653829/115115, determine over $[0,2]$ $$ m_1=\min_{x\in[0,2]} |f'(x)|=\min_{x\in[0,2]} 3x^2+1=1 $$ and $$ M_2=\max_{x\in[0,2]} |f''(x)|=\max_{x\in[0,2]}6x=12 $$ and determine the "contraction" constant $$ C=\frac{M_2}{2m_1}=6. $$ From $$ |x_{n+1}-L|\le C·|x_n-L|^2=(C·|x_n-L|)·|x_n-L|\\ \implies |x_n-L|\le C^{-1}· (C·|x_0-L|)^{2^n} $$ one sees that the method is contractive and quadratically convergent for $$ |x_0-L|<\frac16. $$


Starting with the smaller interval $[\frac12,\frac32]$ these estimates give $m_1=\frac74$, $M_2=9$, $C=18/7<3$ leading to the greater radius $$|x_0-L|<\frac13$$ for the initial interval of good starting points.

Related Question