Localization of Eigenvalues
The estimates of the locations of the eigenvalues follows from Gerschgorin's theorem:
Given an n × n matrix A the eigenvalues of A lie in the union of the disks in the Complex plane:
and similarly
| z - a_{ii} | ≤ r_{i}, where r_{i} = | a_{i,1} | + ··· + | a_{i,n} | - | a_{i,i} |
Given an n × n matrix A the eigenvalues of A lie in the union of the disks in the Complex plane:
| z - a_{ii} | ≤ r_{i}, where r_{i} = | a_{1,i} | + ··· + | a_{n,i} | - | a_{i,i} |
In the event that the matrix A is symmetric, the eigenvalues of A are real and Gerschgorin's theorem becomes:
Given an n × n symmetric matrix A the eigenvalues of A lie in the union of the closed intervals on the Real line:
and
a_{ii} - r_{i} ≤ x ≤ a_{ii} + r_{i}, where r_{i} = | a_{i,1} | + ··· + | a_{i,n} | - | a_{i,i} |
Given an n × n symmetric matrix A the eigenvalues of A lie in the union of the closed intervals on the Real line:
a_{ii} - r_{i} ≤ x ≤ a_{ii} + r_{i}, where r_{i} = | a_{1,i} | + ··· + | a_{n,i} | - | a_{i,i} |
Function List
- void Gerschgorin( double *A, int n, double row_radii[ ], double col_radii[ ] )
Given the n×n matrix A, the routine Gerschgorin calculates both the row radii, row_radii, and column radii, col_radii, such that in the Complex plane an eigenvalue µ is contained in the union of the disks | µ - A[i][i] | ≤ row_radii[i] for i = 0, 1, …, n-1 or in the union of the disks | µ - A[i][i] | ≤ col_radii[i] for i = 0, 1, …, n-1. The arrays row_radii and col_radii should be dimensioned at least n in the calling routine. The matrix A is preserved.
- void Gerschgorin_Symmetric( double *A, int n, double lower_bound[ ], double upper_bound[ ], int sort )
For a symmetric square matrix the eigenvalues are Real. Given the n × n symmetric matrix A, the routine Gerschgorin_Symmetric calculates the lower bounds, lower_bound[] and the upper bounds, upper_bound[] such that on the Real line an eigenvalue µ is contained in the union of the intervals
lower_bound[i] ≤ µ ≤ upper_bound[i] for i = 0, 1, …, n-1.
The argument sort specifies the order of lower and upper bounds which are returned. If sort = 0, then the order returned is the same as the order found. If sort < 0, then the order returned is upper bound decreasing order and if sort > 0, then the order returned is lower bound increasing order. The arrays lower_bound and upper_bound should be dimensioned at least n in the calling routine. The matrix A is preserved.
- void Gerschgorin_Symmetric_lt( double *A, int n, double lower_bound[ ], double upper_bound[ ], int sort )
This routine differs from Gerschgorin_Symmetric only in the storage for the matrix A. This routine assumes that A is a symmetric matrix stored in lower triangular form. The arrays lower_bound and upper_bound should be dimensioned at least n in the calling routine. The matrix A is preserved.
- void Gerschgorin_Symmetric_ut( double *A, int n, double lower_bound[ ], double upper_bound[ ], int sort )
This routine differs from Gerschgorin_Symmetric only in the storage for the matrix A. This routine assumes that A is a symmetric matrix stored in upper triangular form. The arrays lower_bound and upper_bound should be dimensioned at least n in the calling routine. The matrix A is preserved.
C Source Code
- The file, gerschgorin.c, contains the routine Gerschgorin( ).
- The file, gerschgorin_symmetric.c, contains the routine Gerschgorin_Symmetric( ).
- The file, gerschgorin_symmetric_lt.c, contains the routine
Gerschgorin_Symmetric_lt( ).
- The file, gerschgorin_symmetric_ut.c, contains the routine
Gerschgorin_Symmetric_ut( ).