×

zbMATH — the first resource for mathematics

Necessary and sufficient conditions for the existence of a conjugate gradient method. (English) Zbl 0546.65010
Untersucht wird die Klasse von Matrizen A, für welche eine s-gliedrige Methode der konjugierten Gradienten zur Lösung von \(Ax=b\) existiert. Dabei soll in jedem Schritt bezüglich eines Krylov-Raumes die Norm des Fehlervektors minimiert werden. Für symmetrische und positiv definite Matrizen existiert bekanntlich eine dreigliedrige Rekursionsformel zur Berechnung der Basisvektoren im Krylovraum. Die Klasse CG(s) von Matrizen, für welche zu jedem Startvektor eine s-gliedrige Rekursionsformel existiert, wird durch notwendige und hinreichende Bedingungen charakterisiert. Das Hauptresultat besagt, daß \(A\in CG(s)\) genau dann gilt, falls entweder der Grad des Minimalpolynoms von A kleiner oder gleich s ist oder A normal ist und der kleinstmögliche Grad des Polynoms q, für welches \(q(A)=A^*\) gilt, nicht größer als s-2 ist. Dadurch werden diejenigen Matrizen charakterisiert, für die solche Methoden bereits bekannt sind.
Reviewer: H.R.Schwarz

MSC:
65F10 Iterative numerical methods for linear systems
PDF BibTeX XML Cite
Full Text: DOI