The equivalence of the constrained Rayleigh quotient and Newton methods for matrix polynomials expressed in different polynomial bases along with the confluent case

Abstract

We show that using the constrained Rayleigh quotient method to find the eigenvalues of matrix polynomials in different polynomial bases is equivalent to applying the Newton method to certain functions. We find those functions explicitly for a variety of polynomial bases including monomial, orthogonal, Newton, Lagrange and Bernstein bases. In order to do so, we provide explicit symbolic formulas for the right and left eigenvectors of the generalized companion matrix pencils for matrix polynomials expressed in those bases. Using the properties of the Newton basis, we also find two different formulas for the companion matrix pencil corresponding to the Hermite interpolation. We give pairs of explicit LU factors associated with these pencils. Additionally, we explicitly find the right and left eigenvectors for each of these pencils.

Keywords:

• matrix polynomials
• polynomial eigenvalues
• constrained Rayleigh quotient method
• Hermite interpolation
• block LU factoring

2010 AMS Subject Classifications :

• 65F15
• 15A22
• 11C20

Notes

For example, the monomial basis can be considered as a special case of the Newton basis with all nodes being zero and the value and the derivatives of the polynomial are given at zero.

Let Z _φ be the set of all zeros of . This set is necessarily finite. We will see that to apply the above procedure correctly, we will have to block pivot whenever x is in a small enough neighbourhood of any of these zeros. It follows from the work of Amiraslani 1 and Amiraslani et al. 2 that this can always be done.

means that the cost is O(n 2) for fixed s as (with a constant factor that includes s) and simultaneously the cost is O(s 3) for fixed n and . This shorthand should not cause confusion, as simultaneous limits and are not considered (e.g. see 30).