Putzer-Algorithmus

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Beim Putzer-Algorithmus (nach Eugene James Putzer) handelt es sich um eine rekursive Methode zur Berechnung des Matrixexponentials. Ziel des Verfahrens ist es also, für gegebenes und das Matrixexponential zu bestimmen.

Der Algorithmus spielt wie auch das Matrixexponential vor allem in der Theorie gewöhnlicher Differentialgleichungen eine Rolle, da durch ihn Lösungen linearer Differentialgleichungssysteme bestimmt werden können.[1]

Sei eine quadratische -Matrix. Sei weiter eine Abzählung der Eigenwerte der Matrix unter Berücksichtigung der algebraischen Vielfachheit. Diese Abzählung existiert, da algebraisch abgeschlossen ist.

Für definieren wir nun rekursiv stetig differenzierbare Funktionen und -Matrizen , so dass für folgende Beziehung gilt:

.

Die Rekursionsvorschrift für die Matrizen lautet

und .

Die sind rekursiv durch folgende Anfangswertprobleme definiert:

Illustration des Verfahrens für : Sei folgende Matrix gegeben. Wir werden nun mit dem Putzer-Algorithmus das Matrixexponential für beliebiges berechnen. Als erstes bestimmen wir die Eigenwerte der Matrix unter Berücksichtigung der algebraischen Vielfachheit. Dazu berechnen wir das charakteristische Polynom und setzen es gleich :

Es folgt, dass der einzige Eigenwert der Matrix ist, allerdings mit algebraischer Vielfachheit . Somit handelt es sich bei um eine Abzählung der Eigenwerte von .

Als nächstes bestimmen wir mit den Rekursionsformeln von oben die Matrizen . Es folgt und entsprechend .

Zuletzt berechnen wir für die Funktionen , die über folgende Anfangswertprobleme definiert sind:

Das erste Anfangswertproblem lässt sich mittels der Lösungsmethode Trennung der Veränderlichen für gewöhnliche Differentialgleichungen leicht als bestimmen. Das zweite Anfangswertproblem lässt sich ebenfalls sehr einfach über die Methode Variation der Konstanten berechnen und wir erhalten als Lösung .

Da wir nun alles beisammen haben, können wir für ein angeben:

Spezielle Lösungen

[Bearbeiten | Quelltext bearbeiten]

Wie im Beispiel gezeigt, lässt sich das erste Anfangswertproblem mittels der Lösungsmethode Trennung der Veränderlichen für gewöhnliche Differentialgleichungen bestimmen. Die weiteren Anfangswertprobleme mit lassen sich ebenfalls einfach über die Methode Variation der Konstanten berechnen. Dementsprechend folgen zunächst die Lösungen:

Hieraus lassen sich wiederum weitere spezielle Lösungen abhängig von den Eigenwerten ableiten.

Gleiche Eigenwerte

[Bearbeiten | Quelltext bearbeiten]

Sind alle Eigenwerte gleich , folgt aus der integralen Darstellung für mit , dass die Funktion gerade -mal integriert werden muss. Für gilt somit:

Das Matrix-Exponential einer -Matrix mit gleichen Eigenwerten kann schließlich explizit mit folgender Formel bestimmt werden:

Ungleiche Eigenwerte

[Bearbeiten | Quelltext bearbeiten]

Häufig sind alle Eigenwerte der Matrix verschieden ( für ). In diesem Fall gilt für die Diskriminante des charakteristischen Polynoms . Die Lösung für bleibt davon unverändert. Ab folgt nach Integration:

,
usw.

Die Lösung folgt hierbei offensichtlich der Systematik

mit .

Für das Exponential einer -Matrix mit verschiedenen Eigenwerten folgt damit die Newton-Interpolation[2]

für die Darstellung der Matrix-Exponentialfunktion als Polynom. Die von abhängigen Funktionen können dabei rekursiv berechnet werden mit

,
.

Aufwand von Polynom-Lösungsmethoden

[Bearbeiten | Quelltext bearbeiten]

Der Putzer-Algorithmus hat einen Aufwand der Größenordnung (im Wesentlichen Matrizenmultiplikationen). Damit ist der Aufwand deutlich höher als bei Verwendung von Methoden auf Basis der Taylorreihe oder auf Basis von Matrix-Zerlegungsmethoden (wie Diagonalisierung oder QR-Algorithmus), mit jeweils einem Aufwand der Größenordnung . Der Algorithmus ist also eher nur für kleinere Matrizen geeignet, jedoch erhält man hier vorteilhaft eine vollständig symbolische Lösung.

Vergleicht man zum Aufwand die Lösung für die Matrix-Exponentialfunktion mittels Diagonalisieren der Matrix

,

wobei die -te Zeile von ist, mit der Lagrange-Interpolation

,

wobei

,

dann folgt daraus

und der Aufwand der Größenordnung zur Berechnung von ist völlig unnötig.[3]

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Lebovitz 2016 (.pdf)
  2. Moler: Cleve Moler, Charles F. Van Loan: Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later. In: SIAM Review. Band 45, Nr. 1, 2003, ISSN 1095-7200, S. 16 - 18, doi:10.1137/S00361445024180 (cornell.edu [PDF]).
  3. Moler2: Cleve Moler, Charles F. Van Loan: Nineteen Dubious Ways to Compute the Exponential of a Matrix, Twenty-Five Years Later. In: SIAM Review. Band 45, Nr. 1, 2003, ISSN 1095-7200, S. 22 - 23, doi:10.1137/S00361445024180 (cornell.edu [PDF]).