nag_real_general_eigensystem (f02bjc) (PDF version)
f02 Chapter Contents
f02 Chapter Introduction
NAG Library Manual

NAG Library Function Document

nag_real_general_eigensystem (f02bjc)

 Contents

    1  Purpose
    7  Accuracy

1  Purpose

nag_real_general_eigensystem (f02bjc) calculates all the eigenvalues and, if required, all the eigenvectors of the generalized eigenproblem A x = λ Bx  where A  and B  are real, square matrices, using the QZ  algorithm.

2  Specification

#include <nag.h>
#include <nagf02.h>
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 Ax = λ Bx  where A  and B  are real, square matrices, are determined using the QZ  algorithm. The QZ  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 , , 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 QZ algorithm SIAM J. Numer. Anal. 12 835–853
Wilkinson J H (1979) Kronecker's canonical form and the QZ algorithm Linear Algebra Appl. 28 285–303

5  Arguments

1:     n IntegerInput
On entry: n , the order of the matrices A  and B .
Constraint: n1 .
2:     a[n×tda] doubleInput/Output
Note: the i,jth element of the matrix A is stored in a[i-1×tda+j-1].
On entry: the n  by n  matrix A .
On exit: a is overwritten.
3:     tda IntegerInput
On entry: the stride separating matrix column elements in the array a.
Constraint: tdan .
4:     b[n×tdb] doubleInput/Output
Note: the i,jth element of the matrix B is stored in b[i-1×tdb+j-1].
On entry: the n  by n  matrix B .
On exit: b is overwritten.
5:     tdb IntegerInput
On entry: the stride separating matrix column elements in the array b.
Constraint: tdbn .
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.
tol0.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,,n.
8:     beta[n] doubleOutput
On exit: β j , for j=1,2,,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×tdv] doubleOutput
Note: the ith element of the jth vector V is stored in v[i-1×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.
If 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 , tdvn
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 tdan .
On entry, tdb=value  while n=value . These arguments must satisfy tdbn .
On entry, tdv=value  while n=value . These arguments must satisfy tdvn .
NE_INT_ARG_LT
On entry, n=value.
Constraint: n1.
NE_ITERATIONS_QZ
More than n×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 QZ  algorithm. This failure occurs at the i th eigenvalue, i=value . α j  and β j  are correct for j = i + 1 , i + 2 , , 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 QZ  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 Ax = λ Bx  where
A = 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   and   B = 1 1 1 1 2 3 3 3 -3 -5 -4 -4 1 4 3 4 .  

10.1  Program Text

Program Text (f02bjce.c)

10.2  Program Data

Program Data (f02bjce.d)

10.3  Program Results

Program Results (f02bjce.r)


nag_real_general_eigensystem (f02bjc) (PDF version)
f02 Chapter Contents
f02 Chapter Introduction
NAG Library Manual

© The Numerical Algorithms Group Ltd, Oxford, UK. 2015