Die beiden zentralen Aufgaben der numerischen linearen Algebra sind die Lösung linearer Gleichungssysteme und die Lösung von Eigenwertaufgaben. Sie sind Teilgebiete der numerischen Mathematik, welche einerseits eigenständig neben anderen Teilgebieten wie Interpolation, Approximation, Optimierung, Lösung nichtlinearer Gleichungen, Lösung gewöhnlicher und partieller Differentialgleichungen stehen, andererseits wichtige Hilfsmittel bei der Behandlung dieser Themen sind. Auf diesem Gebiet sind in den letzten 30 Jahren, nicht zuletzt wegen der Entwicklung immer leistungsfähigerer Rechner, enorme Fortschritte erzielt worden.
Hier soll ein erster Einblick in die fundamentalen Probleme der numerischen linearen Algebra gegeben werden. Dazu werden die 6 wichtigsten Probleme angegeben, kurz ihre Bedeutung erläutert und es werden die Schwierigkeiten aufgezeigt, mit denen man beim Lösen dieser Probleme auf Rechnern konfrontiert wird, wenn 'offensichtliche' Lösungsansätze verwendet werden.
***************************************************************************************
Eine Variante dieses Problems, welche in der Praxis häufig vorkommt, erfordert das Lösen linearer Gleichungssysteme mit derselben Matrix A auf der linken Seite, verschiedenen Vektoren b auf der rechten Seite. D.h. das Problem ist, eine Matrix X = [ x_1 x_2 ... x_m] zu finden mit AX=B, wobei B = [ b_1 b_2 ... b_m] eine n-x-m Matrix ist.
Eng verknüpft mit dem Problem des Lösens von linearen Gleichungssystemen sind die folgenden Probleme : Bestimmung der Inversen, des Rangs, der Determinante, der führenden Hauptabschnittsdeterminanten, sowie einer orthonormalen Basis für den Bildraum und den Kern einer Matrix A.
Lineare Gleichungssysteme treten in fast allen Bereichen der Naturwissenschaften und Technik auf : angewandte Mathematik, Biologie, Chemie, Physik, Elektrotechnik, Maschinenbau, Tiefbau, Statik, etc.
Die meisten Probleme zum Lösen linearer Gleichungssysteme haben ihren Ursprung in der numerischen Lösung von Differentialgleichungen. Viele mathematische Modelle physikalischer und technischer Systeme sind Systeme von Differentialgleichungen (sowohl gewöhnlicher als auch partieller Differentialgleichungen). Ein System von Differentialgleichungen wird typischerweise numerisch durch Diskretisierung des Systems mittels finiter Differenzen- oder finiter Elemente-Methode gelöst. Der Prozeß der Diskretisierung führt i.a. auf ein lineares Gleichungssystem, dessen Lösung eine Approximation an die Lösung des Systems von Differentialgleichungen ist.
***************************************************************************************
Least-squares Probleme treten in statistischen und geometrischen Anwendungen auf, welche das Anpassen eines Polynoms oder einer Kurve an experimentelle Daten erfordern, sowie in technischen Anwendungen wie Signal- und Bildverarbeitung. Methoden zur numerischen Lösung von least-squares Problemen führen unweigerlich auf das Lösen von linearen Gleichungssystemen.
***************************************************************************************
Das Eigenwertproblem tritt typischerweise bei der Lösung und Stabilitätsanalyse homogener Systeme von Differentialgleichungen erster Ordung auf. Zur Stabilitätsanalyse benötigt man nur implizite Kenntnis der Eigenwerte, bei der Lösung homogener Systeme benötigt man die Eigenwerte und Eigenvektoren explizit.
Anwendungen wie Wertpapieranalyse (stock market analysis) und das Studium des Verhaltens dynamischer Systeme erfordert die Berechnung von nur einigen wenigen Eigenvektoren und Eigenwerten - häufig die größten oder kleinsten.
In vielen Anwendungen ist die Matrix A symmetrisch, das führt dann auf das symmetrische Eigenwertproblem. Eine große Anzahl der Eigenwertprobleme in technischen Anwendungen sind allerdings verallgemeinerte Eigenwertprobleme.
***************************************************************************************
Verallgemeinerte Eigenwertprobleme treten z.B. bei der Analyse von Schwingungen von nicht gedämpften Strukturen auf, welche als System von Differentialgleichungen 2. Ordnung B d^2z/dt^2 + A z = 0 modelliert werden.
Ähnlich führt das gedämpfte System A d^2z/dt^2 + B dz/dt + C = 0 zum quadratischen Eigenwertproblem.
***************************************************************************************
***************************************************************************************
Diese Zerlegung ist als Singulärwertzerlegung von A bekannt. Die Eigenwerte von Sigma sind die singulären Werte. Die Spaltenvektoren von U und V nennt man singuläre Vektoren.
In vielen Bereichen, z.B. Kontrolltheorie, Biomedizintechnik, Signal-, Bildverarbeitung und statistischen Anwendungen, tritt das Problem, eine Singulärwertzerlegung zu berechnen, auf. Diese Anwendungen erfordern typischerweise die Bestimmung des Rangs von A, einer orthonormalen Basis, von Projektionen, des Abstands einer Matrix zu einer anderen von niedrigerem Rang, etc. in Gegenwart von gewissen Verunreinigungen (bekannt als 'noise') in den Daten. Singuläre Werte und Vektoren sind die numerisch verläßlichsten Mittel diese Dinge zu bestimmen. Die Singulärwertzerlegung ist ebenfalls der numerisch effektiveste Ansatz zur Lösung von least-squares Problemen, insbesondere wenn A nicht vollen Rang hat.
Einige 'offensichtliche' Ansätze, obige Probleme zu lösen sind nicht praktikabel im Rahmen einer Computerimplementierung und können sogar ungenaue Ergebnisse produzieren.
Die Cramer'sche Regel ist von theoretischer und historischer Bedeutung. Leider kann sie nicht für praktische Zwecke verwendet werden. Selbst bei einem 20 x 20 System von linearen Gleichungen würde man auf einem schnellen, modernen Computer mehrere zehntausend Jahre zur Lösung des linearen Gleichungssystems benötigen, wenn man die gewöhnliche Definition der Determinante einer Matrix verwendet.
Die eindeutige Lösung eines nichtsingulären linearen Gleichungssystems kann explizit als x = A^{-1} b geschrieben werden. Die Berechnung der Lösung eines linearen Gleichungssystems mittels der Inversen von A ist numerisch ungünstig. Die Berechnung der Inversen einer Matrix erfordert ca. 3mal soviel Zeit wie das Lösen des linearen Gleichungssystems mittels eines Standardeliminationsverfahrens und führt i.a. zu höherer Ungenauigkeit. Betrachte dazu ein triviales Beispiel : Löse 3x=27. Ein Eliminationsverfahren wird x=9 ergeben und nur eine Division benötigen. Berechnet man hingegen die Lösung mittels Inversion, erhält man x = 1/3 * 27. In 4-stelliger Arithmetik ergibt dies x = 0.333*27 = 8.9991 und erfordert eine Division und eine Multiplikation.
Man beachte, daß die Rechenzeit, die ein Algorithmus benötigt, theoretisch als Anzahl der arithmetischen Operationen, welche ausgeführt werden müss en, geschätzt wird.
Hat die Matrix A vollen Rang und ist m >= n, dann hat das least-squares Problem eine eindeutige Lösung, und diese Lösung ist theoretisch durch die Lösung x des linearen Gleichungssystems (A^T)Ax = (A^T)b gegeben. Diese Gleichungen sind als Normalengleichungen bekannt. Ein solches Verfahren hat mehrere schwerwiegende numerische Probleme. Zum einen, in finite-precision Arithmetik geht bei der expliziten Berechnung von (A^T)A wichtige Information verloren. Zum anderen sind die Normalengleichungen sehr viel anfälliger gegenüber Störungen als ein lineares Gleichungssystem Ax=b und diese Sensitivität kann die Genauigkeit der mittels der Normalengleichung berechneten Lösung über das Maß, welches die Daten vermuten lassen, hinaus verderben.
Die Eigenwerte einer Matrix A sind die Nullstellen des zugehörigen charakteristischen Polynoms. Ein offensichtlicher Ansatz zur Bestimmung der Eigenwerte wäre also das charakteristische Polynom von A zu berechnen und seine Nullstellen mittels eines Standard-Nullstellennäherungsverfahrens zu finden. Dies ist kein numerisch akzeptabler Weg. Die Rundungsfehler, welche beim Berechnen des charakteristischen Polynoms auftreten, werden sehr wahrscheinlich kleine Störungen in den berechneten Koeffizienten verursachen. Diese kleinen Fehler in den Koeffizienten können große Fehler in den Eigenwerten hervorrufen. Die Nullstellen gewisser Polynome sind bekanntermaßen extrem anfällig gegenüber kleinen Störungen in den Koeffizienten. Ein klassisiches Beispiel ist das Wilkinson-Polynom. Wilkinson hat ein Polynom 20.ten Grades mit verschiedenen Nullstellen 1, 2, ..., 20 genommen und den Koeffizienten von x^{19} ein wenig gestört. Die Nullstellen dieses leicht gestörten Polynoms wurden dann mit einem Standard-Nullstellennäherungsverfahren berechnet mit dem Resultat, daß einige der Nullstellen völlig anders wurden; einige wurden sogar komplex.
Das verallgemeinerte Eigenwertproblem A x = lambda B x ist im Falle, daß B nichtsingulär ist, äquivalent zu dem Eigenwertproblem B^{-1}A x = lambda x. Ist aber die Matrix B fast singulär, so kann das Bilden der Matrix B^{-1}A auf der linken Seite mittels expliziter Berechnung der Inversen von B zu Ungenauigkeiten führen, welche dann zu Ungenauigkeiten in den berechneten Eigenwerten führen.
Ähnliche Aussagen gelten für das quadratische Eigenwertproblem. In vielen technischen Anwendungen, wie z.B. der Statik, ist die Matrix A eine symmetrisch positiv definite Matrix und daher nichtsingulär. In diesem Fall ist das quadratische Eigenwertproblem äquivalent zu dem Eigenwertproblem E u = lambda u, wobei E eine Blockmatrix mit den Blöcken
E_{11} = 0, E_{12} = I, E_{21} = -A^{-1}B und E_{22} = -A^{-1}C
ist. Numerisch ist es nicht ratsam das quadratische Eigenwertproblem durch die explizite Berechnung von E zu lösen. Ist A fast singulär, dann kann die Matrix E nicht akkurat gebildet werden und die berechneten Eigenwerte sind zu ungenau.
Für m >= n sind die singulären Werte von A die nichtnegativen Wurzeln der Eigenwerte von (A^T)A. Auf diese Art und Weise die singulären Werte zu berechnen ist jedoch numerisch ungünstig. Wie eben führt auch hier das explizite Bilden des Matrixprodukts zu einem Verlust von wesentlicher Information. Betrachte dazu das einfache Beispiel :
A_{11} = 1, A_{12} = 1, A_{21} = eps, A_{22} = 0, A_{31} = 0, A_{32} = 0
wobei eps so gewählt sei, daß 1 + eps^2 = 1 in finite-precision Arithmetik sei. Dann erhalten wir auf dem Rechner
((A^T)A)_{11} = 1, ((A^T)A)_{12} = 1,((A^T)A)_{21} = 1,((A^T)A)_{22} = 1.
Die Eigenwerte sind 2 und 0. Als berechnete singuläre Werte ergeben sich sqrt(2) und 0. Die exakten singulären Werte lauten sqrt(2) und sqrt(2) eps.
Wir haben hier aufgezeigt, wie einige 'offensichtliche' Lösungsansätze zur Lösung von Problemen der numerischen linearen Algebra zu Schwierigkeiten bei der Berechnung auf Computern führen können und Ungenauigkeiten in den Ergebnissen hervorrufen. Die numerische lineare Algebra beschäftigt sich mit der Analyse oben dargestellter Schwierigkeiten, mit Untersuchungen, wie diese Schwierigkeiten überwunden werden können, und mit der Formulierung und Implementierung von numerisch robuster Software. Gute Software-Entwicklung erfordert ein mathematisches Verständnis des zu lösenden Problems, ein Gefühl für algorithmischen Ausdruck und Verständnis für finite-precision Arithmetik. Ein Ziel ist stets, Programmpakete zu entwickeln, deren Prozeduren von anderen Wissenschaftlern und Ingenieuren als verläßliche black-box in komplizierterer Software, welche auf ihre speziellen Probleme zugeschnitten ist, eingesetzt werden können.
Forschungsschwerpunkte der Abteilung Numerische Mathematik sind: