0
$\begingroup$

The roots of polynomial with real coefficients $$p(x)=x^n+c_{n-1}x^{n-1}+ \dots+c_1x+c_0 $$ equal the eigenvalues of the companion matrix: $$ \begin{bmatrix} 0&1&0& \dots & 0\\ 0&0&1& \dots & 0\\ & \vdots & & \ddots &\\ -p_0&-p_1&-p_2& \dots & -p_{n-1}\\ \end{bmatrix} $$ I programed it and it works perfectly. Sometimes there are two identical eigenvalues which should be the real component of two complex conjugated roots, I guess. (This method is said to be the default solver in MATLAB, but I programed it in Java.)

So it seems that ‘finding real roots of polynomial equations’ is ultimately done, but why there are some many mathematicians still working on it, for example: Efficient polynomial root-refiners (McNamee, 2012) or Inverse power and Durand-Kerner iterations for univariate polynomial root-finding (Bini 2004).

To be specific, the celebrated rank-one companion matrix (also appears in the aforementioned paper) has no advantage over the original Frobenius companion matrix, so far I understand.

Again, many papers focus on roots isolation by Vincent's theorem. However, roots isolation seems unnecessary at all if the companion matrix directly gives the roots.

Besides, I am confused when people talking about 'approximate' the roots even then using the companion matrix. In my opinion, the companion matrix gives exact roots though a compute is subject to limited precision. "Numerical approximation of roots of polynomials in one unknown is easily done on a computer by the Jenkins–Traub method, Laguerre's method, Durand–Kerner method, or by some other root-finding algorithm" sounds like a big myth.

Probably I miss some important points?

$\endgroup$
  • 3
    $\begingroup$ How exactly do you find the eigenvalues of the matrix without computing its characteristic polynomial and finding the zeroes of the polynomial? $\endgroup$ – DanielWainfleet Dec 30 '15 at 11:17
  • $\begingroup$ You can't find eigenvalues of a matrix exactly without exactly solving its characteristic polynomial. However, there are many numerical methods for computing (approximations to) eigenvalues of a matrix, which do not rely on characteristic polynomial, and thus can be used to approximate its roots as well $\endgroup$ – Yuriy S Jun 27 '16 at 21:10
  • $\begingroup$ See also en.wikipedia.org/wiki/Eigenvalue_algorithm $\endgroup$ – Yuriy S Jun 27 '16 at 21:11
  • 1
    $\begingroup$ "I miss some important points?" - yes, a lot of them. Mostly, Abel and Galois already showed that one cannot in general have radical representations of roots of polynomials of degree higher than 5, so that root-finding algorithms are inherently iterative. (As for lower degrees, you have to use radicals, which are also computed by a computer with an iterative algorithm like Newton-Raphson anyway. :P ) In any event, the literature is vast because there are, well, many ways to skin a cat, but not all of them are the best in all situations. $\endgroup$ – J. M. is a poor mathematician Apr 13 at 6:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.