Numerische Lineare Algebra

Für gewöhnlich werden die folgenden Probleme als die Standardprobleme der numerischen linearen Algebra betrachtet:

• Lineare Gleichungssysteme: Löse Ax=b. Dabei ist A eine vorgegebene nichtsinguläre n-x-n Matrix , b ein Vektor der Länge n und x der Vektor, dessen Komponenten wir berechnen wollen.
• Lineare Ausgleichsprobleme: Berechne einen Vektor x, der || Ax - b||_2 minimiert, wobei A eine n-x-n Matrix, b ein gegebener Vektor der Länge m und x ein Vektor der Länge n ist. Dabei bezeichnet || y||_2 die 2-Norm eines Vektors y. Wenn m > n ist, haben wir mehr Gleichungen als Unbekannte. Das resultierende System ist überbestimmt. Im Fall m < n ist das System unterbestimmt und es gibt unendlich viele Lösungen, wenn nicht zusätzliche Bedingungen gestellt werden.
• Eigenwertprobleme: Gegeben sei eine n-x-n Matrix A. Finde einen Vektor x der Länge n und ein Skalar c, so dass A*x = c*x.

Diese Standardprobleme tauchen in vielen ingenieur-, wirtschafts- und sozialwissenschaftlichen, biotechnologischen und theoretischen Problemen auf. Sie stehen im Zentrum der meisten Algorithmen des wissenschaftlichen Rechnens und es existieren bereits viele gut verstandene Algorithmen, um sie zu lösen. Desweiteren stehen robuste und intensiv gesteste Programmbibliotheken zur Verfügung, in denen diese Algorithmen implementiert sind. Ein hervorragendes public-domain Archiv für solche Software ist http://www.netlib.org. Der Netlib Service sorgt für einen schnellen, leicht verständlichen und effizienten Zugang für Wissenschaftler. Er beinhaltet verschiedenste Sofwarepakete und nützliche Testprobleme. Besonders hervorzuheben ist die LAPACK Bibliothek. Sie beinhaltet state-of-the-art Routinen zur Lösung der häufigsten Probleme, die in der numerischen linearen Algebra auftauchen. Verschiedene kommerzielle Programmpakete, wie zum Beispiel MATLAB (eingetragenes Warenzeichen von The Mathworks) bieten eine benutzerfreundliche auf LAPACK basierende Umgebung an (auf Kosten von etwas Performance der Routinen).

Aber die wachsende Komplexität und Größe der zu lösenden Probleme erfordert einen stetigen Fortschritt in der Entwicklung neuer Algorithmen und/oder Implementierungen für diese Standardprobleme. Insbesondere die seit einiger Zeit verfügbaren fortschrittlichen Computersysteme haben einen großen Einfluss auf alle Gebiete des wissenschaftlichen Rechnens inklusive der algorithmischen Forschung und der Softwareentwicklung in der numerischen linearen Algebra. Neue Implementierungen bekannter Algorithmen oder völlig neu entwickelte Algorithmen werden für die neuen Architekturen benötigt, um deren Fähigkeiten auszunutzen.

Es gibt auch zahlreiche Variationen der obengenannten Standardprobleme, z.B.,

• Verallgemeinerte Eigenwertprobleme: Ax = Bx für beliebige quadratische Matrizen A und B,
• Nichtlineare Eigenwertprobleme: f (x) = 0, wobei f eine gegebene Funktion ist, die von gewissen Koeffizientenmatrizen abhängt, z.B. das quadratische Eigenwertproblem f (x) = Mx^2 + Cx + K, wobei die Steifigkeitsmatrix K und die Massenmatrix M reell symmetrisch und positiv (semi-)definit sind und die Dämpfungsmatrix C reell ist,
• Rang-defiziente lineare Ausgleichsprobleme || Ax - b||_2 = min, wobei die Lösungen nicht eindeutig sind, da die Spalten von A linear voneinander abhängen,
• Nichtlineare Gleichungssysteme F(x) = 0, wobei F (x) eine quadratische Matrix ist,
• Nichtlineare Ausgleichsprobleme || F(x)||_2^2 = min, wobei F(x) eine rechteckige Matrix,
• Matrixgleichungen, z.B. die lineare Sylvestergleichung AX - XB = C oder die nichtlineare Zeit-diskrete Riccati Gleichung X = A^TXA - A^TXB(R + B^TXB)^{-1}B^TXA + Q

Für eine große Zahl dieser Probleme gibt es einen dringenden Forschungsbedarf für die Entwicklung von Algorithmen und deren Störungstheorie und Fehleranalysis. Es gibt z.B. keine wirklichen black box Software Pakete für nichtlineare Eigenwertprobleme, welche den Standard von denen für lineare Eigenwertprobleme erreichen.

Die Anwendungen dieser Probleme finden sich überall in den angewandten Wissenschaften, so z.B. im Maschinenbau, in der Elektrotechnik und sogar in der Pharmazie und der Medizin. Das Gebiet der numerischen linearen Algebra ist daher interessanter und fundamentaler als es der etwas langweilige Name vermuten lässt. Es ist voller mächtiger Ideen, die ganz anders sind als jene, die normalerweise mit der linearen Algebra assoziiert sind. "It is here that one finds the essential ideas that every (mathematical) scientist needs to work effectively with vectors and matrices. In fact, our subject is more than just vectors and matrices, for virtually everything we do carries over to functions and operators. Numerical linear algebra is really functional analysis, but with the emphasis always on practical algorithmic ideas rather than mathematical technicalities." (Zitat aus der Einleitung des Buches "Numerical Linear Algebra" von L.N. Trefethen und D. Bau,III, SIAM 1997.)

Es gibt mehrere grundlegende Konzepte und Techniken, die bei der Lösung von Problemen aus der angewandten und numerischen linearen Algebra benutzt werden, z.B.:

• Matrix Faktorisierungen (Zerlegungen): Die Faktorisierung einer Matrix A ist eine Darstellung von A in Form mehrerer einfacherer Matrizen, durch die sich das Problem einfacher lösen lässt. Diese Idee wird z.B. beim Lösen von linearen Gleichungssystemen Ax = b mittels dem Gauss Eliminationsverfahren benutzt. Diese Methode kann interpretiert werden als die Faktorisierung von A in das Produkt LR, einer unteren Dreiecksmatrix L und einer oberen Dreiecksmatrix R. Das Lösen von Ax = b ist dann äquivalent zum Lösen von Lz = b und Rx = z, was in einem einfachem Verfahren namens Vorwärts- und Rückwärtssubstitution getan werden kann. Beim Standardeigenwertproblem A*x = c*x wird eine nichtsinguläre Matrix S gesucht, so dass S^{-1}AS = D eine einfache Form hat, von der die Eigenwerte abgelesen werden können. Also wird A faktorisiert als A = SDS^{-1}. Die Information über die Eigenvektoren kann aus den Spalten von S erhalten werden. Das lineare Ausgleichsproblem || Ax - b||_2 = min wird normalerweise gelöst, indem A als QR faktorisiert wird, wobei Q eine Matrix mit orthonormalen Spalten und R eine obere rechte Dreiecksmatrix ist. Eine andere Möglichkeit ist die Faktorisierung von A in deren Singulärwertzerlegung UV, wobei U und V unitäre Matrizen sind und diagonal ist.
• Ausnutzung der Struktur: Wenn physikalische Informationen über das Problem genutzt werden können, sind oftmals effizientere und robustere Lösungsverfahren möglich. Wenn es z.B. bekannt ist, dass beim linearen Gleichungssystem Ax = b die Matrix A symmetrisch und positiv definit ist, kann mit der Benutzung einer Variante des Gauss Eliminationsverfahrens namens Cholesky Verfahren die Hälfte der Arbeit gespart werden. Ist A eine Bandmatrix (d.h. a_{ij} = 0 für | i - j| > m für ein m, dann kann die Rechenarbeit weiter reduziert werden, wenn ein Cholesky Algorithmus für Bandmatrizen benutzt wird. Entsprechend existieren auch speziell zugeschnittene Eigenwertverfahren für die Berechnung der Eigenwerte von symmetrischen Matrizen. Diese Verfahren reduzieren nicht nur die Anzahl an Rechenoperationen, die benötig werden, um das Problem zu lösen, sie erhalten auch die symmetrische Struktur des Problems während der Berechnung, so dass die berechneten Eigenwerte garantiert reell sein werden, eine Eigenschaft, die bei der Benutzung von allgeimeinen Eigenwertlösern nicht garantiert werden kann, obwohl die Eigenwerte symmetrischer Matrizen theoretisch reell sind.
• Störungstheorie und Konditionszahlen : Resultate, die von numerischen Algorithmen produziert werden, sind selten exakt korrekt, selbst wenn eine exakte Arithmetik angenommen wird. Es gibt zwei wesentliche Fehlerquellen, zum einen Fehler, die durch den Algorithmus selber verursacht werden, z.B. durch Approximationen im Algorithmus. Zum anderen sind die Eingabedaten oft nicht exakt, z.B. durch Meßfehler oder durch vorherige Rechnungen. Eine wichtige Frage in diesem Kontext ist, wie weit die Lösung des Problems f sich verändert, wenn die Eingabedaten ein wenig gestört werden. Das heißt, statt der Eingabedaten x haben wir die gestörten Daten x + e. Wird dann der absolute Fehler | f (x + e) - f (x)| klein sein ? Mittels linearer Approximation f(x+e) = f (x) + ef'(x)  ist der absolute Fehler ungefähr gegeben als |e| | f'(x)|. Wenn die absolute Konditionszahl | f'(x)| groß genug ist, kann der Fehler groß sein, auch wenn e klein ist. In diesem Fall ist f schlecht konditioniert.
• Rundungsfehlereffekte: Wenn ein numerischer Algorithmus auf einem Computer implementiert wird, dann wird das Resultat unvermeidbarerweise durch Rundungsfehler der Gleitkommaarithmetik des Computers beeinflusst. Natürlicherweise ist es wünschenswert, dass das berechnete Resultat alg(x) nahe beim exakten Resultat f (x) ist. Für gewöhnlich wird gefordert, dass alg(x) = f (x + e) für eine kleine Störung e.
• Analyse der Geschwindigkeit eines Algorithmus: Der traditionelle Weg, um die Zeit zu schätzen, die ein Algorithmus benötigt, besteht im Zählen der Anzahl der benutzten Gleitkommaoperationen (flops). Bei modernen Computern ist diese Abschätzung oft irreführend. Es kann signifikant länger dauern, die Daten innerhalb des Computers in das benutzte Register zu schieben als die eigentliche Berechnung benötigt. Vor allem, wenn ein Algorithmus iterativ ist (d.h. eine Serie von Approximationen der Lösung wird generiert), ist es wichtig zu wissen, ob die Konvergenzrate linear, quadratisch oder sogar schneller ist.
• Numerische Software: Ein großer Teil der momentanen Forschung in der angewandten und numerischen linearen Algebra führt zu leicht benutzbarer, verlässlicher und robuster Software. Eine große Anstrengung wird unternommen, um Wissenschaftler mit den neuesten Implementationen zu versorgen. Darum wird ein großer Teil der Software in der numerischen linearen Algebra als public-domain (siehe http://www.netlib.org) oder in kommerziellen Produkten wie MATLAB zur Verfügung gestellt. Neben diesen allgemeinen Routinen der numerischen linearen Algebra gibt es noch spezialisiertere Software wie z.B. SLICOT (siehe http://www.slicot.de). SLICOT ist ein qualitativ hochwertiges Sotwarepaket für Probleme in der System- und Kontrolltheorie. All diese Pakete achten sehr auf numerische Stabilität, Genauigkeit, Robustheit der Algorithmen, Performance in Hinblick auf Geschwindigkeit und Speicherverbrauch sowie Portabilität und Wiederbenutzbarkeit. Für gewöhnlich werden Benchmark Beispiele zur Verfügung gestellt.