imported>Aka: Tippfehler entfernt, ISBN-Format, Kleinkram

2024-05-13T15:17:59Z

Tippfehler entfernt, ISBN-Format, Kleinkram

Neue Seite

Das '''CGS-Verfahren''' ist ein [[Iteratives Verfahren|iteratives]] [[Numerische Mathematik|numerisches Verfahren]] zur [[Approximation|approximativen]] Lösung großer, [[Dünnbesetzte Matrix|dünnbesetzter]] [[lineares Gleichungssystem|linearer Gleichungssysteme]] <math>Ax=b</math> mit einer reellen <math>n \times n</math> Matrix ''A''. CGS ist aus der Klasse der [[Krylow-Unterraum-Verfahren]] und ist insbesondere auch für nichtsymmetrische Matrizen geeignet. Es wird eingesetzt, wenn die [[Matrix (Mathematik)|Matrix]] zu groß für die Verwendung von direkten Methoden ist und nicht auf die [[Transponierte]] der Systemmatrix zugegriffen werden kann.

CGS steht für ''conjugate gradient squared'', auf Deutsch ''quadrierte konjugierte Gradienten'' und wird aus dem [[BiCG-Verfahren]] hergeleitet. Ausgehend von der Darstellung der Residuen <math>r_j</math> und Suchrichtungen <math>p_j</math> im BiCG-Verfahren mittels Polynomen lassen sich neuartige Residuen als Quadrate der Polynome angewendet auf das Startresiduum definieren, wobei die benötigten Skalare <math>\alpha_j</math> und <math>\beta_j</math> aus dem BiCG-Verfahren sich durch einen Trick aus den neu konstruierten Vektoren berechnen lassen, ohne den im BiCG-Verfahren benötigten zweiten [[Krylowraum]] aufzubauen.

Die Anwendung der quadrierten Residuenpolynome kann in den Fällen, in denen das BiCG-Verfahren rasch konvergiert, zu einer noch rascheren Konvergenz führen. Wenn das BiCG-Verfahren langsam konvergiert, so hat das CGS-Verfahren meist noch stärkere Probleme. Ebenso wie Bi-CG weist das CGS-Verfahren keinen monotonen Residuenverlauf auf und bricht in manchen Fällen vorzeitig ab.

Das CGS-Verfahren wurde 1984 von [[Peter Sonneveld]] entwickelt und 1989 veröffentlicht. Es basiert auf den Ideen des [[IDR-Verfahren]]s, welches einige Jahre vorher von ihm entwickelt wurde.

== Literatur ==
* Sonneveld: ''CGS: A fast Lanczos-Type Solver for Nonsymmetric Linear Systems.'' SIAM J. Sci. Stat. Comput., 10(1):36-52, 1989
* A. Meister: ''Numerik linearer Gleichungssysteme.'' 2. Auflage, Vieweg 2005, ISBN 3-528-13135-7

{{DEFAULTSORT:Cgsverfahren}}
[[Kategorie:Numerische lineare Algebra]]

CGS-Verfahren - Versionsgeschichte

imported>Aka: Tippfehler entfernt, ISBN-Format, Kleinkram