1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ See the comment of related question for how to determine $\delta$ in general math.stackexchange.com/questions/1652978/… $\endgroup$ – Carl Christian Feb 20 '16 at 11:39
  • $\begingroup$ I still don't know how 1/30 was obtained. If you can solve it for me I would be so thankful $\endgroup$ – Guppy_00 Feb 20 '16 at 12:02
  • $\begingroup$ @ Carl Christian Help me! $\endgroup$ – Guppy_00 Feb 20 '16 at 12:12
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ So [1-1/6, 1+1/6] is like the maximum interval for convergence to the root=1 and since [1-1/30,1+1/30] is within the maximum interval, any guesses in [1-1/30,1+1/30] will lead to convergence? is that it? $\endgroup$ – Guppy_00 Feb 20 '16 at 13:13
  • $\begingroup$ Not the maximum interval, since $[1-1/3, 1+1/3]$ is larger, and even that is smaller than what $C=18/7$ leading to a radius of $δ=\min(1/2, 7/18)=7/18=1/3+1/18$ actually gives. But yes, $[1-1/30,1+1/30]$ is contained in these larger intervals. $\endgroup$ – Dr. Lutz Lehmann Feb 20 '16 at 13:45
  • $\begingroup$ so how do I find the maximum interval? Also I've come across this problem: f(x)=x^3-2x^2-11x+12=(x-4)(x-1)(x+3) for which x_o will newton's method converge for which root??? en.wikipedia.org/wiki/Newton%27s_method#Zero_derivative $\endgroup$ – Guppy_00 Feb 20 '16 at 13:50
  • $\begingroup$ Take a look at the Newton fractal wp-page to see that this is a non-trivial problem for polynomials of degree 3 or higher. $\endgroup$ – Dr. Lutz Lehmann Feb 20 '16 at 14:54
  • $\begingroup$ See for instance usefuljs.net/fractals/index.html?{"current":"newton","colourOptions":8,"TERMS":[1,0,-2,0,-11,0,12,0]} (all one address). $\endgroup$ – Dr. Lutz Lehmann Feb 20 '16 at 15:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.