Iterative Lösung großer schwachbesetzter Gleichungssysteme

Frontmatter

Notationen

Zusammenfassung

Gleichungen im Unterkapitel x.y sind mit (x.y.1), (x.y.2) usw. durchnumeriert. Die Gleichung (3.2.1) wird im gleichen Unterkapitel 3.2 nur mit (1) zitiert, während sie in anderen Unterkapiteln des Hauptkapitels 3 als (2.1) bezeichnet wird.

Wolfgang Hackbusch

1. Einleitung

Zusammenfassung

Iterationsverfahren sind knapp 170 Jahre alt. Die erste Iterationsmethode für lineare Gleichungssysteme stammt von Carl Friedrich Gauß. Seine Methode der «kleinsten Fehlerquadrate» führte ihn auf Gleichungssysteme, die zu groß waren, als daß er sie mit der direkten Methode der Gauß-Elimination bequem berechnen konnte. Das in seinem “Supplementum theoriae combinationis observationum erroribus minime obnoxiae” (1819–1822) beschriebene Iterationsverfahren ist eine Variante des Gauß-Seidel-Verfahrens. Welchen Wert Gauß seinem Iterationsverfahren zumaß, kann man seinem Brief von 1823 entnehmen, der im Auszug dem Vorwort vorangestellt ist.

Wolfgang Hackbusch

2. Grundlagen aus der Linearen Algebra

Zusammenfassung

Gemäß Bemerkung 1.2.1 werden die Indizes der Vektoren zunächst als nicht angeordnet angesehen. Die stets endliche Indexmenge wird mit I bezeichnet. Ein Vektor b ∈ ℝ ^I bzw. b ∈ ℂ^I ist eine Abbildung b: I → K mit K = ℝ im reellen und K = ℂ im komplexen Falle. Der Wert von b für α ∈ I wird als Vektorkomponente b _α geschrieben. Ein aus seinen Komponenten b _α zusammengesetzter Vektor wird in der Form

$$ b = {({b_\alpha })_{\alpha \in I}}$$

dargestellt. Ist die Indexmenge I angeordnet, so werden die Indizes mit 1, 2 , ... , n := ::I (Elementeanzahl von I) identifiziert, wenn nicht explizit anders angegeben. Die Indizes werden dann im allgemeinen mit i, j, k,... statt α, β, γ,... bezeichnet.

Wolfgang Hackbusch

3. Allgemeines zu iterativen Verfahren

Zusammenfassung

In diesem Kapitel werden allgemeine Eigenschaften iterativer Verfahren untersucht. Dazu gehört die Konsistenz, die den Zusammenhang zwischen dem Iterationsverfahren und dem vorgelegten Gleichungssystem schafft, sowie die Konvergenz, die den Erfolg der Iteration garantieren soll. Das wesentliches Ergebnis dieses Abschnittes ist die Charakterisierung der Konvergenz linearer Iterationsverfahren durch den Spektralradius der Iterationsmatrix in §3.1.3. Da nur iterative Verfahren für Gleichungssysteme mit regulärer Matrix untersucht werden, wird nicht auf Iterationsverfahren für singuläre Systeme oder Systeme mit Rechtecksmatrizen eingegangen. Hierzu findet man Hinweise bei Maeß [2], Marek [ 1], KosmolZhou [1].

Wolfgang Hackbusch

4. Jacobi-, Gauß-Seidel- und SOR-Verfahren im positiv definiten Fall

Zusammenfassung

Die Verfahren von Jacobi, Gauß-Seidel und die SOR-Methode hängen eng zusammen und werden deshalb gemeinsam analysiert. Allerdings unterscheidet sich die Analyse bei positiv definiter Matrix A wesentlich von anderen Fällen, die den §§S–6 vorbehalten sind. Daß der positiv definite Fall von praktischem Interesse ist, belegt der Abschnitt 4.1: Die Poisson-Modellmatrix ist positiv definit. Das Kapitel 4.2 ist eine Rekapitulation und Verallgemeinerung der aus §1.4 schon bekannten Algorithmen. §4.3 und §4.6 enthalten einfache Modifikationen dieser Iterationen. Konvergenzresultate qualitativer und quantitativer Art finden sich in §4.4. Abschnitt 4.8 ist den symmetrischen Iterationen, insbesondere dem SSOR-Verfahren gewidmet.

Wolfgang Hackbusch

5. Analyse im 2-zyklischen Fall

Zusammenfassung

Ziel dieses Kapitels sind quantitative Konvergenz aussagen für die klassischen Verfahren (Jacobi-, Gauß-Seidel-, SOR-Iteration).

Wolfgang Hackbusch

6. Analyse für M-Matrizen

Zusammenfassung

Die Positivdefinitheit A > 0 definiert eine partielle Ordnungsrelation auf der Algebra der Hermiteschen Matrizen.

Wolfgang Hackbusch

7. Semiiterative Verfahren

Zusammenfassung

Gegeben sei eine lineare, konsistente, aber nicht notwendigerweise konvergente Iteration Φ (im folgenden auch Basisiteration genannt) mit einer Iterationsmatrix M. Zu einem Startwert x⁰ seien die Iterierten

$$ {x^{m + 1}} = M{x^m} + Nb = \Phi ({x^m},b)$$

(7.1.1)

berechnet. Das Resultat der Iteration Φ war bisher die zuletzt berechnete Iterierte x ^m. Die zuvor berechneten x^j (0 ≤ j ≤m-1) wurden «vergessen».

Wolfgang Hackbusch

8. Transformationen, sekundäre Iterationen, unvollständige Dreieckszerlegungen

Zusammenfassung

Um die Vielfalt der heute angewandten iterativen Verfahren beschreiben zu können, braucht man weitere Techniken, die zum Teil aus schon bekannten Verfahren neue produzieren und zum anderen Teil neue Elemente einführen. Zu der ersten Art gehören die Transformationen, die in §§8.1–3 beschrieben werden, und die mit einer sekundären Iteration erzeugten zusammengesetzten Verfahren aus §8.4, während die ILU-Zerlegung aus §8.5 ein neues Verfahren produziert.

Wolfgang Hackbusch

9. Verfahren der konjugierten Gradienten

Zusammenfassung

Im folgenden seien A ∈ ℝ ^{I × I} und b ∈ ℝ ^I reell.

Wolfgang Hackbusch

10. Mehrgitteriterationen

Zusammenfassung

Mehrgitterverfahren gehören zu den schnellsten Iterationen, da ihre Konvergenzrate von der Schrittweite h unabhängig ist. Zudem benötigt man keine einschränkenden Symmetrie- bzw. Positivitätsbedingungen wie für die cg-Verfahren.

Wolfgang Hackbusch

11. Gebietszerlegungsmethoden

Zusammenfassung

Verschiedene iterative Methoden lassen sich zusammenfassen zu der Klasse der Gebietszerlegungsmethoden (engl.: domain decomposition methods). Obwohl ein Prototyp dieser Iteration von H. A. Schwarz (Viertelsjahresschrift der Naturforschenden Gesellschaft in Zürich, Bd. 15, 1870) schon 120 Jahre alt ist, erlangte diese Verfahrensklasse erst vor relativ kurzer Zeit das volle Interesse der Anwender.

Wolfgang Hackbusch

Backmatter