Symbolic Integration I
Manuel Bronstein
Springer-Verlag, Berlin-Heidelberg-New York,1997, DM 78,00; öS 569,40; sFr 69,00
2nd edition: Springer-Verlag, Berlin-Heidelberg-New York, 2005, 53,45 Euro
ISBN 3-540-60521-5
ISBN 3-540-21493-3
Es folgen die Rezensionen von: 1. Auflage und 2. Auflage
Rezension zur 1. Auflage
Seit dem letzten Buch Integration in Finite Terms zu dieser Thematik im Jahre 1948 von J.F. RITT sind fast fünfzig Jahren vergangen, und in dieser Zeit wurde die symbolischen Integration in entscheidender Weise weiterentwickelt. Einen wichtigen Einfluß für das Aufblühen dieser Theorie hat die Computeralgebra, deren Anforderungen ein Anknüpfen an die algorithmischen Traditionen der Mathematik des letzten Jahrhundert nach sich zog. Das zu lösende Problem kann aus dieser Sicht so formuliert werden: Man finde algorithmisch zu jeder vorgegebenen elementaren Funktionen eine elementare Stammfunktion oder beweise (algorithmisch), daß es keine solche geben kann.
In der ersten Auflage 1905 seines Buches The Integration of Functions of a Single Variable vermutete G.H. HARDY auf Seite 7, daß das Problem für die elementaren Funktionen nie gelöst werden würde: Complete answers to these questions have not and probably never will be given.
Interessanterweise hat der Autor diese Passage in der 2. Auflage 1916 auf Seite 8 dann durch folgenden Satz ersetzt: It would be unreasonable to expect complete answers to these questions.
Im Jahre 1969 ist dann von R.H. RISCH ein Entscheidungsverfahren angegeben worden. Viele weitere Arbeiten im Anschluß an R.H. RISCH waren allerdings nötig, um Implementierungen für gewisse Teilklassen von Funktionen in den verschiedenen Computeralgebra-Systemen zu ermöglichen. Neben den Arbeiten von B. TRAGER, ROTHSTEIN und anderen ist hier besonders der Autor des vorliegenden Buches zu nennen.
In diesem Buch - der erste Band der neu bei Springer aufgelegten Reihe zum Thema Algorithms and Computations in Mathematics wird nun die bis zum heutigen Tag entwickelte algorithmische Theorie zur symbolischen Integration transzendenter Funktionen vollständig als mathematisches Lehrbuch vorgelegt. Alle Abschnitte enthalten neben der Theorie die jeweiligen Algorithmen in Pseudocode, die von jedem (Weiter-)-Entwickler eines Computeralgebra-Systems nahezu direkt in lauffähige Implementierungen umgesetzt werden können.
Nach einer kurzen Erinnerung an die benötigten Basisalgorithmen der Computeralgebra wie Euklidischer Algorithmus, Resultanten und quadratfreie Faktorisierung von Polynomem im ersten Kapitel wird zunächst die algorithmische Theorie der Integration rationaler Funktionen im Detail und mit den verschiedenen Varianten diskutiert - von Bernoulli, Hermite, Horowitz-Ostrogradsky, Rothstein-Trager, Lazard-Rioboo-Trager bis zu den neuesten Ideen von Czichowski, der Gröbnerbasis-Techniken in diese Theorie einbringt. Diese Ausführlichkeit ist deshalb notwendig, da die Ideen der Theorie für die rationalen Funktionen auf die Klassen transzendente Funktionen hochgezogen werden müssen.
Dazu wird im Kapitel 3 eine Einführung in die Theorie der Differentialkörper gegeben um transzendente Erweiterungen k(x)(t) des rationalen Funktionenkörpers k(x) als Einführung etwa der Tangensfunktion t := tan(x) allein durch ihr Ableitungsgesetz Dt = t2 + 1 deuten zu können. Diese Algebraisierung ist der entscheidende Schlüssel zur Lösung dieses Problems aus der Analysis und bestätigt nebenbei die Namensgebung des Gebietes Computeralgebra.
Im Kapitel 4 werden die notwendigen Hilfsmittel aus der Bewertungstheorie zur Verfügung gestellt und damit die Eigenschaften der wichtigen Rothstein-Trager-Resultanten hergeleitet.
Das Kernstück des Buches ist das Kapitel 5 zur Integration transzendenter Funktionen. Es enthält mit dem Beweis des Satzes von Liouville, der entscheidenden Strukturaussage für die Form eines elementaren Integrals. Die verschiedenen Reduktiontechniken werden zunächst in Abschnitt 5.2 überblicksartig erläutert und in Figur 5.1 schematisch dargestellt und im Anschluß daran ausgearbeitet. Je nach Ableitungsgesetz - primitiver Fall mit Dt im Grundkörper (Beispiel t :=log(x)), hyperexponentieller Fall mit Dt ein Polynom vom Grad 1 (Beispiel t :=exp(x)) bzw. der hypertangentielle Fall mit Dt ein Polynom vom Grad 2 (Beispiel t :=tan(x)) - verzweigt der Algorithmus und es sind jeweils auf die gegebenen Situation angepaßte Subalgorithmen erforderlich, die mit eingeschränkter Integration, dem Lösen der Differentialgleichung von RISCH bzw. dem Lösen eines gekoppelten Systems zweier Differentialgleichungen in den drei Fällen das Problem entweder durch Elimination von t rekursiv auf eine einfachere Situation zurückführen oder an dieser Stelle die Nicht-Existenz eines elementaren Integrals zeigen.
Das Kapitel 6 ist den algorithmischen Details zur Lösung der Risch-Differentialgleichung gewidmet, im Kapitel 7 werden die verschiedenen parametrischen Probleme gelöst und das Kapitel 8 ist schließlich der Lösung der auftretenden gekoppelten Differentialgleichungen gewidmet.
Im abschließenden Kapitel werden Strukturaussagen bewiesen, die nötig sind um zu entscheiden, ob beim Aufbau der Funktionskörper durch sukzessives Adjungieren von Logarithmen oder Exponentialfunktionen neue Konstanten entstehen.
Das Buch ist durch Übungsaufgaben und den angegeben Algorithmen gut geeignet, um als Grundlage für Vorlesungen mit Übungen zur Symbolischen Integration, Differentialalgebra und natürlich zur Computeralgebra zu dienen. Diese Monographie zu einem der faszinierenden Basisthemen der Computeralgebra darf in keiner Arbeitsgruppe fehlen. Sie ist auch - etwa nach der Lektüre eines Übersichtsartikels (z.B. R. KRAUME Symbolische Integration im Spektrum der Wissenschaft 3 (1996), S. 95-98 oder Eine Einführung in die Computeralgebra-Algorithmen zur Symbolischen Integration, Wiss. Berichte des FZ Karlsruhe (1996) S. 69-113 des Unterzeichners) - für den Vertiefung und auf Hintergrundinformationen über die Algorithmen eines Computeralgebra-Systems bedachten Gymnasial- oder Fachhochschullehrers, der in der Lehre Computeralgebra-Systeme einsetzt, von Interesse.
Dem rundum gelungenen Buch ist eine weite Verbreitung zu wünschen, dem Autor die Zeit um bald einen zweiten Teil zur Theorie der symbolischen Integration algebraischer Funktionen folgen zu lassen!
Rezension: Johannes Grabmeier (Heidelberg) aus Computeralgebra-Rundbrief, Nr. 20 - März 1997
Kurz vor seinem Tod (siehe Nachruf auf Seite 37 im Computeralgebra-Rundbrief, Nr. 37 - Oktober 2005) ist die zweite Auflage dieser Monographie über symbolische Integration erschienen. Die erste Auflage erschien 1997 und wurde damals vom Unterzeichner im Computeralgebra-Rundbrief mit der Nummer 20 vom Frühjahr 1997 ausführlich besprochen (s.o.).
Das Buch ist das Standardwerk zur Frage, wie algorithmisch entschieden werden kann, ob die Stammfunktion einer elementaren Funktion wieder elementar ist oder nicht. Im ersten Fall wird diese dann auch berechnet. Die römische Eins bezieht sich auf die in diesem Buch ausschließlich behandelte Klasse der transzendenten Funktionen.
Die neun Kapitel der ersten Auflage konnten nahezu unverändert bleiben, lediglich kleinere Fehlerkorrekturen – man hat Mühe solche überhaupt zu finden – wurden eingearbeitet. Komplett neu hingegen ist ein Kapitel 10 zur ”Parallel Integration“. Hier hat der Autor Ideen von Risch, Norman, Davenport, Trager und anderen, die teilweise bis ins Jahr 1976 zurückgehen, im Stil des Buches aufgearbeitet und ergänzt. Ausgangspunkt für diese Theorie ist der zentrale Satz von Liouville, der aussagt, dass sich der Integrand im Falle der elementaren Integrierbarkeit in der Form
darstellen lässt. Dabei sind die ui multivariate Polynome in den transzendenten Körpererweiterungen des Konstantenkörpers, v entsprechend eine rationale Funktion und D die Ableitung (Derivation) (siehe (10.1) auf Seite 297). Nun werden für die ui, für den Nenner von v und den Grad des Zählers von v sinnvolle Ansätze gemacht. Das geschieht parallel! Die Berechnung der algebraischen Größen reduziert sich dann auf das Lösen von linearen Gleichungssystemen. Ist man erfolgreich, hat man sehr schnell und effizient eine Stammfunktion gefunden, falls nicht, dann weiß man natürlich nichts, da ja die Ansätze falsch sein können. Das macht das Verfahren zu einer Heuristik, die aber in einigen Computeralgebrasystemen sehr erfolgreich zum Einsatz kommt.
Bronstein selbst hat mit Datum vom 10.05.2005 eine Maple-Implementierung mit weniger als 100 Zeilen Code im Netz bereit gestellt. Dabei steht pmint für ”Pure Man’s Integrator“. Bronstein schreibt dazu
”It is based on recent improvements to a powerful heuristic called parallel integration. While it is not meant to be as complete as the large commercial integrators based on the Risch algorithm, its very small size makes it easy to port to any computer algebra system or library capable of factoring multivariate polynomials. Because it is applicable to special functions (such as Airy, Bessel, Whittaker, Lambert), it is able to compute integrals not handled by the existing integrators. pmint is not meant as a replacement for existing integrators, but either as an extension, or as a cheap and powerful alternative for any computer algebra project.“
Meine Besprechung der ersten Auflage 1997 endete mit dem folgenden Wunsch: ”Dem rundum gelungenen Buch ist eine weite Verbreitung zu wünschen, dem Autor die Zeit um bald einen zweiten Teil zur Theorie der symbolischen Integration algebraischer Funktionen folgen zu lassen!“ Der erste Teil des Wunsches ist mit dieser Neuauflage in Erfüllung gegangen und gilt weiter, der zweite Teil kann nicht mehr in Erfüllung gehen.
Rezension: Johannes Grabmeier (Deggendorf) aus Computeralgebra-Rundbrief, Nr. 37 - Oktober 2005