Numerische lineare Algebra

mini|Die Modellierung durch finite Elemente, wie hier zur Spannungsanalyse eines Hubkolbens (Dieselmotor), führt auf lineare Gleichungssysteme mit sehr vielen Gleichungen und Unbekannten. Die numerische lineare Algebra ist ein zentrales Teilgebiet der numerischen Mathematik. Sie beschäftigt sich mit der Entwicklung und der Analyse von Rechenverfahren (Algorithmen) für Problemstellungen der linearen Algebra, insbesondere der Lösung von linearen Gleichungssystemen und Eigenwertproblemen. Solche Probleme spielen in allen Natur- und Ingenieurwissenschaften, aber auch in der Ökonometrie und in der Statistik eine große Rolle.

Die Algorithmen der numerischen linearen Algebra lassen sich grob in zwei Gruppen einteilen: in die direkten Verfahren, die theoretisch nach endlich vielen Rechenschritten die exakte Lösung eines Problems liefern, und in die iterativen Verfahren, bei denen die exakte Lösung schrittweise immer genauer angenähert wird. Da aber auch die direkten Verfahren wegen der beim Rechnen mit endlicher Genauigkeit entstehenden Rundungsfehler nur Näherungen für die exakte Lösung liefern, ist diese Unterscheidung nur für die Entwicklung und Untersuchung der Verfahren selbst von Bedeutung; für den praktischen Einsatz spielt sie keine große Rolle. Historisch gehen die ersten systematischen Verfahren aus beiden Gruppen – das direkte gaußsche Eliminationsverfahren und das iterative Gauß-Seidel-Verfahren – auf Carl Friedrich Gauß zurück. Beispiele für bedeutende Verfahren des 20. Jahrhunderts, die zahlreiche Verbesserungen und Weiterentwicklungen zur Folge hatten, sind das Zerlegungsverfahren von André-Louis Cholesky, das QR-Verfahren für Eigenwertprobleme von John G. F. Francis und Wera Nikolajewna Kublanowskaja sowie das CG-Verfahren von Eduard Stiefel und Magnus Hestenes als erster Vertreter der wichtigen Krylow-Unterraum-Verfahren.

Einführung in die Problemstellungen Ein – auch historisch gesehen – zentraler Anfangspunkt der elementaren linearen Algebra sind lineare Gleichungssysteme. Wir betrachten Gleichungen der Gestalt

für Unbekannte . Die Koeffizienten und sind gegebene Zahlen; die gesuchten Werte für sollen so bestimmt werden, dass alle Gleichungen erfüllt werden. Die Koeffizienten lassen sich zu einer Matrix zusammenfassen; die Zahlen und die Unbekannten bilden Spaltenvektoren und . Auf diese Weise ergibt sich die Matrix-Vektor-Darstellung

eines linearen Gleichungssystems: Gesucht ist ein Vektor , der bei der Matrix-Vektor-Multiplikation mit der gegebenen Matrix den gegebenen Vektor ergibt. Als Teilgebiet der Numerik betrachtet auch die numerische lineare Algebra nur sogenannte korrekt gestellte Probleme, also insbesondere nur solche Probleme, die eine Lösung besitzen und bei denen die Lösung eindeutig bestimmt ist. Insbesondere wird im Folgenden stets angenommen, dass die Matrix regulär ist, also eine Inverse besitzt. Dann gibt es für jede rechte Seite eine eindeutig bestimmte Lösung des linearen Gleichungssystems, die formal als angegeben werden kann.

Viele wichtige Anwendungen führen allerdings auf lineare Gleichungssysteme mit mehr Gleichungen als Unbekannten. In der Matrix-Vektor-Darstellung hat in diesem Fall die Matrix mehr Zeilen als Spalten. Solche überbestimmten Systeme haben im Allgemeinen keine Lösung. Man behilft sich deshalb damit, den Vektor so zu wählen, dass die Differenz , das Residuum, in einem noch festzulegenden Sinn „möglichst klein“ wird. Beim mit Abstand wichtigsten Fall, dem sogenannten linearen Ausgleichsproblem, wird dazu die Methode der kleinsten Quadrate verwendet: Hierbei wird so gewählt, dass die Quadratsumme minimal wird, wobei die Komponenten des Differenzvektors bezeichnen. Mithilfe der euklidischen Norm lässt sich das auch so schreiben: Man wähle so, dass minimal wird.

Neben den linearen Gleichungen sind die Eigenwertprobleme ein weiteres zentrales Thema der linearen Algebra. Gegeben ist hierbei eine Matrix mit Zeilen und Spalten; gesucht sind Zahlen und Vektoren , sodass die Gleichung

erfüllt ist. Man nennt dann einen Eigenvektor von zum Eigenwert . Das Problem, alle Eigenwerte und Eigenvektoren einer Matrix zu bestimmen, ist gleichbedeutend damit, sie zu diagonalisieren. Das bedeutet: Man finde eine reguläre Matrix und eine Diagonalmatrix mit . Die Diagonaleinträge von sind dann die Eigenwerte von und die Spalten von die zugehörigen Eigenvektoren.

Diese Probleme treten in allen Natur- und Ingenieurwissenschaften auf. Sie spielen aber auch in den Wirtschaftswissenschaften sowie in der Statistik – und damit in allen Gebieten, die sich statistischer Methoden bedienen – eine große Rolle. Lineare Gleichungssysteme beschreiben beispielsweise Modelle in der Statik, elektrische Netzwerke oder volkswirtschaftliche Verflechtungen. So scheinbar unterschiedliche Aufgabenstellungen wie die Stabilitätsuntersuchung dynamischer Systeme, Resonanzphänomene bei Schwingungen, die Bestimmung eines PageRanks oder die Hauptkomponentenanalyse in der Statistik führen alle auf Eigenwertprobleme. Lineare Gleichungen entstehen auch durch Linearisierung und Diskretisierung innerhalb anderer numerischer Verfahren. So lassen sich beispielsweise zahlreiche Modelle in Naturwissenschaft und Technik durch partielle Differentialgleichungen beschreiben. Ihre numerische Lösung durch Differenzen- oder Finite-Elemente-Verfahren führt auf Systeme mit sehr vielen Unbekannten.

In diesem Übersichtsartikel wird der Einfachheit halber angenommen, dass alle gegebenen Matrizen und Vektoren reell sind, das heißt, dass alle ihre Einträge reelle Zahlen sind. Meist lassen sich die angesprochenen Verfahren direkt auf komplexe Zahlen verallgemeinern; an die Stelle der orthogonalen Matrizen tritt dann beispielsweise ihr komplexes Pendant, die unitären Matrizen. Mitunter ist es auch vorteilhaft, ein gegebenes komplexes Problem – etwa durch Betrachtung von Real- und Imaginärteil – auf ein reelles zurückzuführen. Zusatzüberlegungen treten allerdings bei Eigenwertproblemen mit nichtsymmetrischen reellen Matrizen auf, denn diese können auch nichtreelle Eigenwerte und Eigenvektoren haben.

Geschichte Die Anfänge: Gauß und Jacobi mini|hochkant|Lithographie von Gauß in den Astronomischen Nachrichten, 1828 von Bendixen Bereits seit der Antike sind Lösungen konkreter Problemstellungen überliefert, die aus heutiger Sicht als lineare Gleichungssysteme angesehen werden können. Die Neun Kapitel der Rechenkunst, in denen der Stand der chinesischen Mathematik des 1. Jahrhunderts n. Chr. zusammengefasst ist, enthielten dabei bereits tabellarische Rechenvorschriften, die Eliminationsverfahren in Matrixdarstellung entsprachen. Die systematische Untersuchung linearer Gleichungssysteme setzte gegen Ende des 17. Jahrhunderts mit ihrer Formulierung mithilfe allgemeiner Koeffizienten ein. Nach Vorarbeiten von Gottfried Wilhelm Leibniz und Colin Maclaurin veröffentlichte Gabriel Cramer 1750 eine explizite Lösungsformel für beliebig viele Unbekannte mithilfe von Determinanten. Mit dieser cramerschen Regel war das Problem theoretisch vollständig gelöst, auch in Hinblick auf Existenz und Eindeutigkeit von Lösungen. Für deren praktische Berechnung erwies sich die Formel jedoch als völlig ungeeignet, weil der Rechenaufwand dabei mit der Anzahl der Unbekannten astronomisch schnell anwächst (siehe auch Cramersche Regel#Rechenaufwand).Chabert: A History of Algorithms. 1999, S. 283 f.

Die erste Verwendung und Beschreibung systematischer Rechenverfahren für lineare Gleichungen geht auf Carl Friedrich Gauß (1777–1855) zurück. Zu Beginn des 19. Jahrhunderts waren die Bestimmung der Bahndaten astronomischer Objekte und die Landesvermessung durch Triangulation die wichtigsten Anwendungsaufgaben der mathematischen Praxis. 1801 erregte Gauß großes Aufsehen, als es ihm gelang, die Bahn des neu entdeckten Kleinplaneten Ceres aus wenigen Beobachtungen so genau zu bestimmen, dass Ceres Ende des Jahres wiedergefunden werden konnte. Für das zugehörige überbestimmte Gleichungssystem verwendete er die von ihm entdeckte Methode der kleinsten Quadrate. Das von ihm zur Berechnung der Lösung eingesetzte Eliminationsverfahren beschrieb Gauß systematisch ab 1809 im Rahmen der Bahnbestimmung des Asteroiden Pallas, allerdings noch direkt angewendet auf Quadratsummen.Chabert: A History of Algorithms. 1999, S. 291 f.

mini|hochkant|Carl Jacobi Auch das erste Iterationsverfahren zur Lösung linearer Gleichungssysteme – das Gauß-Seidel-Verfahren – stammt von Gauß. In einem Brief an Christian Ludwig Gerling berichtete er 1823 von einem neuen einfachen Verfahren, mit dem die Lösung Schritt für Schritt immer besser angenähert werden könne. Gauß, der inzwischen mit der Triangulation des Königreichs Hannover beschäftigt war, schreibt darin, er rechne fast jeden Abend noch einen Iterationsschritt; das sei eine angenehme Abwechslung zur einförmigen Aufnahme der Messdaten. Das Verfahren sei so wenig anfällig für Fehler, dass es sich sogar „halb im Schlaf“ ausführen lasse.Chabert: A History of Algorithms. 1999, S. 296 f. 1845 veröffentlichte Carl Gustav Jacob Jacobi ein anderes, ähnliches Iterationsverfahren, das Jacobi-Verfahren. Als Philipp Ludwig von Seidel, ein Schüler Jacobis, 1874 ein System mit 72 Unbekannten lösen musste, entwickelte er eine modifizierte, verbesserte Version dieser Methode. Wie sich im Nachhinein herausstellte, ist dieses Verfahren äquivalent zum Iterationsverfahren von Gauß, von dem Seidel jedoch vermutlich nichts wusste.Chabert: A History of Algorithms. 1999, S. 300–302. Jacobi veröffentlichte 1846 auch ein iteratives Verfahren zur Transformation von Matrizen, das sich zur Lösung des Eigenwertproblems für symmetrische Matrizen eignet und heute ebenfalls als Jacobi-Verfahren bezeichnet wird. Er selbst verwendete es jedoch nur als Vorbereitungsschritt, um die Diagonaleinträge der Matrix stärker dominant zu machen.Golub, Vorst: Eigenvalue computation in the 20th century. 2000, S. 42.

20. Jahrhundert Im Jahr 1923 wurde ein von André-Louis Cholesky entwickeltes Verfahren veröffentlicht, das bestimmte lineare Gleichungssysteme löst, indem die Koeffizientenmatrix in ein Produkt zweier einfacherer Matrizen zerlegt wird, die Cholesky-Zerlegung. Auch das gaußsche Eliminationsverfahren stellte sich im Nachhinein als ein Spezialfall solcher Matrixzerlegungsverfahren heraus. Algorithmen aus dieser Verfahrensgruppe sind auch heute noch die Standardverfahren zur Lösung mäßig großer Systeme.Chabert: A History of Algorithms. 1999, S. 310 f.

Ab Ende der 1920er Jahre kamen auch neue Ideen zur iterativen Lösung von Eigenwertproblemen auf, beginnend 1929 mit der Vorstellung der Potenzmethode durch Richard von Mises. Wie auch bei der Weiterentwicklung zur inversen Iteration durch Helmut Wielandt 1944, können mit diesen einfachen Vektoriterationsverfahren immer nur Eigenvektoren zu einem einzelnen Eigenwert berechnet werden.Golub, Vorst: Eigenvalue computation in the 20th century. 2000, S. 43. Eine vollständige Lösung des Eigenwertproblems für beliebige Matrizen blieb aufwändig. Der Durchbruch kam hier 1961–1962 mit der Entwicklung des QR-Verfahrens durch den britischen Informatiker John G. F. Francis und unabhängig davon durch die russische Mathematikerin Wera Nikolajewna Kublanowskaja. Während Kublanowskaja in ihrer Arbeit von Anfang an ein tiefes Verständnis der Konvergenzeigenschaften der Methode aufzeigte, arbeitete Francis vor allem an Implementierungsdetails, die das Verfahren schnell und stabil machten. Das QR-Verfahren ist bis heute das Standardverfahren zur Berechnung aller Eigenwerte und Eigenvektoren nicht allzu großer Matrizen.Golub, Vorst: Eigenvalue computation in the 20th century. 2000, S. 47.

mini|hochkant|Eduard Stiefel, 1955