Browse Prior Art Database

THE SHIFTED QR ALGORITHM FOR NORMAL MATRICES

IP.com Disclosure Number: IPCOM000128691D
Original Publication Date: 1975-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 6 page(s) / 18K

Publishing Venue

Software Patent Institute

Related People

C. P. Huang: AUTHOR [+3]

Abstract

We show here that if a normal upper Hessenberg matrix of a certain type undergoes one QR transformation with a certain origin shift, then its transform exhibits certain properties.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 51% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

THE SHIFTED QR ALGORITHM FOR NORMAL MATRICES

C. P. Huang

CS-75-3 March THE SHIFTED QR ALGORITHM FOR NORMAL MATRICES

C. P. Huang The University of Tennessee

Abstract

We show here that if a normal upper Hessenberg matrix of a certain type undergoes one QR transformation with a certain origin shift, then its transform exhibits certain properties.

1. Introduction.

The QR algorithm with origin shift for an

(Equation Omitted)

is described [4] [81 by

(Equation Omitted)

are the origin shifts, Qt are unitary and Rt are upper triangular. If A 0 is normal, then all iterates are normal since

(Equation Omitted)

where Q* is the conjugate transpose of Qt If Ao is t t upper Hessenberg, so are all At

Section 2 introduces the notation. In section 3 we show the effect of one QR transformation with a certain origin shift on a certain type of normal upper Hessenberg matrix. One example is also included to demon-strate the necessity of using shifts of higher degree than second.

2. Notation and background. For the remainder of this paper, we consider mostly one typical iteration in the algorithm. Thus we use (2.1)

(Equation Omitted)

to denote one QR transformation. In addition, we write, for example, an-ln-2 to mean an-1, n-2 to avoid numerous commas.

We assume hereafter that the matrix A is upper Hessenberg which may be complex. If A is upper Hessenberg, so is Q and we let

University of Tennessee Page 1 Dec 31, 1975

Page 2 of 6

THE SHIFTED QR ALGORITHM FOR NORMAL MATRICES

(Equation Omitted)

Throughout this paper we assume that no

(Equation Omitted)

since then A could be split into two matrices of lower order.

For

(Equation Omitted)

where

(Equation Omitted)

we have

(2.2)

(Equation Omitted)

Now using the expression for tan 8 and the relation

(Equation Omitted)

to expand pnn' we obtain

(Equation Omitted)

Similarly, by repeatedly expanding p's in the above expression we further obtain (2.4)

(Equation Omitted)

for

(Equation Omitted)

, where d k is the determinant of the lower right k x k matrix of A divided by

(Equation Omitted)

In particular, if

(Equation Omitted)

we have

(Equation Omitted)

University of Tennessee Page 2 Dec 31, 1975

Page 3 of 6

THE SHIFTED QR ALGORITHM FOR NORMAL MATRICES

3. The QR algorithm for normal upper Hessenberg matrices.

In this section we show that if a normal upper Hessenberg matrix A of a certain type undergoes one QR transformation with a certain origin shift, then its transform exhibits certain properties. Lemma 1. If the following normal upper Hessenberg matrix

(Equation Omitted)

undergoes one QR transformation with k ann (a linear shift), then

either

(Equation Omitted)

Proof: From (2.3) since

(Equation Omitted)

unless both of the following two conditions hold

(Equation Omitted)

, which implies

(Equation Omitted)

should have the same column norms as

(Equation Omitted)

Now condition (i) yields r n-In 0 This result together with

conditions (i) and (ii) yield

(Equa...