Iterative Lösung Großer Schwachbesetzter Gleichungssysteme

ISBN-13: 9783519123729 / Niemiecki / Miękka / 1993 / 404 str.

Wolfgang Hackbusch; Wolfgang Hackbusch

Opis

Das Buch entstand aus einem Vorlesungsmanuskript, das der Autor an der Christian-Albrechts-Universitat zu Kiel fUr Studenten der Mathematik gelesen hat. Es versucht, den heutigen Stand der iterativen und damit verwandten Verfahren zu beschreiben, ohne allerdings auf zu spezielle Gebiete einzugehen. Mit der Beschrankung auf iterative Ver fahren ist bereits ein Auswahl getroffen: Verschiedene schnelle, direkte Verfahren fur spezielle Aufgaben wie auch optimierte Versionen der Gaussschen Eliminationsmethode bzw. des Cholesky-Verfahrens oder die Bandbreitenreduktion werden nicht berUcksichtigt. Obwohl das besondere Interesse den modernen, effektiven Verfahren (konjugierte Gradienten, Mehrgitterverfahren) gilt, wird auch Wert auf die Theorie der klassischen Iterationsverfahren gelegt. Andererseits werden einige effektive Algorithmen nicht oder nur am Rande berUck sichtigt, wenn sie zu eng mit Diskretisierungstechniken verknUpft sind. Die iterative Behandlung nichtlinearer Problemen oder Eigenwertauf gaben bleibt vollig unerwahnt. Ein Kapitel Uber die in vielen Bereichen auftretenden Sattelpunktprobleme (spezielle indefinite Aufgaben) wurde aus GrUnden des Buchumfanges nicht verwirklicht. Das Buch setzt keine speziellen Kenntnisse voraus, die Uber die Anfangsvorlesungen Analysis und Lineare Algebra hinausgingen. Die aus der Linearen Algebra benotigten Grundlagen sind noch einmal in Kapitel 2 dieses Buches zusammengestellt. Damit soll zum einen eine geschlossene Darstellung ermoglicht werden, zum anderen ist es notwendig, die aus der Linearen Algebra bekannten Satze in die hier benotigte Formulierung zu bringen. Vom Umfang her eignet sich eine Auswahl des vorliegenden Stoffes fUr eine 4-stUndige Vorlesung nach dem Vordiplom. Eine Teilauswahl ist auch fUr die Vorlesung Numerische Mathemati 11 empfehlenswert

Spis treści

Notationen.- 1 Einleitung.- 1.1 Historische Bemerkungen zu Iterationsverfahren.- 1.2 Das Modellproblem (Poisson-Gleichune).- 1.3 Aufwand ft direkte Lösung des Gleichungssystems.- 1.4 Beispiele für iterative Verfahren.- 2 Grundlagen aus der Linearen Algebra.- 2.1 Bezeichnungen für Vektoren und Matrizen.- 2.1.1 Nichtangeordnete Indexmenge.- 2.1.2 Bezeichnungen und Notationen.- 2.1.3 Sternnotation.- 2.2 Lineare Gleichungssysteme.- 2.3 Permutationsmatrizen.- 2.4 Eigenwerte und Eigenvektoren.- 2.5 Blockvektoren, Blockmatrizen.- 2.6 Normen.- 2.6.1 Vektornormen.- 2.6.2 Äquivalenz aller Normen.- 2.6.3 Zugeordnete Matrixnormen.- 2.7 Skalarprodukt.- 2.8 Normalformen.- 2.8.1 Schur-Normalform.- 2.8.2 Jordan-Normalform.- 2.8.3 Diagonalisierbarkeit.- 2.9 Zusammenhang zwischen Normen und Spektralradius.- 2.9.1 Zugeordnete Matrixnormen als obere Eigenwertschranken.- 2.9.2 Die Spektralnorm.- 2.9.3 Den Spektralradius approximierende Matrixnormen.- 2.9.4 Die geometrische Reihe (Neumannsche Reihe) für Matrizen.- 2.9.5 Der numerische Radius einer Matrix.- 2.10 Positiv definite Matrizen.- 2.10.1 Definitionen und Bezeichnungen.- 2.10.2 Rechenregeln und Kriterien frnnitiv definite Matriten.- 2.10.3 Folgerungen für positiv definite Matrizen.- 3 Allgemeines zu iterativen Verfahren.- 3.1 Allgemeine Aussagen zur Konvergenz.- 3.1.1 Bezeichnuneen.- 3.1.2 Fixpunkte.- 3.1.3 Konsistenz.- 3.1.4 Konvergenz.- 3.1.5 Konvergenz und Konsistenz.- 3.2 Lineare Iterationsverfahren.- 3.2.1 Bezeichnungen, erste Normalform.- 3.2.2 Konsistenz zweite und dritte Normalform.- 3.2.3 Darstellung der Iterierten xm.- 3.2.4 Konvergenz.- 3.2.5 Konvergenzgeschwindigkeit.- 3.2.6 Bemerkungen zu den Normalformmatrizen M, N und W.- 3.2.7 Produktiterationen.- 3.2.8 Drei-Term-Rekursionen (Zweischrittiterationen).- 3.3 Effektivität von Iterationsverfahren.- 3.3.1 Rechenaufwand.- 3.3.2 Effektivität.- 3.3.3 Ordnung der linearen Konvergenz.- 3.4 Test iterativer Verfahren.- 3.5 Erläuterungen zu den Pascal-Prozeduren.- 3.5.1 Zu Pascal.- 3.5.2 Zu den Testbeispielen.- 3.5.3 Konstanten und Typen.- 3.5.4 Format der Iterationsprozeduren.- 3.5.5 Testumgebung.- 4 Jacobi-, Gauß-Seidel- und SOR-Verfahren im positiv definiten Fall.- 4.1 Eigenwertanalyse des Modellproblems.- 4.2 Konstruktion der Iterationsverfahren.- 4.2.1 Jacobi-Iteration.- 4.2.1.1 Die additive Aufspaltung der Matrix A.- 4.2.1.2 Definition des Jacobi-Verfahrens.- 4.2.1.3 Pascal-Prozedur.- 4.2.2 Gauß-Seidel-Verfahren.- 4.2.2.1 Definition.- 4.2.2.2 Pascal-Prozedur.- 4.3 Gedämpfte bzw extrapolierte Iterationsverfahren.- 4.3.1 Gedämpftes Jacobi-Verfahren 82 4.3.1.1 Definition.- 4.3.1.2 Pascal-Prozeduren.- 4.3.2 Richardson-Iteration.- 4.3.2.1 Definition.- 4.3.2.2 Pascal-Prozeduren.- 4.3.3 SOR-Verfahren.- 4.3.3.1 Definition.- 4.3.3.2 Pascal-Prozeduren.- 4.4 Konvergenzuntersuchung.- 4.4.1 Richardson-Iteration.- 4.4.2 Jacobi-Iteration.- 4.4.3 Gauß-Seidel- und SOR-Verfahren.- 4.5 Blockversionen.- 4.5.1 Block-Jacobi-Verfahren.- 4.5.1.1 Definition 1n.- 4.5.1.2 Pascal-Prozeduren.- 4.5.2 Block-Gauß-Seidel und Block-SOR-Verfahren.- 4.5.2.1 Definition.- 4.5.2.2 Pascal-Prozeduren.- 4.5.3 Konvergenz der Blockvarianten.- 4.6 Aufwand der Verfahren.- 4.6.1 Der Fall allgemeiner, schwachbesetzter Matrizen.- 4.6.2 Aufwand im Modellfall.- 4.7 Konvergenzraten im Falle des Modellproblems.- 4.7.1 Richardson- und Jacobi-Iteration.- 4.7.2 Block-Jacobi-Iteration.- 4.7.3 Numerische Beispiele zu den Jacobi-Varianten.- 4.7.4 SOR und Block-SOR-Iteration mit numerischen Beispielen.- 4.8 Symmetrische Verfahren.- 4.8.1 Allgemeine Form der symmetrischen Iteration.- 4.8.2 Konvergenz.- 4.8.3 Symmetrisches Gauß-Seidel-Verfahren.- 4.8.4 Adjungierte und zugehörige symmetrische Iterationen.- 4.8.5 SSR: Symmetrisches SO.- 4.8.6 Pascal-Prozeduren und numerische Resultate zu SSOR.- 5. Analyse im 2-zyklischen Fall.- 5.1 Die 2-zyklischen Matrizen.- 5.2 Vorbereitende Lemmata.- 5.3 Analyse der Richardson-Iteration.- 5.4 Analyse des Jacobi-Verfahrens.- 5.5 Analyse der Gauß-Seidel-Iteration.- 5.6 Analyse des SOR-Verfahrens.- 5.6.1 Konsistent eor dl p t e Matrizen.- 5.6.2 Satz von Young.- 5.6.3 Ordnungsverbesserung durch SOR.- 5.6.4 Praktische Handhabung des SOR-Verfahrens.- 5.7 Anwendung auf das Modellproblem.- 5.7.1 Analyse im Modellfall.- 5.7.2 Gauß-Seidel-Iteration: numerische Beispiele.- 5.7.3 SOR-Iteration: numerische Beispiele.- 5.8 Ergänzungen.- 5.8.1 p-zyklische Matrizen.- 5.8.2 Modifiziertes SOR.- 5.8.3 SSOR im 2-zyklischen Fall.- 5.8.4 Unsymmetrisches SOR-Verfahren.- 6 Analyse für M-Matrizen.- 6.1 Positive Matrizen.- 6.2 Graph einer Matrix und irreduzible Matrizen.- 6.3 Perron-Frobenius-Theorie positiver Matrizen.- 6.4 M-Matrizen.- 6.4.1 Definition.- 6.4.2 Zusammenhang zwischen M-Matrizen und Jacobi-Iteration.- 6.4.3 Diagonaldominanz.- 6.4.4 Weitere Kriterien.- 6.5 Reguläre Aufspaltuneen.- 6.6 Anwendungen.- 7 Semiiterative Verfahren.- 7.1 Erste Formulierung.- 7.1.1 Allgemeines.- 7.1.2 Konsistenz asymptotische Konvergenzrate.- 7.1.3 Fehlerdarstellung.- 7.2 Zweite Formulierung semiiterativer Verfahren.- 7.2.1 Allgemeine Darstellung.- 7.2.2 Pascal-Realisierung der zweiten Formulierung.- 7.2.3 Dreitermrekursion.- 7.3 Ontinale Pn1vnnn.- 7.3.1 Aufgabenstellung.- 7.3.2 Distssion der zweiten Minimierungsaufgabe.- 7.3.3 ebyšëv-Polynome.- 7.3.4 Die ?ebyšëv-Methode.- 7.3.5 Konvergenzordnungsverbesserung durch ? ebyšëv-Methode.- 7.3.6 Optimierung über andere Mengen.- 7.3.7 Die zyklische Iteration.- 7.3.8 Eine Umformulierung.- 7.3.9 Mehrschrittiterationen.- 7.3.10 Pascal-Prozeduren.- 7.3.11 Aufwand der semiiterativen Methode.- 7.4 Anwendung auf bekannte Iterationen.- 7.4.1 Vorbemerkungen.- 7.4.2 Das semiiterative Richardson-Verfahren.- 7.4.3 Das semiiterative Jacobi- und Block-Jacobi-Verfahren.- 7.4.4 Das semiiterative SSOR- und Block-SSOR-Verfahren.- 7.5 Verfahren der alternierenden Richtungen (ADI).- 7.5.1 Erklärung am Modellproblem.- 7.5.2 Allgemeine Darstellung.- 7.5.3 ADf im kommutativen Fall.- 7.5.4 Die ADI-Methode und semiiterative Verfahren.- 7.5.5 Pascal-Prozeduren.- 7.5.6 Aufwandsüberlegungen und numerische Beispiele.- 8 Transformationen, sekundäre Iterationen, unvollständige Dreieckszerlegungen.- 8.1 Erzeugung von Iterationen durch Transformatinnen.- 8.1.1 Bisherige Techniken zur Iterationserzeugung.- 8.1.2 Die Linkstransformation.- 8.1.3 Die Rechtstransformation.- 8.1.4 Die beidseitige Transformation.- 8.2 Die Kaczmarz-Iteration.- 8.2.1 Ursprüngliche Formulierung.- 8.2.2 Interpretation als Gauß-Seidel-Verfahren.- 8.2.3 Pascal-Prozeduren und numerische Beispiele.- 8.3 Präkonditionierung.- 8.3.1 Zur Begriffsbildung.- 8.3.2 Beispiele.- 8.3.3 Rechenregeln für Konditionszahlen.- 8.4 Sekundäre Iterationen.- 8.4.1 Beispiele füir sekundäre Iterationen.- 8.4.2 Konvergenzanalyse im allgemeinen Fall.- 8.4.3 Analyse im symmetrischen Fall.- 8.4.4 Abschätzune des Aufwandes 21S.- 8.4.5 Pascal-Prozeduren.- 8.4.6 Numerische Beispiele.- 8.5 Unvollständige Dreieckszerlegungen.- 8.5.1 Einführung, ILU-Iteration.- 8.5.2 Unvollständige Zerlegung beziglich eines Sternmusters.- 8.5.3 Anwendung auf allgemeine Fünfpunktformeln.- 8.5.4 Modifiziere ILU-Zerlegungen.- 8.5.5 Zur Existenz und Stabilität der ILU-Zerlegung.- 8.5.6 Eigenschaften der ILU-Zerlegung.- 8.5.7 ILU-Zerlegung zuanderen Muschte.- 8.5.8 Approximative ILU-Zerlegungen.- 8.5.9 Blockweise ILU-Zerlegungen.- 8.5.10 Pascal-Prozeduren.- 8.5.11 Numerische Beispiele.- 8.5.12 Anmerkungen.- 8.6 Ein überflüssiger Begriff: Zeitschrittverfahren.- 9 Verfahren der konjugierten Gradienten.- 9.1 Lineare Gleichungssysteme als Minimierungsaufgabe.- 9.1.1 Minimierungsaufgabe.- 9.1.2 Suchrichtungen.- 9.1.3 Andere quadratische Funktionale.- 9.1.4 Der komplexe Fall.- 9.2 Gradientenverfahren.- 9.2.1 Konstruktion.- 9.2.2 Eigenschaften des Gradientenverfahrens.- 9.2.3 Numerische Beispiele.- 9.2.4 Gradientenverfahren basierend auf anderen Iterationen.- 9.2.5 Pascal-Prozeduren und numerische Beisniele.- 9.3 Methode der konjugierten Richtungen.- 9.3.1 Optimalität beziglich einer Richtung.- 9.3.2 Konjugierte Richtungen.- 9.4 Methode der konjugierten Gradienten.- 9.4.1 Erste Formulierung.- 9.4.2 Das cg-Verfahren (angewandt auf die Richardson-Iteration).- 9.4.3 Konvergenzanalyse.- 9.4.4 Die cg-Methode angewandt auf symmetrische Iterationen.- 9.4.5 Pascal-Prozeduren.- 9.4.6 Numerische Beispiele im Modellfall.- 9.4.7 Aufwand der cg-Methode.- 9.4.8 Eignung fir sekundäre Iterationen.- 9.5 Verallgemeinerungen.- 9.5.1 Formulierung mit allgemeinerer Bilinearform.- 9.5.2 Das Verfahren der konjugierten Residuen.- 9.5.3 Dreitermrekursion für Dm.- 9.5.4 Stabilisiertes Verfahren der konjugierten Residuen.- 9.5.5 Konvergenzresultate fir indefinite Matrizen A.- 9.5.6 Pascal-Prozeduren.- 9.5.7 Numerische Beispiele.- 9.5.8 Das Verfahren der orthogonalen Richtungen.- 9.5.9 Lösung unsymmetrischer Systeme.- 9.5.10 Weitere Anmerkungen.- 10 Mehrgitteriterationen.- 10.1 Einfihrung.- 10.1.1 Glättung.- 10.1.2 Hierarcie der Gleichungssysteme.- 10.1.3 Prolongation.- 10.1.4 Restriktion.- 10.1.5 Grobgitterkorrektur.- 10.2 Das Zweigitterverfahren.- 10.2.1 Algorithmus.- 10.2.2 Modifikationen.- 10.2.3 Iterationsmatrix.- 10.2.4 Pascal-Prozeduren.- 10.2.5 Numerische Beispiele.- 10.3 Analyse für ein eindimensionales Beispiel.- 10.3.1 Fourier-Analyse.- 10.3.2 Transformierte Größen.- 10.3.3 Konvergenzresultate.- 10.4 Mehrgitteriteration.- 10.4.1 Algorithmus.- 10.4.2 Pascal-Prozeduren.- 10.4.3 Niimerishe Resnltate.- 10.4.4 Rechenaufwand.- 10.4.5 Iterationsmatrix.- 10.5 Geschachtelte Iteration.- 10.5.1 Algorithmus.- 10.5.2 Genauigkeitsanalyse.- 10.5.3 Rechenaufwand.- 10.5.4 Pascal-Prozeduren.- 10.5.5 Numerische Resultate.- 10.5.6 Anmerkungen.- 10.6 Konvergenzanalyse.- 10.6.1 bersicht.- 10.6.2 Glättungseigenschaft.- 10.6.3 Approximationseigenschaft.- 10.6.3.1 Formulierung.- 10.6.3.2 Die Galerkin-Diskretisierung.- 10.6.3.3 Hierarchie der Gleichungssysteme.- 10.6.3.4 Kanonische Prolongation und Restriktion.- 10.6.3.5 Fehlerabschätzung der Galerkin-Lösung.- 10.6.3.6 Beweis der Approximationseigenschaft.- 10.6.4 Konvergenz der Zweigitteriteration.- 10.6.5 Konvergenz der Mehrgitteriteration.- 10.6.6 Der schwächer reeuläre Fall.- 10.7 Symmetrische Mehrgitterverfahren.- 10.7.1 Der symmetrische Mehrgitteralgorithmus.- 10.7.2 Zweigitterkonvergenzaussagen für v1 > 0, v2 > 0.- 10.7.3 Glättungseigensciaft im symmetrischen Fall.- 10.7.4 Verschärfte Zweigitterkonvergenzaussagen.- 10.7.5 V-Zykluskonvergenz.- 10.7.6 Mehrgitterkonvergenz für alle v2 > 0.- 10.8 Kombination von Mehrgitter- mit semiiterativen Verfahren.- 10.8.1 Semiiterative Glätter.- 10.8.2 Gedämpfte Grobgitterkorrekturen.- 10.8.3 Mehrgitteriteraton als Basis des cg-Verfahrens.- 10.9 Anmerkungen.- 10.9.1 Mehrgitterverfahren zweiter Art.- 10.9.2 Zur Geschichte der Mehrgitterverfahren.- 10.9.3 Robuste Methoden.- 10.9.4 Filternde Zerlegungen.- 11 Gebietszerlegungsmethoden.- 11.1 Allgemeines.- 11.2 Formulierung der Gebietszerlegungsmethode.- 11.2.1 Allgemeine Konstruktion.- 11.2.2 Zu den Prolongationen.- 11.2.3 Multiplikative und additive Schwarz-Iteration.- 11.2.4 Interpretation als Gauß-Seidel- bzw Jacobi-Iteration.- 11.2.5 Die klassische Schwarz-Iteration.- 11.2.6 Genäherte Lösung der Teilprobleme.- 11.2.7 Verschärfte Abscätzung A ? ?W.- 11.3 Eigenschaften der additiven Schwarz-Iteration.- 11.3.1 Parallelität.- 11.3.2 Konditionsabschätzungen.- 11.3.3 Konvergenzaussagen.- 11.4 Analyse der multiplikativen Schwarz-Iteration.- 11.4.1 Konvergenzaussagen.- 11.4.2 Beweis der Konvergenzsätze.- 11.5 Beispiele.- 11.5.1 Schwan-Verfahren mit echter Gebietszerlegung.- 11.5.2 Additive Schwarz-Iteration mit Grobgitterkorrektur.- 11.5.3 Formulierung im Fall einer Galerkin-Diskretisierung.- 11.6 Mehrgitterverfahren als Unterraumzerlegung.- 11.6.1 Eine spezielle Zweigittermethode.- 11.6.2 Der V-Zyklus als multiplikative Schwarz-Iteration.- 11.6.3 Beweis der V-Zyklus-Konvergenz.- 11.6.4 Methode der hierarchischen s is.- 11.6.5 Mehrstufige Schwarz-Iteration.- 11.6.6 Weitere Aisätze für Zerlegungen in Unterräume.- 11.6.7 Indefinite und unsymmetrische Systeme.- 11.7 Schur-Komplement-Methoden.- 11.7.1 Nichtüiberlappende Gebietszerlegung mit innerem Rand.- 11.7.2 Direkte Lö sung.- 11.7.3 Die Kapazitätsmatrixmethode.- 11.7.4 Gebietszerlegung mit nichtüberlappenden Gebieten.- 11.7.5 Mehrgitterähnliche Gebietszerlegungsmethoden.- 11.7.6 Weitere Anmerkungen.- Stichwortverzeichnis.- Verzeichnis der Pascal-Namen.