Eigenvalues and Eigenvectors



Eigenvalues and Eigenvectors of a real Symmetric Matrix

Symmetric Matrices

For a real symmetric matrix all the eigenvalues are real. If only the dominant eigenvalue is wanted, then the Rayleigh method maybe used or the Rayleigh quotient method maybe used. The Rayleigh methods may fail however if the dominant eigenvalue is not unique. If all the eigenvalues are wanted but not the eigenvectors then Given's bisection algorithm can be used after first tridiagonalizing the symmetric matrix. If all the eigenvalues and corresponding eigenvectors are wanted then Jacobi's cyclic method can be used or if the matrix is tridiagonal then the QL algorithm as presented below may be applied.

Function List

  • int Eigenvalue_Rayleigh_Method( double *A, int n, double *eigenvalue, double x[ ], double x0[ ], double tolerance, int max_tries )

    Rayleigh's method is a variant of the power method for estimating the dominant eigenvalue of a symmetric matrix. The process may not converge if the dominant eigenvalue is not unique. Given the n×n real symmetric matrix A and an initial estimate of the eigenvector, x0, the method then normalizes x0, calculates x = Ax0 and sets µ = xTx0. The process is then repeated after setting x0 = x until the relative absolute change in µ is less than the preassigned tolerance at which time the process terminates successfully or until the number of attempts exceeds max_tries at which time the process terminates unsuccessfully.
    The function Eigenvalue_Rayleigh_Method is used if the matrix A is stored as a full symmetric matrix, the function Eigenvalue_Rayleigh_Method_lt is used if the matrix A is stored in lower triangular form and the function Eigenvalue_Rayleigh_Method_ut is used if the matrix A is stored in upper triangular form.
    The function returns the number of iterations performed if successful and -1 if more than max_tries iterations are necessary, -2 if the initial vector or subsequent vector is 0 and -3 if the estimate for the dominant eigenvalue is 0.

  • int Eigenvalue_Rayleigh_Method_lt( double *A, int n, double *eigenvalue, double x[ ], double x0[ ], double tolerance, int max_tries )

    This routine is the same as Eigenvalue_Rayleigh_Method( ), described above, with the exception that the matrix A is stored in lower triangular form.

  • int Eigenvalue_Rayleigh_Method_ut( double *A, int n, double *eigenvalue, double x[ ], double x0[ ], double tolerance, int max_tries )

    This routine is the same as Eigenvalue_Rayleigh_Method( ), described above, with the exception that the matrix A is stored in upper triangular form.

  • int Rayleigh_Quotient_Method( double *A, int n, double *eigenvalue, double x0[ ], double tolerance, int max_tries )

    Rayleigh's quotient method is a variant of the inverse power method for estimating the dominant eigenvalue of a symmetric matrix. The process may not converge if the dominant eigenvalue is not unique. Given the n × n real symmetric matrix A and an initial estimate of the eigenvector, x0, the method then normalizes x0, calculates
    µ = x0TAx0 and solves ( A - µI ) x = x0 for x. The process is then repeated after setting x0 = x until the relative absolute change in µ is less than the preassigned tolerance at which time the process terminates successfully or until the number of attempts exceeds max_tries at which time the process terminates unsuccessfully. This routine has better convergence properties than that of the Rayleigh method and is usually used after the Rayleigh method has obtained a close estimate of the dominant eigenvalue and corresponding eigenvector.
    The function returns the number of iterations performed if successful and -1 if more than max_tries iterations are necessary, -2 if the initial vector or subsequent vector is 0, -3 if the estimate for the dominant eigenvalue is 0 and -4 if there is not enough memory available for working storage.

  • int Givens_Bisection_Method( double diagonal[ ], double off_diagonal[ ], double eigenvalues[ ], double relative_tolerance, int n )

    Given the n×n real tridiagonal symmetric matrix A with diagonal, diagonal, and off-diagonals, off_diagonal, the routine Givens_Bisection_Method uses Gerschgorin's theorem to obtain bounds for the eigenvalues and then the bisection method to estimate the eigenvalues within the user specified relative tolerance, relative_tolerance. The off-diagonal elements begin at off_diagonal[1], off_diagonal[0] is set to 0. The results are returned in the array eigenvalues. The function returns 0 if successful and -1 if there is not enough memory for working storage.

  • int QL_Tridiagonal_Symmetric_Matrix( double diagonal[ ], double off_diagonal[ ], double *U, int n, int max_iteration_count )

    Given the n×n real tridiagonal symmetric matrix A with diagonal, diagonal, and off-diagonals, off_diagonal, the routine QL_Tridiagonal_Symmetric_Matrix uses QL algorithm with implicit shifts of the origin to estimate the eigenvalues and eigenvectors. The off-diagonal elements begin at off_diagonal[1], off_diagonal[0] is set to 0. The eigenvalues are returned in the array diagonal. The n×n matrix U should be set to the transformation matrix if the original matrix was tridiagonalized or set to the identity matrix if the original matrix is tridiagonal. Upon return, U contains the eigenvectors of the original matrix, the ith column being the eigenvector corresponding the the ith eigenvalue, diagonal[i]. The function returns a 0 if successful and a -1 if the process failed to converge within max_iteration_count iterations.
     
  • void Jacobi_Cyclic_Method( double eigenvalues[ ], double *eigenvectors, double *A, int n )

    Given the n × n real symmetric matrix A, the routine Jacobi_Cyclic_Method calculates the eigenvalues and eigenvectors of A by successively sweeping through the matrix A annihilating off-diagonal non-zero elements by a rotation of the row and column in which the non-zero element occurs. The input matrix A is modified during the process. The eigenvalues are returned in the array eigenvalues which should be dimensioned at least n in the calling routine. The eigenvectors are returned in the n×n matrix eigenvectors, the ith column being the eigenvector corresponding the the ith eigenvalue, eigenvalue[i].

C Source Code