In lieu of an abstract, here is a brief excerpt of the content:

Chapter 6 Theoretical results for structured rank QR-algorithms In Chapter 7 of this book we will design different types of implicit QR-algorithms for matrices of semiseparable form. More precisely the chasing techniques will be developed in that chapter. 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 theorems, definitions and results in this chapter are applied to Hessenberglike 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, for computing the singular values. As these structures, semiseparable and upper triangular semiseparable, have more structure with regard to the Hessenberg-like case, we will often be able to simplify some definitions or to obtain stronger results. This chapter consists of three sections. In the first two sections results related to Hessenberg-like matrices will be shown. The preservation of the Hessenberg-like structure after a step of the QR-algorithm is the subject of the first section and the second section focuses on the development of an implicit Q-theorem. The last section briefly discusses the Hessenberg-like plus diagonal case. In the first section of this chapter we focus towards the QR-factorization and the structure after performing a QR-step. In a first subsection 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 [156] and was also presented in Volume I, Chapter 9 of this book [169]. In the factorization presented here, the orthogonal matrix Q is constructed as a product of 2n − 2 171 172 Chapter 6. Theoretical results for structured rank QR-algorithms 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 Q1 will transform the matrix Z into an upper triangular matrix QT 1 Z. These Givens transformations will transform the matrix D into a Hessenberg matrix. Our resulting matrix QT 1 (Z + D) will therefore be Hessenberg. The second sequence of Givens transformations will reduce the Hessenberg matrix to upper triangular form. In the second and third subsection 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. Using the QR-factorization for Hessenberg-like matrices as explained in Subsection 6.1.1, we will prove the following theorems: The structure of a Hessenberg-like matrix is maintained after a step of QR without shift; the strictly lower triangular rank structure of a matrix is maintained after a QRstep with shift; the Hessenberg-like structure is maintained after a QR-step with shift. Note that for these theorems no assumptions concerning the singularity of the matrices are made. In the second section we will develop an implicit Q-theorem for Hessenberg-like matrices. In order to do so, we define what is meant with an unreduced Hessenberglike 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. By essentially unique we mean that two QR-factorizations only differ for the sign of the elements. In the first subsection we will define unreduced Hessenberg-like matrices, and in the third Subsection 6.2.3 we will prove an implicit Q-theorem...

Share