How to choose the starting point in Newton's method?

Question

How to choose the starting point in Newton's method ?

If $p(x)=x^3-11x^2+32x-22$

We only learnt that the algorithm $x_{n+1}:=x_n-\frac{f(x_n)}{f'(x_n)}$ converges only in some $\epsilon$-neighbourhood of a root and that if $z$ is a root then $|z|\le 1+\max\limits_{k=0,...,n-1}\frac{|a_k|}{|a_n|}$

but in this case, $a_n=1\Rightarrow 1+\max\limits_{k=0,...,n-1}\frac{|a_k|}{|a_n|}=1+\frac{32}{1}=33$ this is too large isn't it ?

$\underline{\textbf{My attempt}}$

I think first root can be guessed by plugging in some values $-1,0,1,2$ and at $x=1$ we've a root

then the polynomial can be reduced to $x^3-11x^2+32x-22=(x-1)(x^2-10x+22)$

now the new polynomial to be examined is $g(x)=(x^2-10x+22)$

this is a parabola and $g'(x)=0$ is attained at $x=5$

and the advantage of the parabola is that we can consider any interval $[a,5)$ with $a<5$

any point in this interval as starpoint would converge to the $2^{nd}$ root

the same is valid for $(5,b]$, Hence we obtain our $3$ roots.

BUT in this case we had a bit luck, and if you know a general approach, can you please tell me

Thanks in advance.

Answer 1

The general case is very complicated. See for instance:

• Newton fractal

• How to find all roots of complex polynomials by Newton's method by Hubbard et al.
  Invent. Math. 146 (2001), no. 1, 1–33. pdf

Answer 2

In practice, you may draw a rough graph of the function. You see approximately where are the roots. This give you for each one an approximate value to start the recurrence process.

The first root obviously is $1$. The second is around $3.25$ and the third around $6.75$ The convergence will be fast in starting from these values.

In fact, the analytic solving leads to first $1$ , second $5-\sqrt3 = 3.267949...$ and third $5+\sqrt3 = 6.732051...$

Answer 3

For polynomials the starting point does not really matter, since Newton's method is contractive for large arguments, but with slow convergence. What that really means that the iteration remains bounded, and converges with high probability to one of the roots. So take any random point inside the computed root radius.

You have to check for cycles in the iteration, some polynomials have stable cycles for certain intervals of initial values. In general, after 5 iterations the method should be in the quadratically convergent phase, so check if the step size ratio falls below 0.5 and if that fails, pick another initial value and repeat.