1
$\begingroup$

I'm trying to understand Laguerre's method for root finding and I have hit one road block.

Suppose I have a polynomial $p(x) = x^4 + 1$ and an initial guess $x_0 = 0$. This results in division by zero in the above formula.

What to do in such cases? Should one backtrack and try again with different guess? Are there any guides on how to pick the next $x_k$?

"Numerical Recipes" contain a test for the zero division, in which case, the next step becomes polar(1+abx, iter), where abx is computed above and iter is the number of iteration. Does anyone know what does that polar(1+..., iter) mean? Why does it use polar coordinates?

$\endgroup$
  • $\begingroup$ I guess you should start with $x_0=1$ $\endgroup$ – kingW3 Apr 24 '14 at 9:38
2
$\begingroup$

Each iterative method that can be described by a fraction of some fashion, Newton, Halley, Laguerre, have points where the denominator is zero. There you can not start. Since these are only a finite number of points, it is rather improbable that you encounter these points during an iteration from a random initial point.

What is worse is that the polynomials $x^m\pm1$ show some strange behaviour under the Laguerre method, they converge only in an annulus around the unit circle. I have some pictures of this where you can observe this behavior starting with $m=5$.

$x^5-1$ $x^6-1$ $x^7-1$ $x^8-1$


I would imagine that abx stands for the absolute value of $x$. So what the polar formula is doing is selecting a circle that is to the outside of $x$ and selecting a random point on this circle. The iteration count iter modulo $2\pi$ should be random enough. This has no deeper meaning, it just serves to get away from $x$ without losing the scale of $x$.

$\endgroup$
  • $\begingroup$ This is very interesting, thanks! What is your recommendation then to avoid the zero in denominator? Do you perhaps know, what's with that polar(1+..., ...) from NR? Btw., from the pictures, Laguerre looks rather scary. However, I also tried Halley and, could be that I did something not exactly right, but Laguerre performed better as the pictures might suggest. Just saying... $\endgroup$ – prepaul Apr 24 '14 at 16:05
  • $\begingroup$ In all not completely symmetric situations Laguerre performs visually better. I do not know if there are other polynomials than the unit root ones that produce divergence in the Laguerre method. See the other pictures behind the link. $\endgroup$ – LutzL Apr 24 '14 at 16:09
  • $\begingroup$ Thanks, that answers my questions! Off topic: you seem to have a deep interest in polynomials and root finding. If we were talking about real roots only, what would be your favorite root finding method? Really any kind of method: Ostrowski, Halley, Laguerre, QR, VCA, Jenkins-Traub, ...? $\endgroup$ – prepaul Apr 24 '14 at 16:20
  • $\begingroup$ Real roots are complicated by the fact that two close roots can annihilate each other under small perturbations. To have constrol over that situation, you would need to also compute all complex roots with small imaginary part. I would rank Jenkins-Traub, then Laguerre and then Bairstow. But what really is important is to control the error of deflation, for instance by a robust treatment of clusters of roots, and that is rather independent of the method. $\endgroup$ – LutzL Apr 24 '14 at 18:11

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.