0

I searched for a root finding algorithm and found QR decomposition with Companion matrix which was promising but I found a couple equations where this method didn't work.

These for example won't be solved:$$ x^4 - 10x^2 + 9, \quad x^3 - 5x^2 - 4x + 20. $$

Is it possible to modify the algorithm so that such cases can be solved? If one you reading this knows if this is possible or another algorithm that could be implemented, I hope you will be so kind and give some form of an answer.

Ѕᴀᴀᴅ
  • 34,263
FROST SKIPPER
  • 1
  • What do you mean with won't be solved? Using my own QR routine with balanc from Numerical Recipes and HQR from Eispack, I get the roots $-3,-1,1,3$ for your first polynomial (imaginary parts are all zero). – gammatester Feb 03 '18 at 14:48
  • The Jenkins-Traub algorithm works well enough for polynomials up to about degree 20. The algorithm deflates the polynomial as it finds each linear or quadratic factor. So even though it tries to find the smallest modulus roots first, after deflating 20 times, you run into numerical accuracy problems. I have recollection that the algorithm is equivalent to generalized Rayleigh iteration. – Andy Walls Feb 03 '18 at 15:00
  • gammamaster, did it also solve the second polynomial? I used the C++ code found from https://rosettacode.org/wiki/QR_decomposition#C.2B.2B Neither of those two get solved. – FROST SKIPPER Feb 04 '18 at 10:28
  • Yes, the roots are $-2,2,5$. The Rosetta code computes the QR decomposition for a general matrix, and will not exploit the special structure of the companion matrix. My (ported Eispack) routines compute the eigenvalues of a real upper Hessenberg matrix by the QR method. Here the Eispack links: http://www.netlib.org/eispack/hqr.f and http://www.netlib.org/eispack/balanc.f. See also https://en.wikipedia.org/wiki/QR_algorithm – gammatester Feb 04 '18 at 10:55

0 Answers0