CP1 Skript 2009 04 19b Vorlesung 2009 07 06 Studentenskript · 2012-01-12 · Die Abhängigkeit der Konvergenz von h betrachten wir anhand des rechtssei-tigen Differentialoperators,

Skript Computational Physics I, FSU-Jena, Prof. T. Pertsch, CP1_Skript_WS2011/12, 08.11.2011 1

Computational Physics I Prof. Thomas Pertsch, Friedrich-Schiller-Universität Jena

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

1.1 Grundlagen ......................................................................................................... 3 1.1.1 Zahlendarstellung ............................................................................................... 3 1.1.2 Diskretisierung .................................................................................................... 4 1.2 Differentiation ...................................................................................................... 5 1.3 Integration ........................................................................................................... 9 1.3.1 Rechteckregel ................................................................................................... 10 1.3.2 Trapezregel ....................................................................................................... 11 1.3.3 Simpson-Regel ................................................................................................. 12 1.3.4 Implementierung von Intervallteilungsverfahren .............................................. 13 1.3.5 Gauss-Quadratur .............................................................................................. 15 1.4 Nullstellen & Extrema (Root Finding & Minimization/ Maximization) ............... 17 1.4.1 Nullstellen von Funktionen einer Veränderlichen ............................................. 17 1.4.2 Extrema von Funktionen einer Veränderlichen ................................................ 23 1.4.3 Minima von Funktionen mehrerer Veränderlicher ............................................ 25 1.5 Interpolation ...................................................................................................... 29 1.5.1 Interpolationsformel von Lagrange ................................................................... 30 1.5.2 Die Spline-Interpolation .................................................................................... 31 1.5.3 Rationale Approximation .................................................................................. 34 1.6 Lineare Gleichungssysteme ............................................................................. 35 1.6.1 Implementierung in Computer-Algebra-Systemen ........................................... 35 1.6.2 Gauss-Jordan-Elimination ................................................................................ 37 1.6.3 Lösung linearer Gleichungssysteme mit Tridiagonal-Matrix ............................ 38 1.6.4 LU-Zerlegung (Dekomposition, Faktorisierung) ............................................... 39 1.6.5 Iterative Verbesserung der Lösungsverfahren ................................................. 42 1.6.6 Eigenwertprobleme ........................................................................................... 43 1.7 Fourier-Transformation ..................................................................................... 44 1.7.1 Die diskrete Fourier-Transformation ................................................................. 46 1.7.2 Fast-Fourier-Transformation............................................................................. 48 1.7.3 Das Abtasttheorem ........................................................................................... 49

2. Lösung gewöhnlicher Differentialgleichungen ........................................ 51 2.1 Anfangswertaufgabe (AWA) ............................................................................. 51 2.1.1 Einschrittverfahren ............................................................................................ 52 2.2 Randwertaufgaben für gewöhnliche Differentialgleichungen ........................... 66 2.2.1 Methode der finiten Differenzen ....................................................................... 67 2.2.2 Schießverfahren ............................................................................................... 68

3. Partielle Differentialgleichungen ............................................................. 69 3.1 Elementar Methoden zur Lösung von partiellen Differentialgleichungen mit

Finite-Differenzen-Methode für Anfangswertaufgaben .................................... 70 3.2 Stabilitätsanalyse nach von Neumann ............................................................. 74 3.3 Split-Step-Verfahren ......................................................................................... 76

Ergänzung zu den Kapiteln ........................................................................... 79 Interpolation in höheren Dimensionen ........................................................................ 81

Ausgewählte Lösungsvorschläge .................................................................. 85


0. Einführung und Motivation Computational Physics ist ein Querschnittsfach aus den Bereichen Mathema-tik, Physik und Informatik. Ziel der Vorlesung Computational Physics I ist die Vermittlung der Grundlagen der physikalischen Modellbildung, Simulation, Datenanalyse und Visualisierung. Es handelt sich dabei weder um einen mathematisch fundierten Numerikkurs noch um eine Informatikvorlesung, sondern um eine den Bedürfnissen der Physik entsprechende Veranstaltung. Zum grundlegenden Verständnis physikalischer Systeme sind analytische Lösungen unabdingbar. Unter dem Gesichtspunkt der praktischen Anwend-barkeit erscheinen diese oft stark genäherten Lösungen jedoch nur bedingt brauchbar. Deswegen entwickelte sich die physikalische Modellbildung mit dem rapiden Anstieg der Leistungsfähigkeit der Computertechnik, zur Ver-wendung numerischer Standardverfahren hin. Dies erlaubt die Lösung be-deutend komplexerer Systeme, ohne vorzeitig nähern zu müssen. Wenn physikalische Experimente durch numerische Verfahren simuliert wer-den, muss sichergestellt werden, dass diese auch die Realität wiedergeben, d.h. mit der entsprechenden analytischen Lösung übereinstimmen, die jedoch häufig gar nicht existiert bzw. nicht bekannt ist. Dafür gibt es in der Numerik drei entscheidende Fehlerbewertungsmecha-nismen, die stark miteinander verbunden sind. Diese sind Kondition, Stabilität und Konsistenz. Die Analyse nach der Kondition eines Algorithmus unter-sucht das Verhalten einer numerischen Methode bei Störung der Eingangs-daten. Die Stabilitätsanalyse untersucht das Verhalten eines Verfahrens mit gestörten Eingangsdaten im Verhältnis zu analytischen Lösung. Die Konsis-tenzanalyse untersucht, ob der Algorithmus das gegebene Problem wirklich löst und nicht etwa ein anderes. Es muss dementsprechend immer sicherge-stellt werden, dass die gewählten numerischen Methoden das physikalische Problem widerspiegeln. Letztlich ist es die Aufgabe, die gewonnenen numerischen Kenntnisse in ei-ner Programmiersprache umzusetzen. Dazu wird in der Vorlesung Computa-tional Physics I das Programm MATLAB (bzw. die Programmiersprache MATLAB) verwendet.


1. Grundlegende Methoden der numerischen Ma-thematik

1.1 Grundlagen 1.1.1 Zahlendarstellung Da der Computer im Binärsystem rechnet, wird jede Zahl in einem Binärcode dargestellt, d.h. sie wird ausschließlich durch Nullen und Einsen repräsentiert {0 1}. Dabei gibt die Position der Eins oder Null in der Binärzahl die entspre-chende Zweierpotenz an. Der Übersetzungsmechanismus ist an diesem Beispiel verdeutlicht

7 6 5 4 3 2 1 0

0 1 0 0 1 1 1 02 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 sind die hexadezimalen Zah-len

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 Integertypen, d.h. ganze Zahlen mit oder ohne Vorzeichen und unter-schiedlichem Wertebereich. Der zweite Grundtyp sind Realtypen, mit denen rationale Zahlen dargestellt werden können. Aus diesen beiden Grundtypen können dann weitere Zahlentypen und Strukturen, wie z.B. komplexe Zahlen, abgeleitet werden.

Speicherplatz Für die Kategorisierung der Typen nach Speicherplatz – dieser bestimmt maßgeblich den Wertebereich – ergeben sich meist Einteilungen nach dem Muster

16 32 64 128 bit

da im Computer der Speicher im Raster von 8/16 bit adressiert wird. Dabei sind


1 bit 1 Speichereinheit mit 0 oder 1 belegt8 bit 1 Byte16 bit 1 Wort

Durch den Zahlenvorrat wird die Dynamik und Auflösung eines Zahltyps be-stimmt. Die Dynamik ist das Verhältnis vom größtem zum kleinsten Betrag und die Auflösung der Abstand zweier benachbarter Zahlen. Eine mögliche Aufteilung der Bits bei einem 64 Bit Realtyp ergibt sich in halb-logarithmischer Darstellung nach dem IEEE-Standard.

1 2s ez m

mit s: Signum: 1 Bitm: Mantisse: 52 Bite: Exponent: 11 Bit

Damit ergibt sich durch den Exponenten eine Dynamik von 10 10

1023 1023 308 308

e 2 21023 1023

2 2 10 10

Die Auflösung (relativ) ergibt sich aus der Mantisse zu 52 162 10

1.1.2 Diskretisierung Um numerische Berechnungen vornehmen zu können ist es notwendig, kon-tinuierliche Argumenten- und Werteverteilungen auf endliche diskrete Argu-menten- und Wertemengen abzubilden. Dies können einfach die Funktions-werte an diskreten Stützstellen oder Mittelwerte in einem Intervall um diskrete Stützstellen sein. Bei einer Entwicklung der kontinuierlichen Werteverteilung in ein Funktionensystem werden meist die Entwicklungskoeffizienten als dis-krete Wertemenge numerisch weiterverarbeitet. Es wird prinzipiell zwischen äquidistanter und nichtäquidistanter Diskretisierung unterschieden. Bei der äquidistanten Diskretisierung bleibt der Abstand zwischen den Stützstellen unabhängig vom zu lösenden Problem stets konstant. Bei der nichtäqui-distanten Diskretisierung wird der Stützstellenabstand dem Problem ange-passt und dementsprechend variiert. Die Funktionswerte zu diskreten Argumenten ix heißen dann i if x f . Es werden auch alle Operatoren diskretisiert, dabei werden aus analytischen Ausdrücken rein algebraische Formulierungen.


1.2 Differentiation Für eine gegebene Diskretisierung if der Funktion f x wird ein diskreter Differentialoperator ( ) : 'D f x f x gesucht. Dabei wird von der Definition einer Ableitung ausgegangen, z.B. rechtsseiti-ger/vorwärts Differenzenquotient

0

( ) ( ) ( )( ) limh

f x f x h f xf xx h

Für endliche h ergibt sich demnach ( ) ( )[ ( )]h

f x h f xD f xh

oder analog der linksseitige diskrete Differentialoperator: ( ) ( )[ ( )]h

f x f x hD f xh

.

Codeschnipsel 1 (Differentiation ) 1 x=0:0.01:2*pi; %Diskretisierung von x 2 y=sin(x); %diskrete Funktionswerte 3 h=0.01; %Stützstellenabstand 4 dy= sin(x-h); 5 df = (y - dy)/h; %diskrete Ableitung 6 7 plot(x,y); %Funktions Plot 8 hold on; 9 plot(x,df,'r');%Ableitungs Plot

Fehlerabschätzung Für die Numerik ist eine Abschätzung der durch die Diskretisierung hervorge-rufenen Fehler von Bedeutung. Der Diskretisierungsfehler ist

( ) [ ( )]h hE f x D f x

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 die beiden Operatoren ge-gen die analytische Lösung konvergieren. Die Abhängigkeit der Konvergenz von h betrachten wir anhand des rechtssei-tigen Differentialoperators, mit Hilfe einer Taylorentwicklung der Definition:


2 3 4

2 3

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

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

[ ( )] ( ) ( )

h

h

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

f x h f xD f x f x f x h f x h O hh

D f x f x O h

Für den linksseitigen Differentialoperator verläuft die Rechnung analog. Beide Operatoren konvergieren demnach in erster Ordnung und der Diskretisie-rungsfehler geht mindestens mit h gegen Null.

Stencil-Notation Eine verkürzte Schreibweise ist die sogenannte Stencil-Notation (Stencil = Schablone), welche die Vorfaktoren vor den Funktionstermen bezüglich h no-tiert. Die beiden bereits definierten Operatoren schreiben sich dann folgen-dermaß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

Durch geschickte Kombination dieser beiden Varianten ist es möglich Diffe-rentialoperatoren zu konstruieren, die mit höheren Ordnungen konvergieren. Z.B. Elimination des h-Fehlerterms mittels

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

.

Es folgt der zentrale Operator ( ) ( )[ ( )]

2hf x h f x hD f x

h

mit verbesserten Konvergenzeigenschaften, da

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

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


Diskrete Ableitungen der Funktion sin( )x im Vergleich zur analytischen Lö-

sung

Dieses Verfahren lässt sich weiter verfeinern, indem man in der Stencil-Notation des zentralen Operators zu einem breiteren Stencil übergeht, d.h. von h zu 2h und dann versucht, durch Kombinationen verschiedener Opera-torformen 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 h³ konvergiert.

Höhere Ableitungen Um höhere Ableitungen darzustellen, startet man wieder bei der Taylorent-wicklung


2 3 4

2 3 4

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



Addieren und Umstellen der beiden Terme 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 Ord-nung konvergiert (beachte O(h4)/h2=O(h2)).

Spektralverhalten der Ableitungsoperatoren Nachdem wir untersucht haben, wie sich die Operatoren in Abhängigkeit von h verhalten, untersuchen wir nun, wie sich die Operatoren in Abhängigkeit von der Funktion verhalten, auf die sie angewandt werden. Für lineare Opera-toren eignen sich als Testfunktion die Fourier-Moden, da die Wirkung eines Operators auf alle Fouriermoden die gesamte Information über den Operator enthält.

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

ik x h ik x h ikxikx ikh ikh

h

ikx

Dh h

ik khkh f xhk kh

Der spektrale Diskretisierungsfehler ist demnach

s

sin1

khE f x

kh


0 1 2 3 4

0

0.2

0.4

0.6

0.8

1

x

sinc (x)

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

Aus dem Graphen lassen sich sehr einfach die spektralen Eigenschaften des Operators ablesen: 1kh für niederfrequente bzw. langwellige Moden folgt, wie wir oben

bereits gesehen haben, eine Konvergenz in 2. Ordnung 2sin

1 [ ]kh

O khkh

kh für hochfrequente bzw. kurzwellige Moden folgt: sin0

khkh

, d.h.

der zentrale Operator verschwindet immer

2kh sin0

khkh

, d.h. der Ableitungsoperator liefert das falsche

Vorzeichen

1.3 Integration Nachdem wir uns im vorangegangenen Abschnitt mit der numerischen Diffe-rentiation beschäftigt haben, untersuchen wir jetzt das Gegenstück, die nu-merische Integration. Ziel dieses Abschnittes ist es, Verfahren vorzustellen, um für eine gegebene Funktion ( )f x auf einem definierten Intervall das be-stimmte Integral zu ermitteln

b

a

A dx f x .

Zuerst wenden wir uns Standardverfahren zu, welche das zu integrierende Gebiet in gleich große Teilgebiete zerlegen und versuchen die entstehenden Teilintegrale zu nähern. Für die Zerlegung ergeben sich auf dem Intervall ,a b N gleich große Teilintervalle. Die Intervalle sind dann 1[ , ]i i iI x x mit der Intervallbreite 1i ih x x bzw. ausgedrückt durch die Intervallgrenzen

b ahN

.


Zerlegung in gleichgroße Teilintervalle

Dabei ist 0x a , Nx b . Die Fläche unter der Kurve im nun geschachtelten Intervall ist dann

1[ , ]i i iI x x mit 1i ix x h und b ahN

wobei 0 , Nx a x b und h die Inter-

vallbreite, d.h.

11

0

.i

i

xN

i x

A dx f x

Die Aufgabe besteht darin, 1i

i

x

ix

A f x dx

im i-ten Teilintervall möglichst ge-

nau zu bestimmen.

1.3.1 Rechteckregel Haben wir die N ausreichend schmalen Teilintervalle, approximieren wir die-se durch Rechtecke. Dazu benötigen wir eigentlich den Mittelwert des Funk-tionswertes im Teilintervall. Man wird leicht einsehen, dass dieser ziemlich aufwendig zu berechnen ist. Für langsam veränderliche Funktionen ist der Funktionswert im Mittelpunkt des Teilintervalls

12

( )2i ii

hf x f f x

jedoch eine recht gute Approximation seines Mittelwertes – dies ist die Idee der Rechteckregel. So ergibt sich das gesamte Integral 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 Integrales durch Rechtecke mit Höhe des In-

tervallmittelpunkts

Fehlerbetrachtung Um den durch die Näherung verursachten Fehler analysieren zu können, be-trachten wir eine Taylorentwicklung um den Intervallmittelpunkt

1 1 1 12 2 2 2

2 3 4

1 1 1 12 2 2 2

1 1 1( ) ' '' '''1! 2! 3!i i i ii i i i

f x f f x x f x x f x x O x x

sodass die ungeraden Terme durch die Integration verschwinden

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

doch N~1/h Summanden stehen, konvergiert das Gesamtintegral nur in 2. Ordnung, mit dem Rechteckfehler

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 be-nötigt werden und dadurch keine Probleme mit eventuellen Singulari-täten auftreten.

1.3.2 Trapezregel Bei dieser Methode werden die Teilintegrale durch Trapeze genähert, die den Verlauf der Funktion vermeintlich besser darstellen können als Rechtecke. Das Integral 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 Integrals durch Trapeze

Fehlerbetrachtung Durch Vergleich mit der Struktur der Rechteckregel, sieht man, dass Funkti-onswert im Intervallmittelpunkt genähert wird durch

112 2

i i

i

f ff

Fehlerberechnung erfolgt durch ersetzen von 1 12 2

241

2 8i i

i i

f f hf f O h

in

Rechteckregel. Somit

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. Fehler der Trapezregel ist jedoch doppelt so groß wie bei Rechteckre-

gel. Trapez-Verfahren lässt sich im Vergleich zu Rechteckregel aber sehr

einfach rekursiv von N auf 2N verfeinern, da schon berechnete Stütz-stellen wieder benutzt werden können

1.3.3 Simpson-Regel Das Simpson-Verfahren nähert die zu integrierende Funktion in den Teilinter-vallen durch Parabeln. Bisher hat die symmetrische Entwicklung um den Intervallmittelpunkt bereits zum Verschwinden der ungeraden Ableitungen geführt

1

1

352 0 0

3

i

i

x

i ix

hf x dx h f f O h

.


Jetzt wollen wir eine weitere Verbesserung durch das Ersetzen der zweiten Ableitung durch den diskreten Differentialoperator mit 3-Punkt-Stencil

2[1 2 1]/ h erreichen

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 1,3,5,..., 1i N bei geradem N ergibt für Gesamtinteg-ral

40 1 2 3 14 2 4 ... 4

3 N NhA f f f f f f O h .

Wir erhalten so ein Verfahren, das in 4. Ordnung konvergiert und für Polyno-me bis einschließlich 3. Grades sogar exakt ist. Das Verfahren der Approximation durch Polynome lässt sich natürlich noch weiter verbessern, die Bode-Regel liefert mit

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

eine Formel, die in 6. Ordnung konvergiert (hinreichende Glätte vorausge-setzt) und für Polynome bis zum 5. Grad exakt ist.

1.3.4 Implementierung von Intervallteilungsverfahren Die Fehlerkontrolle für alle Verfahren die auf der Teilung des Integrationsin-tervalls in viele Teilintervalle und Näherung der Funktion in diesen kleinen Intervallen beruhen, lässt sich durch folgenden Algorithmus leicht implemen-tieren

1: Vorgabe einer Zielgenauigkeit ε 2: Wahl von N und Berechnung von NA

3: Halbieren der Intervallbreite 22hh N N , Berechnung von 2NA

4: Schritt 3 solange wiederholen bis 2N NA A Die Simpson- Regel stellte sich als genauerer Algorithmus zur numerischen Integration heraus und hatte einen kleineren Fehler im Vergleich zur Trapez-Regel. Der folgende Kodeschnipsel zeigt eine einfache Implementierung der Trapezregel in MATLAB. Dabei soll die Integralberechnung auf Teilintervallen rekursiv wiederholt werden, auf denen der mittels Simpson-Regel geschätzte Fehler eine bestimmte Toleranz überschreitet.

Codeschnipsel 2 (Trapezregel…) function [Int I]=trapez(f,I,tol) % [Integral Intervall] = trapez(@func_name,Intervall,toleranz) % berechnet das Integral einer uebergebenen Funktion f % in den Grenzen I(1) bis I(2) mittels Trapezregel und einer


% Toleranz tol % Die Funktion gibt den berechneten Integralwert % und den Vektor der Gitterstruktur zurueck %Trapezregel Int = (I(2)-I(1))/2 * (feval(f,I(1)) + feval(f,I(2))); %Simpsonregel 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

Beispielhaft wollen wir das Integral

0

sin( )A x dx

berechnen. Das analytische Ergebnis ist 2A . Wir müssen dabei noch die Sinus-Funktion implementieren. Beispielsweise durch

Codeschnipsel 1 (…Trapezregel…) 1 function y=f1(x) 2 % Trigonometrische-Funktion y=sin(x) 3 y=sin(x); 4 end

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

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

Wir erhalten 1.9879A . Die eigentliche Stärke von MATLAB liegt in einem umfangreichen Repertoire an bereits implementierten Funktionen. Das numerische Integrieren mit Hilfe der Trapezregel lässt sich in MATLAB z.B. viel schneller realisieren:

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


1.3.5 Gauss-Quadratur Es besteht weiterhin das Ziel der genauen Näherung des Integrals mit weni-gen Funktionsberechnungen. Bisher wurde dafür das Integrationsintervall [a,b] in viele Teilintervalle [xi,xi+1] zerlegt, in denen die zu integrierende Funk-tion mit Polynomen zweiter bzw. dritter Ordnung genähert wurde. Jetzt wollen wir diese Idee aufgreifen und das gesamten Intervall [a,b] durch eine analy-tisch integrierbare Funktion hoher Ordnung näheren, z.B. mit Hilfe einer or-thogonalen Basis iP (Legendre o.Ä.). Obwohl dies prinzipiell zu einer sehr hohen Genauigkeitsordnung führen kann, ist Vorsicht geboten. „Hohe Ord-nung“ bedeutet nur „hohe Genauigkeit“, wenn die Funktion hinreichend glatt ist, im Sinne einer guten Approximierbarkeit durch ein Polynom. Eine Funkti-on ( )f x wird nun also durch einen Satz von Polynomen ausgedrückt

0

( ) ( )n

i ii

f x P x

n „klein“ → wenig Basiselemente

Die Bestimmung der Koeffizienten i folgt aus der Orthogonalität der iP

( ) ( )b

i j ija

dx P x P x

durch die Lösung eines linearen Gleichungssystems, was die wesentliche numerische Aufgabe darstellt. Das zu lösende Integral bestimmt sich dann aus

1 1

( ) ( ) ( )b bn n

i i i ii ia a

dx f x dx P x w f x

mit wi, als den für einen jeweiligen Polynomtyp zu bestimmenden Gewichts-funktionen. Der Nährungsfehler ist klein, wenn ( )f x gut in gewählte Basis iP entwickelbar ist. Die Abschätzung des Fehlers ist allgemein nur schwer mög-lich. 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 auszuweiten ist lediglich eine Variablentransformation vorzu-nehmen. Aufgabe 1

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

0

sin( ) 2A x dx

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

Schreiben Sie ein Programm (Funktion), um die Simpson-Regel in MATLAB zu im-


plementieren. Nutzen Sie dabei die im obigen Codeschnipsel gezeigte Funktion f1 (function y = f1(x)) und testen Sie es durch eine Integration der oben genannten Funktion.


1.4 Nullstellen & Extrema (Root Finding & Minimization/ Maximization)

1.4.1 Nullstellen von Funktionen einer Veränderlichen Die Aufgabe ist das Finden von Nullstellen von ( )f x im Intervall ,a b . Die Lösungsansätze beruhen auf Iterationsverfahren, die einen Startpunkt ix in ,a b nach 1ix verbessern bis * 0f x . Die nachstehenden Abbildungen verdeutlichen dabei einige Situationen, die bei der Suche nach Nullstellen auftreten können. Die Wahl eines speziellen Verfahrens zu Suche nach Nullstellen richtet sich oft nach den Eigenschaften der betrachteten Funktion.

Eine isolierte Nullstelle im Intervall.

Es können bei gleichen Vorzeichen der Intervallsgrenzen dennoch z.B. dop-

pelte Nullstellen auftreten.


Es muss bei Vorzeichenwechsel der Intervallsgrenzen nicht zwingend eine

Nullstelle existieren.

Diese Funktion zeigt, dass durchaus eine große Anzahl an Nullstellen existie-

ren kann

1.4.1.1 Bisektion Bei der Bisektion wird das Intervall so lange halbiert bis die Intervallgrenzen, welche die Nullstelle einschließen, hinreichend identisch sind. Dabei wird nur das Vorzeichen von ( )f x untersucht und nicht der Wert von ( )f x , was re-chentechnisch von großem Vorteil sein kann. Das nach stehende Strukto-gramm verdeutlicht noch einmal das Verfahren der Bisektion.


Schematischer Ablauf des Bisektionsverfahrens unter der Annahme

( ) 0 ( ) 0f a f b

1.4.1.2 Sekantenverfahren Für das Sekantenverfahren wird mit zwei Funktionswerten eine Sekante kon-struiert. Die Extrapolation- oder Interpolationslinie ergibt dann einen Schnitt-punkt mit der x-Achse der der den älteren der beiden Startwerte ersetzt. Für die Argumente der Funktion ergibt sich folgende Iterationsformel

11

1

( )( ) ( )

i ii i

i i

x xx x f xf x f x

.

Da bei diesem Verfahren der Nenner zwangsläufig klein wird und gegen nu-merisch Null konvergiert, ist es sinnvoll eine Abbruchbedingung einzuführen

1 10i i if x f x f x

dabei ist ε die relative Maschinengenauigkeit.


Illustration des Sekantenverfahrens. Die einzelnen Punkte sind in der Reihen-

folge ihrer Benutzung nummeriert.

Abschließend eine mögliche Implementierung des Sekantenverfahrens. Codeschnipsel 3 (Sekantenverfahren)

1 function [x,i,status] = sekante(x0,x1,tol1,tol2,no) 2 3 %x0,x1: Startwerte 4 %tol1, tol2: Toleranzen 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 zwichen 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.4.1.3 Regula Falsi (False Position Method) Die Regula Falsi erweitert das Sekanten-Verfahren um die zusätzliche Be-dingung, dass die neue Sekante nur durch die beiden letzten Iterationspunkte gezogen wird, welche die Nullstelle einschließen. Konkret bedeutet dies, dass falls

1 1( ) ( ) 0 ,i i i if x f x x x

dann werden die beiden neuen Iterationspunkte weiterverwendet bzw. 1 1 1 1( ) ( ) 0 ,i i i if x f x x x

Dadurch konvergiert das Verfahren langsamer, allerdings wird ein Abdriften der Iterationspunkte von der Nullstelle verhindert.


Regula-Falsi (False Position Method): Die nächsten Iterationspunkte müssen

dabei stets die Nullstelle umschließen.

Bevor wir zu einem weiteren Verfahren kommen, soll die nachstehende Ab-bildung 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 ge-braucht. Auch viele andere Verfahren ergeben hier keine Verbesserung.

Weitere Ergänzungen zur Fehlerbetrachtung des Verfahrens stehen im An-hang.


1.4.1.4 Newton-Raphson Bei diesem Verfahren ( )f x durch eine Taylorentwicklung genährt (meist nur 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

woraus die Iterationsformel abgeleitet werden kann

1( )( )

ii i

i

f xx xf x

Das Verfahren konvergiert quadratisch, da sich der Fehler wie folgt entwickelt

21

( )2 ( )

ii i

i

f xE Ef x

Eigenschaften des Verfahrens: in jedem Schritt Verdopplung der korrekten Stellen sehr schnell Maschinengenauigkeit erreicht funktioniert nur sicher in der Nähe von Nullstellen gut auf mehrere Dimensionen verallgemeinerbar kombinierbar mit Sekantenverfahren/Regula-Falsi (erst Sekante bis in

Nähe der Nullstelle, da allgemeine Konvergenz, dann Newton Rapson, da schnell zur Maschinengenauigkeit)

Aufgabe 3

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

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

1.4.2 Extrema von Funktionen einer Veränderlichen Da das Auffinden von Nullstellen häufig aufwendig ist, wird diese Aufgaben-stellung oft in ein Mi-nimierungsproblem umgewandelt, indem genutzt wird, dass an einer Nullstelle das Quadrat der untersuchten Funktion ein Minimum hat. Deswegen werden wir nun einige Algorithmen untersuchen, um Minima effizient zu lokalisieren. Damit ist auch die Frage nach eventuellen Maxima beantwortet, da diese Minima des Reziproken sind. Damit ein Minimum im Intervall existiert, muss für eine im Intervall [a,c] steti-ge, nach unten beschränkte Funktion folgendes gelten: Wenn für ein Punktetripel a<b<c (oder c<b<a) f b f a und f b f c ist, so folgt daraus die Existenz eines Minimums im Intervall [a,b].


1.4.2.1 Verfahren des goldenen Schnittes (Golden Section Se-arch)

In Analogie zum Bisektionsverfahren besteht nun die Aufgabe darin, einen neuen Punkt x zu wählen, entweder im Intervall [a,b] oder im Intervall [b,c]. Nun bestimmen wir dessen Funktionswert. Für den Fall f b f x ist das nächste Punktetripel (a, b, x). Für f b f x nehmen wir das Tripel (b, x, c). Der Mittelpunkt des Triplets ist dann der Abszisse am nächsten und ist bis dahin un-ser Minimum. Diesen Schritt der Einschachtelung wiederholen wir solange, bis die Intervallbreite eine bestimmte Toleranz unterschreitet.

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

Wie sollte nun die Intervallteilung erfolgen, damit unabhängig vom Funktions-verlauf eine optimale Konvergenz zum Minimum erfolgt? Das ist gleichbe-deutend mit der Forderung, dass die neue Intervallgröße unabhängig vom Erfolgsfall der Teilung sein soll = Neues Intervall in jedem Fall gleich groß. a+c=b oder x4-x1=x3-x2 x4=x3-x2+x1

Weitere Forderung: Intervallreduktion soll gleich bleiben (nicht langsamer werden) Lösung: Verhältnis der Teilintervalllängen (a/b) soll bei folgenden Iterationen konstant bleiben Verkleinerung des Suchintervalls mit konstanter Rate Fall f4a neues Tripel ist x1, x2, x4 dann soll (a/b)=(c/a) sein Fall f4b neues Tripel ist x2, x4, x3 dann soll (a/b)=(c/)[b-c]) sein Durch Elimination von c aus beiden Gleichungen folgt:

2/ ( / ) 1b a b a

mit der Lösung:

/ (1 5) / 2 1.618033989...b a

Dieses Verhältnis entspricht dem goldenen Schnitt und ist die gesuchte Be-dingung für die Position von x2.


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. Eben für ein „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äheren? 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 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 Abbil-dung soll die Methode noch einmal verdeutlichen.

Das Minimum wird bei dieser Methode durch Interpolation von Parabeln ge-sucht. Durch drei Punkte 1,2,3 auf der gegebenen Funktion (durchgezogene Linie) wird eine Parabel gelegt (gestrichelte Linie). Deren Scheitelpunkt führt zu neuem Punkt 4 auf der gegebenen Funktion. Nun wird durch die Punkte 1,2,4 eine Parabel gelegt (gepunktet) usw. So ist der Scheitelpunkt 5 der zweiten Parabel schon nahe dem Minimum der Funktion.

1.4.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 nun auf mehrdimensionale Funktionen erweitern


1.4.3.1 Downhill-Simplex-Methode Die Downhill-Simplex-Methode ist ein auf Minima konditionierter Suchalgo-rithmus für einen Simplex. Ein Simplex ist ein n-dimensionale Punktmenge aus n+1 Punkten, wobei die Verbindungslinien zwischen den Punkten alle-samt linear unabhängig sind. Im Zweidimensionalen ist dies ein Dreieck, im Dreidimensionalen ein Tetraeder.

Spiegelung Expansion/Kontraktion

S

P

P

Graphische Darstellung der Simplexoperationen an einem 2D Simplex

Das Verfahren sieht mit der Implementierung nach Nelder und Mead folgen-dermaßen aus

1. Wähle beliebige Punkte, die einen Simplex aufspannen und be-stimme deren Funktionswerte

2. Suche den ‚Besten’ Punkt B und ‚Schlechtesten’ Punkt S (kleins-ter/größter Funktionswert)

3. Der Punkt S wird um den Simplexmittelpunkt gespiegelt und o i. wenn der neue Punkt P besser als alle anderen ist, dann

strecke den Simplex in dieser Richtung und ersetze Punkt S durch den neuen gestreckten Punkt P

o ii. ist der Punkt P nur ‚besser’ als Punkt S, dann ersetze Punkt S durch Punkt P

o iii. ist der Punkt P ‚schlechter’ als Punkt S, dann kontrahiere den Simplex unter Beibehaltung der anderen Punkte

4. wiederhole Schritte 2 und 3 bis das Simplexvolumen hinreichend klein ist.

Je nach Problemstellung ist es noch möglich, die Punkte unabhängig von den Implementierungsschritten zu verändern um ein Festfahren des Simplex zu verhindern.

1.4.3.2 Minimierung in alternierende Richtungen Eine andere Minimierungsmethode greift direkt auf die bereits im vergange-nen Abschnitt vorges-tellten Konzepte zurück. Bei der Minimierung in alter-nierende Richtungen werden für eine n-dimensionale Funktion n eindimensi-onale Minimierungsaufgaben in n verschiedene Richtungen gelöst.


Für einen gegebenen Startpunkt 1P

und 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 wesent-liche Verbesserung mehr zu erzielen ist. Die Wahl der Minimierungsrichtungen beeinflusst wesentlich die Effizienz des Verfahrens. Die einfachste Wahl für die Minimierungsrichtungen sind die Ko-ordinatenachsen, allerdings ist dies meistens nicht die effektivste Variante.

x

y gute Konvergenz schlechte Konvergenz

Gebiete mit guter und schlechter Konvergenz der Minimierung in alternieren-

de Richtungen

Methoden zur Richtungsfestlegung werden wesentlich danach unterschieden, ob sie die Ableitung der zu minimierenden Funktion einbeziehen oder nicht. Ziel bei der Richtungswahl ist das Auffinden von „konjugierten“ Richtungen der Eigenschaft, so dass die Minimierung in iu nicht durch die nachfolgende Minimierung in Richtung 1iu

beeinträchtigt wird.

1.4.3.3 Gradientenverfahren (Steepest Descent) Eine Methode zur effektiven Richtungswahl ist das Verfahren des steilsten Abstieges, auch als Gradientenverfahren bekannt. Die Idee ist, dass die Rich-tung entgegen der des Gradienten steht, d.h.

1i i iiP P f P

mit min i ii tf P t f P


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 geht, diese Richtung muss nicht notwendigerweise zum Minimum führen. Zudem ist der Gradient in der Nähe eines lokalen Minimums numerisch nur schwer zu bestimmen.

„Gutes“ und „schlechtes“ Beispiel des Gradientenverfahrens

Was sind nun konjugierte Richtungen? mögliche Methode: zuerst Minimieren entlang u danach steht Gradient senkrecht auf u nun Taylor-Entwicklung nach x um Ursprung p

2

12

,

12i i j

i i ji i jp p

f ff x f p x x x c bx x Âxx x x

mit 2

p iji j p

fc f p b f Âx x

(Hesssematrix)

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

f Âx b

Veränderung des Gradienten bei Verschiebung: f Â x

Resultierendes Vorgehen: zuerst Minimierung entlang iu danach Minimierung entlang 1iu

konjugiert wenn Gradient senkrecht zu iu bleibt


10 i i iu f u Âu

Resultierende Methode: Wahl von N linear unabhängigen paarweise konjugierten Minimierungs-

richtungen ( N -Dimensionen) dadurch für quadratische Funktion Minimierung in N Schritten quadratische Konvergenz: mit jedem Schritt doppelte Anzahl richtiger Stel-

len jedoch komplizierte und auf Ableitungsbildung beruhende Bestimmung der Richtungen

1.4.3.4 Powell’s Methode Wenn das Bilden von Ableitungen vermieden werden soll, bietet sich Powell’s Methode an. Diese erzeugt paarweise zueinander konjugierte Richtungen. Dazu wird folgende Schleife hinreichend oft durchlaufen, wobei die Startrich-tungen entlang der Koordinatenachsen gewählt werden.

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.

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 „Konjugierte-Gradienten-Methode“ die Methode der Wahl (siehe Literatur, z.B. Numerical Recipes).

1.5 Interpolation Um aus Messungen gewonnene Daten physikalisch interpretieren zu können, ist es meistens notwendig die Messwerte zu interpolieren bzw. zu extrapolie-ren. 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 Bereichs kann meist nicht durch allgemeingültige Methoden erfolgen, sondern sollte stark durch das generelle Verhalten des physikalischen Problems geprägt sein.

1.5.1 Interpolationsformel von Lagrange (wird auch als Laplace’sche Interpolationsformel bezeichnet) Bei der Lagrange-Interpolation geht man von n Punkten 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 Gesucht ist ein Polynom vom Grade ( 1)n , welches alle Punkte verbindet

1

10

nj

n jj

y x P x A x

Zur Bestimmung der Koeefizienten 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

deshalb ist 11 1

nnk

n jj k j k

k j

x xP x yx x

das Polynom mit den gesuchten Ei-

genschaften, da

1 1

( )n n

j k j jk k jk k

P x P x y y

.


Da mit dem Grad des Polynoms auch die Anzahl der Maxima und Minima steigt (ein Polynom (n-1)-ten Grades hat (n-2) Extrema), neigt die Interpolati-onsfunktion zum „Schlängeln“. Kapazitätsprobleme bei der Polynombestim-mung ergeben sich bei hoher Stützstellenanzahl (als Faustregel: ab >100), da dann die numerische Produktberechnung instabil wird. Hier bietet sich ei-ne Interpolation in Teilintervallen an. Ein darauf basierendes Verfahren wer-den wir nun behandeln. Außerhalb des Intervalls verhält sich die Funktion wie ein Polynom n-ten Grades und ist daher für eine Extrapolation nicht geeignet. Der Fehler hängt im Wesentlichen von der Wahl der Stützstellen ab, ist aller-dings für äquidistante Stützstellen an den Intervallrändern besonders groß. Dies kann durch eine optimierte Stützstellenwahl umgangen werden, wenn z.B. die Stützstellen die Nullstellen des Tschebyscheff-Polynoms bilden.

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.5.2 Die Spline-Interpolation Die Lagrage-Interpolation hatte zum Einen starke Oszillationen, zum Anderen ist sie instabil bei der Bestimmung großer Produkte. Ein besseres und heute übliches Verfahren ist die Spline-Interpolation, bei der die Funktion nur in je-weils kleinen Intervallen 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 stark ab. (Ein Kodeschnipsel zur Lagrangeinter-

polation und diesem Plot findet man im Anhang)

Spline: (aus Schiffsbau) Biegsame Latte durch alle Punkte legen und deren Spannung minimieren (Variationsproblem z.B. minimieren von [ ( )]²dx s x – schwierig) Die gebräuchlichsten Splines sind kubische, d.h. Polynome dritten Grades. 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 n-1 Intervallen ergibt dies 4(n-1) Parameter und genauso viele Bedingungen. Wie das entstandene lineare Gleichungssystem zu lösen ist, wird im Kapitel 1.6 vorgestellt.

Beispielrechnung

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

, 1, ,j jx y j n

mit dem äquidistanten Abstand

1j jh x x

Der Spline im Intervall 1,j jx x

1 mit ,j j js x x x x

hat dann die Form

2 31 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 xj 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

0

0n

a

a

Durch Einsetzen der Gleichungen ineinander lässt sich ein lineares Glei-chungssystem für 2

ja finden. Aus diesem können dann die anderen Koeffi-zienten ( 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 aufge-stellt. 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.5.3 Rationale Approximation Falls die zu interpolierende Funktion Polstellen aufweist, erscheint folgender Polynomansatz günstig

n

m

P xy x

Q x

wobei P und Q Polynome vom Grade n bzw. m sind. Die Anzahl N der be-kannten Stützstellen kx bestimmt die Polynomgrade durch 1N m n . Ne-ben der Anzahl der Pole ( m ) kann z.B. mit m n j die physikalische In-formation ü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


1.6 Lineare Gleichungssysteme Im Folgenden werden Verfahren zu Lösung von linearen Gleichungssyste-men 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 4

...

......

n

n

m m m m

a a aa a 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

.

1.6.1 Implementierung in Computer-Algebra-Systemen Für die Anwendung der 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, tre-ten numerische Singularitäten auf. Diese müssen gesondert betrachtet wer-den. Falls die Vektoren unterschiedliche Dimensionen haben ergeben sich entwe-der Lösungsräume, im Falle einer unterbestimmten Lösung, oder, bei einer überbestimmten Lösung, muss zusätzlich ein Minimierungsproblem gelöst werden. Hier Konzentration auf den Fall n m Probleme bei analytischer Lösung: degenerierte Probleme


eine Zeile ist Linearkombination von anderen Zeilen zeilendegene-riert

äquivalent dazu: spaltendegeneriert beide Fälle führen auf singulä-re Probleme

Probleme bei numerischer Lösung: Problem numerisch nahezu singulär durch Rundungsfehler ist Sin-

gularität entstanden Problem zu groß große Rundungsfehler (mit Singularität verbun-

den) Aufgabentypen:

Lösung von Ax b

Lösung von ˆj jAx b

, d.h. mehrere jb

jx für ein A

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 ähnli-cher Strukturen entstehen, wurden für häufig auftretende Problemtypen an-gepasste Lösungsmethoden entwickelt. Typische Matrixstrukturen sind z.B.

1. hermitesche Matrizen: †ˆ ˆA A (komplexe Konjugation und Transpo-sition)

2. Bandmatritzen:

Bandmatrix

3. tridiagonale Matrizen:

0

0

Tridiagonal-Matrix


4. Blockmatrizen:

Blockmatrix

5. Sparsematrizen: Matrizen mit sehr vielen Nullen. 6. positiv definite Matrizen: ˆ 0vAv v

immer spezielle Eigenschaften der Matrix nutzen, um angepasste Lö-sungsmethode anzuwenden Neben der Unterscheidung nach Matrixtyp unterteilt man die Lösungsverfah-ren 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 Verbesse-

rung der Genauigkeit Die Qualität der Lösung hängt natürlich von dem der Methoden zu Verfügung gestelltem Speicher und der Rechenkapazität ab. Der Speicherverbrauch kann dabei meist manuell, je nach gewünschter Genauigkeit des verwende-ten Zahlenformates eingestellt werden.

1.6.2 Gauss-Jordan-Elimination Dieses Verfahren stellt eine Verbesserung des aus der linearen Algebra be-kannten 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

vertau-schen.

2. eine Zeile von A und entsprechende Elemente von b

mit einer Kon-stanten 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 durch Rücksubstitution bzw. direkt abgelesen werden. Da bei einer ungünstigen Verteilung der Koeffizienten während der Rechnung numerische Singularitäten beim dividieren durch kleine Zahlen auftreten kön-nen, ist es sinnvoll die Zeilen so anzuordnen, dass durch große Beträge divi-diert wird, um Singularitäten zu vermeiden. Dies bezeichnet man als Pivoti-sierung. 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 obe-

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

Matrixinversion Das Gauss-Jordan-Verfahren dient weiterhin zur Berechnung der Inversen einer Matrix. Dabei wird bei einer n n -Matrix A das Verfahren angewandt und simultan jede einzelne Zeilenoperation an einer n n -Einheitsmatrix E durchgeführt. Die aus der Einheitsmatrix schließlich resultierende Matrix ist

-1A mit -1AA E .

1.6.3 Lösung linearer Gleichungssysteme mit Tridiagonal-Matrix

Dies ist ein für physikalische Probleme häufig auftretender und einfach zu lö-sender Spezialfall. Gesucht wird die Lösung eines linearen Gleichungssys-tems der Struktur


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 Eins-Matrix überführt wird.

1 ( 1) 1N N

i i i i

u du d c u i N

1.6.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 Ldie untere („lower“) Dreiecksmatrix (diese hat nur auf der Haupt-diagonalen und darunter von Null verschiedene Einträge) und Udie obere („upper“) Dreiecksmatrix (diese hat nur auf der Hauptdiagonalen und darüber von Null verschiedene Einträge) sein.


Die obige Gleichung hat also 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

ˆ ˆ ˆ ˆ ˆA 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 haben, die durch „Vorwärts-Elimination“

11

11

1

1

1 i

i i ii jjii

byl

y b l yl

2,3,...,i n

und „Rückwärts-Elimination“

1

1

1

n

nn

n

i i ij jj iii

yxu

x y u xu

1, 2,...,1i n n

gelöst werden können. Doch wie lassen sich Lund U bei gegebenen A bestimmen? Die Koeffizien-ten der n n -Matrizen Lund U zu bestimmen heißt 2n n Unbekannte zu fin-den (die Hauptdiagonale ist doppelt belegt!). Da durch die matrixA jedoch nur 2n Gleichungen resultieren sind wir gezwungen n Koeffi-zienten frei zu wählen und die Gleichung für die anderen 2n zu lösen. Ein sehr einfacher Algorithmus dafür ist der Crout’s-Algoritmus.


Crout’s-Algorithmus: Ableitung des Algorithmus 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 nun leicht (explizit) aus der Ursprungsmatrix ablesen, wenn man die richtige Reihenfolge

11 12 13 21 31 22 23 32 33, , , , , , , ,u u u l l u u l u einhält.

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

Es ist dabei darauf zu achten, dass zunächst beide Prozeduren durchlaufen werden bevor man zum nächsten j geht.

Eigenschaften Kosten der LU-Zerlegung:

3 3n Multiplikationen Vorteil der LU-Methode:

Problem in zwei Teile geteilt Lösungsschritte (1) und (2) direkt explizit eigentliches Problem wird unabhängig von rechter Seite b

Vorteile

bei vielen verschiedenen bn

Codeschnipsel 4 (LU- Dekomposition)

1 function [L, U] = slu(A) 2


3 % slu LU-Dekompensation einer quadratischen Matrix 4 % [L, U] = slu(A) führt den Crout’s-Algorithmus durch und gibt eine 5 % untere Dreiecksmatrix L sowie eine obere Dreiecksmatrix U mit L*U = A 6 % zurueck. Der Algorithmus stoppt, wenn der Eintrag einer Pivotstelle zu klein ist. 7 8 [n, n] = size(A); 9 10 for k = 1:n 11 if abs(A(k, k)) < sqrt(eps) 12 disp(['Kleine Pivotstelle in Zeile ' int2str(k) '.']) 13 end 14 L(k, k) = 1; 15 for i = k+1:n 16 L(i,k) = A(i, k) / A(k, k); 17 for j = k+1:n 18 A(i, j) = A(i, j) - L(i, k)*A(k, j); 19 end 20 end 21 for j = k:n 22 U(k, j) = A(k, j); 23 end 24 end

1.6.5 Iterative Verbesserung der Lösungsverfahren Wenn zu einem linearen Gleichungssystem eine numerische Lösung gefun-den wurde, ist diese durch Rundungsfehler fehlerbehaftet, die speziell bei großen Gleichungssystemen akkumulieren. Ziel der iterativen Verbesserung 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 abwei-chende Lösung x x

mit dem unbekannten Fehler x . Diese falsche Lö-sung x führt in der obigen Gleichung zu einer Abweichung der rechten Seite der Gleichung, also zu

Ax b oder A( )x x b b

.

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

A x b

und schließlich erhalten wir


A A ( ) Ax x x b x b

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

und dem Vek-tor b

ist nun bekannt. Dabei ist die Subtraktion vonb

mit doppelter Genauig-

keit auszuführen (Werte heben sich oft weg). Das obige System ist nun für den Fehler x zu lösen welche dann von der bekannten falschen Lö-sung x x

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

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

m

k 3x 4x

5x 2x 1x

Die Bewegungsgleichungen für die Massepunkte in relativen Koordinaten lau-ten

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 2

3 3

4 4

5 5

1 1 0 0 01 2 1 0 0

, M0 1 2 1 00 0 1 2 10 0 0 1 1

x xx xx x x xx xx 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 2

2 2M

ˆ ˆM E 0

x x

x

x

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

ˆ ˆdet M E ( ) 0P

(denn, dann hat die Gleichung ˆ ˆ 0M E x nicht verschwindende Lösun-

gen.)

Eigenschaften ( )P ist charakteristisches Polynom N -ten Grades mit N komplexen Null-

stellen 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ösungsme-

thoden für spezifizierte Problemklassen (symmetrisch, hermitesch, unitär, etc.), grobe Unterscheidung in: iterative Verfahren, z.B. Jacobi Methode direkte Verfahren, z.B. Housholder Methode QL Methode

Gegeben sei die Matrix

3 2 16 6 39 10 6

A

Aufgabe 5

Berechnen Sie mittels Gaus-Jordan-Verfahren die inverse Matrix 1A von Hand und kontrollieren Sie ihr Ergebnis mit MATLAB. 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 implemen-tieren.

1.7 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 mit-


tels trigonometrischer Funktionen, ist dabei eine gute Methode, um die Lö-sung einfacher zu ermitteln. Wir machen dabei den Ansatz:

i tf t e

.

Wir bezeichnen als Fourier-Koeffizienten und als Frequenz. Die Zeitab-leitung ist dann

i tn

df i edt

.

Diese Idee, eine zeitabhängige Funktion durch eine Summation über Fre-quenzen darzustellen, kann analog auf eine ortsabhängige Funktion übertra-gen werden. Dabei wird eine Funktion f(x) durch eine Summe über Harmoni-sche mit den sogenannten Ortsfrequenzen k dargestellt. So gelangt man von Differentialgleichungen im Zeitraum/Ortsraum zu algeb-raischen 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 Er-gebnis durch Rücktransformation wieder im Zeitraum darzustellen. Für beliebige Zeitverteilungen geht die Anzahl der Frequenzen jedoch gegen unendlich. Deswegen versucht man in der numerischen Berechnung mit peri-odischen Zeitverteilungen zu arbeiten. Da maximal eine endliche Reihenent-wicklung berücksichtigt werden kann, erscheinen auch nur diskrete Fre-quenzspektren.

Eine Funktion die physikalische Bedeutung hat, fällt in der Regel im Unendli-chen auf Null ab. Wie man einer realen Physik stets eine Periode geben kann

zeigt diese Abbildung.


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

cher die Recheckfunktion.

1.7.1 Die diskrete Fourier-Transformation Für die diskrete Fourier-Transformation seien die Raumpunkte N Stützstellen

0, ,2 , ,x a a L a

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

xyy

f x f y ( xy - Kronecker-Symbol, alle Summen über LNa

Elemente)schreiben. Dabei gilt die Identität

ik x yxy

k

a eL

.

Mit zugehörigen diskreten Ortsfrequenzen

2 2 20,1 ,2 , , 1LL L a Lk mit L 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

und damit eine diskrete Fourier-Transformation (FT)

ikx

x

f 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 All-gemeinen 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 periodischen Randbedin-gungen ( ) ( )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 Multiplikatio-nen. Ziel der nachfolgenden Betrachtungen ist es, diese Anzahl zu verrin-gern. 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

1.7.2 Fast-Fourier-Transformation Mit diesem Verfahren werden wir den Rechenaufwand für die eindimensiona-le 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 Wf k

mit der Bezeichnung e (even) für die geradzahligen und o (odd) für die unge-radzahligen Stützstellen. W ist dabei eine komplexe Konstante. Dieses Ver-fahren 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 ei-

ner 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 2N .

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

1.7.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 wir 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 ge-spiegelt (Lösung bei begrenzter Samplingrate: vorher analoger Tiefpassfilter). Beispiel: Siehe bzw. höre 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’


2. Lösung gewöhnlicher Differentialgleichungen Da sich einfache physikalische Systeme bereits durch gewöhnliche Differen-tialgleichungen sehr gut beschreiben lassen, werden wir uns in diesem Kapi-tel mit dem Lösen derselben beschäftigen. Die allgemeine explizite gewöhnli-che Differentialgleichung hat folgende Struktur

1, ',..., ,n

nn

d f tG f f f t

dt

Für die Lösungsmethodik ist es von Bedeutung, ob Anfangsbedingungen o-der Randbedingungen vorgegeben sind. Hier sollen nun zuerst Methoden für Anfangswerte und dann für Randwerte vorgestellt werden.

2.1 Anfangswertaufgabe (AWA) Es seien die Anfangswerte

10 , ' 0 ,..., 0nf t f t f t

Gegeben. Dann ist dies äquivalent zu einem gekoppelten Differentialglei-chungssystem 1. Ordnung aus n Gleichungen

11 1 2

22 1 2

33 1 2

1 2

( ) , ,..., ,

( ) , ,..., ,

( ) , ,..., ,

( ) , ,..., ,

n

n

n

nn n

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 Ord-nung sein

2

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

welche als ein System von Differentialgleichungen erster Ordnung geschrie-ben werden kann

( )

( ) ( ) ( )

dy z tdtdz r t q t z tdt

mit den bekannten Anfangswerten 0 , 0 ( 0)f t f t z t .


Beispiel Ein einfaches Anwendungsbeispiel für eine AWA stellt der radioaktive Zerfall, die lineare Bewegung mit Newtonscher Reibung bzw. die Entladung eines Kondensators dar. Alle Vorgänge werden durch die Gleichung

( )df t f tdt

mit entsprechenden Anfangswerten beschrieben.

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)

mit :n nf t f f f n t

2.1.1 Einschrittverfahren

2.1.1.1 Vorwärts-Euler-Verfahren Dieses einfache Verfahren nähert die Zeitableitung durch den diskreten rechtsseitigen Ableitungsoperator. Damit wird aus

,f t G f t t

die Differenzenformel

'( ) ,t

f t t f tf t D f t G f t t

t

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

und die Rekursionsformel bei gegebenen Anfangswerten ist

1 ,n n nf f t G f t

Fehleranalyse Da wir den rechtsseitigen Differentialoperator verwendet haben, geht der lo-kale Fehler mit 2t gegen null. Um eine globale Fehleraussage treffen zu können, müssen die gesamten lo-kalen Fehler addiert werden.


Ableitung einer globalen Fehlergrenze Sei

n n ne f t f

der globale Fehler nach n Schritten. Es sind nf t der exakte analytische Wert und nf der durch das Vorwärts-Euler-Verfahren bestimmte Wert. Eine Taylorentwicklung der exakten analytischen Lösung ergibt

2

1 12, ''tn n n n n n n nf t f t t G f t t f t t t 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, '' ( )hn n n n n n n n nte e t G f t e f t f 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

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 21

1 2 21 1 1 = 1 1n nh hne 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 1nne C hM resultiert:

02 21 1nt t MnhMhk hk

n M Me e e

globaler Fehler von Euler ist O h 1. Ordnung Demnach ist der globale Fehler von 1. Ordnung in t . Wenn Rundungsfehler einbezogen werden ist Fehlerentwicklung komplizier-ter:

h

Fehler

Diskretisierungsfehler Rundungsfehler

Gesamt

Documents

CP1 Skript 2009 04 19b Vorlesung 2009 07 06 Studentenskript · 2012-01-12 · Die Abhängigkeit der Konvergenz von h betrachten wir anhand des rechtssei-tigen Differentialoperators,