Krylowraum

Ein Krylowraum ist ein Untervektorraum des komplexen Spaltenvektorraums ${\displaystyle \mathbb {C} ^{n}}$, der zu einer quadratischen Matrix ${\displaystyle A\in \mathbb {C} ^{n\times n}}$, einem Spaltenvektor ${\displaystyle q\in \mathbb {C} ^{n}}$, dem Startvektor der Krylow-Sequenz und einem Index m als lineare Hülle iterierter Matrix-Vektor-Produkte definiert ist:

${\displaystyle {\mathcal {K}}={\mathcal {K}}(A,q)={\mathcal {K}}_{m}(A,q)={\mbox{span}}\{q,Aq,\ldots ,A^{m-1}q\}.}$

Dimension des Krylowraumes

Die Dimension des Krylowraumes ${\displaystyle {\mathcal {K}}_{m}(A,q)}$ ist einerseits beschränkt durch die Anzahl m der erzeugenden Elemente, andererseits durch die Dimension n des umgebenden Spaltenvektorraums. Es gibt somit einen maximalen Index ${\displaystyle m\leq n}$, bis zu dem die Dimension des Krylowraumes mit seinem Index übereinstimmt. Dies bedeutet, dass der Vektor ${\displaystyle A^{m}q}$ von den vorhergehenden Erzeugenden linear abhängig wird. Daraus folgt, dass auch alle nachfolgenden Erzeugenden ${\displaystyle A^{m+k}q}$ von den ersten m linear abhängig sind, d. h. die Folge der Dimensionen der Krylowräume bleibt ab m konstant.

Den minimalen Index ${\displaystyle m}$, für den der Raum nicht mehr erweitert wird, nennt man den Grad von ${\displaystyle q}$ in ${\displaystyle A}$. An diesem Punkt brechen die meisten Krylowraum-Verfahren mit der exakt berechneten Lösung ab. Wie man am Beispiel eines Eigenvektors von ${\displaystyle A}$ als Startvektor erkennen kann, kann dieses Ereignis deutlich vor ${\displaystyle n}$, der Dimension des Gesamtraumes stattfinden.

Krylowräume und Polynome

Solange der minimale Index ${\displaystyle m}$ nicht erreicht wurde, lassen sich Vektoren ${\displaystyle x\in {\mathcal {K}}_{\ell }(A,q)}$ eindeutig durch Polynome der Form ${\displaystyle p(A)q}$ vom Höchstgrad ${\displaystyle \ell -1}$ beschreiben. Sei dazu die Krylowmatrix ${\displaystyle K_{\ell }}$ definiert durch ${\displaystyle K_{\ell }=\left(q,Aq,\ldots ,A^{\ell -1}q\right)}$. Dann lässt sich ${\displaystyle x}$ darstellen als ${\displaystyle x=K_{\ell }z}$ für einen Koeffizientenvektor ${\displaystyle z\in \mathbb {K} ^{\ell }}$. Einsetzen zeigt, dass

${\displaystyle x=K_{\ell }z=\sum _{j=0}^{\ell -1}z_{j+1}A^{j}q=p(A)q}$

für ein Polynom vom Höchstgrad ${\displaystyle \ell -1}$ gilt. Diese Umschreibung stellt also eine Bijektion dar.

Für ${\displaystyle \ell =m+1}$ entspricht die Dimension des Krylowraumes nicht mehr der Anzahl ${\displaystyle \ell }$ seiner Erzeuger. Damit gibt es Polynome ${\displaystyle p}$ minimalen Grades ${\displaystyle m}$, die den Nullvektor ergeben, ${\displaystyle p(A)q=0}$. Diese Polynome sind immer Faktoren des charakteristischen Polynoms ${\displaystyle \chi _{A}}$. Die Eigenwerte, die den Nullstellen eines Faktors kleinen Grades entsprechen, sind einfacher aus diesem als aus dem gesamten charakteristischen Polynom zu bestimmen.

Die Identität ${\displaystyle p(A)q=0}$ kann in die Form ${\displaystyle {\big (}p_{0}+A{\tilde {p}}(A){\big )}q=0}$ umgeschrieben werden, d. h.

${\displaystyle q=-{\frac {1}{p_{0}}}A{\tilde {p}}(A)q=A\cdot \left({\frac {1}{p_{0}}}(-p_{1}-p_{2}A-\dots -p_{m}A^{m-1})q\right)}$.

Der zweite Faktor ${\displaystyle \textstyle x={\frac {1}{p_{0}}}{\tilde {p}}(A)q\in {\mathcal {K}}_{m}}$ auf der rechten Seite ist eine Lösung des linearen Gleichungssystems ${\displaystyle Ax=q}$.

Vorkommen

Krylowräume bilden die Grundlage für einige Projektionsverfahren, die sogenannten Krylow-Unterraum-Verfahren. Benannt sind Krylowräume nach dem russischen Schiffbauingenieur und Mathematiker Alexei Nikolajewitsch Krylow, welcher sie in einem 1931 erschienenen Artikel zur Eigenwertberechnung über das charakteristische Polynom verwendete. Der von Krylow gefundene Algorithmus hat nicht mehr viel mit den heutzutage verwendeten Krylowraum-Verfahren gemein, wird aber in der Computeralgebra und insbesondere in Computeralgebrasystemen (CAS) verwendet.

Literatur

• Y. Saad: Iterative Methods for Sparse Linear Systems, 2nd edition, SIAM Society for Industrial & Applied Mathematics 2003, ISBN 0-898-71534-2