www.wikidata.de-de.nina.az

BiCG Verfahren Das ist ein iteratives numerisches Verfahren zur approximativen Lösung eines linearen Gleichungssystems A

BiCG-Verfahren

Das BiCG-Verfahren ist ein iteratives numerisches Verfahren zur approximativen Lösung eines linearen Gleichungssystems , . Es wird eingesetzt, wenn die Matrix zu groß für die Verwendung von direkten Methoden ist. BiCG steht dabei für bikonjugierte Gradienten (im Englischen biconjugate gradients). Das Verfahren basiert auf der Dreitermrekursion des unsymmetrischen Lanczos-Verfahrens.

Das BiCG-Verfahren wurde 1974 durch Roger Fletcher eingeführt.

Der Algorithmus wird in der Praxis selten verwendet, da er ziemlich instabil und anfällig für Rundungsfehler ist. Er ist unbestritten theoretisch interessant, denn er stellt den Ausgangspunkt der Entwicklung der LTPM, der Lanczos-type product methods (Lanczos-artigen Produkt-Methoden) dar. Dazu zählen das (noch stärker instabile) CGS-Verfahren und als Versuch der Stabilisierung des CGS-Verfahrens das (ebenfalls ziemlich instabile) BiCGSTAB-Verfahren von Henk van der Vorst. Unter den Experten gibt es zwei Lager. Die einen glauben, dass eine bessere Fehleranalyse der Verfahren Gründe für die Instabilitäten aufzeigen würde und damit zumindest für Spezialfälle zu stabilen Verfahren führen würde, die anderen glauben, dass diese Verfahren niemals stabil sein können, und verwenden daher eher GMRES mit Verfeinerungen. Als Faustregel lässt sich festhalten: Anwender und kommerzielle Softwarepakete verwenden angepasste direkte Methoden, viele Forscher und Universitäten arbeiten mit den LTPM in allerlei Varianten.

Es hilft beim Verständnis des Algorithmus, von zwei zu lösenden Gleichungssystemen der Gestalt und auszugehen, wobei eine (im Allgemeinen nicht-hermitesche) quadratische Matrix und und gegebene rechte Seiten sind. Eigentlich ist man meist nur an der Lösung des ersten genannten Gleichungssystems interessiert. Gegeben seien ferner zwei Näherungslösungen und .

Das Verfahren kommt in vielen verschiedenen Varianten daher, namentlich genannt seien BiOres, BiOmin und BiOdir. Diese Varianten resultieren aus den unterschiedlichen Ansätzen für Krylow-Unterraum-Verfahren und sind mit den Varianten Ores, Omin und Odir des CG-Verfahrens verwandt. Die bekannteste Variante ist BiOmin und verwendet neben den rechten und linken Residuen und ein Paar bikonjugierte Richtungen und zur Residuenminimierung.

BiOmin (BiCG in der Orthomin-Variante) Bearbeiten

  1. Setze ,
  2. Setze ,
  3. for do
  12. end for

Dabei kann Zeile 6 entfallen, falls wir nur an der Lösung des ersten Gleichungssystems interessiert sind. Die Wahl des zweiten Gleichungssystems, i. e., die Wahl von ist nicht trivial und beeinflusst stark die Stabilität und das Konvergenzverhalten des Algorithmus.

Literatur Bearbeiten

  • Andreas Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg, Wiesbaden 2005, ISBN 3-528-13135-7
  • Yousef Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-89871-534-2
wikipedia, wiki, deutsches, deutschland, buch, bücher, bibliothek artikel lesen, herunterladen kostenlos kostenloser herunterladen, MP3, Video, MP4, 3GP, JPG, JPEG, GIF, PNG, Bild, Musik, Lied, Film, Buch, Spiel, Spiele
Veröffentlichungsdatum:
Das BiCG Verfahren ist ein iteratives numerisches Verfahren zur approximativen Losung eines linearen Gleichungssystems A x b displaystyle Ax b A R n n displaystyle A in mathbb R n times n Es wird eingesetzt wenn die Matrix zu gross fur die Verwendung von direkten Methoden ist BiCG steht dabei fur bikonjugierte Gradienten im Englischen biconjugate gradients Das Verfahren basiert auf der Dreitermrekursion des unsymmetrischen Lanczos Verfahrens Das BiCG Verfahren wurde 1974 durch Roger Fletcher eingefuhrt Der Algorithmus wird in der Praxis selten verwendet da er ziemlich instabil und anfallig fur Rundungsfehler ist Er ist unbestritten theoretisch interessant denn er stellt den Ausgangspunkt der Entwicklung der LTPM der Lanczos type product methods Lanczos artigen Produkt Methoden dar Dazu zahlen das noch starker instabile CGS Verfahren und als Versuch der Stabilisierung des CGS Verfahrens das ebenfalls ziemlich instabile BiCGSTAB Verfahren von Henk van der Vorst Unter den Experten gibt es zwei Lager Die einen glauben dass eine bessere Fehleranalyse der Verfahren Grunde fur die Instabilitaten aufzeigen wurde und damit zumindest fur Spezialfalle zu stabilen Verfahren fuhren wurde die anderen glauben dass diese Verfahren niemals stabil sein konnen und verwenden daher eher GMRES mit Verfeinerungen Als Faustregel lasst sich festhalten Anwender und kommerzielle Softwarepakete verwenden angepasste direkte Methoden viele Forscher und Universitaten arbeiten mit den LTPM in allerlei Varianten Es hilft beim Verstandnis des Algorithmus von zwei zu losenden Gleichungssystemen der Gestalt A x b displaystyle Ax b und A H x b displaystyle A H hat x hat b auszugehen wobei A C n n displaystyle A in mathbb C n times n eine im Allgemeinen nicht hermitesche quadratische Matrix und b C n displaystyle b in mathbb C n und b C n displaystyle hat b in mathbb C n gegebene rechte Seiten sind Eigentlich ist man meist nur an der Losung des ersten genannten Gleichungssystems interessiert Gegeben seien ferner zwei Naherungslosungen x 0 C n displaystyle x 0 in mathbb C n und x 0 C n displaystyle hat x 0 in mathbb C n Das Verfahren kommt in vielen verschiedenen Varianten daher namentlich genannt seien BiOres BiOmin und BiOdir Diese Varianten resultieren aus den unterschiedlichen Ansatzen fur Krylow Unterraum Verfahren und sind mit den Varianten Ores Omin und Odir des CG Verfahrens verwandt Die bekannteste Variante ist BiOmin und verwendet neben den rechten und linken Residuen r j displaystyle r j und r j displaystyle hat r j ein Paar bikonjugierte Richtungen p j displaystyle p j und p j displaystyle hat p j zur Residuenminimierung BiOmin BiCG in der Orthomin Variante BearbeitenSetze r 0 b A x 0 displaystyle r 0 leftarrow b Ax 0 nbsp p 0 r 0 displaystyle p 0 leftarrow r 0 nbsp Setze r 0 b A H x 0 displaystyle hat r 0 leftarrow hat b A H hat x 0 nbsp p 0 r 0 displaystyle hat p 0 leftarrow hat r 0 nbsp for k N displaystyle k in mathbb N nbsp do a k r k r k p k A p k displaystyle alpha k leftarrow langle hat r k r k rangle langle hat p k Ap k rangle nbsp x k 1 x k a k p k displaystyle x k 1 leftarrow x k alpha k p k nbsp x k 1 x k a k p k displaystyle hat x k 1 leftarrow hat x k overline alpha k hat p k nbsp r k 1 r k a k A p k displaystyle r k 1 leftarrow r k alpha k Ap k nbsp r k 1 r k a k A H p k displaystyle hat r k 1 leftarrow hat r k overline alpha k A H hat p k nbsp b k r k 1 r k 1 r k r k displaystyle beta k leftarrow langle hat r k 1 r k 1 rangle langle hat r k r k rangle nbsp p k 1 r k 1 b k p k displaystyle p k 1 leftarrow r k 1 beta k p k nbsp p k 1 r k 1 b k p k displaystyle hat p k 1 leftarrow hat r k 1 overline beta k hat p k nbsp end forDabei kann Zeile 6 entfallen falls wir nur an der Losung des ersten Gleichungssystems interessiert sind Die Wahl des zweiten Gleichungssystems i e die Wahl von b displaystyle hat b nbsp ist nicht trivial und beeinflusst stark die Stabilitat und das Konvergenzverhalten des Algorithmus Literatur BearbeitenAndreas Meister Numerik linearer Gleichungssysteme 2 Auflage Vieweg Wiesbaden 2005 ISBN 3 528 13135 7 Yousef Saad Iterative Methods for Sparse Linear Systems 2nd edition SIAM Society for Industrial amp Applied Mathematics 2003 ISBN 0 89871 534 2 Abgerufen von https de wikipedia org w index php title BiCG Verfahren amp oldid 225299120