Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


37. Gaußsches Eliminationsverfahren



Eine der fundamentalsten wissenschaftlichen Berechnungen ist die Lösung
von Systemen von Gleichungen, die gleichzeitig erfüllt sein sollen. Der grundlegende Algorithmus für die Lösung derartiger Gleichungssysteme, das Gaußsche Eliminationsverfahren, ist relativ einfach und hat sich während der 150 Jahre, die seit seiner Entdeckung vergangen sind, kaum verändert. Dieser Algorithmus ist inzwischen gründlich erforscht worden, insbesondere im Verlaufe der letzten zwanzig Jahre, so daß man bei seiner Anwendung mit einiger Zuversicht erwarten kann, daß er in effizienter Weise genaue Ergebnisse liefert.

Das Gaußsche Eliminationsverfahren ist ein Beispiel für einen Algorithmus, der sicher in den meisten Computeranlagen zur Verfügung steht; tatsächlich stellt er sogar in vielen Programmiersprachen ein Grundelement dar, z.B. in APL. Der grundlegende Algorithmus läßt sich jedoch leicht verstehen und implementieren, und es können besondere Situationen eintreten, in denen es wünschenswert ist, eine modifizierte Variante des Algorithmus zu implementieren, anstatt mit einem Standard-Unterprogramm zu arbeiten. Außerdem verdient das Verfahren untersucht zu werden, da es eins der wichtigsten numerischen Verfahren ist, die derzeit angewandt werden.

Wie bei den anderen mathematischen Fragen, die wir bisher betrachtet haben, werden wir bei unserer Abhandlung nur die Grundprinzipien beleuchten und in einer abgeschlossenen Weise darlegen. Kenntnisse der linearen Algebra sind nicht erforderlich, um die grundlegende Methode zu verstehen. Wir wollen eine einfache Pascal-Implementation entwickeln, die für einfache Anwendungen vielleicht leichter verwendbar ist als ein Bibliotheksunterprogramm. Wir werden jedoch auch Beispiele für die Schwierigkeiten kennenlernen, die auftreten könnten. Natürlich ist für eine umfangreiche oder wichtige Anwendung eine ausgefeilte Implementation notwendig, ebenso wie eine gewisse Vertrautheit mit den zugehörigen mathematischen Grundlagen.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]