Detecting a definite Hermitian pair and a hyperbolic or elliptic quadratic eigenvalue problem, and associated nearness problems.

*(English)*Zbl 1004.65045The paper concerns definite generalized eigenvalue problems and hyperbolic quadratic eigenvalue problems (QEPs) having the property that all eigenvalues are real. It also concerns elliptic QEPs which have eigenvalues that are all non-real. There are two aims: to determine for a given generalized eigenvalue problem or QEP, whether the property of interest holds, and, if it does, to compute the distance to the nearest problem without that property.

The second section, showing that the distance from a definite generalized eigenvalue problem to the nearest non-definite one is given by the Crawford number \[ \gamma(A,B)= \min_{\substack{ z\in \mathbb{C}^n\\ \|z\|_2=1}} \sqrt{(z^*Az)^2+ (z^*Bz)^2}, \] \(A,B\in \mathbb{C}^{n\times n}\) two Hermitian matrices, contains two methods for the computation of that number and for testing the definiteness. The first one, based on the bisection algorithm, detects definiteness and produces a bracket for \(\gamma(A,B)\), that shrinks to zero. The second one, more efficient and rapidly convergent is obtained by applying the level set algorithm derived for stability radii computations. The procedure enables us to test for definiteness and produces only a monotonically lower bound.

The third section contains definitions and characterizations of hyperbolic (including the subclass of overdamped QEPs) and elliptic QEPs. It shows that testing for hyperbolicity can be reduced to testing for definiteness of an associated generalized eigenvalue problem, which can be done using one of the algorithms presented above. It is proved that the distance from a hyperbolic (elliptic) problem to the nearest non-hyperbolic (non-elliptic) one, given by \[ \begin{split} d(A,B,C)= \min\{f(\Delta A,\Delta B,\Delta C): \text{det}(W(x, A+\Delta A, B+\Delta B,C+\Delta C))= 0,\\ \text{for some }x\neq 0\},\end{split} \] where \(f\) is some nonnegative function of the perturbation matrices \(\Delta A\), \(\Delta B\), \(\Delta C\), can be expressed in terms of a global minimization problem over the unit ball.

Finally, to illustrate the results, the paper presents three numerical examples each with a different type of QEPs: a damped mass-spring system which is real and overdamped, a moving wirsaw which is complex and hyperbolic but not overdamped and a wave equation which is real and elliptic.

The second section, showing that the distance from a definite generalized eigenvalue problem to the nearest non-definite one is given by the Crawford number \[ \gamma(A,B)= \min_{\substack{ z\in \mathbb{C}^n\\ \|z\|_2=1}} \sqrt{(z^*Az)^2+ (z^*Bz)^2}, \] \(A,B\in \mathbb{C}^{n\times n}\) two Hermitian matrices, contains two methods for the computation of that number and for testing the definiteness. The first one, based on the bisection algorithm, detects definiteness and produces a bracket for \(\gamma(A,B)\), that shrinks to zero. The second one, more efficient and rapidly convergent is obtained by applying the level set algorithm derived for stability radii computations. The procedure enables us to test for definiteness and produces only a monotonically lower bound.

The third section contains definitions and characterizations of hyperbolic (including the subclass of overdamped QEPs) and elliptic QEPs. It shows that testing for hyperbolicity can be reduced to testing for definiteness of an associated generalized eigenvalue problem, which can be done using one of the algorithms presented above. It is proved that the distance from a hyperbolic (elliptic) problem to the nearest non-hyperbolic (non-elliptic) one, given by \[ \begin{split} d(A,B,C)= \min\{f(\Delta A,\Delta B,\Delta C): \text{det}(W(x, A+\Delta A, B+\Delta B,C+\Delta C))= 0,\\ \text{for some }x\neq 0\},\end{split} \] where \(f\) is some nonnegative function of the perturbation matrices \(\Delta A\), \(\Delta B\), \(\Delta C\), can be expressed in terms of a global minimization problem over the unit ball.

Finally, to illustrate the results, the paper presents three numerical examples each with a different type of QEPs: a damped mass-spring system which is real and overdamped, a moving wirsaw which is complex and hyperbolic but not overdamped and a wave equation which is real and elliptic.

Reviewer: R.Militaru (Craiova)

##### Keywords:

definite Hermitian pair; definite generalized eigenvalue problems; hyperbolic quadratic eigenvalue problems; Crawford number; bisection algorithm; level set algorithm
PDF
BibTeX
XML
Cite

\textit{N. J. Higham} et al., Linear Algebra Appl. 351--352, 455--474 (2002; Zbl 1004.65045)

Full Text:
DOI

##### References:

[1] | Barkwell, L.; Lancaster, P., Overdamped and gyroscopic vibrating systems, Trans. AME: J. appl. mech., 59, 176-181, (1992) · Zbl 0756.70021 |

[2] | Byers, R., A bisection method for measuring the distance of a stable matrix to the unstable matrices, SIAM J. sci. statist. comput., 9, 5, 875-881, (1988) · Zbl 0658.65044 |

[3] | Cheng, S.H.; Higham, N.J., The nearest definite pair for the Hermitian generalized eigenvalue problem, Linear algebra appl., 302-303, 63-76, (1999) · Zbl 0947.65042 |

[4] | Crawford, C.R., ALGORITHM 646 PDFIND: A routine to find a positive definite linear combination of two real symmetric matrices, ACM trans. math. software, 12, 278-282, (1986) · Zbl 0613.65041 |

[5] | Crawford, C.R.; Moon, Y.S., Finding a positive definite linear combination of two Hermitian matrices, Linear algebra appl., 51, 37-48, (1983) · Zbl 0516.15021 |

[6] | Doyle, J., Analysis of feedback systems with structured uncertainties, IEE proc. D, 129, 6, 242-250, (1982) |

[7] | Duffin, R.J., A minimax theory for overdamped networks, J. rat. mech. anal., 4, 221-233, (1955) · Zbl 0068.20904 |

[8] | Duffin, R.J., The rayleigh – ritz method for dissipative or gyroscopic systems, Quart. appl. math., 18, 3, 215-221, (1960) · Zbl 0102.39103 |

[9] | M.K.H. Fan, An algorithm to compute the structured singular value, Technical Report TR-86-8, System Research Center, University of Maryland, 1986 |

[10] | Freitas, P.; Grinfield, M.; Knight, P., Stability of finite-dimensional systems with indefinite damping, Adv. math. sci. appl., 17, 1, 435-446, (1997) |

[11] | Genin, Y.; Van Dooren, P.M.; Vermaut, V., Convergence of the calculation of \(H∞\)-norms and related questions, (), 429-432 |

[12] | N.J. Higham, The Test Matrix Toolbox for MATLAB (version 3.0), Numerical Analysis Report No. 276, Manchester Centre for Computational Mathematics, Manchester, England, 1995 |

[13] | Kato, T., Perturbation theory for linear operators, (1976), Springer Berlin |

[14] | Lancaster, P., Lambda-matrices and vibrating systems, (1966), Pergamon Press Oxford · Zbl 0146.32003 |

[15] | Lancaster, P., Quadratic eigenvalue problems, Linear algebra appl., 150, 499-506, (1991) |

[16] | Markus, A.S., Introduction to the spectral theory of polynomial operator pencils, (1988), AMS Providence, RI · Zbl 0678.47005 |

[17] | Parlett, B.N., Symmetric matrix pencils, J. comp. appl. math., 38, 373-385, (1991) · Zbl 0772.15005 |

[18] | Sreedhar, J.; Dooren, P.V.; Tits, A.L., A fast algorithm to compute the real structured stability radius, (), 219-230 · Zbl 0872.93027 |

[19] | Stewart, G.W., Perturbation bounds for the definite generalized eigenvalue problem, Linear algebra appl., 23, 69-85, (1979) · Zbl 0407.15012 |

[20] | Stewart, G.W.; Sun, J., Matrix perturbation theory, (1990), Academic Press London |

[21] | Tisseur, F., Backward error and condition of polynomial eigenvalue problems, Linear algebra appl., 309, 339-361, (2000) · Zbl 0955.65027 |

[22] | Tisseur, F.; Meerbergen, K., The quadratic eigenvalue problem, SIAM rev., 43, 2, 235-286, (2001) · Zbl 0985.65028 |

[23] | Todd, M.J., Semidefinite optimization, Acta numerica, 10, 515-560, (2001) · Zbl 1105.65334 |

[24] | Veselić, K., A Jacobi eigenreduction algorithm for definite matrix pairs, Numer. math., 64, 241-269, (1993) · Zbl 0805.65038 |

[25] | Wei, S.; Kao, I., Vibration analysis of wire and frequency response in the modern wiresaw manufacturing process, J. sound vibration, 231, 5, 1383-1395, (2000) |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.