Find all of the x-intercepts using the Newton Method.

Question

Use the Newton Method and find all of the x-intercepts of the function: $$f(x)=x^3-4x^2+1$$

The Newton Method to finding the x-intercept is:

$$x_{i+1}=x_i - \frac{f(x_i)}{f'(x_i)}$$

Step $1$: $$f(0)=(0)^3-4(0)^2+1=1 < 0$$ $$f(1)=(1)^3-4(1)^2+1=-2 > 0$$ Thus: $$\frac{0+1}{2}=0.5=x_1$$

Step $2$: $$f(0.5)=0.125$$ $$f'(0.5)=-3.25$$ $$x_2=0.5- \frac{0.125}{-3.25}=0.5285$$

Step $3$: $$f(0.5285)=-0.00377...$$ $$f'(0.5285)=-3.43805325...$$ $$x_3=0.5285 - \frac{-0.00377...}{3.43805325...}=0.53740...$$

It's fair to say that $x \approx 0.53740...$. However, from the Fundamental Theorem of Algebra we know that $f(x)$ should have $2$ more x-intercepts. How can I find those?

Answer 1

You're going to have find out where else the function switches sign. The newton method for finding intercepts basically takes you to the closest intercept your initial point was at. So find out where else the function switches sign and repeat what you did here. It's a tad tedious but that's how it is sometimes.

Answer 2

As @Christopher La Fond Jr. answered, the first task is to find an interval which conatins the root.

So, say that you found $a < x < b$. The question is : what shall we use as $x_0$ ? $a$ or $b$.

The answer is given by Darboux theorem. To avoid any overshoot of the solution, you must start at $x_0=c$ such that $$f(c) \times f''(c) > 0$$

Using your function, we know that there is a solution between $3$ and $5$. Let us see what happens $$\left( \begin{array}{cc} n & x_n \\ 0 & 3.00000 \\ 1 & 5.66667 \\ 2 & 4.59768 \\ 3 & 4.08578 \\ 4 & 3.94597 \\ 5 & 3.93549 \\ 6 & 3.93543 \end{array} \right)$$

$$\left( \begin{array}{cc} n & x_n \\ 0 & 5.00000 \\ 1 & 4.25714 \\ 2 & 3.97849 \\ 3 & 3.93637 \\ 4 & 3.93543 \end{array} \right)$$

Computing $f(3) \times f''(3) =-80$ but $f(5) \times f''(5) =572$

Answer 3

In general, there are multiple cases to consider. For example, you could have 3 distinct real roots, 2 distinct real roots with one of them being a double root, one real root with a pair of complex conjugate non-real roots. It's worthwhile plotting your function, this will give you a great deal of insight and guidance for choosing your initial iterate $x_0$

Answer 4

You can look at the dominating binomials of the polynomial. The first is $x^3-4x^2$ with a focus on large roots giving a root close to $x=4$. The second is $-4x^2+1$ with a focus on smaller roots giving roots close to $x=\pm\frac12$. To get an impression of how good these estimates are, compute the product of the corresponding factors $$ (x-4)(x^2-\frac14)=[x^3-4x^2+1] -\frac14x $$ so that the difference to the original polynomial is a small, but still significant term.

This kind of "guessing" can be made a little more systematic via the Dandelin-Graeffe method and its refinements. The original method gives magnitude estimates for the roots, with some care one can also reconstruct the approximate phase factors.

Answer 5

Hint: you might want to check with Descartes' Rule of Signs how many positive/negative real roots your equation possibly has.

Answer 6

it is nice to understand why NR works in the way that it does. If we have an iteration point $x_i,f(x_i)$ where $f(x_i)>0$ then we want our value to change such at $0<f(x_{i+1})<f(x_i)$. We can approximate where the root is by drawing a straight line to it, so assuming that the function is of the form $f(x)=f(x_i)(x-\alpha)$.

---

Using this we make the approximation that $f'(x_i)\approx\frac{f(x_i)}{x_i-\alpha}$ and this can be manipulated into the formula that we use. Knowing this, you can see that the algorithm will always converge towards the closest route, so to find multiple real routes (if they exist) you have to provide a different starting value. Again the easiest way to do this is using the change of sign iterations.

One problem that you may encounter is that is two roots are close together e.g. $$n\in\mathbb{Z},\,\,\,\alpha_1,\alpha_2\in\mathbb{R}\,\,\,\,\,\, n<\alpha_1<\alpha_2<n+1$$ then the change of sign rule will displace the same sign at both $n$ and $n+1$ making it easy to miss roots.

Hope this helps!

Answer 7

I’m not really sure it is possible on an unbounded function but if you want to find the the roots of a function I suggest you divide your interval $[a,b]$ Into n intervals where your step size h=$\frac{b-a}{n}$

Let $[i,i + h]$ be a sub interval

Record all the sub intervals where $f(i)f(i + h)<0$ Then apply Newton’s fixed point method to find the roots in those intervals and you should be able to all roots in the interval [a,b]