next up previous contents index
Next: The -factorization of Hessenberg-like Up: QR-algorithms Previous: QR-algorithms   Contents   Index


Theoretical results needed to design implicit $ QR$-algorithms for semiseparable matrices

In Chapter 8 of this thesis we will design different types of implicit $ QR$/algorithms for matrices of semiseparable form. Before we are able to construct these algorithms some theoretical results are needed. In this chapter we will provide answers to the following problems for Hessenberg-like matrices. How can we calculate the $ QR$-factorization of a Hessenberg-like plus diagonal matrix? What is the structure of an unreduced Hessenberg-like matrix and how can we transform a matrix to the unreduced form? Is the Hessenberg-like structure maintained after a step of $ QR$ with shift? Does some kind of analogue of the implicit $ Q$-theorem exist for Hessenberg-like matrices? The results in this chapter are applied to Hessenberg-like matrices, because this is the most general structure. In the following chapter, we will adapt, if it is necessary, the theorems to the other cases, namely the symmetric case and the upper triangular semiseparable case.


In a first section of this chapter we will investigate ``a type'' of $ QR$-factorization of Hessenberg-like plus diagonal matrices. We say a type of because we will show in the next section, that the $ QR$-factorization is not necessarily unique. The factorization we propose is based on the paper [178]. In the factorization presented in this paper, the orthogonal matrix $ Q$ is constructed as a product of $ 2n-2$ Givens transformations, with $ n$ the dimension of the matrix. Suppose we have a Hessenberg-like plus diagonal matrix $ Z+D$. It will be shown that a first sequence of $ n-1$ Givens transformations $ Q_1$ will transform the matrix $ Z$ into an upper triangular matrix $ Q_1^T Z$. These Givens transformations will transform the matrix $ D$ into a Hessenberg matrix. Our resulting matrix $ Q_1^T(Z+D)$ will therefore be Hessenberg. The second sequence of Givens transformations will reduce the Hessenberg matrix to upper triangular form.

The concept of irreducibility is an important topic for the construction of implicit $ QR$-algorithms. We define what is meant with an unreduced Hessenberg-like matrix. It will be shown later on that this unreducedness demand plays a very important role in the implicit $ Q$-theorem and in the construction of the implicit $ QR$-algorithm. Moreover, using the definition of an unreduced Hessenberg-like matrix, it is rather easy to prove the essential uniqueness of the $ QR$-factorization for Hessenberg-like matrices. With essentially unique we mean that two $ QR$-factorizations only differ for the sign of the elements.

In the third section we will investigate the structure of a Hessenberg-like matrix after having applied a step of the $ QR$-algorithm with shift. First we show that the choice of the $ QR$-factorization is essential to obtain again a Hessenberg-like matrix after a $ QR$-step. This fact is illustrated by an example in the Hessenberg and in the Hessenberg-like case. Using the $ QR$-factorization for Hessenberg-like matrices as explained in Section 7.1, we will prove the following theorems: The structure of a Hessenberg-like matrix is maintained after a step of $ QR$ without shift; The weakly lower triangular structure of a matrix is maintained after a $ QR$-step with shift; The Hessenberg-like structure is maintained after a $ QR$-step with shift; The diagonal in a Hessenberg-like plus diagonal matrix is maintained after applying a step of $ QR$ with shift. Note that for these theorems, no assumptions concerning the singularity of the matrices are made.

In the second section we defined unreduced Hessenberg-like matrices and in Section 7.5 we will prove an implicit $ Q$-theorem for Hessenberg-like matrices. This implicit $ Q$-theorem strongly depends on the unreducedness of the Hessenberg-like matrix. Therefore we will provide in Section 7.4 an easy way of transforming a Hessenberg-like matrix to unreduced form. The algorithm provided performs in fact a special $ QR$-step without shift on the Hessenberg-like matrix. This results in an algorithm, revealing immediately the singularities of the corresponding Hessenberg-like matrix.

In Section 7.5 of this chapter we will provide an implicit $ Q$-theorem for Hessenberg-like matrices. The theorem is quite similar to the theorem for Hessenberg matrices. It will prove to be very powerful in the next chapter when we start with the construction of the different $ QR$-algorithms.



Subsections
next up previous contents index
Next: The -factorization of Hessenberg-like Up: QR-algorithms Previous: QR-algorithms   Contents   Index
Raf Vandebril 2004-05-03