Beim Putzer Algorithmus nach Eugene James Putzer handelt es sich um eine rekursive Methode zur Berechnung des Matrixexponentials Ziel des Verfahrens ist es also fur gegebenes A C n n displaystyle A in mathbb C n times n und x R displaystyle x in mathbb R das Matrixexponential exp A x k 0 A x k k displaystyle textstyle exp Ax sum k 0 infty frac Ax k k zu bestimmen Der Algorithmus spielt wie auch das Matrixexponential vor allem in der Theorie gewohnlicher Differentialgleichungen eine Rolle da durch ihn Losungen linearer Differentialgleichungssysteme bestimmt werden konnen 1 Inhaltsverzeichnis 1 Das Verfahren 2 Beispiel 3 Spezielle Losungen 3 1 Gleiche Eigenwerte 3 2 Ungleiche Eigenwerte 4 Aufwand von Polynom Losungsmethoden 5 Literatur 6 EinzelnachweiseDas Verfahren BearbeitenSei A C n n displaystyle A in mathbb C n times n nbsp eine quadratische n n displaystyle n times n nbsp Matrix Sei weiter l j j 1 n displaystyle lambda j j 1 ldots n nbsp eine Abzahlung der Eigenwerte der Matrix A displaystyle A nbsp unter Berucksichtigung der algebraischen Vielfachheit Diese Abzahlung existiert da C displaystyle mathbb C nbsp algebraisch abgeschlossen ist Fur k 1 n displaystyle k in 1 ldots n nbsp definieren wir nun rekursiv stetig differenzierbare Funktionen p k C 1 R C displaystyle p k in C 1 mathbb R mathbb C nbsp und n n displaystyle n times n nbsp Matrizen M k 1 C n n displaystyle M k 1 in mathbb C n times n nbsp so dass fur x R displaystyle x in mathbb R nbsp folgende Beziehung gilt exp A x k 1 n p k x M k 1 displaystyle exp Ax sum k 1 n p k x M k 1 nbsp Die Rekursionsvorschrift fur die Matrizen M k displaystyle M k nbsp lautet M 0 I n displaystyle M 0 I n nbsp und M k A l k I M k 1 displaystyle M k A lambda k cdot I M k 1 nbsp Die p k displaystyle p k nbsp sind rekursiv durch folgende Anfangswertprobleme definiert p 1 x l 1 p 1 x p 1 0 1 p k x l k p k x p k 1 p k 0 0 displaystyle left begin aligned p 1 x amp lambda 1 p 1 x p 1 0 amp 1 end aligned right quad left begin aligned p k x amp lambda k p k x p k 1 p k 0 amp 0 end aligned right nbsp Beispiel BearbeitenIllustration des Verfahrens fur n 2 displaystyle n 2 nbsp Sei folgende Matrix A 3 1 1 1 displaystyle A begin pmatrix 3 amp 1 1 amp 1 end pmatrix nbsp gegeben Wir werden nun mit dem Putzer Algorithmus das Matrixexponential exp A x displaystyle exp Ax nbsp fur beliebiges x R displaystyle x in mathbb R nbsp berechnen Als erstes bestimmen wir die Eigenwerte der Matrix A displaystyle A nbsp unter Berucksichtigung der algebraischen Vielfachheit Dazu berechnen wir das charakteristische Polynom und setzen es gleich 0 displaystyle 0 nbsp x A l det A l I det 3 l 1 1 1 l l 2 4 l 4 l 2 2 0 displaystyle chi A lambda det A lambda I det begin pmatrix 3 lambda amp 1 1 amp 1 lambda end pmatrix lambda 2 4 lambda 4 lambda 2 2 overset 0 nbsp Es folgt dass l 2 displaystyle lambda 2 nbsp der einzige Eigenwert der Matrix A displaystyle A nbsp ist allerdings mit algebraischer Vielfachheit 2 displaystyle 2 nbsp Somit handelt es sich bei l 1 l 2 2 2 displaystyle lambda 1 lambda 2 2 2 nbsp um eine Abzahlung der Eigenwerte von A displaystyle A nbsp Als nachstes bestimmen wir mit den Rekursionsformeln von oben die Matrizen M k k 0 1 displaystyle M k k in 0 1 nbsp Es folgt M 0 1 0 0 1 displaystyle M 0 begin pmatrix 1 amp 0 0 amp 1 end pmatrix nbsp und entsprechend M 1 A l 1 I 2 M 0 A l 1 I 2 1 1 1 1 displaystyle M 1 A lambda 1 I 2 M 0 A lambda 1 I 2 begin pmatrix 1 amp 1 1 amp 1 end pmatrix nbsp Zuletzt berechnen wir fur k 1 2 displaystyle k in 1 2 nbsp die Funktionen p k displaystyle p k nbsp die uber folgende Anfangswertprobleme definiert sind p 1 x 2 p 1 x p 1 0 1 p 2 x 2 p 2 x p 1 p 2 0 0 displaystyle left begin array ll p 1 x 2p 1 x p 1 0 1 end array right quad left begin array ll p 2 x 2p 2 x p 1 p 2 0 0 end array right nbsp Das erste Anfangswertproblem lasst sich mittels der Losungsmethode Trennung der Veranderlichen fur gewohnliche Differentialgleichungen leicht als p 1 x exp 2 x displaystyle p 1 x exp 2x nbsp bestimmen Das zweite Anfangswertproblem lasst sich ebenfalls sehr einfach uber die Methode Variation der Konstanten berechnen und wir erhalten als Losung p 2 x x exp 2 x displaystyle p 2 x x exp 2x nbsp Da wir nun alles beisammen haben konnen wir exp A x displaystyle exp Ax nbsp fur ein x R displaystyle x in mathbb R nbsp angeben exp A x k 1 2 p k x M k 1 exp 2 x 1 0 0 1 x exp 2 x 1 1 1 1 exp 2 x 1 x x x 1 x displaystyle exp Ax sum k 1 2 p k x M k 1 exp 2x begin pmatrix 1 amp 0 0 amp 1 end pmatrix x exp 2x begin pmatrix 1 amp 1 1 amp 1 end pmatrix exp 2x begin pmatrix 1 x amp x x amp 1 x end pmatrix nbsp Spezielle Losungen BearbeitenWie im Beispiel gezeigt lasst sich das erste Anfangswertproblem mittels der Losungsmethode Trennung der Veranderlichen fur gewohnliche Differentialgleichungen bestimmen Die weiteren Anfangswertprobleme mit k 2 n displaystyle k in 2 ldots n nbsp lassen sich ebenfalls einfach uber die Methode Variation der Konstanten berechnen Dementsprechend folgen zunachst die Losungen p 1 t e l 1 t displaystyle p 1 t e lambda 1 t nbsp p k t e l k t x 0 t p k 1 x e l k x d x displaystyle p k t e lambda k t int x 0 t p k 1 x e lambda k x mathrm d x nbsp Hieraus lassen sich wiederum weitere spezielle Losungen abhangig von den Eigenwerten ableiten Gleiche Eigenwerte Bearbeiten Sind alle Eigenwerte gleich l l 1 l 2 l n displaystyle lambda lambda 1 lambda 2 dotsc lambda n nbsp folgt aus der integralen Darstellung fur p k displaystyle p k nbsp mit k 2 displaystyle k geq 2 nbsp dass die Funktion f 1 displaystyle f 1 nbsp gerade k 1 displaystyle k 1 nbsp mal integriert werden muss Fur k 1 displaystyle k geq 1 nbsp gilt somit p k t t k 1 k 1 e l t displaystyle p k t frac t k 1 k 1 e lambda t nbsp Das Matrix Exponential einer n n displaystyle n times n nbsp Matrix mit gleichen Eigenwerten l displaystyle lambda nbsp kann schliesslich explizit mit folgender Formel bestimmt werden exp A t e l t E t e l t A l E e l t i 0 n 1 t i i A l E i displaystyle exp At e lambda t E t e lambda t A lambda E dotsc e lambda t sum i 0 n 1 frac t i i A lambda E i nbsp Ungleiche Eigenwerte Bearbeiten Haufig sind alle Eigenwerte der Matrix verschieden l i l j displaystyle lambda i neq lambda j nbsp fur i j displaystyle i neq j nbsp In diesem Fall gilt fur die Diskriminante des charakteristischen Polynoms D n 0 displaystyle D n neq 0 nbsp Die Losung fur p 1 t displaystyle p 1 t nbsp bleibt davon unverandert Ab k 2 displaystyle k geq 2 nbsp folgt nach Integration p 2 t e l 1 t e l 2 t l 1 l 2 displaystyle p 2 t frac e lambda 1 t e lambda 2 t lambda 1 lambda 2 nbsp p 3 t e l 1 t e l 3 t l 1 l 2 l 1 l 3 e l 2 t e l 3 t l 2 l 1 l 2 l 3 displaystyle p 3 t frac e lambda 1 t e lambda 3 t lambda 1 lambda 2 lambda 1 lambda 3 frac e lambda 2 t e lambda 3 t lambda 2 lambda 1 lambda 2 lambda 3 nbsp usw Die Losung folgt hierbei offensichtlich der Systematik p k t i 1 k 1 e l i t e l k t j 1 k l i l j displaystyle p k t sum i 1 k 1 frac e lambda i t e lambda k t prod j 1 k lambda i lambda j nbsp mit j i displaystyle j neq i nbsp Fur das Exponential einer n n displaystyle n times n nbsp Matrix mit verschiedenen Eigenwerten folgt damit die Newton Interpolation 2 exp A t e l 1 t E i 2 n l 1 l i j 1 i 1 A l j E displaystyle exp At e lambda 1 t E sum i 2 n lambda 1 dotsc lambda i prod j 1 i 1 A lambda j E nbsp fur die Darstellung der Matrix Exponentialfunktion als Polynom Die von x displaystyle x nbsp abhangigen Funktionen konnen dabei rekursiv berechnet werden mit l 1 l 2 e l 1 t e l 2 t l 1 l 2 displaystyle lambda 1 lambda 2 frac e lambda 1 t e lambda 2 t lambda 1 lambda 2 nbsp l 1 l k 1 l 1 l k l 2 l k 1 l 1 l k 1 displaystyle lambda 1 dotsc lambda k 1 frac lambda 1 dotsc lambda k lambda 2 dotsc lambda k 1 lambda 1 lambda k 1 nbsp k 2 displaystyle k geq 2 nbsp Aufwand von Polynom Losungsmethoden BearbeitenDer Putzer Algorithmus hat einen Aufwand der Grossenordnung O n 4 displaystyle mathcal O n 4 nbsp im Wesentlichen n displaystyle n nbsp Matrizenmultiplikationen Damit ist der Aufwand deutlich hoher 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 Grossenordnung O n 3 displaystyle mathcal O n 3 nbsp Der Algorithmus ist also eher nur fur kleinere Matrizen geeignet jedoch erhalt man hier vorteilhaft eine vollstandig symbolische Losung Vergleicht man zum Aufwand die Losung fur die Matrix Exponentialfunktion mittels Diagonalisieren der Matrix exp A t V diag e l i t V 1 j 1 n e l i t v j y j T displaystyle exp At V operatorname diag e lambda i t V 1 sum j 1 n e lambda i t v j y j T nbsp wobei y j T displaystyle y j T nbsp die j displaystyle j nbsp te Zeile von V 1 displaystyle V 1 nbsp ist mit der Lagrange Interpolation exp A t j 1 n e l i t A j displaystyle exp At sum j 1 n e lambda i t A j nbsp wobei A j k 1 n A l k E l j l k k j displaystyle A j prod k 1 n frac A lambda k E lambda j lambda k quad k neq j nbsp dann folgt daraus A j v j y j T displaystyle A j v j y j T nbsp und der Aufwand der Grossenordnung O n 4 displaystyle mathcal O n 4 nbsp zur Berechnung von A j displaystyle A j nbsp ist vollig unnotig 3 Literatur BearbeitenPaul Waltman Differential Equations and Dynamical Systems Dover Publications 2004 ISBN 978 0486434780 S 49 60 Eugene J Putzer Avoiding the Jordan Canonical Form in the Discussion of Linear Systems with Constant Coefficients The American Mathematical Monthly Vol 73 1 1966 S 2 7 DOI 10 1080 00029890 1966 11970714 DorFuchs Der Putzer Algorithmus den kaum jemand kennt zur Bestimmung der Matrixexponentialfunktion auf YouTube 13 Februar 2018 abgerufen am 9 Februar 2023 Einzelnachweise Bearbeiten Lebovitz 2016 pdf 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 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 Abgerufen von https de wikipedia org w index php title Putzer Algorithmus amp oldid 230720982
