NAG Library Routine Document

F08JEF (DSTEQR)

+− Contents

1 Purpose

2 Specification

3 Description

4 References

5 Parameters

6 Error Indicators and Warnings

7 Accuracy

8 Further Comments

+− 9 Example

9.1 Program Text

9.2 Program Data

9.3 Program Results

1 Purpose

F08JEF (DSTEQR) computes all the eigenvalues and, optionally, all the eigenvectors of a real symmetric tridiagonal matrix, or of a real symmetric matrix which has been reduced to tridiagonal form.

2 Specification

SUBROUTINE F08JEF (

COMPZ, N, D, E, Z, LDZ, WORK, INFO)

INTEGER	N, LDZ, INFO
REAL (KIND=nag_wp)	D(), E(), Z(LDZ,), WORK()
CHARACTER(1)	COMPZ

The routine may be called by its LAPACK name dsteqr.

3 Description

F08JEF (DSTEQR) computes all the eigenvalues and, optionally, all the eigenvectors of a real symmetric tridiagonal matrix

T

. In other words, it can compute the spectral factorization of

T

T = Z Λ Z^{T},

where

Λ

is a diagonal matrix whose diagonal elements are the eigenvalues

λ_{i}

, and

Z

is the orthogonal matrix whose columns are the eigenvectors

z_{i}

. Thus

T z_{i} = λ_{i} z_{i}, i = 1, 2, \dots, n .

The routine may also be used to compute all the eigenvalues and eigenvectors of a real symmetric matrix

A

which has been reduced to tridiagonal form

T

\begin{array}{l} A & = Q T Q^{T}, where ​ Q ​ is orthogonal \\ = (Q Z) Λ {(Q Z)}^{T} . \end{array}

In this case, the matrix

Q

must be formed explicitly and passed to F08JEF (DSTEQR), which must be called with

COMPZ ='V'

. The routines which must be called to perform the reduction to tridiagonal form and form

Q

are:

full matrix	F08FEF (DSYTRD) and F08FFF (DORGTR)
full matrix, packed storage	F08GEF (DSPTRD) and F08GFF (DOPGTR)
band matrix	F08HEF (DSBTRD) with $VECT ='V'$ .

F08JEF (DSTEQR) uses the implicitly shifted

Q R

algorithm, switching between the

Q R

and

Q L

variants in order to handle graded matrices effectively (see Greenbaum and Dongarra (1980)). The eigenvectors are normalized so that

{‖z_{i}‖}_{2} = 1

, but are determined only to within a factor

\pm 1

If only the eigenvalues of

T

are required, it is more efficient to call F08JFF (DSTERF) instead. If

T

is positive definite, small eigenvalues can be computed more accurately by F08JGF (DPTEQR).

4 References

Golub G H and Van Loan C F (1996) Matrix Computations (3rd Edition) Johns Hopkins University Press, Baltimore

Greenbaum A and Dongarra J J (1980) Experiments with QR/QL methods for the symmetric triangular eigenproblem LAPACK Working Note No. 17 (Technical Report CS-89-92) University of Tennessee, Knoxville

Parlett B N (1998) The Symmetric Eigenvalue Problem SIAM, Philadelphia

5 Parameters

1: COMPZ – CHARACTER(1)Input

On entry: indicates whether the eigenvectors are to be computed.

$COMPZ ='N'$: Only the eigenvalues are computed (and the array Z is not referenced).
$COMPZ ='I'$: The eigenvalues and eigenvectors of $T$ are computed (and the array Z is initialized by the routine).
$COMPZ ='V'$: The eigenvalues and eigenvectors of $A$ are computed (and the array Z must contain the matrix $Q$ on entry).

Constraint:

COMPZ ='N'

'V'

'I'

2: N – INTEGERInput

On entry:

n

, the order of the matrix

T

Constraint:

N \geq 0

3: D( $*$ ) – REAL (KIND=nag_wp) arrayInput/Output

Note: the dimension of the array D must be at least

\max (1, N)

On entry: the diagonal elements of the tridiagonal matrix

T

On exit: the

n

eigenvalues in ascending order, unless

INFO > 0

(in which case see Section 6).

4: E( $*$ ) – REAL (KIND=nag_wp) arrayInput/Output

Note: the dimension of the array E must be at least

\max (1, N - 1)

On entry: the off-diagonal elements of the tridiagonal matrix

T

On exit: E is overwritten.

5: Z(LDZ, $*$ ) – REAL (KIND=nag_wp) arrayInput/Output

Note: the second dimension of the array Z must be at least

\max (1, N)

COMPZ ='V'

'I'

and at least

1

COMPZ ='N'

On entry: if

COMPZ ='V'

, Z must contain the orthogonal matrix

Q

from the reduction to tridiagonal form.

COMPZ ='I'

, Z need not be set.

On exit: if

COMPZ ='I'

'V'

, the

n

required orthonormal eigenvectors stored as columns of

Z

; the

i

th column corresponds to the

i

th eigenvalue, where

i = 1, 2, \dots, n

, unless

INFO > 0

COMPZ ='N'

, Z is not referenced.

6: LDZ – INTEGERInput

On entry: the first dimension of the array Z as declared in the (sub)program from which F08JEF (DSTEQR) is called.

Constraints:

if $COMPZ ='I'$ or $'V'$ , $LDZ \geq \max (1, N)$ ;
if $COMPZ ='N'$ , $LDZ \geq 1$ .

7: WORK( $*$ ) – REAL (KIND=nag_wp) arrayWorkspace

Note: the dimension of the array WORK must be at least

\max (1, 2 \times (N - 1))

COMPZ ='V'

'I'

and at least

1

COMPZ ='N'

COMPZ ='N'

, WORK is not referenced.

8: INFO – INTEGEROutput

On exit:

INFO = 0

unless the routine detects an error (see Section 6).

6 Error Indicators and Warnings

Errors or warnings detected by the routine:

$INFO < 0$: If $INFO = - i$ , argument $i$ had an illegal value. An explanatory message is output, and execution of the program is terminated.

$INFO > 0$: The algorithm has failed to find all the eigenvalues after a total of $30 \times N$ iterations. In this case, D and E contain on exit the diagonal and off-diagonal elements, respectively, of a tridiagonal matrix similar to $T$ . If $INFO = i$ , then $i$ off-diagonal elements have not converged to zero.

7 Accuracy

The computed eigenvalues and eigenvectors are exact for a nearby matrix

(T + E)

, where

{‖E‖}_{2} = O (ε) {‖T‖}_{2},

and

ε

is the machine precision.

λ_{i}

is an exact eigenvalue and

{\tilde{λ}}_{i}

is the corresponding computed value, then

|{\tilde{λ}}_{i} - λ_{i}| \leq c (n) ε {‖T‖}_{2},

where

c (n)

is a modestly increasing function of

n

z_{i}

is the corresponding exact eigenvector, and

{\tilde{z}}_{i}

is the corresponding computed eigenvector, then the angle

θ ({\tilde{z}}_{i}, z_{i})

between them is bounded as follows:

θ ({\tilde{z}}_{i}, z_{i}) \leq \frac{c (n) ε {‖T‖}_{2}}{\min_{i \neq j} |λ_{i} - λ_{j}|} .

Thus the accuracy of a computed eigenvector depends on the gap between its eigenvalue and all the other eigenvalues.

8 Further Comments

The total number of floating point operations is typically about

24 n^{2}

COMPZ ='N'

and about

7 n^{3}

COMPZ ='V'

'I'

, but depends on how rapidly the algorithm converges. When

COMPZ ='N'

, the operations are all performed in scalar mode; the additional operations to compute the eigenvectors when

COMPZ ='V'

'I'

can be vectorized and on some machines may be performed much faster.

The complex analogue of this routine is F08JSF (ZSTEQR).

9 Example

This example computes all the eigenvalues and eigenvectors of the symmetric tridiagonal matrix

T