Krylov subspace

A Krylowraum is a subspace of the complex column vector space, which is defined to be a square matrix, a column vector, the start vector of the Krylov sequence and an index m as a linear hull of iterated matrix - vector products:

Dimension of Krylowraumes

The dimension of the Krylowraumes one hand limited by the number m of generating elements, on the other hand, by the n-dimensional column vector of the surrounding area. There are thus a maximum index to which matches the dimension of the Krylowraumes with its index. This means that the vector of the preceding generatrix is linearly dependent. It follows that all subsequent generating of the first m are linearly dependent, ie the sequence of the dimensions of Krylowräume remains constant from m.

The minimal index for which the space is not expanded, it is called the degree of in. At this point, most Krylowraum process chip with exactly computed solution. As you can see by the example of an eigenvector of a start vector, this event can still clearly be held to the dimension of the entire space.

Krylowräume and polynomials

As long as the minimum index has not reached, Vector images clearly described by polynomials of the form from the maximum degree. For this purpose let the Krylowmatrix defined by. Then can be represented as a coefficient vector. Insert shows that

Applies to a polynomial of maximum degree. So This description represents a bijection

For the dimension of Krylowraumes no longer corresponds to the number of its generators. Thus there are polynomials p minimal degree m which give the zero vector. These polynomials are always factors of the characteristic polynomial. The eigenvalues ​​corresponding to the zeros of a factor small degree, are easier to determine than for that from the entire characteristic polynomial.

The identity can be rewritten into the form, that

The second factor on the right side is a solution of the linear system Ax = q.

Occurrence

Krylowräume form the basis for some of the projection process, the so-called Krylov subspace method. Named are Krylowräume after the Russian naval engineer Alexei Nikolaevich Krylov and mathematician, who used it in a 1931 article published for the eigenvalue calculation using the characteristic polynomial. The algorithm found Krylov no longer has much in common with the Krylowraum method used today, but it is used in computer algebra and in particular in computer algebra systems (CAS).