Higher Order Polynomial Eigenvalue Problems

Some applications lead to a higher order polynomial eigenvalue problem (PEP)

$$\Psi(\lambda) x = 0 \quad \mbox{and} \quad y^{\ast} \Psi(\lambda) = 0,$$ (268)

where $\Psi(\lambda)$ is a matrix polynomial defined as

$$\Psi(\lambda) \equiv \lambda^\ell C_\ell + \lambda^{\ell -1} C_{\ell -1} + \cdots + \lambda C_1 + C_0,$$

in which the $C_j$ are square $n$ by $n$ matrices. A thorough study of the mathematical properties of matrix polynomials can be found in [194].

In order to make the eigenvalue problem well defined, these matrices have to satisfy certain properties; in particular $C_\ell$ should be nonsingular. Similar to the quadratic problem, these problems can also be linearized to

$$A z = \lambda B z,$$

where

$$A \equiv \left[ \begin{array}{ccccc} 0 & I & 0 & \cdots & 0 ... ...& \\ & & & I & \\ & & & & C_\ell \\ \end{array} \right] .$$

The relation between $x$ and $z$ is given by $z=(x^T,\lambda x^T,\ldots,\lambda^{\ell-1}x^T)^T$. $B^{-1}A$ is a block companion matrix of the PEP. The generalized eigenproblem $Az=\lambda Bz$ can be solved with one of the methods discussed in Chapter 8. A disadvantage of this approach is that one has to work with larger matrices of order $n\times \ell$, and these matrices also have $n\times \ell$ eigenpairs, of course. This implies that one has to check which of the computed eigenpairs satisfies the original polynomial equation. Ruhe [372] (see also Davis [102]) discussed methods that directly handle the problem (9.24), for instance, with Newton's method. For larger values of $n$ one may expect all sorts of problems with the convergence of these techniques. In §9.2.5, we have discussed a method that can be used to attack problems with large $n$. In that approach, one first projects the given problem (9.24) onto a low-dimensional subspace and obtains a similar problem of low dimension. This low-dimensional polynomial eigenproblem can then be solved with one of the approaches mentioned above. In [221] a fourth-order polynomial problem has been solved successfully, using this reduction technique.