Crylow room

A Krylow space is a subspace of the complex column vector space , which is defined as a square matrix , a column vector , the start vector of the Krylow sequence and an index m as a linear envelope of iterated matrix-vector products : ${\displaystyle \mathbb {C} ^{n}}$ ${\displaystyle A\in \mathbb {C} ^{n\times n}}$ ${\displaystyle q\in \mathbb {C} ^{n}}$

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

Dimension of the cryogenic space

The dimension of the Krylow space is limited on the one hand by the number m of generating elements, on the other hand by the dimension n of the surrounding column vector space . There is thus a maximum index up to which the dimension of the cryogenic space corresponds to its index. This means that the vector becomes linearly dependent on the previous generators . It follows that all subsequent generators are also linearly dependent on the first m , i.e. H. the sequence of the dimensions of the Krylow spaces remains constant from m . ${\displaystyle {\mathcal {K}}_{m}(A,q)}$ ${\displaystyle m\leq n}$ ${\displaystyle A^{m}q}$ ${\displaystyle A^{m+k}q}$

The minimum index for which the space is no longer expanded is called the degree of in . At this point, most of the cryogenic space methods break off with the precisely calculated solution. As can be seen from the example of an eigenvector of as the start vector, this event can take place well before the dimension of the total space. ${\displaystyle m}$ ${\displaystyle q}$ ${\displaystyle A}$ ${\displaystyle A}$ ${\displaystyle n}$

Krylow spaces and polynomials

As long as the minimum index has not been reached, vectors can be clearly described by polynomials of the form of the highest degree. Let the Krylow matrix be defined by . Then it can be represented as for a coefficient vector . Insertion shows that ${\displaystyle m}$ ${\displaystyle x\in {\mathcal {K}}_{\ell }(A,q)}$ ${\displaystyle p(A)q}$ ${\displaystyle \ell -1}$ ${\displaystyle K_{\ell }}$ ${\displaystyle K_{\ell }=\left(q,Aq,\ldots ,A^{\ell -1}q\right)}$ ${\displaystyle x}$ ${\displaystyle x=K_{\ell }z}$ ${\displaystyle z\in \mathbb {K} ^{\ell }}$

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

holds for a polynomial of the highest degree . This description therefore represents a bijection. ${\displaystyle \ell -1}$

For the size of the cryogenic space no longer corresponds to the number of its producers. This makes a polynomials minimal degree that the zero vector revealed . These polynomials are always factors of the characteristic polynomial . The eigenvalues ​​that correspond to the zeros of a factor of small degree are easier to determine from this than from the entire characteristic polynomial. ${\displaystyle \ell =m+1}$ ${\displaystyle \ell }$ ${\displaystyle p}$ ${\displaystyle m}$ ${\displaystyle p(A)q=0}$ ${\displaystyle \chi _{A}}$

The identity can be rewritten in the form , i.e. H. ${\displaystyle p(A)q=0}$ ${\displaystyle {\big (}p_{0}+A{\tilde {p}}(A){\big )}q=0}$

${\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)}$.

The second factor on the right is a solution to the linear system of equations . ${\displaystyle \textstyle x={\frac {1}{p_{0}}}{\tilde {p}}(A)q\in {\mathcal {K}}_{m}}$ ${\displaystyle Ax=q}$

Occurrence

Krylow spaces form the basis for some projection methods , the so-called Krylow subspace methods . Krylow rooms are named after the Russian shipbuilding engineer and mathematician Alexei Nikolajewitsch Krylow , who used them in an article published in 1931 to calculate the eigenvalue of the characteristic polynomial. The algorithm found by Krylow no longer has much in common with the Krylow space methods used today, but is used in computer algebra and in particular in computer algebra systems (CAS).

literature

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