New version page

Numerische Mathematik

Upgrade to remove ads

This preview shows page 1-2-14-15-29-30 out of 30 pages.

Save
View Full Document
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 30 pages.
Access to all documents
Download any document
Ad free experience

Upgrade to remove ads
Unformatted text preview:

Numer. Math. (1998) 78: 329–358NumerischeMathematikc Springer-Verlag 1998Electronic EditionA numerically stable, structure preserving methodfor computing the eigenvalues of real Hamiltonianor symplectic pencilsPeter Benner1,?, Volker Mehrmann2,?, Hongguo Xu3,??1Zentrum f¨ur Technomath, Fb 3 – Mathematik und Informatik, Universit¨at Bremen,Postfach 330 440, D-28334 Bremen, Germany; e-mail: [email protected]¨at f¨ur Mathematik, TU Chemnitz, D-09107 Chemnitz, Germany;e-mail: [email protected] of Mathematics, Fudan University, Shanghai, 200433, PR ChinaReceived April 8, 1996 / Revised version received December 20, 1996Summary. A new method is presented for the numerical computation of thegeneralized eigenvalues of real Hamiltonian or symplectic pencils and matrices.The method is numerically backward stable and preserves the structure (i.e.,Hamiltonian or symplectic). In the case of a Hamiltonian matrix the method isclosely related to the square reduced method of Van Loan, but in contrast to thatmethod which may suffer from a loss of accuracy of order√ε, where ε is themachine precision, the new method computes the eigenvalues to full possibleaccuracy.Mathematics Subject Classification (1991): 65F151. IntroductionThe eigenproblem for Hamiltonian and symplectic matrices has received a lotof attention in the last 25 years, since the landmark papers of Laub [13] andPaige/Van Loan [20]. The reason for this is the importance of this problem inmany applications in control theory and signal processing, [17, 12] and alsodue to the fact that the construction of a completely satisfactory method is stillan open problem. Such a method should be numerically backward stable, havea complexity of O(n3) or less and at the same time preserve the Hamiltonianor symplectic structure. Many attempts have been made to tackle this problem,?These authors were supported by Deutsche Forschungsgemeinschaft, Research Grant Me 790/7–1??Current address: Fakult¨at f¨ur Mathematik, TU Chemnitz, D-09107 Chemnitz, GermanyResearch supported by Alexander von Humboldt Foundation and Chinese National Natural ScienceFoundationNumerische Mathematik Electronic Editionpage 329 of Numer. Math. (1998) 78: 329–358330 P. Benner et al.see [8, 15, 17] and the references therein, but it has been shown in [1] thata modification of standard QR-like methods to solve this problem is in generalhopeless, due to the missing reduction to a Hessenberg–like form. For this reasonother methods like the multishift-method of [2] were developed that do not followthe direct line of a standard QR-like method. The structure of the multishiftmethod is at first a computation of the eigenvalues followed by a sequence ofexact-shift steps of a QR method that is based on the non-Hessenberg reduction ofPaige and Van Loan [20]. The method is backward stable and structure preservingbut it may suffer from loss of convergence, in particular for large problems andfurthermore it needs good approximations for the eigenvalues first. These canfor example be obtained via the square-reduced method of Van Loan [25]. In thesymplectic case a similar method has been proposed by Lin [16] and improvedby Patel [21]. Both methods are structure preserving and backward stable for amodified problem which involves the square of the original matrix. But squaringa matrix, computing the eigenvalues of the square, and taking square roots toobtain the eigenvalues of the original matrix can lead to a loss of half of thepossible accuracy. This was shown by the worst-case error analysis in [25].In this paper we will present a new method which does not suffer from thisloss of accuracy and it is constructed in such a way that the same method canbe used for Hamiltonian matrices, symplectic matrices, Hamiltonian pencils, orsymplectic pencils. The method is structure preserving, backward stable, andneeds O(n3) floating point operations. There are three main ingredients for thisnew method, a new matrix decomposition, which can be viewed as a symplecticURV decomposition, a periodic Schur decomposition for a product of two or fourmatrices [6, 10, 11] and the generalized Cayley transformation which allows aunified treatment of Hamiltonian and symplectic problems, [14, 18].The paper is organized as follows: In Sect. 2 we introduce the notation andreview some basic results. In Sect. 3 we develop the theoretical basis for the newalgorithm and in Sect. 4 we then describe the new procedure. An error analysisis given in Sect. 5 and numerical examples are presented in Sect. 6.2. Notation and preliminariesIn this section we introduce some notation, important definitions and also somepreliminary results.We will be concerned with the computation of eigenvalues of special matricesand matrix pencils. To simplify the notation we use in the following the expres-sion eigenvalue for eigenvalues of matrices and also for pairs (α, β) /=(0,0) forwhich the determinant of a matrix pencil αE −βA vanishes. These pairs are notunique, since they can be scaled by a nonzero factor and still the determinantvanishes. So if β/= 0 then we identify (α, β) with (αβ, 1) or λ =αβ. Pairs (α, 0)with α/= 0 are called infinite eigenvalues.We now introduce the classes of matrices and matrix pencils that are discussedin this paper.Numerische Mathematik Electronic Editionpage 330 of Numer. Math. (1998) 78: 329–358Eigenvalues of real Hamiltonian or symplectic pencils 331Definition 2.1 Let J :=0 In−In0, where Inis the n × n identity matrix.a) A pencil αEH− βAH∈ R2n×2nis called Hamiltonian iff EHJATH= −AHJETH.The set of Hamiltonian pencils in R2n×2nis denoted by Hp2n.b) A matrix H ∈ R2n×2nis called Hamiltonian iff (HJ )T= HJ . The Lie Algebraof Hamiltonian matrices in R2n×2nis denoted by H2n.c) A matrix T ∈ R2n×2nis called skew-Hamiltonian iff (TJ )T= −TJ . The set ofskew-Hamiltonian matrices in R2n×2nis denoted by SH2n.d) A pencil αES−βAS∈ R2n,2nis called symplectic iff ESJETS= ASJATS. The setof symplectic pencils in R2n×2nis denoted by Sp2n.e) A matrix S ∈ R2n×2nis called symplectic iff SJST= J. The Lie group ofsymplectic matrices in R2n×2nis denoted by S2n.f) A matrix U ∈ R2n×2nis called orthogonal symplectic iff UJUT= J andUUT= I2n. The Lie group of orthogonal symplectic matrices in R2n×2nis denotedby US2n.In this paper we will mainly discuss regular Hamiltonian and symplecticpencils, (a pencil αE − βA is


Download Numerische Mathematik
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Numerische Mathematik and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Numerische Mathematik 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?