Computational Physics I - iap.uni-jena.dePhysics... · Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_2017-10-10s.docx 3 . 0. Einführung und Motivation

Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_2018-04-11s.docx 1

Computational Physics I gelesen von Prof. Thomas Pertsch im SS 2018

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.................................................... 10 1.3.3 Ableitungen höherer Ordnung .................................................................. 12 1.3.4 Spektralverhalten der Ableitungsoperatoren ............................................ 12

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

1.5 Nullstellen und Extrema ...................................................................................... 22 1.5.1 Nullstellen von Funktionen einer Veränderlichen ..................................... 22 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 .......................................................................... 41

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

3. Fourier-Transformation ........................................................................... 53 3.1 Die diskrete Fourier-Transformation ................................................................... 55 3.2 Fast-Fourier-Transformation ............................................................................... 57 3.3 Das Abtasttheorem ............................................................................................. 58

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

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

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


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

Differenzen-Methode für Anfangswertaufgaben) ................................................ 86 5.2 Stabilitätsanalyse nach von Neumann ................................................................ 90 5.3 Split-Step-Verfahren ........................................................................................... 93

Ergänzung zu den Kapiteln .......................................................................... 95 Ausgewählte Lösungsvorschläge ............................................................... 101


0. Einführung und Motivation Computational Physics ist ein Querschnittsfach aus den Bereichen Mathe-matik, 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 Daten-analyse und der Visualisierung. Es handelt sich dabei um einen Einführungskurs, der sich an den Bedürf-nissen der Physik orientiert. Der Kurs erhebt deshalb nicht den Anspruch eines mathematisch fundierten Numerikkurses oder einer Informatikvor-lesung. Zum grundlegenden Verständnis 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 Standardverfahren 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 numerische ermittelte Lösung hinreichend gut mit der exakten (analytischen) Lösung und damit mit der realen Physik übereinstimmt. Problematisch ist dabei, dass die ana-lytische Lösung des numerisch untersuchten Problems meist nicht bekannt ist oder häufig gar nicht existiert. Zur Beschreibung der Fehlereigenschaften numerischer Lösungsverfahren für physikalische Probleme werden häufig drei Fehlerkriterien angewandt, die jedoch stark miteinander verbunden sind. Dies sind die Kondition, die Stabi-litä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ösungs-methode. Sie beschreibt die Abhängigkeit der numerischen Lösung von ge-störten Eingangsdaten im Vergleich zur analytischen Lösung. Insbesondere


beschreibt die Stabilität damit auch die Robustheit eines numerischen Verfahrens gegenüber Rundungsfehlern. 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 Ressourcenbedarf 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 Computer-rechenzeit, Computerspeicher oder immer mehr auch die für die Berech-nungen erforderlich Energie sehr schnell mit der Dimension des Problems wächst. Als Dimension wird hierbei die Anzahl der Freiheitsgrade 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 physikalisch Aufgabenstellungen erlauben. Letztlich besteht die Aufgabe, die entwickelten numerischen Algorithmen in einer Programmiersprache umzusetzen. Dazu wird in der Vorlesung Compu-tational Physics I die Programmierumgebung MATLAB (bzw. die Program-miersprache MATLAB) verwendet, da diese bereits nach geringer Einarbeitungszeit zu ersten Ergebnissen führt und gleichzeitig auch bei fortschreitender Nutzerkenntnis immer bessere/effizientere Lösungen erlaubt.


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 korres-pondiert 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 unterschiedlichem 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 noch nach dem für die jeweilige Darstellung erforderlichen Speicherplatz unterschieden. Für diese Kate-gorisierung 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 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. Dabei werden diese Eigenschaften nicht eindeutig durch den eingesetzten Speicherplatz bestimmt, sondern können geeignet gegeneinander abge-wogen werden. Als Beispiel sei hier eine häufig angewandte Aufteilung der Bits bei einem 64 Bit Realtyp nach dem IEEE-Standard beschrieben. Diese ergibt sich aus der halblogarithmischen Darstellung der Zahlen entsprechend:

( )1 2s ez m= − ⋅ ⋅

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

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 Auflösung über dem gesamten darstellbaren Wertebereich stark variiert. Die Auflösung bestimmt sich im Wesentlichen aus der Mantisse.

52 162 10− −≈

1.2 Diskretisierung Um numerische Berechnungen vornehmen zu können, ist es notwendig, kontinuierliche 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 Entwicklungskoeffizien-ten als diskrete Wertemenge numerisch weiterverarbeitet. Bei der Diskretisierung wird prinzipiell zwischen äquidistanter und nichtäqui-distanter Diskretisierung unterschieden. Bei der äquidistanten Diskretisierung bleibt der Abstand zwischen den Stützstellen, unabhängig vom zu lösenden Problem, 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 Eigen-schaften des Problems angepasst und dementsprechend 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 Anwen-dung auf diskrete Werteverteilungen. Man spricht dabei von der Diskreti-sierung der Operatoren. Dabei werden aus analytischen Ausdrücken rein algebraische Formulierungen.

1.3 Differentiation Als erstes Beispiel für einen solchen diskreten Operators werden wir die diskrete Version der uns bekannten Differentiation behandeln. Dabei wird für eine gegebene Diskretisierung if der Funktion ( )f x ein diskreter Differential-operator [ ] ( )( ) : '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 ) Codebeispiel 11 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 numerische Lösung ist eine Abschätzung der durch die Diskreti-sierung hervorgerufenen Fehler 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 Operatoren ange-nommen wird, sodass kein Rundungsfehler auftritt. Allgemeine Eigenschaften des diskreten Differentialoperators:

− [ ]hD f konvergent: [ ]0

lim hhD f

→ konvergiert (nur bis zum Rundungs-

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

0lim 0hh

E→

→ )

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 Aus-führung der Berechnungen als numerische Operationen mit Computerzahlen endlicher Genauigkeit, sodass bei jeder elementaren Rechenoperation (+, -, *, /, …) ein sog. Rundungsfehler auftritt. Dieser Rundungsfehler ist


unvermeidbar und 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, da dann der bei zu kleinem h auftretende Rundungsfehler vermieden werden kann. Eine Herleitung der Konvergenzeigenschaften des diskreten Differential-operators 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 Differen-tialoperatoren 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 konvergiert. Ziel: Elimination des h-Fehlerterms Ansatz: Kombination des rechtsseitigen und des linksseitigen Differential-

operators

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

− + − = −

.

Es resultiert der sog. zentrale Differentialoperator ( ) ( )[ ( )]

2hf x h f x hD f x

h+ − −

=

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 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 Taylor-entwicklung

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

22

22

( ) 2 ( ) ( )( ) ( )

1 [1 2 1]h

f x h f x f x hf x O hh

Dh

− − + +′′ = +

= −

konstruiert 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 Ab-hä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 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 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 Oszillator-gleichung 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 Konvergenz-verhalten 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. lang-wellige Funktionen besitzt der zentrale Differentialoperator, wie wir oben bereits gesehen haben, eine Konvergenz in 2. Ordnung

kh = π sinc( ) 0π = , d.h. für hochfrequente bzw. kurzwellige Funk-tionen, 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 sogar das falsche Vorzeichen

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

( )b

a

A dx f x= ∫ .

0 1 2 3 4

0

0.2

0.4

0.6

0.8

1

π π π πx

sinc (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 Diskreti-sierung des Integrationsintervalls beruhen. Entsprechend wird das zu inte-grierende 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 Integrations-intervalls [ , ]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 Teil-intervalle 1[ , ]i i iI x x += .

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

( )11

0.

i

i

xN

i x

A dx f x+−

=

= ∑ ∫

Die Aufgabe besteht nun darin, ( )1i

i

x

ix

A f x dx+

= ∫ im i-ten Teilintervall 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 Mittel-wertes. 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 Integra-tion ü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,

konvergiert 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 Singulari-täten der zu integrierenden Funktion ( )f x an den Intervallgrenzen auf-treten.

1.4.2 Trapezregel Bei dieser Methode werden die Teilintegrale durch Trapeze genähert, die den Verlauf der Funktion vermeintlich 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 ge-nä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. • Der Fehler der Trapezregel ist jedoch doppelt so groß wie bei der Recht-

eckregel. • Die Trapezregel lässt sich im Vergleich zur Rechteckregel aber sehr ein-

fach rekursiv von N auf 2N verfeinern, da die schon berechneten Stütz-stellen 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 durch den diskreten Differentialoperator mit dem 3-Punkt-Stencil 2[1 2 1]/ h− erreicht.

( ) ( ) ( ) ( )1

1

35 51 1

1 12

22 43 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= − ergibt bei geradem N 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ützstellen-abstandes 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 Gesamtintegrationsintervalls in viele Teilintervalle und Näherung der Funktion in diesen kleinen Teilintervallen, beruhen, lässt sich durch folgenden Algo-rithmus leicht implementieren. Ablauf: 1. Vorgabe einer Zielgenauigkeit ε 2. Wahl von N und Berechnung von NA 3. Halbieren der Intervallbreite 2 2h h N N→ → , 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.

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) Codebeispiel 2function [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

AN

A

N

ε


% 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 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 2A = verglichen werden. Die zu integrierende Sinus-Funktion muss noch als allgemeine Integrations-funktion für die Übergabe beim Funktionsaufruf implementiert werden:

(Definition des Integranden) Codebeispiel 31 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) Codebeispiel 41 [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 2A = ist. Die Genauigkeit ließe sich durch Ver-kleinerung 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) Codebeispiel 51 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 Integrations-intervall [ , ]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 aufgreifen 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 Genauigkeits-ordnung führen kann, ist Vorsicht geboten. „Hohe Ordnung“ bedeutet nur „hohe Genauigkeit“, wenn die Funktion 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 folgt aus der der Orthogonalität der Baispolynome iP

( ) ( )b

i j ija

dx P x P x = d∫ .

Daraus lässt sich ein lineares Gleichungssystem für die Koeffizienten iα ableiten, dessen Lösung häufig die wesentliche numerische Aufgabe dar-stellt. 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 Berech-nung der Koeffizienten iα und die analytische 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 entwickel-bar 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 vorzu-nehmen.

Integration mit Trapezregel Aufgabe 1Fü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 Aufgabe 2Schreiben 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 Intervall [ ],a b . Die nachstehenden Abbildungen verdeutlichen dabei einige Situationen, die bei der Suche nach solchen Nullstellen auftreten können. Die Wahl eines speziellen Verfahrens zu 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 nach 1ix + verbessern bis

( )*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.

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

Es können bei gleichen 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 eine vorhersagbare Verbesserung erzielt. Das nachstehende Struktogramm verdeutlicht noch einmal das Verfahren der Bisektion.


Schematischer Ablauf des Bisektionsverfahrens unter der Annahme, dass

( ) 0 ( ) 0f a f b> < . Hinweis: Die Implementierung beruht auf einem rekursiven Funktionsaufruf.

1.5.1.2 Sekantenverfahren Für das 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 Reihen-folge ihrer Benutzung in der iterativen 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. 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 jeder Iteration des Verfahrens die Nullstelle ein.

• Da bei diesem Verfahren der Nenner zwangsläufig klein wird und gegen Null konvergiert, ist es sinnvoll eine 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 Codebeispiel 6

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 Iterations-punkte gezogen wird, welche die Nullstelle einschließen. Damit wird 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 weiter-verwendet. 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 die Punkte die 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 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 Bei diesem 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+ + ′≈ + − =

Daraus kann die folgende Iterationsformel abgeleitet werden:

1( )( )

ii i

i

f xx xf x+ ≈ −′

2


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 • 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 Aufgabe 3

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

Struktogramm der Simpson-Regel Aufgabe 4Wie 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 Mini-mums 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 liegt entweder im Teilintervall [ , ]a b oder im Teilintervall [ , ]b c . Um unabhängig von der kon-kreten 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 bestimmen wir 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ählen wir 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 unser Minimum. Diesen Schritt der Einschachtelung des Minimums wieder-holen wir solange, bis die Intervallbreite eine bestimmte Toleranz unter-schreitet.

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 unab-hängig vom Erfolgsfall der Teilung im vorherigen Iterationsschritt 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 Suchinter-valls gleich bleiben. D.h. die Verbesserung, die in jedem Iterationsschritt erzielt wird soll konstant sein.

Lösungsansatz Verhältnis der Teilintervalllängen ( 1 2/∆ ∆ ) soll bei folgenden Iterationen 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

f(x)

x

f(a)

f(c)

f(b)

a b c d

fB(d)

fA(d)

∆3 ∆2 ∆1

∆1

∆2 ∆3


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. „unkooperatives“ 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− − − − − = +− − − − −

Mit dem kleinsten Intervall, das drei Punkte umfasst 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. 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 dem gesuchten Minimum der Funktion.

1.5.3 Minima von Funktionen mehrerer Veränderlicher Echte Nullstellensuche ist in höheren Dimensionen extrem schwierig aber Minimierung ist meist möglich. Die Minimierungsverfahren 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 Such-algorithmus für einen Simplex. Ein Simplex ist eine n-dimensionale Punkte-menge 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 Gerade, im Zweidimensio-nalen ein Dreieck, im Dreidimensionalen ein Tetraeder usw..

Spiegelung Expansion/Kontraktion

S

P

P

Graphische Darstellung der Simplexoperationen an einem 2D Simplex

Das Verfahren sieht in der Implementierung nach Nelder und Mead folgen-dermaßen aus: 1. Wähle aus einer physikalischen Vorbetrachtung geeignete Ausgangs-

punkte, die einen Simplex aufspannen und bestimme deren Funktions-werte.

2. Suche den ‚besten’ Punkt B und ‚schlechtesten’ Punkt S (kleinster/ größter Funktionswert).

3. Der ‚schlechteste’ Punkt S wird nun um den Simplexmittelpunkt gespie-gelt, 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 Sim-

plex 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.

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 ver-gangenen Abschnitt vorgestellten Konzepte für die eindimensionale Mini-mierung zurück. Bei der Minimierung in alternierende Richtungen werden für eine N -dimensionale Funktion N eindimensionale Minimierungsaufgaben in N verschiedene Richtungen nacheinander 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 wesentlich danach unterschieden, ob sie die Kenntnis der Ableitung der zu minimierenden Funktion in die Richtungsfestlegung 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 dabei die Eigenschaft besitzen, dass die Minimierung in iu nicht durch die nachfolgende Minimierung in Richtung 1iu +

beeinträchtigt wird, d.h. dass nach der Minimierung in 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 Ableitungs-bildung einbezogen wird, ist das Verfahren des steilsten Abstieges, das auch als Gradientenverfahren 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 xd : ( ) ( )f Â xd ∇ = d

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 ∇ =

− 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 Minimierungs-

richtungen ( 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.

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 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:

− 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 extra-polieren. Im Folgenden werden dafür geeignete Verfahren vorgestellt, sodass der Funktionsverlauf 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 Interpola-

tionsaufgabe löst, da


( )1 1

( )n n

j k j jk k jk k

P x P x y y= =

= = d =∑ ∑

Eigenschaften Da mit dem Grad des Polynoms auch die Anzahl der Maxima und Minima des Polynomverlaufs steigt (ein Polynom n-ten Grades hat n-1 Extrema), neigt die Interpolationsfunktion zum „Schlängeln“. Zusätzlich ergeben sich numerische Probleme bei der Polynombestimmung für hohe Stützstellenzahlen (als Faustregel: ab >100), da dann die numerische Produktberechnung instabil wird. Hier bietet sich eine Inter-polation in Teilintervallen an (siehe Spline-Interpolation im nächsten Kapitel). Der Fehler der Interpolation innerhalb des Interpolationsintervalls (d.h. die Abweichung des Polynoms von der eigentlichen die Stützstellen verbinden-den 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, das durch alle roten Kreise 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

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


soll zweimal stetig differenzierbar sein. Daraus ergeben sich an den Intervall-grenzen 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 (Bemerkung: Im Folgenden sind die Superskripts x in x

ja ein Index und keine Potenzen.) 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 2 31 12 6j j j j j j j js x y a x x a x x a x x= + − + − + −

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

Aus den Anschlussbedingungen folgt

1 2 2 3 31

1 1 2 3 21

2 2 31

1 12 612

j j j j j

j j j j

j j j

y y a h a h a h

a a a h a h

a a a h

+

+

+

= + + +

= + +

= +

(*)

und an den Rändern ist zusätzlich


212

1

0

0n

aa −

=

=

Durch Einsetzen der Gleichungen ineinander lässt sich ein lineares Gleichungssystem für 2

ja finden. Aus diesem können dann die anderen Koeffizienten ( 1 3,j ja a ) bestimmt werden.

Dafür wird die letzte Gleichung von (*) nach 3ja umgestellt

( )3 2 21 /j j ja a a h+= −

und in die anderen beiden Gleichungen eingesetzt. Dies ergibt

1 2 2 21 1

1 1 2 21 1

1 12 6

1 12 2

j j j j j

j j j j

y y a h a h a

a a a h a h

+ +

+ +

= + + +

= + +(**)

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

ja eliminiert indem die untere Gleichung von (**) bei j aufgestellt wird.

1 1 2 21 11 12 2j j j ja a a h a h− −= + +

Daraus folgt

( )1 1 2 2 21 1 1

1 1 2 21 1

1 15 36 6 2, , 2

1 13 6

j jj j j j

j jj j j

y ya a a h a h

h j ny y

a a h a hh

+− − +

−− −

−= + + +

= −−

= + +

Durch Elimination von 11ja − ergibt sich

( )2 2 21 1 1 12

64 2j j j j j ja a a y y yh+ − + −+ + = − + bei 2, , 2j n= −

Mit den Randbedingungen lassen sich aus diesem Gleichungssystem alle zweiten Ableitungen 2

ja ermitteln. Die anderen beiden Koeffizienten ( 1 3,j ja a ) 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 Flexibilität des Funktionenansatzes aus, d.h. sie lassen sich auf vielfältige Probleme anwenden. Teilweise erfordert das zu lösende Interpolations-problem jedoch die Wahl eines spezifischen, problemangepassten Funktion-enansatzes.


Falls die zu interpolierende Funktion Polstellen aufweist, erscheint folgender Polynomansatz günstig

( ) ( )( )

n

m

P xy x

Q x=

wobei ( )nP x und ( )mQ x Polynome vom Grade n bzw. m sind. Die Anzahl N der bekannten Stützstellen kx bestimmt die Polynomgrade durch 1N 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 Gleichungssystem 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 Gleichungs-systemen vorgestellt. 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 charakteri-siert. 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 müssen gesondert betrachtet werden. Falls die Vektoren unterschiedliche Dimensionen haben ergeben sich komplexere Aufgabenstellungen. Im Falle eines unterbestimmten Problems ergeben sich Lösungsräume, die vom Computer nur Beispielhaft berechnet werden können. Für überbestimmte 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 Strukturen 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

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ösungs-verfahren 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 Ver-

besserung der Genauigkeit Die Qualität der Lösung hängt natürlich von dem der Methode zur Verfügung gestellten 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 stellt eine Verbesserung des aus der linearen Algebra bekannten Gauss-Algorithmus’ dar. Die Koeffizientenmatrix 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 entsprechende Elemente von b

mit einer Konstanten 0λ ≠ multiplizieren,

3. zu einer Zeile von A und entsprechenden Elementen 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 145 7 31

5 17

x x xx 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 Stufenform 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 Gleichungssystems 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) 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)=b⋅ ⋅ ⋅ ⋅ ⋅


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 ii 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+ Unbe-kannte 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 uA LU l u l u u l u u

l u l u l u l u l u u

= =

= = + + + + +

1

1:

i

ij ij ik kjk

i j u a l u−

=

≤ = − ∑

11

1:

jj

j

ij ij ik kjuk

i j l a l 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 • 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

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 Gleichungssystemen akkumulieren. Ziel der iterativen Ver-besserung ist es, diese Fehler zu minimieren. 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′ = + d

mit dem unbekannten Fehler xd . 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+ d = + d


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

A x b⋅ d = d

und schließlich erhalten wir

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

Die rechte Seite der Gleichung mit der falschen Lösung x x+ d 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 xd

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

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

klein genug ist.

2.6 Eigenwertprobleme Für viele physikalische Probleme mit linearen Zusammenhängen lassen sich Eigenwertgleichungen 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 Koordi-naten

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

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= Ω

Nach dem Einsetzen des Ansatzes folgt

( )

2

2M 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 • ( )P λ ist 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, hermi-tesch, unitär, etc.), grobe Unterscheidung in:

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

Matrixinversion mit Gauss-Jordan Aufgabe 5Gegeben 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 Aufgabe 6

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 lineare Differentialgleichungen, in denen Zeitableitungen ( )f t eine wichtige Rolle spielen. Die Fourier-Transformation, die Darstellung einer Funktion ( )f t mittels trigonometrischer Funktionen, ist dabei eine gute Methode, um die Lösung einfacher zu ermitteln. 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 im folgendermaßen formulieren:

( ) i tf t e ωω

ω

= α∑ .

Wir bezeichnen ωα als Fourier-Koeffizienten und ω als Frequenz. Die Zeit-ableitung 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 mit den sogenannten Ortsfrequenzen k dargestellt. So gelangt man von Differentialgleichungen im Zeitraum/Ortsraum zu alge-braischen Gleichungen im Frequenzraum. Dadurch kann eine physikalische Aufgabenstellung (sehr viel einfacher) gelöst werden. Nach einer Fourier-Transformation in den Frequenzraum löst man das Problem, um dann das Ergebnis durch Rücktransformation wieder im Zeitraum darzustellen.


Motivation

Lösungsansatz

Für beliebige Zeitverteilungen geht die Anzahl der Frequenzen jedoch gegen unendlich. Deswegen versucht man in der numerischen Berechnung mit periodischen Zeitverteilungen zu arbeiten. Da maximal eine endliche Reihen-entwicklung berücksichtigt 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 physika-lischen 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 Problem im Bildraum

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 Raumpunkte 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= d∑

( xyd - Kronecker-Symbol, alle Summen über LNa

= Elemente)

schreiben. Dabei gilt die Identität

( )ik x yxy

k

a eL

−d = ∑ .


Mit zugehörigen diskreten Ortsfrequenzen

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

a=

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

−

−

= d

=

=

∑

∑ ∑

∑ ∑

und damit eine diskrete Fourier-Transformation (FT)

( ) ( )ikx

xf k a e f x−= ∑

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= ∑

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 verursachen. 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ücktrans-formation z.B.

( ) ( )

( ) ( )

3

3

1

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 Multipli-kationen. Für m-dimensionale Probleme werden es damit 2mN Multiplika-


tionen. 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, einzelne Berech-nungen der Fourier-Transformation in einer speziellen Reihenfolge auszu-führen, so dass jeweils auf schon berechnete Zwischenergebnisse zurück-gegriffen werden kann. Mit diesem Verfahren werden wir den Rechenaufwand für die eindimen-sionale Fourier-Transformation von 2N auf 2logN N Operationen reduzieren. Dies ermöglicht eine extreme Zeitersparnis, z.B. für N=106. 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

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

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

( ) ( ) ( )1eoeo…oo eoeo…oo eoeo…ooexpaf k f x ikx= −

Das Schema funktioniert gut für 2nN = .

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

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 abtast max min2( )v v v≥ − falls min 0v ≠ .

Häufig wird als charakteristische Frequenz auch die Nyquistfrequenz benutzt

Ny 2∆ϖ

ν ≥π

abtast Ny2v v=

Bei nicht bandbegrenzen Signalen kommt es zum Aliasing-Effekt, d.h. die spektrale Leistung aus zu hohen Frequenzen wird in tiefe Frequenzen gespiegelt (Lösung bei begrenzter Samplingrate: vorher analoger Tiefpass-filter). Beispiel: Siehe bzw. höre http:///de.wikipedia.org/wiki/Nyquist-Shannon-Abtasttheorem

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

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

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

t

Hann

A

Rechteck

Welch

Bartlett

x k k’


4. Gewöhnliche Differentialgleichungen Da sich eine ganze Reihe wichtiger physikalischer Systeme durch gewöhn-liche 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 prinzipieller Bedeutung, ob die Eindeutigkeit der Lösung inner halb der Auf-gabenstellung durch zusätzliche Anfangsbedingungen oder Randbeding-ungen vorgegeben ist. Hier sollen zuerst Methoden für Anfangsbedingungen und erst danach für Randbedingungen vorgestellt werden.

4.1 Anfangswertaufgaben (AWA) Aufgabenstellung ist Anfangswerteaufgabe, die durch eine Differential-gleichung (DGL) und die zugehörigen Anfangswerte (AW) eindeutig beschrie-ben ist

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

kk

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 als ein System gekoppelter Differentialgleichungen erster Ordnung geschrieben werden kann

( )

( ) ( ) ( )

dy z tdtdz r t q t z tdt

=

= −

mit den bekannten Anfangswerten ( ) ( )0 , 0 ( 0)f t f t z t= = = = . Um die Notation übersichtlich zu gestalten, erfolgt im Folgenden die Darstellung der Grundprinzipien von Lösungsverfahren vielfach am Beispiel von Differentialgleichungen 1. Ordnung. Durch den obigen Ansatz zur Trans-formation von Differentialgleichungen höherer Ordnung in Systeme gekop-pelter Differentialgleichungen 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 2. Ordnung Einfache Anwendungsbeispiele für eine Anfangswertaufgabe 2. Ordnung stellen der radioaktive Zerfall, die lineare Bewegung mit Newtonscher Reibung oder die Entladung eines Kondensators dar. Alle 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 Differential-gleichung durch den diskreten rechtsseitigen Ableitungsoperator (Differen-zenquotient). 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

+ −=

∆

Die Lösung der Anfangswertaufgabe erfolgt 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 den rechtsseitigen Differentialoperator für die Näherung der lokalen 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ösungs-intervall 0[ , ]t T . Dieser Fehler kann meist nicht exakt berechnet werden. Jedoch kann meist 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

tn n n n n n n

n n n n tn n n n

n n

n n n n tn n n

n n

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

+ + +

∆

∆

∆

= −

= − + ∆ ⋅ − + ⋅ −

= + ∆ ⋅ − + ⋅ −

−= + ∆ ⋅ + ⋅

−

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

( ) ( )2

1 2, ''tn n n n n nte 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 Kt

∂≤ ≤ >

∂.

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= + geschrieben werden, wodurch die Differentialgleichung 2. Ordnung mit reellen Lösungsvariablen zu einer Differentialgleichung 1. Ordnung mit komplexer Lösungsvariable transformiert wird.

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

Das obige Euler-Vorwärts-Verfahren in Matrixschreibweise ergibt

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


( )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.

1

2 3

exakte analytische Lösung

Euler- Vorwärts-Lösung

p

q

Veranschaulichung der linearen Extrapolation durch die Vorwärts-Ableitungs- Approximation 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 bei 1tγ∆ >

das falsche Vorzeichen. Dies führt zu einem Vorzeichenwechsel der numerischen Lösung in jedem Integrationsschritt und damit zu künstlichen Oszillationen. Bei

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 Aufgabe 7

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 Eigen-schaften der Lösung.

4.1.2 Rückwärts-Euler-Verfahren Anstelle des im Vorwärts Euler verwendeten rechtsseitigen Differential-operators 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 Gleichungs-systems oftmals gut numerisch handhabbar. Für nichtlineare Differential-gleichungssysteme muss man jedoch auf die iterative Lösung des entstehenden nichtlinearen Gleichungssystems zurückgreifen (Nullstellen-suche).

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 2

11

i tt

± ωλ =

+ ω ∆

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 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 Differentialoperators zur Verbesserung der Konvergenzeigen-schaften des diskreten Differentialoperators. 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 Differen-zenquotienten 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 folgendes Vorgehen an. Eine Verallgemeinerung der eben vorgestellten Methoden ist das Alpha-Ver-fahren, 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 Schrittintervall t∆ zu erhalten, werden bei den Eulerverfahren lediglich Informationen am Anfang oder Ende des Integra-tionsintervalls 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 Extra-polation, 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 Extra-polation einer Tangente im Startpunkt approximieren, 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 Crak-Nicolson-Verfahren, da auch dort der Anstieg in der Mitte des Einzelschrittintervalls berechnet wurde. Im Gege-nsatz zum impliziten Crak-Nicolson-Verfahren wird beim Runge-Kutta-Verfahren die Ableitungsbildung in der Intervallmitte durch einen expliziten Integrationsschritt abgeschä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 Genauigkeitsord-nung von 2 für die Berechnung der Lösung über dem gesamten Integrations-intervall. 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) Codebeispiel 7for 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) Codebeispiel 8for 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ösungsgenauigkeit zeigt die nachfolgende Abbildung die Lösung der Diffe-rentialgleichung '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 Integrationsschrittweite der beiden verglichenen numerischen Verfahren.

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

Aufgabe 8

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 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 Integrations-schritt die Ableitung an vier Punkten (dem Intervallanfangspunkt, zweimal in der Intervallmitte und der 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

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

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 Schritt-weite 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

Schrittweite ∆t

Fehler

Rundungsfehler

pt∆

1t∆

globaler Diskretisierungs- fehler

Gesamtfehler 1pt t∆ + ∆


• 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 (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 Rechenaufwand für die Fehler-abschä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änderlichkeit der verschiedenen abhängigen Variablen (z.B.


xf und yf ) von unabhängiger Variable (z.B. t ), wobei die schnell veränder-liche Komponente recht "glatt" verläuft

Beispiel für den Verlauf der numerischen Lösung einer steifen Anfangswert-aufgabe. Die numerische Lösung (gepunktet) wird aufgrund der bereits abge-klungenen Lösungskomponente 2y (physikalisch nicht mehr maßgeblich) instabil und verhindert eine akkurate Berechnung der physikalisch maßgeb-lichen 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 (Randbedingenen = 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 Mini-

mierungsverfahren, z.B. Newton − Wahl eines geeigneten Minimierungskriteriums, z.B. ( i

ierr 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

2

f 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 statio-nä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 Anfangswert-probleme 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

2

2

( , ) ( , )f x t f x tt 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 Differentialgleichung 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 Differentialgleichung

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

k f k tt

∂= −λ ⋅

∂

mit der Lösung

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

oder im Ortsraum

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

mit der Dispersionsrelation 2( )k kγ = −λ ⋅ 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:

− 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 diskre-tisiert

: 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 Differentialoperator geschrieben

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

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 • 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)


f

x

Crank-Nicholson (implizit)

diskreter Ortsdifferentialoperator für endliche Rechengebiete (bzw. auch mit periodischen Randbedingungungen) 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 kreisförmigen Struktur, entsprechen und die einfach zu lösende Tri-Diagonal-Form zerstören.

Für eine günstige Darstellung sei 2

tx

λ ⋅ ∆α =

∆.

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

+ = + ∆ ⋅ λ ⋅

= + ∆ ⋅ λ ⋅


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 dem-zufolge

( )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 constt 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 Ver-fahrens zu bestimmen.


Stabilitätsanalyse Anhand des Vorwärts-Euler-Verfahrens werden wir nun versuchen, eine Stabilitätsbedingung, für diese Differentialgleichung zu finden. Analog zur Betrachtung der analytischen Lösung, erfolgt die Stabilitätsanalyse durch Untersuchung der Lösungseigenschaften der numerischen Lösung für folgen-den Lösungsansatz ( ,0)exp( )exp( )n

jf f k 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 betrags-mäß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 be-schreiben, die Informationsausbreitungsgeschwindigkeit des Differenzen-schemas mindestens so hoch sein muss, wie die Ausbreitungsge-schwindigkeit 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 Schritt-weiten bestimmen sich eher aus der gewünschten Genauigkeit. Die Tat-sache, 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

( , )2

E z t i Ez 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.62

1i 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) Codebeispiel 9

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) Codebeispiel 101 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 Dreidimensionalen 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 aufwä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 ) Codebeispiel 11function [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) Codebeispiel 12

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

Computational Physics I - iap.uni-jena.dePhysics... · Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_2017-10-10s.docx 3 . 0. Einführung und Motivation