Numerische Methoden und Algorithmen in der Physik · Brent’s Methode... Numerische Methoden und Algorithmen in der Physik Christian Autermann 31/ 42. Einführung Ausnahmebehandlung

Einführung Ausnahmebehandlung Nullpunktbestimmung Extremwertbestimmung

Numerische Methoden und Algorithmen in derPhysik

Hartmut Stadie, Christian Autermann

20.11.2008

Numerische Methoden und Algorithmen in der Physik Christian Autermann 1/ 42


Achtung:

Nächste Woche am 27.11.2008 fällt die Vorlesung und dieÜbung aus!



Einführung

Ausnahmebehandlung

Nullpunktbestimmung

Extremwertbestimmung



Übersicht

EinführungLiteraturlisteMinimierungAusnahmebehandlung

Ausnahmebehandlung

Nullpunktbestimmung




Informationen

Material:Stroustrup: The C++ Programming Language, 3rd editionhttp://www.mathematik.uni-marburg.de/∼cpp/B. Stroustrup: C++ In-depth SeriesA. Koenig, B. E. Moo: Accelerated C++Press et al: Numerical Recipes, 3rd editionT. H. Cormen et al: Introductions to Algorithms, 2nd editionhttp://wwwiexp.desy.de/studium/lehre/numalg/



Minimierung

Analyse von FunktionenNullpunktbestimmung (root finding)Extremwertbestimmung: Lokale und Globale Minima undMaxima



Minimierung

Analyse von Funktionen in der PhysikViele Probleme in der Physik erfordern die Analyse vonFunktionenOft hat man eine Menge von Messungen, mit deren Hilfe einezu Grunde liegende Theorie untersucht werden soll.Die unbekannten Parameter dieser Theorie werden variiertund eine Wahrscheinlichkeit der Übereinstimmung mit derTheorie konstruiert (→ Fitting, Thema einer der nächstenVorlesungen)In dieser (möglicherweise mehrdimensionalen)Wahrscheinlichkeitsverteilung muss das globale Extremumbestimmt werden.

Beispiel: Higgs-Suche. Die Higgs-Masse ist unbekannt,Untersuchung von z.B. H → ZZ → µµµµ Spektrum.



Ausnahmebehandlung

Behandlung von Ausnahmebedingungen in C++Es kann vorkommen, dass eine C++ Routine nicht den Zweckerfüllen kann für den sie entwickelt wurde.Dies geschieht in der Regel dann, wenn nicht alle Fälle, z.B.sehr unwahrscheinliche, bei der Entwicklung berücksichtigtwurden.Beispiele:

vector<int> A mit 5 Elementen gefüllt; versuche Zugriff aufA.at(10);Division durch 0, Wurzel aus einer negativen Zahl, etc.Nullpunktbestimmung bei einer Funktion ohne Nullpunkt.Konvertierung einer zu grossen long int Zahl in eine short intZahl...



Ausnahmebehandlung

Behandlung von Ausnahmebedingungen in C++In diesen Fällen lässt sich in diesen Routinen einAusnahme-Signal erzeugen, man “wirft ein Ausnahmesignal”(throws an exception).Dies dient in erster Linie dazu, dem Programmierer der dieseRoutinen benutzt zu signalisieren, dass die Routinen fürunsinnige Fälle (Funktionsargumente) benutzt werden.Ausnahmesignale sollten keinesfalls für normaleFallunterscheidungen (etwa wie if) benutzt werden, sondernausschliesslich für Ausnahmen reserviert sein!Ausnahmen sind Fälle wenn der eigentliche Zweck derFunktion nicht erfüllt werden kann.



Übersicht

Einführung

Ausnahmebehandlungtry, throw, catchExceptions der C++ Standard BibiothekenKonvertierung long (32bit) → short(16bit)Beispiel und Gegenbeispiel

Nullpunktbestimmung




Ausnahmebehandlung

try, throw, catch#include <iostream> //exceptionsusing namespace std;

int main () {try{

throw 20;}catch (int e){

cout << "An exception occurred. "<< "Exception Nr. " << e << endl;

}return 0;

}



Ausnahmebehandlung

try, throw, catchExceptions können verschiedene Typen (int, char, usw.) haben.catch(type param) fängt nur exceptions von Typ type.“catch(...)” fängt alle exceptions:

try {// code here

}catch (int param) { cout << "int exception"; }catch (char param) { cout << "char exception"; }catch (...) { cout << "default exception"; }

Mehrere catch Blöcke sind erlaubt. Nach einem “throw” wird derCode am nächsten passenden catch() fortgesetzt.Existiert kein passender catch() Block, stürzt das Programm ab!



Ausnahmebehandlung

Exceptions der C++ Standard Bibiotheken:

exception descriptionbad_alloc thrown by new on allocation failurebad_cast thrown by dynamic_cast when fails with a referenced typebad_exception thrown when an exception type doesn’t match any catchbad_typeid thrown by typeidios_base::failure thrown by functions in the iostream library

try {int * myarray= new int[1000];

}catch (bad_alloc&) { //bad_alloc special case of exception

cout << "Error allocating memory." << endl;}catch (exception& e) {

cout << "Standard exception: " << e.what() << endl;}



Ausnahmebehandlung

Exception können helfen Fehler zu vermeiden und Bugsaufzuspüren:

Konvertierung long (32bit) → short(16bit)short Convert32to16(long number){

if (a>= pow(2, 8*sizeof(short)-1) )throw ( EXCEPTION_SHORT_OVERFLOW );

return (short)number;}

Manchmal erreicht man aber genau das Gegenteil undverschlimmert alles...



Ausnahmebehandlung

Ariane 5Einer der berühmtesten Bugs der ComputergeschichteOverflow bei der Konversion einer 32bit in eine 16bit ZahlException wurde nicht behandelt∼500 Millionen Dollar Schaden



Übersicht

Einführung

Ausnahmebehandlung

NullpunktbestimmungKriterienBracketingBisektionNewton MethodeAndere Methoden




Nullpunktbestimmung

KriterienEine Funktion f (x) hat (mindestens) einen Nullpunkt imIntervall [a, b], falls f (a) · f (b) < 0.Eine Funktion kann 2 · n, mit n ∈ N, Nullstellen im Intervall[a, b] besitzen falls f (a) · f (b) > 0.Obwohl eine Funktion einen Nullpunkt besitzt, muss kein xexistieren, für das f (x) = 0 gilt, wegen der endlichen Präzisionder Darstellung von Zahlen im Computer.Ein geeignetes Konvergenzkriterium, das die Präzision derDarstellung berücksichtigt, kann viele unnötige Rechenschrittesparen

Ziel: Möglichst kostengünstige Nullpunktsbestimmung (wenigSchritte, wenig Speichernutzung)



Nullpunktbestimmung

Fig. (1) Fig. (2)

Fig. (3) Fig. (4)



Nullpunktbestimmung

Definition: Klammerung (Bracketing)

Die Nullstelle einer Funktion f (x) ist geklammert(bracketed) durch [a, b], wenn sie im Intervall a..b mind. eineNullstelle besitzt.Das Kriterium f (a) · f (b) < 0 ist hinreichend.Falls f (a) · f (b) > 0 muss sich durch Veränderung derIntervallgrenzen a und/oder b ein Vorzeichenwechselerzwingen lassen, falls f (x) eine Nullstelle besitzt und dieSchrittweite klein genug ist.

Im folgenden wird davon ausgegangen, dass mind. eine Nullstelleder Funktion f (x) durch a und b geklammert ist.



Nullpunktbestimmung durch Bisektion

Pseudocode: BisektionBisektion( Funktion f im Intervall [a, b] )

Wenn f(a) * f(b) > 0throw () //Bedingung "Klammerung" ist nicht erfuellt!

Solange i < Maximal_Schrittzahldx = b - ax_mitte = a + 0.5*dxF_mitte = f( x_mitte )Wenn f(a)*F_mitte<0 dann b = x_mitteWenn f(b)*F_mitte<0 dann a = x_mitteWenn dx<Praezision dann

return F_mitte

Die Bisektion kreist die Nullstelle ein, indem das Suchintervall jeweils halbiertwird. Bei einer gewünschten Präzision ε ist die nötige Schrittzahl gegebendurch:

n = log2b − a

ε(1)



Bisektion

Schritt 1



Bisektion

Schritt 2



Bisektion

Schritt 3



Bisektion

Schritt 4



Bisektion

Schritt 5



Newton-Raphson VerfahrenSei f (x) eine steig differenzierbare Funktion:

1 Taylor-Entwicklung von f (x) um die erwartete Nullstelle xn:

f (x) = f (xn) +∂f∂x

˛̨̨̨xn

· (x − xn) +12

∂2f∂x2

˛̨̨̨xn

· (x − xn)2 (2)

2 Vernachlässigung des quadratischen Restgliedes

f (x) ≈ f (xn) + f ′(xn) · (x − xn) (3)

3 Mit f (x) = 0 (Nullstelle) lässt sich x berechnen:

x = xn+1 = xn −f (xn)

f ′(xn)(4)

4 Für das neue xn+1 wird wieder f (xn+1) und f ′(xn+1) bestimmt und eineneue Approximation für die Nullstelle iteriert.



Newton-Raphson

Schritt 1



Newton-Raphson

Schritt 2



Newton-Raphson

Schritt 3



Newton-Raphson

Schritt 4



Nullpunktbestimmung

Der Erfolg der Bisektionsmethode ist garantiert, jedoch ist dasKonvergenzverhalten nur linear, d.h. kleiner als 1 mal derUnsicherheit des letzten Schrittes ε zur ersten Potenz.

Andere MethodenSekantenverfahrenRegula FalsiRidder’s MethodeBrent’s Methode...



Nullpunktbestimmung - Sekantenmethode

Sekanten werden durch die zwei jeweils zuletzt berechneten Punktegezogen. Diese Punkte müssen die Nullstelle nicht klammern. Dernächste Punkt ist der Schnittpunkt der Sekante mit der x-Achse.Konvergenz ist nicht garantiert.



Nullpunktbestimmung - Regula Falsi

Sekanten werden durch die zwei jeweils zuletzt berechneten Punktegezogen, welche die Nullstelle klammern. Der nächste Punkt istder Schnittpunkt der Sekante mit der x-Achse.



Nullpunktbestimmung

Vergleich Sekantenverfahren und Regula FalsiDer einzige Unterschied in der Methode besteht darin, dassdie Nullstelle bei Regula Falsi geklammert bleibt.Das Sekantenverfahren konvergiert am schnellsten, man kannzeigen das sich für kontinuierliche Funktion ein super-linearesVerhalten erzielen lässt:

εn+1 ≈ ε1.618n (5)

Bei unstetigen Funktionen kann das SekantenverfahrendivergierenBei Regula Falsi bleibt die Nullstelle geklammert und dasKonvergenz Verhalten ist oft super-linear aber geringer als beider Sekantenmethode. Die exakte Bestimmung ist jedochschwierig.



Übersicht

Einführung

Ausnahmebehandlung

Nullpunktbestimmung

ExtremwertbestimmungÜberblickBisektionsartige Methode




Bestimmung von Minima und MaximaDie Bestimmung von Minima oder Maxima ist equivalent zuder Suche nach Nullstellen in der Ableitung.Aber:

Die Ableitungsfunktion ist in der Regel nicht bekanntUnterscheidung zwischen Minima und Maxima unterschiedenEs muss zwischen lokalen und globalen Extremwertenunterschieden werden

Analog zur Nullstellenbestimmung ist mind. ein Extremwertgeklammert, wenn f (b) < f (a) und f (b) < f (c) für die dreiWerte a < b < c gilt(oder f (b) > f (a) und f (b) > f (c)).

Im folgenden werden Minima gesucht und es wird vorausgesetzt,dass ein Minimum der Funktion f (x) geklammert ist.



Extremwertbestimmung analog zur BisektionEs sind die Funktionswerte an den Stellen a, b und c gegeben.

Bestimme einen neuen Funktionswert an Stelle x , entwederzwischen a und b (oder zwischen b und c)Wähle o.B.d.A. den ersteren Fall a < x < b:

f (b) < f (x): Die drei neuen Stellen sind a < b < x .f (b) > f (x): Die drei neuen Stellen sind b < x < c.

Wie soll x gewählt werden, um die Gesamtzahl der Schritte zuminimieren?



Extremwertbestimmung analog zur BisektionFür die Strecke a < b < c gilt für das Verhältnis der Abschnitte:

b − ac − a

= w undc − bc − a

= 1− w (6)

Die Entfernung das nächsten Punktes in bezug auf den Punkt b sei z :

x − bc − a

= z (7)

Die Länge des nächsten geklammerten Segmentes ist also entweder w + z oder1− w . →Bestimme z so, dass kein Segment benachteiligt ist, alsow + z = 1− w und damit:

z = 1− 2w (8)

Es ist ein iterativer Algorithmus, d.h. w wurde auf die gleiche Weise optimiertgewählt wie z! Der Punkt x trennt die Strecke b − c also im gleichenVerhältnis, wie der Punkt b die Strecke a− c. Es folgt:

z1− w

= w (9)



Extremwertbestimmung analog zur BisektionMit den Formeln (8) und (9) also

z = 2− w undz

1− w= w (10)

folgt somit für die Wahl eines Intervalls w , welches die Gesamtzahl der nötigenSchritte im worst-case Szenario optimiert:

1 + w 2 − 3w = 0 und damit w =3−

√5

2= 0.38197 (11)

In einem idealen, geklammerten Intervall (a,b,c) ist der Punkt b also 0.38197von einem und 0.61803 vom anderen Ende relativ zur Gesamtstrecke entfernt.Woher kennt man dieses Verhältnis?



Der Goldene Schnitt

Rathaus Leibzig, erbaut 1556-57 von Hieronymus Lotter. Der goldene Schnittwurde von dem gotischen Vorgängerbau übernommen.

0.38197 0.61803

Der Goldene Schnitt ist seit der Zeit der alten Griechen in der Architektur undder Kunst bekannt.



Geeignete AbbruchbedingungUm die Goldenen Schnitt Methode als Algorithmus implementieren zu könnenfehlt noch eine geeignete Abbruchbedingung.

Die naive Annahme: Sobald die Differenz des Minimums von einemSchritt auf den nächsten xn+1 − xn von der Größenordnung der Präzision εvon x ist, dann Abbruch.Für eine beliebige (stetig differenzierbare) Funktion gilt in der Nähe desExtremums (Taylor Entwicklung):

f (x) = f (b) +12

f ′′(b) · (x − b)2 (12)

Daraus folgt mit einer maximal möglichen Genauigkeit vonf (x)− f (b) < ε:

|x − b| <√

ε · |b|

s2|f (b)|b2f ′′(b)

(13)

Der letzte Term ist für viele Funktionen von der Grössenordnung O(1), sodass als Daumenregel gilt:

Abbruchbedingung: xn+1 − xn ≤√

ε · xn+1.



Achtung:

Nächste Woche am 27.11.2008 fällt die Vorlesung und dieÜbung aus!


Documents

Numerische Methoden und Algorithmen in der Physik · Brent’s Methode... Numerische Methoden und Algorithmen in der Physik Christian Autermann 31/ 42. Einführung Ausnahmebehandlung