imported>M-B: /* Krylowräume und Polynome */

2019-07-22T14:43:27Z

Krylowräume und Polynome

Neue Seite

Ein '''Krylowraum''' ist ein [[Untervektorraum]] des [[komplexe Zahl|komplexen]] [[Matrix (Mathematik)|Spaltenvektorraums]] <math>\mathbb{C}^n</math>, der zu einer quadratischen [[Matrix (Mathematik)|Matrix]] <math>A\in\mathbb{C}^{n\times n}</math>, einem Spaltenvektor <math>q\in\mathbb{C}^n</math>, dem ''Startvektor der Krylow-Sequenz'' und einem Index ''m'' als [[lineare Hülle]] iterierter [[Matrix-Vektor-Produkt]]e definiert ist:

:<math>\mathcal{K}=\mathcal{K}(A,q)
=\mathcal{K}_m(A,q)
=\mbox{span}\{q,Aq,\ldots,A^{m-1}q\}.</math>

== Dimension des Krylowraumes ==
Die Dimension des Krylowraumes <math>\mathcal{K}_m(A,q)</math> 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 <math>m\le n</math>, bis zu dem die Dimension des Krylowraumes mit seinem Index übereinstimmt. Dies bedeutet, dass der Vektor <math>A^mq</math> von den vorhergehenden Erzeugenden [[linear abhängig]] wird. Daraus folgt, dass auch alle nachfolgenden Erzeugenden <math>A^{m+k}q</math> von den ersten ''m'' linear abhängig sind, d. h. die Folge der Dimensionen der Krylowräume bleibt ab ''m'' konstant.

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

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

:<math>x=K_\ell z=\sum_{j=0}^{\ell-1} z_{j+1} A^j q = p(A)q</math>

für ein Polynom vom Höchstgrad <math>\ell-1</math> gilt. Diese Umschreibung stellt also eine Bijektion dar.

Für <math>\ell=m+1</math> entspricht die Dimension des Krylowraumes nicht mehr der Anzahl <math>\ell</math> seiner Erzeuger. Damit gibt es Polynome <math>p</math> minimalen Grades <math>m</math>, die den [[Nullvektor]] ergeben, <math>p(A)q=0</math>. Diese Polynome sind immer Faktoren des [[charakteristisches Polynom|charakteristischen Polynoms]] <math>\chi_A</math>. 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 <math>p(A)q=0</math> kann in die Form <math>\big(p_0+A\tilde p(A)\big)q=0</math> umgeschrieben werden, d. h.
:<math>q=-\frac1{p_0}A\tilde p(A)q=A\cdot\left(\frac1{p_0}(-p_1-p_2A-\dots-p_{m}A^{m-1})q\right)</math>.
Der zweite Faktor <math>\textstyle x=\frac1{p_0}\tilde p(A)q\in\mathcal K_{m}</math> auf der rechten Seite ist eine Lösung des linearen Gleichungssystems <math>Ax=q</math>.

== Vorkommen ==
Krylowräume bilden die Grundlage für einige [[Projektion (lineare Algebra)|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 [[Eigenwert]]berechnung ü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

[[Kategorie:Skalarproduktraum]]
[[Kategorie:Numerische lineare Algebra]]

Krylowraum - Versionsgeschichte

imported>M-B: /* Krylowräume und Polynome */