3
$\begingroup$

i am interested in finding roots of complex polynoms (with complex coefficients). i found that if the polynom has degenerate (multiple) root(s) then such algorithms like Newton and Durand-Kerner ones do not lead to the convergent results (simply speaking, the convergence is bad). does anyone in forum knows an algorithm to increase the accuracy (precision) of finding the degenerate roots (for the general case of complex polynoms) ? Thanks.

$\endgroup$
3
$\begingroup$

Hint: if $z_0$ is a root of order $k$ of $P$, then $z_0$ is a root of order $k-1$ of $P'$ (formal derivative). BTW, this is true in any field.

$\endgroup$
  • $\begingroup$ do you want to give an idea that removing degeneracy is made by P/P', and then to find the precise root of P/P' ? $\endgroup$ – R.Goldov Aug 30 '17 at 19:15
  • $\begingroup$ @R.Goldov, $P/\gcd(P,P')$, as Robert Israel said in the other answer. $P'$ can have other roots that aren't roots of $P$. $\endgroup$ – Martín-Blas Pérez Pinilla Aug 30 '17 at 19:35
  • $\begingroup$ Thank you, Martin-Blas. do you know an algorithm according which one could divide one polynom of degree n by another polynom of degree k (k<=n) ? i mean, not by hand but writing a computer code for that purpose. Thanks. $\endgroup$ – R.Goldov Aug 31 '17 at 13:00
  • $\begingroup$ @R.Goldov, see many examples in rosettacode.org/wiki/Polynomial_long_division. But the better option is using some symbolic calculus program. $\endgroup$ – Martín-Blas Pérez Pinilla Aug 31 '17 at 13:24
  • $\begingroup$ Thank you very much, Martin-Blas. $\endgroup$ – R.Goldov Sep 1 '17 at 13:54
2
$\begingroup$

Remove the degeneracy: if $f$ is your polynomial, find the roots of $f/\gcd(f,f')$ instead.

$\endgroup$
  • $\begingroup$ Of course, with finite precision, $f$ and $f'$ are doomed to appear as if coprime ... $\endgroup$ – Hagen von Eitzen Aug 30 '17 at 18:40
  • $\begingroup$ If the complex polynomial has large degree, for example, 100 or 1000, then it might be that there are several (many) multiple (degenerate) roots. how in that case to apply the method f/gcd(f,f') to remove degeneracy ? $\endgroup$ – R.Goldov Aug 30 '17 at 18:50
  • $\begingroup$ It still works. The roots of $f/\gcd(f,f')$ are exactly the roots of $f$ but with multiplicity $1$. Yes, this is assuming exact arithmetic rather than finite precision. With finite precision it is impossible to distinguish a multiple root from several roots close together. $\endgroup$ – Robert Israel Aug 30 '17 at 23:39
  • $\begingroup$ Thank you, Robert. as i guess, gcd(f,f') could be found according Euclidian algorithm ? or may be there are other algorithms for that purpose ? - i mean, how one could divide one polynom by another polynom if the degree of the polynoms is large (hundreds, thousands ...) - is there special computer algorithm for that purpose ? Thanks. $\endgroup$ – R.Goldov Aug 31 '17 at 13:05
  • $\begingroup$ Maple uses modular methods for gcd of polynomials over the rationals. See e.g. Monagan and Margot, "Computing Univariate GCD's over Number Fields" $\endgroup$ – Robert Israel Sep 1 '17 at 3:18
1
$\begingroup$

At multiple roots, the steps or Newton and Durand-Kerner (which is also a Newton method) from one iteration to the next are almost co-linear. This can be used to detect this situation and to extrapolate the root. Of course in the complex plane and for iterations that are not constrained to the real axis, else the property "co-linear" is not very descriptive.

In Durand-Kerner you can also detect clusters in the current root approximations and set one of the cluster points to the center of the cluster. This was reported to increase convergence speed, if I remember correctly Victor Pan has many papers and tech-reports on polynomial root finding, its efficiency and accuracy.

Jenkins-Traub is theoretically in its convergence speed insensitive to multiplicities. However, it too suffers from the usual cancellation errors at multiple roots as it uses the quotient of polynomial value and something that converges to the derivative, which will eventually both be small numbers.

$\endgroup$

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.