Numerische Lineare Algebra
Die numerische lineare Algebra entwickelt Algorithmen zur Lösung linearer Gleichungssysteme, Kleinste-Quadrate-Probleme und Eigenwertprobleme auf einem Computer, unter expliziter Berücksichtigung von Genauigkeit, Stabilität und Kosten in der endlichen Arithmetik.
Definition
Numerische lineare Algebra ist die Untersuchung von Algorithmen zur Durchführung linear-algebraischer Berechnungen – hauptsächlich die Lösung linearer Systeme und Eigenwert-/Singulärwertprobleme – zusammen mit der Analyse ihrer Genauigkeit, Stabilität und Effizienz in der endlichen Arithmetik.
Scope
Dieser Bereich umfasst den rechnerischen Kern, der den meisten wissenschaftlichen Berechnungen zugrunde liegt: das Lösen von Ax = b, das Berechnen von Matrixfaktorisierungen (LU, QR, Cholesky, SVD), das Finden von Eigenwerten und Singulärwerten sowie die Analyse, wie Rundungsfehler und Problemkonditionierung das berechnete Ergebnis beeinflussen. Er umfasst sowohl dichte als auch strukturierte Matrizen und behandelt das Gleitkommaverhalten von Algorithmen als primäres Anliegen.
Sub-topics
Core questions
- Wie kann ein lineares System Ax = b genau und effizient gelöst werden, und wann ist die Antwort vertrauenswürdig?
- Welche Matrixfaktorisierungen legen die Struktur offen, die zur Lösung von Kleinste-Quadrate- und Eigenwertproblemen benötigt wird?
- Wie bestimmen die Konditionierung des Problems und die Stabilität des Algorithmus gemeinsam den Fehler in der endlichen Arithmetik?
- Wie können Eigenwerte und Singulärwerte berechnet werden, ohne schlecht konditionierte Zwischengrößen zu bilden?
Key theories
- Rückwärtsfehleranalyse
- Eine berechnete Lösung wird als exakte Lösung eines leicht gestörten Problems interpretiert; ein Algorithmus ist rückwärtsstabil, wenn diese Störung in der Größenordnung des Maschinengenauigkeit liegt, was die Stabilität des Algorithmus von der Konditionierung des Problems trennt.
- Konditionierung und Konditionszahl
- Die Empfindlichkeit eines linear-algebraischen Problems gegenüber Störungen wird durch eine Konditionszahl quantifiziert; für lineare Systeme ist der relative Fehler durch die Konditionszahl der Matrix multipliziert mit der relativen Störung begrenzt, unabhängig vom verwendeten Algorithmus.
- Matrixfaktorisierungsparadigma
- Die meisten Algorithmen reduzieren ein Problem auf ein Produkt einfacherer (dreieckiger, orthogonaler, diagonaler) Faktoren; LU, QR, Cholesky und die SVD liefern kanonische Faktorisierungen, aus denen Lösungen, Kleinste-Quadrate-Anpassungen und Spektren abgelesen werden.
Clinical relevance
Die numerische lineare Algebra ist das rechnerische Substrat für praktisch jede quantitative Disziplin: diskretisierte Differentialgleichungen, Optimierung, Statistik und Regression, maschinelles Lernen, Signal- und Bildverarbeitung sowie Netzwerkanalyse reduzieren sich alle auf große lineare Systeme, Kleinste-Quadrate-Probleme oder Eigenwertberechnungen, deren Zuverlässigkeit von stabilen Matrixalgorithmen abhängt.
History
Das Feld wurde Mitte des 20. Jahrhunderts durch das Aufkommen digitaler Computer und durch James H. Wilkinsons Rückwärtsfehleranalyse geprägt, die erklärte, warum die Gauß-Elimination mit Pivotisierung zuverlässig ist. In den folgenden Jahrzehnten entstanden der QR-Algorithmus für Eigenwerte, die systematische Untersuchung der Singulärwertzerlegung und die hochwertigen Bibliotheken (LINPACK, LAPACK), die stabile Algorithmen für den allgemeinen Gebrauch kodifizierten.
Key figures
- James H. Wilkinson
- Gene H. Golub
- Lloyd N. Trefethen
- Nicholas J. Higham
Related topics
Seminal works
- trefethen1997
- golub2013
- higham2002
Frequently asked questions
- Was ist der Unterschied zwischen Konditionierung und Stabilität?
- Konditionierung ist eine Eigenschaft des Problems – wie stark sich die exakte Lösung unter Störungen der Daten ändert –, während Stabilität eine Eigenschaft des Algorithmus ist – wie viel zusätzlichen Fehler er in der endlichen Arithmetik einführt. Ein stabiler Algorithmus, der auf ein schlecht konditioniertes Problem angewendet wird, kann dennoch einen großen Fehler erzeugen.
- Warum werden orthogonale Transformationen in der numerischen linearen Algebra bevorzugt?
- Orthogonale (und unitäre) Transformationen erhalten die 2-Norm und verstärken Rundungsfehler nicht, sodass daraus aufgebaute Faktorisierungen – wie QR über Householder-Spiegelungen – tendenziell rückwärtsstabil sind.