NAG Library Function Document

nag_real_general_eigensystem (f02bjc)

void	nag_real_general_eigensystem (Integer n, double a[], Integer tda, double b[], Integer tdb, double tol, Complex alfa[], double beta[], Nag_Boolean wantv, double v[], Integer tdv, Integer iter[], NagError *fail)

3 Description

All the eigenvalues and, if required, all the eigenvectors of the generalized eigenproblem

A x = λ B x

where

A

and

B

are real, square matrices, are determined using the

Q Z

algorithm. The

Q Z

algorithm consists of four stages:

(a)	$A$ is reduced to upper Hessenberg form and at the same time $B$ is reduced to upper triangular form.
(b)	$A$ is further reduced to quasi-triangular form while the triangular form of $B$ is maintained.
(c)	The quasi-triangular form of $A$ is reduced to triangular form and the eigenvalues extracted.
(d)	This function does not actually produce the eigenvalues $λ_{j}$ , but instead returns $α_{j}$ and $β_{j}$ such that $λ_{j} = α_{j} / β_{j}, j = 1, 2, \dots, n$ . The division by $β_{j}$ becomes the responsibility of your program, since $β_{j}$ may be zero indicating an infinite eigenvalue. Pairs of complex eigenvalues occur with $α_{j} / β_{j}$ and $α_{j + 1} / β_{j + 1}$ complex conjugates, even though $α_{j}$ and $α_{j + 1}$ are not conjugate.
(e)	If the eigenvectors are required ( $wantv = Nag_TRUE$ ), they are obtained from the triangular matrices and then transformed back into the original coordinate system.

4 References

Moler C B and Stewart G W (1973) An algorithm for generalized matrix eigenproblems SIAM J. Numer. Anal. 10 241–256

Ward R C (1975) The combination shift

Q Z

algorithm SIAM J. Numer. Anal. 12 835–853

Wilkinson J H (1979) Kronecker's canonical form and the

Q Z

algorithm Linear Algebra Appl. 28 285–303

5 Arguments

1: $n$ – IntegerInput

On entry:

n

, the order of the matrices

A

and

B

Constraint:

n \geq 1

2: $a [n \times tda]$ – doubleInput/Output

Note: the

(i, j)

th element of the matrix

A

is stored in

a [(i - 1) \times tda + j - 1]

On entry: the

n

n

matrix

A

On exit: a is overwritten.

3: $tda$ – IntegerInput

On entry: the stride separating matrix column elements in the array a.

Constraint:

tda \geq n

4: $b [n \times tdb]$ – doubleInput/Output

Note: the

(i, j)

th element of the matrix

B

is stored in

b [(i - 1) \times tdb + j - 1]

On entry: the

n

n

matrix

B

On exit: b is overwritten.

5: $tdb$ – IntegerInput

On entry: the stride separating matrix column elements in the array b.

Constraint:

tdb \geq n

6: $tol$ – doubleInput

On entry: the tolerance used to determine negligible elements.

$tol > 0.0$: An element will be considered negligible if it is less than tol times the norm of its matrix.
$tol \leq 0.0$: machine precision is used in place of tol.

A value of tol greater than machine precision may result in faster execution but less accurate results.

7: $alfa [n]$ – ComplexOutput

On exit:

α_{j}

, for

j = 1, 2, \dots, n

8: $beta [n]$ – doubleOutput

On exit:

β_{j}

, for

j = 1, 2, \dots, n

9: $wantv$ – Nag_BooleanInput

On entry: wantv must be set to Nag_TRUE if the eigenvectors are required. If wantv is set to Nag_FALSE then the array v is not referenced.

10: $v [n \times tdv]$ – doubleOutput

Note: the

i

th element of the

j

th vector

V

is stored in

v [(i - 1) \times tdv + j - 1]

On exit: if

wantv = Nag_TRUE

, then

(i)	if the $j$ th eigenvalue is real, the $j$ th column of v contains its eigenvector;
(ii)	if the $j$ th and $(j + 1)$ th eigenvalues form a complex pair, the $j$ th and $(j + 1)$ th columns of v contain the real and imaginary parts of the eigenvector associated with the first eigenvalue of the pair. The conjugate of this vector is the eigenvector for the conjugate eigenvalue.

Each eigenvector is normalized so that the component of largest modulus is real and the sum of squares of the moduli equal one.

wantv = Nag_FALSE

, v is not referenced and may be NULL.

11: $tdv$ – IntegerInput

On entry: the stride separating matrix column elements in the array v.

Constraint: if

wantv = Nag_TRUE

tdv \geq n

12: $iter [n]$ – IntegerOutput

On exit:

iter [j - 1]

contains the number of iterations needed to obtain the

j

th eigenvalue. Note that the eigenvalues are obtained in reverse order, starting with the

n

th.

13: $fail$ – NagError *Input/Output

The NAG error argument (see Section 3.6 in the Essential Introduction).

6 Error Indicators and Warnings

NE_2_INT_ARG_LT: On entry, $tda = 〈value〉$ while $n = 〈value〉$ . These arguments must satisfy $tda \geq n$ .

On entry, $tdb = 〈value〉$ while $n = 〈value〉$ . These arguments must satisfy $tdb \geq n$ .

On entry, $tdv = 〈value〉$ while $n = 〈value〉$ . These arguments must satisfy $tdv \geq n$ .
NE_INT_ARG_LT: On entry, $n = 〈value〉$ .
Constraint: $n \geq 1$ .
NE_ITERATIONS_QZ: More than $n \times 30$ iterations are required to determine all the diagonal 1 by 1 or 2 by 2 blocks of the quasi-triangular form in the second step of the $Q Z$ algorithm. This failure occurs at the $i$ th eigenvalue, $i = 〈value〉$ . $α_{j}$ and $β_{j}$ are correct for $j = i + 1, i + 2, \dots, n$ but v does not contain any correct eigenvectors.
The value of $i$ will be returned in member $fail . errnum$ of the NAG error structure provided NAGERR_DEFAULT is not used as the error argument.

7 Accuracy

The computed eigenvalues are always exact for a problem

(A + E) x = λ (B + F) x

where

‖E‖ / ‖A‖

and

‖F‖ / ‖B‖

are both of the order of

\max (tol, ε)

, tol being defined as in Section 5 and

ε

being the machine precision.

Note: interpretation of results obtained with the

Q Z

algorithm often requires a clear understanding of the effects of small changes in the original data. These effects are reviewed in Wilkinson (1979), in relation to the significance of small values of

α_{j}

and

β_{j}

. It should be noted that if

α_{j}

and

β_{j}

are both small for any

j

, it may be that no reliance can be placed on any of the computed eigenvalues

λ_{i} = α_{i} / β_{i}

. You are recommended to study Wilkinson (1979) and, if in difficulty, to seek expert advice on determining the sensitivity of the eigenvalues to perturbations in the data.

8 Parallelism and Performance

Not applicable.

9 Further Comments

The time taken by nag_real_general_eigensystem (f02bjc) is approximately proportional to

n^{3}

and also depends on the value chosen for argument tol.

10 Example

To find all the eigenvalues and eigenvectors of

A x = λ B x

where

A = (\begin{matrix} 3.9 & 4.3 & 4.3 & 4.4 \\ 12.5 & 21.5 & 21.5 & 26.0 \\ - 34.5 & - 47.5 & - 43.5 & - 46.0 \\ - 0.5 & 7.5 & 3.5 & 6.0 \end{matrix}) and B = (\begin{matrix} 1 & 1 & 1 & 1 \\ 2 & 3 & 3 & 3 \\ - 3 & - 5 & - 4 & - 4 \\ 1 & 4 & 3 & 4 \end{matrix}) .

NAG Library Function Documentnag_real_general_eigensystem (f02bjc)

▸▿ Contents

1 Purpose

2 Specification

3 Description

4 References

5 Arguments

6 Error Indicators and Warnings

7 Accuracy

8 Parallelism and Performance

9 Further Comments

10 Example

10.1 Program Text

10.2 Program Data

10.3 Program Results

NAG Library Function Document

nag_real_general_eigensystem (f02bjc)