1 Introduction

In this paper, we consider the polynomial eigenvalue problem (PEP)

$$\begin{aligned} P(\lambda )x=0, \end{aligned}$$
(1)

where \(P(\lambda ) = \lambda ^d A_0 + \lambda ^{d - 1} A_{1} + \cdots + \lambda A_{d-1} + A_d \), \(A_k \in C^{n \times n} \), \(0 \le k \le m\). \(\lambda \) and x, known as the eigenvalue and the corresponding eigenvector, respectively, are the variables to be determined. The problem is very general and includes the standard eigenvalue problem \(P(\lambda )=\lambda I-A\) (see, e.g., Wilkinson 1965), the generalized eigenvalue problem \(P(\lambda )=\lambda A-B\) (see, e.g., Dai et al. 2015), the quadratic eigenvalue problem \(P(\lambda )=\lambda ^2 A+\lambda B+C\) (see, e.g., Tisseur and Meerbergen 2001) and the cubic eigenvalue problem \(P(\lambda )=\lambda ^3 A_0+\lambda ^2 A_1+\lambda A_2+A_3\) (see, e.g., Hwang et al. 2005).

The PEP arises in a number of various applications, and has received considerable attention in the last few decades. For example, it is ubiquitous in a wide range of problems, such as vibration analysis of viscoelastic systems (Adhikari and Pascual 2009), structural dynamic analysis (Gupta 1976), stability analysis of control systems (Higham and Tisseur 2002), numerical simulation of quantum dots (Hwang et al. 2004) and so on. Considerable efforts have been devoted to the polynomial eigenvalue problem in the literature. Gohberg et al. (1982) developed the mathematical theory concerning matrix polynomials. Gohberg et al. (1979), Dedieu and Tisseur (2003), Higham and Tisseur (2003) and Chu (2003) gave the perturbation theory for the polynomial eigenvalue problem. Higham et al. (2007), Tisseur (2000) and Lawrence and Corless (2015) analyzed backward error of the polynomial eigenvalue problem.

The classical approach for solving the PEP is linearizing the problem (1) to produce an equivalent larger generalized eigenvalue problem (see, e.g., Gohberg et al. 1982; Higham et al. 2006; Mackey et al. 2006a, b), solved by any appropriate eigensolver. However, the linearization technique will enlarge the size of the original problem, and matrix structures and spectral properties of the problem (1) will not be preserved, and most of all, the linearized eigenvalue problem is more ill-conditioned (Tisseur 2000). In the last few years, lots of researchers have developed numerical methods that work directly with the original data of the polynomial eigenvalue problem for avoiding the above disadvantages. In these methods, the polynomial eigenvalue problem is projected onto a properly chosen low-dimensional subspace to obtain a new polynomial eigenvalue problem with matrix dimension of low order. Then, the reduced polynomial eigenvalue problem can be solved by the linearization method. These methods include Jacobi–Davidson method (Bai and Miao 2017a, b; Hwang et al. 2010; Sleijpen et al. 1996) and Krylov-type subspace method (Hoffnung et al. 2006). Jacobi–Davidson method targets at one eigenvalue at one time with local convergence. However, if the desired eigenvalues of the problem (1) form a cluster of nearby eigenvalues, then Jacobi–Davidson method has difficulties in detecting and resolving such a cluster.

Actually, recent focus in practical engineering, such as stability analysis of control systems, is how to compute all eigenvalues of the PEP in an open half plane, especially in the open right half plane. Besides, it is well known that a real symmetric or Hermitian matrix polynomial has a spectrum that is symmetric with respect to the real axis. Therefore, for the above matrix polynomials, we just need compute all eigenvalues in the open upper half plane instead of all eigenvalues of original matrix polynomial in the whole plane. Overall, a numerical method for computing all eigenvalues of the PEP (1) in an open half plane would be of particular interest.

The organization of the paper is as follows. In Sect. 2, we give a brief description of the linear fractional mapping. Through this mapping, the problem to find all eigenvalues of a PEP in the open half plane can be converted into a new PEP to find all eigenvalues in the open unit disk. Besides, we present the relation of the eigenvalues for the above eigenproblems. In Sect. 3, we introduce the contour integral method to compute all eigenvalues in the open unit disk. In Sect. 4, a novel algorithm to find all eigenvalues of the PEP in an open half plane is derived. Section 5 is devoted to some numerical experiments.

For convenience, we use the following notations: I denotes the identity matrix with suitable dimensions; \(\mathrm{tr}(A)\) and \(\mathrm{det}(A)\) denote the trace and the determinant of a matrix A, respectively; \(\mathrm{Re}(\lambda )\) and \(\mathrm{Im}(\lambda )\) denote the real part and imaginary part of a complex number \(\lambda \), respectively; i denotes the imaginary unit.

2 Linear fractional transformation

To compute all eigenvalues of the PEP (1) in the open half plane, we first introduce the linear fractional transformation (Rudin 1987).

Definition 1

If \(a_1,a_2, a_3\) and \(a_4\) are complex numbers and \(a_{1}a_{4} - a_{2}a_{3} \ne 0\) such that \(\varphi (\lambda ):\lambda \rightarrow \omega \) where \(\omega =\frac{{a_{1}\lambda + a_{2}}}{{a_{3}\lambda + a_{4}}}\), the mapping \(\varphi (\lambda )\) is called a linear fractional transformation.

For the above transformation, every open half plane can be conformally mapped onto an open disk.

Next, we take the linear fractional mapping \(\omega = \frac{{\lambda - 1}}{{\lambda + 1}}\), for example. The following result characterizes the relationship between all eigenvalues of some polynomial eigenproblem in one open half plane and all eigenvalues of another corresponding eigenproblem in the open unit disk.

Theorem 2

For a linear fractional transformation \(\omega = \frac{{\lambda - 1}}{{\lambda + 1}}\), the problem to find all eigenvalues of some polynomial eigenproblem \(P(\lambda )x = 0\) (1) in the open right half plane (\(Re (\lambda ) > 0\)) can be converted into a new problem to find all eigenvalues of another eigenproblem \(B(\omega )x = 0\) in the open unit disk, where \(B(w) = {(w + 1)^d}{A_d} + {(w + 1)^{d - 1}}(1 - w){A_{d - 1}} + \cdots + (w + 1){(1 - w)^{d - 1}}{A_1} + {(1 - w)^d}{A_0}\). Besides, the corresponding eigenvalues of the above two eigenproblems follow the equality \(\lambda = \frac{{\omega + 1}}{{1 - \omega }}\).

Proof

Substitute \(\lambda = \frac{{\omega + 1}}{{1 - \omega }}\) into \(P(\lambda )x = 0\), then the conclusion holds clearly since \(\omega \) is a conformal one-to-one mapping.\(\square \)

Motivated by the above idea, we can also find all eigenvalues of a PEP in the open upper half plane, in the open left half plane or in the open lower half plane. For simplicity, the corresponding result of finding all eigenvalues of a PEP \(P(\lambda )x = 0\) in the open upper half plane is shown as follows.

Theorem 3

For a linear fractional transformation \(\omega = \frac{{\lambda - i}}{{\lambda + i}}\), the problem to find all eigenvalues of \(P(\lambda )x = 0\) (1) in the open upper half plane (\(Im(\lambda ) > 0 \)) can be converted into a new problem to find all eigenvalues of \(B(\omega )x = 0\) in the open unit disk, and the corresponding eigenvalues follow the equality \(\lambda = \frac{{\omega + 1}}{{1 - \omega }}i\).

Proof

The proof is similar to that of Theorem 2. Hence, it is omitted. \(\square \)

3 Computing all eigenvalues of a PEP in the open unit disk

In this section, we will briefly present the algorithm to compute all eigenvalues of a PEP (1) in the open unit disk, see Asakura et al. (2010) for details.

For a PEP (1), we define a function \(f(\lambda ) = \mathrm{det} (P(\lambda ))\), then \(f(\lambda )\) is an analytical function in \(\lambda \). As we know, \(\lambda \) is an eigenvalue of a PEP (1) if and only if \(f(\lambda ) = 0\).

Let \(\varGamma \) be the boundary of an open unit disk for the PEP (1). The center and radius of the open unit disk are denoted as \(\gamma \) and \(\rho \), respectively. Let \(m \ (m \le n)\) be a positive integer and the complex moment \(u_p\) be

$$\begin{aligned} u_p = \frac{1}{{2\pi i}}\oint _\varGamma {(\lambda - \gamma )} ^p \frac{{f'(\lambda )}}{{f(\lambda )}}\mathrm{d}z, \end{aligned}$$

where \(p = 0,1, \ldots , 2m - 1\).

Using these complex moments \(u_p\), we define the following two \(m \times m\) Hankel matrices

$$\begin{aligned} H_m = \left( {\begin{array}{cccc} {u_0 } &{}\quad {u_1 } &{}\quad \cdots &{}\quad {u_{m - 1} } \\ {u_1 } &{} \quad {u_2 } &{} \quad \cdots &{}\quad {u_m } \\ \vdots &{}\quad \vdots &{}\quad {} &{}\quad \vdots \\ {u_{m - 1} } &{}\quad {u_m } &{}\quad \cdots &{}\quad {u_{2m - 2} } \\ \end{array} } \right) \end{aligned}$$

and

$$\begin{aligned} H_{_m }^ < = \left( {\begin{array}{cccc} {u_1 } &{}\quad {u_2 } &{}\quad \cdots &{}\quad {u_m } \\ {u_2 } &{}\quad {u_3 } &{} \quad \cdots &{}\quad {u_{m + 1} } \\ \vdots &{} \quad \vdots &{}\quad {} &{} \quad \vdots \\ {u_m } &{} \quad {u_{m + 1} } &{} \quad \cdots &{}\quad {u_{2m - 1} } \\ \end{array} } \right) . \end{aligned}$$

Now, we consider that the integration is evaluated via a trapezoidal rule on the circle \(\varGamma \). Let N be the number of sample points on the circle \(\varGamma \) and \(\nu _j = \gamma + \rho \exp (2\pi j i/N) (j = 0, 1, \ldots , N - 1)\). According to the trapezoidal rule, the complex moments \(u_p\) can be approximately obtained by the following formula

$$\begin{aligned} u_p \approx \widehat{u}_p = \frac{1}{N}\sum \limits _{j = 0}^{N - 1} {(\nu _j - \gamma )} ^{p + 1} \frac{{f^{\prime } (\nu _j )}}{{f(\nu _j )}}. \end{aligned}$$

Based on the Trace-Theorem of Devidenko (see Davidenko 1960) \(\frac{{f^{\prime } (\lambda )}}{{f(\lambda )}} = \mathrm{tr}(T^{ - 1} (\lambda )T^{\prime } (\lambda ))\), \(\widehat{u}_p\) can be rewritten as

$$\begin{aligned} \widehat{u}_p= \frac{1}{N}\sum \limits _{j = 0}^{N - 1} {(\nu _j - \gamma )} ^{p + 1} \mathrm{tr}\left( T^{ - 1} (\nu _j )T^{\prime } (\nu _j )\right) . \end{aligned}$$
(2)

Using \(\widehat{u}_p \ (p=0, 1, \ldots , 2m - 1)\), we form the following two Hankel matrices \(\widehat{H}_m^<\) and \(\widehat{H}_m\)

$$\begin{aligned} {H_m } \approx \widehat{H}_m = \left( {\begin{array}{cccc} {\widehat{u}_0 } &{}\quad {\widehat{u}_1 } &{}\quad \cdots &{}\quad {\widehat{u}_{m - 1} } \\ {\widehat{u}_1 } &{}\quad {\widehat{u}_2 } &{}\quad \cdots &{}\quad {\widehat{u}_m } \\ \vdots &{}\quad \vdots &{}\quad {} &{}\quad \vdots \\ {\widehat{u}_{m - 1} } &{}\quad {\widehat{u}_m } &{} \quad \cdots &{}\quad {\widehat{u}_{2m- 2} }\\ \end{array} } \right) \end{aligned}$$
(3)

and

$$\begin{aligned} H_m^< \approx \widehat{H}_m^ < = \left( {\begin{array}{cccc} {\widehat{u}_1 } &{} \quad {\widehat{u}_2 } &{}\quad \cdots &{}\quad {\widehat{u}_m } \\ {\widehat{u}_2 } &{}\quad {\widehat{u}_3 } &{}\quad \cdots &{} \quad {\widehat{u}_{m + 1} } \\ \vdots &{} \quad \vdots &{}\quad {} &{} \quad \vdots \\ {\widehat{u}_m } &{}\quad {\widehat{u}_{m + 1} } &{}\quad \cdots &{} \quad {\widehat{u}_{2m - 1} } \\ \end{array} } \right) . \end{aligned}$$
(4)

The numerical algorithm to compute all eigenvalues of the PEP (1) in the open unit disk can be described as follows.

figure a

Remark 3.1

The low order \(\widehat{H}_m^ < - \lambda \widehat{H}_m\) may be solved by the QZ method (Moler and Stewart 1973).

According to the Theorem 3.5 in Asakura et al. (2010), the eigenvalues \(\lambda _k \ (k= 1, 2, \ldots , m)\) of \(\widehat{H}_m^< x = \lambda \widehat{H}_m x\) are the eigenvalues of the PEP (1) in the circle \(\varGamma \).

4 Computing all eigenvalues of a PEP in an open half plane

For the linear fractional transformation

$$\begin{aligned} \omega = \frac{{\lambda - 1}}{{\lambda + 1}}, \end{aligned}$$
(5)

substitute (5) into \(P(\lambda )x = 0\), then it follows that

$$\begin{aligned} B(w)= & {} {(w + 1)^d}{A_d} + {(w + 1)^{d - 1}}(1 - w){A_{d - 1}} + \cdots + (w + 1){(1 - w)^{d - 1}}{A_1} \\&+ {(1 - w)^d}{A_0}. \end{aligned}$$

Next use Algorithm 1 to compute all eigenvalues \(\omega _k\) of \(B(\omega )x = 0\) in the open unit disk, and then substitute \(\omega _k\) into \(\lambda = \frac{{\omega + 1}}{{1 - \omega }}\). Thus, we compute all eigenvalues \(\lambda _k \) of original eigenvalue problem in the open right half plane according to Theorem 1.

From the above results and notations, we can derive the following algorithm to find all eigenvalues of the PEP in the open right half plane.

figure b

Similarly, we can also get the algorithm to find all eigenvalues of a polynomial eigenvalue problem in the open upper half plane.

figure c

5 Numerical examples

In this section, we report some numerical examples to show the effectiveness of the proposed algorithms. All computations are carried out in Matlab (2012b). In our examples, \(\lambda _{k}^{*}\) and \(\lambda _k\) are the kth exact eigenvalue and the kth approximate eigenvalue of the PEP (1), respectively. All eigenvalues \(\lambda _k\) are rounded to 10 decimal places in Tables 1, 2, 3 and 4.

Example 1

Consider the generalized eigenvalue problem with

$$\begin{aligned} P\left( \lambda \right) x = \left( {\lambda A_0 + A_1 } \right) x = 0, \end{aligned}$$

where \(A_1 = \left( {\begin{array}{*{20}ccccccc} 1 &{}\quad 1 &{}\quad 0 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \\ 0 &{} \quad 3 &{} \quad 1 &{}\quad 0 &{}\quad 0 &{}\quad \cdots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad - 1&{} \quad 1 &{}\quad 0 &{} \quad \cdots &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 &{}\quad - 2 &{}\quad \ddots &{}\quad \ddots &{}\quad \vdots \\ \vdots &{}\quad \vdots &{}\quad \ddots &{}\quad \ddots &{}\quad \ddots &{}\quad \ddots &{}\quad 0 \\ 0 &{} \quad \cdots &{}\quad \cdots &{} \quad \ddots &{}\quad 0 &{}\quad - 97 &{}\quad 1 \\ 0 &{} \quad \cdots &{} \quad \cdots &{} \quad \cdots &{}\quad 0 &{} \quad 0 &{}\quad 4 \\ \end{array} } \right) \) and \(A_0 = I \in C^{100 \times 100} \).

Table 1 Numerical results in Example 1
Full size table
Table 2 Numerical results in Example 2
Full size table

It is easy to verify that all eigenvalues \(\lambda _k^{*}\) of this question in the right half plane are 1, 3 and 4.

The numerical results are obtained with the parameters \(N=2000\), \(\gamma =0\) and \(\rho =1\). The eigenvalues \(\lambda _k\) computed by Algorithm 2 are given in Table 1. It shows that the numerical results are very close to the exact eigenvalues.

Example 2

In this example we consider the quadratic eigenvalue problem with

$$\begin{aligned} P(\lambda )x = \left( {\left( {\begin{array}{cc} 0 &{}\quad 1 \\ { - 2} &{}\quad 3 \\ \end{array} } \right) + \lambda \left( {\begin{array}{cc} 7 &{} \quad { - 5} \\ {10} &{} \quad { - 8} \\ \end{array} } \right) + \lambda ^2 \left( {\begin{array}{cc} 1 &{}\quad 0 \\ 0 &{}\quad 1 \\ \end{array} } \right) } \right) x = 0. \end{aligned}$$

We can verify that all eigenvalues \(\lambda _k^{*}\) of \(P(\lambda )x=0\) in the open right half plane are 1 and 2.

The numerical results for Algorithm 2 with the parameters \(N=20\), \(\gamma =0\) and \(\rho =1\) are shown in Table 2. From Table 2, the numerical results are in good agreement with the exact eigenvalues.

Example 3

We consider the polynomial eigenvalue problem with

$$\begin{aligned} P\left( \lambda \right) x = \left( {\lambda ^3 A_0 + \lambda ^2 A_1 + \lambda A_2 + A_3} \right) x = 0 , \end{aligned}$$

where \(A_3 = \left( {\begin{array}{ccc} - 16 &{}\quad - 4 &{} \quad 7 \\ - 14 &{}\quad 7 &{}\quad {13} \\ 6 &{}\quad 8 &{}\quad 7 \\ \end{array} } \right) , \ A_2 = \left( {\begin{array}{ccc} 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{} \quad 0 \\ \end{array} } \right) \), \(A_1 = \left( {\begin{array}{ccc} 2 &{}\quad - 6 &{}\quad 1 \\ - 2 &{}\quad {22} &{}\quad {11} \\ 7 &{}\quad - 1 &{}\quad 1 \\ \end{array} } \right) \) and \(A_0 = \left( {\begin{array}{ccc} - 4 &{}\quad 3 &{}\quad {12} \\ - 17 &{}\quad - 11 &{}\quad 0 \\ 1 &{}\quad - 1 &{}\quad 3 \\ \end{array} } \right) \).

It is easy to verify that all eigenvalues \(\lambda _k^{*}\) of this question in the right half plane are 2.02268890, \(0.43730530 + 0.92713871i, 0.43730530 - 0.92713871i, 0.02570243 + 0.47013943i, 0.02570243 - 0.47013943i\).

The numerical results are obtained with the parameters \(N=1000\), \(\gamma =0\) and \(\rho =1\). The computed eigenvalues \(\lambda _k\) are given in Table 3. It is clearly seen from Table 3 that the numerical results obtained by Algorithm 2 are very close to the exact eigenvalues.

Table 3 Numerical results in Example 3
Full size table
Table 4 Numerical results in Example 4
Full size table

Example 4

We consider another polynomial eigenvalue problem with

$$\begin{aligned} P(\lambda )x = \left( \lambda ^4 A_0 + \lambda ^3 A_1 + \lambda ^2 A_2 + \lambda A_3 + A_4\right) x = 0, \end{aligned}$$

where \(A_4 = \left( {\begin{array}{*{20}c} - 2 &{}\quad 4 &{}\quad {11} \\ - 5 &{}\quad 7 &{}\quad 8 \\ 6 &{}\quad 8 &{}\quad 9 \\ \end{array} } \right) \), \(A_3 = \left( {\begin{array}{*{20}c} 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{} \quad 0 \\ 0 &{}\quad 0 &{}\quad 0 \\ \end{array} } \right) \), \(A_2 = \left( {\begin{array}{*{20}c} 0 &{}\quad 5 &{}\quad 0 \\ 0 &{}\quad 4 &{}\quad 0 \\ 0 &{}\quad 3 &{}\quad 0 \\ \end{array} } \right) \), \(A_1 = \left( {\begin{array}{*{20}c} 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 \\ 0 &{}\quad 0 &{}\quad 0 \\ \end{array} } \right) \) and \(A_0 = \left( {\begin{array}{*{20}c} 6 &{}\quad - 6 &{}\quad 1 \\ - 2 &{}\quad {22} &{}\quad {10} \\ 7 &{}\quad - 1 &{}\quad 3 \\ \end{array} } \right) \).

It is not difficult to verify that all eigenvalues \(\lambda _k^{*}\) in the open upper half plane are \(1.49288447 + 1.20682087i, 0.76712559 + 0.72679201i, 0.57153817 + 0.61343591i, -0.57153817 + 0.61343591i, -0.76712559 + 0.72679201i, -1.49288447 + 1.20682087i\).

The numerical results for Algorithm 3 are given in Table 4 using the parameters \(N=1000\), \(\gamma =0\) and \(\rho =1\). From Table 4, we observe that the numerical results coincide with the exact eigenvalues.

6 Conclusion

In this paper, we have presented a novel method to compute all eigenvalues of the PEP in an open half plane. This approach first transforms the original PEP into a new PEP via a linear fractional transformation, then employs the contour integral method to compute all eigenvalues of the new PEP in the open unit disk, and substitute the above eigenvalues into the linear fractional transformation to find all eigenvalues of original eigenproblem lastly. Our numerical results show that the proposed method is very useful and effective for computing all eigenvalues of the PEP in an open half plane.