7
$\begingroup$

In order to estimate the eigenvalues of a real symmetric $n\times n$ matrix, I intend to use the Gershgorin Circle Theorem. Unfortunately, the examples one might find on the internet are a bit confusing; What would be the mathematical formula for deriving the eigenvalue estimates?

I understand that certain disks are formed, each centered at the diagonal entry, with the radius equal to the summation of absolute values of the associated off-diagonal row entries. (The example from

http://en.wikipedia.org/wiki/Gershgorin_circle_theorem

is clear with the disks, but not with the eigenvalue estimation) Which steps to take from this point to get the estimates on the eigenvalues?

From Theorem 2.1 in

http://buzzard.ups.edu/courses/2007spring/projects/brakkenthal-paper.pdf

one could understand the eigenvalue $ranges$, but the example 2.3 from the above paper gives concrete eigenvalue estimates (some of which are negative). I would appreciate if someone explains this. I'm interested in the largest (positive) and smallest (possibly negative) eigenvalue estimates.

$\endgroup$
  • 1
    $\begingroup$ A substantial reference on Gershgorin is Richard Varga: Gersgorin and his circles. $\endgroup$ – Martin Peters Oct 20 '14 at 10:52
12
$\begingroup$

In gerschgorin's theorem, the diagonal entries $A_{ii}$ of the matrix are the eigenvalue estimates, and the radii $r_i$ of the Gerschgorin disks are corresponding error bounds. Thus $\min_i A_{ii}-r_i$ is a lower bound on the eigenvalues, and $\max_i A_{ii}+r_i$ is an upper bound.

Note that these bounds are generally poor unless the off-diagonal entries are tiny. in the latter case, one can get excellent bounds by an appropriate prior similarity transform of the matrix with as suitable scaling matrix.

To get good bounds for a general matrix, one must compute an approximate eigensystem and then express the matrix in this basis by a simiarity transform. This doesn't change the eigenvalues but makes the off-diagonal entries small, so that the above applies.

$\endgroup$
  • $\begingroup$ This is a great approach! $\endgroup$ – Paul Mar 30 '12 at 14:51
7
$\begingroup$

Gershgorin's Theorem provides a bound on where to find each eigenvalue, but it doesn't provide an algorithm to actually calculate them. You can take an initial guess $x_0$ within each Gershgorin disk, and use the shifted inverse power method to find the eigenvalue closest to $x_{0}$. But there is no guarantee that using one initial guess per Gershgorin disk will will necessarily lead to finding all eigenvalues, unless you know ahead of time that the disks are disjoint.

$\endgroup$
5
$\begingroup$

If you to learn more about this, you might take a look into Horn and Johnson's book on matrix analysis, they have a whole chapter on eigenvalue estimation with Gershgorin disks.

$\endgroup$
  • $\begingroup$ Ok, I'll try to find it. $\endgroup$ – usero Mar 29 '12 at 19:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.