5
$\begingroup$

In eigenvalue characteristic equation computations of large matrices, it is often necessary to find all the the roots of this polynomial. I understand that there is no general explicit solution for irrational roots of polynomials of degree higher than 5. We might thus use numerical approximations, such as Newton's method, to find a root for the polynomial equation.

My question is, for very high degree polynomials, eg. characteristic equation of degree 100, how can we make systematic/algorithmic computation to find all the 100 roots to this polynomial? Is there a consistent method that will always find all the roots to this eigenvalue characteristic equation?

Thank you!

$\endgroup$
3
  • 5
    $\begingroup$ This is not an answer to your question about root-finding in general, but it's important to know that for numerical calculation of eigenvalues one should not use the characteristic polynomial. There are other methods that are much better. $\endgroup$
    – Hans Lundmark
    Nov 7, 2021 at 8:02
  • 3
    $\begingroup$ About polynomial roots in general, there are some starting pointers here. $\endgroup$
    – dxiv
    Nov 7, 2021 at 8:06
  • 1
    $\begingroup$ Tom Copeland has written an answer here: mathoverflow.net/a/368105/25104 See also square root of 2 in the OEIS: oeis.org/A002193 $\endgroup$
    – Mats Granvik
    Nov 7, 2021 at 9:12

1 Answer 1

Reset to default
6
$\begingroup$

There are numerical methods that will compute all roots of polynomials of high degree. Some are listed here.

But, actually, one of the best methods is to find the eigenvalues of the polynomial’s companion matrix. This is how the “roots” function in Matlab works, for example. There are many good numerical methods for computing eigenvalues, some of which are listed here. As you will see, some work by finding the roots of the characteristic polynomial, but many do not. The QR algorithm is a popular one.

So, in some sense, you’re looking at the problem backwards: you shouldn’t use polynomial root finding to compute eigenvalues (except maybe in linear algebra homework problems), you should use eigenvalue computations to find roots of polynomials.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .