Vorlesung im Wintersemester 2001/2002

Computeralgebra

Themen

Wozu Computeralgebra

Erstes Thema sind die grundlegenden Unterschiede zwischen numerischem, exaktem und symbolischem Rechnen. Je nach Anwendung hat jeder der drei Zugänge seine Vor- und Nachteile, und oft hängt die Lösbarkeit eines Problems davon ab, daß man den richtigen gewählt hat. Die "großen" Computeralgebrasysteme wie Maple, MuPad und Mathematica unterstützen allesamt jede der drei Methoden.

Datenstrukturen der Computeralgebra

Da es sich um eine mathematische Vorlesung handelt, werde ich die Vielzahl möglicher Datenstrukturen, die in Computeralgebrasystemen verwendet werden, auch nicht annähernd vollständig abhandeln; stattdessen beschränke ich mich auf einige fundamentale Techniken, anhand derer insbesondere auch klar wird, daß ein Computeralgebrasystem gelegentlich eine ganz andere Aufgabe löst als die, die der naive Anwender im Sinn hatte. Außerdem geht es in diesem Kapitel um grundsätzliche Unentscheidbarkeitsfragen, die jedem Computeralgebrasystem Grenzen setzen: Es gibt keine endliche Datenstruktur zur Beschreibung beliebiger reeller Zahlen.

Der Euklidische Algorithmus

Der Euklidischen Algorithmus zur Bestimmung des größten gemeinsamen Teilers wird wohl (fast) jedem geläfig sein, ist aber in der Praxis, insbesondere wenn es um den ggT von Polynomen geht, keineswegs so unproblematisch, wie man auf den ersten Blick meinen möchte. Bereits hier macht sich eines der Grundprobleme der Computeralgebra bemerkbar: Selbst bei Problemen mit kleinen Ausgangsdaten und kleinen Ergebnissen können riesige Zwischenresultate auftreten. Aus diesem Grund muß der Algorithmus für eine effiziente Anwendung modifiziert werden, und die Strategien, die man hier anwendet, werden sich auch bei komplizierteren und interessanteren Problemen als nützlich erweisen.

Faktorisierung von Polynomen

Das Ausmultiplizieren eines Produkts von Polynomen ist bei hohen Graden oder einer großen Anzahl von Faktoren zwar aufwendig, erfordert aber keinerlei mathematische Ideen. Für die Zerlegung eines Polynoms in Faktoren dagegen gibt es keinen offensichtlichen Ansatz, obwohl auch diese Zerlegung beispielsweise für die Nullstellenbestimmung sehr nützlich ist. Die Computeralgebra hat verschiedene Algorithmen entwickelt, die dieses Problem effizient lösen können.

Symbolische Integration

Schon die möglcherweise aus der Analysis bekannte Integration rationaler Funktionen via Partialbruckzerlegung ist nicht wirklich algorithmisch, da der Nenner in h"ochstens quadratische Faktoren zerlegt werden muß, was nur für hinreichends spezielle Polynome algorithmisch effizient möglich ist; Integrale transzendenter Funktionen werden meist mit ad hoc Methoden behandelt. Tatsächlich gibt es aber eine ganze Reihe von Verfahren, die teilweise bis ins 19. Jahrhundert zur¨ckgehen, mit denen man für große Klassen von Funktionen nicht nur Stammfunktionen konstruieren kann, sondern mit denen man gegebenenfalls auch beweisen kann, daß es keine Stammfunktion gibt, die sich durch gewisse vorgegebene Funktionen ausdrücken läßt: Beispielsweise kann die Stammfunktion von exp(-x²) nicht durch Grundrechenarten, Wurzeln, Exponentialfunktionen, Logarithmen, trigonometrische Funktionen und deren Umkehrfunktionen ausgedrückt werden.

Nichtlineare Gleichungssysteme

Lineare Gleichungssysteme lassen sich vor allem deshalb so einfach lösen, weil ihre Nullstellenmenge eine lineare Stuktur hat. Im Nichtlinearen gibt es nur noch selten Strukturen, so daß es hier zumindest im Fall einer unendlichen Lösungsmenge nur daum gehen kann, das Gleichungssystem in eine möglichst einfache Form überzuführen. Bei endlicher Lösungsmenge möchte man diese natürlich explizit angeben. Für beide Aufgaben stellt die Computeralgebra zwei Arten von Algorithmen zur Verfügung: Die schon im 19. Jahrhundert bekannten Resultantenmethoden, die heute bei der Bewegungsplanung von Robotern eine große Rolle spielen, und die etwa 35 Jahre alten Standardbasen oder Gröbnerbasen, die durch Kombination der Ideen des Gauß-algorithmus und des Euklidischen Algorithmus auch nichtlineare Gleichungssysteme auf eine Art Treppengestalt bringen können.

Exaktes Rechnen mit reellen Zahlen

Im allgemeinen ist nicht entscheidbar, ob zwei reelle Ausdrücke dieselbe Zahl darstellen oder nicht. Es gibt aber einen relativ großen Teilkörper von R, in dem man exakt rechnen und Gleichheit algorithmisch entscheiden kann. Dies spielt beispielsweise eine große Rolle in einigen Teilen der Computergraphik, wo man mit Sicherheit wissen muß, ob zwei Schnittpunkte gleich sind oder nicht.

Voraussetzungen: Grundkenntnisse der linearen Algebra und Analysis.

Hörerkreis: Für den integrierten Studiengang Mathematik und Informatik kann diese Vorlesung bei entsprechender Vertiefung für das Spezialgebiet Algebra gewählt werden oder aber für das Fach "Brücke", falls Computeralgebra entweder für das Vertiefungsfach oder das Anwendungsgebiet nützlich ist.

Für den auslaufenden Diplomstudiengang Mathematik zählt die Computeralgebra zum Prüfungsgebiet Mathematik I.

Für Technische Informatiker und Wirtschaftsinformatiker kann sie eventuell als Ergänzung interessant sein.

Literatur: Eine kommentierte Literaturliste in Postskript ist hier zu finden. Die dort aufgeführten Bücher decken natürlich ein Vielfaches des Stoffs ab, der in einer einsemestrigen Vorlesung behandelt werden kann.