CG-Verfahren

Konvergenzrate des CG-Verfahrens

Man kann zeigen, dass die Konvergenzgeschwindigkeit des CG-Algorithmus durch

beschrieben wird. Hierbei ist die Kondition der Matrix A, sowie die Energienorm von A. ist nicht negativ, da A symmetrisch und positiv definit ist. Ferner ist deswegen die Kondition

Aus der Minimierungseigenschaft lässt sich ferner herleiten, dass

wobei p_k (z) ein beliebiges Polynom vom Grad 1 ist mit p_k (0) = 1 und x^* die Lösung. Mit ist das Spektrum, also die Menge der Eigenwerte der Matrix A gemeint. Daraus folgt, dass CG ein System zu einer Matrix mit nur k Eigenwerten in k Schritten löst und dass CG für Systeme, bei denen die Eigenwerte in kleinen Umgebungen konzentriert sind, sehr schnell konvergiert. Dies wiederum liefert einen Anhaltspunkt für sinnvolle Vorkonditionierer: Ein Vorkonditionierer ist dann gut, wenn er dafür sorgt, dass die Eigenwerte konzentriert werden.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel CG-Verfahren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung