Error analysis of QR algorithms for computing Lyapunov exponents

E.J. McDonald, D.J. Higham

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

Lyapunov exponents give valuable information about long term dynamics. The discrete and continuous QR algorithms are widely used numerical techniques for computing approximate Lyapunov exponents, although they are not yet supported by a general error analysis. Here, a rigorous convergence theory is developed for both the discrete and continuous QR algorithm applied to a constant coefficient linear system with real distinct eigenvalues. For the discrete QR algorithm, the problem essentially reduces to one of linear algebra for which the timestepping and linear algebra errors uncouple and precise convergence rates are obtained. For the continuous QR algorithm, the stability, rather than the local accuracy, of the timestepping algorithm is relevant, and hence the overall convergence rate is independent of the stepsize. In this case it is vital to use a timestepping method that preserves orthogonality in the ODE system. We give numerical results to illustrate the analysis. Further numerical experiments and a heuristic argument suggest that the convergence properties carry through to the case of complex conjugate eigenvalue pairs.
LanguageEnglish
Pages234-251
Number of pages17
JournalETNA - Electronic Transactions on Numerical Analysis
Volume12
Publication statusPublished - 2001

Fingerprint

QR Algorithm
Error Analysis
Lyapunov Exponent
Time Stepping
Computing
Linear algebra
Convergence Rate
Eigenvalue
Complex conjugate
Convergence Theory
Numerical Techniques
Orthogonality
Convergence Properties
Linear Systems
Numerical Experiment
Heuristics
Distinct
Numerical Results
Coefficient
Term

Keywords

  • dynamics
  • eigenvalues
  • orthogonal iteration
  • timestepping
  • computer science
  • applied mathematics

Cite this

@article{0957e44a05d140cd916fbcb561d131b3,
title = "Error analysis of QR algorithms for computing Lyapunov exponents",
abstract = "Lyapunov exponents give valuable information about long term dynamics. The discrete and continuous QR algorithms are widely used numerical techniques for computing approximate Lyapunov exponents, although they are not yet supported by a general error analysis. Here, a rigorous convergence theory is developed for both the discrete and continuous QR algorithm applied to a constant coefficient linear system with real distinct eigenvalues. For the discrete QR algorithm, the problem essentially reduces to one of linear algebra for which the timestepping and linear algebra errors uncouple and precise convergence rates are obtained. For the continuous QR algorithm, the stability, rather than the local accuracy, of the timestepping algorithm is relevant, and hence the overall convergence rate is independent of the stepsize. In this case it is vital to use a timestepping method that preserves orthogonality in the ODE system. We give numerical results to illustrate the analysis. Further numerical experiments and a heuristic argument suggest that the convergence properties carry through to the case of complex conjugate eigenvalue pairs.",
keywords = "dynamics, eigenvalues, orthogonal iteration, timestepping, computer science, applied mathematics",
author = "E.J. McDonald and D.J. Higham",
year = "2001",
language = "English",
volume = "12",
pages = "234--251",
journal = "ETNA - Electronic Transactions on Numerical Analysis",
issn = "1068-9613",
publisher = "Kent State University",

}

Error analysis of QR algorithms for computing Lyapunov exponents. / McDonald, E.J.; Higham, D.J.

In: ETNA - Electronic Transactions on Numerical Analysis, Vol. 12, 2001, p. 234-251.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Error analysis of QR algorithms for computing Lyapunov exponents

AU - McDonald, E.J.

AU - Higham, D.J.

PY - 2001

Y1 - 2001

N2 - Lyapunov exponents give valuable information about long term dynamics. The discrete and continuous QR algorithms are widely used numerical techniques for computing approximate Lyapunov exponents, although they are not yet supported by a general error analysis. Here, a rigorous convergence theory is developed for both the discrete and continuous QR algorithm applied to a constant coefficient linear system with real distinct eigenvalues. For the discrete QR algorithm, the problem essentially reduces to one of linear algebra for which the timestepping and linear algebra errors uncouple and precise convergence rates are obtained. For the continuous QR algorithm, the stability, rather than the local accuracy, of the timestepping algorithm is relevant, and hence the overall convergence rate is independent of the stepsize. In this case it is vital to use a timestepping method that preserves orthogonality in the ODE system. We give numerical results to illustrate the analysis. Further numerical experiments and a heuristic argument suggest that the convergence properties carry through to the case of complex conjugate eigenvalue pairs.

AB - Lyapunov exponents give valuable information about long term dynamics. The discrete and continuous QR algorithms are widely used numerical techniques for computing approximate Lyapunov exponents, although they are not yet supported by a general error analysis. Here, a rigorous convergence theory is developed for both the discrete and continuous QR algorithm applied to a constant coefficient linear system with real distinct eigenvalues. For the discrete QR algorithm, the problem essentially reduces to one of linear algebra for which the timestepping and linear algebra errors uncouple and precise convergence rates are obtained. For the continuous QR algorithm, the stability, rather than the local accuracy, of the timestepping algorithm is relevant, and hence the overall convergence rate is independent of the stepsize. In this case it is vital to use a timestepping method that preserves orthogonality in the ODE system. We give numerical results to illustrate the analysis. Further numerical experiments and a heuristic argument suggest that the convergence properties carry through to the case of complex conjugate eigenvalue pairs.

KW - dynamics

KW - eigenvalues

KW - orthogonal iteration

KW - timestepping

KW - computer science

KW - applied mathematics

UR - http://www.emis.de/journals/ETNA/vol.12.2001/pp234-251.dir/pp234-251.pdf

M3 - Article

VL - 12

SP - 234

EP - 251

JO - ETNA - Electronic Transactions on Numerical Analysis

T2 - ETNA - Electronic Transactions on Numerical Analysis

JF - ETNA - Electronic Transactions on Numerical Analysis

SN - 1068-9613

ER -