Numerical Recipes in C++. The Art of Scientific Computing Der Einstieg in die Programmierung besteht bei den meisten in der Erstellung kleiner Tools oder Spiele. Vor allem im wissenschaftlichen Bereich kriegen viele es dann aber oft früher oder später mit harter Numerik zu tun, wenn zum Beispiel eine Funktion integriert oder in einem gegebenen Parameterraum maximiert oder ein Gleichungssystem gelöst werden soll. Als eine Art "Bibel" haben sich hier die "Numerical Recipes" herauskristallisiert, die es für verschiedene Programmiersprachen gibt und hier als "Numerical Recipes in C++" (von Press, Teukolsky, Vetterling und Flannery) besprochen werden soll. Die Autoren versuchen mit ihrem Buch einen mehr oder weniger kompletten Überblick über die gebräuchlisten Methoden der Numerik zu geben. Auf drei Kapitel soll hier näher eingegangen werden. Ein für viele Programme wichtiger Bestandteil ist der Zufallszahlengenerator, der zuverlässig Zahlen liefern sollte, die eine gegebene Zufallsverteilung so gut wie möglich erfüllen. Folglich ist gleich eines der ersten Kapitel mit dem Titel "Random numbers" überschrieben. Nach einer kurzen Einführung über die Theorie von Zufallszahlengeneratoren auf voll deterministischen System, wie es Computer nun einmal sind, werden gleich ein paar verschiedene Methoden aufgezeigt und deren Effizienz verglichen. Diese elementaren Generatoren lieferen allerding nur gleichmäßig verteilte Zahlen in einem gegebenen Bereich, für viele Fälle sind aber eher solche mit einer exponentiellen oder normalen Verteilung nötig. Diese werden also im Anschluß besprochen, gefolgt von Methoden, Zufallszahlen einer beliebigen Verteilung zu erzeugen. Für jeden Generator ist natürlich auch ein Quellcode angegeben, der sich sofort abtippen und benutzen läßt. Kapitel 10 trägt den Titel "Minimization and Maximization of Functions", hier wird also allgemein auf die Optimierung von Funktionen eingegangen. Beginnend mit der einfacheren Suche in einer Dimension wird zunächst der "Goldene Schnitt" beschrieben, gefolgt von einem Algorithmus, der zur Optimierung auch noch die erste Ableitung der Funktion auswertet. Anschließend geht es an das ungleich schwerere Problem der Optimierung in N Dimensionen. Es gilt also, den N-elementigen Vektor zu finden, der eine gegebene Funktion minimiert oder maximiert. Hier werden verschiedene Methoden vorgestellt, die für jeweils verschiedene zu optimierende Funktionen eher geeignet sind, eins wird nämlich schnell klar: den besten Optimierungs-Algorithmus gibt es nicht. Als bekanntes Beispiel wird zum Schluß noch auf eine Lösung des "Traveling Salesman"-Problems eingegangen. Die Benutzung von genetischen Algorithmen zur Optimierung wird leider nicht besprochen, dies würde allerdings wohl auch den Rahmen des Buches sprengen. In Kapitel 14 geht es mit "Statistical Description of Data" um einen Bereich, den auch Programmierer interessieren dürften, die jenseits der harten Numerik arbeiten. Zunächst geht es quasi um Schulstoff: Was sind Mittelwert und Standardabweichung? Dann wird der wichtigen Frage nachgegangen, wie ähnlich sich zwei Verteilungen sind, ob es sich bei zwei Datensätzen im Grunde also um das gleiche Signal handelt. Hier wird zum Beispiel der bekannte Chi-Square-Test besprochen, bei dem einfach die Quadrate der Differenzen zwischen den Punkten zweier Datensätze addiert werden und das Ergebnis als Maß für deren Ähnlichkeit betrachtet wird. Damit verwandt ist das Problem der Korrelation, auf das im Rest des Kapitels eingegangen wird. Auch eine Erweiterung auf zwei Dimensionen wird besprochen. In den restlichen Kapiteln geht es um die Lösung von Gleichungssystemen (Kap. 2), Inter- und Extrapolation (Kap. 3), Integration (Kap. 4) und Auswertung (Kap. 5) von Funktionen und spezielle Funktionen wie z.B. die Bessel-Funktionen (Kap. 6). Nach dieser geballten Ladung Mathe kommen die schon erwähnten Zufallszahlen, gefolgt von einem Kapitel übers Sortieren (Kap. 8). Bevor es dann an die Optimierung geht, geht es in Kap. 9 um das verwandte Thema der Nullstellensuche. Ein letzter Ausflug in die Algebra macht Kap. 11 mit den Eigensystemen. Die Kap. 12 und 13 beschäftigen sich dann mit der Fourier-Transformation und deren Anwendungen, gefolgt von einem Abschnitt über die Modellierung von Daten (Kap. 15). In den Kapiteln 16 bis 19 geht es dann schließlich um Differential- und Integralgleichungen. Jedes Kapitel in dem 1032-seitigen Buch ist im Grunde zweigeteilt in eine mathematische Herleitung und die numerische Umsetzung. Erstere sind teilweise durchaus fordernd, ein Studium der Mathematik ist allerdings keine Voraussetzung, im Grunde kann man die vorgestellten Algorithmen ja auch als Black Boxes ansehen und einfach nur benutzen ohne sie verstanden zu haben. Der "normale" Leser dieses Buches dürfte allerdings einen wissenschaftlichen Hintergrund haben, für dieses Klientel ist der Anspruch dann durchaus im Rahmen des Üblichen. Der Quellcode ist ausreichend gut kommentiert, liegt allerdings nicht auf CD dabei, sondern kann auf der Homepage www.nr.com seperat für $65 erworben werden, was bei dem Preis des Buches durchaus als unverschämt angesehen werden kann. Das Buch selber (zumindest die Versionen für C und Fortran) sind auf ebendieser Homepage aber auch kostenlos als PDF herunterladbar. Die "Numerical Recipes in C++" sind also durchaus zu empfehlen und für jeden, der sich mit Numerik auseinandersetzen muß, ist es quasi Pflicht, dieses Buch im Regal stehen zu haben. Es bietet einen gelungenen Überblick über die anspruchsvolle Thematik der Numerik und die abgedruckten Sources lassen sich direkt abtippen und nutzen. Warum also jedesmal das Rad neu erfinden?

Der Einstieg in die Programmierung besteht bei den meisten in der Erstellung kleiner Tools oder Spiele. Vor allem im wissenschaftlichen Bereich kriegen viele es dann aber oft früher oder später mit harter Numerik zu tun, wenn zum Beispiel eine Funktion integriert oder in einem gegebenen Parameterraum maximiert oder ein Gleichungssystem gelöst werden soll. Als eine Art "Bibel" haben sich hier die "Numerical Recipes" herauskristallisiert, die es für verschiedene Programmiersprachen gibt und hier als "Numerical Recipes in C++" (von Press, Teukolsky, Vetterling und Flannery) besprochen werden soll.

Die Autoren versuchen mit ihrem Buch einen mehr oder weniger kompletten Überblick über die gebräuchlisten Methoden der Numerik zu geben. Auf drei Kapitel soll hier näher eingegangen werden.

Ein für viele Programme wichtiger Bestandteil ist der Zufallszahlengenerator, der zuverlässig Zahlen liefern sollte, die eine gegebene Zufallsverteilung so gut wie möglich erfüllen. Folglich ist gleich eines der ersten Kapitel mit dem Titel "Random numbers" überschrieben. Nach einer kurzen Einführung über die Theorie von Zufallszahlengeneratoren auf voll deterministischen System, wie es Computer nun einmal sind, werden gleich ein paar verschiedene Methoden aufgezeigt und deren Effizienz verglichen. Diese elementaren Generatoren lieferen allerding nur gleichmäßig verteilte Zahlen in einem gegebenen Bereich, für viele Fälle sind aber eher solche mit einer exponentiellen oder normalen Verteilung nötig. Diese werden also im Anschluß besprochen, gefolgt von Methoden, Zufallszahlen einer beliebigen Verteilung zu erzeugen. Für jeden Generator ist natürlich auch ein Quellcode angegeben, der sich sofort abtippen und benutzen läßt.

Kapitel 10 trägt den Titel "Minimization and Maximization of Functions", hier wird also allgemein auf die Optimierung von Funktionen eingegangen. Beginnend mit der einfacheren Suche in einer Dimension wird zunächst der "Goldene Schnitt" beschrieben, gefolgt von einem Algorithmus, der zur Optimierung auch noch die erste Ableitung der Funktion auswertet. Anschließend geht es an das ungleich schwerere Problem der Optimierung in N Dimensionen. Es gilt also, den N-elementigen Vektor zu finden, der eine gegebene Funktion minimiert oder maximiert. Hier werden verschiedene Methoden vorgestellt, die für jeweils verschiedene zu optimierende Funktionen eher geeignet sind, eins wird nämlich schnell klar: den besten Optimierungs-Algorithmus gibt es nicht. Als bekanntes Beispiel wird zum Schluß noch auf eine Lösung des "Traveling Salesman"-Problems eingegangen. Die Benutzung von genetischen Algorithmen zur Optimierung wird leider nicht besprochen, dies würde allerdings wohl auch den Rahmen des Buches sprengen.

In Kapitel 14 geht es mit "Statistical Description of Data" um einen Bereich, den auch Programmierer interessieren dürften, die jenseits der harten Numerik arbeiten. Zunächst geht es quasi um Schulstoff: Was sind Mittelwert und Standardabweichung? Dann wird der wichtigen Frage nachgegangen, wie ähnlich sich zwei Verteilungen sind, ob es sich bei zwei Datensätzen im Grunde also um das gleiche Signal handelt. Hier wird zum Beispiel der bekannte Chi-Square-Test besprochen, bei dem einfach die Quadrate der Differenzen zwischen den Punkten zweier Datensätze addiert werden und das Ergebnis als Maß für deren Ähnlichkeit betrachtet wird. Damit verwandt ist das Problem der Korrelation, auf das im Rest des Kapitels eingegangen wird. Auch eine Erweiterung auf zwei Dimensionen wird besprochen.

In den restlichen Kapiteln geht es um die Lösung von Gleichungssystemen (Kap. 2), Inter- und Extrapolation (Kap. 3), Integration (Kap. 4) und Auswertung (Kap. 5) von Funktionen und spezielle Funktionen wie z.B. die Bessel-Funktionen (Kap. 6). Nach dieser geballten Ladung Mathe kommen die schon erwähnten Zufallszahlen, gefolgt von einem Kapitel übers Sortieren (Kap. 8). Bevor es dann an die Optimierung geht, geht es in Kap. 9 um das verwandte Thema der Nullstellensuche. Ein letzter Ausflug in die Algebra macht Kap. 11 mit den Eigensystemen. Die Kap. 12 und 13 beschäftigen sich dann mit der Fourier-Transformation und deren Anwendungen, gefolgt von einem Abschnitt über die Modellierung von Daten (Kap. 15). In den Kapiteln 16 bis 19 geht es dann schließlich um Differential- und Integralgleichungen.

Jedes Kapitel in dem 1032-seitigen Buch ist im Grunde zweigeteilt in eine mathematische Herleitung und die numerische Umsetzung. Erstere sind teilweise durchaus fordernd, ein Studium der Mathematik ist allerdings keine Voraussetzung, im Grunde kann man die vorgestellten Algorithmen ja auch als Black Boxes ansehen und einfach nur benutzen ohne sie verstanden zu haben. Der "normale" Leser dieses Buches dürfte allerdings einen wissenschaftlichen Hintergrund haben, für dieses Klientel ist der Anspruch dann durchaus im Rahmen des Üblichen. Der Quellcode ist ausreichend gut kommentiert, liegt allerdings nicht auf CD dabei, sondern kann auf der Homepage www.nr.com seperat für $65 erworben werden, was bei dem Preis des Buches durchaus als unverschämt angesehen werden kann. Das Buch selber (zumindest die Versionen für C und Fortran) sind auf ebendieser Homepage aber auch kostenlos als PDF herunterladbar.

Die "Numerical Recipes in C++" sind also durchaus zu empfehlen und für jeden, der sich mit Numerik auseinandersetzen muß, ist es quasi Pflicht, dieses Buch im Regal stehen zu haben. Es bietet einen gelungenen Überblick über die anspruchsvolle Thematik der Numerik und die abgedruckten Sources lassen sich direkt abtippen und nutzen. Warum also jedesmal das Rad neu erfinden?

geschrieben am 11.03.2006 | 804 Wörter | 4876 Zeichen