63
Verfahren zur Berechnung der Exponentialmatrix Konrad Waldherr Verfahren zur Berechnung der Exponentialmatrix – p.1/14

Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

  • Upload
    vokien

  • View
    244

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Verfahren zur Berechnung derExponentialmatrix

Konrad Waldherr

Verfahren zur Berechnung der Exponentialmatrix – p.1/14

Page 2: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Motivation

• In einem Quantensystem ist folgendes Produktvon besonderer Bedeutung:

e−itMHM · . . . e−itkHk · . . . e−it1H1

Verfahren zur Berechnung der Exponentialmatrix – p.2/14

Page 3: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Motivation

• In einem Quantensystem ist folgendes Produktvon besonderer Bedeutung:

e−itMHM · . . . e−itkHk · . . . e−it1H1

• Zur Berechnung dieses Produkts muss jeweils dieExponentialfunktion einer Matrix berechnetwerden:

e−itMHM · . . . e−itkHk · . . . e−it1H1

Verfahren zur Berechnung der Exponentialmatrix – p.2/14

Page 4: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Motivation

• In einem Quantensystem ist folgendes Produktvon besonderer Bedeutung:

e−itMHM · . . . e−itkHk · . . . e−it1H1

• Zur Berechnung dieses Produkts muss jeweils dieExponentialfunktion einer Matrix berechnetwerden:

e−itMHM · . . . e−itkHk · . . . e−it1H1

• Frage: Wie berechnet man

e−itkHk

Verfahren zur Berechnung der Exponentialmatrix – p.2/14

Page 5: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Definition der Exponentialmatrix

• Ausgangspunkt: Taylorreihe der e-Funktion

ex =∞∑

k=0

xk

k!

Verfahren zur Berechnung der Exponentialmatrix – p.3/14

Page 6: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Definition der Exponentialmatrix

• Ausgangspunkt: Taylorreihe der e-Funktion

ex =∞∑

k=0

xk

k!

• Definition der Exponentialfunktion einer Matrix A

exp(A) := eA :=

∞∑

k=0

Ak

k!

Verfahren zur Berechnung der Exponentialmatrix – p.3/14

Page 7: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Definition der Exponentialmatrix

• Ausgangspunkt: Taylorreihe der e-Funktion

ex =∞∑

k=0

xk

k!

• Definition der Exponentialfunktion einer Matrix A

exp(A) := eA :=

∞∑

k=0

Ak

k!

• Für eine Diagonalmatrix D = diag(d1, . . . , dn) gilt

eD = diag(ed1 , . . . , edn)Verfahren zur Berechnung der Exponentialmatrix – p.3/14

Page 8: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Berechnung der Exponentialmatrix

• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:

exp(A) ≈

n∑

k=0

Ak

k!

Verfahren zur Berechnung der Exponentialmatrix – p.4/14

Page 9: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Berechnung der Exponentialmatrix

• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:

exp(A) ≈

n∑

k=0

Ak

k!

• Diese Reihe konvergiert allerdings sehr langsam:

‖ eA−

n∑

k=0

Ak

k!‖≤

(

‖ A ‖n+1

(n + 1)!

)(

1

1− ‖ A ‖ /(n + 2)

)

≤ δ

Verfahren zur Berechnung der Exponentialmatrix – p.4/14

Page 10: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Berechnung der Exponentialmatrix

• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:

exp(A) ≈

n∑

k=0

Ak

k!

• Diese Reihe konvergiert allerdings sehr langsam:

‖ eA−

n∑

k=0

Ak

k!‖≤

(

‖ A ‖n+1

(n + 1)!

)(

1

1− ‖ A ‖ /(n + 2)

)

≤ δ

• Beispiel: ‖ A ‖= 100 und δ = 10−6 liefert n = 284.

Verfahren zur Berechnung der Exponentialmatrix – p.4/14

Page 11: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Berechnung der Exponentialmatrix

• Naheliegend: Berechnung durch “abgeschnittene“Taylor-Reihe:

exp(A) ≈

n∑

k=0

Ak

k!

• Diese Reihe konvergiert allerdings sehr langsam:

‖ eA−

n∑

k=0

Ak

k!‖≤

(

‖ A ‖n+1

(n + 1)!

)(

1

1− ‖ A ‖ /(n + 2)

)

≤ δ

• Beispiel: ‖ A ‖= 100 und δ = 10−6 liefert n = 284.

• Weiteres Problem: Numerische InstabilitätVerfahren zur Berechnung der Exponentialmatrix – p.4/14

Page 12: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 13: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 14: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 15: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

− Wähle m als Zweierpotenz: m = 2k

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 16: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

− Wähle m als Zweierpotenz: m = 2k

−(

eA/m)m

durch wiederholtes Quadrieren

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 17: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

− Wähle m als Zweierpotenz: m = 2k

−(

eA/m)m

durch wiederholtes Quadrieren

• Padé-Approximation:

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 18: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

− Wähle m als Zweierpotenz: m = 2k

−(

eA/m)m

durch wiederholtes Quadrieren

• Padé-Approximation:

− reelle Padé-Approximation: ex ≈ p(x)q(x)

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 19: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

− Wähle m als Zweierpotenz: m = 2k

−(

eA/m)m

durch wiederholtes Quadrieren

• Padé-Approximation:

− reelle Padé-Approximation: ex ≈ p(x)q(x)

− eA ≈ (q(A))−1p(A)

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 20: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Scaling and Squaring

− eA =(

eA/m)m

− Wähle m, so dass ‖ A ‖ /m ≤ 1

− Wähle m als Zweierpotenz: m = 2k

−(

eA/m)m

durch wiederholtes Quadrieren

• Padé-Approximation:

− reelle Padé-Approximation: ex ≈ p(x)q(x)

− eA ≈ (q(A))−1p(A)

− Kombination mit Scaling and Squaring

Verfahren zur Berechnung der Exponentialmatrix – p.5/14

Page 21: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Chebyshev-Approximation

Verfahren zur Berechnung der Exponentialmatrix – p.6/14

Page 22: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung

e−αx = 2I0(α)T0(αx) + 2∞∑

j=1

Tj(αx)Ij(α)(−1)j

Verfahren zur Berechnung der Exponentialmatrix – p.6/14

Page 23: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung

e−αx = 2I0(α)T0(αx) + 2∞∑

j=1

Tj(αx)Ij(α)(−1)j

− Tj: Chebyshev-Polynom 1. Art der Ordnung j

Verfahren zur Berechnung der Exponentialmatrix – p.6/14

Page 24: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung

e−αx = 2I0(α)T0(αx) + 2∞∑

j=1

Tj(αx)Ij(α)(−1)j

− Tj: Chebyshev-Polynom 1. Art der Ordnung j

− Ij: Besselfunktion der Ordnung j

Verfahren zur Berechnung der Exponentialmatrix – p.6/14

Page 25: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Chebyshev-Approximation− Für −1 ≤ x ≤ 1 gilt die Entwicklung

e−αx = 2I0(α)T0(αx) + 2∞∑

j=1

Tj(αx)Ij(α)(−1)j

− Tj: Chebyshev-Polynom 1. Art der Ordnung j

− Ij: Besselfunktion der Ordnung j

− Transfer auf Matrizen: r0 =‖ A ‖, A0 = A/r0

eA = er0A0 = 2I0(−r0)T0(−A)+2∞∑

j=1

Tj(−A)Ij(−r0)(−1)j

Verfahren zur Berechnung der Exponentialmatrix – p.6/14

Page 26: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über gewöhnliche Differentialgleichung:

Verfahren zur Berechnung der Exponentialmatrix – p.7/14

Page 27: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über gewöhnliche Differentialgleichung:− Gegeben ist das AWP

y′ = Ay, y(t0) = y0

Verfahren zur Berechnung der Exponentialmatrix – p.7/14

Page 28: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über gewöhnliche Differentialgleichung:− Gegeben ist das AWP

y′ = Ay, y(t0) = y0

− Die analytische Lösung lautet

y(t) = e(t−t0)Ay0

Verfahren zur Berechnung der Exponentialmatrix – p.7/14

Page 29: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über gewöhnliche Differentialgleichung:− Gegeben ist das AWP

y′ = Ay, y(t0) = y0

− Die analytische Lösung lautet

y(t) = e(t−t0)Ay0

− eA aus n Differentialgleichungen

y′(i) = Ay(i), y(i)(0) = ei

Verfahren zur Berechnung der Exponentialmatrix – p.7/14

Page 30: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Damit ergibt sich

eA =(

y1(1) . . . yn(1))

Verfahren zur Berechnung der Exponentialmatrix – p.8/14

Page 31: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Damit ergibt sich

eA =(

y1(1) . . . yn(1))

• Lösung der Differentialgleichungen:

Verfahren zur Berechnung der Exponentialmatrix – p.8/14

Page 32: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Damit ergibt sich

eA =(

y1(1) . . . yn(1))

• Lösung der Differentialgleichungen:− Einschrittverfahren (z.B. Runge-Kutta-Verfahren

mit fester Schrittweite)

Verfahren zur Berechnung der Exponentialmatrix – p.8/14

Page 33: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Damit ergibt sich

eA =(

y1(1) . . . yn(1))

• Lösung der Differentialgleichungen:− Einschrittverfahren (z.B. Runge-Kutta-Verfahren

mit fester Schrittweite)− Mehrschrittverfahren

Verfahren zur Berechnung der Exponentialmatrix – p.8/14

Page 34: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Damit ergibt sich

eA =(

y1(1) . . . yn(1))

• Lösung der Differentialgleichungen:− Einschrittverfahren (z.B. Runge-Kutta-Verfahren

mit fester Schrittweite)− Mehrschrittverfahren− allgemeiner ODE-Solver

Verfahren zur Berechnung der Exponentialmatrix – p.8/14

Page 35: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über Eigenwert-Zerlegung

Verfahren zur Berechnung der Exponentialmatrix – p.9/14

Page 36: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den

Eigenwerten λ1, . . . , λn

Verfahren zur Berechnung der Exponentialmatrix – p.9/14

Page 37: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den

Eigenwerten λ1, . . . , λn

− Dann gilt A = V diag(λ1, . . . , λn)V −1

Verfahren zur Berechnung der Exponentialmatrix – p.9/14

Page 38: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den

Eigenwerten λ1, . . . , λn

− Dann gilt A = V diag(λ1, . . . , λn)V −1

− Es folgt eA = eV diag(λ1,...,λn)V −1

= V ediag(λ1,...,λn)V −1

Verfahren zur Berechnung der Exponentialmatrix – p.9/14

Page 39: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Zugang über Eigenwert-Zerlegung− Seien v1, . . . , vn die Eigenvektoren von A zu den

Eigenwerten λ1, . . . , λn

− Dann gilt A = V diag(λ1, . . . , λn)V −1

− Es folgt eA = eV diag(λ1,...,λn)V −1

= V ediag(λ1,...,λn)V −1

− Es ergibt sich eA = V diag(eλ1 , . . . , eλn)V −1

Verfahren zur Berechnung der Exponentialmatrix – p.9/14

Page 40: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Splitting Methode

Verfahren zur Berechnung der Exponentialmatrix – p.10/14

Page 41: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C

Verfahren zur Berechnung der Exponentialmatrix – p.10/14

Page 42: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C

− Die Funktionalgleichung ex+y = exey gilt fürMatrizen im Allgemeinen nicht.

Verfahren zur Berechnung der Exponentialmatrix – p.10/14

Page 43: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C

− Die Funktionalgleichung ex+y = exey gilt fürMatrizen im Allgemeinen nicht.

− Es gilt legiglich die folgende Äquivalenz:

eB+C = eBeC ⇐⇒ BC = CB

Verfahren zur Berechnung der Exponentialmatrix – p.10/14

Page 44: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Weitere Verfahren zur Berechnungvon eA

• Splitting Methode− Ausgangspunkt: Zerlegung A = B + C

− Die Funktionalgleichung ex+y = exey gilt fürMatrizen im Allgemeinen nicht.

− Es gilt legiglich die folgende Äquivalenz:

eB+C = eBeC ⇐⇒ BC = CB

− Es gilt jedoch die Trotter-(Produkt-)Formel:

eB+C = limm→∞

(

eB/meC/m)m

Verfahren zur Berechnung der Exponentialmatrix – p.10/14

Page 45: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Ziele der Diplomarbeit:

• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C

2n×2n

Verfahren zur Berechnung der Exponentialmatrix – p.11/14

Page 46: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Ziele der Diplomarbeit:

• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C

2n×2n

• Folgende Aspekte sind zu berücksichtigen:

Verfahren zur Berechnung der Exponentialmatrix – p.11/14

Page 47: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Ziele der Diplomarbeit:

• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C

2n×2n

• Folgende Aspekte sind zu berücksichtigen:− Effizienz

Verfahren zur Berechnung der Exponentialmatrix – p.11/14

Page 48: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Ziele der Diplomarbeit:

• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C

2n×2n

• Folgende Aspekte sind zu berücksichtigen:− Effizienz− Numerische Stabilität

Verfahren zur Berechnung der Exponentialmatrix – p.11/14

Page 49: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Ziele der Diplomarbeit:

• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C

2n×2n

• Folgende Aspekte sind zu berücksichtigen:− Effizienz− Numerische Stabilität− Parallelisierbarkeit

Verfahren zur Berechnung der Exponentialmatrix – p.11/14

Page 50: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Ziele der Diplomarbeit:

• Untersuchung und Implementierung derverschiedenen Verfahren zur Berechnung vone−itH mit jeweils fester Matrix H ∈ C

2n×2n

• Folgende Aspekte sind zu berücksichtigen:− Effizienz− Numerische Stabilität− Parallelisierbarkeit− Ausnutzen der speziellen Struktur von H

H = D + C = diag(d1, . . . , dN ) + C1 ⊗ · · · ⊗ Cn

Verfahren zur Berechnung der Exponentialmatrix – p.11/14

Page 51: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Wie kann man die Struktur von H ausnutzen?

• H = D + C

Verfahren zur Berechnung der Exponentialmatrix – p.12/14

Page 52: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Wie kann man die Struktur von H ausnutzen?

• H = D + C

• Anwendung der Splitting-Methode

e−iHt = e−it(D+C) ≈(

e−itD/me−itC/m)m

Verfahren zur Berechnung der Exponentialmatrix – p.12/14

Page 53: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Wie kann man die Struktur von H ausnutzen?

• H = D + C

• Anwendung der Splitting-Methode

e−iHt = e−it(D+C) ≈(

e−itD/me−itC/m)m

• Direkte Berechnung von e−itD/m und e−itC/m

Verfahren zur Berechnung der Exponentialmatrix – p.12/14

Page 54: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Wie kann man die Struktur von H ausnutzen?

• H = D + C

• Anwendung der Splitting-Methode

e−iHt = e−it(D+C) ≈(

e−itD/me−itC/m)m

• Direkte Berechnung von e−itD/m und e−itC/m

− D ist Diagonalmatrix

Verfahren zur Berechnung der Exponentialmatrix – p.12/14

Page 55: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Wie kann man die Struktur von H ausnutzen?

• H = D + C

• Anwendung der Splitting-Methode

e−iHt = e−it(D+C) ≈(

e−itD/me−itC/m)m

• Direkte Berechnung von e−itD/m und e−itC/m

− D ist Diagonalmatrix− Die Eigenvektoren von C sind gerade die

Spalten von F2 ⊗ · · · ⊗ F2

Verfahren zur Berechnung der Exponentialmatrix – p.12/14

Page 56: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Wie kann man die Struktur von H ausnutzen?

• H = D + C

• Anwendung der Splitting-Methode

e−iHt = e−it(D+C) ≈(

e−itD/me−itC/m)m

• Direkte Berechnung von e−itD/m und e−itC/m

− D ist Diagonalmatrix− Die Eigenvektoren von C sind gerade die

Spalten von F2 ⊗ · · · ⊗ F2

• Wiederholtes Quadrieren für m = 2k

Verfahren zur Berechnung der Exponentialmatrix – p.12/14

Page 57: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

• Ausnutzung der Persymmetrie

Verfahren zur Berechnung der Exponentialmatrix – p.13/14

Page 58: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

• Ausnutzung der Persymmetrie

• Transformation von H auf reelle Matrix H̃

H̃ =

(

A1 rE

rE A2

)

Verfahren zur Berechnung der Exponentialmatrix – p.13/14

Page 59: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

• Ausnutzung der Persymmetrie

• Transformation von H auf reelle Matrix H̃

H̃ =

(

A1 rE

rE A2

)

• H̃ ist ähnlich zur Matrix(

A1 + A2 + 2rE 0

0 A1 + A2 − 2rE

)

Verfahren zur Berechnung der Exponentialmatrix – p.13/14

Page 60: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

• Ausnutzung der Persymmetrie

• Transformation von H auf reelle Matrix H̃

H̃ =

(

A1 rE

rE A2

)

• H̃ ist ähnlich zur Matrix(

A1 + A2 + 2rE 0

0 A1 + A2 − 2rE

)

• Reduktion des Problems der EW/EV-Zerlegungauf zwei Matrizen halber Größe

Verfahren zur Berechnung der Exponentialmatrix – p.13/14

Page 61: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Offene Fragen

• Kann die Struktur von H auch bei weiterenVerfahren (ODE,Padé,...) ausgenutzt werden?

Verfahren zur Berechnung der Exponentialmatrix – p.14/14

Page 62: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Offene Fragen

• Kann die Struktur von H auch bei weiterenVerfahren (ODE,Padé,...) ausgenutzt werden?

• Wie pessimistisch sind dieKonvergenzabschätzungen in unserem Fall?

Verfahren zur Berechnung der Exponentialmatrix – p.14/14

Page 63: Verfahren zur Berechnung der Exponentialmatrix · Weitere Verfahren zur Berechnung von eA • Splitting Methode − Ausgangspunkt: Zerlegung A = B + C − Die Funktionalgleichung

Inhalt der Diplomarbeit

Offene Fragen

• Kann die Struktur von H auch bei weiterenVerfahren (ODE,Padé,...) ausgenutzt werden?

• Wie pessimistisch sind dieKonvergenzabschätzungen in unserem Fall?

• Wie lässt sich die Matrix-Matrix Multiplikationmöglichst schnell berechnen?

Verfahren zur Berechnung der Exponentialmatrix – p.14/14