gelesen von Prof. Thomas Pertsch im WS 2018/19 …...Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_2019-02-16s.docx 1 Computational Physics I gelesen von Prof

Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_2019-02-16s.docx 1

Computational Physics I gelesen von Prof. Thomas Pertsch im WS 2018/19

an der Friedrich-Schiller-Universität Jena

0. Einführung und Motivation ..................................................................................... 3 1. Grundlegende Methoden der numerischen Mathematik ....................................... 5

1.1 Zahlendarstellung im Computer .............................................................................................. 5 1.2 Diskretisierung .......................................................................................................................... 6 1.3 Differentiation .......................................................................................................................... 7

1.3.1 Fehlerabschätzung ....................................................................................................... 8 1.3.2 Verbesserung der Konvergenzordnung ...................................................................... 9 1.3.3 Ableitungen höherer Ordnung .................................................................................. 11 1.3.4 Spektralverhalten der Ableitungsoperatoren........................................................... 11

1.4 Integration .............................................................................................................................. 13 1.4.1 Rechteckregel ............................................................................................................. 14 1.4.2 Trapezregel ................................................................................................................. 15 1.4.3 Simpson-Regel ............................................................................................................ 17 1.4.4 Bode-Regel ................................................................................................................. 17 1.4.5 Intervallteilungsverfahren ......................................................................................... 17 1.4.6 Gauss-Quadratur ........................................................................................................ 20

1.5 Nullstellen und Extrema ......................................................................................................... 21 1.5.1 Nullstellen von Funktionen einer Veränderlichen ................................................... 21 1.5.2 Extrema von Funktionen einer Veränderlichen ....................................................... 29 1.5.3 Minima von Funktionen mehrerer Veränderlicher .................................................. 32

1.6 Interpolation ........................................................................................................................... 37 1.6.1 Interpolationsformel von Lagrange .......................................................................... 37 1.6.2 Die Spline-Interpolation ............................................................................................. 39 1.6.3 Rationale Approximation ........................................................................................... 42

2. Lineare Gleichungssysteme ................................................................................... 44 2.1 Implementierung in Computer-Algebra-Systemen .............................................................. 44 2.2 Gauss-Jordan-Elimination ...................................................................................................... 46 2.3 Löser für tridiagonale Matrizen ............................................................................................. 48 2.4 LU-Zerlegung (Dekomposition, Faktorisierung) .................................................................... 49 2.5 Iterative Verbesserung der Lösung ....................................................................................... 51 2.6 Eigenwertprobleme ............................................................................................................... 52

3. Fourier-Transformation ......................................................................................... 54 3.1 Die diskrete Fourier-Transformation..................................................................................... 56 3.2 Fast-Fourier-Transformation ................................................................................................. 58 3.3 Das Abtasttheorem ................................................................................................................ 59

4. Gewöhnliche Differentialgleichungen ................................................................... 62 4.1 Anfangswertaufgaben (AWA) ................................................................................................ 62

4.1.1 Vorwärts-Euler-Verfahren ......................................................................................... 63 4.1.2 Rückwärts-Euler-Verfahren ....................................................................................... 69 4.1.3 Crank-Nicolson-Verfahren ......................................................................................... 71 4.1.4 Alpha-Verfahren ......................................................................................................... 73 4.1.5 Explizite Runge-Kutta-Verfahren ............................................................................... 73 4.1.6 Implizite Runge-Kutta-Verfahren .............................................................................. 78 4.1.7 Schrittweitensteuerung ............................................................................................. 78 4.1.8 Steife Probleme .......................................................................................................... 80


4.2 Randwertaufgaben (RWA) ..................................................................................................... 81 4.2.1 Methode der finiten Differenzen .............................................................................. 82 4.2.2 Schießverfahren ......................................................................................................... 84

5. Partielle Differentialgleichungen ........................................................................... 86 5.1 Elementare Methoden zur Lösung von partiellen Differentialgleichungen (Finite-

Differenzen-Methode für Anfangswertaufgaben) ............................................................... 88 5.2 Stabilitätsanalyse nach von Neumann .................................................................................. 92 5.3 Split-Step-Verfahren............................................................................................................... 95

Ergänzung zu den Kapiteln .......................................................................................... 97 Ausgewählte Lösungsvorschläge ............................................................................... 103


0. Einführung und Motivation Computational Physics ist ein Querschnittsfach aus den Bereichen Mathematik, Physik und Informatik. Ziel der Vorlesung Computational Physics I ist die Vermittlung der Grundlagen physikalischer Modellbildung, der Simulation physikalischer Systeme mittels computergestützter Methoden, der Datenanalyse und der Visualisierung. Es handelt sich dabei um einen Einführungskurs, der sich an den Bedürfnissen der Physik orientiert. Der Kurs erhebt deshalb nicht den Anspruch eines durch und durch mathematisch fundierten Numerikkurses oder einer systematischen Informatikvor-lesung. Zur Entwicklung eines grundlegenden Verständnisses physikalischer Systeme sind analytische Lösungen unabdingbar. Unter dem Gesichtspunkt der Anwendung auf reale physikalische Problemstellungen sind analytische Lösungen aufgrund der meist erforderlichen starken Nährungen jedoch nur bedingt brauchbar. Mit dem rapiden Anstieg der Verfügbarkeit leistungsfähiger Computertechnik entwickelt sich deshalb die physikalische Modellbildung hin zu Modellen, die mit numerischen Standard-verfahren gelöst werden können. Dies erlaubt die Untersuchung bedeutend komplexerer Systeme, ohne die Notwendigkeit ergebnisbeeinflussender starker Nährungen bei der Modellbildung.

Lösungsgenauigkeit Wenn physikalische Experimente durch numerische Verfahren simuliert werden, muss jedoch sichergestellt werden, dass die numerisch ermittelte Lösung hinreichend gut mit der exakten (analytischen) Lösung und damit mit der realen Physik übereinstimmt. Problematisch ist dabei, dass die analytische Lösung des numerisch untersuchten Problems meist nicht bekannt ist oder gar nicht existiert. Zur Beschreibung der Fehlereigenschaften numerischer Lösungsverfahren für physi-kalische Probleme werden häufig drei Fehlerkriterien angewandt, die jedoch stark miteinander verbunden sind. Dies sind die Kondition, die Stabilität und die Konsistenz. Die Kondition ist eine Eigenschaft des Problems selbst und ist deshalb unabhängig vom spezifischen Lösungsverfahren. Die Kondition beschreibt die Abhängigkeit der Lösung von einer Störung der Eingangsdaten, da auch diese meist nur mit begrenzter Genauigkeit bekannt sind. Demgegenüber ist die Stabilität eine Eigenschaft der numerischen Lösungsmethode. Sie beschreibt die Abhängigkeit der numerischen Lösung von gestörten Eingangs-daten im Vergleich zur analytischen Lösung. Insbesondere beschreibt die Stabilität damit auch die Robustheit eines numerischen Verfahrens gegenüber Rundungs-fehlern, die durch den begrenzten Zahlenvorrat bei der Berechnung mathematischer Basisoperationen (+,-,*,/) entstehen.


Die Konsistenz ist wiederum eine Eigenschaft des numerischen Verfahrens. Diese beschreibt, inwieweit durch das Verfahren wirklich das gegebene mathemisch-physikalische Problem gelöst wird oder ob nicht etwa die numerische berechnete Lösung aufgrund ihres numerisch formulierten Lösungsansatzes ganz systematisch ein alternatives Problem löst.

Skalierung notwendiger Ressourcen Ein weiteres Kriterium für den Erfolg numerischer Methoden liegt im Ressourcen-bedarf zur Berechnung der numerischen Lösung und dabei insbesondere dessen Skalierungsverhaltens hinsichtlich der Dimensionalität des Problems. So erlauben die meisten numerischen Verfahren auch heute noch lediglich die Lösung sehr kleiner Probleme, da der Bedarf an Computerrechenzeit, Computerspeicher oder immer mehr auch die für die Berechnungen erforderliche Energie sehr schnell mit der Dimension des Problems wächst. Als Dimension wird hierbei die Anzahl der Freiheits-grade der Lösung, also z.B. die Anzahl zu berechnender freier Lösungspunkte, bezeichnet. Es ist deshalb wichtig, möglichst effiziente numerische Verfahren zu entwickeln, die auch mit begrenzten Computerressourcen die hinreichend akkurate Berechnung relevanter physikalischer Aufgabenstellungen erlauben. Letztlich besteht die Aufgabe, die entwickelten numerischen Algorithmen in einer Programmiersprache umzusetzen. Dazu werden in der Vorlesung Computational Physics I die Programmierumgebung MATLAB (bzw. die Programmiersprache MATLAB) sowie die Programmiersprache PYTHON verwendet, da diese bereits nach geringer Einarbeitungszeit zu ersten Ergebnissen führen und gleichzeitig auch bei fortschreitender Nutzerkenntnis immer bessere/effizientere Lösungen erlauben.


1. Grundlegende Methoden der numerischen Mathematik

1.1 Zahlendarstellung im Computer Im Computer werden alle Berechnungen im sog. Binärsystem ausgeführt. Jede Zahl wird deshalb in einem Binärcode dargestellt, d.h. sie wird ausschließlich durch Nullen und Einsen repräsentiert 0 1. Dabei korrespondiert die Position der Nullen oder Einsen in der gesamten Binärzahl mit der entsprechenden Zweierpotenz. Der Übersetzungsmechanismus sei an diesem Beispiel verdeutlicht:

7 6 5 4 3 2 1 0

Binärzahl: 0 1 0 0 1 1 1 0Zweierpotenz: 2 2 2 2 2 2 2 2

128 64 32 16 8 4 2 164 8 4 2 78+ + + + =

Eine zum Binärsystem kompatible Darstellung ist das Hexadezimalsystem

0 1 2 3 4 5 6 7 8 9 A B C D E F

Die hexadezimale Darstellung der Dezimalzahl 78 ist dann

3 2 1 0 3 2 1 0

0 1 0 0 1 1 1 02 2 2 2 2 2 2 28 4 2 1 8 4 2 1

4 8 4 2 4E

E+ + =

In der Numerik werden zwei Grundtypen von Zahlen unterschieden. Dies sind einerseits Integertypen, d.h. ganze Zahlen mit oder ohne Vorzeichen und unter-schiedlichem Wertebereich. Der zweite Grundtyp sind Realtypen, mit denen rationale Zahlen dargestellt werden können. Aus diesen beiden Grundtypen können dann weitere Zahlentypen und Strukturen, wie z.B. komplexe Zahlen, abgeleitet werden.

Speicherplatzbedarf Innerhalb spezieller Zahlentypen wird meist nach dem für die jeweilige Darstellung erforderlichen Speicherplatz unterschieden. Für diese Kategorisierung der Typen erfolgt die Einteilung meist nach folgendem Muster:

16 32 64 128 bit

Dieses Muster beruht auf der Adressierung des Speichers im Computer mit einem Raster von 8/16/32/64 bit. Dies bezeichnet den kleinsten separat zu lokalisierenden Speicherabschnitt. Dabei sind: Bit = 1 Speichereinheit mit 0 oder 1 belegt Byte = 8 Bit


Wort = 16 Bit 1kBit = 1024 Bit

Eigenschaften der Zahlentypen Durch den endlichen Zahlenvorrat im Binärsystem mit begrenztem Speicher wird die Dynamik und Auflösung eines Zahlentyps bestimmt. Die Dynamik ist das Verhältnis vom größtem zum kleinsten Betrag und die Auflösung der Abstand zweier benachbarter Zahlen. Für rationale Computerzahlen werden diese Eigenschaften jedoch nicht eindeutig durch den eingesetzten Speicherplatz bestimmt, sondern können geeignet gegen-einander abgewogen werden. Als Beispiel sei hier eine häufig angewandte Aufteilung der Bits bei einem 64 Bit Realtyp nach dem IEEE-Standard beschrieben. Diese Aufteilung ergibt sich aus der halblogarithmischen Darstellung der Zahlen ent-sprechend:

( )1 2s er m= − ⋅ ⋅

mit s = Signum: 1 Bit m = Mantisse: 52 Bit e = Exponent: 11 Bit Die Dynamik dieses Zahlentyps bestimmt sich vor allem aus dem Exponenten.

10 10

1023 1024 308 308

e (2 1) 21023 1024

2 2 10 10− −

= − −= −

≈

Die Auflösung ist dabei nur relativ zum jeweiligen Zahlenwert zu bestimmen, da die Auflösung über dem gesamten darstellbaren Wertebereich stark variiert. Die Auf-lösung bestimmt sich im Wesentlichen aus der Mantisse.

52 162 10− −≈

1.2 Diskretisierung Um numerische Berechnungen vornehmen zu können, ist es notwendig, kontinu-ierliche Argumenten- und Werteverteilungen auf endliche diskrete Argumenten- und Wertemengen abzubilden. Dies können einfach die Funktionswerte an diskreten Stellen, den sog. Stützstellen, sein. Alternativ können als Wertemenge z.B. auch die Mittelwerte in Intervallen um die jeweiligen diskreten Stützstellen dienen. Eine weitere Möglichkeit, um kontinuierliche Werteverteilungen mit einer endlichen Zahl von Werten zu beschreiben, ist die Entwicklung der kontinuierlichen Werteverteilung in ein Funktionensystem. Dabei wird eine endlich Zahl von Entwicklungskoeffizienten als diskrete Wertemenge numerisch weiterverarbeitet.


Bei der Diskretisierung wird prinzipiell zwischen äquidistanter und nichtäquidistanter Diskretisierung unterschieden. Bei der äquidistanten Diskretisierung bleibt der Abstand zwischen den Stützstellen, unabhängig von den lokalen Eigenschaften des zu lösenden Problems, stets konstant. Eine Anpassung der Diskretisierung an das Problem erfolgt nur global für den gesamten Lösungsbereich. Bei der nichtäqui-distanten Diskretisierung wird der Stützstellenabstand den lokalen Eigenschaften des Problems angepasst und dementsprechend über den Argumentenbereich variiert. Um die Schreibweise diskretisierter Werteverteilungen zur Notation der Algorithmen effizienter zu gestalten, werden z.B. die Funktionswerte ( )if x für diskrete Argumenten ix mit ( )i if f x= bezeichnet. Wesentlicher Gegenstand der numerischen Mathematik und auch dieser Vorlesung ist die Formulierung mathematischer Operatoren für die Anwendung auf diskrete Werteverteilungen. Man spricht dabei von der Diskretisierung der Operatoren. Dabei werden aus analytischen Ausdrücken rein algebraische Formulierungen.

1.3 Differentiation Als erstes Beispiel für einen solchen diskreten Operator werden wir die diskrete Version der uns bekannten Differentiation behandeln. Dabei wird für eine gegebene Diskretisierung if der Funktion ( )f x ein diskreter Differentialoperator

[ ] ( )( ) : 'D f x f x= gesucht. Zur Ableitung des diskreten Differentiationsoperators gehen wir von der Definition der uns bekannten Ableitung aus. Eine mögliche Definition, ist die des Grenzwertes des rechtsseitigen (vorwärts) Differenzenquotienten:

0

( ) ( ) ( )( ) limh

f x f x h f xf xx h→

∂ + −′= =∂

Im Gegensatz zur analytischen Lösung mit Ausführung des Grenzübergangs, wird für die diskrete Version des Differentialoperators der Differenzenquotient numerisch mit einem endlichen h berechnet.

( ) ( )[ ( )]hf x h f xD f x

h+ −

=

Alternativ kann die Ableitung des diskreten Differentialoperators auch ausgehend vom linksseitigen (rückwärts) Differenzenquotienten erfolgen:

( ) ( )[ ( )]hf x f x hD f x

h− −

=

(Differentiation ) 1 h=0.01; %Stützstellenabstand 2 x=0:h:2*pi; %Diskretisierung des Argumentenbereichs x 3 y=sin(x); %Berechnung der diskreten Funktionswerte 4 y2=sin(x-h); %Berechnung Funktionswerte an versetzten Stützstellen 5 df = (y – y2)/h; %Berechnung der diskreten Ableitung


6 7 plot(x,y); %grafische Darstellung der Funktionswerte 8 hold on; %Grafikausgabe für weitere Darstellung anhalten 9 plot(x,df,'r'); %grafische Darstellung der Ableitung

1.3.1 Fehlerabschätzung Für die Einschätzung der Richtigkeit der numerischen Lösung ist eine Abschätzung der durch die Diskretisierung hervorgerufenen Fehlers von Bedeutung. Dieser sogenannte Diskretisierungsfehler bezeichnet die Abweichung des Ergebnisses der numerischen Näherungsrechnung vom exakten analytischen Ergebnis:

( ) [ ( )]h hE f x D f x′= −

Der Diskretisierungsfehler ergibt sich demnach aus der Differenz der analytisch berechneten Ableitung ( )f x′ gegenüber der Abschätzung durch die Berechnung eines Differenzenquotienten mit endlichem h , wobei eine exakte Repräsentation der numerischen Zahlen und elementaren Operatoren angenommen wird, sodass kein zusätzlicher Rundungsfehler durch den endlichen Zahlenraum auftritt. Allgemeine Eigenschaften des diskreten Differentialoperators:

− [ ]hD f konvergent: [ ]0

lim hhD f

→ konvergiert (nur bis zum Rundungsfehler)

− [ ]hD f konsistent: konvergiert gegen richtigen Wert (0

lim 0hhE

→→ )

Beide Operatoren (rechtsseitiger und linksseitiger) sind konsistent, weil mit

0lim 0hh

E→

→

der diskrete Operator in die kontinuierliche Definition übergeht (zumindest für stetig differenzierbare Funktionen). Es ist allerdings von großer Bedeutung, mit welcher Abhängigkeit von h der diskrete Operator gegen die exakte analytische Lösung konvergiert. Zum Verständnis soll folgende Erläuterung helfen. Es ist zu unterscheiden, dass einerseits ein Fehler durch die Diskretisierung des Operators [ ]hD f eingeführt wird, der sog. Diskretisierungsfehler. In diesem Beispiel ist dies die Berechnung des Differenzenquotienten für endliche h statt der Ausführung des Grenzübergangs

0h → . Zusätzlich entsteht ein Fehler durch die Ausführung der Berechnungen als numerische Operationen mit Computerzahlen endlicher Genauigkeit, sodass bei jeder elementaren Rechenoperation (+, -, *, /, …) ein sog. Rundungsfehler auftritt. Dieser Rundungsfehler ist unvermeidbar, kann aber durch die Verwendung von Zahlenformaten mit hoher Auflösung (siehe Abschnitt 1.1) reduziert werden. Die wirkliche Größe des Rundungsfehlers ist meist nur schwer abzuschätzen. Im Beispiel ist es verständlich, dass der Rundungsfehler der Division umso größer ist, je kleiner der Divisor h ist. Eine Formulierung des diskreten Differentialoperators ist deshalb umso besser, je schneller der Diskretisierungsfehler mit kleiner werdendem h gegen


Null geht, d.h. das Ergebnis des Operators gegen die exakte Lösung konvergiert. Damit kann der bei zu kleinem h auftretende Rundungsfehler vermieden werden.

Konvergenzeigenschaften des diskreten Differentialoperators Eine Herleitung der Konvergenzeigenschaften des diskreten Differentialoperators kann folgendermaßen erfolgen: Voraussetzung: ( )f x differenzierbar und ( )'f x bekannt

Die Abhängigkeit der Konvergenz von h betrachten wir am Beispiel des rechtsseitigen Differentialoperators,

( ) ( )[ ( )]hf x h f xD f x

h+ −

=

mit Hilfe einer Taylorentwicklung der Definition:

2 3 41 1( ) ( ) ( ) ( ) ( ) ( )2 6

f x h f x f x h f x h f x h O h′ ′′ ′′′+ = + ⋅ + ⋅ + ⋅ + (*)

ersetzen wir ( )f x h+ in [ ( )]hD f x durch (*)

2 31 1[ ( )] ( ) ( ) ( ) ( )2 6

[ ( )] ( ) ( )

h

h

D f x f x f x h f x h O h

D f x f x O h

′ ′′ ′′′= + ⋅ + ⋅ +

′= +

Eigenschaften: • Der diskrete Differentialoperator konvergiert demnach in erster Ordnung. Der Diskretisierungsfehler geht mindestens mit h gegen Null.

Für den linksseitigen Differentialoperator verläuft die Rechnung analog.

Stencil-Notation Eine verkürzte Schreibweise ist die sogenannte Stencil-Notation (Stencil = Schablone), welche die Vorfaktoren vor den Funktionstermen bezüglich h notiert. Die beiden bereits definierten Operatoren schreiben sich dann folgendermaßen:

( ) ( ) 1 [0 11]f x h f xh h

+ −⇒ − rechtsseitig / vorwärts

( ) ( ) 1 [ 110]f x f x hh h

− −⇒ − linksseitig / rückwärts

1.3.2 Verbesserung der Konvergenzordnung Durch geschickte Kombination verschiedener langsam konvergenter Differential-operatoren ist es möglich komplexe Differentialoperatoren zu konstruieren, bei denen sich die führenden Fehlerterme der Einzeloperatoren gegenseitig aufheben und somit der komplexe Gesamtoperator mit höherer Ordnung in h gegen die exakte analytische Lösung konvergiert.


Ziel: Elimination des h-Fehlerterms Ansatz: Kombination des rechtsseitigen und des linksseitigen Differentialoperators

1 1 1 1[0 11] [ 110] [ 101]2 2h h h

− + − = −

.

Es resultiert der sog. zentrale Differentialoperator

( ) ( )[ ( )]2h

f x h f x hD f xh

+ − −=

mit verbesserten Konvergenzeigenschaften. Fehlerabschätzung:

2 3

2

( ) ( ) 1[ ( )] ( ) ( ) ( )2 6

[ ( )] ( ) ( )

h

h

f x h f x hD f x f x f x h O hh

D f x f x O h

+ − − ′ ′′′= = + ⋅ +

′= +

konvergiert mindestens mit h2 Anhand der Beispielfunktion sin( )x lässt sich die unterschiedliche Genauigkeit der diskreten Differentialoperatoren graphisch darstellen.

Ableitungen der Funktion sin( )x bei Anwendung verschiedener diskreter Differentialoperatoren im Vergleich zur analytischen Ableitung.

Dieses Verfahren lässt sich weiter verbessern, indem durch Hinzufügen weiterer Operatoren zum Gesamtoperator der jeweils führende Fehlerterm eliminiert wird.


Eine Möglichkeit ist z.B., dass man in der Stencil-Notation des zentralen Operators zu einem breiteren Stencil übergeht, d.h. von h zu 2h und dann versucht, durch Kombination verschiedener Operatorformen den h²-Term ( f ′′′ -Term) zu eliminieren.

2 3

1 ( 2 ) ( 2 )[ 10 0 01]4 4

4( ) ( ) ( )6

f x h f x hh h

f x f x h O h

+ − −− =

′ ′′′= + ⋅ +

Demnach ergibt folgende Kombination

( ) ( ) ( ) ( )

3

112

1 14 [ 101] [ 10 0 01] 3 ( )2 4

1[ ( )] [1 8 0 8 1]12

2 8 8 2

h

h

f O hh h

D f xh

f x h f x h f x h f x h

′− − − = +

= − −

= − + + + − − + −

einen Differentialoperator, der mit 3h konvergiert.

1.3.3 Ableitungen höherer Ordnung Um höhere Ableitungen darzustellen, startet man wieder bei der Taylorentwicklung

2 3 4

2 3 4

1 1( ) ( ) ( ) ( ) ( ) ( )2 61 1( ) ( ) ( ) ( ) ( ) ( )2 6

f x h f x f x h f x h f x h O h

f x h f x f x h f x h f x h O h

′ ′′ ′′′+ = + ⋅ + ⋅ + ⋅ +

′ ′′ ′′′− = − ⋅ + ⋅ − ⋅ +

Addieren der beiden Gleichungen und Umstellen nach ( )''f x ergibt

22

22

( ) 2 ( ) ( )( ) ( )

1 [1 2 1]h

f x h f x f x hf x O hh

Dh

− − + +′′ = +

= −

Und konstruiert damit einen Differentialoperator zweiter Ordnung, der mit zweiter Ordnung konvergiert (beachte 4 2 2( ) / ( )O h h O h= ).

1.3.4 Spektralverhalten der Ableitungsoperatoren Bisher haben wir untersucht, wie sich die Differentialoperatoren in Abhängigkeit vom Stützstellenabstand der Diskretisierung h verhalten. Durch den Einsatz der Taylorentwicklung haben wir dabei implizit angenommen, dass es sich bei den abzuleitenden Funktionen um hinreichend glatte Funktionen ( )f x handelt, bei denen die Taylorentwicklung konvergiert. Für verschiedene abzuleitende Funktionen wird diese Annahme unterschiedlich gut gewährleistet sein. Wir wollen deshalb nun untersuchen, wie sich die Differentialoperatoren in Abhängigkeit von der Form der Funktion ( )f x verhalten, auf die sie angewandt


werden. Nun können wir allerdings diese Untersuchung nicht für alle möglichen Fälle abzuleitender Funktionen einzeln durchführen. Wir suchen stattdessen nach einem verallgemeinerungsfähigen Ergebnis. Für lineare Operatoren, wie z.B. die zu untersuchenden Differentialoperatoren, eignen sich die harmonischen Funktionen exp( )ikx (Lösungen der Oszillatorgleichung mit der Oszillationsfrequenz k bzw. sog. Fourier-Moden) sehr gut als allgemeine Testfunktion, da die Wirkung eines Operators auf alle Fourier-Moden die gesamte Information über den Operator enthält. Bei der Untersuchung der Differentialoperatoren wird deren Konvergenzverhalten in Abhängigkeit vom Parameter kh , d.h. dem Verhältnis der Oszillationsperiode der Testfunktion (1/ k ) zum Stützstellenabstand h , betrachtet.

( ) e( ) e

ikx

ikx

f xf x ik

=

′ =

Die Bestimmung von f’ mittels des zentralen Differentialoperators ergibt

( )

( )

( ) ( )e e e[e ] e e2 2

sin( )e sin ( ) ( )sinc( )

ik x h ik x h ikxikx ikh ikh

h

ikx

Dh h

ik khkh f x f x khhk kh

+ −−−

= = −

′ ′= = =

Der Diskretisierungsfehler in Abhängigkeit von der Oszillationsfrequenz k , der sog. spektrale Fehler, ist demnach

( )( )s 1 sinc( )E f x kh′= −

Plot von ( ) sinc( )f x x= mit Nullstellen bei ,2 ,3 ,π π π

Aus dem Graphen lassen sich sehr einfach die spektralen Eigenschaften des Operators ablesen:

1kh << 2sinc( ) 1 ([ ] )kh O kh= + , d.h. für niederfrequente bzw. langwellige Funktionen besitzt der zentrale Differentialoperator, wie wir oben bereits gesehen haben, eine Konvergenz in 2. Ordnung

0 1 2 3 4

0

0.2

0.4

0.6

0.8

1

π π π πx

sinc (x)


kh = π sinc( ) 0π = , d.h. für hochfrequente bzw. kurzwellige Funktionen, bei denen die Oszillationsperiode genau mit dem Stützstellenabstand übereinstimmt, kann der zentrale Operator sogar verschwinden

2khπ < < π sinc( ) 0kh < , d.h. der zentrale Differentialoperator liefert bei Anwendung auf sehr hochfrequent oszillierende Funktionen das falsche Vorzeichen und damit ein vollkommen falsches Ergebnis

1.4 Integration Numerische Integrationsverfahren erlauben die Berechnung des bestimmten Inte-grals einer Funktion ( )f x auf einem Intervall [ , ]a b

( )b

a

A dx f x= ∫ .

Es sollen nun Verfahren vorgestellt werden, mit denen solche Berechnungen mit möglichst wenig Rechenaufwand und hoher Genauigkeit durchgeführt werden können. Zuerst betrachten wir dazu sog. Standardverfahren, welche auf der Diskretisierung des Integrationsintervalls beruhen. Obwohl das bestimmte Integral einer Funktion

( )f x eine globale Eigenschaft dieser Funktion über dem gesamten Integrations-intervall darstellt, wird bei der numerischen Berechnung des Integrals mittels einem Standardverfahren, von den lokalen Eigenschaften der Funktion ( )f x bzw. von deren Approximation ausgegangen. Entsprechend wird das zu integrierende Intervall in Teilintervalle zerlegt und die resultierenden Teilintegrale werden genähert. Zur Vereinfachung der Betrachtung gehen wir von einer äquidistanten Diskretisierung aus. Durch diese Zerlegung des Integrationsintervalls [ , ]a b ergeben sich N gleichgroße Teilintervalle 1[ , ]i i iI x x += mit der Intervallbreite 1i ih x x+= − bzw. ausgedrückt durch die Intervallgrenzen

( ) /h b a N= − . Dabei ist 0x a= , Nx b= .

Zerlegung des Integrationsgesamtintervalls [ , ]a b in N gleichgroße Teilintervalle

1[ , ]i i iI x x += .


Die Fläche unter der Kurve in dem in N Teilintervalle zerlegten Gesamtintervall ist dann

( )11

0.

i

i

xN

i x

A dx f x+−

=

= ∑ ∫

Die Aufgabe besteht nun darin, das einzelne Teilintegral im i-ten Teilintervall

( )1i

i

x

ix

A f x dx+

= ∫

möglichst genau zu bestimmen.

1.4.1 Rechteckregel Die N ausreichend schmalen Teilintervalle 1[ , ]i i iI x x += approximieren wir nun durch Rechtecke der Breite h . Um ein exaktes Ergebnis zu erzielen, sollte die Höhe der Rechtecke eigentlich dem Mittelwert des Funktionswertes im jeweiligen Teilintervall entsprechen, da dann die aufsummierte Fläche der Rechte genau der Fläche unter der zu integrierenden Funktion entspricht. Man wird leicht einsehen, dass dieser Mittelwert ziemlich aufwendig zu berechnen ist. Für langsam veränderliche Funktionen ist der Funktionswert im Mittelpunkt des Teilintervalls jedoch eine gute Approximation des Mittelwertes. Dies ist die Idee der Rechteckregel.

12

( )2i i i

hf x f x f+

≈ + =

So ergibt sich das gesamte Integral näherungsweise zu 11 1 1

1 1 10 0 02 2 2

i

i

xN N N

i i ii i ix

b aA dx f h f fN

+− − −

+ + += = =

−≈ = =∑ ∑ ∑∫

Rechteckregel: Näherung des Gesamtintegrals durch mehrere Rechtecke mit Höhe des Funktionswertes im Teilintervallmittelpunkt.


Fehlerbetrachtung für Teilintegral Um den durch die Näherung verursachten Fehler analysieren zu können, betrachten wir eine Taylorentwicklung um den Mittelpunkt eines Teilintervalls

1 1 12 2 2

12

2

1 12 2

3 4

1 12 2

1 1( ) ' ''1! 2!

1 '''3!

i i ii i

i i i

f x f f x x f x x

f x x O x x

+ + ++ +

+ + +

= + ⋅ − + ⋅ −

+ ⋅ − + −

Die ungeraden Terme der Taylorentwicklung verschwinden bei der Integration über Teilintervalle.

( ) ( ) ( )1

12

35 3

1 12 2

0 024

i

i

x

ii ix

hf x dx h f f O h h f O h+

++ +′′= + + + + = ⋅ +∫ .

Eigenschaften • Teilintegral ist mit 3. Ordnung genau in h. • Da im Gesamtintegral jedoch N~1/h fehlerbehaftete Summanden stehen, konver-

giert das Gesamtintegral nur in 2. Ordnung, mit dem verbleibenden Gesamtfehler des Rechteckverfahrens

• Gesamtfehler:

( )12

3 14

Rechteck024

N

ii

hE f O h−

+=

′′= + ∑ .

• Vorteile dieses Verfahrens sind, die sehr einfache Implementierung und der Fakt, dass keine Funktionswerte an den Intervallgrenzen berechnet werden müssen und dadurch keine Probleme mit eventuellen Singularitäten der zu integrierenden Funktion ( )f x an den Intervallgrenzen auftreten.

1.4.2 Trapezregel Bei dieser Methode werden die Teilintegrale durch Trapeze genähert, die den Verlauf der Funktion lokal besser darstellen können als Rechtecke. Die Näherung des Integrals schreibt sich dann als

( ) ( )11 1

01 1 1 2 1

0 0

12 2 2 2

i

i

xN NN

i i i i Ni ix

h b a f fA dx f f f f f f fN

+− −

+ + −= =

− ≈ + = + = + + + + + ∑ ∑∫


Trapezregel: Näherung des Gesamtintegrals durch mehrere Trapeze.

Fehlerbetrachtung für Teilintegral Durch Vergleich mit der Struktur der Rechteckregel, sieht man, dass bei der Trapezregel der Funktionswert im Intervallmittelpunkt folgendermaßen genähert wird

112 2

i i

i

f ff +

+

+≈

Die Fehlerberechnung erfolgt deshalb einfach durch Ersetzen von 12if + in der

Fehlerbetrachtung der Rechteckregel durch

( )1 12 2

2

41 22 2

i ii i

hf ff f O h+

+ +

+ ′′= − +

Somit ergibt sich als Fehlerabschätzung

( ) ( ) ( )1

12

35 3

1 12 2

0 012

i

i

x

ii ix

hf x dx h f f O h h f O h+

++ +′′= + + + + = ⋅ +∫

Eigenschaften • Sowohl Rechteck- als auch Trapezregel konvergieren in 2. Ordnung mit h. Die

gegenüber der Rechteckregel bessere Beschreibung des lokalen Funktionsverlaufes durch die Trapezregel zahlt sich bei der Integration nicht aus, da die Integration die erste Ableitung der Funktion nicht berücksichtigt.

• Der Fehler der Trapezregel ist sogar doppelt so groß wie bei der Rechteckregel. • Die Trapezregel lässt sich im Vergleich zur Rechteckregel aber sehr einfach rekursiv

von N auf 2N verfeinern, da die schon berechneten Stützstellen wieder benutzt werden können.

• Trapezregel besser rekursiv verfeinerbar ( 2N N→ Stützstellen)


1.4.3 Simpson-Regel Bisher hat die symmetrische Entwicklung um den Intervallmittelpunkt bereits zum Verschwinden der ungeraden Ableitungen geführt. Jetzt sollen weitere Fehlerterme eliminiert werden, um die Genauigkeit der Integralnäherung zu verbessern. Eine Möglichkeit ist das Simpson-Verfahren, bei welchem die zu integrierende Funktion in den Teilintervallen durch Parabeln approximiert wird.

( ) ( )1

1

352 0 0

3

i

i

x

i ix

hf x dx h f f O h+

−

′′= ⋅ + + + +∫ .

Diese Verbesserung wird durch das Approximieren der zweiten Ableitung mittels des diskreten Differentialoperators mit dem 3-Punkt-Stencil 2[1 2 1]/ h− erreicht.

( ) ( ) ( ) ( )1

1

35 51 1

1 1222 4

3 3

i

i

xi i i

i i i ix

h f f f hf x dx h f O h f f f O hh

+

−

− +− +

− + = ⋅ + + = + + + ∫ .

Die Summation über die Teilintervalle 1,3,5,..., 1i N= − (bei geradem N ) ergibt für das Gesamtintegral

[ ] ( )40 1 2 3 14 2 4 ... 4

3 N NhA f f f f f f O h−= + + + + + + + .

Eigenschaften Wir erhalten so ein Verfahren, das in 4. Ordnung konvergiert und damit für Polynome bis einschließlich 3. Grades exakt ist.

1.4.4 Bode-Regel Das Verfahren der Approximation durch Polynome lässt sich natürlich noch weiter verbessern, indem die zu integrierende Funktion ( )f x durch analytisch integrierbare Polynome immer höherer Ordnung genähert wird. Ein Beispiel dafür ist die sog. Bode-Regel, bei der der Mittelwert der zu integrierenden Funktion im Teilintervall auf der Basis eines Polynoms 5. Grades genähert wird

2 1 1 214 64 24 64 14( )45 45 45 45 45i i i i if x f f f f f− − + += + + + +

Damit konvergiert die Bode-Regel bei Verkleinerung des Stützstellenabstandes h mit 6. Ordnung gegen den exakten Integrationswert, wobei eine hinreichend glatte Funktion ( )f x vorausgesetzt) wird. Damit integriert die Bode-Regel Polynome bis zum 5. Grad exakt.

1.4.5 Intervallteilungsverfahren Eine Fehlerkontrolle für Standardverfahren, die auf der Zerlegung des Gesamt-integrationsintervalls in viele Teilintervalle und Näherung der Funktion in diesen kleinen Teilintervallen beruhen, lässt sich durch folgenden Algorithmus implemen-


tieren. Dabei basiert die Fehlerabschätzung auf der Annahme, dass die stärke der Abhängigkeit des Ergebnisses der numerischen Integration von der Intervallbreite h ein Maß dafür ist, wie stark das für ein endliches h berechnete numerische Ergebnis noch vom exakten Ergebnis ( 0h → ) abweicht. Ablauf: 1. Vorgabe einer Zielgenauigkeit ε 2. Wahl der Anzahl N der Teilintervalle aus einer physikalischen Vorbetrachtung

und Berechnung von NA

3. Halbieren der Intervallbreite 2h h→ bzw. Verdopplung der Intervallanzahl 2N N→ und Berechnung von 2NA

4. Schritt 3 solange wiederholen bis 2N NA A− < ε

Abbruchkriterium der Intervallteilung: Die Fehlerschranke wird aus der Differenz zweier aufeinanderfolgender Intervallteilungen abgeschätzt, da dies bei stetigem Konvergenzverhalten ein Maß für den Abstand zum exakten Ergebnis Aanalyt ist.

Beispielimplementierung für Integration mittels Standardverfahren Das folgende Codebeispiel zeigt eine einfache Implementierung der Trapezregel in MATLAB. Dabei soll die Integralberechnung auf Teilintervallen rekursiv wiederholt werden, so lange der geschätzte Fehler eine bestimmte Toleranz überschreitet. Für die Fehlerabschätzung wird ausgenutzt, dass die Simpson-Regel im Vergleich zur Trapez-Regel einen kleineren Fehler aufweist und die Differenz beider Fehler zur Abschätzung des absoluten Fehlers verwendet werden kann.

(Integrationsverfahren, Trapez- /Simpson-Regel) function [Int I]=trapez(f,I,tol) % [Integral Intervall] = trapez(@func_name,Intervall,toleranz) % berechnet das Integrals der uebergebenen Funktion f % in den Grenzen I(1) bis I(2) mittels Trapezregel und einer % Toleranz tol % Die Funktion gibt den berechneten Integralwert % und den Vektor der Gitterstruktur zurueck %Trapezregel Int = (I(2)-I(1))/2 * (feval(f,I(1)) + feval(f,I(2))); %Simpsonregel

AN

Aanalyt

N

ε


S = (I(2)-I(1))/6 * (feval(f,I(1)) + 4*feval(f,(I(2)+I(1))/2) + feval(f,I(2))); if(abs(Int-S)>=tol*(I(2)-I(1))) I = [I(1);(I(2)+I(1))/2;I(2)]; [Int1 I1] = trapez(f,I(1:2),tol); [Int2 I2] = trapez(f,I(2:3),tol); Int = Int1 + Int2; I = [I1;I2(2:end)]; end end

Die Implementierung des Integrationsalgorithmus erfolgte für eine beliebige zu integrierende Funktion ( )f x . Beispielhaft wollen wir das Integral der Sinus-Funktion

0

sin( )A x dxπ

= ∫

berechnen. Zur Betrachtung des numerischen Fehlers kann bei diesem Beispiel mit dem exakten analytischen Ergebnis der Integration analyt 2A = verglichen werden. Die zu integrierende Sinus-Funktion muss noch als allgemeine Integrationsfunktion für die Übergabe beim Funktionsaufruf implementiert werden.

(Definition des Integranden) 1 function y=f1(x) 2 % Trigonometrische-Funktion y=sin(x) 3 y=sin(x); 4 end

Nun können wir das Ergebnis berechnen und die Funktion inklusive der Stützstellen zeichnen lassen.

(Aufruf der Integrationsfunktion) 1 [Int I] = trapez(@f1,[0 pi],0.01); 2 Int 3 x=linspace(0,pi,100); 4 y=f1(x); 5 y2=f1(I); 6 plot(x,y,I,y2,'x')

Für 0.01ε = erhalten wir 1.9879A = , was bereits eine gute Abschätzung des exakten Ergebnisses analyt 2A = ist. Die Genauigkeit ließe sich durch Verkleinerung der Zieltoleranz weiter verbessern.


Die eigentliche Stärke von MATLAB liegt in einem umfangreichen Repertoire an bereits implementierten Funktionen. Das numerische Integrieren mit Hilfe der Trapezregel ließe sich in MATLAB deshalb viel schneller realisieren, indem z.B. die bereits in MATLAB vorhandene Integrationsfunktion trapz verwendet wird:

(Trapezregel als MATLAB-Funktion) 1 X = 0:pi/100:pi; 2 Y = sin(X); 3 Z = trapz(X,Y) %liefert Z = 1.9998

1.4.6 Gauss-Quadratur Es besteht weiterhin das Ziel der möglichst genauen Näherung des Integrals mit so wenig wie möglich Funktionsberechnungen ( )f x , da häufig die Berechnung der zu integrierenden Funktion selber den größten Teil des Rechenaufwandes darstellt. In den bisher diskutierten Standardverfahren wurde dafür das Integrationsintervall [ , ]a b in viele Teilintervalle 1[ , ]i i iI x x += zerlegt, in denen die zu integrierende Funktion mit Polynomen relativ niedriger Ordnung genähert wurde. Jetzt wollen wir diese Idee modifizieren und die Funktion ( )f x im gesamten Integrationsintervall [ , ]a b durch eine analytisch integrierbare Funktion hoher Ordnung näheren, z.B. mit Hilfe einer orthogonalen Basis iP (Legendre o.Ä.). Obwohl dies prinzipiell zu einer sehr hohen Genauigkeitsordnung führen kann, ist Vorsicht geboten. „Hohe Ordnung“ bedeutet nur dann „hohe Genauigkeit“, wenn die zu integrierende Funktion ( )f x hinreichend glatt ist, im Sinne einer guten Approximierbarkeit durch ein Polynom. Diesem Ansatz folgend wird eine Funktion ( )f x nun durch einen Satz von Polynomen ausgedrückt

0( ) ( )

n

i ii

f x P x=

≈ α∑ mit n „klein“ wenig Basiselemente

Die Bestimmung der Koeffizienten iα folgt aus der der Orthogonalität der Basis-polynome iP

( ) ( )b

i j ija

dx P x P x = δ∫ .

Daraus lässt sich ein lineares Gleichungssystem für die Koeffizienten iα ableiten, dessen Lösung häufig die wesentliche numerische Aufgabe darstellt. Die Näherung des zu berechnenden Integrals ergibt sich dann zu

1( ) ( )

b bn

i iia a

dx f x dx P x=

≈ α∑∫ ∫


Für einige Basispolynome, wie z.B. Legendre-Polynome, kann die Berechnung der Koeffizienten iα und die Integration analytisch aufgelöst werden. Damit ergibt sich dann eine sehr einfache Rechenvorschrift

1( ) ( )

b n

i iia

dx f x w f x=

≈ ∑∫

mit iw als den für einen jeweiligen Polynomtyp zu bestimmenden Gewichts-koeffizienten.

Eigenschaften Der Näherungsfehler ist klein, wenn ( )f x gut in gewählte Basis iP entwickelbar ist. Die Abschätzung des verbleibenden Fehlers ist allgemein nur schwer möglich. Die bekannteste Gauß-Quadratur ist die Gauß-Legendre-Integration auf dem Intervall [ 1;1]− durch Legendre-Polynome. Um das Verfahren auf beliebige Intervalle [ ; ]a b anzuwenden ist lediglich eine Variablentransformation vorzunehmen.

Integration mit Trapezregel Führen Sie eine numerische Integration nach der Trapez-Regel für die Funktion

0

sin( ) 2A x dxπ

= =∫

von Hand (mit Taschenrechner) für 4 bzw. 8 Teilintervalle durch.

Integration mit Simpson-Regel Schreiben Sie ein Programm (Funktion), um die Simpson-Regel in MATLAB zu implementieren. Nutzen Sie dabei die im obigen Codebeispiel gezeigte Funktion f1 (function y = f1(x)) und testen Sie Ihr Programm durch die Integration der in der vorherigen Aufgabe genannten Funktion.

1.5 Nullstellen und Extrema in Englisch-sprachiger Literatur: Nullstellensuche = Root Finding

1.5.1 Nullstellen von Funktionen einer Veränderlichen Die Aufgabe ist das Finden von Nullstellen von ( )f x in einem Intervall [ ],a b . Die nachstehenden Abbildungen verdeutlichen dabei einige Situationen, die bei der Suche nach solchen Nullstellen auftreten können. Die Wahl eines speziellen Ver-fahrens zur Suche nach Nullstellen richtet sich oft nach den Eigenschaften der betrachteten Funktion ( )f x . Viele computergestützte Lösungsansätze beruhen auf Iterationsverfahren, die einen Startpunkt ix in der Nähe einer Nullstelle mehrfach nach 1ix + verbessern bis ein *x gefunden wurde für welches ( )*f x < ε . Gleichermaßen existieren auch viele Verfahren, die ausgehend vom Suchintervall [ ],

ia b , in dem sich die Nullstelle


befindet, dieses Intervall iterativ nach [ ] 1,

ia b

+ verkleinern, bis das Intervall [ ]*

,a b die Nullstelle hinreichend genau eingrenzt. Während bei der ersten Art von Verfahren geprüft wird, wie gut die Zielbedingung ( ) 0f x = erfüllt wird, spielt dies bei der zweiten Verfahrensart keine Rolle. Stattdessen wird ausgewertet, wie genau die Position der Nullstelle bestimmt wurde.

Eine isolierte Nullstelle im Intervall [a,b] ist durch den Vorzeichenwechsel der Funktionswerte f(a) und f(b) an den die Nullstelle eingrenzenden Intervallgrenzen a und b gekennzeichnet.

Es können bei gleichem Vorzeichen der Funktionswerte an den Intervallgrenzen dennoch z.B. doppelte Nullstellen im Intervall existieren.


Bei Vorzeichenwechsel der Funktionswerte an den Intervallgrenzen muss nicht zwingend eine Nullstelle existieren falls die Funktion f(x) im Intervall [a,b] Unstetigkeiten aufweist.

Diese Funktion zeigt, dass eine große Anzahl Nullstellen in einem Suchintervall existieren kann.

1.5.1.1 Bisektion Bei der Bisektion wird das Intervall [ ],

ia b , welches anfänglich bereits genau eine

Nullstelle einschließt, halbiert. Dann wird untersucht, welches der resultierenden Teilintervalle weiterhin die Nullstelle einschließt und dieses wiederum halbiert, usw. bis die Intervallgrenzen [ ]*

,a b , welche die Nullstelle einschließen, hinreichend identisch sind. Für die Feststellung der Existenz der Nullstelle in einem Teilintervall muss nur das Vorzeichen von ( )f x untersucht werden und nicht der Wert von ( )f x . Das kann bzgl. des Rechenaufwandes von großem Vorteil sein. Das Verfahren konvergiert zwar langsam aber dafür mit hoher Sicherheit, d.h. in jedem Iterationsschritt wird unabhängig von den Eigenschaften der Funktion ( )f x eine vorhersagbare Verbesserung erzielt. Das nachstehende Struktogramm verdeutlicht noch einmal das Verfahren der Bisektion.


Schematischer Ablauf des Bisektionsverfahrens unter der Annahme, dass für das Startintervall ( ) 0 ( ) 0f a f b> < gilt. Hinweis 1: Die Implementierung beruht auf einem rekursiven Funktionsaufruf. Hinweis 2: Die hier gewählte Abbruchbedingung wertet die Qualität der Nullstelle mit dem Kriterium *(x )f ε< aus.

1.5.1.2 Sekantenverfahren Während das bereitsbetrachtete Bisektionsverfahren nur den Mittelpunkt im jeweiligen Suchintervall als nächsten Iterationspunkt verwendet und deshalb bei der Wahl des neuen Suchpunktes nicht die Eigeschaften von ( )f x im Suchintervall auswertet, wird nun der Verlauf der Funktion ( )f x linear genährt. Für dieses so genannte Sekantenverfahren wird mit den zwei Funktionswerten 1( )if x − und ( )if x eine Sekante konstruiert. Die Extrapolations- oder Interpolationslinie ergibt dann einen Schnittpunkt 1ix + mit der x-Achse, der den älteren der beiden Startwerte ( 1ix − ) ersetzt. Für die Argumente der Funktion ergibt sich folgende Iterationsformel

11

1

( )( ) ( )

i ii i i

i i

x xx x f xf x f x

−+

−

−= −

−.


Illustration des Sekantenverfahrens. Die einzelnen Punkte sind in der Reihenfolge ihrer Benutzung für die iterative Verbesserung des Suchintervalls nummeriert.

Eigenschaften • Das Sekantenverfahren konvergiert schneller gegen eine Nullstelle in der Nähe von

zwei Startpunkten bzw. innerhalb des Startintervalls als das Bisektionsverfahren, falls sich die Funktion ( )f x im Suchintervall jinreichend gut linear näheren lässt. Für lineare Funktionen wird die Nullstelle sogar in einem Iterationsschritt gefunden.

• Die Konvergenz des Sekantenverfahrens ist jedoch nicht sicher, da nicht in jedem Iterationsschritt zwangsläufig eine Verbesserung der Annäherung an die Nullstelle erzielt wird.

• Das Intervall 1[ , ]i ix x + schließt nicht in jedem Iterationsschritt des Verfahrens die Nullstelle ein.

• Da bei diesem Verfahren der Nenner zwangsläufig klein wird und gegen Null konvergiert, ist es sinnvoll eine zusätzliche Abbruchbedingung einzuführen (Dabei ist ε die relative Maschinengenauigkeit):

• konvergiert schneller als Bisektionsverfahren (lineare Funktionen: 1 Schritt) • nicht jeder Iteration Verbesserung unsichere Konvergenz • Intervall 1[ , ]i ix x + schließt nicht unbedingt Nullstelle ein

( ) ( ) ( )1 10i i if x f x f x−− ≤ ε

Sekantenverfahren

1 function [x,i,status] = sekante(x0,x1,tol1,tol2,no) 2 %x0,x1: Startwerte 3 %tol1: Toleranz fuer Funktionswert 4 %tol2: Toleranz für Funktionsargument


5 %no: maxiamle Anzahl an Iterationen 6 7 %graphische Ausgabe 8 ab = -0.4; x_old=1000;fx_old=1000; 9 axis on; 10 plot( [-5 5], [0 0]); % x-Achse zeichnen 11 hold on; 12 set(findobj(gca,'Type','line','Color',[0 0 1]),'Color', 'black','LineWidth',1) 13 p=(-5):0.1:(5); 14 for i=1:1:(101) 15 f(i) = f1(p(i)); 16 end 17 plot(p,f,'LineWidth',1); 18 i = 0; fa = f1(x0); fb = f1(x1); 19 if abs(fa) > abs(fb) 20 a = x0; b = x1; 21 else 22 a = x1; b = x0; tmp = fb; fb = fa; fa = tmp; 23 end 24 % Iteration der Sekante 25 while i < no 26 s=fb/fa; r=1-s; 27 t=s*(a-b); % Anstieg zwischen den zwei Punkten der Sekanten 28 x=b-t/r; % konvergiert gegen Nullstelle 29 fx=f1(x); % konvergiert gegen Null 30 % Ausgabe der Punkte der Sekante 31 if abs(x_old-x)<0.3 && abs(fx_old-fx)<0.3 32 ab=ab-0.2; 33 end 34 x_old=x; fx_old=fx; 35 plot(x,fx,'rO','LineWidth',1); 36 text(x+ab, fx,num2str(i+1),'HorizontalAlignment','left') 37 if t == 0 38 status = 'Verfahren wurde nicht durchgefuehrt.'; return 39 end 40 if abs(fx) < tol1 41 status = 'Verfahren konvergiert, Loesung berechnet.'; return 42 end 43 if abs(x-b) < tol2*(1+abs(x)) 44 status = 'Verfahren konvergiert, Loesung berechnet.'; return 45 end 46 i = i+1; 47 if abs(fx) > abs(fb) 48 a = x; fa = fx; 49 else


50 a = b; fa = fb; b = x; fb = fx; 51 end 52 end 53 status = 'Iterationszahl ueberschritten';

1.5.1.3 Regula Falsi (False Position Method) Die bisherigen Verfahren zeigten entweder eine sehr langsame Konvergenz (Bisektion) oder keine sichere Konvergenz (Sekantenverfahren). Die Regula Falsi erweitert das Sekantenverfahren um die zusätzliche Bedingung, dass die neue Sekante nur durch die beiden letzten Iterationspunkte gezogen wird, welche die Nullstelle einschließen. Damit wird auch für sogenannte nicht kooperative Funktionen ( )f x eine sicherere Konvergenz erzwungen. Konkret bedeutet dies die Unterscheidung in zwei Fälle. Fall A:

1 1( ) ( ) 0 ,i i i if x f x x x+ +< ⇒

In diesem Fall werden der neue und der letzte Iterationspunkt weiterverwendet. Fall B:

1 1 1 1( ) ( ) 0 ,i i i if x f x x x+ − + −< ⇒

Oder es werden im anderen Fall der neue und der vorletzte Iterationspunkt weiterverwendet, da nur diese Punkte die Nullstelle weiterhin einschließen.

Regula-Falsi (False Position Method): Die nächsten Iterationspunkte müssen dabei stets die Nullstelle einschließen.


Eigenschaften • Durch die Einführung der Zusatzbedingung konvergiert das Verfahren gegenüber

dem Sekantenverfahren manchmal langsamer. • Die Zusatzbedingung verhindert jedoch das Abdriften der Iterationspunkte von der

Nullstelle und es wird allgemeine Konvergenz erzielt, d.h. unabhängig vom Verlauf der Funktion ( )f x wird in jedem Iterationsschritt eine Verbesserung der Nullstellenabschätzung erzielt.

Weitere Ergänzungen zur Fehlerbetrachtung des Verfahrens stehen im Anhang. Bevor wir zu einem weiteren Verfahren kommen, soll die nachstehende Abbildung noch einmal verdeutlichen, dass sowohl das Sekantenverfahren als auch die Regula-Falsi nur bedingt geeignet sind, um eine Nullstelle schnell zu finden.

In diesem Beispiel würden sowohl mit dem Sekantenverfahren als auch mit der Regula Falsi viele Iterationen zum Finden der echten Nullstelle benötigt. Auch viele andere Verfahren ergeben hier keine Verbesserung.

1.5.1.4 Newton-Raphson-Verfahren Wenn von einer Funktion ( )f x neben den Funktionswerten auch die Ableitung der Funktion bekannt ist, dann sollte diese für die Nullstellensuche mit ausgewertet werden. Bei Newton-Raphson-Verfahren wird ( )f x durch eine Taylorentwicklung genähert (meist nur in erster Ordnung - linear), wofür die Ableitung ( )f x′ bekannt sein muss. Dann gilt

( )!

1 1( ) ( ) ( ) 0i i i i if x f x x x f x+ + ′≈ + − =

Durch Auflösen nach 1ix + kann daraus die folgende Iterationsformel abgeleitet werden:

2


1( )( )

ii i

i

f xx xf x+ ≈ −′

Eigenschaften • quadratische Konvergenz mit folgender Fehlerentwicklung

21

( )2 ( )

ii i

i

f xE Ef x+

′′≈

′⋅

in jedem Schritt Verdopplung der korrekten Stellen erreicht sehr schnell Maschinengenauigkeit

• funktioniert nur sicher in der Nähe von Nullstellen (sobald ( )f x hinreichend gut als lineare Funktion genähert werden kann)

• gut auf mehrere Dimensionen verallgemeinerbar • kombinierbar mit Sekantenverfahren/Regula-Falsi: erst Regula-Falsi bis in Nähe der

Nullstelle (da allgemeine Konvergenz), dann Newton Rapson (da schnell zur Maschinengenauigkeit)

Bisektionsverfahren Implementieren Sie das Bisektionsverfahren in MATLAB. Nutzen Sie dazu das obige Struktogramm.

Struktogramm der Simpson-Regel Wie könnte ein Struktogramm der Regula Falsi aussehen?

1.5.2 Extrema von Funktionen einer Veränderlichen Da das Auffinden von Nullstellen häufig aufwendig ist und numerisch sowieso nie zu einer exakten Lösung mit *( ) 0f x = führt, wird diese Aufgabenstellung oft in ein Minimierungsproblem umgewandelt. Dabei wird ausgenutzt, dass für eine Nullstelle das Quadrat der untersuchten Funktion auch ein Minimum hat. Auch unabhängig von Nullstellenproblemen stellt das Auffinden des Minimums einer Funktion eine häufig zu lösende Aufgabe dar. Deswegen werden wir nun Algorithmen untersuchen, um Minima effizient zu lokalisieren. Damit ist auch die Frage nach eventuellen Maxima beantwortet, da diese Minima des Reziproken der zu maximierenden Funktion sind. Damit ein Minimum im Intervall [ , ]a c existiert, muss für eine im Intervall [ , ]a c stetige, nach unten beschränkte Funktion ( )f x Folgendes gelten: Wenn für ein Punktetripel a<b<c (oder c<b<a) ( ) ( )f b f a< und ( ) ( )f b f c< gilt, so folgt daraus die Existenz eines Minimums im Intervall [ , ]a c .


1.5.2.1 Verfahren des goldenen Schnitts (Golden Section Search) In Analogie zum Bisektionsverfahren besteht die Aufgabe darin, einen neuen "verbesserten" Punkt d innerhalb [ , ]a c zu wählen. Dieser Punkt d liegt entweder im Teilintervall [ , ]a b oder im Teilintervall [ , ]b c . Um unabhängig von der konkreten Funktion ( )f x eine möglichst gut Verbesserung der Annäherung an das Minimum zu erzielen, wählt man den neuen Punkt d innerhalb des größeren der beiden Teilintervalle [ , ]a b und [ , ]b c . Danach bestimmt man die Funktionswerte ( )f b und (d)f . Für den Fall ( ) ( )f b f d< ist das nächste Punktetripel ( , , )a b d . Für den alternativen Fall ( ) ( )f b f d> wählt man das Tripel ( , , )b d c für die nächste Iteration. Der Mittelpunkt des Tripels ist dann der Abszisse am nächsten und ist bis dahin das Minimum. Diesen Schritt der Einschachtelung des Minimums wiederholt man solange, bis die Intervallbreite eine bestimmte Toleranz unterschreitet.

Mögliche Fälle der Eingrenzung eines Minimums nach der Intervallteilung.

Wie sollte nun die Intervallteilung erfolgen, damit unabhängig vom Verlauf der Funktion ( )f d eine optimale Konvergenz zum Minimum erfolgt? Diese Frage ist gleichbedeutend mit der Forderung, dass die neue Intervallgröße unabhängig vom Erfolgsfall der Teilung sein soll, d.h. das neues Intervall soll in jedem Fall gleich groß sein.

1 3 2∆ + ∆ = ∆ oder d a c b− = −

Festlegung des neuen Punktes durch d c b a= − +

Gleichzeitig soll im gesamten Iterationsverlauf die Reduktion des Suchintervalls gleich bleiben. D.h. die Verbesserung, die in jedem einzelnen Iterationsschritt erzielt wird, soll konstant sein.

f(x)

x

f(a)

f(c)

f(b)

a b c d

fB(d)

fA(d)

∆3 ∆2 ∆1


Lösungsansatz Verhältnis der Teilintervalllängen ( 1 2/∆ ∆ ) soll bei aufeinander folgenden Iterations-schritten konstant bleiben Verkleinerung des Suchintervalls mit konstanter Rate Fall A ( )f d : neues Tripel ist ( , , )a b d

dann soll ( ) ( )1 2 3 1/ /∆ ∆ = ∆ ∆ sein

Fall B( )f d : neues Tripel ist ( , , )b d c

dann soll ( ) ( )1 2 3 2 3/ / ( )∆ ∆ = ∆ ∆ − ∆ sein

Durch Elimination von 3∆ aus beiden Gleichungen folgt:

( )22 1 2 1/ ( / ) 1∆ ∆ = ∆ ∆ +

mit der Lösung:

( )2 1/ (1 5) / 2 1.618033989...∆ ∆ = + =

Dieses Verhältnis entspricht dem goldenen Schnitt und ist die gesuchte Bedingung für die Position von b .

1.5.2.2 Quadratische Interpolation (Parabolic Interpolation) Die Methode des Goldenen Schnittes ist in ihrer Art speziell für den „worst case“, der beim Suchen des Minimums auftreten kann, ausgelegt, d.h. für ein sog. „unkoopera-tives“ Minimum. Befindet man sich jedoch bereits in der Nähe eines Extremums, kann man die Funktion meist hinreichend gut durch eine parabolische Funktion nähern? Die Methode der quadratischen Interpolation legt durch ein gegebenes Punktetripel eine Parabel und wählt den neuen Punkt x nahe des Scheitels. Diese Methode ist für geeignete Funktionen sehr effizient. Für die Wahl des neuen Iterationspunktes x ergibt sich folgender Zusammenhang:

( ) ( ) ( ) ( ) ( ) ( )( ) ( ) ( ) ( ) ( ) ( )

2 212

b a f b f c b c f b f ax b

b a f b f c b c f b f a− − − − − = +− − − − −

x ist dabei der Scheitelpunkt der Parabel durch die dreit Punkte ( , ( ))a f a , ( , ( ))b f b und ( , ( ))c f c . Mit dem kleinsten Intervall, das drei Punkte umfasst und ein Minimum einschließt wird dieser Vorgang so oft wiederholt bis die gewünschte Genauigkeit erreicht ist. Folgende Abbildung soll die Methode noch einmal verdeutlichen.


Das Minimum wird bei dieser Methode durch Interpolation von Parabeln gesucht. Durch drei Punkte 1,2,3 der gegebenen Funktion (durchgezogene Linie) wird eine Parabel gelegt (gestrichelte Linie). Deren Scheitelpunkt führt zum neuen Punkt 4 der gegebenen Funktion. Das neue Punktetripel wird als kleinstes mögliches Intervall ausgewählt, welches ein Minimum einschließt. D.h. im nächsten Iterationsschritt wird durch die Punkte 1,2,4 eine Parabel gelegt (gepunktet) usw. So ist der Scheitelpunkt 5 der zweiten Parabel schon sehr nahe am gesuchten Minimum der Funktion.

1.5.3 Minima von Funktionen mehrerer Veränderlicher Echte Nullstellensuche ist in höheren Dimensionen meist extrem schwierig, da nicht eindeutig bestimmbar ist, ob eine isolierte Nullstelle im Suchbereich überhaupt existiert oder ob stattdessen eine Lösungsmanigfaltigkeit vorliegt. Die Lösung einer korrespondierenden Minimierungsaufgabe ist aber meist möglich. Die Minimierungs-verfahren aus dem letzten Abschnitt werden wir deshalb auf mehrdimensionale Funktionen erweitern.

1.5.3.1 Downhill-Simplex-Methode Die Downhill-Simplex-Methode ist ein auf Minima spezialisierter Suchalgorithmus für einen Simplex. Ein Simplex ist eine n-dimensionale Punktemenge aus n+1 Punkten, wobei die Verbindungslinien zwischen den Punkten allesamt linear unabhängig sind und diese deshalb den gesamten Raum aufspannen. Im Eindimensionalen ist dies eine Strecke, im Zweidimensionalen ein Dreieck, im Dreidimensionalen ein Tetraeder usw..


Wandern durch Spiegelung

Expansion/Kontraktion

S

P

P

Graphische Darstellung der Simplexoperationen am Beispiel eines 2D Simplex.

Das Verfahren sieht in der Implementierung nach Nelder und Mead folgendermaßen aus: 1. Wähle aus einer physikalischen Vorbetrachtung geeignete Ausgangspunkte, die

einen Simplex aufspannen und bestimme deren Funktionswerte. 2. Suche den ‚besten’ Punkt B und ‚schlechtesten’ Punkt S (kleinster/ größter

Funktionswert). 3. Der ‚schlechteste’ Punkt S wird nun um den Simplexmittelpunkt gespiegelt,

woraus sich ein neuer Eckpunkt P des Simplex ergibt. Danach verfahre wie folgt:

3.a Wenn der neue Punkt P besser als alle bisherigen Punkte des Simplex ist, dann strecke den Simplex in dieser Richtung und ersetze den Punkt S durch den neuen gestreckten Punkt P.

3.b Ist der Punkt P nur ‚besser’ als Punkt S, dann ersetze Punkt S durch Punkt P. 3.c Ist der Punkt P ‚schlechter’ als Punkt S, dann kontrahiere den Simplex unter

Beibehaltung der anderen Punkte. 4. Wiederhole die Schritte 2 und 3 bis das Simplexvolumen hinreichend klein ist.

Typische Modifikationen zur Verbesserung der Konvergenz Je nach Problemstellung ist es noch möglich, die Punkte unabhängig von den oben genannten Implementierungsschritten immer etwas stochastisch zu verändern, um ein Festfahren des Simplex zu verhindern.

1.5.3.2 Minimierung in alternierende Richtungen Eine andere Minimierungsmethode greift direkt auf die bereits im vergangenen Abschnitt vorgestellten Konzepte für die eindimensionale Minimierung zurück. Bei der Minimierung in alternierende Richtungen werden für eine N -dimensionale Funktion 1 2( , ,..., )Nf x x x aufeinanderfolgend N eindimensionale Minimierungsauf-gaben in N verschiedene Richtungen gelöst.


Für einen aus einer physikalischen Vorbetrachtung gegebenen Startpunkt 1P

und eine Richtung 1u

1 1,P u

wird folgendermaßen vorgegangen

( )( )( )( )

( )( )

1 1 1 2 1 1 1

2 2 2 3 2 2 2

1

min

min

min N N N N N N

f P u P P u

f P u P P u

f P u P P u

+ λ = + λ

+ λ = + λ

+ λ = + λ

Das Verfahren wird so lange ausgeführt, bis in alle Richtungen keine wesentliche Verbesserung mehr zu erzielen ist. Die Wahl der Minimierungsrichtungen beeinflusst wesentlich die Effizienz des Verfahrens. Die einfachste Wahl für die Minimierungsrichtungen sind die Koordinatenachsen, allerdings ist dies meistens nicht die effektivste Variante.

x

y gute Konvergenz schlechte Konvergenz

Gebiete mit guter und schlechter Konvergenz der Minimierung in alternierende Richtungen, wenn dafür einfach die Koordinatenachsen als Richtungsvektoren gewählt werden.

Methoden zur Richtungsfestlegung werden im Wesentlichen danach unterschieden, ob sie die Kenntnis der Ableitung der zu minimierenden Funktion in die Richtungs-festlegung einbeziehen oder nicht. Um das gesamte Minimierungsproblem durch die nacheinanderfolgende Minimierung in möglichst wenige verschiedene Richtungen zu lösen, ist es das Ziel der Richtungswahl, möglichst sog. „konjugierte“ Richtungen zu finden. Diese konjugierten Richtungen sollen die Eigenschaft besitzen, dass die Minimierung in iu durch die nachfolgende Minimierung in Richtung 1iu +

nicht beeinträchtigt wird, d.h. dass nach der Minimierung in die Richtung 1iu +

man auch entlang iu noch im Minimum sitzt und nicht in die vorherige Richtung iu noch einmal "nachminimieren" muss.


A) Gradientenverfahren (Steepest Descent) Eine Methode zur effektiven Richtungswahl, bei welcher die Ableitungsbildung einbezogen wird, ist das Verfahren des steilsten Abstieges, das auch als Gradienten-verfahren bekannt ist. Die Idee ist, dass die Suchrichtung entgegen der des Gradienten steht, d.h.

( )1i i iiP P f P+ = − λ ∇

mit ( )( )( )min i ii tf P t f P

∈λ = − ∇

Eigenschaften Das Problem der Methode des steilsten Abstieges ist es, dass das Verfahren in sehr "schmalen Tälern" dazu neigt, sich dem Minimum in einem Zick-Zack-Kurs zu nähern. Die Ursache liegt darin, dass der neue Minimierungspfad immer gegen den Gradienten in einem konkreten Punkt steht und deshalb senkrecht zur vorherigen Richtung ist. Diese Richtung muss jedoch nicht notwendigerweise direkt zum gesuchten Minimum führen. Zudem ist der Gradient in der Nähe eines lokalen Minimums numerisch nur schwer zu bestimmen.

„Gutes“ und „schlechtes“ Beispiel für die Anwendung des Gradientenverfahrens zur Suche des Minimums einer zweidimensionalen Funktion.

Was sind konjugierte Richtungen? Wir wollen nun versuchen eine Methode abzuleiten, mit der wir die gesuchten konjugierten Richtungen bestimmen können. Dafür müssen wir uns zuerst über die mathematische Definition konjugierter Richtungen verständigen. Wir untersuchen deshalb, wie sich ein Minimierungsschritt auf das Ergebnis des vorherigen Minimierungsschrittes auswirkt. • zuerst Minimieren entlang u bis zum Punkt p

• danach steht Gradient senkrecht auf u • nun Taylor-Entwicklung nach x um Ursprung p


( ) ( )2

12

,

1 ( ) ( )2i i j

i i ji i jp p

f ff x f p x x x c b p x xÂ p xx x x

∂ ∂= + + + ≈ + +

∂ ∂ ∂∑ ∑

mit ( ), ( )p

c f p b p f= = ∇

(Gradient am Punkt p )

und 2

( )ij

i j p

fÂ px x∂ = ∂ ∂

(Hesssematrix am Punkt p )

• mit dieser Näherung Berechnung der Ortsabhängigkeit des Gradienten von f

( )f x Âx b∇ = +

• Veränderung des Gradienten bei Verschiebung um xδ

: ( ) ( )f Â xδ ∇ = δ

Resultierendes Vorgehen zur Bestimmung der konjugierten Richtung: • zuerst Minimierung entlang iu

• danach Minimierung entlang 1iu +

, wobei 1iu +

aus folgender Bedingung bestimmt wird:

− konjugiert wenn Gradient senkrecht zu iu bleibt

( ) 10 i i iu f u Âu += δ ∇ =

− d.h. es muss die Hessematrix am Punkt p berechnet werden und danach das obige lineare Gleichungssystems zur Bestimmung von 1iu +

gelöst werden.

Eigenschaften der resultierenden Methode • Wahl von N linear unabhängigen paarweise konjugierten Minimierungsrichtungen

( N Dimensionen) • dadurch erfolgt für quadratische Funktion Minimierung in N Schritten • quadratische Konvergenz: mit jedem Schritt doppelte Anzahl richtiger Stellen • jedoch komplizierte und auf Ableitungsbildung beruhende Bestimmung der

Richtungen

B) Powell’s Methode Wenn das Bilden von Ableitungen vermieden werden soll, bietet sich Powell’s Methode an. Diese erzeugt paarweise zueinander konjugierte Richtungen ohne Ableitungsbildung. Dazu wird die folgende Abfolge von Einzelschritten hinreichend oft durchlaufen, wobei anfänglich die Suchrichtungen einfach entlang der Koordinatenachsen gewählt werden können, wenn nicht aus einer physikalischen Vorbetrachtung geeignetere Suchrichtungen bekannt sind.

Methodezur Erzeugung paarweise konjugierter Richtungen 1. Startpunkt 0p

2. für 1, ,i N= Verschiebung von 1ip −

zum Minimum entlang iu bis Punkt ip


3. für 1, , 1i N= − setze 1i iu u +⇐ und 0N Nu p p⇐ −

(mittlere Richtung)

4. Verschiebe Np zum Minimum entlang Nu und 0 1Np p += , danach Neustart bei

Schritt 1.

Eigenschaften • ( )1N N + Iterationen notwendig für die Minimierung einer quadratischen Form

• Problem: Richtungen iu werden linear abhängig nur Teilraum von N wird minimiert Verbesserung der Konvergenz:

− z.B. nach N -maligem Ausführen der obigen Schritte (1,2,3,4) Rückkehr zu Einheitsvektoren ie

− oder noch besser: ersetze in Schritt (3) die Richtung mit dem stärksten Anstieg, da diese schon voll minimiert ist

Bemerkung In der Praxis ist häufig die sog. „Konjugierte-Gradienten-Methode“ die Methode der Wahl (siehe Literatur, z.B. Numerical Recipes).

1.6 Interpolation Um aus Messungen gewonnene Daten physikalisch interpretieren zu können, ist es meistens notwendig die Messwerte zu interpolieren bzw. zu extrapolieren. Im Folgenden werden dafür geeignete Verfahren vorgestellt, sodass der Funktions-verlauf möglichst nahe an den Messwerten liegt. Hier wird sich auf Interpolationsverfahren konzentriert. Die Extrapolation auf Argumentenbereiche außerhalb des bekannten Intervalls kann meist nicht durch allgemeingültige Methoden erfolgen, sondern sollte stark durch das Wissen um das generelle Verhalten des physikalischen Problems geprägt sein. Beispielweise könnte aus der Physik der Aufgabenstellung bekannt sein, mit welcher Potenz eine Größe sich bei der Annäherung an einen Grenzwert verändert.

1.6.1 Interpolationsformel von Lagrange (teilweise auch als Laplace’sche Interpolationsformel bezeichnet) Bei der Lagrange-Interpolation geht man von n bekannten Funktionswerten ( )if x an den sog. Stützstellen 1,..., nx x aus

( ) ( ) ( ) 1 1 1 2 2 2, ( ) , , ( ) , , , ( )n n nx y f x x y f x x y f x= = =

die durch das Polynom ( )P x von Grad ( 1)n≤ − verbunden werden sollen ges.: Polynom vom Grade ( 1)n≤ − , welches alle Punkte verbindet

( ) ( )1

10

nj

n jj

y x P x A x−

−=

= = ∑


Zur Bestimmung der Koeffizienten jA wählt man ein einfaches Vorgehen • Multiplikation von Wert jy mit Polynom ( )1n − ten Grades

( ) ( )( ) ( )( ) ( ) ( )1 2 1 1... ...j j j n kk j

p x x x x x x x x x x x x x− +≠

= − − − − − = −∏

• teilen durch ( )j jp x

man erhält ( )( ) 1

0 mitnkj k

j jj jk j kj j

k j

x k jp x x xy yy x xx xp x =

≠

∀ ≠−= = =−

∏

damit ist ( )11 1

nnk

n jj k j k

k j

x xP x yx x−

= =≠

−= −

∑ ∏ das Polynom, welches die Interpolationsauf-

gabe löst, da

( )1 1

( )n n

j k j jk k jk k

P x P x y y= =

= = δ =∑ ∑

Eigenschaften Da mit dem Grad des Polynoms auch die Anzahl der Maxima und Minima des Poly-nomverlaufs steigt (ein Polynom n-ten Grades hat bis zu n-1 Extrema), neigt die Interpolationsfunktion zum „Schlängeln“. Zusätzlich ergeben sich numerische Probleme bei der Polynombestimmung für hohe Stützstellenzahlen (ca. ab >100), da dann die numerische Produktberechnung instabil wird. Hier bietet sich eine Interpolation in Teilintervallen an (siehe Spline-Inter-polation im nächsten Kapitel). Der Fehler der Interpolation innerhalb des Interpolationsintervalls (d.h. die Ab-weichung des Polynoms von der eigentlichen, die Stützstellen verbindenden Originalfunktion) hängt im Wesentlichen von der Wahl der Lage der Stützstellen ab. Für äquidistante Stützstellen ist dieser Fehler an den Intervallrändern tendenziell besonders groß. Dies kann durch eine optimierte Stützstellenwahl umgangen werden, wenn z.B. als Stützstellen die Nullstellen des Tschebyscheff-Polynoms gewählt werden. Außerhalb des Interpolationsintervalls verhält sich die Interpolationsfunktion wie ein Polynom n-ten Grades und ist daher für eine Extrapolation meist nicht geeignet.


Bemerkung Das Tschebyscheff-Polynom ist Lösung der Differentialgleichung

( )2 21 0x y xy n y′′ ′− − + =

Für ganzzahlige n ergeben sich als Lösungen Polynome, deren Nullstellen durch

( )2 1cos 0, 1

2j

j nn

+ π = −

beschrieben werden.

1.6.2 Die Spline-Interpolation Die Lagrange-Interpolation hatte zum Einen starke Oszillationen, zum Anderen ist sie instabil bei der Bestimmung großer Produkte. Ein besseres und weit verbreitetes Verfahren ist die Spline-Interpolation, bei der die Funktion nur in jeweils kleinen Teilintervallen interpoliert wird. Dabei werden die verschiedenen Interpolanten hinreichend glatt aneinandergesetzt und Polynome geringeren Grades genutzt.


Es wird ein Polynom gesucht, welches durch alle mit roten Kreisen gekennzeichneten Punkte geht. Die Lagrange-Interpolation (blauer Plot) mit ihren Extremwerten (blaue Punkte) weicht dabei von der Spline-Interpolation (grüner Plot) stark ab. (Ein Kodeschnipsel zur Lagrange-Interpolation und diesem Plot findet man im Anhang)

Bemerkung Spline: (aus Schiffsbau) biegsame Holzlatte durch alle Punkte legen und deren Spannung minimieren Lösung eines Variationsproblems z.B. minimieren von

[ ( )]²dx s x′′∫

Die gebräuchlichsten Splines sind kubische, d.h. Polynome dritten Grades. Ansatz: Der Spline

( )js x mit 1,j jx x x + ∈

soll zweimal stetig differenzierbar sein. Daraus ergeben sich an den Intervallgrenzen folgende Bedingungen

− ( )j j js x y= - stetiger Anschluss an vorhergehenden Spline

− ( )1 1j j js x y+ += - stetiger Anschluss an nachfolgenden Spline

− ( ) ( )1' 'j j j js x s x−= - Stetigkeit der 1. Ableitung

− ( ) ( )1'' ''j j j js x s x−= - Stetigkeit der 2. Ableitung

− ( ) ( )1 1 1'' '' 0n ns x s x−= = - „kraftfreie Einspannung“ an den Enden


Dabei sind in jedem Intervall vier Parameter für ein Polynom dritten Grades anzupassen. Auf 1n − Intervallen ergibt dies 4( 1)n − Parameter und genauso viele Bedingungen. Wie das daraus entstehende lineare Gleichungssystem gelöst werden kann, wird in einem späteren Kapitel vorgestellt.

Beispielrechnung für den einfachen Fall mit äquidistanten Stützstellen Gegeben seien die Stützstellen

( ), 1, ,j jx y j n=

mit dem äquidistanten Abstand

1j jh x x+= −

Der Spline im Intervall 1,j jx x +

( ) 1 mit ,j j js x x x x + ∈

hat dann die Form

( ) ( ) ( ) ( )2 31 12 6j j j j j j j js x y a x x b x x c x x= + − + − + −

mit den Koeffizienten = Ableitungen der Fit-Funktion an der Stelle jx .

Aus den Anschlussbedingungen folgt

2 31

21

1

1 12 612

j j j j j

j j j j

j j j

y y a h b h c h

a a b h c h

b b c h

+

+

+

= + + +

= + +

= +

(*)

und an den Rändern ist zusätzlich

1

1

00n

bb −

==

Durch Einsetzen der Gleichungen ineinander lässt sich ein lineares Gleichungssystem für jb finden. Aus diesem können dann die anderen Koeffizienten ( ,c )j ja bestimmt

werden. Dafür wird die letzte Gleichung von (*) nach jc umgestellt

( )1 /j j jc b b h+= −

und in die anderen beiden Gleichungen eingesetzt. Dies ergibt


21 1

1 1

1 12 6

1 12 2

j j j j j

j j j j

y y a h b h b

a a b h b h

+ +

+ +

= + + +

= + +(**)

Die obere Gleichung von (**) wird an den Intervallgrenzen j und j+1 aufgestellt. Aus diesen beiden Gleichungen wird ja eliminiert indem die untere Gleichung von (**)

bei j aufgestellt wird. 1 1

1 12 2j j j ja a b b h− −= + +

Daraus folgt

( )11 1 1

11 1

1 15 36 6 2, , 2

1 13 6

j jj j j j

j jj j j

y ya b b h b h

h j ny y

a b h b hh

+− − +

−− −

−= + + +

= −−

= + +

Durch Elimination von 1ja − ergibt sich

( )1 1 1 1264 2j j j j j jb b b y y yh+ − + −+ + = − + bei 2, , 2j n= −

Mit den Randbedingungen lassen sich aus diesem Gleichungssystem alle zweiten Ableitungen jb ermitteln. Die anderen beiden Koeffizienten ( , )j ja c lassen sich dann durch Einsetzen in die entsprechenden Gleichungen leicht bestimmen.

1.6.3 Rationale Approximation Die bisher diskutierten Interpolationsverfahren zeichnen sich durch eine hohe Flexi-bilität des Funktionenansatzes aus, d.h. sie lassen sich auf vielfältige Probleme anwenden. Teilweise erfordert das zu lösende Interpolationsproblem jedoch die Wahl eines spezifischen, problemangepassten Funktionenansatzes. Falls die zu interpolierende Funktion Polstellen aufweist, erscheint folgender Poly-nomansatz günstig

( ) ( )( )

n

m

P xy x

Q x=

wobei ( )nP x und ( )mQ x Polynome vom Grade n bzw. m sind. Die Anzahl NS der bekannten Stützstellen kx bestimmt die Summe der Polynomgrade durch

1SN m n= + − . Neben der Anzahl der Pole ( m≤ ) kann z.B. mit m n j= + die physikalische Information über das asymptotische Verhalten berücksichtigt werden (für große x ist ( ) ~ jy x x− ). Die Werte der Polynome lassen sich durch ein System gekoppelter Gleichungen an den Stützstellen kx bestimmen


( ) ( )n k k m kP x y Q x= ( ) ( )2 20 1 2 1 2... 1 ...k k k k ka a x a x f x b x b x+ + + = ⋅ + + +


2. Lineare Gleichungssysteme Im Folgenden werden Verfahren zu Lösung von linearen Gleichungssystemen vorge-stellt. Dabei betrachten wir Systeme algebraischer Gleichungen der Form

11 1 12 2 13 3 1 1

21 1 22 2 23 3 2 2

31 1 32 2 33 3 3 3

1 1 2 2 3 3

...

...

......

...

n n

n n

n n

m m m mn n m

a x a x a x a x ba x a x a x a x ba x a x a x a x b

a x a x a x a x b

+ + + + =

+ + + + =

+ + + + =

+ + + + =

Dies können wir auch in der Matrixdarstellung schreiben als

Ax b=

Wobei A die Koeffizientenmatrix ist und b

ein Spaltenvektor.

11 12 1

21 22 2

1 2 3

...

...A

...

n

n

m m m mn

a a aa a a

a a a a

=

,

1

2

...

m

bb

b

b

=

.

Eine alternative Formulierung des Problems ist

( ) 0f x =

mit ( )1

1, , 1, ,n

i ij j ij

f x a x b j n i m=

= − = =∑

2.1 Implementierung in Computer-Algebra-Systemen Für die Anwendung von Lösungsalgorithmen in Computer-Algebra-Systemen wird das Problem zuerst nach verschiedenen Gesichtspunkten charakterisiert. Wenn die Vektoren b

und x die gleiche Dimension haben lässt sich das Problem am einfachsten lösen. Ist jedoch eine Zeile oder Spalte degeneriert, d.h. sie ist nicht von den anderen Zeilen bzw. Spalten linear unabhängig, treten Singularitäten auf. Diese Fälle müssen gesondert betrachtet werden. Falls die Vektoren unterschiedliche Dimensionen haben ergeben sich komplexere Aufgabenstellungen. Im Falle eines unterbestimmten Problems ergeben sich Lösungs-räume, die vom Computer nur Beispielhaft berechnet werden können. Für über-bestimmte Probleme kann der Computer zur Lösung einer Minimierungsaufgabe eingesetzt werden (siehe Kapitel "Nullstellen und Extrema"), deren Lösung das lineare Gleichungssystem "möglichst gut" löst. Hier Konzentration auf den Fall A ( n m= ): • Probleme bei analytischer Lösung: degenerierte Probleme


− eine Zeile (Spalte) ist Linearkombination von anderen Zeilen (Spalten) zeilendegeneriert (spaltendegeneriert) beide Fälle führen auf singuläre Probleme

• Probleme bei numerischer Lösung: − Problem numerisch nahezu singulär durch Rundungsfehler kann

Singularität entstehen − Problem zu groß große Rundungsfehler kann ebenfalls zu Singularität

führen • Aufgabentypen:

− Lösung von Ax b=

− Lösung von ˆj jAx b=

, d.h. mehrere jb

für ein A jx

− Berechnung von 1A− entspricht dem Aufwand des Typs ˆj jAx b=

mit

1,...,j n= und 1jjb = , sonst 0 , dann ( )11

ˆ ,..., nA x x− =

• Vorhandene Programmpakete: Lapack, IMSL, NAG Da bei physikalischen Problemstellungen oftmals Gleichungssysteme ähnlicher Struk-turen entstehen, wurden für häufig auftretende Problemtypen angepasste Lösungsmethoden entwickelt. Typische Matrixstrukturen, für die angepasste Lösungsmethoden existieren, sind z.B.:

1. hermitesche Matrizen: †ˆ Â A= († = komplexe Konjugation und Trans-position)

2. positiv definite Matrizen: ˆ 0vAv v> ∀

3. Bandmatritzen:

Bandmatrix

4. tridiagonale Matrizen:


0

0

Tridiagonal-Matrix

Entsteht z.B. durch symetrische 1. Ableitung oder durch 2. Ableitung:

2( ) 2 ( ) ( )( ) f x h f x f x hf x

h− − + +′′ ≈

5. Blockmatrizen:

Blockmatrix

6. Sparse-Matrizen: Matrizen mit sehr vielen Nullen. immer spezielle Eigenschaften der Matrix nutzen, um angepasste

Lösungsmethode anzuwenden Neben der Unterscheidung nach Matrixtyp unterteilt man die Lösungsverfahren hinsichtlich ihrer Herangehensweise:

− direkt: vorhersagbare Zahl von Lösungsschritten − iterativ: konvergiert von Startwert zur Lösung x (Anwendung bei großen N

oder bei nahezu singulären Problemen) − kombiniert direkt-iterativ: erst direkt und dann iterative Verbesserung der

Genauigkeit Die Qualität der Lösung hängt natürlich von dem der Methode zur Verfügung ge-stellten Speicher ab, da dieser die Genauigkeit des verwendeten Zahlenformates begrenzt. Der Speicherverbrauch kann dabei meist manuell, je nach erforderlicher Genauigkeit des Zahlenformates eingestellt werden.

2.2 Gauss-Jordan-Elimination Dieses Verfahren gehört zur Klasse der Eliminationsverfahren und stellt eine Verbes-serung des aus der linearen Algebra bekannten Gauss-Algorithmus’ dar. Die Koeffi-


zientenmatrix wird dabei auf strenge Stufenform gebracht, d.h. nur in der Diagonalen befinden sich noch Einträge und die Lösung ist somit sofort abzulesen. Um dies zu erreichen, werden von Ax b=

ausgehend, folgende elementare Zeilenoperationen angewandt:

1. zwei Zeilen von A und entsprechende Elemente von b

vertauschen,

2. eine Zeile von A und entsprechendes Element von b

mit einer Konstanten 0λ ≠ multiplizieren,

3. zu einer Zeile von A und entsprechendem Element von b

das λ -Fache einer anderen Zeile hinzuaddieren.

Diese Schritte werden so oft angewendet, bis die gewünschte Struktur einer Dreiecksmatrix erreicht ist.

Stufenform: 1 2 1 50 2 1 40 0 3 3

bzw. strenge Stufenform: 1 0 0 10 1 0 1/ 20 0 1 3

Damit kann die Lösung x durch Rücksubstitution bzw. direkt abgelesen werden.

Beispiel

1 2 3

1 2 3

1 2 3

2 3 143 2 112 3 11

x x xx x xx x x

+ + =

+ + =

+ + =

Subtraktion von 3x Gl. (1) von Gl. (2) und Subtraktion von 2x Gl. (1) von Gl. (3) ergibt

1 2 3

2 3

2 3

2 3 14

5 7 315 17

x x x

x xx x

+ + =

− − = −

− − = −

Subtraktion von 1/5x Gl. (2) von Gl. (3)

1 2 3

2 3

3

2 3 145 7 31

18 545 5

x x xx x

x

+ + =

− − = −

− = −

Da bei einer ungünstigen Verteilung der Koeffizienten während der Rechnung numerische Singularitäten beim Dividieren durch kleine Zahlen auftreten können, ist es sinnvoll die Zeilen so anzuordnen, dass immer durch große Beträge dividiert wird, um Singularitäten zu vermeiden. Dies bezeichnet man als Pivotisierung. Der Gauss-Jordan-Algorithmus mit Pivotisierung hat dann folgende Gestallt:


Pivotisierung • Sei 1j die Nummer der erste Spalte von links, mit einem Eintrag 0≠

Ggf. stellt man durch Vertauschen der Zeilen sicher, dass 11A 0j ≠ bzw. auch nicht

nahe Null ist. Dies ist dann die erste Pivotstelle.

• Man multipliziert die erste Zeile mit 11

1A j

, sodass 11A 1j = wird

• Für jedes 2 i m≤ ≤ zieht man das 11A j -fache der ersten Zeile von der i-ten ab

(„kehren unter Pivotstelle“)

• Sei B die Matrix, die aus Zeilen 2 bis m von A besteht, man führe die oberen Schritte rekursiv mit B durch. Die Matrix A ist nun in Zeilenstufenform.

• Für jede Pivotstelle ( , )ii j „kehre“ man oberhalb indem man für jedes 1 a i≤ < das

iajA -fache der i-ten Zeile von der a-ten subtrahiert. A hat nun strenge-Zeilen-

Stufenform.

Eigenschaften • erfordert 3~ n Multiplikations-/Divisionsoperationen • solides aber nicht problemangepasstes Verfahren

Matrixinversion Das Gauss-Jordan-Verfahren dient teilweise auch zur Berechnung der Inversen -1A einer Matrix A mit -1ˆ ˆ ÂA E= , wobei E die Einheitsmatrix ist. Dabei wird bei einer n n× -Matrix A das Gauss-Jordan-Verfahren bis zum Erreichen der strengen Stufen-form angewandt und simultan jede einzelne Zeilenoperation auch an einer n n× -Einheitsmatrix E durchgeführt. Die letztendlich aus der Einheitsmatrix resultierende Matrix ist das gesuchte Ergebnis der Matrixinversion -1A .

2.3 Löser für tridiagonale Matrizen Tridiagonale Matrizen sind ein für physikalische Probleme häufig auftretender und einfach zu lösender Spezialfall. Dabei wird die Lösung eines linearen Gleichungs-systems mit folgender Struktur gesucht

1 1 1 1

2 2 2 2 2

3 3 3 3 3

1 1 1 1 1

0 00

00 0

N N N N N

N N N N

b c u da b c u d

a b c u d

a b c u da b u d

− − − − −

=

Um die iu zu erhalten wird in zwei Schritten vorgegangen.


Zuerst wird durch eine Gauss-Elimination eine obere Dreiecksmatrix erzeugt. Dies erreicht man durch

1 1

1

1 1

1

1

1/ 1

2 ( 1)

/ 1

2

i

i i

i i i

i i i i

i i i

bc b i

c c i Nb a c

d b id d a d i N

b a c

−

−

−

′ =

=′ = = − ′−

=′ ′= − = ′−

Damit wird das Gleichungssystem zu

1 1 1

2 2 2

3 3 3

1 1 1

1 0 00 1 0

0 1

0 0 10 0 0 1

N N N

N N

c u dc u d

c u d

c u du d

− − −

′ ′ ′ ′ ′ ′

= ′ ′ ′

Im zweiten Schritt erfolgt die Rücksubstitution von unten nach oben, so dass die obere Dreiecksmatrix in eine Einheitsmatrix überführt wird.

1 ( 1) 1N N

i i i i

u du d c u i N+

′=′ ′= − = −

2.4 LU-Zerlegung (Dekomposition, Faktorisierung) Dieses Verfahren gehört zur Klasse der Dekompositions- bzw. Faktorisierungsver-fahren. Dabei stellen wir uns vor, man könne die Koeffizientenmatrix A als ein Produkt zweier Matrizen schreiben

Ax b=

ˆˆ ˆL U=A⋅ .

Dabei soll L eine untere („lower“) Dreiecksmatrix sein. Diese hat nur auf der Hauptdiagonalen und darunter von Null verschiedene Einträge. U ist eine obere („upper“) Dreiecksmatrix. Diese hat nur auf der Hauptdiagonalen und darüber von Null verschiedene Einträge. Die obige Gleichung hat damit die Gestalt:

11 11 12 13 1411 12 13 14

21 22 21 22 23 2422 23 24

31 32 33 31 32 33 3433 34

41 42 43 33 41 42 43 4444

0 0 00 0 0

0 0 00 0 0

l a a a au u u ul l a a a au u ul l l a a a au ul l l l a a a au

⋅ =


Es ist so möglich, das lineare Gleichungssystem zu zerlegen

ˆ ˆ ˆ ˆ Â x=(L U) x=L (U x )=by=

⋅ ⋅ ⋅ ⋅ ⋅

indem man zunächst L y = b⋅

und anschließend U =x y⋅ löst.

Der Vorteil besteht dabei darin, zwei triviale Gleichungssysteme zu erhalten, die durch „Vorwärts-Elimination“ und nachfolgende „Rückwärts-Elimination“ gelöst werden können.

1. Schritt: lösen von L =y b⋅

durch Vorwärts-Elimination

11

11

1

1

1 i

i i ij jjii

byl

y b l yl

−

=

=

= −

∑

2,3,...,i n=

2. Schritt: lösen von U =x y⋅ durch Rückwärts-Elimination

1

1

nn

nn

n

i i ij jj iii

yxu

x y u xu = +

=

= −

∑

1, 2,...,1i n n= − −

Doch wie lassen sich L und U bei L gegebener Matrix A bestimmen? Die Koeffizienten der n n× -Matrizen L und U zu bestimmen heißt 2n n+ Unbekannte zu finden (die Hauptdiagonale ist doppelt belegt!). Da durch die Ursprungsmatrix A jedoch nur 2n Gleichungen resultieren, sind wir gezwungen, n Koeffizienten frei zu wählen und die Gleichung für die anderen 2n Unbekannten zu lösen. Ein sehr einfacher Algorithmus für die Zerlegung der Matrix A in das Matrixprodukt ˆ ˆLU ist der Crout’s-Algoritmus.

Crout’s-Algorithmus: Ableitung am Beispiel einer 3x3 Matrix

11 12 13

21 22 23

31 32 33

11 12 13

21 11 21 12 22 21 13 23

31 11 31 12 32 22 31 13 32 23 33

1 0 0ˆ ˆ1 0 U 0

1 0 0

ˆˆ ˆ

u u uL l u u

l l u

u u uLU l u l u u l u u A

l u l u l u l u l u u

= =

= + + = + + +

Die Elemente der Dreiecksmatrizen lassen sich leicht (explizit) aus der Ursprungsmatrix ablesen, wenn man die richtige Reihenfolge einhält.


11 12 13 21 31 22 23 32 33, , , , , , , ,u u u l l u u l u

Crout’s-Algorithmus: Ablaufplan für beliebige Matrizen • setze 1iil = für 1,...,i n=

• für 1,...,j n= sind nun die Koeffizienten wie folgt zu bestimmen

− für 1,...,i j= 1

1

i

ij ij ik kjk

u a l u−

=

= − ∑

− für 1, 2,...,i j j n= + + 1

1

1

j

ij ij ik kjjjk

l a l uu−

=

= −

∑

Dabei ist darauf zu achten, dass zunächst beide Prozeduren durchlaufen werden bevor man zum nächsten j übergeht.

Eigenschaften • Kosten der LU-Zerlegung: 3~ / 3n Multiplikationen/Divisionen

• Kosten der Rücksubstitution: 2~ / 2n Multiplikationen/Divisionen • Vorteil der LU-Zerlegung:

− Problem in zwei Teile geteilt − direktes explizites Verfahren

− eigentliches Problem wird unabhängig von rechter Seite b

Vorteile bei vielen verschiedenen bn

, weil die Zerlegung der "teuerste" Bestandteil des Algorithmus ist

2.5 Iterative Verbesserung der Lösung Wenn zu einem linearen Gleichungssystem eine numerische Lösung gefunden wurde, ist diese durch Rundungsfehler fehlerbehaftet, die speziell bei großen Gleichungs-systemen akkumulieren. Ziel der iterativen Verbesserung ist es, diese Fehler zu mini-mieren. Sei x die exakte analytische Lösung des Systems

Ax b=

.

So erhält man durch eine direkte numerische Lösung des Gleichungssystems (z.B. Gauss-Jordan-Verfahren) niemals x sondern immer eine etwas abweichende Lösung x x x′ = + δ

mit dem unbekannten Fehler xδ

. Diese falsche Lösung x′ führt in der obigen Gleichung zu einer Abweichung von der rechten Seite der Gleichung, also zu

Ax b′ ′=

oder A( )x x b b+ δ = + δ

Subtrahieren wir nun die exakte Gleichung von der verfälschten erhalten wir

A x b⋅ δ = δ


und schließlich erhalten wir

A A ( ) Ax x x b x b′⋅ δ = ⋅ + δ − = ⋅ −

Die rechte Seite der Gleichung mit der falschen Lösung x x+ δ

und dem Vektor b

ist nun bekannt. Dabei ist die Subtraktion von b

mit doppelter Genauigkeit auszuführen (Werte heben sich sonst oft weg). Das obige System ist nun für den Fehler xδ

zu lösen, welcher dann von der bekannten falschen Lösung x x+ δ

abzuziehen ist, um eine Verbesserung zu erzielen. Dieser Algorithmus wird wiederholt bis der Fehler xδ

klein genug ist.

2.6 Eigenwertprobleme Für viele physikalische Probleme mit linearen Zusammenhängen lassen sich Eigen-wertgleichungen in algebraischer Form formulieren. Ein numerisches Verfahren zu Lösung von Eigenwertgleichungen ist somit enorm wichtig. Zur Veranschaulichung des Problems demonstrieren wir ein Beispiel aus der theoretischen Mechanik, der gekoppelte harmonische Oszillator.

Ausgehend von den Kräftegleichgewichten für jeden einzelnen Massepunkt lauten die Bewegungsgleichungen für die Massepunkte in relativen Koordinaten

( )( ) ( )( ) ( )( ) ( )( )

1 1 2

2 2 3 2 1

3 3 4 3 2

4 4 5 4 3

5 5 4

mx k x x

mx k x x k x x

mx k x x k x x

mx k x x k x x

mx k x x

= − −

= − − − −

= − − − −

= − − − −

= − −

Mit der Substitution kmω = ergibt sich in Matrixschreibweise

1 1

2 22

3 3

4 4

5 5

1 1 0 0 01 2 1 0 00 1 2 1 00 0 1 2 10 0 0 1 1

x xx xx xx xx x

− − = ω ⋅− − −

oder 2Mx x= ω

Da es sich um ein harmonisch oszillierendes System handelt, wählt man als Lösungsansatz

( ) 0 exp( )x t x i t= Ω

mit den gesuchten Lösungsvariablen 0x und Ω


Nach dem Einsetzen des Ansatzes folgt

( )

2

20 0

0

M mit

ˆ ˆM E 0

x x

x

Ωω

⋅ = λ λ =

− λ =

Dies ist ein typisches Eigenwertproblem, da λ genau dann ein Eigenwert ist, wenn

ˆ ˆdet M E ( ) 0P − λ = λ =

(Nur dann hat die Gleichung ( )ˆ ˆ 0M E x− λ =

nicht verschwindende Lösungen.)

Eigenschaften • für eine N-dimensionales Eigenwertproblem ist ( )P λ charakteristisches Polynom

N -ten Grades mit N komplexen Nullstellen transzendentes Problem (kein expliziter Lösungsalgorithmus)

• damit wurde diese Aufgabenstellung auf das bereits behandelte Problem der Nullstellensuche zurückgeführt.

• numerische Lösung erfolgt in der Regel jedoch mit speziellen Lösungsmethoden für spezifische Problemklassen (symmetrisch, hermitesch, unitär, etc.), grobe Unterscheidung in:

− iterative Verfahren, z.B. Jacobi Methode − direkte Verfahren, z.B. Housholder Methode QL Methode

Matrixinversion mit Gauss-Jordan Gegeben sei die Matrix

3 2 16 6 39 10 6

A =

Berechnen Sie mittels Gaus-Jordan-Verfahren die inverse Matrix 1A− von Hand und kontrollieren Sie ihr

Ergebnis mit MATLAB.

LU-Dekomposition

Berechnen sie die LU- Dekomposition von Hand A L U= ⋅ und vergleichen Sie ihr Resultat, indem Sie den Kodeschnipsel zur LU- Komposition in MATLAB implementieren.


3. Fourier-Transformation Die Beschreibung physikalischer Systeme geschieht oftmals durch Differentialglei-chungen, in denen Zeitableitungen ( )f t eine wichtige Rolle spielen. Wenn es sich dabei um lineare Differentialgleichungen handelt, kann man vom Superpositions-prinzip Gebrauch machen. Die Fourier-Transformation, die Darstellung einer Funktion

( )f t als eine Superposition trigonometrischer Funktionen, ist dann eine gute Methode, um die Lösung einfacher zu ermitteln. Daraus ergeben sich gegenüber der Oroginalfunktion ( )f t zwei Vorteile: 1) Wir können die Ableitungen trigonometrischer Funktionen analytisch berechnen. 2) Das Ergebnis der Ableitung ist wieder eine trigonometrische Funktion.

Zusammenhang von Fourier-Transformation und Fourier Reihe Fourier-Transformation Diskretisierung Fourier-Reihe

( ) ( )exp( )f t f i t d+∞

−∞

= ω ω ω∫ 1( ) ( )exp( )

n

n nf t f i tT ω

= ω ω∑

1( ) ( )exp( )2

f f t i t dt+∞

−∞

ω = − ωπ ∫ ( ) ( )exp( )

n

n nt

f t f t i tω = ∆ − ω∑

Für die Berechnung mittels Computer verfolgen wir den Ansatz der Fourier-Reihe, den wir folgendermaßen formulieren:

( ) i tf t e ωω

ω

= α∑ .

Wir bezeichnen ωα als Fourier-Koeffizienten und ω als Frequenz. Die Zeitableitung ist dann

i tn

df i edt

ω

ω

= ωα∑ .

Diese Idee, eine zeitabhängige Funktion durch eine Summation über Frequenzen darzustellen, kann analog auf eine ortsabhängige Funktion übertragen werden. Dabei wird eine Funktion ( )f x durch eine Summe über harmonische Funktionen exp( )ikx mit den sogenannten Ortsfrequenzen k dargestellt. So gelangt man von Differentialgleichungen im Zeitraum/Ortsraum zu algebraischen Gleichungen im Frequenzraum. Dadurch kann eine physikalische Aufgabenstellung (sehr viel einfacher) gelöst werden. Nach einer Fourier-Transformation in den Fre-quenzraum löst man das Problem, um dann das Ergebnis durch Rücktransformation wieder im Zeitraum darzustellen.


Motivation

Lösungsansatz 1) Problem im Zeitraum (Originalraum) Fourier-Transformation

Frequenzraum (Fourier-Raum / Bildraum) 2) Berechnung der Lösung des Problems im Frequenzraum 3) Lösung im Frequenzraum (FT)-1 Lösung im Zeitraum

Für beliebige Zeitverteilungen geht die Anzahl der Frequenzen jedoch gegen unend-lich. Deswegen versucht man in der numerischen Berechnung mit periodischen Zeitverteilungen zu arbeiten. Da maximal eine endliche Reihenentwicklung berück-sichtigt werden kann, erscheinen auch nur diskrete Frequenzspektren.

Eine Funktion, die physikalische Bedeutung hat, erfährt in der Regel zu einer bestimmten Zeit eine Anregung, die zu einer Auslenkung von der Ruhelage führt, und fällt aufgrund von dissipativen Effekten, wie Reibung etc., nach endlicher Zeit zurück in die Ruhelage. Der Response eines realen physikalischen Problems kann deshalb meist eine "künstliche" Periodizität geben werden, indem unendlich viele Anregung hintereinander betrachtet werden, ohne, dass sich die Einzelanregungen dabei beeinflussen.

Problem im Originalraum (Differentialgleichung)

Problem im Bildraum (algebraische Gleichung)

Lösung im Bildraum Lösung im Originalraum

FT

FT-1


Beispiel: Zerlegung einer periodischen Rechteckfunktion(blauer Graph). Bei Hinzunahme von immer mehr diskreten Frequenzkomponenten auf der linken Seite (roter Graph) ergibt deren Summe auf der rechten Seite immer deutlicher die Rechteckfunktion.

3.1 Die diskrete Fourier-Transformation Für die diskrete Fourier-Transformation seien die Funktionswerte an den N Stütz-stellen

0, ,2 , ,x a a L a= −

in einer Periode L mit der Schrittweite a gegeben. Dann lässt sich eine Funktion als

( ) ( )xyy

f x f y= δ∑

( xyδ - Kronecker-Symbol, alle Summen über LNa

= Elemente)

schreiben. Dabei gilt die Identität

( )ik x yxy

k

a eL

−δ = ∑ .

Mit zugehörigen diskreten Ortsfrequenzen


[ ] 2 2 20,1 ,2 , , 1LL L a Lk π π π= ⋅ ⋅ − mit

L Na

=

kann man obige Feststellungen nochmals aufschreiben

( ) ( )

( ) ( )

( )1

xyy

ik x yaL

y k

ikx iky

k y

f x f y

e f y

e a e f yL

−

−

= δ

=

=

∑

∑ ∑

∑ ∑

und damit eine diskrete Fourier-Transformation (FT)

( ) ( )ikx

xf k a e f x−= ∑ (dabei y durch x ersetzt)

mit ( )2, 0La LN k n n Nπ= = ≤ < , x n a= ⋅

und die zugehörige inverse diskrete Fourier-Transformation (FT-1)

( ) ( )1 ikxL

kf x e f k= ∑

In der Literatur können bei der Einführung der Fourier-Transformation die Vorfak-toren und Vorzeichen variieren. definieren. Da es sich hier um eine endliche Summe handelt, bestehen, mit den im Allgemeinen komplexen Koeffizienten, keinerlei Konvergenzprobleme. Einzig der Speicherbedarf für die N unabhängigen Werte im Zeit- und Ortsraum kann noch Probleme verur-sachen. Bisweilen sind bei den Vorfaktoren und Vorzeichen unterschiedliche Konventionen üblich, jedoch muss immer ( )f x FT ( )f k FT-1 ( )f x gelten sowie die periodische Randbedingung ( ) ( )f x L f x± = gewährleistet sein.

Verallgemeinerung für höhere Dimensionen Genauso lässt sich dies auch für höhere Dimensionen schreiben ( x x→

; k k→

) Im dreidimensionalen Raum lauten Transformation und Rücktransformation z.B.

( ) ( )

( ) ( )

3

31

ikx

x

ikx

k

f k a e f x

f x e f kL

−=

=

∑

∑

Aufwand Für die Implementierung des Algorithmus muss im Eindimensionalen jeder k-Wert N mal mit ikxe multipliziert werden. Für alle Werte sind dies 2N Multiplikationen. Für


m-dimensionale Probleme werden es damit 2mN Multiplikationen. Ziel der nachfolgenden Betrachtungen ist es, diese Anzahl zu verringern. Deswegen bietet es sich für m-dimensionale Fouriertransformationen an, je nur eine Variable in einer eindimensionalen Transformation zu transformieren und diesen Vorgang für alle m Variablen zu wiederholen. Dafür sind dann nur noch 1mm N +⋅ Multiplikationen nötig. Beispiel für 3D:

− zuerst nur eine Variable transformieren

( )1 2 3, ,f k k k ( ) ( ) ( )1 1

1

1 11 2 3 1 2 3, , , ,ik x

Lk

f x k k e f k k k= ∑

− danach für jede weitere Variable einmal anwenden.

3.2 Fast-Fourier-Transformation Die Idee der Fast-Fourier-Transformation besteht darin, die einzelnen Berechnungs-schritte der Fourier-Transformation in einer speziellen Reihenfolge auszuführen, so dass jeweils auf schon berechnete Zwischenergebnisse zurückgegriffen werden kann. Mit diesem Verfahren werden wir den Rechenaufwand für die eindimensionale Fourier-Transformation von 2N auf 2logN N Operationen reduzieren. Dies ermög-licht eine extreme Zeitersparnis, z.B. für N=106 Ergibt sich eine Reduzierung von 2 Wochen auf 30 Sekunden. Das Prinzip der FFT besteht aus zwei Tricks.

1. Trick Zuerst wird die Fourier-Transformation mit Länge N in 2 Fourier-Transformationen der halben Länge 2

N zerlegt – eine enthält die geraden Punkte, die andere die ungeraden. Das ergibt

( ) ( )

[ ] [ ]

[ ]( ) [ ]( )

( ) ( )

2 2

e o

2 2

12

0

1 12 2

2 2 10 0

1 12 2

2 2 10 0

e o

1 exp

1 1exp 2 exp 2 1

1 1exp 2 exp 2

N N

N N

N

k n Nn

n nN Nn n

x x

n nN Nn n

f k f iknN

f ik n f ik nN N

f ik n W f ik nN Nf k f k

−π

=

− −π π

+= =

− −π π

+= =

= −

= − + − +

= − + −

= +

∑

∑ ∑

∑ ∑

mit der Bezeichnung e (even) für die geradzahligen und o (odd) für die ungeradzahligen Stützstellen. W ist dabei eine komplexe Konstante. Dieses Verfahren lässt sich rekursiv anwenden und führt auf

( ) ( ) ( ) ( ) ( )ee eo oe oof k f k f k f k f k= + + +


(4 FT mit Länge 4N ) und wird fortgeführt, bis auf ( 2log N ) Zerlegungen mit einer

Intervalllänge von Eins. Dann hat die letzte Zerlegung die einfache Form

( ) ( ) ( )1 1eoeo…oo eoeo…oo eoeo…ooexpa N

W

f k f x ikx= −

Das Schema funktioniert natürlich nur gut für 2 ( )mN m= ∈ .

2. Trick Im zweiten Schritt muss noch ermittelt werden, welcher f-Wert zu welchem eoeo oo -Muster gehört. Dazu wird

e 0o 1

→→

gesetzt und dann die Reihenfolge des entstandenen Binärcodes umgekehrt. Dann ist der Binärwert gleich dem Index n des Funktionswertes nf . Ursache: die vielfache Teilung in e und o entspricht der Abfrage der Bits von n startend vom höchstwertigsten zum niederwertigsten Bit Insgesamt wird dann die Fouriertransformation sukzessive aus den Teilschritten Zusammengesetz. Da bei dieser Zusammensetzung für unterschiedliche k identische Teilelemente der Zerlegung auftreten, können Zwischenschritte wiederverwendet werden, wodurch sich der Geschwindigkeitsvorteil der Fast-Fourier-Transformation gegenüber der "normalen" Fourier-Transformation ergibt.

3.3 Das Abtasttheorem Um aus einem bandbegrenzten Signal das Ursprungssignal wiederherstellen zu können, muss die Abtastfrequenz abtastv mindestens doppelt so groß sein wie die maximale Frequenz, bzw. das Frequenzband, d.h. mindestens zwei Punkte je schnellste Periode

abtast max2v v≥ oder allgemeiner Nyquist

abtast max min2( )v

v v v≥ −

falls min 0v ≠ .

Häufig wird als charakteristische Frequenz auch die Nyquist-Frequenz benutzt

Nyquist 2∆ϖ

ν =π

abtast Nyquist2v v≥

Bei nicht bandbegrenzen Signalen kommt es zum Aliasing-Effekt (Faltungsver-zerrung), d.h. die spektrale Leistung aus zu hohen Frequenzen wird in tiefe Frequenzen verschoben (Lösung bei begrenzter Samplingrate: vorher analoger Tiefpassfilter).


Beispiel zum Ansehen bzw. Anhören: http:///de.wikipedia.org/wiki/Nyquist-Shannon-Abtasttheorem

ω DFT-Intervall Aliasing-Effekt

Kompromissfindung: Zeit gegen Frequenzauflösung • Fenster Methoden

• Wavelet-Transformation

Allgemeine Hinweise • Frequenzverteilung in Computerdarstellung

t

Hann

A

Rechteck

Welch

Bartlett

t0

http://de.wikipedia.org/wiki/Nyquist-Shannon-Abtasttheorem


• reelle Funktionen sin, cos-Transformation • FFTW – Fastest Fourier Transform in the West (parallel) • Spezialimplementierungen für spezielle Rechnertypen • digitales Filtern • nichtäquidistantes Sampling

x k k’


4. Gewöhnliche Differentialgleichungen Da sich eine ganze Reihe wichtiger physikalischer Systeme durch gewöhnliche Differentialgleichungen (DGL) beschreiben lassen, werden wir uns in diesem Kapitel mit dem Lösen derselben beschäftigen. Die allgemeine explizite gewöhnliche Differentialgleichung hat dabei folgende Struktur

( ) ( )( 1), ',..., ,k

kk

d f tG f f f t

dt−=

Für die Lösungsmethodik ist neben der eigentlichen Differentialgleichung von prin-zipieller Bedeutung, ob die Eindeutigkeit der Lösung innerhalb der Aufgabenstellung durch zusätzliche Anfangsbedingungen oder Randbedingungen vorgegeben ist. Hier sollen zuerst Methoden für Anfangsbedingungen und erst danach für Randbe-dingungen vorgestellt werden.

4.1 Anfangswertaufgaben (AWA) Aufgabenstellung ist Anfangswerteaufgabe, die durch eine Differentialgleichung (DGL) und die zugehörigen Anfangswerte (AW) eindeutig beschrieben ist

DGL k-ter Ordnung: ( ) ( )( 1), ',..., ,

kk

k

d f tG f f f t

dt−=

AW: ( ) ( ) ( ) ( )10 , ' 0 ,..., 0kf t f t f t−= = =

Dies ist äquivalent zu einem gekoppelten Differentialgleichungssystem 1. Ordnung aus k Gleichungen Transformation in System gekoppelter DGL 1. Ordnung

( )

( )

( )

( )

11 1 2

22 1 2

33 1 2

1 2

( ) , ,..., ,

( ) , ,..., ,

( ) , ,..., ,

( ) , ,..., ,

k

k

k

kk k

df t G f f f tdt

df t G f f f tdt

df t G f f f tdt

df t G f f f tdt

=

=

=

=

mit den zugehörigen Anfangswerten. Ein Beispiel soll die DGL zweiter Ordnung sein 2

2 ( ) ( )d y dyq t r tdt dt

+ =

welche in ein System gekoppelter Differentialgleichungen erster Ordnung umge-schrieben werden kann


( )

( ) ( ) ( )

dy z tdtdz r t q t z tdt

=

= −

mit den bekannten Anfangswerten ( ) ( )0 , 0 ( 0)y t y t z t′= = = = . Um die Notation übersichtlich zu gestalten, erfolgt im Folgenden die Darstellung der Grundprinzipien von Lösungsverfahren vielfach am Beispiel von Differential-gleichungen 1. Ordnung. Durch den obigen Ansatz zur Transformation von Differentialgleichungen höherer Ordnung in Systeme gekoppelter Differential-gleichungen 1. Ordnung, kann diese Darstellung leicht erweitert werden, indem von einer skalaren Notation ( )f t auf eine vektorielle Notation ( )f t

übergegangen wird.

Beispiel für DGL 1. Ordnung Einfache Anwendungsbeispiele für eine Anfangswertaufgabe 1. Ordnung stellen der radioaktive Zerfall, die lineare Bewegung mit Newtonscher Reibung oder die Entladung eines Kondensators dar. Alle diese Vorgänge können durch die folgende Differentialgleichung und zugehörigen Anfangswerte beschrieben werden

( )( )df t f tdt

= −γ ⋅

Allgemeines Vorgehen zur Lösung von Anfangswertproblemen − Reduzierung der Ordnung auf ein System von DGLs erster Ordnung − Diskretisierung der Ableitung − Ausführen von N Integrationsschritten mit t∆ (hier z.B. Zeitschritt) bis zum

Ende der Integrationsintervalls bei T

( ) nf t f→ mit ( ):nf f n t= ⋅ ∆ und 0( ) /t T t N∆ = −

4.1.1 Vorwärts-Euler-Verfahren Dieses einfache Verfahren nähert die Zeitableitung in der Differentialgleichung durch den diskreten rechtsseitigen Ableitungsoperator (Differenzenquotient). Damit wird aus

( ) ( )( ),f t G f t t′ =

die Differenzenformel

( ) ( ) ( ) ( )( )'( ) ,tf t t f t

f t D f t G f t tt∆

+ ∆ −= = = ∆

Mit der diskreten Schrittweite t∆ lassen sich die Funktionswerte als

( ) :nf f n t= ⋅ ∆


schreiben. Die Differenzengleichung lautet dann

( )1 ,n nn

f f G f tt

+ −=

∆

Durch Umstellen nach dem unbekannten Element 1nf + erfolgt die Lösung der Anfangswertaufgabe dann ausgehend von dem Anfangswert 0f mittels folgender Rekursionsformel

( )1 ,n n nf f t G f t+ = + ∆ ⋅ mit 0 Anfangswertf f=

4.1.1.1 Fehleranalyse Da wir für die Näherung des Funktionsverlaufes nur die lokale Ableitung ( )f t′ verwendet haben, geht der Fehler dieser Näherung mit 2t∆ gegen Null. Gleichermaßen verhält sicher der Fehler bei der einmaligen Anwendung der obigen Rekursionsformel. Dies ist der sog. lokale Fehler in einem Einzelschritt von t nach t t+ ∆ . Dieser Fehler entsteht durch die Vernachlässigung höherer Taylor-Terme. Um eine globale Fehleraussage treffen zu können, müssen die gesamten lokalen Fehler addiert werden. Dies ist der sog. globale Fehler bei der Berechnung der Lösung der Differentialgleichung im gesamten Lösungsintervall 0[ , ]t T . Dieser Fehler kann meist nicht exakt berechnet werden. Jedoch kann häufig eine Fehlergrenze abgeleitet werden. Zusätzlich tritt noch ein Rundungsfehler auf, der durch die Ungenauigkeit der numerischen Berechnungen im begrenzten Zahlenvorrat bedingt ist.

Ableitung einer globalen Fehlergrenze Wir definieren den globalen Fehler der n Integrationsschritten durch

( )n n ne f t f= −

Dabei ist ( )nf t der exakte analytische Wert der Lösung und nf ist der durch das Vorwärts-Euler-Verfahren numerisch bestimmte Näherungswert. Eine Taylorentwicklung der exakten analytischen Lösung ergibt

( ) ( ) ( )( ) ( )2

1 2, ''tn n n n nf t f t t G f t t f t∆

+ = + ∆ ⋅ + ⋅ mit 1n n nt t t +< < .

Gleichzeitig ergibt sich die Entwicklung der numerischen Lösung zu

( )1 ,n n n nf f t G f t+ = + ∆ ⋅

Daraus folgt


( )( ) ( )( ) ( ) ( )

( )( ) ( )( ) ( ) ( )

( )( ) ( )( )

( )

2

2

2

1 1 1

2

2

2

,

, , ''

, ,''

, , ''

n

n

n n

n n n

tn n n n n n n

e

n n n n tn n n n

n ne

n n n n tn n

n n

G f tf

e f t f

f t f t G f t t G f t f t

G f t t G f te t f t f f t

f t f

G f t t G f te t e f t

f t f

+ + +

∆

∆

∆

∂∂

= −

= − + ∆ ⋅ − + ⋅

− = + ∆ ⋅ − + ⋅ −

−= + ∆ ⋅ + ⋅

−

( )n

Mit Hilfe des Mittelwertsatzes lässt sich dies für kontinuierliche Funktionen als

( ) ( )2

1 2, ''tn n n n n nfe e t G f t e f t∂ ∆

+ ∂= + ∆ ⋅ + ⋅

mit ( )n n nf f f t< <

schreiben. Für "vernünftige" physikalische Systeme gilt

( ) ( ), '' , 0 : KonstantenG f t M f t K M Kf∂

≤ ≤ >∂

.

Dann lässt sich der globale Fehler zu

( ) 2

1 21 tn ne tM e K∆

+ < + ∆ +

abschätzen. Durch Induktion folgt dann

( ) 21 1n tKn Me C tM C ∆ ≤ + ∆ − =

Demnach ist der globale Fehler von 1. Ordnung in t∆ .

Beweis: da ( )0 0f t f= und 0 0e = gilt ( )∗∗∗ für 0n = Induktion von n auf 1n + : von oben gilt: ( ) 2

1 21 hn ne hM e K+ < + +

( ) ( ) ( ) ( )2 211 2 21 1 1 = 1 1n nh h

ne hM C hM K C hM hM K++

≤ + + − + + − + +

mit 2

2hChM K= erhalten wir: ( ) 1

1 1 1nne C hM +

+ ≤ + −

aus 1 für 0 folgt 1x hMx e x hM e+ ≤ ≥ + ≤ ( )1 n nhMhM e+ ≤ aus der Anwendung auf Behauptung ( )( )1 1n

ne C hM ≤ + − resultiert: ( ) ( )( )0

2 21 1nt t MnhMhk hkn M Me e e −≤ − = −

globaler Fehler von Euler ist ( )O h 1. Ordnung Wenn Rundungsfehler in die Fehlerbetrachtung einbezogen werden ist Fehlerentwicklung komplizierter, da der Rundungsfehler nahezu unabhängig von t∆ mit der Anzahl der Integrationsschritte n steigt.


Schrittweite ∆t

Fehler

Diskretisierungsfehler Rundungsfehler

Gesamt

4.1.1.2 Stabilitätsanalyse Die Stabilitätseigenschaften des Verfahrens werden wir anhand von zwei einfachen Beispielen untersuchen.

Beispiel 1 Zuerst betrachten wir das Verhalten des harmonischen Oszillators

( ) ( )2''f t f t= −ω

Zur numerischen Lösung schreiben wir die Differentialgleichung 2. Ordnung in ein System von Differentialgleichungen 1. Ordnung um. Dabei wählen wir eine besondere Form der Umschreibung, indem sog. konjugierte Variablen eingeführt werden. Dies führt zu einer besonders symmetrischen Form des Differentialgleichungssystems 1. Ordnung.

( ) ( ) ( ) ( )

( ) ( )( ) ( )

'

''

p t f t q t f t

q t p tp t q t

= = ω⋅

= ω⋅= −ω⋅

Bemerkung Alternativ könnte ( ),p q auch als komplexwertige Funktion ( ) ( ) ( )z t q t ip t= + ge-schrieben werden, wodurch die Differentialgleichung 2. Ordnung mit reellen Lösungsvariablen zu einer Differentialgleichung 1. Ordnung mit komplexer Lösungs-variable transformiert wird.

( ) ( ) ( )z t q t ip t= + DGL ( ) ( )'z t i z t= − ω

Das obige Euler-Vorwärts-Verfahren in Matrixschreibweise ergibt für die Umschrei-bung in konjugierte Variablen

1

1

Îterationsmatrix M

1 ˆ1

n n n n n

n n n n n

q q p q qtt M

p p q t p p+

+

ω∆ = + ω⋅ ∆ ⋅ = = − −ω∆


Die Eigenwerte der Iterationsmatrix sind aus dem charakteristischen Polynom bestimmbar (mit E = Einheitsmatrix)

( )2 2 2

Num

ˆ ˆ0 1

1

M E t

i t

= − λ = − λ + ω ∆

λ = ± ω∆

Für die Differentialgleichungslösung bedeutet

Num 1λ >

bei jedem Zeitschritt eine Verstärkung um einen konstanten Faktor. Dem entspricht ein exponentielles Anwachsen der Lösung.

Phasen- bzw. Zustandsdiagramm Die Variablen p und q werden als die Zustandsvariablen des Systems bezeichnet und können interpretiert werden als:

pot( ) ( ) ~q t f t E= ω

kin( ) ( ) ~ ~ Impulsp t f t E′=

Damit ist der Zustand des Systems durch diese beiden Variablen vollständig beschrieben und die Lösungstrajektorie lässt sich in diesem sog. Phasenraum grafisch visualisieren.

1

2 3

exakte analytische Lösung

Euler- Vorwärts-Lösung

p~sqrt(Ekin)

q~sqrt(Epot)

Veranschaulichung der linearen Extrapolation durch die Vorwärts-Ableitungs-Approxi-mation des Euler-Vorwärts-Verfahrens im Phasenraum.

Ein Vergleich mit der analytischen Lösung ergibt

( ) ( )0 i tf t f e± ω= ⋅

mit den Eigenwerten

Analyti te± ω∆λ =

d.h.

Analyt 1λ = Betrag ( ) ( )0 const.z t z= = (Energieerhaltung)


Hier zeigt sich die Abweichung, der numerischen von der analytischen Lösung. Im numerischen Fall ist aufgrund des zu großen Eigenwertes die Energieerhaltung nicht mehr gewährleistet. In einem Phasenraumdiagramm stellt sich dieses Phänomen folgendermaßen dar

Phasenraumdiagramm von analytischer (schwarz) und numerischen Lösungen mit dem Euler-Vorwärts-Verfahren für verschiedenen Schrittweite t∆ (je größer die Schrittweite, um so stärker ist das „Herausspiralen“)

Obwohl das Verfahren instabil ist, stellt es für hinreichend kleine Zeitschritte eine gute Lösung dar, denn mit

( )2Analyt Num O tλ − λ = ∆

wird die Konsistenzforderung erfüllt (konvergiert für 0t∆ → gegen exakte Lösung).

Beispiel 2 In einem zweiten Beispiel werden wir uns mit der weiter oben bereits erwähnten Differentialgleichung 1. Ordnung beschäftigen

( )( )d f t f td t

= −γ ⋅

Das Euler-Vorwärts-Verfahren liefert hier

( )1

1n n n

n

f f t ft f

+ = − γ∆ ⋅

= − γ∆

mit dem Eigenwert

Num 1 tλ = − γ∆

Die analytische Lösung lautet

( ) ( )0 tf t f e−γ= ⋅


mit dem Eigenwert

Analytte−γ∆λ =

Für kleine Zeitschritte wird auch hier die Konsistenzforderung erfüllt

( )2Analyt Num O tλ − λ = ∆

Allerdings hat der Eigenwert Nλ der numerischen Lösung für

1tγ∆ >

das falsche Vorzeichen. Dies führt zu einem Vorzeichenwechsel der numerischen Lösung in jedem Integrationsschritt und damit zu künstlichen Oszillationen, wenn die Integrationsschrittweite zu groß gewählt wird. Für

2tγ∆ >

ist

Num 1λ >

und die Lösung würde zusätzlich zu den künstlichen Oszillationen in jedem Integrationsschritt anwachsen (obwohl die exakte Lösung abklingt), was sich als numerische Instabilität darstellt. Aufgrund der bisherigen Feststellungen ist das Euler-Vorwärts-Verfahren zur Lösung von Differentialgleichungen nicht besonders gut geeignet, da die Lösungen im Allgemeinen dazu neigen, instabil zu werden und auch die Konvergenzordnung der Lösung nicht sehr hoch ist. Deswegen werden wir nun versuchen, diese Probleme durch die Einführung verbesserter Verfahren zu beheben.

Implementierung Euler-Vorwärts

Implementieren Sie das Euler-Vorwärts-Verfahren in MATLAB. Dabei soll die Differentialgleichung

dy c ydt

= ⋅

numerisch gelöst werden. Stellen Sie das Ergebnis zusammen mit der analytischen Lösung graphisch dar und testen Sie verschiedene Schrittweiten der numerischen Integration und deren Einfluss auf die Eigenschaften der Lösung.

4.1.2 Rückwärts-Euler-Verfahren Anstelle des im Vorwärts Euler verwendeten rechtsseitigen Differentialoperators werden wir hier den linksseitigen Differentialoperator verwenden und untersuchen, welche Lösungseigenschaften sich daraus ergeben. Analoges Vorgehen wie oben liefert


( ) ( )( )( ) ( )( )

( ) ( ) ( )( )

,

,

,

t

f t G f t t

D f t G f t t

f t f t tG f t t

t

∆

′ =

= − − ∆

=∆

Nun wird die Gleichung um einen Zeitschritt verschoben, was einer Substitution der Zeitvariable durch t t t→ + ∆ entspricht.

( ) ( ) ( ) ( )( )' ,f t t f t

f t t G f t t t tt

+ ∆ −+ ∆ ≈ ≈ + ∆ + ∆

∆

Das Umschreiben auf diskretisierte Funktionswerte und Umstellen der Gleichung liefert das Rückwärts-Euler-Verfahren

( )1 1,n n nf f tG f t t+ += + ∆ + ∆

Eigenschaften Ähnlich wie der Vorwärts-Euler konvergiert auch dieses Verfahren in erster Ordnung mit t∆ . Da jedoch 1nf + nicht bekannt ist, kann auch ( )1,nG f t t+ + ∆ im Allgemeinen nicht direkt berechnet werden. Für lineare Differentialgleichungssysteme ist die daraus notwendig werdende Matrixinversion eines linearen Gleichungssystems oftmals gut numerisch handhabbar. Für nichtlineare Differentialgleichungssysteme muss man jedoch auf die iterative Lösung des entstehenden nichtlinearen Gleichungssystems zurückgreifen (Nullstellensuche).

Stabilitätsanalyse Um einen Vergleich mit dem Vorwärts Euler Verfahren zu ermöglichen, werden wir an dieser Stelle nochmals den harmonischen Oszillator betrachten. Von oben folgt

1 1

1 1

n n n

n n n

q q t pp p t q

+ +

+ +

= + ω∆ ⋅

= − ω∆ ⋅

in Matrixschreibweise

1

1

11

n n

n n

q qtp pt

+

+

−ω∆ = ω∆

auflösen nach den zukünftigen Werten, d.h. Invertierung der Matrix

12 2

1

1111

n n

n n

q qtp ptt

+

+

+ω∆ = −ω∆+ ω ∆

Die Eigenwerte der Iterationsmatrix sind


Num 2 21

1i t

t± ω

λ =+ ω ∆

Da

Num 1 , 0tλ < ∀∆ ω >

ist das Verfahren unbedingt stabil, allerdings ist das numerische System dissipativ, d.h. die Lösung wird gedämpft, und die Systemeigenschaften wurden durch den numerischen Lösungsansatz verändert. Ähnlich wie beim Euler-Vorwärts ist also auch hier die Energieerhaltung nicht gewährleistet.

1

2 3


p

q

Euler-Rückwärts- Lösung

Veranschaulichung der linearen Extrapolation durch die Rückwärts-Ableitungs- Approximation des Euler-Rückwärts-Verfahrens im Phasenraum.

4.1.3 Crank-Nicolson-Verfahren Eine geschickte Kombination aus Vorwärts-Euler und Rückwärts-Euler im Crank-Nicolson-Verfahren ermöglicht die Gewährleistung der Stabilität bei gleichzeitiger Energieerhaltung. Dies ist vergleichbar mit der Einführung des zentralen Differential-operators zur Verbesserung der Konvergenzeigenschaften des diskreten Differential-operators. Aus dem Vorwärts-Euler

( )1 ,n n nf f t G f t+ = + ∆ ⋅

und dem Rückwärts-Euler

( )1 1,n n nf f tG f t t+ += + ∆ + ∆

wird durch Addition und Division durch 2 das Crank-Nicolson-Verfahren

( ) ( )( )1 1, ,2n n n ntf f G f t G f t t+ +

∆= + ⋅ + + ∆

Wie beim Rückwärts-Euler-Verfahren besteht das Problem, ( )1,nG f t t+ + ∆ zu bestimmen, obwohl 1nf + nicht bekannt ist. Es resultiert deshalb wie schon beim Rückwärts Euler ein implizites Verfahren. Allerdings konvergiert dieses Verfahren in 2. Ordnung mit t∆ .


Stabilitätsanalyse Beispiel: harmonischer Oszillator Von oben folgt

( )( )

1 12

1 12

tn n n n

tn n n n

q q p p

p p q q

ω∆+ +

ω∆+ +

= + ⋅ +

= − ⋅ +

in Matrixschreibweise

12 2

12 2

1 11 1

t tn n

t tn n

q qp p

ω∆ ω∆+

ω∆ ω∆+

− = −

Invertieren ergibt

( )( )

( )

221

2 21 2 2

M

111 1

tn n

t tn n

tq qp pt

ω∆+

ω∆ ω∆+

− ω∆ = + −ω∆ −

Die Eigenwerte der Iterationsmatrix M sind

( )( )

22 2

N 222

1 111

t t

tt

i ii

ω∆ ω∆

ω∆ω∆

± ±λ = =

+

mit

N 1 , 0tλ = ∀∆ ω >

Demnach findet weder eine zusätzliche Verstärkung noch eine zusätzliche Dämpfung des Systems statt, die gewünschte Energieerhaltung ist somit gewährleistet. Die Approximation der Ableitung durch den zentralen Differenzenquotienten hinterlässt deshalb lediglich einen Phasenfehler in der numerischen Lösung.

1

2 3


p

q

Crank-Nicholson- Lösung

Veranschaulichung der linearen Extrapolation durch die zentrale Ableitungs- Approximation des Crank-Nicolson-Verfahrens im Phasenraum.


4.1.4 Alpha-Verfahren Die Lösungseigenschaften der bisher untersuchten numerischen Integrations-verfahren für gewöhnliche Differentialgleichungen sind im Allgemeinen stark vom jeweiligen Problem abhängig. Deshalb werden nicht immer die an den obigen Beispielen demonstrierten Eigenschaften der Verfahren erreicht. Um dennoch die Eigenschaften Stabilität und Genauigkeit kontrollieren zu können, bietet sich folgen-des Vorgehen an. Eine Verallgemeinerung der eben vorgestellten Methoden ist das Alpha-Verfahren, dabei ist das Verhältnis von Vorwärts-Euler (explizites Verfahren) zu Rückwärts-Euler (implizites Verfahren) variabel. Das Verhältnis zwischen Stabilität und Genauigkeit kann dadurch dem Problem angepasst werden.

( ) ( ) ( )1 1, 1 ,n n n nf f t G f t G f t t+ + = + ∆ α ⋅ + − α ⋅ + ∆

kontinuierlicher Übergang zwischen: • 1α = entspricht Vorwärts-Euler

− rein explizit instabil − konvergiert in 1. Ordnung mit t∆

• 0.5α = entspricht Crank-Nicolson-Verfahren − gemischt explizit/implizit marginal stabil − konvergiert in 2. Ordnung mit t∆

• 0α = entspricht Rückwärts-Euler − rein implizit stabil − konvergiert in 1. Ordnung mit t∆

Damit kann durch eine geeignete Wahl des Koeffizienten α im Intervall [0,1] ein an das jeweilige Problem angepasster Kompromiss zwischen Stabilität und Genauigkeit werden

4.1.5 Explizite Runge-Kutta-Verfahren Um eine Lösung der AWA im Einzelschrittintervall t∆ zu erhalten, werden bei den Eulerverfahren lediglich Informationen am Anfang oder Ende des Integrationsinter-valls jedes einzelnen Diskretisierungsschrittes verarbeitet. Es gibt viele Gründe zur Suche nach einer verbesserten numerischen Lösung einer AWA. Eulerverfahren sind, verglichen mit anderen Verfahren bei gleicher Schrittweite, nicht sehr genau (Fehler:

2( )O t∆ ) und es gibt, wie wir bereits gesehen haben, zudem Probleme mit der Stabilität der Lösung. Wir werden in diesem Abschnitt deshalb das Runge-Kutta-Verfahren kennenlernen, welches heute die Standardmethode zur Lösung einer AWA ist.


Runge-Kutta-Verfahren 2. Ordnung Um zu vermeiden, dass sich die numerische Lösung durch die lineare Extrapolation, ausgehend vom Intervallanfang, immer weiter von der analytischen Lösung entfernt, nutzen wir die in der untenstehenden Abbildung gezeigte Idee. Die Funktion im Intervall [ ]1,n n nt t t t+ = + ∆ wird dabei nicht durch die Extrapolation einer Tangente im Startpunkt approximiert, sondern in einem Zwischenschritt wird die Steigung in der Mitte des Intervalls abgeschätzt, welche dann zur Approximation im gesamten Intervall dient. Von der Idee entspricht dies, dem Crank-Nicolson-Verfahren, da auch dort der Anstieg in der Mitte des Einzelschrittintervalls berechnet wurde. Im Gegensatz zum impliziten Crank-Nicolson-Verfahren wird beim Runge-Kutta-Verfahren die Ablei-tungsbildung in der Intervallmitte durch einen expliziten Integrationsschritt abge-schätzt.

Prinzip des Euler-Vorwärts-Verfahrens (links) und des Runge-Kutta-Verfahrens zweiter Ordnung (rechts)

Die beschriebene und in der Abbildung gezeigte Idee lautet in Formeln

1

2 1

31 2

( , )1 1,2 2

( )

n n

n n

n n

k t G f t

k t G f k t t

f f k O t+

= ∆ ⋅

= ∆ ⋅ + + ∆

= + + ∆

Das Verfahren hat einen Restfehler 3( )O t∆ in jedem Integrationsschritt, der mit 3t∆ gegen Null geht. Insgesamt ergibt sich damit eine Genauigkeitsordnung von 2 für die Berechnung der Lösung über dem gesamten Integrationsintervall. Die Erhöhung der Genauigkeit erfordert dabei zwei Zwischenschritte zur Abschätzung von 1k und 2k in der Gesamtberechnung. Dies verdeutlichen die folgenden Codeschnipsel. Links ist der Kern einer Implementierung des Runge-Kutta-Verfahrens, rechts der des Eulerverfahrens.


(Runge-Kutta) for i=1:N k1=h*f(t,y); k2=h*f(t+0.5*h,y+0.5*k1); y=y+k2; t=t+h; Y=[Y,y]; T=[T,t]; end

(Euler) for i=1:N y=y+h*f(t,y); t=t+h; Y=[Y,y]; T=[T,t];

End

Zur Illustration der mit dem Runge-Kutta-Verfahren 2. Ordnung erzielbaren Lösungs-genauigkeit zeigt die nachfolgende Abbildung die Lösung der Differentialgleichung

'y y= mit (0) 1y = auf analytischem Weg, mit Hilfe des Euler-Vorwärts-Verfahrens und mittels des Runge-Kutta-Verfahrens 2. Ordnung bei gleicher Integrations-schrittweite der beiden verglichenen numerischen Verfahren.

Lösung der Anfangswertaufgabe 'y y= , (0) 1y = mittels verschiedener Lösungs-methoden.

Schreiben sie eine Funktion zur graphischen Ausgabe der Lösung für den harmonischen Oszillator

( ) ( )2''f t f t= −ω .

Die Lösung soll mittels Runge-Kutta- und Euler-Methode gefunden werden und der analytische Funktionsverlauf soll vergleichend dargestellt werden. Der Funktion sollen als Parameter die Zeitspanne, die Anfangsbedingung sowie die Anzahl der zu berechnenden Punkte im Intervall übergeben werden.

Runge-Kutta-Verfahren 4. Ordnung und 4. Stufe Der Fehler des im vorherigen Abschnitt behandelten Runge-Kutta-Verfahrens 2. Ordnung konvergiert mit dem Fehlerterm (2. Ordnung genau) noch recht langsam


gegen das exakte Ergebnis, sodass wir das Verfahren im Folgenden weiter optimieren werden, um eine bessere Näherung der exakten (analytischen) Lösung zu erhalten. Eine Möglichkeit, den Fehlerterm auf 5( )O t∆ (4. Ordnung genau) zu verkleinern, bietet das hier vorgestellte Runge-Kutta-Verfahren 4. Ordnung. Dies ist eines der am häufigsten benutzten Integrationsverfahren für gewöhnliche Differentialgleichungen und wird häufig auch als "das klassische Runge-Kutta-Verfahren" bezeichnet.

Schematische Darstellung der Idee des Runge-Kutta-Verfahrens vierter Ordnung (4. Stufe). Um von ny auf 1ny + zu schließen, berechnet man in 4 Zwischenschritten Abschätzungen der Ableitungen am Anfang, Mittelpunkt (zweimal) und Ende des Intervalls.

Die Idee des Runge-Kutta-Verfahrens 4. Ordnung ist, in jedem Integrationsschritt die Ableitung an vier Punkten (dem Intervallanfangspunkt, zweimal in der Intervallmitte und dem Intervallendpunkt) abzuschätzen, um so von ny auf 1ny + zu extrapolieren.

( )

1

2 1

3 2

4 3

51 2 3 41

( , )1 1,2 21 1,2 2

,

( ).6 3 3 6

n n

n n

n n

n n

n n

k t G f t

k t G f k t t

k t G f k t t

k t G f k t tk k k kf f O t+

= ∆ ⋅

= ∆ ⋅ + + ∆ = ∆ ⋅ + + ∆

= ∆ ⋅ + + ∆

= + + + + + ∆

Eigenschaften • 4 Zwischenschritte Verfahren 4. Stufe

• Restfehler im einzelnen Integrationsschritt 5( )O t∆ 4. Ordnung genaues Ergebnis der Gesamtintegration mit 1/ t∆ Schritten Verfahren 4. Ordnung (p=4)

Verallgemeinerung des Runge-Kutta-Verfahrens für verschiedene Ordnungen und Stufenzahlen Allgemeine Berechnungsformel mit der Stufenzahl s


11

s

n n j jj

f f t b k+=

= + ∆ ∑ .

mit

( , )j jj n nk G f t=

mit

jn n jt t c t= + ∆ und

1

1

jj

n n jl ll

f f t a k−

=

= + ∆ ∑

Butcher-Schema zur Festlegung der Koeffizienten jb , jc und jla

1 11 12 1

2 21 22 2

1 2

1 2

0 0 00 0

A

0

s

s

T

s s s ss

s

c a a ac a a a

c

b c a a ab b b

= = == =

==

Beispiele für verschiedene Verfahren • 1. Ordnung (Euler-Vorwärts-Verfahren): 1p = , 1s =

(mit p = Genauigkeitsordnung)

0 01

• 2. Ordnung: 2p = , 2s = (wie oben)

0 0 01 1 02 2

0 1

• 2. Ordnung (Heun-Verfahren): 2p = , 2s =

0 0 01 1 0

1 12 2

• 4. Ordnung (klassische Runge-Kutta-Verfahren): 4p = , 4s = (wie oben)


01 12 21 102 21 0 0 1

1 1 1 16 3 3 6

Eigenschaften • maximal erzielbare Genauigkeitsordnung p s≤

Stufenzahl wächst schneller als Ordnung; kein Verfahren mit p s= für 5s ≥

• höhere Ordnungen nur bei hinreichend glatten Funktionen vorteilhaft bei gleicher Genauigkeit größere Schrittweite möglich

4.1.6 Implizite Runge-Kutta-Verfahren Allgemeine Berechnungsformel mit der Stufenzahl s

11

s

n n j jj

f f t b k+=

= + ∆ ∑ .

mit

( , )j jj n nk G f t=

mit

jn n jt t c t= + ∆ und

1

sj

n n jl ll

f f t a k=

= + ∆ ∑ Summation bis s statt j

Butcher-Schema zur Festlegung der Koeffizienten jb , jc und jla

1 11 12 1

2 21 22 2

1 2

1 2

s

s

s s s ss

s

c a a ac a a a

c a a ab b b

Eigenschaften • maximal erzielbare Genauigkeitsordnung 2p s≤

• bessere Stabilität als explizite Runge-Kutta-Verfahren

4.1.7 Schrittweitensteuerung Ziel: weitere Optimierung des Fehlers durch Wahl einer geeigneten Schrittweite t∆


Globaler Fehler ( ) ( ) ( )N N Ne t f t f t∆ = − ∆ entsteht durch Überlagerung lokaler

Fehler. Lokale Fehler ( )nl t∆ :

• hängt von t∆ ab und schwankt sehr mit n • flache (langweilige) Lösungsgebiete nl klein

• hügelige (spannende) Lösungsgebiete nl groß

t

f

Zur Minimierung des lokalen Fehlers gibt es verschiedene Lösungsansätze: • wähle Schrittweite so klein, dass Fehler auch im „schlimmsten Gebiet“ hinreichend

klein steigender Rechenaufwand und Zunahme des Rundungsfehlers mit kleinerer Schrittweite

• wähle Schrittweite variabel, kleine Schrittweite in kurzwelligen, große Schrittweite in langwelligen Gebieten weniger Rechenaufwand und reduzierter Rundungsfehler

Schrittweitensteuerung ist bessere Strategie

( ) nt t n t∆ = ∆ = ∆ .

Ges.: Schätzung für lokalen Fehler, um Schrittweite lokal geeignet festzulegen ohne den Rundungs- und Diskretisierungsfehler zu groß werden zu lassen

Schrittweite ∆t

Fehler

Rundungsfehler

pt∆

1t∆

globaler Diskretisierungs- fehler

Gesamtfehler 1pt t∆ + ∆


(A) physikalische Nebenbedingungen, z.B. Energieerhaltung oder Hamiltonien-Erhaltung (Vorsicht: bei Energieerhaltenden numerischen Verfahren kann diese Nebenbedingung nicht angewandt werden)

(B) Vergleich eines Schritts vom Punkt t nach t t+ ∆ mit Schrittweite t∆ bzw. der halben Schrittweite 0.5 t⋅ ∆ (step doubling):

( ) ( ) ( )( ) ( )1 1 1

1

0.51 2

n n pn p

f t f tl t O t

t+ + +

+ −

∆ − ∆∆ = + ∆

∆ ⋅ − (C) Vergleich eines Schritts vom Punkt t nach t t+ ∆ für zwei Verfahren

unterschiedlicher Ordnung (Fehlberg-Methode):

( )( ) ( ) ( ) ( ) ( )

111 1

1

p ppn n

nf t f t

l t O tt

+++ +

+

∆ − ∆∆ = + ∆

∆

Wenn geschätzter Fehler im Toleranzintervall

( )1 010 nl t+ε

≤ ∆ ≤ ε ε >

ok, sonst Schrittweite anpassen

( )1

1

2 11

p

n nn

t tl

+

+ ++

ε∆ ε = ∆ ρ ⋅

mit Sicherheitsfaktor 1ρ < (meist 0.5ρ = )

Bemerkung Weit verbreitet ist die sog. Cash-Karp Methode (verbesserte Fehlberg-Methode). Dies ist ein Runge-Kutta-Verfahren 5. Ordnung (6. Stufe), in welches ein Runge-Kutta-Verfahren 4. Ordnung eingebettet ist. D.h. das Butcher-Schema der 4. Ordnung ist in Verfahren mit 5. Ordnung enthalten und es entsteht geringer zusätzlicher Rechen-aufwand für die Fehlerabschätzung nach Variante (C).

4.1.8 Steife Probleme Steifes Problem = Anfangswertproblem höherer Ordnung (mehr als eine gekoppelte DGL 1. Ordnung) mit mindestens zwei stark unterschiedlichen Skalen der Veränder-lichkeit der verschiedenen abhängigen Variablen (z.B. xf und yf ) von unabhängiger

Variable (z.B. t ), wobei die schnell veränderliche Komponente recht "glatt" verläuft

Beispiel Ein System besteht z.B. aus zwei sehr unterschiedlichen Teilsystemen 1 und 2, die jedoch gemeinsam die Gesamtantwort bestimmen (hier triviale Summation):

1) 11 1

(t) ( )dy y tdt

= −µ mit der Teillösung 1 1 1( ) (0)exp( )y t y t= −µ


2) 22 2

(t) ( )dy y tdt

= −µ mit der Teillösung 2 2 2( ) (0)exp( )y t y t= −µ

mit der Gesamtantwort 1 2( ) ( ) ( )y t y t y t= +

Wenn nun 2 1µ µ , dann erfordert das Stabilitätskriterium des z.B. Euler-Vorwärts-Verfahrens ( 2 2tµ ∆ < ) eine sehr kleine Schrittweite, die im Lösungsteil 1 möglicher-weise bereits zu großen Rundungsfehlern beiträgt.

Beispiel für den Verlauf der numerischen Lösung einer steifen Anfangswertaufgabe. Die numerische Lösung (gepunktet) wird aufgrund der bereits abgeklungenen Lösungs-komponente 2y (physikalisch nicht mehr maßgeblich) instabil und verhindert eine

akkurate Berechnung der physikalisch maßgeblichen Lösungskomponente 1y .

Dilemma Steifer Probleme Welche Schrittweite soll bei der numerischen Integration gewählt werden? • Stabilität: erzwingt kleine Integrationsschrittweite • Genauigkeit: erlaubt bzw. erfordert zur Minimierung des Rundungsfehlers große

Schrittweite

Lösungsmöglichkeiten • implizite Verfahren mit unbedingter Stabilität • Gleichungen immer geeignet skalieren, damit Schrittweitensteuerung in allen

Dimensionen gleichmäßig greift • alle numerischen Operationen und Zahlendarstellungen mit hoher Genauigkeit

ausführen, um Einfluss des Rundungsfehlers bei für Stabilität erforderlicher großer Schrittzahl zu begrenzen

4.2 Randwertaufgaben (RWA) bisher: • Anfangswertaufgaben (AWA)


• Lösung einer Dgl., die am Anfang des Integrationsintervalls vorgegebene Anfangswerte annimmt

jetzt: • Lösung von Randwertaufgaben (RWA): Lösung von DGL die am Rand des

Integrationsintervalls vorgegebene Randwerte annimmt (Randbedingungen = RB) • Existenz und Eindeutigkeit von Lösungen von DGL und Randwerten abhängig Bemerkungen: • für nichtlineare Dgl. noch komplizierter, da mehrere isolierte Lösungen möglich

sind • Art der RB, die bei RWA zu (eindeutigen) Lösungen führen, sind oft nicht allgemein

bekannt, aber können meist „physikalisch“ begründet werden

Beispiel Wärmeleitungsgleichung • dünner Stab der Länge: 1L = • eingespannt zwischen zwei Körpern mit Temperaturen: 1µ und 2µ

• Wärmeleitfähigkeit des Stabmaterials: ( ) 0k x ≥

• Dichteverteilung innerer Energiequellen und Senken: ( )f x

• Wärmeaustausch mit Außenraum: ( ) 0q x ≥

DGL

( ) ( )( ) ( ) ( ) ( ) 0k x y x q x y x f x′′− + + = (*)

mit den Randwerten

( ) ( )1 20 1y y= µ = µ

µ1 µ2

4.2.1 Methode der finiten Differenzen • Anwendung bewährter Prinzipien von AWA • Approximation des kontinuierlichen Problems auf einem (z.B. gleichabständigen)

Gitter

: 0,1, , , , b ah i Nx x a ih i N h N−ω = = = + = = ∈

Beispiel: Anwendung der Methode auf Wärmeleitungsgleichung von oben


Ausdifferenzieren des ersten Terms der Differentialgleichung (*):

( )( ) ( ) ( ) ( ) ( ) ( )k x y x k x y x k x y x′′ ′ ′ ′′− = − −

Ersetzen der Ableitungen durch diskrete Differentialoperatoren (hier zentrale Differenzenquotienten, um Symmetrie des Problems zu erhalten)

( ) ( ) ( )

( ) ( ) ( )2

2

h

h

k x h k x hD k x

hy x h y x h

D y xh

+ − −=

+ − −=

( ) ( ) ( ) ( )22

2h

y x h y x y x hD y x

h+ − + −

=

Einsetzen in Wärmeleitungsgleichung (*):

( ) ( ) ( ) ( ) ( ) ( ) ( ) ( )

( ) ( ) ( )2

22 2

0

y x h y x y x h k x h k x h y x h y x hk x

h h hq x y x f x

+ − + − + − − + − −− − ⋅

+ + =

Übergang auf diskrete Gitterpunkte:

1 1 1 1 1 12

2 02 2

i i i i i i ii i i i

y y y k k y yk q y fh h h

+ − + − + −− + − −− − ⋅ + + =

mit Randbedingungen

0 1 2Ny y= µ = µ

Einführen von Abkürzungen:

( )( )

11 14

11 14

2

i i i i

i i i i

i i i i

a k k k

b k k k

c a b q h

+ −

+ −

= − −

= + −

= + +

Dann wird die diskrete Wärmeleitungsgleichung zu

( )21

1 1 0i i i i i i iha y c y b y f− +− + − + =

oder in Matrixschreibweise zu 2

1 1 1 1 1 12

2 2 2 2 2

22 2 2 2 2

21 1 1 1 1 2

0

N N N N N

N N N N N

c b y h f aa c b y h f

a c b y h fa c y h f b

− − − − −

− − − − −

− − µ − − ⋅ + = − −

− − µ

• beachte: Der Anfangspunkt 0y und der Endpunkt Ny sind nicht Bestandteil des Lösungsvektors, da sie bereits durch die Randbedingungen festgelegt sind.


• In jeder Gleichung treten drei benachbarte Gitterpunkte auf 1 1, ,i i ix x x− +

− Bezeichnung als Dreipunkt-Differenzen-Schema − Koeffizientenmatrix ist tridiagonal einfache Lösung

• Problem: keine exakte Lösung, da " 0= ", eigentlich " 0≈ " • Ausweg: Relaxations-Methode

− iterative Verbesserung eines „geratenen“ Startvektors mittels Minimierungs-verfahren, z.B. Newton

− Wahl eines geeigneten Minimierungskriteriums, z.B. ( ii

err Y= ∆∑ )

− Wahl eines „guten“ Startvektors aus Schießverfahren (siehe unten)

4.2.2 Schießverfahren • Umwandlung von RWA in parameterabhängige AWA • Lösung des AWA mit verschiedenen Parametern bis der Parameter gefunden ist,

bei dem die AWA auch die RWA löst

Beispiel Randwertproblem

( ) ( ) ( )'' 2 0 0 1 0 1 1 1y x x y y+ = ≤ ≤ = =

Ersetzen der zweiten Randbedingung Anfangswertaufgabe

( ) ( ) ( )'' 2 0 0 1 ' 0y x y y S+ = = = ( S ist unbekannter Parameter)

mit parameterabhängiger Lösung

( ),y x S

ges.: Parameter *S mit

( ) ( )*1, 1 1y S y= =

( )*,y x S löst auch Randwertaufgabe.

• lineare Dgl. Bestimmung von S ∗ aus linearer Gleichung

• nichtlineare Dgl. iterative Berechnung von S ∗ z.B. mit Sekantenverfahren


• Genauigkeit abhängig von Integrationsverfahren zur Lsg. der AWA • Anwendung problematisch wenn ( ),y x S stark parameterabhängig ist oder

Singularitäten aufweist Verbesserte Schießverfahren • Zerlegung des Integrationsintervalls 0 1x x x≤ ≤ in l Teilintervalle und Einführung

von Stetigkeitsbedingungen an Teilintervallgrenzen • Schießen aus zwei Richtungen (von beiden Intervallgrenzen), z.B. falls

Singularitäten an beiden Intervallgrenzen


5. Partielle Differentialgleichungen • zentrale Rolle in Physik • Größen hängen von mehreren unabhängigen Variablen ab • allgemeine PDE 2.Ordnung

2 2 2

2 2 0f f f f fp q r s t u f vx x y y x y

∂ ∂ ∂ ∂ ∂+ + + + + ⋅ + =

∂ ∂ ∂ ∂ ∂ ∂

Prinzipiell werden folgende Typen von partiellen Differentialgleichungen unterschieden

− 1. 2 4q pr< : elliptische PDE

− 2. 2 4q pr= : parabolische PDE

− 3. 2 4q pr> : hyperbolische PDE

physikalische Klassifikation − 1. elliptisch: Poisson-Gleichung (Elektrostatik, inkompressible Strömungen)

( )2 2

2 2 ,f ff x yx y

∂ ∂∆ = + = ρ

∂ ∂ − 2. parabolisch: Diffusionsgleichung oder Wärmeleitungsgleichung

2

2f f f ft x x x x x

∂ ∂ ∂ ∂ ∂λ ∂ = λ = λ + ∂ ∂ ∂ ∂ ∂ ∂ − 3. hyperbolisch: Wellengleichung

2 22

2 2 0f fct x

∂ ∂− =

∂ ∂ • zusätzlich zu den Gleichungen müssen immer die Randbedingungen spezifiziert

werden. • Existenz/Eindeutigkeit der Lösungen und Art der kompatiblen Anfangs-

/Randbedingungen sind nur in den einfachsten Fällen bekannt

Numerik Randwertprobleme erlauben eine statische Rechnung (Suche nach stationären Zuständen) und werden oft für elliptische PDEs angewendet.


Randwertproblem

Die Grenzen der Lösbarkeit von Randwertaufgaben sind primär durch den zur Verfügung stehenden Speicher und die benötigte Rechenzeit definiert. Für parabolische und hyperbolische PDEs werden eher Anfangswertprobleme gelöst, da diese einer dynamischen Rechnung angepasster sind.

Anfangswertproblem

Die Grenzen der Lösbarkeit von Anfangswertaufgaben werden vorrangig durch die Stabilität des verwendeten Algorithmus definiert.

Rand


5.1 Elementare Methoden zur Lösung von partiellen Differentialgleichungen (Finite-Differenzen-Methode für Anfangswertaufgaben)

Beispiel Diffusionsgleichung Das Anfangswertproblem lautet (parabolische Differentialgleichung)

2

2( , ) ( , )f x t f x t

t x∂ ∂

= λ∂ ∂

mit ( ) ( )0,0f x f x= und constλ =

Sowohl die exakte analytische Lösung dieser Gleichung als auch numerische Lösungsverfahren beruhen auf der Transformation der partiellen Differential-gleichung in eine gewöhnliche Differentialgleichung.

Exakte analytische Lösung Für dieses lineare und homogene Problem liefert ein Fourieransatz eine exakte analytische Lösung

( ) ( ) ( )12

ˆ, , expf x t f k t ikx dkπ

= ⋅∫

Ein Einsetzen in die partielle Differentialgleichung liefert die gewöhnliche Differential-gleichung

( ) ( )2ˆ , ˆ ,f k t

k f k tt

∂= −λ ⋅

∂

mit der Lösung

( ) ( ) ( )2ˆ ˆ, ,0 expf k t f k k t= ⋅ −λ

oder im Ortsraum (für eine Fourier-Komponente)

( ) ( )ˆ, ,0 exp( )exp( )f x t f k ikx t= γ

mit der Dispersionsrelation 2kγ = −λ ⋅

Lösungseigenschaften:

• Fourier-Mode mit Wellenzahl k klingt exponentiell mit Dämpfungsrate 2kλ ab (außer Gleichanteil mit 0k = )

• kurzwellige Moden (größeres k ) werden schneller gedämpft als langwellige (kleines k )

• Die allgemeine Lösung ist die lineare Superposition von Einzelmoden (Fourier-Komponente):

− Transformation der Ausgangsbedingungen ( ) ( )0 ,0f x f x= in das

Anfangsspektrum ( )ˆ ,0f k

− Lösung im k -Raum entsprechend ( ) ( ) 2ˆ ˆ, ,0 k tf k t f k e−λ ⋅= ⋅


− Rücktransformation der Lösung

( ) ( ) ( )1 ˆ, , exp2

f x t f k t ikx dk= ⋅π ∫

Numerische Finite-Differenzen-Lösung Für die numerische Finite-Differenzen-Lösung werden Raum und Zeit diskretisiert

: 1,2,...,jx x j x j J= = ⋅ ∆ = und : 1,2,...,nt t n t n N= = ⋅ ∆ =

( ) ( ): , ,njf f x t f j x n t= = ⋅ ∆ ⋅ ∆

Zusätzlich wird der eindimensionale Laplace-Operator als diskreter Differential-operator geschrieben, wobei vorerst nur der Ort diskretisiert wird

( ) ( ) ( ) ( ) ( ) ( )( )

1 12 22

2, , , j j j

xx x x

f t f t f tf x t D f x t D f x t

x+ −

∆ ∆

− +∂ → → = ∆

Die Differentialgleichung lautet dann

( ) ( ) ( )( )1 12

d2 ( )

dj

j j j

f tf t f t f t

t x + −λ

= − +∆

Mögliche Verfahren wären dabei (hier jeweils nur ein Zeitschritt notiert) • Vorwärts-Euler-Verfahren

( )11 12n n n n n

j j j j jtf f f f f

x+

+ −2

λ ⋅ ∆= + − +

∆

• oder Rückwärts-Euler-Verfahren

( )1 1 1 11 12n n n n n

j j j j jtf f f f f

x+ + + +

+ −2

λ ⋅ ∆= + − +

∆

• oder Leapfrog-Methode (symmetrische Zeit-Diskretisierung und dennoch explizit)

( )

( )

1 1

1 12

1 11 12

22

2 2

n nj j n n n

j j j

n n n n nj j j j j

f ff f f

t xtf f f f f

x

+ −

+ −

+ −+ −

− λ= − +

∆ ∆λ ⋅ ∆

= + − +∆


f

x

nf 1nf −

1jx − jx 1jx +

1nf +

Vorwärts-Euler (explizit)

f

x

Euler-Rückwärts (implizit)

f

x

nf 1nf −

1jx − jx 1jx +

1nf +

Leap-Frog Methode (explizit)

t

t

t


f

x

Crank-Nicholson (implizit)

Der diskrete Ortsdifferentialoperator für endliche Rechengebiete (bzw. auch mit periodischen Randbedingungen) lautet in Matrixschreibweise

( )

1 1

2 2

2

ˆ

2 1 (1)1 2 1

1 ˆ1 21

(1) 1 2

xx j

J J

D

f ff f

f Dx

f f

− − ∂ ≈ ⋅ = ⋅−

∆

−

Die Matrix D hat wieder die Struktur einer Tri-Diagonal-Matrix und realisiert einen expliziten Zeitschritt durch Matrixmultiplikation. Die mit "(1)" besetzten Ecken würden periodischen Randbedingen einer linearen Anordnung, d.h. einer kreis-förmigen Struktur, entsprechen und die einfach zu lösende Tri-Diagonal-Form zerstören.

Für eine günstige Darstellung sei 2t

xλ ⋅ ∆

α =∆

.

Das Vorwärts-Euler-Verfahren erster Ordnung in der Zeit und zweiter Ordnung im Ort lautet damit

( )

11 1 1

12 2 2

13 3 3

11 1 11

(1 2 ) ( )(1 2 )

(1 2 ) ˆ1

( ) (1 2 )

n n n

n n n

n n n

n n nJ J Jn n n

J J J

f f ff f f

a af f ft D

f f ff f f

+

+

+

+− − −+

− α α α α − α α − α

= = + ∆ ⋅ λ ⋅ α α α α − α

( )( )

1

0

ˆ1

ˆ1

n n

nn

f t D f

f t D f

+ = + ∆ ⋅ λ ⋅

= + ∆ ⋅ λ ⋅

für einen bzw. n Zeitschritte


Dementsprechend ergibt sich für das Rückwärts-Euler-Verfahren

( )

11 1

12 2

13 3

11 11

1 1

1

1 2 ( )1 2

1 2

( ) 1 2ˆ

ˆ1

n n

n n

n n

n nN Nn n

J J

n n n

n n

f ff f

a a f f

f ff f

f f t D f

t D f f

+

+

+

+− −+

+ +

+

+ α −α −α −α + α −α − + α −

= −α −α −α −α + α

= + ∆ ⋅ λ ⋅

− ∆ ⋅ λ ⋅ =

Da es sich um ein implizites Verfahren handelt, muss eine Matrixinversion vorgenommen werden

( ) 11 ˆ1n nf t D f−

+ = − ∆ ⋅ λ ⋅

Das aus den Euler-Verfahren folgende Crank-Nicholson-Verfahren ist demzufolge

( )1 1

11

ˆ2

ˆ ˆ1 12 2

n n n n

n n

tf f D f f

t tf D D f

+ +

−+

∆ ⋅ λ= + +

∆ ⋅ λ ∆ ⋅ λ = − +

5.2 Stabilitätsanalyse nach von Neumann Beispiel: Diffusionsgleichung

( ) ( )2

02( , ) ( , ) ,0f x t f x t f x f x const

t x∂ ∂

= λ = λ =∂ ∂

Eigenschaften der analytischen Lösung (siehe oben): alle Ortsfrequenzen klingen ab nur Gleichanteil bleibt bestehen. Eigenschaften der numerischen Lösung aus praktischer Erfahrung: Es lässt sich empirisch beobachten, dass das Vorwärts-Euler-Verfahren für

( )2

2x

t∆

∆ >λ

instabil wird. Das Rückwärts-Euler-Verfahren ist jedoch unbedingt stabil. Daraus resultiert die Frage, ob es eine Möglichkeit gibt, die Stabilität eines auf eine partielle Differentialgleichung angewendeten numerischen Verfahrens zu bestimmen.

Stabilitätsanalyse Anhand des Vorwärts-Euler-Verfahrens werden wir nun versuchen, eine Stabilitäts-bedingung, für diese Differentialgleichung zu finden. Analog zur Betrachtung der


analytischen Lösung, erfolgt die Stabilitätsanalyse durch Untersuchung der Lösungs-eigenschaften der numerischen Lösung für folgenden Lösungsansatz

0 (k)exp( )exp( )njf f n t ikj x= γ ∆ ∆ (*)

Das Einsetzen des Ansatzes in das numerische Schema liefert jeweils die numerische Dispersionsrelation.

Stabilitätsbedingung für Vorwärts-Euler-Verfahren Das Vorwärts-Euler-Verfahren lautet hier

11 12 2n n n n n

j j j j jtf f f f f

x+

+ −∆ = + λ − + ∆

Für die Stabilitätsanalyse betrachten wir das Verhalten des Lösungsansatzes (*) beim Einsetzen in das Euler-Schema

( )

( ) ( )( )

10 0

1 10 0 02

ˆ ˆ( ) ( )

ˆ ˆ ˆ( ) 2 ( ) ( )

n t ik j x n t ik j x

ik j x ik j xn t n t ik j x n t

f k e e f k e et f k e e f k e e f k e e

x

γ⋅ + ∆ ⋅ ∆ γ⋅ ∆ ⋅ ∆

⋅ + ∆ ⋅ − ∆γ⋅ ∆ γ⋅ ∆ ⋅ ∆ γ⋅ ∆

=

∆+λ − +

∆

( ) ( )12 2n t n t n t ik x n t n t ik xte e e e e e e

xγ⋅ + ∆ γ⋅ ∆ γ⋅ ∆ ⋅∆ γ⋅ ∆ γ⋅ ∆ − ⋅∆∆ ⋅ λ

= + − +∆

( )21 2t ik x ik xte e ex

γ⋅∆ ⋅∆ − ⋅∆∆ ⋅ λ= + − +

∆

( )( ) 22 2

2 0

1 2 cos 1 1 4 sin2

t t k xk xx x

− ≤ ≤

∆ ⋅ λ λ∆ ∆ = + ⋅ ∆ − = − ∆ ∆

dies entspricht dem Fortpflanzungsfaktor der Lösung: 1

22exp( ) ( ) 1 4 sin

2

nj

nj

f t k xt g kf x

+ λ∆ ∆ γ ⋅ ∆ = = = − ∆

Für eine stabile Lösung muss folgende Bedingung erfüllt sein:

( ) 1g k ≤

Eigenschaften des Verstärkungsfaktors g(k) Für das oben abgeleitete numerische Lösungsverfahren (Euler-Vorwärts) finden wir: • immer

− monoton fallend bezüglich k für 0 xk π∆≤ ≤ (Nyquist-Wellenzahl oder Nyquist-

Frequenz) − immer reellwertig und 1≤

im Einklang mit exakter Lösung 2t k te eγ⋅∆ −λ ⋅∆=

• für 2

4xt ∆

∆ ≤λ


− ( ) 0g k ≥ für alle k

• für 2

4xt ∆

∆ >λ

− für große k (kurze Wellenlängen) dann ( )g k negativ

f wechselt an jedem Gitterpunkt von einem Zeitschritt zum nächsten das Vorzeichen künstliche Oszillationen der numerischen Lösung

• für 2

2xt ∆

∆ >λ

− für sehr große k ( ) 1g k ≤ −

f wechselt an jedem Gitterpunkt Vorzeichen und wächst betragsmäßig an instabil

Resultierende Stabilitätsbedingung Courant-Friedrichs-Leavy-Bedingung (CFL-Bedingung)

2

2xt ∆

∆ ≤λ

Das Vorwärts-Euler-Verfahrens ist somit nur bedingt stabil. Die Vorgabe einer räumlichen Auflösung gibt eine obere Schranke für die zeitliche Schrittweite an, gemäß der obigen Courant-Friedrichs-Levy-Bedingung. Effektiv bedeutet dies, dass bei Differentialgleichungen, welche Ausbreitungsprozesse beschreiben, die Informa-tionsausbreitungsgeschwindigkeit des Differenzenschemas mindestens so hoch sein muss, wie die Ausbreitungsgeschwindigkeit des physikalischen Prozesses. Vergleich mit Rückwärts-Euler:

( )1 1 1 11 12 2n n n n n

j j j j jtf f f f fx

+ + + ++ −

∆ ⋅ λ= + − +

∆

gibt: ( )( )21 2 cos 1 1t te k xx

γ⋅∆ ∆ ⋅ λ − ⋅ ∆ − = ∆

bzw.: ( )( )

1

2

1 11 2 cos 1

nj t

nj

fe tf k x

x

+γ⋅∆= = ≤

∆ ⋅ λ− ⋅ ∆ −∆

Dieser „Verstärkungsfaktor“ liegt immer im Intervall (0,1] Verfahren ist unbedingt stabil (aber wie das Euler-Vorwärts-Verfahren nur 1. Ordnung genau in der Zeit) Für explizite Verfahren lässt sich meist eine CFL-Bedingung finden, unter der sie stabil laufen. Implizite Verfahren sind tendenziell stabiler und die Schrittweiten bestimmen


sich eher aus der gewünschten Genauigkeit. Die Tatsache, dass ein Algorithmus stabil läuft, heißt jedoch noch lange nicht, dass er auch das richtige Ergebnis liefert.

5.3 Split-Step-Verfahren Typische Differentialgleichung

ˆ ˆ( )E A B Ez

∂= +

∂ (*)

− A - Differentialoperator 1

− B - Differentialoperator 2

z.B. Schrödinger-Gleichung mit Nichtlinearität

22

2 2ˆ

ˆ

( , )2

BA

E z t i E i E Ez t

∂ ∂= − β + γ

∂ ∂

− exakt: beide Operatoren wirken gleichzeitig − Nährung: Operatoren wirken in kurzen Abschnitten unabhängig Schritt von z nach z h+ in zwei Schritten

(1) Ê AEz

∂=

∂ & (2) Ê BE

z∂

=∂

mathematische Begründung dieses Vorgehens:

Formale Lösung von (*) für z -unabhängige Operatoren A und B

ˆ ˆ( , ) exp[ ( )] ( , )E z h t h A B E z t+ = +

Anwendung der Baker-Hausdorff-Formel. Diese ist für die zwei Operatoren â hA= und ˆ ˆb hB= wie folgt definiert

( )1 12 12

ˆ ˆ ˆ ˆ ˆˆ ˆ ˆ ˆ êxp( )exp( ) exp [ , ] ,[ , ] ...a b a b a b a b a b = + + + − +

mit ˆ ˆ ˆˆ ˆ ˆ[ , ]a b ab ba= − und a , b nicht-kommutativ

Der Split-Step-Algorithmus ignoriert diese nicht-kommutative Natur von a , b bzw. A , B Fehleranalyse

− Split-Step: ˆ ˆ( , ) exp[ ]exp[ ] ( , )E z h t hA hB E z t+ ≈

− Baker-Hausdorff: 212

führender Fehlerterm

ˆ ˆˆ ˆ( , ) exp( [ , ] ...) ( , )E z h t hA hB h A B E z t+ ≈ + + +

Fehler zweiter Ordnung in h

Beispiel: Nichtlineare Schrödinger-Gleichung Lösung von DGL mit Operator A :

2

2 2( , )

2E z t i E

z t∂ ∂

= − β∂ ∂

Lösung im Fourier-Raum


1ˆ êxp[ ] ( , ) exp[ ( )] ( , )hA E z t FT hA i FT E z t−= ω durch Ersetzen von t

∂∂

mit iω

Lösung von DGL mit Operator B :

2( , ) ( , ) ( , )E z t i E z t E z tz

∂= γ

∂

z.B. durch Annahme, dass 2( , ) constE z t = im einzelnen Diskretisierungsintervall Lösung mit exp -Ansatz

Lösungsschema

A B A B

h h t

Eigenschaften − sehr effizient + einfach − weitere Genauigkeitsverbesserung durch zusätzliche Symmetrisierung

möglich − z.B. auch Anwendung, um ein 2D Problemen näherungsweise durch die

Überlagerung von zwei 1D Problemen zu beschreiben


Ergänzung zu den Kapiteln zu Abschnitt 1.5 – Nullstellen & Extrema

Fehlerentwicklung bei der Regula Falsi: Berechnung des Fehlers Ei=xi-x* aus der num. Lösung xi unter Voraussetzung das gesuchte Lösung x* bekannt ist aus der obigen Iterationsformel:

211 12 21

1 2 1

´ ( *)( *) ( )( ) ( *) ( ) ´ ( *) 2 ( *)

i ii i i i i i

i i i i

E E f xE E E f x E E O EE E f x E E f x f x

−+ −

− −

−− = +

− + −

Rekursionsformel für Fehler: 1 1i i iE CE E+ −= mit C als unbekanntem Faktor

Mit Werten 0E und 1E hinreichend klein, so dass 0CE K≤ und 1CE K≤ ergibt sich deshalb: 2

2 1 0CE CE CE K≤ ≤ , 33 2 1CE CE CE K≤ ≤ , 5

4 3 2CE CE CE K≤ ≤

(interessant: die Exponenten ergeben Fibonacci-Folge [0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987]; entsteht durch Rekursionsformel 1 1i i ia a a+ −= + mit

0 10, 1α = α = ; hängt mit goldenem Schnitt zusammen; Fibonacci-Zahlen finden sich im Bauplan vieler Pflanzen)

daraus kann gezeigt werden, dass 1.621i iE E+ ≈ τ

Weitere Ergänzungen zu diesem Abschnitt stehen im Anhang. zu Abschnitt 1.6 – Interpolation

Quelle: Department of Electrical Engineering Columbia University (Lagrange-Interpolation)

function [P,R,S] = lagrangepoly(X,Y,XX) %LAGRANGEPOLY Lagrange interpolation polynomial fitting a set of points % [P,R,S] = LAGRANGEPOLY(X,Y) where X and Y are row vectors % defining a set of N points uses Lagrange's method to find % the N-1th order polynomial in X that passes through these % points. P returns the N coefficients defining the polynomial, % in the same order as used by POLY and POLYVAL (highest order first). % Then, polyval(P,X) = Y. R returns the x-coordinates of the N-1 % extrema of the resulting polynomial (roots of its derivative), % and S returns the y-values at those extrema. % % YY = LAGRANGEPOLY(X,Y,XX) returns the values of the polynomial % sampled at the points specified in XX -- the same as % YY = POLYVAL(LAGRANGEPOLY(X,Y)). % % Example: % To find the 4th-degree polynomial that oscillates between % 1 and 0 across 5 points around zero, then plot the interpolation % on a denser grid inbetween: % X = -2:2; Y = [1 0 1 0 1]; % P = lagrangepoly(X,Y); % xx = -2.5:.01:2.5;


% plot(xx,polyval(P,xx),X,Y,'or'); % grid; % Or simply: % plot(xx,lagrangepoly(X,Y,xx)); % % Note: if you are just looking for a smooth curve passing through % a set of points, you can get a better fit with SPLINE, which % fits piecewise polynomials rather than a single polynomial. % % See also: POLY, POLYVAL, SPLINE % 2006-11-20 Dan Ellis [email protected] % $Header: $ % For more info on Lagrange interpolation, see Mathworld: % http://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html % Make sure that X and Y are row vectors if size(X,1) > 1; X = X'; end if size(Y,1) > 1; Y = Y'; end if size(X,1) > 1 || size(Y,1) > 1 || size(X,2) ~= size(Y,2) error('both inputs must be equal-length vectors') end N = length(X); pvals = zeros(N,N); % Calculate the polynomial weights for each order for i = 1:N % the polynomial whose roots are all the values of X except this one pp = poly(X( (1:N) ~= i)); % scale so its value is exactly 1 at this X point (and zero % at others, of course) pvals(i,:) = pp ./ polyval(pp, X(i)); end % Each row gives the polynomial that is 1 at the corresponding X % point and zero everywhere else, so weighting each row by the % desired row and summing (in this case the polycoeffs) gives % the final polynomial P = Y*pvals; if nargin==3 % output is YY corresponding to input XX YY = polyval(P,XX); % assign to output P = YY;


end if nargout > 1 % Extra return arguments are values where dy/dx is zero % Solve for x s.t. dy/dx is zero i.e. roots of derivative polynomial % derivative of polynomial P scales each power by its power, downshifts R = roots( ((N-1):-1:1) .* P(1:(N-1)) ); if nargout > 2 % calculate the actual values at the points of zero derivative S = polyval(P,R); end end

(Lagrange vs. Spline Plot) 1 X = [1 2 3 4 5 6 7 8]; 2 Y = [0 1 0 1 0 1 0 1]; 3 [P,R,S] = lagrangepoly(X,Y); 4 5 xx = 0.5 : 0.01 : 8.5; 6 plot(xx,polyval(P,xx),X,Y,'or',R,S,'.b',xx,spline(X,Y,xx),'--g') 7 grid

zu Abschnitt 1.6 – Interpolation in höheren Dimensionen Da meist auf orthogonalen Gittern diskretisiert wird, hat jeder Punkt vier nächste Nachbarn mit denen er auf jeden Fall wechselwirkt. Allerdings geht im Dreidimensio-nalen eine Ebene im Allgemeinen nicht durch vier frei gewählte Punkte

( ) ( ) ( ) ( )1, 2, , 1, 1 2, 1, 1, 1 2, 1 1, 1 1, 2, 1 , 1, , , , , , , , , , ,j k j k j k j k j k j k j k j kx x y x x y x x y x x y+ + + + + + + +

Deswegen müsste mindestens eine quadratische Interpolationsfunktion angesetzt werden. Dabei wird die eindimensionale Interpolation auf zwei Dimensionen erweitert. Eine mögliche Interpolationsformel lautet

( ) ( )( ) ( ) ( )1 2 , , 1 1, 1, 1, 1 1 1 1j k j k j k j kf x x t u y t u y t u y t u y+ + + +≈ − − ⋅ + − ⋅ + − ⋅ + ⋅ ⋅

Mit den Koeffizienten

1 1,1, 1 1, 1

1, 1 1,

2 2,2, 2 2, 1

2, 1 2,

jj j

j j

kk k

k k

x xt x x x

x xx x

u x x xx x

++

++

−= ≤ ≤

−

−= ≤ ≤

−


Zu Abschnitt 2.4 – QR-Zerlegung Wie auch die LU-Zerlegung wird bei diesem Verfahren die Matrix in zwei Matrizen zerlegt. Das Verfahren ist für nicht degenerierte Matrizen eine numerisch auf-wändigere Alternative zur LU-Zerlegung. Der Algorithmus ist jedoch wichtiger Bestandteil bei der Bestimmung der Eigenwerte von Matrizen. Die Zerlegung lautet

ˆ ˆ Â QR=

− mit ˆ m nA ×∈ (m>n)

− mit der oberen Dreiecksmatrix R

− und der unitären Matrix Q ( †ˆ ˆ 1QQ = mit †Q gleich der zu Q adjungierten

Matrix - die Transponierte der komplex Konjugierten von Q )

Falls Q keine quadratische Matrix ist, wird sie auf eine quadratische Matrix erweitert, ebenso werden an R hinreichend viele Nullen angefügt. Damit diese Zerlegung für reguläre und überbestimmte Probleme eindeutig ist müssen die Vorzeichen der Diagonalelemente der Dreiecksmatrix vorgegeben werden. Für gewöhnlich werden sie positiv gesetzt. Um die Lösung des Problems

Ax b=

bei gegebener Zerlegung zu bestimmen wird †ˆz Q b=

berechnet. Rückwärts einsetzen in

Rx z=

liefert dann die gewünschte Lösung.

Zu Abschnitt 4.1.1 – Vorwärts-Euler-Verfahren

(Euler –Vorwärts/Einheitskreis ) function [T , Y] = euler1(f,tspan,y0) % function [T , Y] = euler1(f,tspan,y0) % loest DGL dy/dt = f(t,y) mit Anfangswerten y(a) = y0 %Aufruf: z.B. [T Y] = euler1(g,[0 2*pi],[1;0]); % Inputs: f -- eine Funktion f(t,y) die einen Zeilenvektor % mit der selben Laenge wie y zurueck gibt % z.B. f = inline(’[y(2);-y(1)]’,’t’,’y’) % tspan -- Vektor [a,b] mit Start- und Endzeitpznkt % y0 -- Zeilenvektor der Anfangswerte, y(a) = y0 % Outputs: T -- a n+1 Zeilenvektor der die zeit beinhaltet % Y -- a (n+1) mal d Matrix wobei d die Laenge von y hat % Y(t,i) ist die i-te Komponente von y zur Zeit t


%fuer Plot figure(1) close all hold on axis equal farben = ['r', 'g', 'c', 'm', 'b']; var=[ 400, 200,100, 70, 50]; for i=1:5 str = farben(i); for n=var(i) a = tspan(1); b = tspan(2); h = (b-a)/n; % Schrittweite t = a; y = y0; % t und y sind die Laufvariablen T = a; Y = y0'; % T und Y speichern alle Schritte %Euler-Vorwaerts for i = 1:n y = y + h*f(t,y); t = a + i*h; T = [T; t]; Y = [Y; y']; end y1=Y(:,1); y2=Y(:,2); ylabel('q');xlabel('p'); plot(y1,y2, str,'LineWidth' ,1); end %Referenzplot mit der ODE45-Funktion [A,B]=ode45(f,[0,2*pi],[1;0]); plot(B(:,2),B(:,1),'k','LineWidth' ,2); title('Vorwaerts-Euler-Verfahren','FontSize',20); end


Verfahren von Dormand und Price

01 15 5

3 3 910 40 40

4 44 56 325 45 15 9

8 19372 25360 64448 2129 6561 2187 6561 729

9017 355 46732 49 510313168 33 5247 176 18656

35 500 125 2187 111 0384 1113 192 6784 84

−

− −

− −

−


Ausgewählte Lösungsvorschläge zu Aufgabe 2 (Simpson-Verfahren ) 1 function s = simpson(a,b,m) 2 3 % a,b sind Integrationsgrenzen 4 % Integral wird in 2*m Segemente unterteielt 5 % s approximiert das Integral 6 7 h=(b-a)/(2*m); 8 s0=f1(a)+f1(b); 9 s1=0; 10 s2=0; 11 12 for k=1:2*m-1 13 x = a+k*h; 14 if mod(k,2)==0 15 s1 = s1+f1(x); % k gerade 16 else 17 s2 = s2+f1(x); % k ungerade 18 end 19 end 20 s = h*(s0+2*s1+4*s2)/3;

zu Aufgabe 3 (Verfahren des Goldenen Schnittes ) 1 f = inline('(x-1).^2'); 2 3 x = linspace(-4,4, 101); 4 plot(x, f(x)) 5 N = 10; 6 a0 = -4 ; b0 = 4; 7 r = (sqrt(5)-1)/2; 8 9 alist = zeros(N,1); 10 blist = zeros(N,1); 11 a = a0; b = b0; 12 s = a + (1-r)*(b-a); 13 t = b - (1-r)*(b-a); 13 f1 = f(s); 15 f2 = f(t); 16 for n = 1:N 17 18 if f1 < f2 19 b = t; 20 t = s; 21 s = a+(1-r)*(b-a); 22 f2 = f1; f1 = f(s);


23 else 24 a = s; 25 s = t; 26 t = b-(1-r)*(b-a); 27 f1 = f2; 28 f2 = f(t); 29 end 30 alist(n) = a; 31 blist(n) = b; 32 end 33 disp(' a b f(a) f(b) b-a ') 34 disp(' ') 35 alist = [a0;alist]; 36 blist = [b0; blist]; 37 [alist, blist, f(alist), f(blist), blist-alist]

zu Aufgabe 8 (Euler-Vorwärts ) 1 function euler(a,b,N) 2 3 h=(b-a)/N; t=a; T=t; x=1.0; X=x; 4 5 for i=1:N 6 x=x+h*f(t,x); 7 t=t+h; 8 X=[X,x]; 9 T=[T,t]; 10 end 11 12 S=a:h/4:b; 13 Y=exp(S); 14 plot(T,X,'o', S,Y,'-') 15 16 function dx=f(t,x) 17 dx=x;

(LU- Dekomposition)

1 function [L, U] = slu(A) 2 3 % slu LU-Dekompensation einer quadratischen Matrix 4 % [L, U] = slu(A) führt den Crout’s-Algorithmus durch und gibt eine 5 % untere Dreiecksmatrix L sowie eine obere Dreiecksmatrix U mit L*U = A 6 % zurueck. Der Algorithmus stoppt, wenn der Eintrag einer Pivotstelle zu klein ist. 7 8 [n, n] = size(A); 9 10 for k = 1:n


11 if abs(A(k, k)) < sqrt(eps) 12 disp(['Kleine Pivotstelle in Zeile ' int2str(k) '.']) 13 end 14 L(k, k) = 1; 15 for i = k+1:n 16 L(i,k) = A(i, k) / A(k, k); 17 for j = k+1:n 18 A(i, j) = A(i, j) - L(i, k)*A(k, j); 19 end 20 end 21 for j = k:n 22 U(k, j) = A(k, j); 23 end 24 end

Documents

gelesen von Prof. Thomas Pertsch im WS 2018/19 …...Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_2019-02-16s.docx 1 Computational Physics I gelesen von Prof