The spectrum of delay-differential equations [Elektronische Ressource] : numerical methods, stability and perturbation / von Elias Jarlebring

Description

The spectrum of delay-differentialequations: numerical methods,stability and perturbationVon der Carl-Friedrich-Gauß-Fakultat¨Technische Universitat¨ Carolo-Wilhelmina zuBraunschweigzur Erlangung des GradesDoktor der Naturwissenschaften (Dr. rer. nat.)genehmigte Dissertationvon Elias Jarlebringgeboren am 3. Februar 1978in Vann¨ ¨as, SchwedenEingereicht am: 01.02.2008Mun¨ dliche Pruf¨ ung am: 28.05.2008Referentin: Prof. Dr. Heike Faßbender, TU BraunschweigKorreferent: Prof. Dr. Achim Ilchmann, TU IlmenauKorreferent: Prof. Dr.

Subjects

• Documents
• Knowledge
• Mathematics

Informations

• Published by: technische_universitat_carolo-wilhelmina_zu_braunschweig
• Published: 01 January 2009
• Reads: 15
• Language: English
• Document size: 1 MB

Exrait

The spectrum of delaydifferential equations: numerical methods, stability and perturbation Von der CarlFriedrichGaußFakultät Technische Universität CaroloWilhelmina zu Braunschweig

zur Erlangung des Grades Doktor der Naturwissenschaften (Dr. rer. nat.)

genehmigte Dissertation

vonElias Jarlebring geboren am3. Februar 1978 inVännäs, Schweden

Eingereicht am:

Mündliche Prüfung am:

Referentin: Korreferent: Korreferent:

01.02.2008

28.05.2008

Prof. Dr. Heike Faßbender, TU Braunschweig Prof. Dr. Achim Ilchmann, TU Ilmenau Prof. Dr. Daniel Kreßner, ETH Zürich

2008

ii

Notation

R R + R − Z Q C C + C − D, ∂D ∂C closC i Rez Imz l(z 1 , z 2 ) Argz z¯ ∗ A σ(A), σ(Σ) σ(G) σ(A, B) σ min (A) k ∙ k κ(A) r σ (A)   a atan b sgn(z) O(g(x)) ǫ mach ⊗,⊕ W k d m (S 1 , S 2 ) d H (S 1 , S 2 ) C([a, b])

real numbers positive real numbers negative real numbers integer numbers rational numbers complex numbers open right half plane open left half plane open unit disc (D:={z∈C:|z|<1}), unit circle boundary of the setC closure of the setC, closC=∂C∪C 2 imaginary unit,i=−1 real part of the complex numberz imaginary part of the complex numberz straight line connectingz 1 , z 2 ∈Cnot including endpoints principal branch argument of the complex numberz complex conjugate of the complex numberz complex conjugate transpose of the matrixA spectrum of the matrixAor system Σ n×n solutions ofs∈σ(G(s)) whereG:C→C solutions of the generalized eigenvalue problem det(A−λB) = 0 the smallest singular value of the matrixA Eucledian or spectral norm condition number of matrixA spectral radius of matrixA   a four quadrant inverse of tangent, atan = Arg (b+ai) b sign of complex numberz, sgn(z) =z/|z|ifz6= 0 big O,f(x) =O(g(x))⇔ ∃M >0, x 0 >0 :|f(x)|< M|g(x)| ∀x > x 0 −16 machine precision, where not explicitly stated:ǫ mach ≈2.2∙10 Kronecker product, Kronecker sum kth branch of the LambertWfunction maxmin distance between setsS 1 andS 2 Hausdorff distance between setsS 1 andS 2 A continuous function on the segmentt∈[−a, b]

Acronyms

DDE DEP IGD LHP LMI LMS MS NPhard PDDE PDE PS RHP RI RII SOD SRII TDS

delaydifferential equation delay eigenvalue problem infinitesimal generator discretization left halfplane linear matrix inequality linear multistep MilneSimpson nondeterministic polynomialtime hard partial delaydifferential equation partial differential equation pseudospectral right halfplane Rayleigh iteration residual inverse iteration solution operator discretization subspace accelerated residual inverse iteration timedelay system

Contents

1

2

3

Introduction

Computing the spectrum 2.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Methods for DDEs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.1 Scalar or simultaneously triangularizable DDEs: LambertW 2.2.2 Solution operator discretization (SOD) . . . . . . . . . . . . . 2.2.3 PDE discretization (IGD) . . . . . . . . . . . . . . . . . . . . 2.3 Methods for nonlinear eigenvalue problems . . . . . . . . . . . . . . 2.3.1 Scalar and vector valued fixed point methods . . . . . . . . . 2.3.2 Projecton methods . . . . . . . . . . . . . . . . . . . . . . . . 2.4 Numerical examples . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.4.1 A PDDE with real eigenvalues . . . . . . . . . . . . . . . . . 2.4.2 Random matrix with complex eigenvalues . . . . . . . . . . .

. . . . . . . . . . .

. . . . . . . . . . .

Critical Delays 3.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.1.1 Problem formulation . . . . . . . . . . . . . . . . . . . . . . . . . 3.2 Notes and references on delaydependent stability results . . . . . . . . . 3.3 A parameterization for retarded DDEs . . . . . . . . . . . . . . . . . . . 3.3.1 Main results . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

9 9 14 16 24 38 46 47 51 60 60 65

69 72 75 82 90 95

4

3.4

3.5

3.6

3.7

3.3.2 Plotting critical curves . . . . . . . . . . . . . . 3.3.3 Commensurate delays . . . . . . . . . . . . . . 3.3.4 Examples . . . . . . . . . . . . . . . . . . . . . A parameterization for neutral DDEs . . . . . . . . . . 3.4.1 Main results . . . . . . . . . . . . . . . . . . . . 3.4.2 Commensurate delays . . . . . . . . . . . . . . 3.4.3 Examples . . . . . . . . . . . . . . . . . . . . . Solving the quadratic eigenproblem . . . . . . . . . . . 3.5.1 Exploiting the structure . . . . . . . . . . . . . 3.5.2 Example . . . . . . . . . . . . . . . . . . . . . . Multiparameter problems and matrix pencil methods . 3.6.1 Polynomial twoparameter eigenvalue problems 3.6.2 One single delay . . . . . . . . . . . . . . . . . 3.6.3 Neutral systems . . . . . . . . . . . . . . . . . 3.6.4 Commensurate delays . . . . . . . . . . . . . . NPhardness issues . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . . .

Perturbation of nonlinear eigenproblems 4.1 Notes on current literature . . . . . . . . . . . . . . . . . . . . . . 4.2 The fixed point form and a similarity transformation . . . . . . . 4.3 Local perturbation and convergence . . . . . . . . . . . . . . . . 4.3.1 Local perturbation and sensitivity analysis . . . . . . . . 4.3.2 Convergence of fixed point iterations . . . . . . . . . . . . 4.4 Nonlocal perturbation results and the BauerFike theorem . . . 4.4.1 The BauerFike theorem . . . . . . . . . . . . . . . . . . . 4.4.2 Contraction mappings in setvalued fixed point theory . . 4.4.3 A BauerFike theorem for nonlinear eigenvalue problems .

. . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . .

. . . . . . . . . . . . . . . .

. . . . . . . . .

104 105 107 113 115 120 121 126 128 130 131 132 136 137 138 140

145 147 150 153 153 158 162 165 166 168

A Appendix 171 A.1 Linearization of polynomial eigenproblems . . . . . . . . . . . . . . . . . 171

Abstract

Three types of problems related totimedelay systemsare treated in this the sis. In our context, a timedelay system, or sometimesdelaydifferential equation (DDE), is a generalization of an ordinary differential equation (ODE) with con stant coefficients. For DDEs, unlike ODEs, the derivative of the state at some timepoint is not only dependent on the state at that timepoint, but also on one or more previous states.

We first consider the problem of numerically computing theeigenvaluesof a DDE, i.e., finding solutions of thecharacteristic equation, here referred to as thedelay eigenvalue problem. Unlike standard ODEs, the characteristic equation of a DDE contains an exponential term. Because of this nonlinear term, the delay eigenvalue problem belongs to a class of problems referred to asnonlinear eigenvalue problems. An important contribution of the first part of this thesis is the application of a projection method for nonlinear eigenvalue problems, to the author’s knowledge, previously not applied to the delay eigenvalue problem. We compare this projection method with other methods, suggested in the literature, and used in software packages. This includes methods based on discretizations of thesolution operatorand discretizations of the equivalentboundary value problem formulationof the DDE, i.e., theinfinitesimal generatorreview discretiza. We tions based on, but not limited to,linear multistep,RungeKuttaandspectral collocationprojection method is computationally superior to all of the other. The tested method for the presented largescale examples. We give interpretations of the methods based on discretizations in terms of rational approximations of the exponential function or the logarithm. Some notes regarding a special case where the spectrum can be explicitly expressed are presented. The spectrum can be expressed with a formula containing a matrix version of the Lambert W func

tion. The formula is not new. We clarify its range of applicability, and, by counterexample, show that it does not hold in general. The second part of this thesis is related to exact stability conditions of the DDE. We find exact conditions on the delays such that the DDE has a purely imaginary eigenvalue. All those combinations of the delays such that there is a purely imaginary eigenvalue (calledcritical delaysThat) are parameterized. is, we construct amappingconsisting of computable expressions, from a simple mathematical object onto the set of all subsets of the critical delays. The map ping can be expressed explicitly with trigonometric functions for scalar DDEs. We find some new formulas and verify some formulas in the literature. In general, an evaluation of the map consists of solving aquadratic eigenvalue problemof squared dimension for nonscalar problems. The constructed eigenvalue problem is large, even for DDEs of moderate size. For that reason, we show how the com putational cost for one evaluation of the map can be reduced. In particular we show that the matrixvector product corresponding to thecompanion lineariza tionof the quadratic eigenvalue problem can be computed by solving aLyapunov equation. Most of the results in the chapter on critical delays are derived for retarded DDEs as well as neutral DDEs with an arbitrary number of delays. The third and last part of this thesis is about perturbation results for non linear eigenvalue problems. We discuss some results in eigenvalue perturbation theory which can be generalized to nonlinear eigenvalue problems. A sensitivity formula for the movement of the eigenvalues extends nicely to nonlinear eigen value problems. We introduce a fixed point form for the nonlinear eigenvalue problem, and show that some methods in the literature can be interpreted as set valued fixed point iterations. The convergence order of these types of iterations can be determined from an expression containing the left and right eigenvec tors. We also use some results fromfixed point theoryfamous result in. The perturbation theory referred to asthe BauerFike theorem, can be generalized to the nonlinear eigenvalue problem if we assume that the setvalued fixed point problem has a certain contraction property.

Zusammenfassung

In dieser Arbeit werden drei verschiedene Problemklassen im Bezug zu timedelay Systemen behandelt. Unter einem timedelay System, oder manchmal delay differential equation (DDE), verstehen wir die Verallgemeinerung einer gewöhn lichen Differentialgleichung (ODE) mit konstanten Koeffizienten. Wobei im Ge gensatz zu ODEs, bei DDEs die Ableitung zu jedem Zeitpunkt nicht nur vom aktuellen, sondern auch von einem oder mehreren vorhergehenden Zuständen abhängig ist.

Als erstes gehen wir auf die numerischen Berechnung der Eigenwerte von DDEs ein. Das heißt es sind Lösungen der charakterischen Gleichung zu finden. Dieses Problem wird im Folgenden als DelayEigenwertproblem (DEP) bezeich net. Im Gegensatz zu ODEs enthält die charakteristische Gleichung einer DDE einen exponentiellen Term. Aufgrund des nichtlinearen Terms gehört das Delay Eigenwertproblem zur Klasse der nichtlinearen Eigenwertprobleme. Ein wichtiger Beitrag dieser Arbeit ist die Anwendung einer Projektionsmethode für nichtlinea re Eigenwertprobleme, welche bisher noch nicht auf DEPs angewendet wurde. Wir vergleichen diese Projektionsmethode mit anderen in der Literatur vorgeschlage nen und in Softwarepaketen verwendeten Verfahren. Dieser Vergleich schliesst Methoden der Diskretisierung des Lösungsoperators sowie der Diskretisierung des äquivalenten Randwertproblems ein. Dabei betrachten wir auf Diskretisierung basierende Methoden, wie lineare Mehrschrittverfahren, RungeKutta Verfahren und spectral collocation, näher. Es stellt sich heraus, dass die hier vorgestell te Projektionsmethode bedeutend bessere numerische Eigenschaften für die hier verwendeten großen Beispiele, als sämtliche andere getestete Verfahren besitzt. Zusätzlich treffen wir Aussagen über Diskretisierungsmethoden zur rationalen Approximation der Exponentialfunktion bzw. des Logarithmus. Des weiteren be trachten wir einen Spezialfall, bei welchem das Spektrum explizit mit Hilfe einer

MatrixVersion der Lambert WFunktion dargestellt werden kann. Für diese an sich nicht neue Formel bestimmen wir einen möglichen Anwendungsbereich und zeigen durch ein Gegenbeispiel, dass diese nicht allgemein gilt. Im zweiten Teil der Arbeit werden exakte Stabilitätsbedingungen von DDEs betrachtet. Für die Delays werden exakte Bedingungen so bestimmt, dass die DDE einen rein imaginären Eigenwert besitzt. Die Menge dieser Delays, soge nanntekritische Delays, wird parameterisiert. Das heißt, wir bilden eine aus berechenbaren Ausdrücken bestehende Abbildung von einem einfachen mathe matischen Objekt auf die Menge aller Teilmengen kritischer Delays. Für skalare Probleme wird diese Abbildung mit trigonometrischen Funktionen explizit aus gedrückt. Dabei werden sowohl neue Formeln hergeleitet als auch bereits in der Literatur bekannte Formeln bestätigt. Für nicht skalare Probleme ist zur Aus wertung der Abbildung das Lösen einesquadratischen Eigenwertproblemsnötig, dessen Größe dem Quadrat der Dimension der DDE entspricht. Damit wird auch für DDEs kleiner und mittlerer Dimension das konstruierte Eigenwertproblem groß beziehungsweise sehr groß. Weiterhin werden möglichkeiten zur Reduktion des Rechenaufwandes der Auswertung der Abbildung diskutiert. Es wird gezeigt, dass das zur companion Linearisierung des quadratischen Eigenwertproblems gehörende MatrixVektor Produkt durch das Lösen einer LyapunovGleichung berechnet werden kann. Die meisten Ergebnisse des Kapitels über kritische De lays sind speziell auf DDEs mit beliebiger Anzahl von Delays, sowohl retardierter als auch neutraler Form, anwendbar. Der dritte und letzte Teil dieser Arbeit befasst sich mit der Störungstheo rie von nichtlinearen Eigenwertproblemen. Hierin werden einige Aussagen über Ergebnisse der Eigenwertstörungstheorie, welche sich auf nichtlineare Eigenwert probleme verallgemeinern lassen, getroffen. Unter anderem lässt sich eine Formel für die Sensitivität auf nichtlineare Eigenwertprobleme erweitern. Desweiteren wird eine Fixpunktform für nichtlineare Eigenwertprobleme vorgestellt, und ge zeigt dass einige Methoden aus der Literatur als mengenwertige Fixpunktitera tionen dargestellt werden können. Die Konvergenzordnung solcher Iterationen kann durch einen aus linkem und rechtem Eigenvektor bestehenden Ausdruck bestimmt werden. Ausserdem werden einige Ergebnisse aus der Fixpunkttheorie verwendet. Damit kann das in der Störungstheorie bekannte BauerFike Theorem auf nichtlineare Eigenwertprobleme verallgemeinert werden, wenn angenommen wird, dass das mengenwertige Fixpunktproblem äquivalent zu einer Kontraktion ist.

Acknowledgements

This thesis would not have been possible without the assistance and support of friends and colleagues at thetechnical university of Braunschweigand elsewhere. First of all, I have the pleasure to thank my supervisor, Heike Fassbender, for guidance and very valuable support throughout my years as a PhD student in Braunschweig. I am grateful for her outstanding efforts which have made this thesis possible. Among the friends and colleagues, special thanks go to: Tobias Damm for very often providing constructive accurate criticism, my master thesis examiner and supervisor Axel Ruhe, KTH Stockholm, for discussions and allowing a nice time as a visitor at the numerical analysis group at KTH, Michiel E. Hochstenbach, for his enthusiasm, inspiration, discussions and advices, and my former master thesis supervisor Heinrich Voss, for discussions and valuable comments. I am also grateful to many other colleagues and friends for technical discus sions, and fruitful comments on programming issues, as well as drafts and final versions of this thesis: Matthias Bollhöfer, Dimitri Breda, Henrik Bäärnhielm, Johan Karlsson, Daniel Kressner, Volker Mehrmann, Wim Michiels, Timo Reis, Bor Plestenjak, Peter Stange and Fabian Wirth.