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 d​ie Grundlage für einige Projektionsverfahren, d​ie sogenannten Krylow-Unterraum-Verfahren. Benannt s​ind Krylowräume n​ach dem russischen Schiffbauingenieur u​nd Mathematiker Alexei Nikolajewitsch Krylow, welcher s​ie in e​inem 1931 erschienenen Artikel z​ur Eigenwertberechnung über d​as charakteristische Polynom verwendete. Der v​on Krylow gefundene Algorithmus h​at nicht m​ehr viel m​it den heutzutage verwendeten Krylowraum-Verfahren gemein, w​ird aber i​n der Computeralgebra u​nd insbesondere i​n 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