f02 Chapter Contents
f02 Chapter Introduction
NAG C Library Manual

NAG Library Function Documentnag_real_general_eigensystem (f02bjc)

1  Purpose

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

2  Specification

 #include #include
 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=\lambda 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 ${\lambda }_{j}$, but instead returns ${\alpha }_{j}$ and ${\beta }_{j}$ such that $\text{ }{\lambda }_{j}={\alpha }_{j}/{\beta }_{j}\text{, }j=1,2,\dots ,n$. The division by ${\beta }_{j}$ becomes the responsibility of your program, since ${\beta }_{j}$ may be zero indicating an infinite eigenvalue. Pairs of complex eigenvalues occur with ${\alpha }_{j}/{\beta }_{j}$ and ${\alpha }_{j+1}/{\beta }_{j+1}$ complex conjugates, even though ${\alpha }_{j}$ and ${\alpha }_{j+1}$ are not conjugate. (e) If the eigenvectors are required (${\mathbf{wantv}}=\mathrm{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:     nIntegerInput
On entry: $n$, the order of the matrices $A$ and $B$.
Constraint: ${\mathbf{n}}\ge 1$.
2:     a[${\mathbf{n}}×{\mathbf{tda}}$]doubleInput/Output
Note: the $\left(i,j\right)$th element of the matrix $A$ is stored in ${\mathbf{a}}\left[\left(i-1\right)×{\mathbf{tda}}+j-1\right]$.
On entry: the $n$ by $n$ matrix $A$.
On exit: a is overwritten.
3:     tdaIntegerInput
On entry: the stride separating matrix column elements in the array a.
Constraint: ${\mathbf{tda}}\ge {\mathbf{n}}$.
4:     b[${\mathbf{n}}×{\mathbf{tdb}}$]doubleInput/Output
Note: the $\left(i,j\right)$th element of the matrix $B$ is stored in ${\mathbf{b}}\left[\left(i-1\right)×{\mathbf{tdb}}+j-1\right]$.
On entry: the $n$ by $n$ matrix $B$.
On exit: b is overwritten.
5:     tdbIntegerInput
On entry: the stride separating matrix column elements in the array b.
Constraint: ${\mathbf{tdb}}\ge {\mathbf{n}}$.
6:     toldoubleInput
On entry: the tolerance used to determine negligible elements.
${\mathbf{tol}}>0.0$
An element will be considered negligible if it is less than tol times the norm of its matrix.
${\mathbf{tol}}\le 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: ${\alpha }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$.
8:     beta[n]doubleOutput
On exit: ${\beta }_{\mathit{j}}$, for $\mathit{j}=1,2,\dots ,n$.
9:     wantvNag_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[${\mathbf{n}}×{\mathbf{tdv}}$]doubleOutput
Note: the $i$th element of the $j$th vector $V$ is stored in ${\mathbf{v}}\left[\left(i-1\right)×{\mathbf{tdv}}+j-1\right]$.
On exit: if ${\mathbf{wantv}}=\mathrm{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 $\left(j+1\right)$th eigenvalues form a complex pair, the $j$th and $\left(j+1\right)$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 ${\mathbf{wantv}}=\mathrm{Nag_FALSE}$, v is not referenced and may be set to the null pointer, i.e., (double *)0.
11:   tdvIntegerInput
On entry: the stride separating matrix column elements in the array v.
Constraint: if ${\mathbf{wantv}}=\mathrm{Nag_TRUE}$, ${\mathbf{tdv}}\ge {\mathbf{n}}$
12:   iter[n]IntegerOutput
On exit: ${\mathbf{iter}}\left[j-1\right]$ 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:   failNagError *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, ${\mathbf{tda}}=〈\mathit{\text{value}}〉$ while ${\mathbf{n}}=〈\mathit{\text{value}}〉$. These arguments must satisfy ${\mathbf{tda}}\ge {\mathbf{n}}$.
On entry, ${\mathbf{tdb}}=〈\mathit{\text{value}}〉$ while ${\mathbf{n}}=〈\mathit{\text{value}}〉$. These arguments must satisfy ${\mathbf{tdb}}\ge {\mathbf{n}}$.
On entry, ${\mathbf{tdv}}=〈\mathit{\text{value}}〉$ while ${\mathbf{n}}=〈\mathit{\text{value}}〉$. These arguments must satisfy ${\mathbf{tdv}}\ge {\mathbf{n}}$.
NE_INT_ARG_LT
On entry, ${\mathbf{n}}=〈\mathit{\text{value}}〉$.
Constraint: ${\mathbf{n}}\ge 1$.
NE_ITERATIONS_QZ
More than ${\mathbf{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=〈\mathit{\text{value}}〉$. ${\alpha }_{j}$ and ${\beta }_{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 ${\mathbf{fail}}\mathbf{.}\mathbf{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 $\left(A+E\right)x=\lambda \left(B+F\right)x$ where $‖E‖/‖A‖$ and $‖F‖/‖B‖$ are both of the order of $\mathrm{max}\left({\mathbf{tol}},\epsilon \right)$, tol being defined as in Section 5 and $\epsilon$ 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 ${\alpha }_{j}$ and ${\beta }_{j}$. It should be noted that if ${\alpha }_{j}$ and ${\beta }_{j}$ are both small for any $j$, it may be that no reliance can be placed on any of the computed eigenvalues ${\lambda }_{i}={\alpha }_{i}/{\beta }_{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. .

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.

9  Example

To find all the eigenvalues and eigenvectors of $Ax=\lambda 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 .$

9.1  Program Text

Program Text (f02bjce.c)

9.2  Program Data

Program Data (f02bjce.d)

9.3  Program Results

Program Results (f02bjce.r)
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 106, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0, "math_score": 0.9984003305435181, "perplexity": 1216.4289269649046}, "config": {"markdown_headings": false, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "plain"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "warc_path": "s3://commoncrawl/crawl-data/CC-MAIN-2014-10/segments/1394011355201/warc/CC-MAIN-20140305092235-00097-ip-10-183-142-35.ec2.internal.warc.gz"}