Direkte Verfahren, iterative Verfahren

Die Verfahren zur Lösung des linearen Gleichungssystems

mit quadratischer Koeffizientenmatrix (n Gleichungen mit n Unbekannten) können in zwei große Gruppen eingeteilt werden:

• Die direkten Verfahren liefern nach einer endlichen Anzahl von Rechenschritten den Lösungsvektor x.
   
• Die iterativen Verfahren ermitteln den Lösungsvektor durch sukzessive Annäherung mit einer Vektorfolge x₁, x₂, x₃, ... , die mit einem (beliebigen) Vektor  x₀ gestartet wird. Der Iterationsprozess wird abgebrochen, wenn ein iterierter Vektor x_i das Gleichungssystem in einem zu definierenden Sinne ausreichend gut erfüllt.

Einige Aussagen zu den Verfahren aus beiden Gruppen

• Die erforderlichen Rechenzeiten sind bei den direkten Verfahren exakt vorauszusagen, weil die Anzahl der Operationen bekannt ist (diese Aussage gilt grundsätzlich auch für dünn besetzte Matrizen, weil das Fill-in und damit die Anzahl der Operationen vorhergesagt werden können, auch wenn man in der Praxis in der Regel mit Schätzungen zufrieden ist).
  
  Bei den Iterationsverfahren sollte man unbedingt eine Begrenzung der Anzahl der Iterationsschritte vorsehen, weil schlechte oder fehlende Konvergenz zu beliebig großen Rechenzeiten führen kann.
   
• Bei sehr großen Gleichungssystemen mit dünn besetzter Koeffizientenmatrix ist das Fill-in (Erzeugen neuer Nicht-Null-Elemente) das entscheidende Kriterium für den Aufwand der direkten Verfahren. Eine Optimierung der Struktur der Koeffizientenmatrix ist bei großen Systemen unabdingbar.
  
   Im Gegensatz dazu arbeiten die iterativen Verfahren nach Algorithmen, die die Koeffizientenmatrix nicht verändern, sind also deutlich anspruchsloser hinsichtlich des Speicherbedarfs.
   
• Bei Gleichungssystemen mit mehreren rechten Seiten (z. B. bei mehreren Lastfällen eines mechanischen Systems) oder wiederkehrender Lösung mit geänderter rechter Seite bei unveränderter Koeffizientenmatrix (z. B. bei den inversen Iterationsverfahren zur Berechnung von Matrizeneigenwertproblemen) ist der Zusatzaufwand bei den direkten Verfahren gering.
  
  Bei den iterativen Verfahren fällt für jede neue rechte Seite der komplette Aufwand neu an.
   
• Das Erkennen von Singularität bzw. des Fehlens der Eigenschaft der positiven Definitheit der Koeffizientenmatrix (sehr wichtig für die Kontrolle, ob das Gleichungssystem ein sinnvolles Modell abbildet bzw. richtig aufgestellt wurde) bereitet den direkten Verfahren einige Schwierigkeiten (siehe z. B. "Schwieriges Problem: Singularität erkennen").
  
  Die iterativen Verfahren haben damit sogar erhebliche Schwierigkeiten, häufig reagieren sie nur mit Nicht-Konvergenz (siehe z. B. "Matlab: Probleme mit singulären Matrizen (2)").
   
• Die unvermeidlichen Rundungsfehler können wegen der gewaltigen Anzahl von Rechenoperationen bei der Lösung großer Gleichungssysteme ein erhebliches Problem darstellen, insbesondere bei den direkten Verfahren (siehe "Rundungsfehler, Kondition, Singularität, Skalierung"). Diese erzeugen ständig Zwischenergebnisse aus bereits mit Rundungsfehlern behafteten vorangegangenen Zwischenergebnissen (man denke nur an das Vorwärts- und Rückwärtseinsetzen, bei dem in jeden berechneten Wert des Lösungsvektors alle bis dahin berechneten Werte einfließen).
  
  Dieses Problem ist bei den iterativen Verfahren nicht annähernd so gravierend, denn die Koeffizientenmatrix bleibt unverändert, und die Fehler in einem iterierten Vektor bedeuten nur, dass es ein anderer Vektor ist als der, der sich ohne Rundungsfehler ergeben hätte (man kann nicht einmal sagen, ob besser oder schlechter).
   
• Bei großen Gleichungssystemen ist die Präkonditionierung dringend zu empfehlen. Bei Verwendung von direkten Verfahren ist im Allgemeinen (insbesondere bei positiv definiter Koeffizientenmatrix) eine Skalierung ausreichend.
  
  Bei der Verwendung von iterativen Verfahren ist häufig eine effektivere Präkonditionierung geboten (siehe "Präkonditionierung für iterative Verfahren" und "Vergleich Direktes Verfahren - Iterationsverfahren"), der dafür erforderliche und sinnvolle Aufwand kann kaum vorher bestimmt werden.

Versuch einer Wertung, subjektiv geprägte Empfehlung

Diese Überschrift ist so vorsichtig gewählt worden, weil die Frage "Direkte Verfahren oder Iterationsverfahren?" in der Vergangenheit unter den Numerikern manchmal durchaus die Form eines Glaubenskrieges annehmen konnte (wie die Frage nach der besten Programmiersprache unter den Informatikern oder die Frage nach dem besten CAD-System unter den Ingenieuren). Deshalb also die folgenden vorsichtigen Formulierungen:

• Die direkten Verfahren arbeiten stabiler als die Iterationsverfahren. Diese Aussage gilt für die Berechnung mit Computern, weil man davon ausgehen kann, dass diese keine Rechenfehler produzieren. Ein Rechenfehler wäre für das Ergebnis bei Verwendung eines direkten Verfahrens in der Regel katastrophal, die Iterationsverfahren würden sich nur mit verlängerter Rechenzeit rächen.
   

Natürlich sind die unvermeidlichen Rundungsfehler ganz enge Verwandte der Rechenfehler. Die Auswirkungen der Rundungsfehler können bei direkten Verfahren deutlich unangenehmer sein als bei den Iterationsverfahren.

• Für kleine Gleichungssysteme (und als klein darf man bei dieser Aussage auch noch Systeme mit 10000 Unbekannten bezeichnen) gibt es eigentlich keinen Grund, nicht mit direkten Verfahren zu arbeiten.
   
• Das übliche Abbruchkriterium für die iterativen Verfahren ist, dass eine Norm des Restvektors einen vorzugebenden Wert unterschreitet. Die Unsicherheiten bei der Festlegung dieses Wertes und die offene Frage, ob nicht einzelne (und vielleicht besonders interessierende) Unbekannte besonders große Abweichen haben, sollten nicht zu hoch bewertet werden. Die Abweichungen der berechneten Lösung von der exakten Lösung eines großen Gleichungssystems sind im Allgemeinen deutlich geringer als die Fehler, die bereits bei der Aufstellung des Gleichungssystems generiert werden (ungenaue Problemparameter, Näherungsverfahren - z. B. Finite-Elemente-Methode, Differenzenverfahren ... -, mit denen das Gleichungssystem erzeugt wurde).
   
• Während die Verfahrensauswahl für die direkten Verfahren nach Beantwortung der Fragen "Koeffizientenmatrix symmetrisch und positiv definit?" weitgehend klar ist (LR-Zerlegung oder Cholesky), steht bei den iterativen Verfahren ein kaum zu überblickendes Sortiment mit zahlreichen Modifikationen und verschiedenen Varianten zur Präkonditionierung zur Auswahl. Ohne tieferes Eindringen in die Theorie ist dem Anwender die Auswahl eines Verfahrens kaum möglich, selbst dann bleibt häufig nur der Test des Verfahrens am aktuellen Objekt.
  
  Die intensive Forschung auf dem Gebiet der iterativen Verfahren in den vergangenen Jahrzehnten hat zur erfolgreichen Lösung sehr großer dünn besetzter Gleichungssysteme geführt, die aus verschiedenen Anwendungsgebieten kommen. Eine Klassifizierung mit Wertung, nach der ein Anwender für sein Problem das geeignete Verfahren auswählen kann, ist offensichtlich außerordentlich schwierig. Der Schreiber dieser Zeilen hat in einschlägigen Lehrbüchern, im Internet und z. B. auch in Matlab stets nur eine (weitgehend unbewertete) Zusammenstellung der iterativen Verfahren (und natürlich zahllose Publikationen zu einzelnen Verfahren) gefunden und würde sich deshalb selbst folgenden Rat geben:
   
• Auch bei sehr großen linearen Gleichungssystemen sollte - wenn nicht bereits andere Erfahrungen vorliegen - stets zunächst der Versuch mit einem direkten Lösungsverfahren gestartet werden.

Homepage “Dankert/Dankert: Technische Mechanik”

Homepage “WWW - Ergänzung - Vertiefung - WWW”

D

nkert.de