Computerphysik und Numerik - jkrieger.dejkrieger.de/download/computerphysik.pdf · 2006. 7. 23. · Inhaltsverzeichnis •Es gilt bei nExponentenbits mit obigen Benennungen: E:= C−BIAS

Computerphysik und Numerik

Jan Krieger

23. Juli 2006

Inhaltsverzeichnis

1. Allgemeine Definitionen 51.1. Numerischer Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.2. Gleitkommadarstellung und Rundung . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.3. IEE754-Standard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61.4. Konditionierung und Stabilität . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71.5. Sammlung von Grundregeln der Numerik . . . . . . . . . . . . . . . . . . . . . . . . . 8

2. Grundaufgaben 102.1. quadratische Gleichungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.2. Polynome auswerten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

3. Lineare Algebra am Computer 113.1. Lösen von Gleichungssystemen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

3.1.1. Störungstheorie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.1.2. Dreiecks-Matritzen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1.3. Gauss-Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133.1.4. Gauss-Jordan-Elimination . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143.1.5. LU-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153.1.6. Cholesky-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163.1.7. Zusammenstellung der Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . 18

3.2. Eigentwertprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193.2.2. Jacobi-Methode für reel-symmetrische Matritzen . . . . . . . . . . . . . . . . . 193.2.3. Givens-Householder-Reduktion auf Tridiagonalform . . . . . . . . . . . . . . . 213.2.4. QL/QR-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 243.2.5. Zusammenstellung der Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . 263.2.6. Anwendung: Lineare Variatios-Methode in der Quantenphysik . . . . . . . . . . 27

4. Numerische Integration 304.1. Quadraturformel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304.2. Simpson’s Regel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

5. Gewöhnliche Differentialgleichungen 315.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 315.2. Euler-Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335.3. Allgemeine Taylor-Reihen Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345.4. Runge-Kutta-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

5.4.1. Runge-Kutta-Verfahren zweiter Ordnung . . . . . . . . . . . . . . . . . . . . . 355.4.2. Runge-Kutta-Verfahren vierter Ordnung . . . . . . . . . . . . . . . . . . . . . . 365.4.3. Allgemeines Runge-Kutta-Verfahren . . . . . . . . . . . . . . . . . . . . . . . . 385.4.4. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

5.5. Schrittweitenkontrolle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405.6. Numerov-Algorithmus und Shooting-Methode . . . . . . . . . . . . . . . . . . . . . . . 41

5.6.1. Numerov-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 415.6.2. Shooting-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5.7. Duffing-Oszillator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43

2

Inhaltsverzeichnis

5.7.1. Einführung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.7.2. Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 445.7.3. Stabilitätsanalyse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.8. Zwei- und Drei-Körper-Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.8.1. Das Zweikörperproblem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485.8.2. Das allgemeine n-Körper-Problem . . . . . . . . . . . . . . . . . . . . . . . . . 505.8.3. Der Leap-Frog–Integrator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 515.8.4. Verlet-Integrator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.8.5. Das Hermite-Schema . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545.8.6. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

5.9. Populationsdynamik und Ratengleichungen . . . . . . . . . . . . . . . . . . . . . . . . 555.9.1. Einzelne Populationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 555.9.2. Interagierende Populationen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5.10. Lorenz-Atraktor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565.11. Zusammenstellung der Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

6. Diskrete Dynamik 626.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626.2. Definitionen und Sätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.3. Logistische Abbildung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

6.3.1. Fixpunkte . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 666.3.2. Feigenbaum-Konstante und Lyapunov-Exponent . . . . . . . . . . . . . . . . . 676.3.3. C++-Programme zur Berechnung . . . . . . . . . . . . . . . . . . . . . . . . . 68

6.4. Periodisch getriebener Rotator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7. Zufallszahlen 747.1. Erzeugung gleichverteilter Zufallszahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 74

7.1.1. Zufallszahlen im GNU C-Compiler . . . . . . . . . . . . . . . . . . . . . . . . 747.1.2. Linear Kongruente Generatoren (LCGs) . . . . . . . . . . . . . . . . . . . . . . 757.1.3. Multiplikativ Kongruente Generatoren (MCGs) . . . . . . . . . . . . . . . . . . 76

7.2. Erzeugung von Zufallszahlen mit vorgegebener Verteilung . . . . . . . . . . . . . . . . 787.2.1. Transformations-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787.2.2. Rejection-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

7.3. Zusammenstellung der Verfahren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

8. Monte-Carlo-Methoden 858.1. Einfache Monte-Carlo-Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85

8.1.1. Beispiel: Wie man π erschießt . . . . . . . . . . . . . . . . . . . . . . . . . . . 868.2. Integration mit Importance Sampling . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868.3. Monte-Carlo Simulationen: Der Metropolis-Algorithmus . . . . . . . . . . . . . . . . . 878.4. Beispiel: Das Ising-Modell . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 88

8.4.1. Beschreibung des Modells . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 888.4.2. Mean-Field-Näherung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 898.4.3. Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908.4.4. Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

8.5. Der Random-Walk . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

A. utils.h-Paket 94

B. GSL-GNU Scientific Library 96

List of Algorithms 97

Listings 98

c© 2004-2006 by Jan Krieger (http://www.jkrieger.de/) – 3 –

http://www.jkrieger.de/

Inhaltsverzeichnis

Literaturverzeichnis 101



1. Allgemeine Definitionen

1.1. Numerischer Algorithmus

Ähnlich wie in der (theoretischen) Informatik kann man einen numerischen Algorithmus als endliche,deterministische Abfolge einfacher (elementarer) Anweisungen auffassen. Er stellt ein Rechenverfahrendar, das eine Eingabe x in eine Ausgabe y, bzw. ihren Näherungswert y überführt.

Formal kann man das so fassen:

Numerischer Algorithmus: Gegeben sei eine numerische Aufgabe in der Form y = f(x), mit f :Rn → Rm. Unter einem Algorithmus zu deren Lösung versteht man eine Abfolge von k Elementaroperationen/-abbildungen ϕ(1)...ϕ(k), dere skzessive Anwendung die Näherungslösung y der Aufgabe liefert:

y = (ϕ(k) ... ϕ(1))x

Benutzt man Zwischenergebnisse x(1)...x(k−1), so gilt:

x(1) = ϕ(1)(x) → x(2) = ϕ(2)(x(1)) → ... → y = ϕ(k)(x(k−1)).

Ein solcher Algorithmus lässt sich meißt einfach auch in gebräuchlichen Programmiersprachen dar-stellen. In obiger Form ist er sogar sehr einfach in funktionalen Programmiersprachen, wie etwa Haskellimplementierbar.

1.2. Gleitkommadarstellung und Rundung

• IEEE-Gleitkommadarstellung: Die Gleitkommadarstellung ermöglicht es Zahlen über einen wei-ten Größenordnungsbereich darzustellen, wobei der gesamte darstellbare Bereich diskret gerastertwerden kann. Für kleine Zahlen gibt es viele Rasterpunkte und hin zu größeren, werden es weniger.Jede Zahl x ∈ R hat dann die folgende Darstellung:

x = ±m · b±e.

Dabei ist m die Mantisse, b ∈ N die Basis und e der Exponent. In Computern können nur Zahlenmit endlich vielen Stellen dargestellt werden:

r Ziffern für die Mantisse ms Ziffern für den Exponenten e

Damit erhält man also:

x = ±[m1b

−1 +m2b−2 + ...+mrb

−r]· b±[es−1bs−1+...+e0b0].

Diese darstellbaren Zahlen heißen Maschinenzahlen. Sie bilden das numerische Gleitkommagitter,das die Zahlen in obiger Weise rastert.Damit gibt es größte und kleinste darstellbare Zahlen:

xmax/min = ±(1− b−r) · bbs−1

xposmin/negmax = ±b−bs

5

Inhaltsverzeichnis

• Rundungsoperator rd: Ein Rundungsoperator nimmt die Rundung einer Zahl auf eine vorgege-bene Anzahl von Stellen vor. Er ist eine Abbildung rd : D → A, wobei D der zulässige Bereichfür die Zahlen in der Rechnung ist und A die Menge der Maschinenzahlen, im entsprechendenSystem (z.B. IEEE). Der Rundungsoperator muss folgende Forderung erfüllen:

|x− rd(x)| = miny∈A|x− y| ∀x ∈ D.

Dies bedeutet gerade, dass die Rundung auf die nächstgrößere Zahl aus A erfolgt. Mit der Run-dung ist ein sog. absoluter Rundungsfehler verbunden, der sich bei der IEEE-Darstellung wie folgtergibt:

|x− rd(x)| ≤ 12b−rbe.

Analog erhält man den relativen Rundungsfehler:∣∣∣∣x− rd(x)x

∣∣∣∣ ≤ 12b−rbe

|m| be≤ 1

2b−r+1

Bei dieser Rechnung wurde die größtmögliche Mantisse |m| = 1 · b−1 angenommen.

• Maschinengenauigkeit: Als Maschinengenauigkeit eps wird nun die Beschränkung des relativenRundungsfehlers definiert:

eps :=12b−r+1

Sie entspricht damit auch dem kleinesten möglichen Inkrement der Mantisse und hängt somitmit der Auflösung der Zahlen in einem bestimten Größenordnungsbereich zusammen. Für real-Typen erhält man epsreal = 1

22−23 ≈ 10−7. Für double-Typen gilt epsdouble = 122−52 ≈ 10−16.

Es gilt:rd(x) = x · (1 + ε) mit |ε| ≤ eps

• Maschinenoperationen: Durch die Rundung werden die üblichen arithmetischen Operationen+,−,×, / durch entsprechende Maschinenoperationen ⊕,,⊗, ersetzt, die die Rundung desErgebnisses berücksichtigen und nicht mehr das exakte Ergebnis liefern müssen, also fehlerbehaf-tet sind:

x~ y = rd(x ∗ y) = (x ∗ y) · (1± ε), 0 ≤ ε ≤ eps

Jede Operation erzeugt also einen Rundungsfehler in der Größenordnung der Maschinengenauig-keit. Man muss also bei N arithmetischen Operationen mindestens mit einem Gesamtfehler von√N · eps rechnen. Die Fehler treten gleichverteilt in beide Richtungen auf, sodass man sich den

Vorgang wie einen Random-Walk vorstellen kann, dessen Größe mit√N wächst (daher die Wur-

zel). Dabei ist aber zu beachten, dass diese Abschätzung sehr konservativ ist, da die Rundungs-fehler auch viel größer als eps sein können und es zusätzlich den Effekt der Fehlerverstärkunggibt.

1.3. IEE754-Standard

• Gleitkommadarstellung einer Zahl z mit single precission nach IEEE 754:

Bits: 31 30..23 22..0Bedeutung: Sign S Charakteristik C Mantisse M

Zuordnung: S e7..e0 m−1..m−23

• Gleitkommadarstellung einer Zahl z mit double precission nach IEEE 754:

Bits: 63 62..52 52..0Bedeutung: Sign S Charakteristik C Mantisse M

Zuordnung: S e10..e0 m−1..m−52



Inhaltsverzeichnis

• Es gilt bei n Exponentenbits mit obigen Benennungen: E := C − BIAS mit BIAS = 2n−1 − 1,

C M Wert255 (2047) 0 INF (∞)255 (2047) 6= 0 NaN (not a number)

0 0 00 6= 0 (−1)S ·

(∑−ki=−1mi2i

)· 2−126

0 < C < 255 (2047) beliebig (−1)S ·(1 +

∑−ki=−1mi2i

)· 2C−BIAS

• Addition:

1. Angleichen des kleineren an den größeren Exponenten

2. Addition der Mantissen

3. Normalisierung, Rundung ...

• Multiplikation:

1. Multiplizieren der Vorzeichen

2. Multiplizieren der Mantissen

3. Addition der Exponenten:

Charerg = (Char1−BIAS) + (Char2−BIAS) + BIAS = Char1 +Char2−BIAS

4. 4. Normalisierung, Rundung ...

• Zusammenfassung der Eigenschaften von einfach- und doppelt-genauen Gleitkommazahlennach IEEE:

einfach genau doppelt genauVorzeichenstellen 1 1Exponentenstellen 8 11Mantissenstellen 23 52Bits insgesamt 32 64BIAS 127 1023Exponentenbereich -126 bis 127 -1022 bis 1023Darstellunsgbereich 2−149...(1− 2−24) · 2128 2−1022...(1− 2−53) · 21024

1.4. Konditionierung und Stabilität

• Konditionierung: Die Konditionierung einer numerischen Aufgabe gibt an, wie „gut“ sich ei-ne gegebene Aufgabe auf einem Computer lösen lässt, also wie stark kleine Anfangsfehler derEingaben in das Ergebnis hineinspielen. Eine numerischer Aufgabe sei hier die Bestimmung vonGrößen y ∈ Rn aus gegebenen Größen x ∈ Rm, die mittels einer Rechenvorschrift (Funktion)f(·) verknüpft sind:

y = f(x).

Den absoluten Fehler ∆yi in erster Ordnung der i-ten Komponente erhält man aus einer Taylor-Entwicklung der Funktion f :

∆yi = fi(x+ ∆x)− fi(x) =m∑

j=1

∂fi

∂xj(x) ·∆xj +O(|∆x|)



Inhaltsverzeichnis

Deren relativen Fehler erhält man zu:

∆yi

yi=

m∑j=1

∂fi

∂xj(x) · ∆xj

yi+O(

|∆x|2

|yi|) =

m∑j=1

∂fi

∂xj(x) · xj

fi(x)︸︷︷︸=:kij(x)

·∆xj

xj+O(

|∆x|2

|yi|)

Die so gefundenen Größen kij bezeichnet man als (relative) Konditionszahlen. Eine Aufgabeheißt schlecht konditioniert, wenn |kij | 1 und gut konditioniert anderenfalls. Für |kij | > 1 liegtFehlerverstärkung und für |kij | < 1 Fehlerdämpfung vor. Die Konditionszahlen geben an, wiesich ein relativer Fehler der Eingabedaten durch den Algorithmus fortsetzt, also welchen Einflusser auf den relativen Fehler der Ausgabe hat.

• Fehler der Addition/Subtraktion: Man betrachte y = f(x1, x2) = x1 + x2, mit x1, x2 ∈R, x1, x2 6= 0. Dafür erhält man:

k1 =∂f

∂x1

x1

f=

x1

x1 + x2=

11 + x2/x1

k2 =∂f

∂x2

x2

f=

x2

x1 + x2=

11 + x1/x2

Eine solche Addition ist also schlecht konditioniert, falls die Zahlen ähnlich groß, aber mit unter-schioedlichem Vorzeichen sind (x1/x2 ≈ −1).

• Auslöschung bei Subtraktion: Die Auslöschung ist der Verlust an wesetlichen Dezimalstellenbei der Subtraktion zweier Zahlen mit gleichem Vorzeichen.

• Fehler der Multiplikation: Man betrachte y = f(x1, x2) = x1 · x2, mit x1, x2 ∈ R, x1, x2 6= 0.Dafür erhält man:

k1 =∂f

∂x1

x1

f=x1 · x2

x1 · x2= 1 = k2

Damit ist die Multiplikation generell gut konditioniert.

• Fehler der Division: Man betrachte y = f(x1, x2) = x1/x2, mit x1, x2 ∈ R, x1, x2 6= 0. Dafürerhält man:

k1 =∂f

∂x1

x1

f=

1x2

x1

x1/x2= 1

k2 =∂f

∂x2

x2

f=−x1

x22

x2

x1/x2= −1

Die Division ist also ebenfalls generell gut konditioniert.

• Stabilität numerischer Algorithmen: Ein numerischer ALgorithmus heißt stabil, wenn die inseinem Verlauf auftretenden aufaddierten Fehler, den durch die Konditionierung vorgegebenenProblemfehler nicht überschreiten.

1.5. Sammlung von Grundregeln der Numerik

1. Bei der Durchführung einer numerischen Berechnung sollten die schlecht konditionierten Schrittemöglichst früh angewendet werden, damit die durch sie entsehenden Fehler nicht weiter verstärktwerden.

2. Prüfung des numerischen Verfahrens an bekannten Testfällen (siehe z.B. Evaluation des Euler-Verfahrens in 5.2)

3. Bei Funktionen mit wenig Rechenaufwand sollte man inline-Funktionen oder Makros verwenden,um den Overhead durch den Funktionsaufruf zu vermeiden. Dies ist vor Allem wichtig, wenn dieRoutine oft aufgerufen wird.



Inhaltsverzeichnis

4. Physikalische Probleme sollten in eine dimensionslose Form gebracht werden. Dann löst mannämlich nicht nur ein spezielles Problem, sondern eine ganze Klasse ähnlicher Probleme. Dazunormiert man alle auftretenden Größen auf Referenzgrößen. Dabei sollte darauf geachtet werden,dass die sich ergebenden Größen alle die selbe Größenordnung haben, um den Auflösungsbe-reich von Gleitkommaarithmetik möglichst gut auszunutzen (bei Verknüpfung sehr unterschied-lich großer Zahlen können Dezimalstellen verloren gehen, das vor der Operation die Zahlen aufgleiche Exponenten gebracht werden müssen!)



2. Grundaufgaben

2.1. quadratische Gleichungen

Man betrachte die folgende Quadratische Gleichung

y2 + p · y − q = 0, p, q ∈ R; q 6= 0

und ihre Lösung:

y1,2 =p

2±√p2

4− q, mit p = y1 + y2; q = y1 · y2

Diese Aufgabe ist für y1/y2 ≈ 1 schlecht konditioniert. Dies erhält man durch Ausnutzung der obigenBeziehungen für y1, y2, p, q:

∂y2

∂p=

y2

y2 − y1;

∂y1

∂p=

y1

y2 − y1;

∂y1

∂q= −∂y2

∂p=

1y1 − y2

.

Damit kommt man auf die Konditionszahlen

k11 =∂y1

∂p

p

y1=

1 + y2/y1

1− y2/y1und k12 =

11− y2/y1

.

2.2. Polynome auswerten

Man betrachte eine numerische Berechnungsaufgabe der folgenden Form:

y = p(x) = a0 + a1x+ a2x2 + ...+ anx

n

Bei der Auswertung solcher Polynome spart man einige Rechenoperationen, wenn man das Horner-Schema anwendet, also die Berechnung nach folgendem Muster vornimmt:

y = p(x) = a0 + x · (a1x+ x · (a2 + ...+ x · (an−1 + anx)...))

10

3. Lineare Algebra am Computer

3.1. Lösen von Gleichungssystemen

Eine der Grundaufgaben der linearen Algebra ist das Lösen von linearen Gleichungssystemen. Sie habendie folgende allgemeine Form, mit einer bekannten Matrix A = (aij) und einem bekannten Vektor~b = (bi). Das Ziel ist einen Vektor ~x = (xi) zu finden, der die Gleichung löst: a11 . . . a1N

.... . .

...aM1 . . . aMN

·x1

...xN

=

b1...bN

⇔ A · ~x = ~b (3.1.1)

Es liegen also M Gleichungen für N Unbekannte Größen vor. Solche Gleichungssysteme heißen imFalle M < N unterbestimmt. Es kann dann keine eindeutige Lösung angegeben werden. Allerdingskann man einen höherdimensionalen Lösungsraum angeben, also einen Vektor xb, zu dem eine Linear-kombination anderer Vektoren addiert werden kann, so dass das Ergebnis die Gleichung löst. Im FalleM > N sind sie überbestimmt und es kann Lösungen geben, die alle Gleichungen erfüllen. Manchmalmöchte man bei überbestimten Gleichungssystemen die „beste“ Lösung finden, also eine Lösung, die alleGleichungen möglichst gut erfült. Man kann die Güte einer Lösung z.B. über den „least-square“-Abstanddefinieren und kommt so zu lienaren „least-square“-Problemen.

Im FalleM = N gibt es eine gute Chance eine eindeutige Lösung zu finden, allerdings nur dann wennalle Spalten- bzw. Zeilenvektoren linear unabhängig sind. Andernfalls lässt sich das Gleichungssystemauf ein unterbestimmtes System zurückführen. Die folgenden Aussagen sind äquivalent:

• A~x = ~b ist für jedes~b eindeutig lösbar.

• Rang(A) = n.

• det(A) 6= 0.

• Alle Eigenwerte von A sind ungleich null.

Aus numerischer Sicht gibt es zwei zusätzliche Fehlerquellen:

1. Sind eine Gleichungen nahezu linear abhängig, so kann es sein, dass der Algorithmus aufgrund vonRundungsfehlern zu dem Ergebnis kommt, dass sie dies tatsächlich sind und somit kein Ergebnisliefert.

2. Numerische Fehler können sich aufhäufen und dazu führen, dass der ALgorithmus zwar ein Er-gebnis liefert, dieses aber (auch in numerische Grenzen) falsch ist.

Nach [Numerical Recipies Software 1992] kann man folgende Faustregeln für die numerisch sinnvolleLösbarkeit annehmen. Sie hängt aber auch stark von der Beschaffenheit der Matrizen ab:

• single precision: Sicheres Lösen von Gleichungssystemen mit N = 20...50

• double precision: Sicheres Lösen von Gleichungssystemen mit N < 1000

Systeme mit tausenden von Gleichungen können können mit speziellen Verfahren gelöst werden, wennsie dünn besetzt sind (fast alles 0), wie etwa Bandmatritzen etz.

11

Inhaltsverzeichnis

3.1.1. StörungstheorieHilfssatz zum Störungssatz: Die Matrix B ∈ Kn×n habe die Norm ‖B‖ < 1. Dann ist die MatrixEn +B regulär und es gilt: ∥∥(En +B)−1

∥∥ ≤ 11− ‖B‖

Störungssatz: Die Matrix A ∈ Kn×n sei regulär und werde durch eine Matrix δA ∈ Kn×n gestört,für die gilt:

‖δA‖ < 1‖A−1‖

.

Dann ist die gestörte Matrix A = A+ δA ebenfalls regulär und für den relativen Fehler der Lösung deszugehörigen Gleichungssystems Ax = b gilt:

‖δx‖‖x‖

≤ cond(A)1− cond(A) ‖δA‖ / ‖A‖

·(‖δb‖‖b‖

+‖δA‖‖A‖

)Dabei ist condA := ‖A‖ ·

∥∥A−1∥∥ die bereits vorher definierte Konditionszahl einer Matrix.

Gilt zusätzlich, dass cond(A) · ‖δA‖‖A‖ 1, so wird aus obiger Ungleichung:

‖δx‖‖x‖

≤ cond(A) ·(‖δb‖‖b‖

+‖δA‖‖A‖

)Man sieht also, dass die Konditionszahl gerade die Verstärkung von Fehlern im Gleichungssystem angibt.Eine große Konditionszahl bedeutet also, dass die Lösung empfindlich auf kleine Störungen der Matrixund/oder von b reagiert. Man kann daraus über eine einfache Abschätzung ersehen, dass man s Stellenim Ergebnis verliert, wenn die Konditionszahl in der Größenordnung 10s liegt:

Es sei cond(A) ≈ 10s und ‖δA‖‖A‖ ≈ 10−k und ‖δb‖

‖b‖ ≈ 10−k. Dann gilt nach obigem Störungssatz:‖δx‖‖x‖ ≈ 10s−k.

einfache Variante des Störungssatzes: Man betrachtet ein Gleichungssystem, bei dem nur ~x gestörtwird:

A(~x+ δ~x) = ~b+ δ~b, A~x = ~b

Dabei ist natürlich δ~b = A · δ~x. Man erhält dann durch erweitern und umformen:

‖δ~x‖ =∥∥∥A−1 · δ~b

∥∥∥ ≤∥∥A−1

∥∥ · ∥∥∥δ~b∥∥∥≤

∥∥A−1∥∥ · ‖A~x‖‖A~x‖

·∥∥∥δ~b∥∥∥

≤∥∥A−1

∥∥ · ‖A‖ · ‖~x‖∥∥∥~b∥∥∥ ·∥∥∥δ~b∥∥∥

Daraus ergibt sich dann durch Umformung das einfache Ergebnis:

‖δ~x‖‖~x‖

≤ cond(A) ·

∥∥∥δ~b∥∥∥∥∥∥~b∥∥∥



Inhaltsverzeichnis

3.1.2. Dreiecks-MatritzenOft (z.B. bei der Gauss-Elimination 3.1.3) kommen (rechte obere) Dreieckmatritzen R vor. Die aus ihnenaufgebaurten Gleichungssysteme R~x = ~c können besonders leicht gelöst werden.

r11x1 + r12x2 + . . . + r1NxN = c1r22x2 + . . . + r2NxN = c2

...rNNxN = cN

(3.1.2)

Ein solches System (3.1.2) lässt sich leicht in O(N2) Schritte lösen:

xN =cNrNN

(3.1.3)

xN−1 =1

rN−1,N−1· (cN−1 − rN−1,NxN ) (3.1.4)

xj =1rjj·

cj − N∑k=j+1

rjkxk

(3.1.5)

3.1.3. Gauss-EliminationFolgende Operationen an einem Gleichungssystem der obigen Form (3.1.1) ändern nichts am Lösungs-vektor x:

1. Austauschen zweier Zeilen des Gleichungsystems (also der Matrix und des Vektors~b)

2. Austauschen einer beliebigen Zeile des Gleichungssystems durch eine Linearkombination von sichselbst und einer anderen Zeile des Systems.

3. Das Vertauschen zweier Spalten ist ebenfalls möglich, ändert aber die Reihenfolge der Ergebnissein ~x, sodass auch dort eine Vertuaschung durchgeführt werden muss.

Die Gauss-Jordan-Elimination nutzt eine oder mehrere der obigen Operationen 1-3, um die Matrix Aauf die Einheitsmatrix zu reduzieren. Danach steht rechts die Lösung des Systems. Eigentlich genügtes eine rechte obere Dreiecksmatrix zu erzeugen, da ein solches System R · ~x = ~c in O(n2) Schrittendurch elementares Einsetzen gelöst werden kann. Es ist intuitiver das Gleichungssystem in der folgendenSchreibweise zu notieren: a11 . . . a1N b1

.... . .

......

aM1 . . . aMN bN

(3.1.6)

Das Verfahren läuft auf der zusammengesetzten Matrix (3.1.6) reltiv einfach ab:

1. Die erste Zeile wird durch a11 dividiert, sodass an erster Stelle eine 1 steht:

a11 = a11/a11 = 1; a1i = a1i/a11; b1 = b1/a11 (3.1.7)

2. Nun wird von jeder Zeile j das aj1-fache der ersten Zeile abgezogen. Dadurch wird die erste Spalteauf die Form des Einheitsmatrix gebracht.

aj1 = aj1 − 1 · aj1 = 0; aji = aji − a1i · aj1; bj = bj − b1 · aj1. (3.1.8)

3. nun betrachtet man nur noch die rechte untere, (N − 1) × (N − 1)-dimensionale Teilmatrix undfängt mit ihr bei Schritt 1 wieder von vorne an. Dabei entspricht jetzt also das dortige Element a11

dem wharen Element a22: a11 . . . a1N b1...

. . ....

...aN1 . . . aNN bN

→

1 a12 . . . a1N b10...0

a22 . . . a2N b2...

. . ....

...aN2 . . . aNN bN

(3.1.9)



Inhaltsverzeichnis

Dieses elementare Verfahren funktioniert solange, wie nicht durch 0 dividiert wird. Um diesen Fall zuvermeiden und das Verfahren numerisch stabil zu machen, wird eine Pivot-Suche durchgeführt. Die Ideeist es das Element a11, durch das dividiert wird gezielt auszuwählen. Welches Element man am bestenauswählt ist theoretisch nicht ganz klar. Es hat sich aber als gutes Faustregel erwiesen jeweils das größteElement auszusuchen. Es gibt nun zwei mögliche Pivot-Suchen:

1. Spalten-Pivot-Suche: Man such das Pivot-Element nur in der ersten Spalte des Verfahrens. Ist dasgrößte Element p := max

1≤i≤N|ai1| gefunden, so wird es durch eine einfache Zeilenvertauschung der

ersten und der i-ten Zeile positioniert. Das hat den Vorteil, dass sich nichts an der Reihenfolge derElemente in ~x ändert.

2. totale Pivot-Suche: Es wird in der gesamten N × N -Matrix gesucht. Man benötigt dann nochSpaltenvertauschungen, um das Pivot-Element p an die Position 1, 1 in der Matrix zu befördern.Man muss also zusätzlich die richtige Reihenfolge der Elemente in ~x speichern, um nicht einwertloses Ergebnis auszugeben.

Die Pivot-Suche bietet außerdem noch den Vorteil, dass ein Gleichungssystem genau dann nicht lösbarist, wenn eine ganze Unterspalte 0 ist, also keine Pivot-Element 6= 0 gefunden werden kann.Der Gauss-Algorithmus hat eine Komplexität O(N3), da für jede der N -Spalten jeweils O(N2) mathe-matische Operationen (Addition/Multiplikation/Division) durchgeführt werden müssen. Die endgültigeLösung des Systems mit der rechten obere Dreiecksmatrix erfolgt nach 3.1.2 in O(N2) Schritten, wasdie Ordnung des ALgorithmus nicht ändert.

3.1.4. Gauss-Jordan-EliminationDie Gauss-Jordan-Elimination löst nicht ein einfaches Gleichungssystem der Form A · ~x = ~b, son-dern ein ganzes System solcher Gleichungssysteme. Sie ist also die natürliche Erweiterung der Gauss-Elimination:

A · ~xj = ~bj , j = 1, ...,K (3.1.10)

Dies entspricht der Lösung einer Matrix-Gleichung der Form

A ·X = B, A ∈ RN×N , X,B ∈ RN×K (3.1.11)

Wie die einfache Gauss-Elimination auch benutzt die Gauss-Jordan-Elimination eine Reihe von Vertau-schungen und Linearkombinationen, sowie eine Pivot-Suche und wendet sie auf das folgende Koeffizi-entenschema an: a11 . . . a1N b11 . . . b1K

.... . .

......

. . ....

aN1 . . . aNN bN1 . . . bNK

(3.1.12)

Dies enstrpciht einfach der simultanen Lösung des Gleichungssystems A~x = ~bi, fürK Vektoren~bi. Mansieht das sofort, wenn man die Matrixmultiplikation A ·X explizit ausführt:

A·X =

a11x11 + ...+ a1NxK1 a11x12 + ...+ a1NxK2 . . . a11x1K + ...+ a1NxKK

a21x11 + ...+ a2NxK1 a21x12 + ...+ a2NxK2 . . . a21x1K + ...+ a2NxKK... . . .

...aN1x11 + ...+ aNNxK1 aN1x12 + ...+ aNNxK2 . . . aN1x1K + ...+ aNNxKK

=

=

...

......

A~x1 A~x2 . . . A~xK...

......

!=

...

......

~b1 ~b2 . . . ~bK...

......

(3.1.13)

Im Gegensatz zu ihrem einfachen Gegenstück wird die Matrix A aber auf die Einheitsmatrix zurückge-führt, nicht nur auf eine obere Dreiecksmatrix. Dazu betrachtet man für den nächsten Schritt nicht nur



Inhaltsverzeichnis

die rechte untere Teilmatrix (in (3.1.9)), sondern subtrahiert auch von den Elementen, die über ihr ste-hen. Mit diesem Verfahren kann man nicht nur ein Gleichungssystem lösen, sondern auch die Inverseeiner Matrix bestimmen. Dazu benutzt man die Gauß-Jordan-Elimination mit N Vektoren ~xi und einerN ×N -Einheitsmatrix auf der rechten Seite (B = 1). Man löst also:

A ·X = 1 ⇔ X = A−1 (3.1.14)

3.1.5. LU-ZerlegungEs gibt noch eine weitere Möglichkeit eine Matrix auf Dreiecksform zu bringen. Angenommen man kanneine Matrix A in folgende Form schreiben (exemplarisch für 4× 4-Matritzen):

L ·U = A

⇔

l11 0 0 0l21 l22 0 0l31 l32 l33 0l41 l42 l43 l44

·u11 u12 u13 u14

0 u22 u23 u24

0 0 u33 u34

0 0 0 u44

=

a11 a12 a13 a14

a21 a22 a23 a24

a31 a32 a33 a34

a41 a42 a43 a44

(3.1.15)

so kann man die Lösung eines Systems A · ~x = ~b in zwei SChritten durchführen, da gilt:

A · ~x = (L ·U) · ~x = L · (U · ~x︸︷︷︸:=~y

) = L · ~y = ~b (3.1.16)

Dies Entspricht der Lösung zweier Gleichungssysteme mit Dreiecksmatritzen, die nach 3.1.2 einfachin quadratischer Zeit gelöst werden können. Zuerst berechnet man dazu ~y aus L · ~y = ~b und erhältschließlich ~x aus U · ~x = ~y.

Das obige Gleichungssystem (3.1.15) hat folgende Form:

a11 = l11u11 a12 = l11u12 a13 = l11u13 a14 = l11u14

a21 = l21u11 a22 = l21u12 + l22u22 a23 = l21u13 + l22u23 a24 = l21u14 + l22u24

a31 = l31u11 a32 = l31u12 + l32u22 a33 = l31u13 + l32u23 + l33u33 a34 = l31u14 + l32u24 + l33u34

a41 = l41u11 a42 = l41u12 + l42u22 a43 = l41u13 + l42u23 + l43u33 a44 = l41u14 + l42u24 + l43u34 + l44u44

(3.1.17)

Dies sind also N2 Gleichungen für N2 + N unbekannte lij , uij . Man hat also einige Freiheiten und eszeigt sich, dass die Setzung

lii := 1, i = 1, ..., N (3.1.18)

immer möglich ist. Wie man in (3.1.17) sieht, lassen sich die Elemente u11, ..., a1N der ersten Zeile vonU leicht ermitteln. Sobald diese bekannt sind (eigentlich genügt u11) kann man die Elemente l21, ..., lN1

der ersten Spalte von L bestimmen. Nun betrachtet man die rechte untere Teilmatrix

(a22 ... a2N

.... . .

...an2 ... aNN

). In

ihr kann wieder elementar in der ersten Zeile und danach der ersten Spalte gerechnet werden. Dies setztsich fort, bis alle Unbekannten berechnet sind. Das Verfahren läuft (wegen der Summierungen inO(N3)Schritten ab und lässt sich algorithmisch wie folgt notieren:

Dieses Verfahren wird Crout’s Algorithmus genannt. Um Speicherplatz zu sparen kann der Algorith-mus so implementiert werden, dass nachher die Matritzen L und U in einer Matrix gespeichert werden,da ja jeweils nahezu die Hälfte der EInträge 0 ist. Außerdem kann man das Verfahren so implementieren,dass das Ergebnis in der Eingabematrix A gespeichert wird, die dabei allerdings überschrieben wird. Daauch in obiger Formel eine Divison erfolgt, muss hier Pivoting eingesetzt werden. Die beiden Formeln inobigem Algorithmus unterscheiden sich nur um den Faktor 1

ujj. Man kann also zuerst nur die Summen/-

Differenzen berechnen und während der zweiten for-Schleife das Pivot-Element suchen. Nachdem alleberechnungen durchgeführt wurden, wird dann evtl. eine Zeilenvertauschung und die Division durch dasPivot-Element ujj durchgeführt.



Inhaltsverzeichnis

For i = 1, 2, ..., N . setze Diagonalelemente von L auf 1lii ← 1

for j = 1, 2, ..., N do . Gehe durch alle Diagonalelemente. Für jedes Element werden ...For i = 1, ..., j . ...die zugehörige Zeile von U ...

uij ← aij −i−1∑k=1

likukj

For i = j + 1, ..., N . ...und dann die Spalte von L berechnet

lij ← 1ujj·

(aij −

j−1∑k=1

likukj

)end for

Algorithme 1: LU-Zerlegung

Die LU-Zerlegung bietet außerdem den Vorteil, dass es relativ einfach ist die Determinante der Matrixzu berechnen. Es gilt nämlich:

detA =N∏

i=1

uii = u11 · u22 · . . . · uNN . (3.1.19)

Dies ist in linearer Zeit O(N) berechenbar. Zusätzlich kann man Gleichungssysteme mit verschiede-nen rechten Seiten b lösen, ohne jedesmal eine neue Zerlegung durchführen zu müssen. Bei der Gauss-Elimination ist dies nötig.

3.1.6. Cholesky-ZerlegungEine Matrix heißt symmetrisch, falls aij = aji für alle i, j = 1, ..., N gilt. Sie heißt positiv definit, wennzusätzlich gilt:

~vt ·A · ~v > 0 ∀~v ∈ Rn (3.1.20)

Eine positiv definite Matrix besitzt nur positive Eigenwerte. Für positiv definite, symmetrische MatritzenA gibt es eine spezielle LU-Zerlegung (siehe 3.1.5), die die folgende Form hat:

L · Lt = A, also U ≡ Lt. (3.1.21)

Dabei ist L eine linke untere Dreiecksmatrix und ihr Transponiertes folglich eine rechte obere Dreiecks-matrix. In dem obigen Schema der LU-Zerlegung ändern sich folglich nur die zwei Summationen. Dortsteht jetzt:

lii =

√√√√aii −i−1∑k=1

l2ik (3.1.22)

lji =1lii·

(aij −

i−1∑k=1

likljk

), j = i+ 1, i+ 2, ..., N (3.1.23)

Ein Pivoting ist hier nicht nötig, da die Cholesky-Zerlegung auch ohne Pivoting stabil ist. Da die Pivot-Suche entfällt kommt die Cholesky-Zerlegung mit etwa der Hälfte der Operationen, wie die LU-Zerlegungaus. Sie ist aber immernoch O(N3). Solche Matritzen sind zwar ein Spezialfall, treten aber z.B. bei derGenerierung von Gauss-verteilten Zufallszahlen auf.

Anwendung: Wenn man Zufallszahlen yi generieren will, die mit einer Kovarianzmatrix C gauß-verteilt sind (also 〈yi〉 = 0 und 〈yi · yj〉 = Cij), so kann man hierzu folgendermaßen vorgehen:

1. erzeuge unabhängige, Gauß-verteilte Zufallszahlen xi (〈xi〉 = 0 und 〈xixj〉 = δij)



Inhaltsverzeichnis

2. erzeuge yi =i∑

k=1

Likxk, mit C = L · Lt.



Inhaltsverzeichnis

3.1.

7.Zu

sam

men

stel

lung

der

Verf

ahre

nVe

rfah

ren

Kom

plex

ität

Mat

rix-

Kla

sse

Bem

erku

ngen

Löse

nvo

nD

reie

cksm

atri

tzen

O(N

2)

Dre

ieck

smat

ritz

en

Gau

ß-Jo

rdan

-Elim

inat

ion

N3 3

+N

2K

belie

bige

Mat

ritz

en•

sim

ulta

nes

Lös

envo

nK

Gle

ichu

ngen

mit

glei

chem

A•

erla

ubtm

itB

=1

die

Inve

rse

Mat

rixA−

1zu

best

imm

en•

pivo

ting

nötig

LU-Z

erle

gung

N3 6

+N

2K

2be

liebi

geM

atri

tzen

•O

(N)-

Ber

echn

ung

derD

eter

min

ante

mög

lich

•pi

votin

gnö

tig•

Lös

ende

sG

lSys

erfo

rder

tAlg

orith

mus

fürd

reie

cksm

atri

t-ze

nzw

eim

alan

zuw

ende

n

Cho

lesk

y-Ze

rleg

ung

1 2L

U-Z

erle

gung

reel

l-sy

mm

etri

sch,

po-

sitiv

defin

it•

wie

LU

-zer

legu

ng,a

berw

enig

erV

aria

blen⇒

wen

iger

Re-

chen

schr

itte

•ke

inpi

votin

gnö

tig



Inhaltsverzeichnis

3.2. Eigentwertprobleme

3.2.1. EinleitungIn der Physik treten oft Eigenwertprobleme auf. So lassen sich etwa quantenmechanische Zustände inder Basis der EIgenzustände eines Hermite’schen Operators darstellen. Man kann auch die möglichenEnergien eines QM-Systems als Eigenwerte des Hamiltonians (H|ψn〉 = En · |ψn〉) bestimmen. Allge-mein stellt sich also die Aufgabe die Eigenwerte λi einer Matrix A = (aij) zu bestimmen. Sie folgen derbekannten Gleichung und Bedingung:

A~vi = λi~vi; det(A− λ · 1) = 0 (3.2.1)

Es gibt einige spezielle Klassen von Matritzen, für die die Eigenwerte spezielle Eigenschaften haben:

• Unitäre Matritzen (A−1 = A† = (A∗)t):Zu jeder unitären Matrix A gibt es eine unitäre Matrix S, sodass S−1 · A · S = S† · A · S =diag(λ1, ..., λn) die selben Eigenwerte λ1, ..., λn wie A hat. Außerdem ist |λi| = 1 und S bestehtaus den EIgenvektoren von A.

• Orthogonale Matritzen (A−1 = At, At ·A = A ·At = 1):Da die orthogonalen Matritzen gerade die reellen unitären Matritzen sind, haben sie dieselbenEigenschaften.

• Hermite’sche/Selbstandjungierte Matritzen (A = A†, aij = a∗ji):Alle Eigenwerte einer Hermite’schen Matrix sind reel. Für jede symmetrische bzw. hermite’scheMatrix gibt es eine unitäre Matrix S, sodass S† ·A ·S = diag(λ1, ..., λn). Dabei besteht S wiederaus den Eigenvektoren von A.

• Normale Matritzen (A† ·A = A ·A†):Die Eigenvektoren einer normalen Matrix mit lauter unterschiedlichen Eigenwerten sind orthogo-nal.

Daraus leitet sich für spezielle Matritzen ein weiteres Verfahren um die Eigenwerte (und Eigenvekto-ren!) zu berechnen: Man versucht einfach die Ähnlichkeitstransformation S (im obigen Sinne) zu findenund erhält dann aus der transformierten Matrix die Eigenwerte und aus S die Eigenvektoren. Dies istaufgrund folgender kurzer Rechnung möglich:

det(S−1 ·A · S− λ · 1) = det(S−1 · (A− λ · 1) · S) =

= detS−1 · det(A− λ · 1) · detS = det(A− λ · 1). (3.2.2)

Ist man nur an den Eigenwerten interessiert, so reicht es auch aus die Matrix A nur auf Tridiagonal-form (rechte obere Dreiecksmatrix) zu bringen. Auf der Hauptdiagonalen stehen dann auch die Eigen-werte. Allerdings erhält man so keine Eigenvektoren. Es gibt so für verschiedene Arten von Matritzenverschiedene Algorithmen um sie zu diagonalisieren. Da z.B. quantenmechanische Operatoren immerhermite’sch sind, kann man hier speziell auf solche Matritzen zugeschnittene Verfahren anwenden.

3.2.2. Jacobi-Methode für reel-symmetrische MatritzenDie Jacobi-Methode benutzt eine Serie von Jacobi-Transformationen Ppq:

Ppq =

26666666666664

1 0. . .

c . . . s... 1

...−s . . . c

. . .0 1

37777777777775(3.2.3)



Inhaltsverzeichnis

Eine solche Transformation enthält 1 auf der Hauptdiagonalen und sonst überall 0. Ausnahmen sind nurdie Positionen (p, p) und (q, q) an der c und die Positionen (p, q) und (q, p) an denen s, bzw. −s steht.Die Zahlen c und s sind Kosinus und Sinus eines Rotationswinkels φ:

c ≡ cosφ, s ≡ sinφ : c2 + s2 = cos2 φ+ sin2 φ = 1 (3.2.4)

Ein solche Rotation (3.2.3) wird nun als Ähnlichkeitstransformation auf die Matrix A angewendet: A′ =Pt

pq ·A · Ppq. Dabei ändern sich nur die Elemente in der p-ten und q-ten Zeile, sowie p-ten und q-tenSpalte. Für diese Elemente gilt:

a′rp = carp − sarq (3.2.5)

a′rq = carq + sarp (3.2.6)

a′pp = c2app + s2aqq − 2scapq (3.2.7)

a′qq = c2app + s2aqq + 2scapq (3.2.8)

a′pq = (c2 − s2)apq + sc(app − aqq) (3.2.9)

Mit Hilfe von (3.2.9) kann man nun Ppq so erstellen, dass gerade a′pq = 0 wird. Dazu wählt man denoben eingeführten Rotationswinkel φ so, dass gilt:

cot 2φ =c2 − s2

2sc= −app − aqq

2apq. (3.2.10)

Wendet man nun eine ganze Serie P1, ...,Pk solcher Transformationen auf A an, so kann man A sukzes-sive in eine Matrix D verwandeln, die (numerisch) nahezu Diagonalgestalt hat. Exakt ist dies natürlichnicht möglich, da evtl. schon 0 gesetzte Einträge wieder größer werden können, wenn eine weitere Trans-formation angewendet wird. Mit V = P1 · ... ·Pk erhält man dann D = Vt ·A ·V. Die Matrix V enthältdie Eigenvektoren von A und D ergibt die Eigenwerte. Es bleibt noch die Frage, welche Matritzen Pi

man für die Serie auswählt. Ursprünglich wurde in jedem Schritt das jeweils größte Element der Matrixgewählt. Auf Computern ist dieses Verfahren nicht aktzeptabel, da für die Suche O(N2) Operationennötig wären. Man wählt daher eine zyklische Abfolge für (p, q):

(1, 2), (1, 3), ..., (1, N), (2, 3), (2, 4), ..., (2, N), ...

Da die Matrix A nach Voraussetzung symmetrisch ist, sind hier nur die Elemente über der Diagonalenzu beachten. Einen solchen kompletten zyklischen Satz von Transformationen nennt man einen Sweep:

S = P12 · . . . ·P1N ·P23 · . . . ·P2N · . . . · (3.2.11)

Damit ergibt sich das Verfahren 3.2.2 in algorithmischer Schreibweise und mit den oben eingeführtenGrößen.

V← 1 . Ähnlichkeitstransformations-Matrix (Eigenvektoren)D← A . Ausgabematrix (Eigenwerte)s←∞ . Summe über die Nicht-Diagonal-Elementewhile not converged (s > 0) do

for all Ppq in a sweep docalculate θ in order to get apq = 0D← Ppq(θ)t ·D ·Ppq(θ) . eine Rotation berechnenV← V ·Ppq(θ)

end fors←

∑i6=j

|dij |2 . für das Konvergenzkriterium

end whileAlgorithme 2: Jacobi-Methode



Inhaltsverzeichnis

Das Verfahren läuft iterativ ab. Die Abbruchbedingung ist natürlich nicht hart, sondern es wird abge-brochen, wenn die Summe der Nebendiagonalelemente nur unwesentlich größer ist, als 0. Die MatrixV′ = V · Ppq ist aufgrund ihrer einfachen Struktur auch einfach zu berechnen. Es ist keine (zeit-quadratische) Matrixmultiplikation auszuführen, sondern es genügt eine einfache O(N)-Rechnung. DieKonvergenz des Verfahrens kann anhand der Summe über die Quadrate der Nebendiagonal-Elementeüberprüft werden:

S :=∑r 6=s

|ars|2 (3.2.12)

Nach der Transformation Ppq haben sich dann die Elemente nach (3.2.5)-(3.2.9) geändert. Aus (3.2.9)wird natürlich a′pq = 0. Für die Summe (3.2.12) sind also nur (3.2.5) und (3.2.6) von Bedeutung. Manerhält dann:

S′ := S − 2 |apq|2 (3.2.13)

Das Betragsquadrat der Nebendiagonal-Elemente nimmt also mit jedem Schritt ab, bis es irgendwannnahezu 0 erreicht. Die Konvergenz ist also gesichert, allerdings nicht unbedingt in n < ∞ Schritten,weswegen man eine Obergrenze der Iterationen in das Verfahren einbaut.

Typische Matritzen benötigen nach [Numerical Recipies Software 1992] etwa 6 bis 10 Sweeps. Dassind etwa 3n2 bis 5n2 Rotationen. Jede Rotation benötigt etwa 4n mathematische Operationen. Sokommt man für das Verfahren auf eine Ordnung von 12n3 bis 20n3.

3.2.3. Givens-Householder-Reduktion auf TridiagonalformDas Jacobi-Verfahren ist ein iterativer Prozess, der nicht gezwungenermaßen in endlich vielen Schrittenkonvergiert. Für einfach strukturierte Matritzen gibt es recht gute iterative Verfahren, um die Eigenwerteund Eigenvektoren zu bestimmen. Daher ist es sinnvoll zuerst Verfahren anzuwenden, die eine allge-meinere Matrix auf eine Spezialform (z.B. Tridiagonal-Gestalt) reduzieren, um danach erst ein iterativesVerfahren auf diese Matrix anzuwenden.

Die Givens-Householder-Reduktion ist ein solches Verfahren, das eine symmetrische Matrix auf Tri-diagonalform zurückführt. Eine Matrix heißt Tridiagonal, wenn Sie neben der Hauptdiagonalen nur nochauf den ersten beiden Nebendiagonalen Werte besitzt. Eine symmetrische Tridiagonalmatrix hat folgendeForm:

J =

α1 β1 0β1 α2 β2

β2 α3. . .

. . . . . . βn−1

0 βn−1 αn

Das Reduktionsverfahren nutzt eine (endliche) Sequenz von orthogonalen Ähnlichkeitsabbildungen

Pi = (pnm):Ai+1 = Pt

i ·A ·Pi. (3.2.14)

Dabei ist jedes Pi eine sog. Householder-Matrix der folgenden Form:

P = 1− 2 · ~w · ~wt ⇔ pnm = δnm − 2wnwm, mit |~w| = 1 (3.2.15)

Für solche Matritzen gilt:

P2 = (1− 2~w · ~wt) · (1− 2~w · ~wt) = 1+ 4~w · ( ~wt · ~w︸︷︷︸=|~w|2=1

) · ~wt − 4~w · ~wt = 1 (3.2.16)

Daraus erhält man durch Multiplikation von P−1 auf Beiden Seiten: P = P−1. Da die Householder-Matritzen auch orthogonal sind, gilt Pt = P−1 und es folgt zusammenfassend:

P = P−1 = Pt (3.2.17)

Householder-Matritzen lassen sich auch anschaulich deuten: Sie sind gerade eine Spiegelung an derEbene, die orthogonal zu ~w steht:



Inhaltsverzeichnis

w (Normalen- vektor)

w x

Ebene

Beispiel:

Sei ~w = 1√2

(11

). Dann ergibt sich für ~P =

(0 −1−1 0

), was

gerade eine Spiegelung an der Winkelhalbierenden durch den IV.und II. Quadranten entspricht.

Man kann eine Householder-Matrix P so auf einen Vektor ~x = (x1, ..., xn)t abstimmen, dass P~x =c · ~e1 gilt. Man such also eine Ebene, die den Vektor ~x auf den gestreckten Einheitsvektor c · ~e1 spiegelt.Da man für die Ebene beliebige Freiheitsgrade hat, ist anschaulich klar, dass dies immer möglich ist. Istnun ~x gerade der erste Spalten-Vektor einer Matrix A, so wird durch Pt ·A · P die erste Zeile und dieerste Spalte bis auf das Element links oben auf 0 gesetzt. Dazu setzt man in (3.2.15):

~w =~x∓ |~x| · ~e1|~x∓ |~x| · ~e1|

=~x∓ |~x| · ~e1√

|~x|2 ∓ 2 |~x| · x1 + |~x|2, mit |~w| = 1 (3.2.18)

e1

x

|x| e1

Winkelhalbierende/Spiegelebene

-|x| e1

wNormalenvektor aufSpiegelebene

w

Vervollständigungzu Trapez

Abbildung 3.1.: Konstruktion des unnormierten Vektor ~w für die Householder-Transformation im R2

Die Abbildung 3.1 zeigt die Konstruktion des Vektors ~w (noch unnormiert). Dabei spannen ~x und|~x| · ~e1 ein Trapez auf. Die eine Hauptdiagonale bildet die Spiegelebene und die zweite Hauptdiagonaleist gerade ~w, da diese senkrecht aufeinander stehen. Die Zeichnung gilt übrigens in einem Vektorraumbeliebiger Dimension, da nur zwei Vektoren betrachtet werden, die gerade eine Ebene (die Zeichenebene)aufspannen.

Um die gewünschte „Funktion“ mathematisch zu überprüfen rechnet man:

P · ~x =(1− 2 · ~w · ~wt

)· ~x =

(1− 2~w · ~x

t ∓ |~x| · ~et1|~x∓ |~x| · ~e1|

)· ~x = ~x− 2 · ~w · |x|

2 ∓ |~x|x1

|~x∓ |~x| · ~e1|=

=(3.2.18)

~x− 2 · (~x∓ |~x| · ~e1) ·|x|2 ∓ |~x|x1

2 · (|~x|2 ∓ |~x| · x1)= ~x− ~x± |~x| · ~e1 =

= ± |~x| · ~e1 = ±

|~x|0...0

(3.2.19)

Mithilfe dieser Eigenschaft wählt man nun die erste Householder-Transformation (n−1)P, als (n −1)× (n− 1)-Matrix mit den unteren n− 1 Elementen von ~A als Vektor ~x = (a21, a31, ..., an1). Sie wird



Inhaltsverzeichnis

in eine n× n-Einheitsmatrix eingebettet:

P1 =

1 0 . . . 00... (n−1)P0

(3.2.20)

Ein solches P1 löscht die unteren n − 2 Einträge der ersten Zeile bzw. Spalte (von links bzw. rechtsangewendet) einer Matrix A. Mit Pt

1 = P1 gilt dann:

A′ = P1 ·A·P1 =

1 0 . . . 000... (n−1)P0

·

a11 a12 . . . a1n

a21

a31... *an1

·

1 0 . . . 000... (n−1)P0

=

=

a11 a12 . . . a1n

k0... *0

·

1 0 . . . 000... (n−1)P0

=

a11 k 0 . . . 0k0... *0

(3.2.21)

Danach wendet man das selbe Verfahren auf die (n−1)×(n−1)-Untermatrix von ~A′ an. Die Householder-Transformation (n−2)P wird dann wieder in eine n× n-Einheitsmatrix eingefügt:

P2 =

1 0 0 . . . 00 1 0 . . . 00 0...

... (n−2)P0 0

(3.2.22)

Das geht so fort, bis die Matrix die Tridiagonalgestalt hat. Dies ist der Fall nach genau n − 2 Transfor-mationen Pn−2 · ... · P1 =: P des oben beschriebenen Typs. Nach diesen Operationen erhält man eineTridiagonalmatrix ~T = P ·A ·P mit den selben Eigenwerten λi, aber unterschiedlichen Eigenvektorenwie A. Hat man später die Eigenvektoren ~ti von T bestimmt, so erhält man die Eigenvektoren ~vi von Azu:

~vi = P · ~ti (3.2.23)

Dies folgt sofort aus P2 = 1, wie (3.2.24) zeigt. Man muss nur von links mit P multiplizieren und mitA~v = λ~v vergleichen:

T~t = λ~t ⇒ P ·A ·P~t = λ~t ⇒ A ·P~t = λP · ~t (3.2.24)

Wendet man die Householder-Reduktion auf allgemeine Matritzen (nicht symmetrisch) an, so kann mandiese damit auf Hessenberg-Form bringen:

H =

× × × × ×× × × × ×× × × ×× × ×

0 × ×

(3.2.25)

Eine Hessenberg-Matrix hat Einträge auf der Hauptdiagonalen, der ersten unteren Nebendiagonalen undin der rechten oberen Ecke. Der Rest ist 0.



Inhaltsverzeichnis

Für das obige Verfahren wären Matrix-Matrix-Multiplikationen nötig, die in die Klasse O(n3) ge-hören. Um dies zu umgehen kann man einen Rechentrick anwenden, sodass nur noch Matrix-Vektor-Multiplikationen auftreten, die in die Klasse O(n2) gehören. Dazu definiert man einen Vektor

~p := 2 · A · ~u|~u|2

mit ~u := ~x∓ |~x| · ~e1 (3.2.26)

Mit (3.2.26) und (??) erhält man dann:

A ·P = A ·(1− 2 · ~u · ~u

t

|~u|2

)= A− ~p · ~ut und P ·A = A− ~u · ~pt

⇒ A′ = P ·A ·P = PA−P · (~p~ut) = A− ~u~pt − (1− 2~u~ut

|~u|2) · (~p~ut) =

A− ~u~pt − ~p~ut + 2(~u~ut) · (~p~ut)|~u|2

= A− ~u~pt − ~p~ut +2~ut · ~p|~u|2︸︷︷︸=:2K

·(~u~ut) (3.2.27)

Mit der weiteren Setzung ~p := ~p−K~u (bzw. ~p = ~q +K~u) erhält man dann die einfache Form

A′ = A− ~q · ~ut − ~u · ~qt (3.2.28)

Hierin sind keineO(n3)-Prozesse mehr enthalten. Ein äußeres Produkt ~x ·~yt ergibt nur eine Multiplikati-on pro Eintrag (alsoO(n2)). Die restlichen Operationen sind Matrixadditionen, die ebenfalls quadratischskalieren. Zur Berechnung von ~p (und mithin ~q) ist allerdings eine Matrix-Vektor-Multiplikation nötig,die aber auch in O(n2) abläuft. Somit erhält man eine Gesamtkomplexität von O(n3), da n − 2 Trans-formationen angewendet werden müssen. Der Trick hat aber eine O(n4)-Komplexität verhindert.

3.2.4. QL/QR-AlgorithmusMit der Givens-Householder-Reduktion aus 3.2.3 kann man eine reell-symmetrische Matrix auf Tridiagonal-, bzw. eine allgemeine Matrix auf Hessenberg-Form bringen. Nun benötigt man einen Algorithmus umdie Eigenwerte und -vektoren einer solchen Matrix zu bestimmen. Wie im letzten Abschnitt erklärt wurdehat man dann direkt die Eigenwerte und nach einer Transformation auch die Eigenvektoren der ursprüng-lichen, untransformierten Matrix.

Das Verfahren basiert auf der Idee, dass sich jede reelle Matrix A in folgender Form zerlegen lässt:

A = Q ·R (3.2.29)

Dabei ist Q orthogonal (Q−1 = Qt) und R ist ein obere Dreiecksmatrix. Daraus erhält man folgendenützliche Beziehung:

R = Q−1 ·A = Qt ·A (3.2.30)

Fasst man (3.2.29) und (3.2.30) zusammen, so ergibt sich schließlich:

A′ = Qt ·A ·Q. (3.2.31)

Also geht A′ gerade durch eine orthogonale Transformation aus A hervor, wobei die Eigenwerte erhaltenbleiben. Außerdem bleiben folgende Eigenschaften erhalten: Symmetrie, Tridiagonal- oder Hessenberg-Form. Natürlich ist es vollkommen irrelevant, ob man A in Q und eine obere oder untere Dreiecksmatrixzerlegt. Im zweiteren Falle nennt man diese L und erhält A = Q · L (QL-Tranformation).



Inhaltsverzeichnis

for all i ∈ N docalculate QR-Decomposition of Ai: Ai = Q ·Rcalculate Ai+1 ← R ·Q = Qt

i ·Ai ·Qi

end forAlgorithme 3: QR-Algorithmus

Der QR/QL-Algorithmus konstruiert nun eine Reihe von Matritzen Ai:Es wird also eine Folge von QR-Zerlegungen Qi,Ri berechnet und daraus eine Folge von ähnlichen

Matritzen Ai, mit:Ai+1 = Qt

i ·Ai ·Qi. (3.2.32)

Die Folge Ai konvergiert gegen eine spezielle Form aus der die Eigenwerte abgelesen werden können:

• haben alle Eigenwerte Multiplizität 1, so konvergiert Ai (i → ∞) gegen eine obere Dreiecksma-trix, bei der die Eigenwerte auf der Hauptdiagonalen stehen.

• ist ein Eigenwert mit Multiplizität p vorhanden, so konvergiert Ai gegen eine Dreiecksmatrix, bisauf einen p× p-Block, dessen Eigenwerte gegen den gesuchten λi konvergieren.

Die Eigenvektoren erhält man als Spaltenvektoren der akkumulierten orthogonalen TransformationenQ = Q1 · ... ·Qk.

Es bleibt also nur noch die Frage offen, wie man eine QR-Zerlegung berechnen kann. Dies erfolgt unterVerwendung von Householder-Transformationen Pi (siehe auch 3.2.3 und dort (3.2.15)). Man wählt dieTransformationen Pi so, dass nacheinander die Subdiagonalelemente der Spaltenvektoren verschwinden.P1 löscht also die n−1 Subdiagonalelemente der ersten Spalte, P2 die n−2 Elemente der zweiten Spalteusw. Mit (3.2.15) gilt dann:

R = Pn−1 · ... ·P1︸︷︷︸=:Q

·A = Q ·A (3.2.33)

Auf diese Weise erhält man also die beiden Matritzen Q und R der Zerlegung von A.Aufgrund der Matrixmultiplikationen ist die Ordnung des QR-Algorithmus O(Nn3) (O(N) Matrix-

multiplikationen/Iterationen). Für Hessenberg-Matritzen reduziert sich dies zuO(Nn2) und für Tridiagonal-Matritzen sogar auf O(Nn) (die Anzahl der Elemente auf den drei Diagonalen skaliert nur mit 3n). DasVerfahren ist also für allgemeine Matritzen zu langsam, da ja evtl. sehr viele Iterationen durchgeführtwerden müssen. Reduziert man aber vorher die Matrix A (in endlich vielen Schritten) auf Tridiagonal-oder Hessenberg-Gestalt (z.B. mit Givens-Householder aus 3.2.3), so lässt sich die QR-Zerlegung sehreffektiv einsetzen.



Inhaltsverzeichnis

3.2.

5.Zu

sam

men

stel

lung

der

Verf

ahre

nVe

rfah

ren

Kom

plex

ität

Mat

rix-

Kla

sse

Bem

erku

ngen

Jaco

bi-M

etho

de12..20N

3re

el-s

ymm

etri

sch

•ap

prox

imat

ives

/itte

rier

ende

sV

erfa

hren

(Kon

verg

enz

aber

gara

ntie

rt)

•Ja

cobi

-Rot

atio

nen

Ppq

lösc

hen

jew

eils

ein

Mat

rixe

lem

ent

(p,q

)au

s•

einf

ache

Stru

ktur

der

Jaco

bi-M

atri

tzen

mac

htM

atri

x-M

atri

x-M

ultip

likat

ione

nüb

erflü

ssig

•E

igen

vekt

oren

könn

enbe

stim

mtw

erde

n

Giv

ens-

Hou

seho

lder

-Red

uktio

nO

(N3)

belie

bige

Mat

ritz

en•

brin

gtsy

mm

etri

sche

Mat

ritz

enau

fTri

diag

onal

form

•br

ingt

belie

bige

Mat

ritz

enau

fHes

senb

ergf

orm

•Vo

rstu

fefü

rEig

enw

ertb

estim

mun

gz.

B.m

itQ

R•

Hou

seho

lder

-Mat

ritz

en(S

pieg

elun

gen

anH

yper

eben

e)la

s-se

ndi

ek

unte

ren

Ele

men

teei

nerS

palte

vers

chw

inde

n

QL/

QR

-Alg

orith

mus

O(N

2)

Trid

iago

nalf

orm

,H

esse

nber

g-M

atri

tzen

•A

blei

ten

eine

rFol

gevn

Mat

ritz

enA

i,di

ege

gen

eine

Form

konv

ergi

ert,

aus

derd

ieE

igen

wer

teab

gele

sen

wer

den

kön-

nen

•nu

tztH

ouse

hold

er-M

atri

tzen

•E

igen

vekt

oren

könn

enbe

stim

mtw

erde

n



Inhaltsverzeichnis

3.2.6. Anwendung: Lineare Variatios-Methode in der Quantenphysik

GrundlagenNur einige wenige quantenmechanische Probleme können analytisch gelöst werden. Dazu gehören nebendiversen Kastenpotenzialen vor Allem das Wasserstoff-Atom und der harmonische Oszillator. Für andereProbleme muss man eine Näherungslösung suchen.

Oft stellt sich das Problem in der Form einer Eigenzustandgleichung

H|ψλ〉 = λ · |ψλ〉. (3.2.34)

Man möchte also die Eigenwerte λ zu einem gegebenen Operator H, sowie die zugehörigen Eigenzu-stände ermitteln. Handelt es sich bei dem Operator um den Hamiltonian des Systems, so erhält man alsLösung die Energien der einzelnen Zustände. Um dies praktisch zu lösen wählt man einen endlichenUnterraum des Hilbert-Raumes, der von einer (normierten) Basis |ϕi〉 aufgespannt wird. In diesem Un-terraum kann man dann den Operator als Matrix aufstellen, indem man seine Matrixelemente berechnet:

Hij = 〈ϕi|H|ϕj〉 (3.2.35)

Die Eigenwerte und -vektoren dieser Matrix können nun numerisch berechnet werden. Die Eigenvek-toren sind dann natürlich Zahlenvektoren (x1, ..., xn)t, aus denen man dann einfach die entsprechendeWellenfunktion ψ(~q) berechnen kann:

ψ(~q) = x1 · ϕ1(~q) + ...+ xnϕn(~q) (3.2.36)

Dabei sind die ϕi(~q) die Basis von Wellenfunktionen, die verwendet wurde.Man kann das Problem auch etwas anders auffassen. Man ermittelt dann die Energiezustände Ei als

stationäre Lösungen des Energiefunktionals

E[ψ] =〈ψ|H|ψ〉〈ψ|ψ〉

⇔ 〈ψ|ψ〉 · E[ψ] = 〈ψ|H|ψ〉. (3.2.37)

Die Stationären Zustände sind gerade die Punkte, für die δE = 0 gilt, wobei δE eine kleine Variationder Energie durch eine Variation ψ → ψ + δψ der Funktionen ist. Man kann δE leicht berechnen, wennman (3.2.37) mit 〈ψ|ψ〉 multipliziert (zweite Formel in (3.2.38)) und auf beiden Seiten differenziert:

〈ψ|ψ〉 · δE + E · (〈ψ|δψ〉+ 〈δψ|ψ〉) = 〈δψ|H|ψ〉+ 〈ψ|H|δψ〉

⇒ δE =1〈ψ|ψ〉

·(〈δψ|H|ψ〉 − E · 〈δψ|ψ〉+ 〈ψ|H|δψ〉 − E · 〈ψ|δψ〉

)!= 0 (3.2.38)

In einem endlichen Unterraum des Hilbertraumes wird dann aus dem Energiefunktional (3.2.37) einFunktion in Zustandvektoren ~x, der von einer Familie ϕi aufgespannt wird:

E[ψ] =〈ψ|H|ψ〉〈ψ|ψ〉

=∫ψ∗Hψ d~q∫ψ∗ψ d~q

→ E(~x) =

∑n,m x∗nHnmxm∑n,m x∗nSnmxn

(3.2.39)

Dabei sind Hnm = 〈ϕn|H|ϕm〉 die Matrixelemente des Hamiltonians und Snm = 〈ϕn|ϕm〉 ist dieÜberlappmatrix der aufspannenden Familie. In dieser Formulierung geht das Variationsproblem in einverallgemeinertes Eigenwertproblem über

H · ~x = E · S · ~x (3.2.40)

Hat man eine Orthonormalbasis gewählt, so wird S zur Einheitsmatrix 1 und das verallgemeinerte gehtin ein normales Eigenwertproblem über. Es gibt Verfahren um verallgemeinerte Eigenwertprobleme aufnormale Eigenwertprobleme zurückzuführen. Am einfachsten multipliziert man (3.2.40) mit S−1 undlöst dann das neue Problem

H′ · ~x = (S−1 ·H) · ~x = E · ~x (3.2.41)



Inhaltsverzeichnis

das die selben Eigenwerte und Eigenvektoren aufweist. Allerdings verliert man hier im Allgemeinendie Hermitizität der Matrix H, die sonst durch die Regeln der Quantenmechanik gesichert wird. Manbenötigt dann kompliziertere numerische Verfahren, um das Problem zu lösen.

Man sollte also möglich orthonormale Basen wählen. Betrachtet man z.B. Störungen eines analytischlösbaren Systems, so kann man die Eigenfunktionen des ungestörten Systems als Basis wählen. Es istauch zu beachten, dass die Ergebnisse sensitiv von der Größe der Matrix für H abhängen. Die Dimensiondes Unterraumes darf also nicht zu niedrig gewählt werden.

Beispiel: Gestörter harmonischer OszillatorZunächst betrachte man den ungestörten quantenharmonischen Oszillator. Sein Hamiltonian ist

H0 =P2

2m+

12mω2X2 (3.2.42)

Um das Problem anzugehen bringt man es zunächst in eine einheitenlose Gestalt. Dazu führt man ein-heitenlose Impuls- und Ortsoperatoren ein Π, Q und erhält:

H0 = ~ω ·(

12Π2 +

12Q2

), mit Π :=

P√mω~

und Q :=√mω

~︸︷︷︸=:1/x0

·X (3.2.43)

Die Operatoren Π und Q erfüllen die Kommutatorrelation [Π, Q] = −i. Die gut bekannte Lösung diesesProblem sind (Hi(Q) sind die sog. Hermite’schen Polynome):

ϕn(Q) =1

π1/4· 1√

2nn!·Hn(Q) · e−Q2/2 (3.2.44a)

〈ϕn|ϕm〉 =∫ϕn(Q) · ϕm(Q) dQ = δnm (3.2.44b)

H0(Q) = 1; H1(Q) = 2Q; H2(Q) = 4Q2 − 2 (3.2.44c)

H ′n(Q) = 2nHn−1(Q) (3.2.44d)

2QHn(Q) = 2nHn−1(Q) +Hn+1(Q) (3.2.44e)

Die Eigenwerte En des Hamiltonians (3.2.42) bzw. (3.2.43) sind bekanntermaßen

En =(n+

12

)~ω. (3.2.45)

Da die Funktionen ϕi(Q) gerade die Eigenwertgleichung von H0 erfüllen hat der Hamilton-Operator indieser Basis Diagonalgestalt:

(H0)nm = ~ω(n+

12

)· δnm, H0 =

~ω/2 0. . .

0 ~ω ·(n+ 1

2

) (3.2.46)

Die (normierten) Eigenvektoren zu dieser Matrix sind dann im Rn gerade Einheitsvektoren ~e1, ..., ~en,die im Ortsraum jeweils einer Funktion ϕn entsprechen. Für die Betrachtung einer Störung des Systemsist es noch interessant auch die Matrix-Darstellung des Ortsoperators in der gewählten Basis zu kennen.Dazu ist etwas mehr Rechenaufwand nötig:

Qnm = 〈ϕn|Q|ϕm〉 =∫ϕn(Q) ·Q · ϕm(Q) dQ (3.2.47)

Um dies einfacher zu lösen, führt man Auf- und Absteigeoperatoren ein:

Q =1√2(a + a†), Π =

1√2 · i

(A− a†), aϕn =√nϕn−1, a†ϕn =

√n+ 1ϕn+1 (3.2.48)



Inhaltsverzeichnis

Damit erhält man dann:

Qnm =1√2〈ϕn|a + a†|ϕm〉 =

1√2〈ϕn|√mϕm−1 +

√m+ 1ϕm+1〉 =

=1√2·(√mδn,m−1 +

√m+ 1δn,m+1

), (3.2.49)

bzw. als Matrix im Rn×n:

Q =

0 11 0

√3/2√

3/2 0. . .

. . . . . .√n/2√

n/2 0

(3.2.50)

Nun stört man das harmonische Potential durch Terme höherer Ordnung in Q, also z.B. H′ = H0 +λ ·Q4. Man kann dann die Matrix-Darstellung des neuen Hamiltonians leicht ermitteln:

H′ = H0 + λ ·Q4 (3.2.51)

Von dieser neuen Matrix kann man dann wieder die Eigenwerte und Vektoren bestimmen, die dann(bei Begrenzung auf einen endlichen Unterraum) eine Näherungslösung der erlaubten Energien und derEigenfunktionen ergeben.

Verallgemeinerung auf beliebige Potential V (Q)

Eben wurde das Verfahren auf ein spezielles System angewendet, über das recht viel bekannt ist. Auchwurde eine orthonormierte Basis den Hilber-Raumes gewählt. Das Vorgehen lässt sich aber noch vielallgemeiner fassen und zwar für beliebige zeit-unabhängige Potentiale V (Q). Man geht dann wie folgtvor:

1. Wähle eine Basis ψn für den betrachteten Unterraum. Es sollte darauf geachtet werden, dasssich evtl. auftretende Symmetrien des Potentials in den Basis-Funktionen wiederspiegeln. Es kannz.B. sinnvoll sein einen symmetriscen und einen asymmetrischen Satz von Funktionen zu verwen-den. Desweiteren sollten die Funktionswerte an der gleichen Stelle in der selben Größenordnungliegen, um numerische Fehler zu v ermeiden. Außerdem muss darauf geachtet werden, dass dieFunktionen quadrat-integrabel (und also normierbar) sind.

2. Berechne die zwei Anteile des Hamiltonians H = T + V als Matrixelemente:

Tnm = 〈ψn|P2/2m|ψm〉 =∫

Rψ(x) · ∂

2

∂x2ψ(x) dx (kinetischer Anteil)

Vnm = 〈ψn|V|ψm〉 =∫

Rψ(x) · V (x) · ψ(x) dx (potentieller Anteil)

Außerdem benötigt man die Überlappmatrix D, da die Basis nicht unbedingt orthonormiert ist:

Dnm = 〈ψn|ψm〉 =∫

Rψ(x) · ψ(x) dx

3. Mit einer numerischen Bibliothek löst man nun das verallgemeinerte Eigenwertproblem

H ·X = En ·D ·X.

Dazu kann man evtl. erst die Eigenvetoren der Matrix D bestimmen, die dann eine orthogonaleMatrix Z bilden. Mit dieser orthogonalen Transformation kann man dann das obige verallgemei-nerte Eigenwertproblem auf ein normales reduzieren, da ZtDZ = 1 und H = ZtHZ die selbenEigenwerte, wie H hat.



4. Numerische IntegrationOft ist es wünschenwert das Bestimte Integral einer Funktion f(~x) : Rn → R zu berechnen. DieseGrundaufgabe wird von den Algorithmen in diesem Abschnitt gelöst. Sie lässt sich forumlieren als:

I[f ] =∫

Vf(~x) dnx. (4.0.1)

4.1. Quadraturformel

Zur Lösung dieser Aufgabe verwendet man üblicherweise die sog. Quadraturformel:

I[f ] =

b∫a

f(x) dx ≈n−1∑i=0

αif(xi) (4.1.1)

Dabei sind a ≤ x1 < ... < xn ≤ b Stützstellen, an denen die Funktion ausgewertet wird und αi ∈ Rsind Gewichte zu diesen Stützstellen. Ein einfaches Beispiel ist die Rechteckregel:

I[f ] ≈n−1∑i=0

(xi+1 − xi) · f(xi) =n−1∑i=0

∆x · f(xi). (4.1.2)

Dabei ist ∆x der Abstand zweier Stützstellen (wenn dieser konstant ist). Die folgende Abbildung 4.1zeigt das Prinzip.

0

0.1

0.2

0.3

0.4

0.5

0 2 4 6 8 10

Abbildung 4.1.: Summationsregel zur Integration

4.2. Simpson’s Regel

Bei dem bisherien Verfahren wurde die Fläche unter der Funktion f(x) als Summe von Rechteckenaufgefasst. Man kann aber auch kompliziertere Objekte aufsummieren. Bei Simpson’s Regel sind dasParabelstücke, die über drei Stützstellen aufgespannt werden. Deswegen muss hier die Anzahl n derStützstellen auch gerade sein. Man erhält daraus die folgende Formel:

I[f ] ≈ b− a3n·[f(x0) + 4f(x1) + 2f(x2) + 4f(x3) + ...+ 2f(xn−2) + 4f(xn−1) + f(xn)

](4.2.1)

Der Fehler bei diesem Verfahren ist von der Ordnung O(∆x4). Bei d-dimensionalen Integralen müssendabei allerdings n = (L/∆x)d Stützstellen ausgewertet werden und die Methode konvergiert insgesamtmit O(n−4/d), was bei hohen Dimensionszahlen zu schlechten Ergebnisse führen kann. Einen Auswegbietet die Monte-Carlo-Integration aus 8.

30

5. Gewöhnliche Differentialgleichungen

5.1. Einleitung

Physikalische Probleme werden oft in Form von Differentialgleichungen dargestellt. Im einfachsten Fallhandelt es sich dabei um gewöhnliche Differentialgleichungen (ordinary differential equations, ODEs)n-ter Ordnung. Solche Gleichungen lassen sich in der folgenden allgemeinen Form darstellen:

∂nφ = F (∂n−1φ, ..., ∂φ, φ;x) (5.1.1)

Dabei ist dann φ(x) die Lösung der Gleichung. Um eine solche ODE zu lösen genügt es einfache Inte-grationen auszuführen. Man kann nämlich (5.1.1) auf „Normalform“ bringen:

y1(x) ≡ φ(x)y′1(x) = y2(x)y′2(x) = y3(x)

...y′n−1(x) = yn(x)yn(x) = F (yn−1, ..., y1;x)

:⇔ ~y′ = ~F (~y;x) (5.1.2)

Nun ist nicht mehr eine Integration n-ter Ordnung, sondern n Integrationen erster Ordnung nötig.Bei den meißten physikalischen Problemen handelt es sich um Randwertprobleme, bei denen der

Anfangszustand ~y0 am Punkt x0 bekannt ist ~y(x0) = ~y0. Man fragt dann nach dem Zustand des Systemsam Ort x (x kann natürlich auch die Zeit t sein. Es handelt sich hier um eine allgemeine Koordinate imZustandsraum.). Die Lösung dieses Problemes ist:

~y(x) = ~y0︸︷︷︸Anfangszustand

+∫ x

x0

~F (~y, x) dx︸︷︷︸Dynamik/Entwicklung

(5.1.3)

Im weiteren genügt es das eindimensionale Problem y′ = f(y;x) zu betrachten, da das volle Problem(5.1.2) dann durch Komponentenweise Integration (bei yn startend und bei y1 endend) gelöst wird. Allenumerischen Integrationsmethoden basieren darauf, die Koordinaten zu disketisieren. Aus der kontinu-ierlichen Koordinate x ∈ R wird dann:

x → xn = x0 + n · h, n ∈ N (5.1.4)

Dabei ist h ∈ R die (kleine) Schrittweite, in der diskretisiert wird.

Fehlerabschätzung: Zu numerischen Lösung eines solchen Systems macht man eine Diskretisierungund errechnet nacheinander die Punkte ~yi der Lösung. Man erhält dann eine Integrationsvorschrift derForm

~yn+1 = ~gh(..., ~yn, ~yn−1, ..., x) (5.1.5)

Dabei ist ~gh eine Abbildungsvorschrift, mit der Diskretisierungsintervalllänge h. Hängt diese Vorschriftnur von den alten Werten ~yn, ..., ~y1, so nennt man den Algorithmus explizit. Der Fehler pro Iterations-schritt wird lokaler Fehler genannt. Die Abweichung |~yn − ~ytheo| am Ende der Integration heißt dannglobaler Fehler.

31

Inhaltsverzeichnis

Problemtypen: Bei der Lösung gewöhnlicher Differentialgleichungen stellen sich im Wesentlichenzwei Typen von numerischen Augaben, die hier kurz definiert werden sollen. Sie lösen jeweils die fol-gende d-dimensionale Differentialgleichung

~y′(x) = ~f(~y(x), x

), y(x) ∈ Rd, x ∈ R (5.1.6)

und unterscheiden sich eigentlich nur in der Art der gegebenen Randbedingungen:

• Anfangswertaufgabe: Zu einem gegebenen Punkt (x0, y0) ∈ R× Rd wird eine (stetig) differen-zierbare Funktion y : R→ Rd gesucht, mit:

~y(x0) = ~y0 (5.1.7a)

~y′(x) = ~y(~y(x), x

)(5.1.7b)

• Randwertaufgabe: Zu einer gegebenen Funktion r : Rd × Rd → Rd und einer Menge vonPunkten a1, a2, ... ∈ R wird eine (stetig) differenzierbare Funktion y : R→ Rd gesucht, mit:

r(y(a1), y(a2), ...

)= 0 (5.1.8a)

~y′(x) = ~y(~y(x), x

)(5.1.8b)

Von der Lösung wird also gefordert, dass sie an einer Menge von Punkten bestimte Werte annimmt.

Damit lässt sich natürlich das Anfangswertproblem als Spezialfall des Randwertproblems auffassen.

Existenz und Eindeutigkeit einer Lösung des Anfangswertproblems (5.1.7a)/eq:intintro6b ist in ei-ner Umgebung U ⊂ Rn+1 um x0, ~y0 garantiert, wenn ~f(~y, x) dort der Lipschitzbedingung genügt, d.h.es gibt eine Konstante λ ∈ R, sodass:∥∥∥~f(~y, x)− ~f(~z, x)

∥∥∥ ≤ λ · ‖~y − ~z‖ ∀(~y, x), (~z, x) ∈ U (5.1.9)

Lineares Stabilitätskriterium für Lösungen: Sei eine DGl dNdt = f(N) gegeben. Eine Lösung N∗

heißt stationär, wenn dN∗/dt = f(N∗) = 0 gilt. Um die Stabilität einer solchen Lösung zu untersuchenstört man sie mit einer Funktion |n(t)| 1:

N(t) := N∗ + n(t) ⇒ dn

dt= f ′(N∗)n+O(n2) (5.1.10)

Die rechte DGl in (5.1.10) hat eine Exponentialfunktion n(t) = n0 · exp[f ′(N∗) · t] als Lösung. Gehtnun diese Störung gegen 0, für t → ∞, so heißt N∗ stabil, da Trajektorien, die in einer Umgebung vonN∗ starten auf N∗ zulaufen (Fixpunkt). Damit erhält man folgendes Stabilitätskriterium:

f ′(N∗) < 0 ⇔ N∗ stabil. (5.1.11)

Im Mehrdimensionalen Fall wird die erste Ableitung in der Taylor-Entwicklung in (5.1.10) durch dieJacobi-Matrix A = ~∇~f(~u∗) ersetzt (Aij = ∂fi

∂uj

∣∣∣~u∗

). Die stationäre Lösung ~u∗ wird durch ~v(t) gestört:

~u(t) = ~u∗ + ~v(t). Man erhält dann analog zu (5.1.10):

d~v

dt= ~∇~f(~u∗)~v +O(~v2) (5.1.12)

Die Lösung dieser DGl ist formal gerade:

~v(t) = et·~∇~f(~u∗)~v(0) = etA · ~v0 (5.1.13)

Man kann diese Lösung in der Basis der Eigenvektoren ~Ψi (zu den Eigenwerten λi) der Jacobi-MatrixA schreiben:

~v(t) =∑

i

ci · eλi ~Ψi (5.1.14)

Man erhält dann folgendes Stabilitätskriterium:

• ~u∗ ist instabil, wenn mindestens für einen Eigenwert gilt Re (λ) > 0.

• ~u∗ ist stabil, wenn für alle Eigenwerte Re (λi) < 0 gilt.



Inhaltsverzeichnis

5.2. Euler-Integration

Die einfachste Integrationsmethode ist das Euler-Verfahren. Es nutzt die Taylor-Entwicklung der Funk-tion y(x) bis zur ersten Ordnung:

y(x+ ∆x) = y(x) + ∆x · dydx

+O(∆x2) (5.2.1)

Diskretisiert man diese Beziehung, so erhält man:

yn+1 = yn + h · f(yn, xn) +O(h2) (5.2.2)

Dabei erzeugt man natürlich fehlerhafte Ergebnisse, weil die Diskretisierung das System verändert. Derlokale Fehler, der hier auftritt ist von der Ordnung O(h2). Da üblicherweise h 1 ist, stehen hier hohePotenzen für kleine Fehler. Der globale Fehler (bei Integration von z.B. a nach b) skaliert allerdingsschon mit O(n). Dieses resultat erhält man folgendermaßen: Um mit Schittweite h von a nach b zuintegrieren benötigt man N = (b− a)/h Schritte, in denen Jeweils ein Fehler von O(h2) gemacht wird.Der Gesamtfehler ist das Produkt der Einzelfehler und folglich O(N · h2) = O(h).

Man kommt also zu folgendem Algorithmus:

function EULERINTEGRATE(y0, a, b, h, f(·))N ← b−a

hy ← y0

For i = 1, ..., Ny ← y + h · f(a+ i · h)

return yend function

Algorithme 4: Euler-Methode zur Integration

Die folgende Abbildung veranschaulicht das Verfahren. Die Kurve y(x) wird also durch einen Poly-gonzug aproximiert.

x1 x2

h

numerischer Fehler

tatsächliche Lösung y (x)real

Approximation y(x)

bestimme y'(x)=f(y, x) hier

Abbildung 5.1.: Veranschaulichung eines Integrationsschrittes bei der Euler-Methode.

Das Verfahren benötigt recht kleine h, um verünftige Ergebnisse zu erzeugen. Als Beispiel wurde dieODE y′ = y von

(a = −1, y0 = exp(a)

)bis (b = 1, y1) integriert. Das Ergebnis für den letzten Punkt

sollte natürlich y(b) = e = 2.71828... sein. Die folgende Tabelle fasst die Ergebnisse zusammen. DerGraph zeigt, wie sich die numerischen Lösungen mit kleiner werdendem h an die tatsächliche Lösung(blau) anschmiegen:



Inhaltsverzeichnis

h y(b)1 1.4715177650.1 2.4749089220.01 2.6914125590.001 2.7155667140.0001 2.71801003210−5 2.71822746410−6 2.71827639210−7 2.718281285Ideal 2.718281285

0

0.5

1

1.5

2

2.5

3

-1 -0.5 0 0.5 1

exp(x)h=1

h=0.5h=0.25

h=0.125

Abbildung 5.2.: Evaluation des Euler-Verfahrens für die Differentialgleichung y′ = y.

Listing 5.1: Diese C++-Routine integriert eine ODE y = f(y(x), x) mit Euler. Als letzten Parameter wirddie Funktion f(·) übergeben. Die Implementation einer solchen Funktion ist zuerst angegeben.

1 / / zu i n t e g r i e r e n d e F u n k t i o n2 void f ( double∗ yout , double∗ y , double x ) 3 you t [ 1 ] = y [ 1 ]∗ y [ 2 ] . . . ; / / D e f i n i t i o n der v e k t o r w e r t i g e n F u n k t i o n4 you t [ 2 ] = . . . ;5 6

7

8 / / I n t e g r a t o r9 void e u l e r ( double∗ yout , double∗ y0 , double a , double b , double h ,

10 void (∗ f ) ( double ∗ , double ∗ , double ) ) 11 long N=( long ) abs ( ( b−a ) / h ) ;12 long s i z e = v _ g e t s i z e ( you t ) ;13 double∗ fo = v e c t o r ( s i z e ) ;14 double x=a ;15 v_copy ( yout , y0 ) ;16 f o r ( i n t i =1 ; i <=N; i ++) 17 / / cou t <<x < <" ,\ t "<< y o u t [1]<< e n d l ;18

19 / / y o u t = y o u t + h∗ f ( you t , x )20 f ( fo , yout , x ) ;21 v _ m u l t c o n s t s e l f ( fo , h ) ;22 v _ a d d s e l f ( yout , fo ) ;23

24 / / x=x+h25 x=x+h ;26 27 / / cou t <<x < <" ,\ t "<< y o u t [1]<< e n d l ;28 v _ f r e e ( fo ) ;29

5.3. Allgemeine Taylor-Reihen Methode

Das Euler-Verfahren ist nur ein Spezialfall der allgmeineren Taylor-Reihen-Methoden. Man kann dieGenauigkeit des obigen Algorithmus steigern, indem man noch weitere Summanden der Taylorreihe der



Inhaltsverzeichnis

Funktion f(y, x) berücksichtigt. Analog zu (5.2.1) erhält man dann folgende diskrete Integrationsformel:

yn+1 = yn + h · f(yn, xn) +h

2· f ′(yn, xn) + ...+

hp

p!f (p)(yn, xn) +O(hp+1) (5.3.1)

Dabei ist die k-te Ableitung der Funktion f(yn, xn) (man beachte die x-Abhängigkeit von y(x)!):

f (y)(yn, xn) =dk

dxkf(yn, xn) = ∂xf

(k−1)(yn, xn) + ∂yf(k−1)(yn, xn) · y′(xn) =

= ∂xf(k−1)(yn, xn) + ∂yf

(k−1)(yn, xn) · f(yn, xn) (5.3.2)

Analog zum Eulerverfahren ist der lokale Fehler O(hp+1) und der globale Fehler O(hp). Der Haupt-nachteil liegt in der Notwendigkeit höhere partielle Ableitungen der Funktion f zu berechnen.

5.4. Runge-Kutta-Methode

5.4.1. Runge-Kutta-Verfahren zweiter OrdnungDie bishrigen Verfahren waren sog. Einschritt-Verfahren. Sie propagieren die Lösung von einem Start-wert y0 aus schrittweise bis ans Ziel. Die Runge-Kutta-Verfahren versuchen ebenfalls Taylor-Reihen zuaproximieren. Sie berechnen dabei aber keine Ableitungen, sondern werten die Funktion f an Zwischen-stellen aus. Das Euler-Verfahren propagiert zwar über ein Intervall h, wertet aber f(y, x) nur am Anfangdieses Intervalles aus. Das Runge-Kutte-Verfahren zweiter Ordnung (RK2) nimmt noch eine Stützstelleauf der Hälfte des Intervalles h hinzu. Zuerst wird die Stützstelle x mittels eines halben Euler-Schrittesapproximiert (k1). Danach wird an der Stützstelle die Steigung k2 = y′(x) ermittelt und mit dieser wirddanach ein ganzer Euler-Schritt ausgeführt:

k1 = f(xn, yn)

k2 = f(x, y) = f(xn +12h, yn +

12k1h)

yn+1 = yn + hk2 +O(h3)

(5.4.1)

Die folgende Abbildung veranschaulich das Verfahren:

x1 x2

h

numerischer Fehlerdurch Euler-Verfahren

tatsächliche Lösung y (x)real

Euler Approximation

bestimme y'(x)=f(y, x) hier

x^

RK2 Approximation

Abbildung 5.3.: Veranschaulichung eines Integrationsschrittes beim RK2-Algorithmus

Listing 5.2: Diese C++-Routine integriert eine ODE y = f(y(x), x) mit RK2

1 void rk2 ( double∗ yout , double∗ y0 , double a , double b , double h ,2 void (∗ f ) ( double ∗ , double ∗ , double ) ) 3 long N=( long ) abs ( ( b−a ) / h ) ;4 long s i z e = v _ g e t s i z e ( you t ) ;5 double∗ fo = v e c t o r ( s i z e ) ;



Inhaltsverzeichnis

6 double∗ k1= v e c t o r ( s i z e ) ;7 double∗ k2= v e c t o r ( s i z e ) ;8 double∗ yd= v e c t o r ( s i z e ) ;9 double x=a , xd ;

10 v_copy ( yout , y0 ) ;11 f o r ( i n t i =1 ; i <=N; i ++) 12 / / cou t <<x < <" ,\ t "<< y o u t [1]<< e n d l ;13

14 / / k1 = f ( x , y )15 f ( k1 , yout , x ) ;16

17 / / yd = y+ ( h / 2 ) ∗ k1 ; xd=x +(h / 2 )18 v _ m u l t c o n s t s e l f ( k1 , h / 2 . 0 ) ;19 v_add ( yd , yout , k1 ) ;20 xd=x+h / 2 . 0 ;21

22 / / k2 = f ( xd , yd )23 f ( k2 , yd , xd ) ;24

25 / / y o u t=y o u t + h ∗ k226 v _ m u l t c o n s t s e l f ( k2 , h ) ;27 v _ a d d s e l f ( yout , k2 ) ;28 x=x+h ;29 30 / / cou t <<x < <" ,\ t "<< y o u t [1]<< e n d l ;31 v _ f r e e ( yd ) ;32 v _ f r e e ( fo ) ;33 v _ f r e e ( k1 ) ;34 v _ f r e e ( k2 ) ;35

5.4.2. Runge-Kutta-Verfahren vierter OrdnungDas Runge-Kutta-Verfahren vierter Ordnung (RK4) nimmt die Steigung an drei Zwischenstellen undbildet daraus ein gewichtetes Mittel. Sie hat die folgende Form:

k1 = f(xn, yn)

k2 = f(xn +h

2, yn + h

k1

2)

k3 = f(xn +h

2, yn + h

k2

2)

k4 = f(xn + h, yn + hk3)

yn+1 = yn + h · k1 + 2k2 + 2k3 + k4

6+O(h5)

(5.4.2)

Zuerst wird also wie bei RK2 ein Punkt auf der Hälfte des Intervalls aproximiert, an dem dann dieSteigung k2 genommen wird. Mit Hilfe dieser Steigung aproximiert man einen weiteren Punkt auf derHälfte des Intervalls, der dann die Steigung k3 liefert. Zum Schluss wird noch die Steigung k4 am Endedes Intervalls bestimmt. Aus diesen vier Parametern wird dann ein gewichtetes Mittel gebildet, das dieSteigung für den gesamten Schritt wiederspiegelt.

Das Konzept lässt sich einfacher verstehen, wenn man folgende Abbildung betrachtet.



Inhaltsverzeichnis

-2-2 -1-1 00 11 22

00

0.50.5

11

1.51.5

22xF(x)=eVektorfeld der ODE y'(x)=y xF(x)=2e

x1 x2

h

tatsächliche Lösung y (x)realk1

x^

k2

k3

k4

Abbildung 5.4.: (a) Vektorfeld der Differentialgleichung y′ = y und (b) Schema des RK4-Integrators

Sie zeigt das Vektorfeld der ODE y′ = f(x, y) = y, die bekanntermaßen die Lösung y(x) = b · exhat. Es sind die zwei Lösungen ex und 2ex eingezeichnet. In jedem Punkt (x, y) der Ebene ist ein Pfeilaufgetragen, der die Steigung an diesem Punkt wiedergibt. Eine Lösung muss sich in allen Punkten andiese Pfeile anschmiegen. Die Lösung der ODE ist bis auf den freien Parameter b festgelegt. Dieser wirdnun vom Anfangswertproblem festgelegt, das einem einen Startpunkt (x0, y0) für die Integration angibt.Hier ergibt sich damit b = y0 · e−x0 .

Listing 5.3: Diese C++-Routine integriert eine ODE y = f(y(x), x) mit RK4

1 void rk4 ( double∗ yout , double∗ y0 , double a , double b , double h ,2 void (∗ f ) ( double ∗ , double ∗ , double ) ) 3 long N=( long ) abs ( ( b−a ) / h ) ;4 long s i z e = v _ g e t s i z e ( you t ) ;5 double∗ fo = v e c t o r ( s i z e ) ;6 double∗ k1= v e c t o r ( s i z e ) ;7 double∗ k2= v e c t o r ( s i z e ) ;8 double∗ k3= v e c t o r ( s i z e ) ;9 double∗ k= v e c t o r ( s i z e ) ;

10 double∗ k4= v e c t o r ( s i z e ) ;11 double∗ yd= v e c t o r ( s i z e ) ;12 double x=a , xd ;13 v_copy ( yout , y0 ) ;14 f o r ( i n t i =1 ; i <=N; i ++) 15 / / cou t <<x < <" ,\ t "<< y o u t [1]<< e n d l ;16

17 / / k1 = f ( x , y )18 f ( k1 , yout , x ) ;19 v_copy ( k , k1 ) ; / / k=k1 −> Z w i s c h e n s p e i c h e r n , da f ü r Rechnung k1 . . k3 v e r ä n d e r t werden muss20

21 / / k2 = f ( xd , yd )22 / / wobei : yd = y+ ( h / 2 ) ∗ k1 ; xd=x +(h / 2 )23 v _ m u l t c o n s t s e l f ( k , h / 2 . 0 ) ;24 v_add ( yd , yout , k ) ;25 xd=x+h / 2 . 0 ;26 f ( k2 , yd , xd ) ;27 v_copy ( k , k2 ) ; / / k=k228

29 / / k3 = f ( xd , yd )



Inhaltsverzeichnis

30 / / wobei : yd = y+ ( h / 2 ) ∗ k2 ; xd=x +(h / 2 )31 v _ m u l t c o n s t s e l f ( k , h / 2 . 0 ) ;32 v_add ( yd , yout , k ) ;33 xd=x+h / 2 . 0 ;34 f ( k3 , yd , xd ) ;35 v_copy ( k , k3 ) ; / / k=k136

37 / / k4 = f ( xd , yd )38 / / wobei : yd = y+ h∗k3 ; xd=x+h39 v _ m u l t c o n s t s e l f ( k , h ) ;40 v_add ( yd , yout , k ) ;41 xd=x+h ;42 f ( k4 , yd , xd ) ;43

44 / / y o u t=y o u t + ( h / 6 ) ∗ ( k1 + 2∗ k2 + 2∗ k3 + k4 )45 v_add ( k , k1 , k4 ) ;46 v _ m u l t c o n s t s e l f ( k2 , 2 ) ;47 v _ m u l t c o n s t s e l f ( k3 , 2 ) ;48 v _ a d d s e l f ( k , k2 ) ;49 v _ a d d s e l f ( k , k3 ) ;50 v _ m u l t c o n s t s e l f ( k , h / 6 . 0 ) ;51 v _ a d d s e l f ( yout , k ) ;52 x=x+h ;53 54 / / cou t <<x < <" ,\ t "<< y o u t [1]<< e n d l ;55 v _ f r e e ( yd ) ;56 v _ f r e e ( fo ) ;57 v _ f r e e ( k1 ) ;58 v _ f r e e ( k2 ) ;59 v _ f r e e ( k3 ) ;60 v _ f r e e ( k4 ) ;61 v _ f r e e ( k ) ;62

5.4.3. Allgemeines Runge-Kutta-VerfahrenDie (expliziten) Runge-Kutta-Verfahren haben allgemein die folgende Form:

k1(xn, yn) = f(xn, yn)k2(xn, yn) = f(xn + ha2, yn + hb21k1)

...

ki(xn, yn) = f(xn + hai, yn + h ·

i−1∑s=1

bisks

)yn+1 = yn + h · FR(xn, yn) = yn + h ·

R∑r=1

crkr(xn, yn)

(5.4.3)

Die letzte Gleichung gibt dabei die Aproximation eines Integrationsschrittes an. Die Verfahren werdenparametrisiert, indem man einen Schritt mit der Taylor-Approximation vergleicht, also:

FR(x, y(x)) =R∑

r=1

crkr(x, y(x))!=

R∑r=1

hr−1

r!f (r−1)(x, y(x)) +O(hm). (5.4.4)

Dabei werden die freien Parameter (RK-Matrix B = (brs), RK-Knoten ~a, RK-Gewichte ~c) so bestimmt,dass die beiden Seiten von (5.4.4) bis zu einer möglichst großen Ordnung m (am Besten m = R)gleich sind. Ein so konstruiertes Runge-Kutta-Verfahren hat dann die Ordnung m. Dabei bleiben ofteinige Koeffizienten als freie Parameter übrig, was dann zu verschiedenen Verfahren der selben Ordnungführt. Es gibt nach der Definition (5.4.3) zwei grundsätzlich verschiedene Arten von Verfahren. Zum



Inhaltsverzeichnis

einen explizite Verfahren, die einfach gelöst werden können, weil der i-te Koeffizient ki nur von denKoeffizienten k1, ..., ki−1 abhängt. Die ki können also sukzessive berechnet werden. Diese Bedingungentspricht der Aussage, dass die Matrix A linke untere Dreiecksform hat. Ist diese Bedingung nichterfüllt, so handelt es sich um ein implizites RK-Verfahren, das nur iterativ gelöst werden kann.

Beispiel: Ableitung des RK2: Die bereits vorher (siehe (5.4.1)) gegebene Formel des klassichenRunge-Kutta-Verfahrens zweiter Ordnung soll hier hergeleitet werden. Zuerst die linke Seite von Aus-druck (5.4.4) für den Fall R = 2:

c1k1(x, y) + c2k2(x, y) = c1f + c2f(xn + ha2, yn + hb21f) == c1f(x, y) + c2 · [f(x, y) + a2h · f(x, y) + b21h · f(x, y) · ∂xf(x, y)]

= (c1 + c2) · f(x, y) + h · [c2a2 · ∂xf(x, y) + c2b21 · f(x, y) · ∂yf(x, y)] (5.4.5)

In der zweiten Zeile wurde der hintere c2-Term Taylor-entwickelt. Außerdem wurde k1 = f(xn, yn) undk2(xn, yn) = f(xn + ha2, yn + hb21k1), sowie y′ = f(xn, yn) verwendet. Nun vergleicht man diesmit der Taylor-Entwicklung der Funktion f(x, y):

R∑r=1

hr−1

r!f (r−1)(x, y(x)) = f(x, y) +

h

2· [∂xf(x, y) + f(x, y) · ∂yf(x, y)] +O(h2). (5.4.6)

Aus dem Koeffizientenvergleich erhält man dann:

c1 + c2 = 1 (5.4.7)

c2a2 = c2b21 =12

(5.4.8)

Als mögliche Lösung erhält man c1 = 0, c2 = 1, a2 = b21 = 12 . Das ergibt folgenden Algorithmus:

k1 = f(xn, yn)

k2 = f(xn +

h

2, yn +

h

2k1

)yn+1 = yn + hk2

Dies bestätigt das Ergebnis aus 5.4.1.Zum Schluss soll noch angegeben werden, wie man die Runge-Kutta-Verfahren geschickt als Koeffizienten-

Schema darstellen kann:~a B

~ct

Hier noch der RK2 und RK4, wie sie hier angegeben wurden in dieser Schreibweise:

012

12

0 1

012

12

12 0 1

21 0 0 1

16

13

13

16

5.4.4. EvaluationWie beim Euler-Verfahren wurde als Beispiel die ODE y′ = y von

(a = −1, y0 = exp(a)

)bis (b =

1, y1) integriert. Das Ergebnis für den letzten Punkt sollte wieder y(b) = e = 2.71828... sein. Diefolgende Tabelle fasst die Ergebnisse zusammen. Die Graphen zeigen, wie sich die Lösungen durchEuler, RK2 und RK4 für unterschiedliche h an die tatsächliche Lösung (magenta) anschmiegen:



Inhaltsverzeichnis

h yEuler(b) yRK2(b) yRK4(b)1 1.471517765 2.299246507 2.6984212480.1 2.474908922 2.709886357 2.718277660.01 2.691412559 2.718191897 2.7182818280.001 2.715566714 2.718280923 2.7182818280.0001 2.718010032 2.718281819 2.71828182810−5 2.718227464 2.718254646 2.71825464610−6 2.718276392 2.71827911 2.7182791110−7 2.718281285 2.718281557 2.71828155710−8 2.718281285 2.718281557 2.718281557Ideal 2.718281285 2.718281828 2.718281828

0

0.5

1

1.5

2

2.5

3

-1 -0.5 0 0.5 1

h=1

EulerRK2RK4

exp(x)

0

0.5

1

1.5

2

2.5

3

-1 -0.5 0 0.5 1

h=0.25

EulerRK2RK4

exp(x)

0

0.5

1

1.5

2

2.5

3

-1 -0.5 0 0.5 1

h=0.5

EulerRK2RK4

exp(x)

0

0.5

1

1.5

2

2.5

3

-1 -0.5 0 0.5 1

h=0.125

EulerRK2RK4

exp(x)

Abbildung 5.5.: Vergleich der Integratoren Euler, RK2 und RK4, bezüglich der Differentialgeleichung y′ = y

Während Euler noch recht weit von der tatsächlichen Lösung entfernt ist, nähern sich die Runge-Kutta-Methoden sehr schnell.

5.5. Schrittweitenkontrolle

Um die bisher vorgestellten Integrationsverfahren zu verbessern, kann man die Schrittweite h vom loka-len AUssehen der Funktion abhängig machen. Der Nachteil ist, dass der Nutzer die Kontrolle über dieSTellen, an denen evaluiert wird verliert; dafür wird die Approximation besser. Die Schrittweite ist groß,wenn sich die Funktion wenig ändert und wird kleiner, wenn höhere Ableitungen wachsen, da dies ein



Inhaltsverzeichnis

ANzeichen für starke Schwankungen in der Funktion ist. Solche Verfahren kann man auch benutzen, umeine bestimte Genauigkeit zu garantieren.

Für RK4 ist das einfachste Verfahren die Schrittweitenverdopplung. Dabei wird das selbe Intervall ein-mal in einem Schritt h berechnet und einmal in zwei Schritten h/2. Man erhält so zwei Endpunktepaare(x+ h, y1) und (x+ h, y2). Der Abstand ∆ := y2 − y1 ist ein guter Indikator für den Abschneidefehler,der bei dem Verfahren gemacht wird. Aufgrund dieser Größe kann man dann h modifizieren.

Eine weitere Methode ist der Bulirsch-Stoer-Algorithmus, der auf der Richardson-Extrapolation ba-siert. Dazu geht man davon aus, dass das endgültige Ergebnis eine (wenn auch komplizierte) analytischeFunktion eines Parameters (z.B. der Schrittweite h) ist. Eine solche Funktion kann man für verschiedeneh (viel größer, als sie für ein akurates Ergebnis mit RK nötig wären) testen. Wenn man genug Informatio-nen über die Funktion gesammelt hat, so kann man den Fall h = 0 extrapolieren. Man untersucht jeweilsein großes Intervall H h, das mit einer steigenden Zahl n = 2, 4, 6, 8, 12, 16, ... von Zwischenschrit-ten berechnet wird. Nach jeder Berechnung für ein n wird dann eine Extrapolation durchgeführt. JederSchritt liefert so einen Endpunkt, sowie Fehlerabschätzungen. Sind die (lokalen) Fehler befriedigendklein, so geht man zum nächsten großen Intervall über. wenn n über eine Grenze Nmax steigt, ohne dassdie Fehler klein genug werden, so wird das Intervall H geteilt, da sich offensichtlich ein „Hindernis“(=sich stark ändernde Stellen) dort befindet.

5.6. Numerov-Algorithmus und Shooting-Methode

5.6.1. Numerov-AlgorithmusDer Numerov-Algorithmus ist ein Verfahren für eine spezielle Klasse von Differentialgleichungen, diez.B. in der Quantenmechanik oft vorkommen:

y′′(x) + k(x) · y(x) = 0 (5.6.1)

Dies entspricht der eindimensionalen, zeitunabhängigen Schrödinger-Gleichung(−~2

2m· ∂

2

∂x2+ V (x)

)· ψ(x) = E · ψ(x), (5.6.2)

wenn man die Setzung (5.6.3) vornimmt:

k(x) :=2m~2·(E − V (x)

). (5.6.3)

Der Algorithmus nutzt vorwärts-/rückwärts-Iteration, die ausgehend von zwei Startwerten y(x0) = y0

und y(x1) = y1 alle weiteren Punkte yi = y(xi) der Lösung berechnet. Es handelt sich hier um ein Ver-fahren zur Lösung eines Randwertproblemes. Alle bisherigen Algorithmen lösten Anfangswertprobleme.Die Größe des Diskretisierungsintervalles sei wieder h. Es gilt dann (durch Taylor-Entwicklung nach h):

yn+1 = y(xn + h) = y(xn) + hy′(xn) +h2

2y′′(xn) +

h3

6y(3)(xn) +

h4

24y(5)(xn) +O(h5) (5.6.4)

yn−1 = y(xn − h) = y(xn)− hy′(xn) +h2

2y′′(xn)− h3

6y(3)(xn) +

h4

24y(5)(xn) +O(h5) (5.6.5)

Daraus ergibt sich sofort:

yn+1 + yn−1 = 2y(xn) + h2y′′(xn) +h4

12y(4)(xn) +O(h6). (5.6.6)

Daraus erhält man sofort einen Ausdruck für die zweite Ableitung y′′(x):

y′′(xn) =1h2

(yn+1 + yn−1 − 2yn −

h4

12y(4)(xn)

)+O(h4). (5.6.7)



Inhaltsverzeichnis

Man kann jetzt die Differentialgleichung (5.6.1) verwenden, um einen Ausdruck für die 4-te ABleitungvon y(x) zu finden:

y′′(x) = −k(x) · y(x) ⇒ y(4)(x) = − d2

dx2

(k(x) · y(x)

)(5.6.8)

Um den letzten Ausdruck in (5.6.8) zu berechnen verwendet man die Zweipunkte-Differenzenformel derzweiten Ableitung:

y′′(xn) =yn+1 − 2yn + yn−1

h2+O(h4) (5.6.9)

Und erhält daraus:y(4)(xn) = −kn+1yn+1 − 2knyn + kn−1yn−1

h2(5.6.10)

Setzt man nun (5.6.7) und (5.6.10) in (5.6.1) ein, so erhält man:

−knyn = y′′(xn) =1h2

[yn+1 + yn−1 − 2yn −

h4

12y(4)

]=

=1h2

[yn+1 + yn−1 − 2yn +

h2

12(kn+1yn+1 − 2knyn + kn−1yn−1)

]=

=1h2

[yn+1 + yn−1 − 2yn] +112

[kn+1yn+1 − 2knyn + kn−1yn−1]

Nun fasst man die Koeffizienten nach den Faktoren yi zusammen und sortiert um:

yn+1 =

(2− 5h2

6 kn

)· yn −

(1 + h2

12kn−1

)· yn−1

1 + h2

12kn+1

+O(h6) (5.6.11)

Dies ist die Iterationsformel des Numerov-Algorithmus. Nachdem eine Lösung mit dieser Formel in NSchritten ermittelt wurde, muss sie noch (zumindest für QM-Probleme) normiert werden:

1 !=∫y(x) dx =

Disketisierung

N∑i=0

yi (5.6.12)

Es bleibt nur noch die Frage der Startwerte y0, y1 zu klären. Erwartet man anti-symmetrische Eigen-zustände, so kann man folgendes wählen:

y0 = y(0) = 0, y1 = y(h) 6= 0 beliebig, falls y(x) anti-symmetrisch (5.6.13)

Das begründet sich aus der Bedingung, dass eine anti-symmetrische Eigenfunktion in x = 0 ihr Vorzei-chen wechselt. Der zweite Parameter ist beliebig und kann nachher über die Normierung wieder heraus-gerechnet werden. Für symmetrische Funktionen y(x) verwendet man:

y0 = y(−h/2) 6= 0 beliebig, y1 = y(h/2) = y0, falls y(x) symmetrisch (5.6.14)

Dies nutzt einfach die Symmetrie um 0 aus. Eine weitere Möglichkeit ist:

y0 6= 0 beliebig, y1 = y0 −h2

2k0y0, falls y(x) symmetrisch (5.6.15)

Bei beliebigen Potentialen kann man Methoden höherer Ordnung verwenden, um y(h) = y1 aus y0 undy′(0) zu bestimmen.



Inhaltsverzeichnis

5.6.2. Shooting-MethodeDer Numerov-Algorithmus ermöglicht es die Wellenfunktionen einer stationären Schrödinger-Gleichungzu bestimmen. Es wird für beliebige Energien E eine Lösung ausgeben. Allerdings sind diese Lösungenu.U. nicht normierbar und damit unbrauchbar, denn eine QM-Wellenfunktion ist nur dann normierbar,wenn sie Eigenfunktion zum Hamiltonian

H =(−~2

2m· ∂

2

∂x2+ V (x)

)ist. Es müssen also weiterhin die Eigenwerte dieses Hamiltonian bestimt werden. Dies kann mit den in3.2 besprochenen Methoden geschehen (siehe besonders 3.2.6).

Es gibt aber noch ein zweites Verfahren zur Eigenwertbestimmung, das Shooting-Methode heißt. Sienutzt aus, dass der Numerov-Algorithmus sehr schnell ist. Außerdem wird die Tatsache benötigt, dass„vernünftige“ (also normierbare) Wellenfunktionen für x → ±∞ schnell gegen 0 fallen müssen. Manprobiert mit dem Numerov-Algorithmus solange EnergienE aus, bis die Ergebnisfunktion y(x) für großex λ0 (λ0 sei eine typische Länge im System) gegen 0 strebt. Ist E kein Energieeigenwert, so wirdy(x) → ±∞ (x → ±∞). Man kann dabei dann einen bestimten Energie-Bereich durchrastern. Findetman eine Stelle En, an der ein Minimum von y(x), x → ∞ vorliegt (yn < yn+1, yn−1), so kannman diese Stelle mit einer feineren Rasterung untersuchen und so die Genauigkeit des Eigenwertes En

verbessern.Beim Durchlaufen der Energie E ändert die Lösung y(x) für sehr große x λ0 ihr Vorzeichen, wenn

ein Energieeigenwert Ei passiert wird. Diese Eigenschaft kann ausgenutzt werden, um die Eigenwer-te zu lokalisieren. Da zwischen zwei Vorzeichenwechseln immer nur genau ein Eigenwert liegt, kannman so auch überprüfen, ob alle Eigenwerte gefunden wurde. Jedem Eigenwert kann so eine Knoten-zahl n (Anzahl der Nulldurchgänge bis zu Ermittlung des Eigenwertes) zugeordnet werden und mankann auch das Intervall bestimmen, in dem ein Eigenwert übersprungen wurde. Die folgende Abbildungveranschaulicht das Verfahren nochmals:

E zu klein E richtig

E zu groß

y(x)

xteste hier auf 0-Durchgang

interessierender Bereich

Abbildung 5.6.: Zur Shooting-Methode beim Numerov-Algorithmus

5.7. Duffing-Oszillator

5.7.1. EinführungBeim Duffing-Oszillator handelt es sich um ein bistabiles, gedämpftes und periodisch getriebenes Sys-

tem. Es beschreibt die gedämpfte, periodisch getriebene Bewegung eines Teilchen in einem Doppelmulden-



Inhaltsverzeichnis

Potential (sieh Abbildung ??):

V (x) =14· x4 − 1

2· x2 (5.7.1)

Für das ungetriebene und ungedämpfte System ergibt sich der folgende Hamiltonian

H =p2

2m+

14· x4 − 1

2· x2 (5.7.2)

Daraus ergeben sich die folgenden Bewegungsgleichungen:

x =∂H

∂p=

p

m⇒ p = mx, p = −∂H

∂x= x− x3 (5.7.3)

Diese kann man zu einer einzigen Bewegungsgleichung (zweiter ORdnung) Zustammenfassen. Hierwurden auch gleich ein Dämpfungsterm rx und eine treibende Kraft a · cosωt hinzugefügt:

x(t) + rx(t) + x(t)3 − x(t) = a · cosωt (5.7.4)

Man kann das System analog zu (5.7.3) in ein System erster Ordnung konvertieren:

x = p (5.7.5)

p = −rp+ x− x3 + a · cosωt (5.7.6)

Ein physikalische Beispiel ist ein geladener Defekt in einem dielektrischen Kristall, der durch Mikro-wellen getrieben wird. Die Dämpfung rührt dann aus der Kopplung mit dem Wärmebad der Phononen.Das System ist nicht autonom, d.h. es existiert eine explizite Zeitabhängigkeit. Man kann es durch dieSetzung z(t) := ωt aber in eine autonomes System dreier Gleichungen verwandeln. Dies zeigt, dasses dem System im Prinzip möglich ist chaotisches Verhalten zu zeigen (Poincaré-Bendixson-Theorem,siehe 6.2). Die DGLs zeigen ein solches Chaos auch tatsächlich. Chaotisches Verhalten bedeutet hier,dass die Trajektorie empfindlich von den Startwerten abhängt (tatsächlich entfernen sich zwei Trajekto-rien sogar exponentiell schnell voneinander). Dies bedeutet aber auch, dass das System empfindlich aufnumerische Fehler reagiert. Man kann also verschiedene Integrationsverfahren anhand dieses Systemstesten.

5.7.2. IntegrationDas System wurde mit den Parameter r = 0.25, a = 0.8, sowie ω = 1 von den Startwerten x(0) =−1, x(0) = 1 aus integriert. Abbildung 5.10 zeigt die Ergebnisse. Wie man sieht schwankt das Systemzwischen den Zwei lokalen Minima x = ±1. Die Ergebnisse für die unterschiedlichen Integratorengehen recht weit auseinander. RK2 und RK4 liegen noch relativ lange recht nahe beieinander, währendEuler schon nach einer Periode ein krass anderes Verhalten zeigt.



Inhaltsverzeichnis

-1.5

-1

-0.5

0

0.5

1

1.5

-1.5 -1 -0.5 0 0.5 1 1.5

Euler RK2 RK4

-1.5

-1

-0.5

0

0.5

1

1.5

0 20 40 60 80 100

t

x(t)

x

x'

Abbildung 5.8.: Integration des Duffing-Oszillators mit Euler, RK2 und RK4 jeweils für t = 0..100 und mit2000 Schritten (h = 1

20 )

Die folgende Abbildung 5.9 zeigt einen Vergleich der Performance von RK4 für das Problem. DieDGl wurde mit den selben Parametern, wie oben integriert. Die Abbildung zeigt den Verlauf von x(t)für verschiedene Anzahlen N an Integrationsschritten (h = 100

N ).

Abbildung 5.9.: Integration des Duffing-Oszillators mit RK4 für t = 0..100. Die Schritweiten variiertenzwischen 102 und 105.

Die folgende Abbildung zeigt eine Integration für r = 0.65. Nun bleibt das Teilchen in der linkenPotentialmulde stecken. Die Integration ist hier stabiler, was im nächsten Abschnitt erläutert wird.



Inhaltsverzeichnis

-1.5

-1

-0.5

0

0.5

1

1.5

-1.5 -1 -0.5 0 0.5 1 1.5

Euler RK2 RK4

-1.5

-1

-0.5

0

0.5

1

1.5

0 20 40 60 80 100

t

x(t)

x

x'

Abbildung 5.10.: Integration des Duffing-Oszillators mit Euler, RK2 und RK4 jeweils für t = 0..100 und mit64000 Schritten. Die Parameter waren: r = 0.65, a = 0.8, ω = 1, x(0) = −1, x(0) = 1

5.7.3. StabilitätsanalyseDie Ergebnisse aus dem vorherigen Abschnitt können verstanden werden, wenn man eine Stabilitätsana-lyse durchführt, die entlang einer Trajektorie gültig ist. Dazu betrachtet man allgemein eine ODE derForm

~y′(x) = ~f(~y, ~x) (5.7.7)

Nun stört man das System lokal um ein kleines δ~y und erhält durch Taylor-Entwicklung bis zum erstenGlied:

(~y(x) + δ~y)′ = ~f(~y + δ~y, ~x) = f(~y, x) + ~∇~f(~y, x) · δ~y ⇒ δ~y′ = ~∇~f(~y, x) · δ~y (5.7.8)

Dabei ist A~∇~f(~y, x) die Matrix der ersten partiellen Ableitungen nach den Koordinaten ~y, bei festgehal-tenerm x (Jacobi-Matrix). Hat nun die Jacobi-Matrix A die Eigenwerte λ1, ...λn und Eigenvektoren~ψ1, ..., ~ψn,so kann man δ~y in der Basis der Eigenvektoren darstellen und spezielle Lösungen der zweiten DGl in(5.7.8) lauten:

δ~y = eλit ~ψi ∀i = 1, ..., n. (5.7.9)

Man sieht also, dass sich die Abweiche mit fortlaufender Zeit exponentiell vergrößert, wenn die Eigen-werte einen positiven Realteil haben. Sind alle Eigenwerte negativ (im Realteil), so ist die Trajektorielokal stabil. Ein komplexer Anteil in den Eigenwerten bedeutet einen zusätzlichen oszillatorischen An-teil.

Für den Duffing-Oszillator erhält man aus (5.7.5) und (5.7.6):

~∇~f(~y, x) =

(∂x∂x

∂x∂p

∂p∂x

pp

)=(

0 11− 3x2 −r

)(5.7.10)

Die Eigenwerte dieser Matrix sind:

λ± = −r2±√r2

4+ 1− 3x2 (5.7.11)



Inhaltsverzeichnis

Diese Eigenwerte sind komplexe Zahlen mit negativem Realteil (−r/2), falls 3x2 > r2

4 + 1. λ− hatauf jeden Fall einen negativen Realteil, während λ+ für 1 − 3x2 > 0 positiv wird. Damit wird derDuffing-Oszillator also instabil, sobald x2 < 1

3 ist.Abbildung 5.10 zeigt eine Integration für r = 0.65. Die Oszillation ist dann so stark gedämpft, dass sie

die rechte Potentialmulde nicht mehr erreicht. Man siehr aber, dass die Integratoren vor Allem dann von-einander abweichen, wenn die Trajektorie nahe am (mechnaisch ebenfalls instabilen) lokalen Maximumx = 0 liegt. Dort greift dann die Bedingung x2 < 1

3 für die Instabilität.



Inhaltsverzeichnis

5.8. Zwei- und Drei-Körper-Problem

5.8.1. Das ZweikörperproblemDas Zweikörperproblem beschreibt zwei Mas-

m1

m2

r1

r2

r

R

Schwerpunkt

Abbildung 5.11.: Größen im Zweikörper-Problem

senm1,m2 im Gravitationspotential (siehe Abb.5.11). Wegen der Homogenität des Raumes kanndie Kraft ~F zwischen den Massen nur vo Dif-ferenzvektor der Positionen ~r := ~r1 − ~r2 ab-hängen. Man erhält dann die Bewegungsglei-chungen:

m1~r1 = ~F (~r, ~r, t) = −G · m1 ·m2

r2· ~rr

m2~r2 = −~F (~r, ~r, t) = G · m1 ·m2

r2· ~rr

(5.8.1)

Die Bewegung dieser zwei Körper kann in ei-ne Relativ-Bewegung und eine Bewegung desSchwerpunktes ~R := m1~r1+m2~r2

m1+m2transformiert

werden. Die Addition der zwei Gleichungen (5.8.1) führt hierfür auf

~R = 0. (5.8.2)

Damit bewegt sich der Schwerpunkt linear fort. Für die Relativkoordinate ~R ergibt die Subtraktion derGleichungen (5.8.1):

m1 ·m2

m1 +m2︸︷︷︸=:µ

·~r = −G · m1 ·m2

r2· ~rr

(5.8.3)

Eine einfach Umformung führt dies auf die folgende DGl:

~r = −G · (m1 +m2)r2

· ~rr

= −G ·Mr2

· ~rr

(5.8.4)

Führt man noch die Relativgeschwindigkeit ~v = ~r als Koordinate ein, so erhält man daraus zwei Diffe-rentialgleichungen erster Ordnung, die einfach integriert werden können:

~r = ~v

~v = −GMr2

~r

r∝ 1r2

(5.8.5)

Es ist günstig sich Erhaltungsgrößen (df/dt = 1) den Systems zu suchen, da man an ihnen die Güte derIntegration messen kann: Weicht die berechnete Bahn stark von der realen ab, so ändern sich i.A. auchdie Erhaltungsgrößen. Bewegt sich etwa ein Teilchen im 2-Körper-Problem nicht auf Ellipsen, sondernspiralt auf das Zentrum zu, bzw. davon weg, so ändert sich dabei die Energie. Die Gesamtenergie ist hiereine Erhaltungsgröße. Zwei weitere Erhaltungsgrößen sind der Drehimpulsvektor ~j = ~r × ~v und derRunge-Lenz-Vektor ~e. Für den ersteren gilt:

d~j

dt=

d

dt(~r × ~v) = ~v × ~v︸︷︷︸

=0

+~r × ~v =mit (5.8.5)

−GMr3

(~r × ~r︸︷︷︸=0

) = 0 (5.8.6)

Der Runge-Lenz-Vektor ist definiert als:

~e =~v ×~jGM

− ~r

r. (5.8.7)



Inhaltsverzeichnis

Um hier die Konstanz zu zeigen berechnet man:

d~e

dt=

d

dt

(~v ×~jGM

)− d

dt

(~r

r

)= −~v ×

~j + ~r ×

=0︷︸︸︷~j

GM− d

dt

(~r

r

)=

mit (5.8.5)

~r ×~jr3− d

dt

(~r

r

)(5.8.8)

Nun betrachtet man nur den linken Term im letzten Ausdruck in (5.8.8) und verwendet ( ~A× ~B)× ~C =( ~B( ~A~C)− ~A( ~B ~C):

~r ×~jr3

=(~r × ~v)× ~r

r3=~v · ~r2 − ~r · (~r · ~v)

r3(5.8.9)

Für den rechten Teil erhält man unter Verwendung von r = ~r·~rr :

d

dt

(~r

r

)=~r · r − ~r · r

r2=~v · r2

r3− ~r · (~r · ~v)

r3(5.8.10)

Damit erhält man sofort die zeitliche Konstanz des Runge-Lenz-Vektors ~e. Der Runge-Lenz-Vektor bietetauch eine sehr einfache Möglichkeit die Bahnkurve des Teilchens 2 um das Teilchen 1 zu bestimmen.Dazu betrachtet man den Winkel α zwischen dem kosntanten Vektor ~e und dem Ort ~r. Dazu betrachtetman das Skalarprodukt dieser Vektoren ~e · ~r = e · r · cosα:

~e ·~r = e ·r ·cosα =

(~v ×~jGM

− ~r

r

)·~r =

(~v ×~j) · ~rGM

− ~r · ~rr

=(~r × ~v) · ~vGM

− ~r · ~rr

=j2

GM−r. (5.8.11)

Daraus ergibt sich folgender Zusammenhang zwischen Radius r und Winkel α:

r(α) =j2/GM

1 + e · cosα(5.8.12)

Die folgende Abbildung 5.12 zeigt die Kurven aus (5.8.12). Es ergeben sich die wohlbekannten Kegel-schnitte:• e = 0: Kreisbahn

• 0 < e < 1: Ellipse

• e = 1: Parabel

• e > 1: Hyperbel

Der Runge-Lenz-Vektor zeigt immer vom Zen-trum der Bahn zu ihrem Pericenter, also denzentrumsnächsten Punkt.



Inhaltsverzeichnis

2

1.5

1

0.5

0

0.5

1

1.5

2

2 1.5 1 0.5 0 0.5 1 1.5 2

e=0e=0.5

e=1e=4

r

α

e

Abbildung 5.12.: Kegelschnitte als Lösungen des 2-Körper-Problems

Man kann dieses System verwenden, um Integratoren zu testen, da eine analytische Lösung bekanntist. Für numerische Studien ist es sinnvoll zu einheitenlose Größen überzugehen. Hier bieten sich folgen-de Variablen an:

~s =~r

r0

~w =~v

v0; v0 =

√GM

r0

τ =t

t0; t0 =

√r30GM

Dabei ist r0 ein freier Parameter und skaliert die typische Größe (Radius) des Systems. Aus den ODEs(5.8.5) wird dann:

d~s

dτ= ~w

d~w

dτ= − ~s

s3

(5.8.13)

5.8.2. Das allgemeine n-Körper-ProblemDas bisher besprochene Zweikörperproblem lässt sich leicht auf nKörper erweitern. Man nutzt dann denHamilton-Formalismus und stellt die Hamilton-Funktion des Systems auf:

H =N∑

i=1

~p2i

2mi−

N∑i=1

N∑j=i+1

Gmimj

|~qi − ~qj |=

N∑i=1

~p2i

2mi−

N∑i=1

N∑j=i+1

Gmimj

rij(5.8.14)

Die Gravitationskraft wirkt also immer Paarweise zwischen zwei Teilchen. Der kanonische Impuls derTeilchen ist gerade ~pi = mi~vi. Das Hamilton’sche Prinzip liefert dann die Bewegungsgleichungen:

~qi(t) =∂H∂~pi⇒ d~ri

dt= ~vi

~pi(t) = −∂H∂~qi⇒ d~vi

dt= ~ai

(5.8.15)



Inhaltsverzeichnis

Zu Berechnung der Beschleunigung ~ai betrachtet man folgenden Ausdruck:

d

dx

(1rij

)=

d

dx

(1√

(x− x0)2 + (y − y0)2 + (z − z0)2

)=

− 12·[(x− x0)2 + (y − y0)2 + (z − z0)2

]−3/2 · 2(x− x0) =x− x0

rij(5.8.16)

Daraus erhält man dann mit der Hamilton-Funktion (5.8.17):

~ai =∑i<j

Gmj ·~rijr3ij

(5.8.17)

Man muss also pro Zeitschritt n · (n − 1) ∝ n2 Kräfte berechnen. Die folgenden Integrationsverfahrensind so abgefasst, dass sie leicht für jedes beliebige n-Körper-Problem angewendet werden können. Esmüssen dann nur alle Koordinaten ~r1, ..., ~rn in die Berechnung mit einbezogen werden.

Stabilität und Chaos: Im Zweikörperproblem liegen 6 unabhängige Differentialgleichungen ersterOrdnung vor (siehe (5.8.5)): Zusätzlich hat man die Erhaltungsgrößen Energie E = H(~q, ~p) und dieKomponenten des Drehimpulses ~j = ~r × ~p: Das ergibt zusammen vier Erhaltunsggrößen. Das Systemlässt sich also auf zwei Differentialgleichungen erster Ordnung (bzw. zwei Integrationen) zurückführen.Damit schließt das Theorem von Poincaré-Bendixson (siehe 6.2) ein chaotisches Verhalten aus. Schonim Dreikörper-Problem ist dies nicht mehr garantiert, sodass dort chaotisches Verhalten auftreten kann.

5.8.3. Der Leap-Frog–IntegratorEine Verbesserung des Euler-Verfahrens, speziell für physikalische Bewegungsgleichung (Ort r, Ge-schwindigkeit v, Beschleunigung a), besteht darin, die Geschwindigkeiten zur Propagation zwischenzwei Punkten, also an den Stellen tn+1/2 = tn + h/2 auszuwerten. Damit erhält man folgenden Algo-rithmus:

function LEAPFROG(r0, v0, h, tmax, a(·)) . Integration der DGl von r0, v0, t = 0, bis t = tmax, inSchritten von h

t← 0; i← 0r1/2 ← r0 + v0 · h

2 . Anfangsschrittwhile t ≤ tmax do

vi+1 ← vi + ai+1/2 · h . hier ist: ai+1/2 = a(ti+1/2, ri+1/2

)ri+3/2 ← ri+1/2 + vi+1 · h[rn ← ri+1/2 + vi+1 · h

2

]. evtl. ri berechnen

t← t+ h; i← i+ 1 . Zeit propagierenend whilern+1 ← rn+1/2 + vn+1 · h

2 . letzter Zeitschrittend function

Algorithme 5: Leap-Frog-Integrator

Die Orte ri für ganzzahlige i können optional berechnet werden, wenn man etwa nicht nur den End-punkt, sondern die gesamte Trajektorie benötigt. Sie gehen aber nicht in die weitere Rechnung mit ein.Die folgende Abbildung verdeutlicht das Prinzip. Hier sieht man auch, dass die Berechnungen auf der(schwarzen) Zeitachse „übereinander herspringen“. Daher auch der Name Leap-Frog.



Inhaltsverzeichnis

t1 t2 t3t3/2 t5/2

v1 v2 v3

r3/2 r5/2r2 r3r1

Abbildung 5.13.: Zum Leap-Frog-Integrator

Diese Methode hat lokale Fehler der OrdnungO(h3) (durch die Auswertung an Zwischenstellen). Sieerreicht die Konstanz der Erhaltungsgrößen aber besser, der Integrator ist nämlich symplektisch (Energie-und Volumenerhaltend), da zeit-umkehrbar ist.

Time-Transformed Leap-Frog: Der Leapfrog folgt einem Schema, das in [Mikkola, Aarseth 2001]genau beschrieben wird: Es gilt für hamilton’sche Systeme ~r = ~F (~r), deren Kraftkomponente sich inzwei Teile zerlegen lässt

~F = ~FA + ~FB,

so dass sich die Bewegungsgleichungen der Einzelteile leicht lösen lassen:

~y = ~FA(~y) ~y = ~FB(~y).

Man kann da die Lösung des Gesamtsystems aus den Einzellösungen aproximieren, indem man zuerstSystemA einen halben Schritt h/2 propagiert, danach SystemB einen ganzen Schritt h und zum Schlussnochmals System A einen halben Schritt. Für eine einfache Newton-Dynamik ~r = ~F (~r) ist dies durchfolgende Darstellung möglich:

d

dt

(~r~v

)=(~v0

)+(

0~F (~r)

). (5.8.18)

Daraus erhält man den einfachen Leapfrog:

~r1/2 = ~r0 +h

2~v0 (5.8.19)

~v1 = ~v0 + h · ~F (~r1/2) (5.8.20)

~r1 = ~r1/2 +h

2~v1 (5.8.21)

Man kann nun eine Transformation der Zeitvariable einführen:

dτ = Ω(~r)dt (5.8.22)

Dabei ist Ω(~r) eine beliebige positive Funktion. Führt man eine neue VariableW = Ω ein, so hat (5.8.18)nun folgende Form:

d

dτ

~rt~vW

=

~v/W1/W

00

+

00

~F (~r)Ω(~r)

~vΩ(~r) ·

∂Ω∂~r

. (5.8.23)

Daraus lässt sich wieder ein Leapfrog-Schema ableiten. Dazu beachtet man, dass sich ~r und t, sowie ~vund W gleich transformieren und wendet das obige halbe-ganz-halbe-Schema an:

~r1/2 = ~r0 +h

2~v0W0

t1/2 = t0 +h

21W0

~v1 = ~v0 + h ·~F (~r1/2)Ω(~r1/2)

W1 = W0 + h · ~v0 + ~v12Ω(~r)

∂Ω(~r1/2)∂~r1/2

~r1 = ~r1/2 +h

2~v1W1

t1 = t1/2 +h

21W1



Inhaltsverzeichnis

Hat das System einen separierbaren Hamiltonian H = HA(~p) + HB(~q), so kann man Ω(~r) = HB(~r)wählen. Ein so konstruierter zeit-transformierter Leapfrog hat erstaunliche Eigenschaften, was die Kon-stanz der Erhaltunsggröße Energie angeht (siehe [Mikkola, Aarseth 2001]). Die Energiefehler sind um10−10 kleiner, als bei anderen Verfahren. Außerdem benötigt man wesentlich weniger Funktionsauswer-tungen.

Zeittransformation und logarithmierter Hamiltonian: Man kommt zu einem gleichwertigen Algo-rithmus auch über die Logarithmierung der Hamilton-Funktion. Dazu betrachtet man wie oben die Zeit-Transformation dt = |HB(~r)|−1 dτ . Mit der Poincaré-Transformatio erhält man dann:

Γ = |HB(~r)|−1 ·(HA(~p) +HB(~r)− E

)=HA(~p)− E|HB(~r)|

− 1 (5.8.24)

Dieses Γ ist nicht separierbar, dafür aber Λ = ln(1 + Γ):

Λ = ln(1 + Γ) = ln(HA(~p)− E)− ln |HB(~r)| (5.8.25)

Daraus erhält man dann die neuen Hamilton-Gleichungen:

∂~p

∂τ= −∂Λ

∂~r= − 1

1 + Γ· ∂Γ∂~r

(5.8.26)

∂~r

∂τ=∂Λ∂~p

=1

1 + Γ· ∂Γ∂~p

(5.8.27)

∂t

∂τ=∂Λ∂p0

=1

1 + Γ· ∂Γ∂p0

(5.8.28)

5.8.4. Verlet-IntegratorEin weiterer Integrator für physikalische Bewegungsgleichungen ist das Verlet-Verfahren. Hierbei han-delt es sich um ein Verfahren mit lokalem Fehler der Ordnung h4. Man geht von der Forwärts- undRückwärts-Taylor-Entwicklung aus:

r(tn + h) = r(tn) + v(tn) · h+a(tn)

2· h2 +

a(tn)6· h3 +O(h4) (5.8.29)

r(tn − h) = r(tn)− v(tn) · h+a(tn)

2· h2 − a(tn)

6· h3 +O(h4) (5.8.30)

(5.8.31)

Addiert man die zwei Gleichungen (5.8.29) und (5.8.30), so kann man nach r(tn + h) = rn+1 auflösenund erhält folgende Integrationsvorschrift:

rn+1 = 2rn − rn−1 + anh2 +O(h4) (5.8.32)

Aus der Differenz der Gleichungen (5.8.29) und (5.8.30) erhält man:

vn =rn+1 − rn−1

2h+O(h2) (5.8.33)

Dabei wurde die Taylor-Entwicklung allerdings nur bis zur Ordnung 3 durchgeführt. Man sieht also, dassman die Geschwindigkeiten aus den Orten berechnen kann. Allerdings ist die Berechnung der Geschwin-digkeiten um zwei Ordnungen ungenauer, als die der Orte. Der Integrator eignet sich also besondersdann, wenn für ein Problem nur die Orte bestimmt werden müssen. Desweiteren sind für diesen Integra-tor zwei Startwerte r−1, r0 nötig, da beide in (5.8.32) eingehen. Man kann sich aber einen Startwert r−1

errechnen, durch:r−1 = r0 − v0 · h+

a0

2· h2. (5.8.34)

Dann muss nur noch der Startort und die Startbeschleunigung, die sich aus dem Fraftgesetz ergibt, be-kannt sein.



Inhaltsverzeichnis

5.8.5. Das Hermite-SchemaEine weitere Möglichkeit der Integration ist das Hermite-Schema, ein Predictor-Corrector-Integrator.Bei einem soclhen Verfahren berechnet man zuerst einen Vorhersagewert, der nachher auf höhere Ord-nung korrigiert wird. Man möchte ein Integrationsverfahren kostruieren, dass in der Geschwindigkeiteinen lokalen Fehler der Ordnung O(h5) und im Ort einen Fehler von O(h6) aufweist. Der direkte Wegwäre über eine Taylor-Entwicklung bis zu diesen Ordnungen:

~pn+1 = ~vn + ~an · h+~an

2· h2 +

~a(2)n

6· h3 +

~a(3)n

24· h4 +O(h5)

~rn+1 = ~rn + ~vn · h+~an

2· h2 +

~an

6· h3 +

~a(2)n

24· h4 +

~a(3)n

120· h5 +O(h6)

(5.8.35)

Die Berechnung der ersten ABleitung der Beschleunigung kann noch akzeptiert werden, die Berechnunghöherer Ableitungen wird aber immer teurer. Deswegen beschränkt man die Gleichungen (5.8.35) biszum Term ~an und nimmt diese Werte als Schätzwerte ~rp

n+1, ~ppn+1 an:

~ppn+1 = ~vn + ~an · h+

~an

2· h2 +O(h3)

~rpn+1 = ~rn + ~vn · h+

~an

2· h2 +

~an

6· h3 +O(h4)

(5.8.36)

Nun kann man aber auch die Beschleunigung und deren Ableitung durch eine Taylor-Reihe aproximie-ren:

~an+1 = ~an + ~an · h+~a

(2)n

2· h2 +

~a(3)n

6· h3 +O(h4)

~an+1 = ~an + ~a(2)n · h+

~a(3)n

2· h2 +O(h3)

(5.8.37)

Andererseits lässt sich ~an+1 als ~a(tn+1, rpn+1) und ~an+1 als ~a(tn+1, r

pn+1, r

pn+1) auch explizit aus der

bekannten Formel für die Beschleunigung und deren ABleitung berechnen. Setzt man diese beiden An-sätze gleich, so kann man die Gleichungen nach a(2)

n und a(3)n auflösen und diese schließlich verwenden,

um ~ppn+1 und ~rp

n+1 auf die gewünschte Ordnung zu korrigieren. Aus (5.8.38) folgt nämlich:

12~a(2)

n = −3~an − ~ap

n+1

h2−

2~an + ~apn+1

h

16~a(3)

n = 2~an − ~ap

n+1

h3−

2~an + ~apn+1

h2

(5.8.38)

Man erhält dann nach dem eben erklärten Verfahren die korrigierten Werte ~pcn+1 und ~rc

n+1:

~pcn+1 = ~pp

n+1 +16~a(2)

n h3 +124~a(3)

n h4

~rcn+1 = ~rp

n+1 +124~a(2)

n h4 +1

120~a(3)

n h5(5.8.39)

5.8.6. EvaluationDie Abbildung 5.14 zeigt die Trajektorien und den Energiefehler verschiedener Integratoren, bei h =0.01 und ~r0 = (1, 0);~v0 = (0, 1.05).



Inhaltsverzeichnis

-2

-1.5

-1

-0.5

0

0.5

1

1.5

2

-2.5 -2 -1.5 -1 -0.5 0 0.5 1 1.5 2

EulerRK2RK4

LeapFrog

1e-012

1e-010

1e-008

1e-006

0.0001

0.01

1

0 10 20 30 40 50 60 70 80 90 100

EulerRK2RK4

LeapFrog

Abbildung 5.14.: Evaluation verschiedener Integratoren im 2-Körper-Problem

5.9. Populationsdynamik und Ratengleichungen

5.9.1. Einzelne PopulationenMan betrachtet eine Population N(t) mit fester Geburtsrate b und Sterberate s:

dN

dt= (b− s)N = rN ⇒ N(t) = N0e

rt (5.9.1)

Diese DGl hat auch nur eine (instabile) stationäre Lösung: N(t) = N0 = 0. Dieses Wachstumsmodellist sehr unrealistische, da es exponentielles Wachstum über alle Grenzen vorhersagt. In realistischenSystemen gibt es aber immer limitierende Faktoren K, wie etwa das Nahrungsangebot. Man kann dannnach Verhulst (1836) die folgende limitierte Dynamik aufstellen:

dN

dt= r ·N · (1−N/K) (5.9.2)

Dies lässt sich folgendermaßen verstehen: Bisher wurden einfach in jedem Zeitschritt dt r ·N · dt Lebe-wesen gebohren. Je mehr Lebewesen also da sind, desto mehr Nachkommen können diese Zeugen (alsor Kinder pro Lebewesen in der Zeit dt). Nun führt man eine populationsabhängige Sterberate r·N

K ∝ Nein. Je mehr Lebewesen vorhanden sind, desto höher wird die Sterberate, weil mehr Lebewesen auchmehr Ressourcen verbrauchen. Hier ist wieder N∗

1 = 0 eine stationäre Lösung. Eine zweite stationäreLösung ist N∗

2 = K. Auch diese DGl lässt sich analytisch lösen. Man erhält:

N(t) =N0 ·K · ert

K +N0(ert − 1)(5.9.3)

Für t → ∞ geht diese Lösung gegen die Konstante K. Dieses System wird in diskretisierter Form, alslogistische Abbildung in 6.3 diskutiert. Das Aussehend er Kurve N(t) ist in Abbildung 6.1 gezeigt.



Inhaltsverzeichnis

Abbildung 5.15.: analytische Lösung der Verhulst-Dynamik, für r = 15,K = 1, N0 = 0.001

5.9.2. Interagierende PopulationenDas Lotka-Volterra-Modell beschreibt die interagierenden Populationen zweier SpeziesN1(t)undN2(t).Man hat folgendes DGL-System:

dN1

dt= N1 · (a− b ·N2)

dN2

dt= N2 · (c ·N1 − d)

(5.9.4)

Alle Parameter a, b, c, d sind positiv. Die DGl kann so verstanden werden: Ohne N2 wächst die Populati-on N1 exponentiell. Sie wird aber von der Spezies N2 gefressen, was mit einer Rate −bN1N2 geschieht.Die Spezies N2 frisst N1, stirbt also ohne N1 aus. Dafür steigt die Population mit cN1N2, wenn beideSpezies vorhanden sind.

5.10. Lorenz-Atraktor

Der folgende Abschnitt basiert teilweise auf der WWW-Seite von Andreas Jung (http://andreas.welcomes-you.com/research/talks/lorenz/) ud vor Allem auf der Seminararbeit [Jönck, Prill 2003].Das Lorenz-System beschreibt die Konvektion in einer viskosen Flüssigkeit, die sich in einem Tempera-turgradienten befindet (zwischen zwei unterschiedlich warmen Metallplatten). Die Abbildung 5.17 zeigtdie Situation.

DT

x

y

z

T

T+DT

h

Abbildung 5.16.: Lorenz-System

Dieses Experiment wurd 1900 das erste Mal von Bernard durchgeführt. Der Temperaturunterschiedbeträgt gerade ∆T und ist ein kritischer Parameter für das Verhalten des Systems. Die unteren Teile derFlüssigkeit dehnen sich aus und wollen aufsteigen. Die oberen Teile ziehen sich zusammen und sinkenaufgrund der Gravitation ab. Dadurch bilden sich z.B. Konvektionswalzen aus. Bei verschiedenen ∆Tgibt es unterschiedliches Verhalten:

1. Bei kleinen ∆T verhindert die Viskosität eine freie Bewegung der Flüssigkeit. Es kommt zu reinerWärmeleitung.


http://andreas.welcomes-you.com/research/talks/lorenz/



Inhaltsverzeichnis

2. Ab einer ersten krit. Temperaturdifferenz ∆T1 bilden sich Konvektionsrollen aus, wie sie in Abb.5.17 zu sehen sind.

3. Oberhalb einer zweiten Temperaturdifferenz pulsiert die Strömung (also deren Geschwindigkeit)periodisch.

4. Bei weiterer Erhöhung kommt noch eine zusätzliche, periodische Teilströmung hinzu. Nach ei-nem letzten kritischen Punkt wird das System schlagartig turbulent und chaotisch. Alle anderenZustände sind laminar.

Zur mathematischen Modellierung geht man von den folgenden Grundgleichungen für Flüssigkeits-Strömungen aus:

1. Kontinuitätsgleichung (Massenerhaltung):

∂ρ

∂t+ div(ρ~v) = 0 (5.10.1)

2. Navier-Stokes-Gleichung (Impulserhaltung):

ρd~v

dt= ρ

∂v

∂t+ ρ · (~v · ~∇)~v = ρ~g − ~∇p+ η∇2~v (5.10.2)

Dabei ist ~g = (0, 0,−g)t die Erdbeschleunigung in z-Richtung, ~∇p beschreibt den Druckgradien-ten und η∇2~v berücksichtigt die Viskosität. Die Navier-Stokes-Gleichung beschreibt das Verhaltendes Geschwindigkeitsfeldes ~v einer Ströhmung unter gewissen Bedingungen (Dichte, Druck ...).

3. Wärmetransportgleichung (Energieerhaltung):

dT

dt=(∂T

∂t+ (~v · ~∇)T

)=

λ

ρcV ·· ~∇2T (5.10.3)

In den obigen Gleichungen ist η die dynamische Viskosität, cV die Wärmekapazität und λ der Wärme-leitkoeffizient. Man bringt nun einige Näherungen an:

1. Die Dichte ist überall (auch zeitlich) konstant (ρ = ρ0,∂ρ∂t = 0), außer im Term der Erdbeschleu-

nigung ρ~g.

2. Der Druck hat keinen Einfluss auf die Dichte der Flüssigkeit (inkompressibel) und die Temperatu-rabhängigkeit ist linear:

ρ(~x, t) = ρ0 · [1− α(T (~x, t)− T0)] . (5.10.4)

Mit diesen Annahmen erhält man dann aus (5.10.1), (5.10.2) und (5.10.3):

div~v = 0 (5.10.5)∂~v

∂t+ (~v · ~∇)~v = −g · [1− α(T (~x, t)− T0)] · ~ez −

1ρ0

~∇p+η

ρ0︸︷︷︸=:ν

~∇2~v (5.10.6)

∂T

∂t+ (~v · ~∇)T =

λ

ρcV ·︸︷︷︸=:χ

·~∇2T (5.10.7)

Weiter kann man annehmen, dass sich die Konvektionsrollen in y-Richtung unendlich ausdehnen. Da-mit erhält man ein 2-dimensionales System, in dem man folgende Koordinaten und Geschwindigkeiteneinführt:

x := x1, z := x3, u := v1, w := v3.



Inhaltsverzeichnis

Mit diesen Definitionen wird aus (5.10.5) - (5.10.7):

∂u

∂x+∂w

∂z= 0 (5.10.8)

du

dt=∂u

∂t+ u

∂u

∂t+ w

∂u

∂z= − 1

ρ0

∂p

∂x+ ν ·

(∂2u

∂x2+∂2u

∂z2

)(5.10.9)

dw

dt=∂w

∂t+ u

∂w

∂t+ w

∂w

∂z= − 1

ρ0

∂p

∂z+ ν ·

(∂2w

∂x2+∂2w

∂z2

)+ g · [1− α(T − T0)](5.10.10)

∂T

∂t+ u

∂T

∂x+ w

∂T

∂z= χ · ~∇2T (5.10.11)

Man führt nun eine Stromfunktion Ψ(x, z) ein, die folgende Eigenschaften aufweist:

(u,w) =(−∂Ψ∂z

,∂Ψ∂x

)(5.10.12)

∇2Ψ :=(∂2

∂x2+

∂2

∂z2

)Ψ =

∂w

∂x− ∂u

∂z(5.10.13)

∇4Ψ := ~∇2(~∇2Ψ) =∂

∂x~∇2w − ∂

∂z~∇2u (5.10.14)

Das Geschwindigkeitsfeld (als Vektorfeld) (u,w) ist also eine Art Gradient einer PotenitalfunktionΨ. Das Temperaturprofil ist in erster Näherung linear. Nichtlinearitäten werden durch eine FunktionΘ(x, z, t) dargestellt:

T (x, z, t) = T0 + ∆T ·(1− z

h

)+ Θ(x, z, t). (5.10.15)

Man berechnet nun ∂∂x (5.10.10) − ∂

∂z (5.10.9), um die Durck-Abhängigkeit (p-Term) dieser Form derNavier-Stokes-Gleichung zu eliinieren:

∂

∂t

(∂w

∂x− ∂u

∂z

)︸︷︷︸

=~∇2Ψ

+∂

∂x

(u∂w

∂x+ w

∂w

∂z

)− ∂

∂z

(u∂u

∂x+ w

∂u

∂z

)︸︷︷︸

=:∂(Ψ, ~∇2Ψ

∂(x,z)

=

= ν ·(∂

∂x~∇2w − ∂

∂z~∇2u

)︸︷︷︸

=~∇4Ψ

+∂

∂x

[1− α(T − T0)

]· g︸︷︷︸

=g·α· ∂Θ∂x

(5.10.16)

Dabei wurde folgende Bezeichnung/Schreibweise verwendet:

∂(a, b∂(x, z)

:=(∂a

∂x

∂b

∂z− ∂b

∂x

∂a

∂z

). (5.10.17)

Außerdem kann man auch Gleichung (5.10.11) mit den Funktionen Ψ und Θ ausdrücken. Die erreichtman Einfach durch Einsetzen von (5.10.15) in (5.10.11):

∂T

∂t+ u

∂T

∂x+ w

∂T

∂z=

∂Θ∂t− u∂Θ

∂x+ w

(−∆T

h+∂Θ∂z

)=

=∂Θ∂t−∂Ψ∂z︸︷︷︸

=u

∂Θ∂x

+∂Ψ∂x︸︷︷︸=w

(−∆T

h+∂Θ∂z

)=

=∂Θ∂t

+∂(Ψ, Θ)∂(x, z)

− ∆Th

∂Ψ∂x

=

= χ · ~∇2Θ.



Inhaltsverzeichnis

Insgesamt erhält man dann ein System von zwei partiellen, gekoppelten Differentialgleichungen für dieBénard-Konvektio:

∂

∂t~∇2Ψ = −∂(Ψ, ~∇2Ψ)

∂(x, z)+ ν ~∇4Ψ + g · α · ∂Θ

∂x(5.10.18)

∂Θ∂t

= −∂(Ψ,Θ)∂(x, z)

+∆Th

∂Ψ∂x

+ χ~∇2Θ (5.10.19)

Zu Lösung dieser Gleichungen wählt man die einfachen Randbesingungen Ψ = 0 und ~∇2Ψ = 0 fürz = 0, h, also an den Begrenzungsflächen. Damit kann man als Lösungen die folgenden (zweifachen)Fourierreihen als Ansatz annehmen:

Ψ(x, z, t) =∞∑

m=−∞

∑n

Ψmn(t) · exp[i · 2πh ·

(mLx+

n

2hz)]

Θ(x, z, t) =∞∑

m=−∞

∑n

Θmn(t) · exp[i · 2πh ·

(mLx+

n

2hz)]

Für diesen Ansatz fand Barry Saltzman durch numerische Integration, dass nur drei Amplituden fürnichtperiodische Lösungen nicht gegen 0 tendieren. Mit diesen drei Komponenten ergibt sich:

Ψ(x, z, t) =χ(1 + a2)

√2

2·X(t) · sin(πax) sin(πz)

Θ(x, z, t) =∆Tπ

Racrit

Ra

(√2 · Y (t) · cos(πax) sin(πz)− Z(t) · sin(2πz)

)Dabei sind X,Y, Z Funktionen der Zeit t und a = Zellenhöhe

Zellenbreite beschreibt die Geometrie der Konvek-

tionszellen. Desweiteren ist Ra = αgh3∆Tχν die Rayleighzahl und Racrit = π4(1+a2)3

a2 die kritischeRayleigh-Zahl. Setzt man nun diese Lösungen in (5.10.18) und (5.10.19) ein, so erhält man das sog.Lorenz-System:

X = σ · (Y −X) (5.10.20)

Y = r ·X − Y −XZ (5.10.21)

Z = −bZ +XY (5.10.22)

In diesen Gleichungen sind die folgenden (dimensionslosen) Parameter enthalten:

• σ = νχ = ηcV

λ heißt Prandtl-Zahl und gibt die Trägheit des hydrodynamischen Systems an. Fürσ →∞ ist das System trägheitslos und folgt einer Temperaturänderung instantan.

• b = 41+a2 ist ein Maß für die Zellgeometrie

• r = RacritRa ist die relative Rayleigh-Zahl.

Für die FUnktionen X,Y, Z gibt es ebenfalls physikalische Analogien:

• X(t) ∝ Ψ ist proportional zur Intensität der Konvektionsströmung

• Y (t) ist proportional zur Temperaturdifferenz

• Z(t) ist proportional zur Abweichung vom lineraren Temperaturprofil

Die Fixpunkte dieses Systems erhält man durch 0-Setzen aller drei Gleichungen:

O = (0, 0, 0), R±,=(±(√b(r − 1), ±(

√b(r − 1), r − 1

)(5.10.23)

Für die Fixpunkte R± muss r > 1 gelten, da sonst komplexe Lösungen vorliegen (komplexe Wurzeln!).



Inhaltsverzeichnis

Man kann das Lorenz-System mit RK4 integrieren. Zum einen erhält man so einen Plot der Verhaltensvon (X,Y, Z). Zum Anderen kann man über die speziellen Lösungen für Ψ und Θ auf die Teperaturund das Geschwindigkeitsfeld zurückrechnen. Die Abbildung zeigt Ergebnisse einer SIulation für dieParameter r = 28, b = 8/3, σ = 10. Die Integration startet bei (0.1, 0.1, 0.1), also nahe am Fixpunkt O.Der Grenzzyklus des Lorenz-Systems ist ein sogenanter seltsamer Atraktor, also ein Atraktor fraktalerDimension.

Abbildung 5.17.: Lorenz-System: links ist (X,Y,Z) aufgetragen; rechts sieht man das Temperaturfeld farbko-diert und das Geschwindigkeitsfeld als Vektoren.

Das Lorenz-System zeigt unterschiedliches Verhalten in Abhängigkeit vom kritischen Paramater r. ZuAnfang gibt es nur einen Fixpunkt, nämlichO = (0, 0, 0). Er ist bis zu einer ersten Grenze stabil. Danachentstehen zwei neue Fixpunkt R±. Diese sind zuerst stabil (Hopf-Bifurkation), währen O Sattelpunktwird (d.h. aus gewissen Richtungen zeiht er Trajektorien an und stößt sie dann in andere Richtungen ab).O bleibt für alle größeren r Sattelpunkt. Die Eigenwerte der Jacobi-Matrix erhalten später an R± einenkomplexen Anteil, was zu oszillierenden, aber immernoch kontrahierenden Lösungen dort führt. D.h.die Trajektorien spiralen zu diesen Fixpunkten. Wird r weiter vergrößert, so bildet sich zuerst an R±je ein instabiler Grenzzyklus aus, der danach in instabil abstoßende Fixpunkte übergeht. Nun wird dieTrajektorie zwischen den Fixpunkten hin- und hergezogen. Dieses Verhalten ist chaotisch und für diesenFall ist auch die Trajektorie in 5.17 gezeichnet. Dabei ist zu beachten, dass die Trajektorien immer nureinen begrenzten Bereich des Phasenraumes einnehmen, die Trajektorien unvorhersagbar zwischen denUmgebungen von R+ und R− wechseln. Außerdem reagieren die Trajektorien kritisch auf veränderteAnfangswerte. Alle diese EIgenschaften sind typisch für ein chaotisches System.



Inhaltsverzeichnis

5.11

.Zu

sam

men

stel

lung

der

Verf

ahre

n

Verf

ahre

nPr

oble

mkl

asse

lokale

rFeh

ler

Startw

erte

Bem

erku

ngen

Eul

erSt

anda

rdO

(h2)

1•

sim

pels

terI

nteg

rato

r

RK

2St

anda

rdO

(h2)

1•

Aus

wer

tung

derA

Ble

itung

anei

nerZ

wis

chen

stel

le

RK

4St

anda

rdO

(h4)

1•

Aus

wer

tung

der

Abl

eitu

ngan

zwei

Zw

isch

enst

elle

n,zu

mA

nfan

gun

dE

nde,

dana

chM

ittel

ung

Num

erov

y′′ (x)+k(x

)·y

(x)

=0

O(h

6)

2•

Spez

ialv

erfa

hren

,z.

B.

für

zeitu

nabh

ängi

geSc

hröd

inge

r-gl

eich

ung

•be

nötig

tzw

eiSt

artw

erte

(for

wär

ts/r

ückw

ärts

-Int

egra

tion)

Leap

-Fro

gN

ewto

nO

(h3)

1•

optim

iert

erIn

tegr

ator

fürN

ewto

n’sc

heSy

stem

e

time-

tran

sfor

med

Leap

-Fro

gN

ewto

nO

(h2)

1•

verf

eine

rte

Ver

sion

,die

Ene

rgie

gutk

onst

anth

ält

Verl

etN

ewto

nO

(h4),

O(h

2)

2•O

(h4)

inde

rOrt

skoo

rdin

ate

•O

(h2)

inde

rGes

chw

indi

gkei

tsko

ordi

nate

•vo

rwär

ts-/

rück

wär

ts-I

nteg

rato

r

Her

mite

-Sch

ema

New

ton

O(h

4),

O(h

5)

2•O

(h5)

inde

rOrt

skoo

rdin

ate

•O

(h4)

inde

rGes

chw

indi

gkei

ts-/

Impu

lsko

ordi

nate

•Pr

edic

tor-

Kor

rekt

or-V

erfa

hren

•be

nötig

tAus

wer

tung

dere

rste

nA

blei

tung~a(~r,~p

)

Bem

erku

ng:D

abei

ist:

•St

anda

rd:D

iffer

entia

lgle

ichu

ngen

erst

erO

rdnu

ng:~y

=~ F(~y

)•

New

ton:

New

tons

che

Bew

egun

gsgl

eich

unge

n:~r

=~v,

~v=

~a(~r

,~v,t

),bz

w.~r

=~ F(~r

,t)



6. Diskrete Dynamik

6.1. Motivation

Diskrete Dynamik tritt an verschiedenen Stellen auf. Die augenfälligste ist wohl die Diskretisierung einesDGl-Systems. Allgemein haben diskrete Abbildungen folgende Form:

~xn+1 = ~f(~xn) (6.1.1)

Man propagiert das System also in dis-Abbildung 6.1.: Verhulst-Dynamik

0

2

4

6

8

10

0 2 4 6 8 10

ρ=0.5, β=0.5, x0=1ρ=-0.5, β=0.5, x0=1

ρ=1, β=0.5, x0=1ρ=1, β=5*10

-10, x0=1

kreten (immer gleich langen) Schritten ent-lang einer Koordinate. Ein einfaches Bei-spiel ist die Populationsdynamik nach Ver-hulst:

xn+1 = ρxn · (1− βxn) (6.1.2)

Die nebenstehende Abbildung zeigt Be-rechnungen für das System und verschie-dene Parameter. Der Parameter ρ beschreibtdie Wachstumsrate zwischen zwei Gene-rationen. Mi β = 0 würde sich damit ex-ponentielles Wachstum ergeben. Ein ne-gatives ρ bedeutet eien schrumpfende Po-pulation. Der Parameter β begrenzt dasWachstum.

Ursprünglich wurde diese Populationsdynamik als kontinuierliche ODE betrachtet:

dx

dt= rx · (1− bx), ⇒ x(t) =

x0ert

1 + bx0(ert − 1)→ 1

b(t→∞) (6.1.3)

Daraus erhält man (6.1.2), indem man Euler-Diskretisierung anwendet:

xn+1 = xn + ∆t · rx · (1− bx) = (1 + ∆tr)xn − br∆tx2n (6.1.4)

Dies entspricht der Form (6.1.2), wenn man die Setzungen ρ = 1 + ∆tr und β = br∆t1+∆tr einführt.

Diese Diskretisierung führt eine neue Qualität in das System ein. Ein ein- oder zwei-dimensionales kon-tinuierliches System, wie etwa (6.1.3) kann kein chaotisches Verhalten zeigen (das sicher der Satz vonPoincaré-Bendixson). Das diskretisierte System zeigt aber eine Reihe neuer Phänomene, wie etwa Pe-riodenverdopplung und Chaos, die im kontinuierlichen System nicht vorhanden waren. Dies zeigt, dassbeim Diskretisieren (also beim numerischen Lösen) von ODEs immer die Gefahr besteht ein dynami-sches Verhalten durch die Numerik aufzuprägen, das so im System eigentlich nicht vorkommt.

Man kommt aber nicht nur über die Diskretisierung von DGls zu diskreter Dynamik. Eine weitereMöglichkeit sind Phasen-Raum oder Poincaré-Schnitte, bei denen nur der Durchgang einer Trajektoriedurch eine niederdimensionale Hyperebene des Phasenraumes betrachtet wird. Man erhält dann eineMenge von Punkten in dieser Ebene. Die folgende Abbildung verdeutlicht, wie ein zweidimensionalerPoincaré-SChnitt durch einen dreidimensionalen Phasenraum entsteht:

62

Inhaltsverzeichnis

x1

x2

x3

x4

kontinuierliche Dynamik

diskreteDynamik

Schnitt-Ebene Schnitt-Ebene

Abbildung 6.2.: Verdeutlichung zum Poincaré-Schnitt

6.2. Definitionen und Sätze

In diesem Abschnitt werden die grundlegenden Begriffe und Sätze der Diskreten Dynamik zusammen-gefasst. Wie bereits gesagt, wird eine diskrete Dynamik durch eine Iterationsvorschrift der Form

xn+1 = f(xn) (6.2.1)

definiert. Man hat dann folgende weiteren Begriffe definiert:

Orbit/Trajektorie: Eine Menge X = x0, x1, ... von Punkten xi, die aus einer diskreten Abbildunghervorgehen heißt Trajektorie oder Orbit.

Fixpunkt: Ein Punkt x∗ heißt Fixpunkt einer Dynamik f(·), falls gilt:

f(x∗) = x∗ (6.2.2)

Ein Fixpunkt wird also bis in alle Ewigkeit auf sich selbst abgebildet.

p-periodischer Orbit: Ein Orbit heißt p-periodisch, wenn er nach p Iterationen wirder zum Ausgangs-punt zurückkehrt:

xn+p = xn (6.2.3)

Ein Orbit, der immer zwischen zwei Punkten hin- und herspringt wäre also ein 2-periodischerOrbit.

p-fach iterierte Abbildung: nur eine Schreibweise

f (p)(xn) = f(f(...f︸︷︷︸p mal

(xn))) (6.2.4)

Auch eine solche Abbildung kann einen Fixpunkt haben. Es gilt dann natürlich:

xn+p = f (p)(xn) = xn (6.2.5)



Inhaltsverzeichnis

Stabilität: Ein Fixpunkt x∗ heißt stabil, wenn er Punkte aus seiner Umgebung anzieht. Startet also dieDynamik ind er Umgebung von x∗, so läuft sie auf diesen Punkt zu. Notwendig und hinreichend für dieStabilität ist: ∣∣f ′(x∗)∣∣ < 1 (6.2.6)

zum Beweis: Man betrachtet Punkte xn, die Nahe an einem Fixpunkt x∗ liegen und definiert noch δn =xn − x∗. Durch Taylor-Entwicklung von f(x∗ + δn) erhält man dann:

|δn+1| = |xn+1 − x∗| = |f(xn)− x∗| = |f(x∗ + δn)− x∗| = |δn| ·∣∣f ′(x∗) +O(δn)

∣∣Für p-periodische Orbits erhält man daraus:∣∣∣∣ ddxf (p)(xk)

∣∣∣∣ < 1 ∀xk aus dem Orbit. (6.2.7)

Außerdem sieht man sofort: Die p Punkte eines p-periodischen Orbits von f sind entweder alle stabil,oder alle instabil.

Superstabilität: Ein Fixpunkt x∗ heißt superstabil, wenn:∣∣f ′(x∗)∣∣ = 0 (6.2.8)

Durch Taylor-Entwicklung erhält man dann:

|δn+1| = |xn+1 − x∗| =∣∣δ2n∣∣ · ∣∣f ′′(x∗) +O(δ2n)

∣∣Also ist die Konvergenz in der Umgebung eines superstabilen Punktes schneller, als in der Umgebungeines einfachen, stabilen Fixpunktes.

Satz von Singer: Für stetige Funktionen f : [0, 1] → [0, 1] mit f(0) = f(1) = 0 , die nur eineinziges Maximum xm auf [0, 1] besitzen, gibt es maximal einen stabilen Orbit, wenn ihre Schwarz’scheAbleitung S[f ](x) überall negativ ist:

S[f ](x) =d

dy

(1√f ′(y)

)∣∣∣∣∣y=x

=f ′′′(x)f ′(x)

− 32

(f ′′(x)f ′(x)

)2

< 0, ∀x ∈ [0, 1] (6.2.9)

Der folgende Satz von Poincaré-Bendixson beschränkt die Dynamik eines kontinuierlichen Systemsim ein- und zweidimensionalen auf drei einfache Fälle. Dür diskrete Systeme gilt dies natürlich nicht!

Satz von Poincaré-Bendixson: Sei D ⊂ R2,R1 eine kompakte Teilmenge des ein- oder zweidimen-sionalen Phasenraums einer Differentialgleichung

~x = ~f(~x), ~x ∈ R1,R2, ~f : R1,R2 → R1,R2

Außerdem enthalte D nur endlich viele Fixpunkte der DGl und ~f(·) sei stetig differenzierbar auf D. Fürjede Phasenraumtrajektorie φ(D) ⊂ D der DGl, die für alle t > 0 in D bleibt gilt, nun für t → ∞ eineder folgenden drei Möglichkeiten:

(i) φ geht gegen einen Fixpunkt ~x0

(ii) φ geht gegen einen periodischen Orbit ω ∈ D

(iii) φ ist selbst ein periodischer Orbit.

Folgerungen:

1. Wenn D keinen Fixpunkt enthält und eine Trajektorie in D bleibt, so strebt sie einem periodischenOrbit zu.

2. In einem kontinuierlichen ein- oder zweidimensionalen System kann kein chaotisches Verhaltenauftreten.



Inhaltsverzeichnis

6.3. Logistische Abbildung

Die logistische Abbildung wird definiert durch:

xn+1 = fr(xn) := 4rxn · (1− xn), r > 0 (6.3.1)

Man erhält sofort die erste Ableitung

f ′r(x) = 4r · (1− 2x). (6.3.2)

Die folgende Abbildung zeigt einige Orbits der logistischen Abbildung für verschiedene r und den Start-wert x0 = 0.4. Wie man in den folgenden Abschnitten sehen wird ist die Wahl des Startwertes unerheb-lich.

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50

r=0.3

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50

r=0.85

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50

r=0.885

0

0.2

0.4

0.6

0.8

1

0 10 20 30 40 50

r=0.95

Abbildung 6.3.: Verschiedene Iterationen der logistischen Abbildung

Die nun folgende Abbildung illustriert die 2- und 4-fach Iterierte der logistischen Abbildung und zeigt,wie man die Arbeitsweise dieser Dynamik bildlich veranschaulichen kann. Zuerst wird der Punkt (x0, 0)auf die Funktion f(x) projiziert und von dort nach rechts auf die Winkelhalbierende. Von da aus wiederauf die Funktion und zurück auf die Winkelhalbierende ... usw. ad infinitum. Die Projektion auf dieWinkelhalbierende entspricht der Setzung x = fr(x), da sie die Identitätsabbildung darstellt.



Inhaltsverzeichnis

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

f(x)f

(2)(x)

f(4)

(x)

f(x)

x

0

0.1

0.2

0.3

0.4

0.5

0 0.1 0.2 0.3 0.4 0.5

r=0.3 x0=0.4

0

0.1

0.2

0.3

0.4

0.5

0.6

0 0.1 0.2 0.3 0.4 0.5 0.6

r=0.5 x0=0.4

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

r=0.85 x0=0.1

0

0.2

0.4

0.6

0.8

1

0 0.2 0.4 0.6 0.8 1

r=0.95 x0=0.05

Abbildung 6.4.: Erste, zweite und vierte Iterierte der logistischen Abbildung, sowie geometrische Konstruk-tion mit unterschiedlichen Startwerten

6.3.1. FixpunkteEin Fixpunkt x∗ muss natürlich f(x∗) = x∗ erfüllen. Durch einsetzen in die Definition (6.3.1) erhältman die zwei Lösungen:

x∗0 = 0 und x∗1 = 1− 14r. (6.3.3)

Um die Stabilitätseigenschaften dieser Punkte zu bestimmen, setzt man sie in die erste Ableitung (6.3.2)ein und prüft, wo diese betragsmäßig kleiner als eins ist. Man erhält folgendes Ergebnis:

r < 14 : Der Fixpunkt x∗0 = 0 ist stabil. x∗1 ist instabil.

r > rt = 14 : Hier wird x∗0 = 0 instabil und x∗1 wird stabil (siehe r = 0.3 in obiger Abbildung).

r > r0 = 34 : Es kommt zu einer Bifurkation. Der Fixpunkt spaltet sich in zwei Zweige auf, zwischen

denen die Abbildung hin- und herspringt (siehe r = 0.85 in obiger Abbildung).

r > r1 = 1+√

64 : Es kommt zu einer weiteren Bifurkation. Die Zweige spalten beide in jeweils zwei

neue Zweige auf. Die Abbildung springt jetzt zwischen vier Punkten hin und her (siehe r = 0.885in obiger Abbildung).

r > r2: Es kommt wieder zu einer Verdopplung der Zweige. Am Punkt ri wird ein Orbit der Periode 2i

instabil und es entsteht ein stabiler orbit der Periode 2i+1. Dies geht unendlich so weiter, wobeidie Punkte ri immer näher zusammenrücken.

r > r∞: Ab hier gibt es keine Bifurkationen mehr. Die Abbildung gleitet ins Chaos ab (siehe r = 0.95in obiger Abbildung). Der Wert r∞ stellt den Grenzwert der Folge ri für i→∞ dar.

Die folgende Abbildung zeigt f(x), sowie die 2- und 4-fach Iterierte. Daneben ist das sog. Feigenbaum-Diagramm zu sehen. Für jeden Wert von r werden etwa 500 Werte xn berechnet und als Punkte einge-tragen. In diesem Diagramm kann man deutlich die Periodenverdopplung und den Übergang ins Chaosbeobachten.



Inhaltsverzeichnis

Abbildung 6.5.: Feigenbaum-Diagramm der logistischen Abbildung

6.3.2. Feigenbaum-Konstante und Lyapunov-ExponentMitchel Feigenbaum hat einen allgemeingültigen Zusammenhang (gilt für alle Abbildungen mit Peri-odenverdopplung) zwischen den Abständen aufeinanderfolgender Bifurkationen gefunden:

limn→∞

rn − rn−1

rn+1 − rn= lim

n→∞

∆rn∆rn+1

= δ = 4.66920... (6.3.4)

Die ri konvergieren mit der Feigenbaumkonstante wie

rn ≈ r∞ + c · δ−n, r∞ ≈ 0.8924. (6.3.5)

Im chaotischen Bereich reagieren Orbits sehr empfindlich auf die Anfangsbedingung, während es imperiodischen Bereich eigentlich egal ist, mit welchen 0 < x0 < 1 man die Iteration startet. Wie es fürchaotische Systeme typisch, ja definierend ist, streben die Orbits für zwei benachbarte Startwerte x0

und x0 + ε exponentiell auseinander. Sei ∆x0 = |x0 − y0| der Abstand zweier Startpunkt x0, y0 derAbbildung. Dann steigt dieser Abstand mit steigendem n exponentiell an:

∆xn ∝ eλn (6.3.6)

Dabei ist λ der Lyapunov-Exponent, der durch folgende Beziehung definiert ist:

λ = limn→∞

1n

n−1∑k=0

log∣∣f ′(xk)

∣∣ . (6.3.7)

Ist λ > 0, so liegt eine chatotische Region vor. Für λ < 0 nähern sich die Trajektorien zweier benachbar-ter Punkte exponentiell an und die Dynamik ist stabil, da keine Sensitivität auf die Anfangsbedingungenmehr besteht. Die folgende Abbildung zeigt den Lyapunov-Exponenten der logistischen Abbildung (be-rechnet über eine Näherung von (6.3.7) mit 1000 Summengliedern):



Inhaltsverzeichnis

-1

-0.5

0

0.5

1

0 0.2 0.4 0.6 0.8 1

Abbildung 6.6.: Lyapunov-Exponent bei der logistischen Abbildung

Betrachtet man das Feigenbaum-Diagramm, so stellt man fest, dass es auch im chaotische Bereichnoch Struktur gibt. So gibt es Bänder, in denen stabile Orbits zu existieren scheinen. Diese lösen sichdann wieder durch Periodenverdopplung auf, die durch die gleichen Gesetze beschrieben wird, wie dieHauptbifurkation. Dies zeigt eine weitere Eigenschaft, die typisch für chaotische Systeme ist: Selb-stähnlichkeit. Die folgende Abbildung zeigt den chaotischen Bereich und zusätzlich die Funktionenf (k)(r, x = 1/2). Man erkennt, dass die Inseln im Chaos von diesen Funktionen begrenzt werden. Au-ßerdm ist ein Zoom in den chaotischen Bereich abgebildet:

Abbildung 6.7.: Zoom in das Feigenbaum-Diagramm der logistischen Abbildung: links sieht man zusätzlichdie Kurven f (k)(r, x = 1/2). rechts sieht man ein Fenster der Ordnung im Chaos.

Trifft eine dieser „Spuren“ auf den Wert x = 1/2, so ist hier ein superstabiler p-Orbit erreicht(f ′(r, 0.5) = 0). Dies bedeutet, dass die Folge, falls sie in die Nähe von x = 1/2 kommt viel schnellerkonvergiert, als sonst. Ein solcher superstabiler Orbit zerfällt dann wieder mit Periodenverdopplung inRichtung Chaos. Die Gesetze sind die selben!

6.3.3. C++-Programme zur BerechnungDas erste Programm 6.1 durchläuft einen Bereich für r von rstart bis rstop, bei der Schrittweiterstep. Für Jedes r wird die logistische Abbildung N Schritte lang iteriert und jeweils die Punktepaare(r, x) ausgegeben. Dabei werden die ersten skip Werte übersprungen. Die Iteration startet bei x0. Das



Inhaltsverzeichnis

Programm kann verwendet werden, um ein Feigenbaum-Diagramm zu zeichnen, indem die Wertepaareals Punkte in ein r − x-Diagramm eingetragen werden. Das Programm wird wie folgt aufgerufen:

logisticmap rstart rstop rstep N skip x0

Listing 6.1: Berechnung eines Feigenbaum-Diagrammes1 # i n c l u d e < c s t d l i b >2 # i n c l u d e 3 # i n c l u d e <cmath >4

5 us ing namespace s t d ;6

7 double f ( double x , double r ) 8 re turn 4∗ r ∗x∗(1−x ) ;9

10 i n t main ( i n t argc , char ∗ a rgv [ ] )11 12 double r s t a r t = a t o f ( a rgv [ 1 ] ) ;13 double r s t o p = a t o f ( a rgv [ 2 ] ) ;14 double r s t e p = a t o f ( a rgv [ 3 ] ) ;15 long N= a t o i ( a rgv [ 4 ] ) ;16 long s k i p = a t o i ( a rgv [ 5 ] ) ;17 double x0= a t o f ( a rgv [ 6 ] ) ;18 i n t i ;19 double r ;20

21 double x=x0 ;22 c o u t . p r e c i s i o n ( 1 5 ) ;23 cout <<"# Logistische Abbildung"<< e n d l ;24 cout <<"# r,\t\tx"<< e n d l ;25 f o r ( r = r s t a r t ; r <= r s t o p ; r += r s t e p ) 26 x=x0 ;27 f o r ( i =0 ; i <=N; i ++) 28 x= f ( x , r ) ;29 i f ( i > s k i p ) cout <<r <<",\t\t"<<x<< e n d l ;30 31 32 re turn EXIT_SUCCESS ;33

Das zweite Programm 6.2 berechnet die ersten N Glieder der logistischen Abbildung mit dem Parame-ter r und dem Startwert x0. Es gibt die Punktepaare (i, x) aus. Das Programm wird wie folgt aufgerufen:

logisticmap2 r x0 N

Listing 6.2: Iteration der logistischen Abbildung1 # i n c l u d e < c s t d l i b >2 # i n c l u d e 3 # i n c l u d e <cmath >4



10 i n t main ( i n t argc , char ∗ a rgv [ ] )11 12 double r = a t o f ( a rgv [ 1 ] ) ;13 double x0= a t o f ( a rgv [ 2 ] ) ;14 long N= a t o i ( a rgv [ 3 ] ) ;15 i n t i ;16 c o u t . p r e c i s i o n ( 2 0 ) ;17 double x=x0 ;



Inhaltsverzeichnis

18 cout <<"# Logistische Abbildung r="<<r <<", x0="<<x0<< e n d l ;19 cout <<"# i,\t\tx"<< e n d l ;20 f o r ( i =1 ; i <=N; i ++) 21 cout << i <<",\t\t"<<x<< e n d l ;22 x= f ( x , r ) ;23 24 cout << i <<",\t\t"<<x<< e n d l ;25 re turn EXIT_SUCCESS ;26

Das dritte Programm 6.3 berechnet wieder die ersten N Glieder der logistischen Abbildung mit demParameter r und dem Startwert x0. Es gibt Punktepaare (x, y) aus, mit denen sich die logistische Ab-bildung veranschaulichen lässt (Projektion auf die Winkelhalbierende!). Das Programm wird wie folgtaufgerufen:

logisticmap3 r x0 N

Listing 6.3: Geometrische Interpretation der logistischen Abbildung.

1 # i n c l u d e < c s t d l i b >2 # i n c l u d e 3 # i n c l u d e <cmath >4



10 i n t main ( i n t argc , char ∗ a rgv [ ] )11 12 double r = a t o f ( a rgv [ 1 ] ) ;13 double x0= a t o f ( a rgv [ 2 ] ) ;14 long N= a t o i ( a rgv [ 3 ] ) ;15 i n t i ;16 c o u t . p r e c i s i o n ( 2 0 ) ;17 double x=x0 ;18 double xx=x0 , yy =0;19 cout <<"# Logistische Abbildung r="<<r <<", x0="<<x0<< e n d l ;20 cout <<"# xx,\t\tyy"<< e n d l ;21 f o r ( i =1 ; i <=N; i ++) 22 cout <<xx<<",\t\t"<<yy<< e n d l ;23 yy= f ( xx , r ) ;24 cout <<xx<<",\t\t"<<yy<< e n d l ;25 xx=yy ;26 cout <<xx<<",\t\t"<<yy<< e n d l ;27 x= f ( x , r ) ;28 29 cout <<xx<<",\t\t"<<yy<< e n d l ;30 re turn EXIT_SUCCESS ;31

Das vierte Programm 6.4 durchläuft einen Bereich für r von rstart bis rstop, bei der Schrittweiterstep. Für Jedes r wird der Lyapunov-Exponent abgeschätzt und ausgegeben. Die Iteration startet beix0. Das Programm wird wie folgt aufgerufen:

logisticmap_lyapunov rstart rstop rstep N x0

Listing 6.4: Berechnung des Lyapunov-Exponenten einer logistischen Abbildung.

1 # i n c l u d e < c s t d l i b >2 # i n c l u d e 3 # i n c l u d e <cmath >4

5 us ing namespace s t d ;



Inhaltsverzeichnis

6


10

11 double fd ( double x , double r ) 12 re turn 4∗ r ∗(1−2∗x ) ;13 14 i n t main ( i n t argc , char ∗ a rgv [ ] )15 16 double r s t a r t = a t o f ( a rgv [ 1 ] ) ;17 double r s t o p = a t o f ( a rgv [ 2 ] ) ;18 double r s t e p = a t o f ( a rgv [ 3 ] ) ;19 long N= a t o i ( a rgv [ 4 ] ) ;20 double x0= a t o f ( a rgv [ 5 ] ) ;21 i n t i ;22 double r , l ;23 c o u t . p r e c i s i o n ( 1 5 ) ;24 double x=x0 ;25 cout <<"# Logistische Abbildung"<< e n d l ;26 cout <<"# r,\t\tlambda"<< e n d l ;27 f o r ( r = r s t a r t ; r <= r s t o p ; r += r s t e p ) 28 x=x0 ;29 l =0 ;30 f o r ( i =0 ; i <=N; i ++) 31 x= f ( x , r ) ;32 l += l o g ( abs ( fd ( x , r ) ) ) ;33 34 l = l /N;35 cout <<r <<",\t\t"<<l << e n d l ;36 37 re turn EXIT_SUCCESS ;38

6.4. Periodisch getriebener Rotator

Ein Rotator werde zu äquidistanten Zeitpunkten mit Abstand τ mit einem kurzen Schlag angetrieben.Der Körper werde durch sein Trägheitsmoment I beschrieben. Weiter sei k die Stärke der Kicks und ϕdie Position des Rotators (Winkel!). Dann ist die Hamilton-Funktion des Systems:

H =L2

2I+k · cosϕ

2π·∑n∈N

δ(t− nτ). (6.4.1)

Für kleine k ist die Dynamik regulär. Für sehr große k wird sie chaotisch. Aus (6.4.1) erhält man dieHamilton’schen Bewegungsgleichungen:

ϕ =∂H

∂L=L(t)I

(6.4.2)

L = −∂H∂ϕ

=k

2πsin(ϕ) ·

∑n∈N

δ(t− nτ) (6.4.3)

Wegen der δ-Funktionen ist L zwischen den Kicks konstant. Damit ist auch ϕ konstant und ϕ hängtmaximal linear von der Zeit ab. Dies regt dazu an, die Dynamik nur Stroboskop-artig bei den Kicks zubetrachten. Dazwischen passiert ja nicht viel. Integriert man diese Bewegungsgleichungen über einenKick hinweg (Integrationsintervall [tk − ε, tk + ε], so erhält man:

ϕ(tk + ε)− ϕ(tk − ε) = 0 (6.4.4)

L(tk + ε)− L(tk − ε) =k

2π· sin(ϕ(tk)) (6.4.5)



Inhaltsverzeichnis

Da tk = nτ ist, kann man schreiben Ln = L(nτ + ε) und analog ϕn. Daraus erhält man mit (6.4.2) und(6.4.3) folgende Diskretisierung (ε→ 0):

ϕn = ϕn−1 +τ

ILn−1 (6.4.6)

Ln = Ln−1 +k

2π· sin(ϕn) (6.4.7)

oder mit pn = τLn/I und κ = kτ/(2πI):

pn = pn−1 + κ · sin(ϕn) (6.4.8)

ϕn = ϕn−1 + pn = ϕn−1 + κ · sin(ϕn) (6.4.9)

Dieses Modell heißt auch Chirikov-Standard-Abbildung. Die Größen pn, ϕn werden nur modulo 2π be-rechnet. Die folgende Abbildung zeigt das Ergebnis einer Simulation für verschiedene κ. Das verwendeteProgramm ist in 6.5 gezeigt.

Listing 6.5: Dieses Programm berechnet die Chirikov Standard-Abbildung

1 / / b e r e c h n e t d i e C h i r i k o v map .2 / / p , p h i werdem mod 2 p i b e r e c h n e t3 / / Ausgabe f ü r GnuPlot4 / / Z u f ä l l i g e Auswahl von N T e i l c h e n und5 / / Berechnung e i n i g e r Punk te der T r a j e k t o r i e6 # i n c l u d e < c s t d l i b >7 # i n c l u d e 8 # i n c l u d e <cmath >9


12 i n t main ( i n t argc , char ∗ a rgv [ ] )13 14 / / Kommando−Z e i l e n−Parameter e i n l e s e n15 double kappa= a t o f ( a rgv [ 1 ] ) ; / / kappa16 long N= a t o i ( a rgv [ 2 ] ) ; / / Anzah l der T e i l c h e n17 long l e n g = a t o i ( a rgv [ 3 ] ) ; / / I t e r a t i o n e n pro T e i l c h e n18 i n t i ;19 double phi , p ;20

21 s r a n d ( 1 2 3 4 5 6 7 8 9 ) ;22 c o u t . p r e c i s i o n ( 1 5 ) ;23 cout <<"# Chirikov map, kappa="<<kappa << e n d l ;24 cout <<"# p,\t\tphi"<< e n d l ;25 f o r ( i =1 ; i <=N; i ++) 26 / / z u f ä l l i g e S t a r t w e r t e27 p h i =( double ) r and ( ) / ( double )RAND_MAX∗M_PI∗2 ;28 p =( double ) r and ( ) / ( double )RAND_MAX∗M_PI∗2−M_PI ;29

30 cout <<"#new trajectory"<<phi << e n d l ;31 f o r ( i n t j =1 ; j <= l e n g ; j ++) 32 double p t ;33 p t =fmod ( p+kappa / ( 2 ∗M_PI )∗ s i n ( p h i ) , 2∗M_PI ) ;34 p h i =fmod ( p h i +p+kappa / ( 2 ∗M_PI )∗ s i n ( p h i ) , 2∗M_PI ) ;35 p= p t ;36 cout <<p<<",\t\t"<<phi << e n d l ;37 38 39 re turn EXIT_SUCCESS ;40



Inhaltsverzeichnis

Abbildung 6.8.: Phasenraumplots der Chirikov-Normal-Abbildung, alsod er diskreten Dynamik des peri-odisch getriebenen Rotators.



7. ZufallszahlenEin Zufallszahlgenerator (random number generator, RNG) erzeugt eine Folge von Zahlen x1, ..., xn mitbestimten statistischen Eigenschaften, die aber bis auf diese Randbesingungen (z.B. Gauß-Verteilung)vollkommen zufällig gezogen werden. Inwieweit tatsächliche Implementierungen eines solchen RNGdem nahekommen bleibt natürlich noch zu diskutieren. Solche zufälligen Zahlenfolgen habe weite Ein-satzgebiete:

• zufällige Generierung von Startzuständen mit bekannten Eigenschaften für Simulationen

• stochastische Prozesse in Physik (Brown’sche Bewegung, Diffusion, Teilchen-Transport ...), Bio-logie (Chemotaxis ...) oder Wirtschaftswissenschaften

• statistische Physik (Spin-Systeme etz.)

• Simulation quantenmechanischer Prozesse (Lichtstreuung, Absorption ionisierender Strahlung ...)

Es gibt verschiedene Möglichkeiten Zufallszahlen zu erzeugen:

• Würfel werfen

• Rauschen an einem pn-Übergang vermessen

• Vermessen von radioaktiven Zerfällen (z.B. Zeit zwischen zwei „Clicks“ eines Geiger-Zählers

• Tabellen (z.B. von der RAND Corp.)

• Pseudo-Zufallsgeneratoren am Computer

Die letzte Methode ist meißt die Methode der Wahl, liefert aber keine perfekten Zufallszahlen. Deswegenbenötigt man Tests, um unerwünschte Korrelationen zwischen Folgenglieder xi zu ermitteln, bzw. derenUnabhängigkeit zu bestätigen. In der Kryptographie, wo gute Zufallszahlen wesentlich sind, gibt es auchnur ein bekanntes, unknackbares Verfahren. Man verwendet dabei sog. Einmal-Pads, die eine bestimmteKodierung vorgeben, mit der die Buchstaben im Text chiffriert werden. Dabei ist es natürlich wesentlich,dass ein solches Pad nur einmal zum Einsatz kommt, da bei wiederholter Anwendung der selben Chiffredie Gefahr der Dekodierung durch Dritte steigt.

7.1. Erzeugung gleichverteilter Zufallszahlen

Die meißten Algorithmen zur Erzeugung beliebig verteilter Zufallszahlen starten mit gleichverteiltenZufallszahlen. Darum soll deren Erzeugung hier diskutiert werden. Die meißten Zufallszahlgeneratorenerzeugen eine lange Sequenz von Zahlen, die sich irgendwann wiederholen kann, deren Periode aber solang ist, dass sie praktisch keine Rolle spielt. Oft werden Zufallszahlgeneratoren durch ein sog. seedinitialisiert. Bei gleichem seedwird dann auch immer die gleiche Folge von Zufallszahlen erzeugt. Mannimmt also möglichst einen Wert für seed, der sich bei jedem Programmstart ändert (z.B. die aktuelleUhrzeit oder die Millisekunden seit Systemstart).

7.1.1. Zufallszahlen im GNU C-CompilerDie GNU C Library (libc) bietet einige Methode um gleichverteilte Zufallszahlen zu erzeugen. Die De-klarationen liegen in der Datei stdlib.h. Es werden zwei Methode deklariert:

74

Inhaltsverzeichnis

• int rand (void):liefert eine Zufallszahl zurück, die im Bereich 0.. RAND_MAX liegt.

• void srand (unsigned int seed):legt das seed für den Zufallszahlgenerator fest. Wird rand () ohne vorherigen Aufruf von seed (...)

verwendet, so wird mit dem Standardwert 1 gearbeitet.

Diese zwei Methoden sind bereits im ISO-C-Standard beschrieben. Durch ein einfaches Makro kannman daraus einen Zufallszahlgenerator mit dem Bereich 0..1 machen:

#define frand () rand ()/( RAND_MAX+1.0)

Auf SVID-Systemen (The System V Interface Description) gibt es noch eine weitere Möglichkeit, besserZufallszahlen zu erhalten. Die meißten modernen Unix-Systeme implementieren diesen Standard. Es gibtzwei Arten von Funktionen: Die einen speichern ihren Zustand applikationsweit in einer Variable, sodassalle Prozesse/Threads und Routinen auf einen Zufallszahlgenerator mit dem selben Zustand zugreifenkönnen. Die anderen verlangen die Speicherung des Zustandes vom Benutzer selbst. So kann etwa jederProzess einen unabhängigen Zufallszahlgenerator haben. Alle diese Generatoren nutzen indessen dieselbe kongruente Beziehung:

Y = (a ∗X + c) mod m mit a = 0x5DEECE66D = 25214903917, c = 0xb = 11, m = 248

Es sind die folgenden FUnktionen implementiert:

• double drand48 (void)

double erand48 (unsigned short int xsubi [3]) :liefert eine Zufallszahl zwischen 0 und 1 zurück. Da double 52 lang ist, werden 4 bits mit 0 initia-lisiert (diese sind die niederwertigsten Bits). Die zweite Routine hat ein Array als Parameter, dasden Zustand des Generators beschreibt.

• long int lrand48 (void)

nrand48 (unsigned short int xsubi [3]) :liefert eine Zufallszahl zwischen 0 und 231.

• mrand48 (void)

jrand48 (unsigned short int xsubi [3]) :lifert eine Zufallszahl zwischen −231 und 231.

• void srand48 (long int seedval ):initialisert den internen Zufallszahlgenerator. Dabei werden die unteren 16 Bit zu 0x330E initia-lisiert und die oberen aus seedval.

• unsigned short int ∗ seed48 (unsigned short int seed16v[3]):setzt alle Stellen des internen Zufallszahl-generators. Es wird ein Zeiger auf den alten Zustand des Generators zurückgegeben.

• void lcong48 (unsigned short int param[7]):initialisiert den internen Zufallszahlgenerator und ändert zusätzlich die Konstanten a und c in derkongruenten Beziehung.

7.1.2. Linear Kongruente Generatoren (LCGs)Wie bereits im vorherien Abschnitt 7.1.1 beschrieben nutzen Zufallszahlgeneratoren oft linear-kongrunetenBeziehungen aus:

Ij+1 = (a · Ij + c) mod m (7.1.1)

Dabei sind a, c,m gegebene Parameter des Generators. Die Periode eines solchen Generators kann nichtlänger als m sein und mit ungeschickter Wahl von a und c kann sie wesentlich kürzer ausfallen.



Inhaltsverzeichnis

Die linear-kongruente Methode bietet vor Allem einen Vorteil: Sie ist schnell (benötigt wenige Opera-tionen pro Schritt). Allerdings ist sie nicht frei von Korellationen aufeinanderfolgender Zahlen. Um dieszu analysieren zeichnet man Punkte im k-dimensionalen Raum. Die Koordinaten jedes Punktes werdendabei aus k aufeinanderfolgenden Zufallszahlen gebildet. Die Zahlen füllen dann nicht (wie erwartet)den Raum gleichmäßig aus, sondern liegen auf maximal ca. m1/k (k − 1)-simensionalen Hyperebenenin diesem k-dimensionalen Raum. Werden die Konstante a und c ungünstig gewählt, so können sichnoch weniger Ebenen ergeben. Die Abbildung 7.1 zeigt diesen Effekt beispielhaft für schlecht gewählteKonstanten. Solche Fehler können z.B. eine Rolle spielen, wenn man versucht viele Teilchen zufällig zupositionieren, etwa um ein klassisches Gas zu simulieren. Ein solches Verhalten prägt dann dem Systemnatürlich eine Struktur auf.

0

1000

2000

3000

4000

0 1000 2000 3000 4000

I j+1

I j

a) Ij-I j+1-Plot

0 1000

2000 3000

4000 0

1000

2000

3000

4000

0

1000

2000

3000

4000

I j+2

b) Ij-I j+1-I j+2-Plot

I j

I j+1

I j+2

Abbildung 7.1.: Zufalls-Zahlen, die mit einem linear-kongruenten Genrator und a = 106, c = 1283 undm = 6075 erzeugt wurde, in (a) 2-dimensionalem und (b) 3-dimensionalen Korellationsplot.

Man sollte sich zur Verdeutlichung folgende Abschätzungen für eine ideale Wahl von a und c ansehen:

m Anzahl der Ebenen für k = 2 Anzahl der Ebenen für k = 31024 = 210 32 1032768 = 215 181 32

232 65535 = 216 2625 ≈ 210

Alerdings sind Korellationen nicht das einzige Problem der linear-kongrunenten Zufallszahlgeneratoren.Sie haben oft auch das Problem, dass die niederwertigen Bits weniger zufällig sind, als die höherwerti-gen.

7.1.3. Multiplikativ Kongruente Generatoren (MCGs)Es gibt gute Gründe, anzunehmen, dass auch multiplikativ-kongruente Generatoren genausogut sein kön-nen, wie LCGs (siehe7.1.2). Sie haben die folgende, einfachere Abbildungsvorschrift:

Ij+1 = (aIj) mod m (7.1.2)

Sind sind also Spezialfälle der LCGs mit c = 0. Von Park und Miller wurden die folgenden Werte zurInitialisierung vorgeschlagen:

a = 75 = 16807, m = 231 − 1 = 2147483647 (7.1.3)

Das Problem, das sich ergibt ist ein Integer-Überlauf bei der Multiplikation. Man kann es umgehen, in-dem man Assembler-Code schreibt und eine 32-Bit-Multiplikation ausführt und deren Zwischenergebnis



Inhaltsverzeichnis

weiterverarbeitet, oder man nutzt einen Trick, nämlich Schrage’s Algorithmus, aus: Schrage’s Algorith-mus nimmt eine Approximative Faktorisierung von m vor:

m = aq + r, q = bm/ac , r = m mod a (7.1.4)

Dabei bezeichnet b·c den ganzzahligen Anteil einer Zahl. Man kann dann zeigen, dass für r < q sowohla · (z mod q), als auch r · bz/qc im Intervall [0,m − 1] liegen. Außerdem gilt dann die folgendeGleichung:

(a · z) mod m =

a · (z mod q)− r · bz/qc wen dieser Ausdruck ≥ 0 ista · (z mod q)− r · bz/qc+m sonst

(7.1.5)

Für die oben angegebenen Zahlen (7.1.3) nutzt man:

q = 127773, r = 2836 (7.1.6)

Damit erhält man dann folgenden Algorithmus (in C++):

Listing 7.1: Implementation eines MCG mit Schrage’s Algorithmus1 # d e f i n e a 168072 # d e f i n e q 1277733 # d e f i n e r 28364 # d e f i n e m 21474836475

6 / / Park−M i l l e r−Z u f a l l s z a h l g e n e r a t o r m i t long−Rückgabe [ 0 . . m]7 long ran_mcgl ( long ∗ s t a t e ) 8 ∗ s t a t e =a ∗ ( (∗ s t a t e ) % q )− r ∗ (∗ s t a t e ) / q ;9 i f ( ( ∗ s t a t e ) <0) ∗ s t a t e =∗ s t a t e + m;

10 re turn ∗ s t a t e ;11

Die vorgestellte Methode ist ein „minimaler Standard“. Sie hat aber (aufgrund des MCG-Algorithmus(7.1.2)) einen weiteren Nachteil: Da a ≈ 1.6 · 104 ist, wird einer kleinen Zahl Ij eine Zahl folgen, diemaximal um einen Faktor a größer ist. Dies kann in einigen Fällen unerwünscht sein, da der Generatorso (bei einem Maximum von m ≈ 2 · 109) einige Zahlen lang im niederen Potenzbereich verbleibt.

Man kann den hier vorgestellten Generator weiter verbessern, wenn man seine Ausgaben mischt. Dazuwird eine Tabelle der Länge 32 angelegt, die mit Zufallszahlen gefüllt ist. Bei jedem Aufruf wird einezufällige Position in der Tabelle gewählt und deren Zahl zurückgegeben. An die Position wird danachdie erzeugte Zufallszahl gescrieben. Dies entfernt Korellationen zwischen aufeinanderfolgenden Zahlen.Der gezeigte Generator hat eine Periode in der Größenordnung von 108.

Listing 7.2: Implementation eines MCG mit Mischen der Ausgabe1 / / Länge der Misch−T a b e l l e2 # d e f i n e NTAB 323 / / Z u f a l l s z a h l g e n e r a t o r m i t Mischen4 long ran_mcg_mix ( long ∗ s t a t e , bool i n i t = f a l s e ) 5 s t a t i c long m i x t a b l e [NTAB ] ; / / s t a t i c h e i ß t , das Array b l e i b t6 / / z w i s c h e n zwe i F u n k t i o n s a u f r u f e n7 / / e r h a l t e n8 long x , temp ;9 i n t j ;

10

11 i f ( i n i t ) / / i n i t i a l i s i e r e d i e T a b e l l e12 f o r ( i n t j =NTAB+7; j >=0; j−−) 13 x= ran_mcgl ( s t a t e ) ;14 i f ( j <NTAB) m i x t a b l e [ j ]= x ; / / B e f ü l l e n nach 8 " Aufwärmrunden "15 16 17

18 x= ran_mcgl ( s t a t e ) ; / / Z u f a l l s z a h l z i e h e n19 j =x % NTAB; / / j aus [ 0 . . NTAB−1]



Inhaltsverzeichnis

0

1000

2000

3000

4000

0 1000 2000 3000 4000

I j+1

I j

a) ohne Mischen

0

1000

2000

3000

4000

0 1000 2000 3000 4000

I j+1

I j

b) mit Mischen

Abbildung 7.2.: Vergleich des einfachen LCG aus dem letzten Abschnitt, mit und ohne Mischen (Werte desLCG: a = 106, c = 1283 und m = 6075)

20

21 temp= m i x t a b l e [ j ] ; / / mischen22 m i x t a b l e [ j ]= x ;23

24 re turn temp ;25

Die folgende Abbildung 7.2 zeigt die Auswirkungen des Mischalgorithmus. Die Ebenen-Struktur imN2 wird aufgehoben. Die Strukturierung der Zahlen wird aber augenscheinlich nicht ganz aufghoben.

Will man Folgen von Zufallszahlen, die wesentlich länger als 108 sind, so kann man obiges Konzeptweiter verfeinern, indem man zwei unterschiedliche Zufallszahlgeneratoren verwendet. Man erhält dannzwei Zufallsgrößen X und Y . Deren begrenzte Summe (X + Y ) mod m ist wieder eine Folge vonPseudozufallszahlen, die bei geschickter Wahl der zwei Generatoren eine Periode der Größenordnung1018 erreicht. Man kann auch hier das Mischen mit einbeziehen. Dazu verwendet X um eine Zufallszahlaus der Tabelle auszulesen, zu der dann Y addiert wird. Um einen Integer-Überlauf zu vermeiden kannman die Modulo-Operation auf jede Zahl einzeln anwenden, die Ergebnisse hernach subtrahieren undevtl. m addieren, wenn die erhaltene Zahl kleiner als 0 ist.

7.2. Erzeugung von Zufallszahlen mit vorgegebener Verteilung

Die bisherigen Zufallszahlgeneratoren haben allesamt gleichverteilte Zahlen erzeugt. Im nun folgendenAbschnitt sollen Methoden diskutiert werden, die Zufallszahlen erzeugen, die einer vorgegebenen Ver-teilung entsprechen.

7.2.1. Transformations-MethodeDazu betrachte man ein Zufallsgröße Y mit ihrer Realisation y. Die Zufallszahlen x seien nach p(x)verteilt. Weiter sei x(y) eine monotone Funktion von y. Natürlich ist die Funktion x(y) wieder eineZufallsvariable, mit der Verteilung f(y). Es gilt dann aufgrund der Normierung:

1 =

∞∫−∞

p(x) dx =

∞∫−∞

f(y) dy (7.2.1)



Inhaltsverzeichnis

Aus dem ersten Integral erhält man:

∞∫−∞

p(x) dx =

∞∫−∞

p(x(y)

)·∣∣∣∣dxdy

∣∣∣∣ dy (7.2.2)

Setzt man dies nun mit dem zweiten Integral aus (7.2.1) gleich, so erhält man eine Definition von f(y):

f(y) = p(x(y)

)·∣∣∣∣dxdy

∣∣∣∣ . (7.2.3)

Diese Bestimmungsgleichung für f(y) impliziert sofort ein Verfahren zur Generierung von ZUfallszah-len mit einer vorgegebenen Verteilung f(y) aus gleichverteilten Zufallszahlen x aus dem Untervall [0, 1)(also mit p(x) = 1):

1. Man stelle sicher, dass: ∣∣∣∣dxdy∣∣∣∣ = f(y). (7.2.4)

2. Aus (7.2.4) erhält man durch Integration:

x = F (y) =

y∫ymin

f(y′) dy′ ⇒ y = F−1(x). (7.2.5)

Man berechne also F−1(x) und erhält damit aus gleichverteilten Zufallszahlen x f(y)-verteilteZufallszahlen y. Wenn f(y) die Wahrscheinlichkeitsdichte ist, so nenn man F (y) die zugeförigeVerteilungsfunktion.

Das Verfahren ist also für Verteilungen anwendbar, die integrierbar sind und deren Verteilungsfunktionumkehrbar ist. Beispiele sind die Exponentialverteileung oder die Gauß-Verteilung.

Die Exponential-Verteilung f(y) = e−y

0

0.2

0.4

0.6

0.8

1

0 2 4

x

y

f(y)=e-y

F(y)=1-e-y

Abbildung 7.3.: Illustration zur Transformations-Methode für die Exponential-Verteilung f(y) = e−y

Das Verfahren kann man auch graphisch veranschaulichen. Abbildung 7.3 zeigt die Transformationsme-thode am Beispiel der Exponentialverteilung

f(y) = e−y. (7.2.6)



Inhaltsverzeichnis

Diese spielt z.B. in der statistischen Physik eine zentrale Rolle. Mit ymin = 0 erhält man damit aus(7.2.5):

F (y) = e−ymin − e−y = 1− e−y ⇒ y(x) = − ln(1− x). (7.2.7)

In der Abbildung wird die Vorschrift y = F−1(x) geometrisch ausgeführt, indem äquidistante Punkte aufder x-Achse auf die y-Achse abgebildet werden. Man sieht deutlich, dass die Abstände auf der y-Achseexponentiell größer werden, wie es nach obiger Herleitung zu erwarten war.

Gauß’sche Zufallszahlen – Box-Muller-AlgorithmusFür Gauß- oder Normal-verteilte Zufallszahlen muss man die obige Methode etwas generalisieren, dadas Integral über die Gauß-Dichtefunktion zwar noch lösbar (Gamma-Funktion) aber nicht invertierbarist. Man möchte also eine Methode finden, um Zufallszahlen zu erzeugen, die folgender Dichtefunktionfolgen:

f(y)dy =1√2π· e−y2/2 dy (7.2.8)

Dazu verallgemeinert man Gleichung (7.2.3) auf mehrere Zufallsvariablen x1, x2, ...: Dabei wird dieJacobi-Determinante verwandt:

∣∣∣∣∂(x1, x2, ...)∂(y1, y2, ...)

∣∣∣∣ :=∣∣∣∣∣∣∣∂x1∂y1

∂x1∂y2

. . . ∂x1∂yn

......

. . ....

∂xn∂y1

∂xn∂y2

. . . ∂xn∂yn

∣∣∣∣∣∣∣ (7.2.9)

Man betrachte nun speziell für die Gauß-Verteilung folgende Setzung:

y1 =√−2 lnx1 · cos 2πx2 (7.2.10)

y2 =√−2 lnx1 · sin 2πx2 (7.2.11)

(7.2.12)

Daraus erhält man durch quadrieren und addieren, bzw. durch dividieren von (7.2.17) und (7.2.18):

x1 = exp(−1

2(y21 + y2

2

))(7.2.13)

x2 =12π· arctan

y2

y1(7.2.14)

(7.2.15)

Nun kann man die Jacobi-Determinante berechnen:∣∣∣∣∂(x1, x2, ...)∂(y1, y2, ...)

∣∣∣∣ =∣∣∣∣∣∂x1∂y1

∂x1∂y2

∂x2∂y1

∂x2∂y2

∣∣∣∣∣ =(∂x1

∂y1

)·(∂x2

∂y2

)−(∂x1

∂y2

)·(∂x2

∂y1

)=

= −y1 · exp[...] · 12π

y1

y21 + y2

2

− y1 · exp[...] · 12π

y2

y21 + y2

2

=

= − 12π· y

21 + y2

2

y21 + y2

2

· exp[−y

21 + y2

2

2

]=[

1√2πe−y2

1/2

]·[

1√2πe−y2

2/2

](7.2.16)

Hier liegt also ein Produkt einer Funktion in y1 und einer Funktion in y2 vor. Damit sind beide Variableny1, y2 unabhängig voneinander noralverteilt.



Inhaltsverzeichnis

(v ,v )1 2

a

R

Abbildung 7.4.: Illustration zum Box-Muller-Algorithmus

Es gibt nun noch einen Trick um diesen Zufallszahlgenerator zu beschleunigen. Dazu müssen dieSinus, bzw. Cosinus-Terme entfernt werden. Man zieht nun statt x1, x2 aus dem Einheitsquadrat, zweiZahlen v1, v2 mit v2

1 +v22 ≤ 1, also aus dem inneren des Einheitskreises. Dann ist geradeR2 = v2

1 +v22 ∈

[0..1] eine gleichverteilte Zufallszahl und kann als x1 angewendet werden. Der Punkt (v1, v2) definiertzur v1-Achse einen Winkel α, der als Winkel 2πx2 verwendet werden kann. Man kann dann Cosinus undSinus über die Beziehungen im rechtwinkligen Dreieck ausdrücken und erhält statt(7.2.17) und (7.2.18):

y1 =√−2 lnR2 · v1√

R2(7.2.17)

y2 =√−2 lnR2 · v2√

R2. (7.2.18)

Man erhält also folgenden Algorithmus: Man kann den Algorithmus weiter beschleunigen, wenn man

function GAUSSDEV

repeat . ziehe zwei Zufallszahlen aus dem Einheitskreisv1 ← 2 · rand()− 1v2 ← 2 · rand()− 1rsq← v2

1 + v22

until rsq < 1

faktor←√

−2·ln(rsq)rsq

. Box-Muller-Transformationreturn v2 · faktor

end functionAlgorithme 6: Box-Muller-Algorithmus zur Erzeugung Gauß-verteilter Zufallszahlen (µ = 0, σ2 = 1)

nur einmal alle zwei Aufrufe die Box-Muller-Transformation ausrechnet und bei jedem zweiten Aufrufstatt v2 · faktor gerade v1 · faktor zurückgibt. Dann ist aber eine Speicherung des Zustandes in derFunktion nötig.

7.2.2. Rejection-MethodeDie Transformationsmethode hatte zwei gewichtige Voraussetzungen: Zum einen musste die integrierteWahrscheinlichkeitsdichte (also die Verteilung) berechenbar sein und zum Anderen musste diese sogarnoch invertierbar sein. Dies ist für viele, oft benötigte, Verteilungen nicht gegeben, sodass ein anderesVerfahren benötigt wird. Die Rejection-Methode leistet dies. Mit ihr kann man Zufallszahlen erzeugen,die einer beliebigen Verteilung gehorchen. Die einzige Bedingung ist, dass die Wahrscheinlichkeitsdichtep(x)dx der Verteilung berechenbar ist.

Die Methode basiert auf folgender Idee: Man zeichne die gewünschte Verteilung p(x) (siehe Abb 7.5).Wenn man nun eine Möglichkeit hat einen Punkt (x, y) unterhalb des Graphen p(x) zu wählen, sodassseine Position in diesem Gebiet gleichverteilt ist, so muss seine x-Koordinate nach p(x) verteilt sein.Das macht man sich leicht anschaulich: Je mehr Fläche über einem Stück [x;x + dx] auf der x-Achseliegt, desto höher ist die Wahrscheinlichkeit dort den Punkt (x, y) zu setzen. Sie ist nämlich gerade:

P(„(x, y) über [x0;x0 + dx]“

)=

p(x0)dx∫p(x) dx

∝ p(x0).



Inhaltsverzeichnis

Nun bleibt also die Frage, wie man einen Zufallspunkt unter dem Graphen findet, in diesem Gebietgleichverteilt ist. Dazu betrachte man Abb. 7.6.

0

A

p(x)f(x)

òf(x)dx

0

A

p(x)f(x)

òf(x)dx

(1) wähle erste Zufallszahl x, die nach f(x) verteilt ist

(0) gewünschte Verteilung p(x), approximierende Verteilung f(x) und

deren integrierte Verteilung

0

A

p(x)f(x)

òf(x)dx

(2) wähle zweite Zufallszahl y gleichverteilt aus aus [0, f(x)](x,y) ist dann gleichverteilt im

Gebiet unter f(x)

0

A

p(x)f(x)

òf(x)dx

(3) verwerfe oder akzeptiere x, wenn er über,bzw. unter p(x) liegt

x akzeptierenx zurückweisen

f(x)

x x

x

Abbildung 7.6.: Praktische Durchführung der Rejection-Methode

Man benötigt eine Vergleichsfunktion f(x), die überall über p(x) liegt und deren Integral berechen-bar und invertierbar ist; man nutzt nämlich eine Variante der Transformations-Methode aus. Eine solcheFunktion kann immer gefunden werden, da ja die Fläche von p(x) auf 1 normiert ist und damit insbe-sondere praktisch überall p(x) < 1 gilt. Man geht dann folgendermaßen vor:

1. Ziehe mit der Transformations-Methode eine Zufallszahl x, die nach f(x) verteilt ist.

2. Ziehe eine zweite Zufallszahl y ∈ [0, f(x)]. Damit ist dann die Position des Punktes (x, y) unterf(x) gleichverteilt.

3. Wenn y < p(x), so akzeptieren den Punkt (x, y), ansonsten ziehe einen neuen Punkt (x, y). Da-nach ist (x, y) gleichverteilt unter p(x) und x ist somit p(x) verteilt.

0

1

p(x)

òp(x)dx = 1

(x, y)

xdx

Abbildung 7.5.: Veranschaulichung der Rejection-Methode



Inhaltsverzeichnis

Das Verfahren hat den Nachteil, dass evtl. recht viele Punkt (x, y) verworfen werden, bevor einerakzeotiert wird. Darum sollte man die Vergleichsfunktion f(x) so wählen, dass sie möglichst nahe anp(x) liegt, da die Verwerfungswahrscheinlichleit nur von

Rp(x) dxRf(x) dx

abhängt.Hat man eine Wahrscheinlichkeitsverteilung mit einem Maximum, so kann man z.B. eine Lorentz-

Kurve als Vergleichsfunktion wählen:

f(x) =c0

1 + (x−x0)2

a20

(7.2.19)

Sie hat einen Peak bei x0 mit f(x0) = c0. Ihre volle Breite bei halber Höhe (FWHM) ist gerade 2a0. Ihrunbestimtes Integral (dessen Umkehrfunktion einfach zu berechnen ist) ergibt sich zu:

F (x) = a0c0 arctan((y − y0)/a0

)+ const (7.2.20)

Man kann die Rejection-Methode auch anwenden, um diskrete Wahrscheinlichkeitsverteilunge pd(i) :N→ [0, 1] zu berechnen, die nur ganzzahlige Argumente erhalten. Eigentlich beschreibt man eine solcheVerteilung über eine Summe von δ-Funktionen:

p(x) =

∞∫−∞

∑i

pd(i) · δ(x− i) dx (7.2.21)

Es ist natürlich nicht möglich eine Vergleichsfunktion zu finden, die höher als ein δ-Spike liegt, aber mankann folgenden Trick anwenden: Man führt den Zug von δ-Funktionen in eine Summe von Kästen über,wie es Abb. 7.7 zeigt.

0

p d(x-1)1 p d(x-21)2p d(x-2)2 p d(x-3)3 ...............

x

p1

p2

p3

Abbildung 7.7.: Rejection-Methode für diskrete Wahrscheinlichkeitsverteilungen

Dabei ist jeder Kasten symmetrisch um x ∈ N platziert ([x− 12 ;x+ 1

2 ]) und hat eine Höhe von pd(x).Natürlich muss diese neue Wahrscheinlichkeitsverteilung novh auf 1 normiert werden. Danach ist es aberkein Problem mehr eine Vergleichsfunktion zu finden. Man gibt dann natürlich den Ganzzahl-Anteil vonx zurück.



Inhaltsverzeichnis

7.3.

Zusa

mm

enst

ellu

ngde

rVe

rfah

ren

Typ

Verf

ahre

nVe

rtei

lung

Vort

eile

Nac

htei

leph

ysik

.pn

-Rau

sche

ngl

eich

/gau

ß•

Ver

teilu

ngab

häng

igvo

nA

rtde

sR

au-

sche

ns(w

eiß/

rosa

)•

gute

Zuf

alls

zahl

en

•H

ardw

are

nötig

radi

oakt

.Zer

fall

Pois

son

•gu

teZ

ufal

lsza

hlen

•H

ardw

are/

radi

oakt

.Sto

ffe

nötig

•ev

tl.la

nge

War

teze

it,fü

rgro

ßeZ

ahl

Pseu

doLi

near

Kon

grue

nt(L

CG

)gl

eich

vert

eilt

•ei

nfac

hun

dsc

hnel

l•

Ebe

nens

truk

tur/

Kor

rela

tione

n•

gute

Kon

figur

atio

nen

sind

selte

n•

nied

erw

ertig

eB

itsw

enig

erzu

fälli

g

Mul

tiplik

ativ

Kon

grue

nt(M

CG

)gl

eich

vert

eilt

•ei

nfac

hun

dsc

hnel

l•

Kor

rela

tione

n•

blei

btu.

U.

lang

eim

nied

rige

nZ

ahle

nbe-

reic

h,w

enn

eine

Zah

lIk

klei

nw

ar,d

aM

o-du

lono

chni

chtg

reif

t

LCG

/MC

Gm

itM

isch

engl

eich

vert

eilt

•et

was

aufw

ändi

gera

lsM

CG

/LC

G•

Auf

hebu

ngde

rEbe

nens

truk

tur

Tran

form

atio

ns-M

etho

debe

liebi

gm

.E.

•er

zeug

tp(x

)-ve

rtei

lteZ

ahle

nau

sgl

eich

-ve

rtei

lten

Zah

len

•F

(x)

=x ∫ x0

p(x

′ )dx′m

uss

inve

rtie

rbar

sein

•ke

ine

disk

rete

nV

erte

ilung

en

Tran

form

atio

ns-M

etho

debe

liebi

gm

.E.

•er

zeug

tp(x

)-ve

rtei

lteZ

ahle

nau

sgl

eich

-ve

rtei

lten

Zah

len

•p(x

)ka

nnau

chdi

skre

tsei

n•p(x

)m

uss

nura

ppro

xim

ierb

arse

in,m

itin

-ve

rtie

rbar

erV

erte

ilungF

(x)

•ev

tl.w

erde

nvi

ele

Zah

len

verw

orfe

n



8. Monte-Carlo-MethodenAls Monte-Carlo-Methode bezeichnet man Simulationsverfahren, bei denen Zufallszahlen eingesetztwerden, um bestimte Prozesse zu beeinflussen, oder ganz darzustellen. Einige Beispiele:

• Simulation von stochastischen Prozessen (z.B. Brown’sche Molekularbewegung, Diffusion ...)

• Erzeugung heterogener Medium, um die Interaktion bestimter Prozesse mit diesen Medien zustudieren.

• Berechnung von Schätzwerten für Zufallsprozesse

• Monte-Carlo-Integration

8.1. Einfache Monte-Carlo-Integration

Ein Integrator soll folgende Aufgabe lösen:

Es sei ein Gebiet V ∈ Rn und eine Funktion f(~x) : Rn → R gegeben. Berechne dann:

I =∫

Vf(~x) dnx (8.1.1)

Normale Integratoren zerlegen das (n − 1)-dimensionale Volumen unter der Funktion in bekannteTeilvolumina, die dann aufsummiert werden. Die Monte-Carlo-Integration geht einen anderen Weg:

Wenn p(~x) eine Wahrscheinlichkeitsdichte ist, so ist der Erwartungswert einer Funktion f(~x) unterdieser Verteilung gerade durch den folgenden Ausdruck gegeben:

〈f〉 =∫

Vp(~x) · f(~x) dnx (8.1.2)

Nach dem Gesetz der großen Zahlen wird 〈f〉 durch den empirischen Mittelwert f angenähert. Ziehtman N nach p(~x) verteilte Punkte, so ergibt sich:

fN =1N

N∑i=1

f(~xi), f2N =

1N

N∑i=1

f(~xi)2 (8.1.3)

Der Fehler, der bei dieser Abschätzung gemacht wird ist:

σN [f ] =

√f2

N − fN2

N − 1∝ 1√

N. (8.1.4)

Dieser Fehler ist ein Maß für die Fluktuation des Ergebnisses 〈f〉:

〈f〉 =∫

Vp(~x) · f(~x) dnx = fN ± σN [f ]. (8.1.5)

Eine robuste und simple Integrations-Methode ergibt sich für den Fall der Gleichverteilung p(x) = 1V .

Es gilt nämlich ∫Vp(~x) · f(~x) dnx =

fN ± σN [f ]V

, (8.1.6)

was gerade der Grundaufgabe (8.1.1) entspricht. Es bleibt allerdings zu bemerken, dass dieser Integratorzwar simpel und robust ist, sein Fehler aber mitN−1/2 langsamer als der aller anderer Integratoren sinkt.Außerdem muss das Volumen V vernünftig darstellbar sein, um aus ihm Zufallszahlen zu ziehen.

85

Inhaltsverzeichnis

8.1.1. Beispiel: Wie man π erschießtEin einfaches Beispiel für Monte-Carlo-Integrationen ist die Berechnung der Zahl π, als Fläche desEinheitskreises. Dazu geht man folgendermaßen vor:

function SHOOTPIcount← 0for i = 1, ..., N do

x← 2 · rand()− 1y ← 2 · rand()− 1if x2 + y2 ≤ 1 then

count← count + 1end if

end forreturn 4 ∗ count/N

end functionAlgorithme 7: Berechnung von π über einen Monte-Carlo-Algorithmus

Man zieht also N Punkte in einem symmetrischen Quadrat der Länge 2 um den Nullpunkt. Danachwird überprüft, ob der Punkt zum Einheitskreis gehört oder nicht. Man kann das obige Verfahren natür-lich auch im bisherigen Formalismus ausdrücken:

π =

1∫−1

1∫−1

p(x, y) dx dy ≈ 4N

N∑i=1

p(xi, yi), mit p(x, y) =

1 x2 + y2 ≤ 10 sonst

(8.1.7)

Die folgende Tabelle 8.1 zeigt, wie diese Monte-Carlo-Integration konvergiert:

Iterationen pi

100 8101 4.4102 3.24103 3.12104 3.1264105 3.14164106 3.141876107 3.1416012108 3.14142364109 3.1415898881010 3.141579739ideal 3.141592654

Tabelle 8.1.: Evaluation der π-Berechnung nach der Monte-Carlo-Methode. Als Idealwert wurde M_PI ausmath.h angegeben.

8.2. Integration mit Importance Sampling

Die Integrationsmethode in 8.1 ist vor Allem dann schlecht, wenn nur ein kleiner Teil des Volumens Veinen großen Beitrag zum bestimmten Integral I hat. Dann addiert ein einfacher MC-Integrator, aufgrundder Gleichverteilung der Zufallszahlen, nach 8.1 viele Beiträge zu I , die aber eigentlich unsignifikantsind. Man kann dann das sog. Importance Sampling anwenden. Dazu generiert man Zufallszahlen, diegerade so beschaffen sind, dass die Wahrscheinlichkeit in einm Bereich mit großem Integranden zu seingroß ist, und umgekehrt. Man benötigt also eine normierte Verteilung p(x) mit den folgenden Eigen-



Inhaltsverzeichnis

schaften:

p(~x) ∝ f(x) ∀x ∈ [a, b] und

b∫a

p(x) = 1 (8.2.1)

Dann gilt weiter:b∫

a

f(x)dx =

b∫a

p(x) · f(x)p(x)︸︷︷︸≈const

dx =⟨f(x)p(x)

⟩p(x)

≈ 1N

N∑i=1

f(xi)p(xi)

(8.2.2)

Dabei sind dann die xi nach p(x) verteilte Zufallszahlen, man benötigt also die Möglichkeit Zufallszah-len mit der Verteilung p(x) zu erzeugen. Dies kann z.B. mit einer der Methoden aus 7.2 geschehen, oderman konstruiert nach dem Metropolis-Algorithmus einen stochastischen Prozess, der die xi erzeugt. Dieswird im nächsten Abschnitt genauer erklärt.

8.3. Monte-Carlo Simulationen: Der Metropolis-Algorithmus

Man kann die Zufallszahlen für die Integration auch mit Hilfe eines Markov-Prozesses generieren, ei-nem stochastischen Prozess, dessen Gleichgewichtsverteilung gerade p(~x) entspricht und nutzt ihn zurIntegration aus.

Als Prozess verwendet man hier einen Markov-Prozess, bei dem die Wahrscheinlichkeit für den nächs-ten Zustand nur vom vorherigen Zustand abhängt, der also kein Gedächtnis aufweist. Ein solcher Prozesswird vollständig durch eine Übergangsmatrix W =

(W (~x, ~x′)

)beschrieben, die die Übergangsraten

~x→ ~x′ enthält.Mit einer solchen Matrix W kann man eine Master-Gleichung aufschreiben, die eine Kontinuitätsglei-

chung fr Wahrscheinlichkeitsdichten darstellt:

∂p(~x, t)∂t

=∑~x′

[W (~x′~x) · p(~x′, t)−W (~x, ~x′) · p(~x, t)

]. (8.3.1)

Im Gleichgewichtsfall verschwindet die rechte Seite von (8.3.1), was hier ausgenützt wird. Man konstru-iert W so, dass detailierte Balance gilt, d.h. für jedes ~x′ gilt gerade:

W (~x′, ~x) · p(~x′, t) = W (~x, ~x′) · p(~x, t). (8.3.2)

Ein kanonischer Vorschlag zur Konstruktion einer solchen Matrix stammt von Metropolis, Rosenbluth,Rosenbluth, Teller and Teller (MRRTT) (da den Physikern Metropolis, Rosenbluth und Teller die Idee zudiesem Verfahren bei einem gemeinsamen Abendessen mit ihren Ehefrauen kam, sind diese ebenfalls alsAutoren aufgeführt). Das Verfahren erzeugt W wie folgt:

W (~x′, ~x) = γ ·Θ(δ −

∣∣~x− ~x′∣∣) ·min

1,p(~x)p(~x′)

(8.3.3)

W (~x, ~x′) = γ ·Θ(δ −

∣∣~x− ~x′∣∣)︸︷︷︸Vorschlags-Wahrscheinlichkeit

· min

1,p(~x′)p(~x)

︸︷︷︸

Akzeptanz-Wahrscheinlichkeit

(8.3.4)

Der erste Teil γ ·Θ(δ − |~x− ~x′|

)beschränkt die Bewegungen auf eine bestimte Maximal-Distanz. Der

zweite Anteil veranlasst einen Wechsel, wenn der nächste Zustand wahrscheinlicher ist. Ist der aktuelleZustand sehr viel Wahrscheinlicher, als der nächste, wird der Quotien p(A)

p(B) > 1. Dieses wird durch dieMinimumsbildung abgefangen.

So lange W so konstruiert ist, dass jeder Zustand von jedem anderen Zustand aus in endlich vielenSchritten erreicht werden kann, ist die Gleichgewichtsverteilung eindeutig. Der Markov-Prozess konver-giert also nach einer gewissen Zeit gegen die Gleichgewichtsverteilung p(~x). Man kann dann also dieAufgabe (8.1.1) lösen, indem man ~xi aus dem Markov-Prozess erzeugt und danach I berechnet:

I =∫

Vp(~x) · f(~x) dnx ≈ 1

N

N∑i=1

f(~xi). (8.3.5)



Inhaltsverzeichnis

8.4. Beispiel: Das Ising-Modell

8.4.1. Beschreibung des ModellsDie folgende Abhandlung folgt in großen Teilen der Quelle [Coddington 1996]. Beim Ising-Modell be-trachtet man ein d-dimensionales Gitter mit interagierenden Spins. Wie in der Atomphysik kann ein Spinnur zwei Zustände haben |↑〉 (S = +1) und |↓〉 (S = −1) haben. Die Hamilton-Funktion eines solchenSystems ist gegeben als:

H = −J ·∑〈i,j〉

Si · Sj (8.4.1)

Dabei bezeichnet 〈i, j〉 die Summation über die nächsten Nachbarn eines jeden Spins und J die Interak-tionsstärke. Für zwei Spins gilt dann exemplarisch:

↑↑, ↓↓: E = −J, ↑↓, ↓↑: E = +J

Ist J > 0, so ist der Zustand der kleinesten Energie ein Zustand, in dem alle Spins ausgerichtet sind.Dies entspricht einem Ferromagneten. Eine sinnvolle Observable für das System ist die Magnetisierung

M =∑

i

Si. (8.4.2)

Das Verhalten der Spins hängt natürlich von äußeren Einflüssen ab. Diese sind hier vor Allem die Tem-peratur T und ein etwaig angelegtes externes MagnetfeldBext. Bei hoher Temperatur (kBT J könnenSpins leicht ihren Zustand wechselns, da ihre thermische Energie sehr groß ist. Dies führt zu einer zu-fälligen Anordnung der Spins und die Magnetisierung geht somit gegen 0. Für kleine Temperaturen(T → 0) richten sich die Spins aneinander aus und man erhält maximale Magnetisierung. Um ein exter-nes Magnetfeld zu berücksichtigen, in dem sich die Spins ausrichten modifiziert man den Hamiltonian(8.4.1):

H = −J ·∑〈i,j〉

Si · Sj −Bext ·∑

i

Si (8.4.3)

Möchte man die Magnetisierung aus (8.4.2) theoretisch berechnen, so muss man folgende Mittelwertberechnen:

〈M〉 =∑C

p(C) ·M(C). (8.4.4)

Diese Summe geht über alle möglichen Konfigurationen C des Systems. Eine Konfiguration C tritt dabeimit der Wahrscheinlichkeit p(C) auf. Diese Wahrscheinlichkeit ist gerade die Boltzmann-Verteilung:

p(C) =1Z· e−H(C)/kbT , mit: Z =

∑C

e−H(C)/kbT (8.4.5)

Dabei ist Z die Zustandssumme über alle möglichen Konfigurationen. Aus ihr können alle relevantenthermodynamischen Größen berechnet werden. Für kontinuierliche Systeme geht (8.4.5) in eine Integralüber. Die Ableitbarkeit aller interessanter Größen aus Z impliziert, dass Z berechnet werden muss. Fürein 1-dimensionales Ising-Modell mag die Anzahl der Möglichkeit (2N ) noch überschaubar sein, aberfür höhere Dimensionen steigt sie rapide (Gitter mit n = 10 Spins in jeder Raum-Dimension):

Dimensionen d ] Spins ] Zustände N1 10 210 = 10242 100 210·10 = 1.26 · 1030

3 1000 21000 = 1.07 · 10301

Eine solche Summation ist mit normalen numerischen Mitteln (und auf den größten verfügbaren Com-putern) nicht zu bewältigen. Man bedient sich daher der Monte-Carlo-Methode. Mit ihr genügt es einige



Inhaltsverzeichnis

(im Vergleich zu N ) wenige Konfigurationen auszurechnen, um einen guten Schätzwert für die Obser-vable 〈M〉 zu erhalten:

〈M〉 =1N·

N∑i=1

M(Ci)e−H(Ci)/kbT

N∑i=1

e−H(Ci)/kbT

(8.4.6)

Hier muss auch wieder Importance-Sampling angewendet werden, da die meisten Konfigurationen Ci

nur einen sehr kleinen Beitrag bringen (sie Abbildung ?? der Boltzmann-Verteilung). Dazu wählt manidealerweise eine Folge Ci von Konfigurationen nach ihrem Boltzmann-Gewicht p(Ci) aus. Es ergibtsich dann der Monte-Carlo-Mittelwert:

〈M〉 ≈M =1N·

N∑i=1

M(Ci) (8.4.7)

Leider ergibt sich hier das Problem, dass man p(C) nicht angeben kann, ohne die Zustandssumme Z =∑C e

−H(C)/kbT über alle Konfigurationen zu berechnen. Dies ist aber kein wirkliches Problem, da imMetropolis-Algorithmus (8.3.3) und (8.3.4) nur die Verhältnisse p(A)

p(B) , bzw. p(B)p(A) vorkommen. Für diese

erhält man:p(A)p(B)

=1Z · e

−H(A)/kbT

1Z · e−H(B)/kbT

= e−(H(A)−H(B))/kbT = e−∆E/kbT (8.4.8)

Mit dieser Formel (8.4.8) kann man nun leicht eine Simulation eines Spin-Gitters schreiben. Der soerhaltene Monte-Carlo-Algorithmus ist gültig, wenn:

1. die sich ergebende Verteilung stationär ist:Dies garantiert der Metropolis-Algorithmus, der hier angewendet wurde, da er auf detailierter Ba-lance basiert.

2. die Prozedur „ergodisch“ ist, d.h. jeder Zustand ist von jedem Zustand aus in endlich viele Schrittenerreichbar.

8.4.2. Mean-Field-NäherungFür bestimte Fälle kann man das Ising-Modell analytisch lösen, oder zumindest Näherungen angeben.Hier soll die sog. Mean-Field-Näherung kurz erläutert werden. Für diese Näherung ersetzt man den Spinder Nachbarn durch den Erwartungswert des Spins:

〈S〉 =1N

∑i

Si. (8.4.9)

Aus dem Hamiltonian wird dann:

H ≈ −Bext∑

i

Si − J∑〈i,j〉

Si · 〈S〉 = −(Bext + 4J · 〈S〉

)·∑

i

Si (8.4.10)

Nun kann man analytisch die Zustandssumme Z berechnen:

Z =

[ ∑S=±1

expBext + 4J 〈S〉

T· S]n

=[2 · cosh

(Bext + 4J 〈S〉

T

)]n

(8.4.11)

Nun ist es möglich Voraussagen über die anderen thermodynamischen Größen zu treffen.



Inhaltsverzeichnis

(1) generiere eine zufälliges Spin-Gitter Si

(2) berechne nun ausgehende von S eine neue Konfiguration S′. Führ dazu folgende Schritte für jedenGitterplatz Si aus (ein Durchlauf = ein „Sweep“):

(2.1) bestimme zufällig (p = 12 ), ob der Spin geändert wird („Flip“)

(2.2) Ist S′i = Si (kein Flip), dann gehe zum nächsten Gitterplatz

(2.3) Ist S′i = −Si (Flip), dann berechne die Energierdifferenz ∆E der durch diesen Flip verän-derten Konfiguration. Ist ∆E < 0, so wird die neue Konfiguration akzeptiert. Für ∆E > 0wird sie mit der Wahrscheinlichkeit e−∆E/kbT angenommen.

(3) nimm die neue Konfiguration S′ in die Mittelwertsummen der Observablen auf.

(4) S← S′ und beginne bei 2 von Neuem

Algorithme 8: Metropolis-Algorithmus für das Ising-Modell

8.4.3. AlgorithmusDamit ergibt sich für das Ising-Modell folgendes Vorgehen: Der Schitt (2.3) scheint etwas kompliziert,ist aber nur eine Umsetzung der Akzeptanz-Wahrscheinlichkeit aus (8.3.3) und (8.3.4). Für die Energie-differenz ∆E muss natürlich nicht zweimal die Gesamtenergie des Gitters berechnet werden. Es genügtdabei die lokale Umgebung zu betrachten (1-dimensionaler Fall):

∆Ei = −Bext · (Si − S′i)− J · (Si−1Si + Si+1Si − Si−1S′i − Si+1S

′i) =

= −Bext · (Si − S′i)− J ·(Si−1(Si − S′i) + Si+1(Si − S′i)

)=

= −(Bext + J · (Si−1 + Si+1)

)· (Si − S′i) (8.4.12)

Am Beginn einer jeden Simulation sollten einige Sweeps durchlaufen werden, ohne dass die Ergebnissein die Observablen-Mittelwerte eingehen. Dies ermöglicht es der Markov-Kette ins Gleichgewicht zukommen. Man startet so mit einer typischen Konfiguration. Als Observablen kommen die folgendenGrößen in Frage (d: Anzahl der Dimensionen):

• Energie pro Spin E = 1NdH(S)

•Magnetisierung M = 1Nd

∑C

• spez. Wärme CV = 1

V∂E∂T =

⟨(E − 〈E〉)2

⟩=⟨E2⟩− 〈E〉2

• Suszeptibilität χV = 1

V∂M∂T =

⟨(M − 〈M〉)2

⟩=⟨M2⟩− 〈M〉2

Man nimmt periodische Randbedingungen an, um einen Ausschnitt aus einem großen (evtl. unendlichen)Gitter zu simulieren.5

8.4.4. EvaluationFür die Simulation setzt man zunächst (wie in der statistischen Physik üblich, β := 1

kbT. Damit ist

β die reziproke Temperatur und β−1 gibt die Temperatur in Energie-Einheiten an. Ein erster Test sollzeigen, ob das Ising-Modell typische Phänomene eines Ferromagneten reproduzieren kann. Ein einfachesPhänomen ist eine Hysterese-Schleife. Man erhält eine solche Struktur, wenn man einen Paramagnetenin ein externes Magnetfeld bringt und dieses zwischen −B0 und B0 hin- und hervariiert. Die Abbildung8.2 zeigt die Ergebnisse für ein 2-dimensionales Modell.



Inhaltsverzeichnis

-1

-0.5

0

0.5

1

-2 -1 0 1 2

Mag

net

isie

run

g

ext. Magnetfeld

Abbildung 8.2.: Hysterese-Kurve im 2D-Ising-Modell. Es wurde folgende Parametrisierung verwendet:N2 = 104 Spins, Bext = [−2..2], β = 1, J = 3.7.

Legt man ein konstantes externes Magnetfeld an, so richten sich alle Spins bei niedriger Temperaturentsprechend diesem Feld aus. Steigt nun die Temperatur, so wird diese Vorzugsamagnetisierung zerstört.Ab einer Grenztemperatur Tc (=Curie-Temperatur) verhält sich der Stoff nicht mehr Ferromagnetisch.Die folgende Abbildung 8.4 zeigt die Ergebnisse aus dem Ising-Modell.

Oben wurde die Abhängigkeit des Spin-Modells vom externen Magnetfeld diskutiert und es ergab sicheine Hysteresekurve. Mit steigender Temperatur wird der Einfluss des externen Magnetfeldes natürlichkleiner, was man deutlich in Abbildung 8.4 sieht.



Inhaltsverzeichnis

-8

-4

0

En

erg

ieJ=0.15

J=0.4J=0.8

J=0.99

0

0.5

1

0 1 2 3 4

Mag

net

isie

run

g

Temperatur

Abbildung 8.3.: Temperaturabhängigkeit im 2D-Ising-Modell. Es wurde folgende Parametrisierung verwen-det: N2 = 104 Spins, Bext = 1, T = [0..4].

-8

-4

0

En

ergi

e

-1

-0.5

0

0.5

1

-2 -1 0 1 2

Mag

net

isie

run

g

ext. Magnetfeld

T=0.5/kbT=1/kbT=2/kb

T=10/kb

Abbildung 8.4.: Temperatur- und Magnetfeldabhängigkeit im 2D-Ising-Modell. Es wurde folgende Parame-trisierung verwendet: N2 = 104 Spins.



Inhaltsverzeichnis

8.5. Der Random-Walk

Skalenverhalten über diskrete Zeitschritte: Bei einem Random-Walk betrachtet man ein Teilchen,dass sich auf einem Gitter (d-dimensional) bewegt. In jedem Zeitschritt hat es (im Falle d = 1) dieMöglichkeit mit der Wahrscheinlichkeit p1 = p nach rechts und mit p2 = 1 − p nach links zu laufen.Dabei legt es jedesmal die Strecke ∆x zurück. Im 2-dimensionalen Fall gibt es dann z.B. die Möglichkeitmit p1 nach oben, mit p2 nach unten, mit p3 nach rechts und mit p4 nach links zu laufen. Wichtig ist nur,dass die Wahrscheinlichkeiten normiert sind, also

∑i pi = 1. Hier soll aber nur der 1-dimensionale

Fall mit p = 1/2 und ∆x = ±1 behandelt werden; die anderen Fälle ergeben sich dann analog. Zuerstbetrachten wir die Position 〈x〉t=0 = 0 des Teilchens zu Anfang; es liegt im Ursprung. Für den nächstenZeitschritt gilt dann bzgl. der Mittelwerte:

〈x〉t=n+1 = 〈x〉t=n + 〈∆x〉︸︷︷︸=0

= 〈x〉t=n = ... = 〈x〉t=0 (8.5.1)

Da sich das Teilchen in beide Richtungen ∆x = ±1 mit gleicher Wahrscheinlcihkeit p = 1/2 bewegt, isthier 〈∆x〉 = 0 und der Mittelwert der Teilchenposition bleibt Null. Da sich das Teilchen aber trotzdembewegt, hätte man gerne ein Maß für die Bewegung. Dazu zieht man seine Varianz (resp. Standardab-weichung) heran:⟨

x2⟩t=n+1

=⟨(xn + ∆xn)2

⟩=⟨x2⟩t=n

+ 〈xn ·∆x〉︸︷︷︸=〈xn〉·〈∆x〉=0

+⟨∆x2

n

⟩︸︷︷︸=1

=⟨x2⟩t=n

+ 1 (8.5.2)

Da die Wahrscheinlichkeiten in zwei SChritten hier unabhängig sind, zerfällt der mittlere Ausdruck inein Produkt von Mittelwerten, wovon 〈∆x〉 = 0 ist. Aus obiger Rekursionsgleichung erhält man also dasSkalenverhalten des Random-Walk: ⟨

x2⟩

= n ⇔ σn =√n (8.5.3)

Die mittlere Breite des Randomwalk (Standardabweichung) ist also√n.

Skalenverhalten über Master-Gleichung: Wir betrachten nun ein Ensemble von Walkern auf einemd-dimensionalen hyperkubischen Gitter. Zu jedem Zeitschritt ∆t macht der Walker einen Schitt ∆~x ineiner der 1

2d möglichen Richtungen. Hier sei mit p(~x, t) die Wahrscheinlichkeit benannt, zum Zeitpunktt am Ort ~x zu sein. Man erhält dann folgende Master-Gleichung für den Walk:

∆t · ∂p∂t

=diskrete Zeitschritte

p(~x, t+ ∆t)− p(~x, t) =2d∑i=1

12d· p(~x+ ∆~xi, t)︸︷︷︸

Wahrsch. herzukommen

− 12d· p(~x, t)︸︷︷︸

Wahrsch. wegzugehen

(8.5.4)

Dividiert man diese Gleichung durch ∆t, so erhält man im Limes ∆t→ 0 eine Diffusionsgleichung, dieals Lösung einer anfänglichen Lokalisierten Verteilung p(~x, t0) = δ(~x − ~x0) eine Gauß-Kurve liefert.Diese skaliert dann mit

√t, was analog zu

√n bei diskreten Zeitschritten ∆t = 1 ist.



A. utils.h-PaketIn einigen Programmen in diesem Skript werden Matrix-Operationen benötigt. Sie werden in einfacherForm in der Datei utils.h zur Verfügung gestellt. Dabei sind Vektoren ein-dimensionale und Matrit-zen eben zwei-dimensionale Felder vom Typ double. Dazu gibt es eine Reihe von Methode, um sie zuallozieren, damit zu rechenen, sowie für die Ausgabe. Bei vielen Befehlen gibt es mehrere Varianten.Eine Variante erzeugt das Ergebnis als neue Ausgabe und gibt einen Pointer auf diesen Speicherbereichzurück. EIne weitere Variante verlangt als ersten Parameter einen Pointer auf eine Datenstruktur für dasErgebnis. Die dritte Variante speichert das Ergebnis im ersten Parameter. Die letztere ist meißt mit einemself im Namen gekennzeichnet.

• double ∗vector (long size ); :Erzeugt einen Vektor mit den Elementen a [1].. a[ size ]. Alle Elemente werden mit 0 initialisiert.

• double ∗∗matrix(long size ); :Erzeugt eine quadratische Matrix mit den Elementen mit den Elementen a [1.. size ][1.. size ]. AlleElemente werden mit 0 initialisiert.

• double ∗∗matrix_unity(long size ); :Erzeugt eine quadratische Einheits-Matrix mit den Elementen mit den Elementen a [1.. size ][1.. size ].

• long m_getsize(double∗∗ m)

long v_getsize (double∗ v);:Gibt die Größe einer Matrix bzw. eines Vektors zurück.

• void m_free(double ∗∗m)

void v_free (double ∗v):Gibt den Speicher einer Matrix/eines Vektors frei.

• void m_print(double∗∗ a)

void v_print (double∗ a):Gibt eine Matrix/einen Vektor auf cout aus.

• double∗ v_copy(double∗ a);

void v_copy(double∗ a, double∗ b); // a=b:Legt eine Kopie des Vektors an, bzw. kopiert den Inhalt eines Vektors in einen anderen

• double∗∗ m_copy(double∗∗ a);

void m_copy(double∗∗ a, double∗∗ b); // a=b:Legt eine Kopie der Matrix an, bzw. kopiert den Inhalt einer Matrix in eine andere

• double∗∗ m_add(double∗∗ a, double∗∗ b);

void m_add(double∗∗ a, double∗∗ b, double∗∗ c); // a = b + c

void m_addself(double∗∗ a, double∗∗ c); // a = a + c:Addiert zwei Matritzen

• double∗ v_add(double∗ a, double∗ b);

void v_add(double∗ a, double∗ b, double∗ c ); // a=b+c

void v_addself (double∗ a, double∗ c ); // a=a+c:Addiert zwei Vektoren

• double∗∗ m_mult(double∗∗ a, double∗∗ b) // = a∗b

void m_mult(double∗∗ a, double∗∗ b, double∗∗ c); // a= b∗c

void m_multself(double∗∗ b, double∗∗ c); // b=b∗c:Multiplizier zwei Matritzen.

94

Inhaltsverzeichnis

• double∗ vm_multr(double∗∗ a, double∗ b)

void vm_multr(double∗ a, double∗∗ b, double∗ c ); // a= b∗c:Multipliziert eine Matrix mit einem Spaltenvektor, von rechts.

• double∗ vm_multl(double∗ a, double∗∗ b)

void vm_multl(double∗ a, double∗ b, double∗∗ c); // a= b∗c:Multipliziert einen Zeilenvektor von links an die Matrix

• double∗ v_multconst(double∗ a, double c)

void v_multconst(double∗ a, double∗ b, double c ); // a = b ∗ c

void v_multconstself (double∗ a, double c ); // a=a∗c:Multipliziert einen Vektor mit einer Konstante.

• double∗∗ m_multconst(double∗∗ a, double c)

void m_multconst(double∗∗ a, double∗∗ b, double c ); // a = b ∗ c

void m_multconstself(double∗∗ a, double c ); // a=a∗c:Multipliziert eine Matrix mit einer Konstante.

• double∗ v_cross(double∗ a, double∗ b);

void v_cross(double∗ a, double∗ b, double∗ c ); // a= b∗c:Berechnet das Kreuzprodukt zweier Vektoren im R3.

• double v_skalar (double∗ a, double∗ b);:Berechnet das Skalarprodukt der beiden Vektoren.



B. GSL-GNU Scientific LibraryDi GSL ist eine freie Numerik-Bibliothek des GNU-Projektes. Die Homepage des Projektes ist http://www.gnu.org/software/gsl/. Unter folgender Adresse gibt es die Dokumentation der Biblio-thek zum Download: http://www.gnu.org/software/gsl/manual/gsl-ref_toc.html.Hier sollen nur einige kleine Jinweise zum grundlegenden Gebrauch gegeben werden.

96

http://www.gnu.org/software/gsl/

http://www.gnu.org/software/gsl/

http://www.gnu.org/software/gsl/manual/gsl-ref_toc.html

List of Algorithms

1. LU-Zerlegung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162. Jacobi-Methode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203. QR-Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4. Euler-Methode zur Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335. Leap-Frog-Integrator . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

6. Box-Muller-Algorithmus zur Erzeugung Gauß-verteilter Zufallszahlen (µ = 0, σ2 = 1) . 81

7. Berechnung von π über einen Monte-Carlo-Algorithmus . . . . . . . . . . . . . . . . . 868. Metropolis-Algorithmus für das Ising-Modell . . . . . . . . . . . . . . . . . . . . . . . 90

97

Listings5.1. Diese C++-Routine integriert eine ODE y = f(y(x), x) mit Euler. Als letzten Parameter

wird die Funktion f(·) übergeben. Die Implementation einer solchen Funktion ist zuerstangegeben. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34

5.2. Diese C++-Routine integriert eine ODE y = f(y(x), x) mit RK2 . . . . . . . . . . . . . 355.3. Diese C++-Routine integriert eine ODE y = f(y(x), x) mit RK4 . . . . . . . . . . . . . 376.1. Berechnung eines Feigenbaum-Diagrammes . . . . . . . . . . . . . . . . . . . . . . . . 696.2. Iteration der logistischen Abbildung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 696.3. Geometrische Interpretation der logistischen Abbildung. . . . . . . . . . . . . . . . . . 706.4. Berechnung des Lyapunov-Exponenten einer logistischen Abbildung. . . . . . . . . . . 706.5. Dieses Programm berechnet die Chirikov Standard-Abbildung . . . . . . . . . . . . . . 727.1. Implementation eines MCG mit Schrage’s Algorithmus . . . . . . . . . . . . . . . . . . 777.2. Implementation eines MCG mit Mischen der Ausgabe . . . . . . . . . . . . . . . . . . 77

98

Weblinks• Runge-Kutta:

– http://www.learn-line.nrw.de/angebote/modell/runge.htm• QL/QR

– http://de.wikipedia.org/wiki/QR-Algorithmus

– http://de.wikipedia.org/wiki/QR-Zerlegung

– http://en.wikipedia.org/wiki/QR_decomposition

– http://en.wikipedia.org/wiki/QR_algorithm• Numerov-Algorithmus:

– http://javapsi.sourceforge.net/JavaPsi_Bundeswb.pdf

– http://printfix.physik.uni-dortmund.de/vorlesungen/COMPHY/par14_shooting.pdf

– http://www.ma.umist.ac.uk/gb/UA392/notes/numv_cip.pdf

– http://www.heliosat3.de/e-learning/computational-physics/week7.pdf

• Poincaré-Bendixson:

– http://www.chaos.gwdg.de/~holger/Lehre/Chaos_WS03/node32.html

– http://en.wikipedia.org/wiki/Poincare-Bendixson_theorem• Verhulst-Dynamik, logistische Abbildung:

– http://www.achim-und-kai.de/kai/fuc/fuc_ver.html

– http://www.tphys.uni-heidelberg.de/~wegner/mech/Mechanik04-11a.ps

– http://tina.nat.uni-magdeburg.de/heiko/Mathematische_Methoden/WS2004/chaotic_maps.pdf

• Lorenz-Atraktor:

– http://andreas.welcomes-you.com/research/talks/lorenz/

– http://www.math.uni-hamburg.de/home/lauterbach/scripts/seminar03/prill.pdf

– http://www.tu-harburg.de/rzt/rzt/it/lorenz/lorenz.html• n-Körper-Problem:

– http://de.wikipedia.org/wiki/Laplace-Runge-Lenz-Vektor

– http://www.tat.physik.uni-tuebingen.de/~kley/lehre/cp-prakt/projekte/projekt1.pdf

– http://www.physics.drexel.edu/courses/CompPhys/Integrators/leapfrog/

– http://arxiv.org/PS_cache/astro-ph/pdf/9710/9710043.pdf• Standard-Abbildung:

– http://mathworld.wolfram.com/StandardMap.html• Integratoren/Quadratur:

– http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/integral/numint.html

• Monte-Carlo-Methoden/Ising-Modell:

– http://www.npac.syr.edu/users/paulc/lectures/montecarlo/p_montecarlo.html

99

http://www.learn-line.nrw.de/angebote/modell/runge.htm

http://de.wikipedia.org/wiki/QR-Algorithmus

http://de.wikipedia.org/wiki/QR-Zerlegung

http://en.wikipedia.org/wiki/QR_decomposition

http://en.wikipedia.org/wiki/QR_algorithm

http://javapsi.sourceforge.net/JavaPsi_Bundeswb.pdf

http://printfix.physik.uni-dortmund.de/vorlesungen/COMPHY/par14_shooting.pdf

http://printfix.physik.uni-dortmund.de/vorlesungen/COMPHY/par14_shooting.pdf

http://www.ma.umist.ac.uk/gb/UA392/notes/numv_cip.pdf

http://www.heliosat3.de/e-learning/computational-physics/week7.pdf

http://www.heliosat3.de/e-learning/computational-physics/week7.pdf

http://www.chaos.gwdg.de/~holger/Lehre/Chaos_WS03/node32.html

http://en.wikipedia.org/wiki/Poincare-Bendixson_theorem

http://www.achim-und-kai.de/kai/fuc/fuc_ver.html

http://www.tphys.uni-heidelberg.de/~wegner/mech/Mechanik04-11a.ps

http://www.tphys.uni-heidelberg.de/~wegner/mech/Mechanik04-11a.ps

http://tina.nat.uni-magdeburg.de/heiko/Mathematische_Methoden/WS2004/chaotic_maps.pdf

http://tina.nat.uni-magdeburg.de/heiko/Mathematische_Methoden/WS2004/chaotic_maps.pdf


http://www.math.uni-hamburg.de/home/lauterbach/scripts/seminar03/prill.pdf


http://www.tu-harburg.de/rzt/rzt/it/lorenz/lorenz.html

http://de.wikipedia.org/wiki/Laplace-Runge-Lenz-Vektor

http://www.tat.physik.uni-tuebingen.de/~kley/lehre/cp-prakt/projekte/projekt1.pdf

http://www.tat.physik.uni-tuebingen.de/~kley/lehre/cp-prakt/projekte/projekt1.pdf

http://www.physics.drexel.edu/courses/CompPhys/Integrators/leapfrog/

http://arxiv.org/PS_cache/astro-ph/pdf/9710/9710043.pdf

http://mathworld.wolfram.com/StandardMap.html

http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/integral/numint.html

http://people.hofstra.edu/faculty/Stefan_Waner/RealWorld/integral/numint.html

http://www.npac.syr.edu/users/paulc/lectures/montecarlo/p_montecarlo.html

http://www.npac.syr.edu/users/paulc/lectures/montecarlo/p_montecarlo.html

Listings

– http://www.g-pipa.de/Projekte/theoretische_Physik/seminar/seminar.html

– http://www.science.gmu.edu/~cchien/stm/ising/ising.html

– http://www.wmi.badw-muenchen.de/E23/lehre/skript/magnetismus/Kapitel-8.pdf


http://www.g-pipa.de/Projekte/theoretische_Physik/seminar/seminar.html

http://www.g-pipa.de/Projekte/theoretische_Physik/seminar/seminar.html

http://www.science.gmu.edu/~cchien/stm/ising/ising.html

http://www.wmi.badw-muenchen.de/E23/lehre/skript/magnetismus/Kapitel-8.pdf

http://www.wmi.badw-muenchen.de/E23/lehre/skript/magnetismus/Kapitel-8.pdf


Literaturverzeichnis[Coddington 1996] Coddington, Paul (1996): CPS 713: Monte Carlo Simulation. Syracuse University:

Vorlesungsskript.[http://www.npac.syr.edu/users/paulc/lectures/montecarlo/]

[Herrmann 2001] Herrmann, Dietmar (2001): C++ für Naturwissenschaftler. BeispielorientierteEinführung. Bonn - München - Reading, Mass.: Addison-Wesley.

[Jönck, Prill 2003] Jönck, Uwe / Prill, Florian (2003): Das Lorenz-System. Universität Hamburg: Se-minararbeit.

[http://www.math.uni-hamburg.de/home/lauterbach/scripts/seminar03/prill.pdf]

[Kuypers 1993] Kuypers, Friedhelm (1993): Klassiche Mechanik, 4. Auflage, Weinheim - New York -Basel - Cambridge: VCH.

[Mikkola, Aarseth 2001] Mikkola, Seppo / Aarseth, Sverre (2001): A Time-Tranformed LeapfrogScheme. Integration of Few-Body-Systems with Large Mass Ratios, in: Celestial Mechanicsand Dynamical Astronomy 84, S. 343-354.

[Numerical Recipies Software 1992] Numerical Recipies Software (1992): Numerical Recipes in C.The Art of Scientific Computing. Cambridge: Cambridge University Press.[http://www.library.cornell.edu/nr/cbookcpdf.html]

[Rannacher 2005a] Rannacher, Rolf (2005a): Einführung in die Numerische Mathematik (Numerik0). o.O. Institut für angewandte Mathematik, Uni Heidelberg.[http://numerik.uni-hd.de/~lehre/notes/num0/numerik0.pdf]

[Rannacher 2005b] Rannacher, Rolf (2005b): Numerische Methoden für gewöhnliche Differential-gleichungen (Numerik 1). o.O. Institut für angewandte Mathematik, Uni Heidelberg.[http://numerik.uni-hd.de/~lehre/notes/num1/numerik1.pdf]

[Stoer 1999] Stoer, Josef (1999): Numerische Mathematik 1. Eine Einführung - unter Berücksich-tugung von Vorlesungen von F.L. Bauer, 8. Auflage, Berlin - Heidelberg - New York: SpringerVerlag.

[Stoer, Bulirsch 2000] Stoer, Josef / Bulirsch, Roland (2000): Numerische Mathematik 2. Eine Ein-führung - unter Berücksichtugung von Vorlesungen von F.L. Bauer, 4. Auflage, Berlin -Heidelberg - New York: Springer Verlag.

[Weisstein 2005] Weisstein, Eric W. (2005): QR Decomposition. 13.10.2005[http://mathworld.wolfram.com/QRDecomposition.html]

[Wiedemann 2004] Wiedemann, Harald (2004): Numerische Physik. New York - Berlin - Heidelberg:Springer.

Stoffzusammenfassungen der Analysis und Linearen Algebra finden im Internet sich unter:

http://jkrieger.de/mathe/index.html

101

http://www.npac.syr.edu/users/paulc/lectures/montecarlo/


http://www.library.cornell.edu/nr/cbookcpdf.html

http://numerik.uni-hd.de/~lehre/notes/num0/numerik0.pdf

http://numerik.uni-hd.de/~lehre/notes/num1/numerik1.pdf

http://mathworld.wolfram.com/QRDecomposition.html

http://jkrieger.de/mathe/index.html

Documents

Computerphysik und Numerik - jkrieger.dejkrieger.de/download/computerphysik.pdf · 2006. 7. 23. · Inhaltsverzeichnis •Es gilt bei nExponentenbits mit obigen Benennungen: E:= C−BIAS