Direkte Methoden für lineare Systeme

Direkte Methoden lösen ein lineares System Ax = b in einer endlichen Anzahl arithmetischer Schritte, typischerweise durch Faktorisierung der Matrix und anschließende Lösung von Dreieckssystemen mittels Substitution.

Definition

Eine direkte Methode ist ein Algorithmus, der die exakte Lösung eines linearen Systems – bis auf Rundungsfehler – in einer vorbestimmten endlichen Anzahl von Operationen berechnet, im Gegensatz zu einer iterativen Methode, die eine Folge von Approximationen erzeugt.

Scope

Dieses Thema behandelt die Gauß-Elimination, ihre Darstellung als LU-Faktorisierung, die Rolle der Pivotisierung bei der Kontrolle des Fehlerwachstums, Vorwärts- und Rückwärtssubstitution für Dreieckssysteme sowie die Operationszählungen, die direkte Löser für dichte und Bandmatrizen praktikabel machen.

Core questions

• Wie reduziert die Gauß-Elimination ein System auf Dreiecksform, und warum ist dies äquivalent zu einer LU-Faktorisierung?
• Warum ist Pivotisierung notwendig, und wie kontrollieren partielle und vollständige Pivotisierung das Wachstum von Rundungsfehlern?
• Was sind die Rechenkosten einer direkten Lösung, und wie reduziert die Ausnutzung von Struktur (Symmetrie, Bandbreite, Dünnbesetztheit) diese?
• Unter welchen Bedingungen ist die Gauß-Elimination mit partieller Pivotisierung in der Praxis rückwärtsstabil?

Key theories

LU-Faktorisierung mit partieller Pivotisierung

Die Gauß-Elimination mit Zeilenvertauschungen faktorisiert eine Matrix als PA = LU, wobei L eine unäre untere Dreiecksmatrix und U eine obere Dreiecksmatrix ist; partielle Pivotisierung begrenzt die Multiplikatoren und macht die Methode für fast alle in der Praxis vorkommenden Matrizen zuverlässig.

Wachstumsfaktor und Rückwärtsstabilität

Der Rückwärtsfehler der Gauß-Elimination wird durch den Wachstumsfaktor der Einträge während der Elimination bestimmt; obwohl in konstruierten Fällen exponentielles Wachstum möglich ist, hält partielle Pivotisierung das Wachstum klein genug, sodass die Methode für praktisch alle realen Probleme rückwärtsstabil ist.

Mechanisms

Die Gauß-Elimination verläuft spaltenweise: In jedem Schritt wird ein Pivotelement ausgewählt (partielle Pivotisierung wählt den Kandidaten mit dem größten Betrag in der aktuellen Spalte), Vielfache der Pivotzeile werden von den darunterliegenden Zeilen subtrahiert, um Nullen zu erzeugen, und die Multiplikatoren werden gespeichert, um L zu bilden. Das resultierende obere Dreieckssystem U wird durch Rückwärtssubstitution gelöst, und die rechte Seite wird durch Vorwärtssubstitution verarbeitet. Für eine n-mal-n-dichte Matrix kostet die Faktorisierung etwa zwei Drittel n-hoch-drei Operationen, während jede Dreieckslösung etwa n-hoch-zwei Operationen kostet.

Clinical relevance

Direkte Löser sind das Standard-Arbeitspferd, wann immer ein mittelgroßes dichtes oder Band-System mit voller Genauigkeit gelöst werden muss – bei der Finite-Elemente-Montage, Schaltungssimulation, Steuerung und als innere Lösung innerhalb größerer numerischer Schemata – und eine einzige Faktorisierung kann wiederverwendet werden, um viele rechte Seiten kostengünstig zu lösen.

History

Eliminationsmethoden lassen sich auf Gauß und frühere zurückführen, aber ihr Verhalten in der endlichen Arithmetik wurde durch Wilkinsons Rückwärtsfehleranalyse in den 1960er Jahren geklärt, die zeigte, dass partielle Pivotisierung das Fehlerwachstum zähmt und die empirische Zuverlässigkeit der Methode erklärte, die lange auf frühen Computern beobachtet worden war.

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

Wann sollte eine direkte Methode einer iterativen vorgezogen werden?

Direkte Methoden werden bevorzugt, wenn die Matrix dicht oder mittelgroß ist, wenn viele rechte Seiten eine Matrix gemeinsam haben (sodass eine einzige Faktorisierung wiederverwendet wird) oder wenn eine garantierte endliche Lösung mit voller Genauigkeit erforderlich ist. Sehr große dünnbesetzte Systeme bevorzugen in der Regel iterative Methoden.

Garantiert Pivotisierung immer einen kleinen Fehler?

Partielle Pivotisierung garantiert in der Praxis für fast alle Matrizen Rückwärtsstabilität, überwindet aber keine schlechte Konditionierung: Wenn die Matrix selbst nahezu singulär ist, kann selbst eine rückwärtsstabile Lösung eine Lösung mit großem Vorwärtsfehler liefern.