On the optimality of Krylov information (Q580896)

Betrachtet wird die iterative Lösung eines linearen Gleichungssystems \(Ax=b\) mit \(\| b\| =1\) und die Berechnung einer \(\epsilon\)- Näherung \(\bar x\) mit \(\| A\bar x-b\| \leq \epsilon\). Dazu wird allgemein ein Informationsoperator \(I_ k(A,b)=[b,Az_ 1,Az_ 2,...,Az_ k]\) definiert, wobei \(z_{k+1}\) von der vorhergehenden Information abhängt, mit dessen Hilfe der iterierte Vektor \(x_ k=\Phi_ k(I_ k(A,b))\) erzeugt wird. Ein Algorithmus \(\Phi\) heißt optimal, falls er eine \(\epsilon\)-Approximation \(x_ k\) mit einem Minimum an Iterationsschritten für alle Matrizen A aus einer bestimmten Klasse liefert. Es wird gezeigt, daß die Krylov-Information mit \(z_ i=A^{i-1}b\) fast optimal ist in der Menge der genannten Informationsoperatoren für beliebige orthogonal invariante Matrizenklassen. Daraus folgen Aussagen über die \(\epsilon\)- Komplexität eines Algorithmus. Die Resultate lassen sich auf die Eigenwertaufgabe \(Ax=\lambda x\) sinngemäß übertragen, indem der verallgemeinerte Algorithmus der minimalen Residuen fast optimal ist für die Krylov-Information in der Klasse der orthogonal invarianten Matrizen.