Finding more than one root using Newton's Method

Question

The problem is stated as follows:

Find the two roots of $x^{4}-8x^{2}-x+16 \:\:in \: [1,3].$

What is a good first guess / a good way to make a first guess when more than one root is involved, if one does not have access to the graph?

In this problem, would it be best to start with $x_{0}=1$ and $x_{0}=3$? I tried using $x_{0}=2$, but that yielded $f(x_{0})=-2, f(x_{1})=16, f(x_{3})=63488$, and that is many computations from $f(x)\approx0$.

Answer 1

The lesson you have to learn here is the following: Newton's method is of no help in finding the global configuration of the zeros; but if you start sufficiently near a zero you're going to find it.

Let $$f(x):=x^4-8x^2-x+16\ .$$ We have to undertake a global study of $f$ in the $x$-interval $[1,3]$.

First note that $f(1)=9>0$, $\>f(2)=-2<0$, $\>f(3)=22>0$.

We compute $$f'(x)=4x^3-16x-1=4x(x^2-4)-1\ ,$$ which shows that $f'(x)<0$ on $\ ]1,2[\ $, whence $f$ has at most one zero $\xi_1$ in this interval. Since $$f''(x)=12x^2-16$$ is $>0$ for $x>{2\over\sqrt{3}}\doteq1.155$, and $f\left({3\over2}\right)={25\over16}>0$, it is safe to start the search for $\xi_1$ at $x_0:={3\over2}$.

Since $f(2)<0$, $\>f(3)>0$ the function $f$ has one or three zeros in $\ ]2,3[\ $. Three zeros would, by Rolle's theorem, enforce $\geq2$ zeros of $f'$ and $\geq1$ zero of $f''$, but there is none of the latter in this interval. It follows that $f$ has exactly one zero $\xi_2$ in $\ ]2,3[\ $, and as $f''(x)>0$ in this interval it is safe to start the search for $\xi_2$ at $x_0:=3$.

Answer 2

Bairstow's method is of this nature, using Newton iterations to approximate two roots of a real polynomial simultaneously. However it is usually employed to find a pair of complex conjugate roots. Obviously if we find one quadratic real factor of the real quartic polynomial, the other factor will also be quadratic, and the quadratic formula can be used on both of them.

Added in view of OP's background:

From the single variable calculus perspective we can only pursue the roots by Newton iteration one at a time. However the experience with starting the Newton iteration at $x=2$ teaches us a valuable lesson. If our starting value is close to a critical point (there is a local maximum at $x\approx 2.0305$), the curve is pretty flat there and a Newton step will be correspondingly "big".

Because of this (and the related issue of two roots that are equal or close together), a practical approach is to use a more robust (but more slowly converging) method to get the initial value for Newton iteration. Here we might easily take a step or two with the bisection method to make sure we are much closer to one of the two roots than the other, and away from any critical points. We can say then that the root(s) are "isolated", and Newton's iteration should work well on each of them individually.