Kazragis Gershgorin Circle Theorem For instance, it lets you look at the matrix. Moreover, many posts use MathML, which is, currently only supported in Mozilla. Tom Leinster on September 16, Therefore, applying the triangle inequality. For very high condition numbers, even very small errors due to rounding can be magnified to such an extent that the result is meaningless. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.
|Published (Last):||17 May 2010|
|PDF File Size:||1.61 Mb|
|ePub File Size:||17.82 Mb|
|Price:||Free* [*Free Regsitration Required]|
Together with their corresponding eigenvector, they form the fundamental basis for many applications. Calculating eigenvalues from a given matrix is straightforward and implementations exist in many libraries. But sometimes the concrete matrix is not known in advance, e. In this case, it may be good to give at least some estimation of the range in which the eigenvalues can lie. As the name of this article suggests, there is a theorem intended for this use case and which will be discussed here.
Before looking into the theorem though, let me remind the reader that eigenvalues may be complex valued even for a matrix which contains only real numbers. For the theorem, the concept of a Gershgorin disc is relevant. Markers show the label for the disc centres and eigenvalues.
The rectangle is a rough estimation of the possible range where the eigenvalues lie see below. Indeed, all eigenvalues lie in the blue area defined by the discs. But you also see from this example that not all discs have to contain an eigenvalue the theorem does not state that each disc has one eigenvalue.
This is why the theorem makes only a statement about the complete union and not each disc independently. This defines nothing else than a rectangle containing all discs. Of course, the rectangle is an even more inaccurate estimation as the discs already are, but the ranges are easier to handle e.
Furthermore, if we have more information about the matrix, like that it is symmetric and real-valued and therefore contains only real eigenvalues , we can discard the complex range completely. In summary, with the help of the Gershgorin circle theorem, it is very easy to give an estimation of the eigenvalues of some matrix. We only need to look at the diagonal elements and corresponding sum of the rest of the row and get a first estimate of the possible range.
In the next part, I want to discuss why this estimation is indeed correct. This is a valid assumption since one component must be the maximum and there is no restriction on the component number to choose for the next discussion. Last but not least, the product is split up. For complex values, this defines the previously discussed discs. Two notes on this insight: The result is only valid for the maximum component of the eigenvector.
In the explanation above only one eigenvector was considered. But usually, there are more e. The result is therefore true for each maximum component of each eigenvector. This also implies that not every eigenvector gives new information.
It may be possible that for multiple eigenvectors the first component is the maximum. In this case, one eigenvector would have been sufficient. What the theorem now does is some kind of worst-case estimate. We now know that if one component of some eigenvector is the maximum, the row corresponding to this component defines a range in which the eigenvalue must lie.
In this case, we need to consider all diagonal elements and their corresponding absolute sum of the rest of the row. This is exactly what is done in the example from above. There is another nice feature which can be derived from the theorem when we have disjoint discs. This will be discussed in the next section. Additional statements can be extracted from the theorem when we deal with disjoint disc areas 3. With other words: we have two disjoint areas. The question is: does this gives us additional information?.
Indeed, it is possible to state that there is exactly one eigenvalue in the third disc. Then, each joined area defined by the discs contains so many eigenvalues as discs contributed to the area. In the example, we have exactly one eigenvalue in the third disc and exactly two eigenvalues somewhere in the union of disc one and two 4. Why is it possible to restrict the estimation when we deal with disjoint discs?
To see this, let me first remind you that the eigenvalues of any diagonal matrix are exactly the diagonal elements itself. I chose a 2-by-2 matrix because this point is easier to see here. Finding roots of higher dimensional matrices can suddenly become much more complicated.
But the statement of continuously increasing eigenvalues stays true, even for matrices with higher dimensions. The principle is simple: just add both matrices together and apply the circle theorem on the resulting matrix. As you can see, the eigenvalues start at the disc centres because here only the diagonal elements remain, i.
But note again that this transition is smooth: no eigenvalue suddenly jumps to a completely different position. Note also that at some point the discs for the first and second eigenvalue merge together.
List of attached files: GershgorinCircle. The absolute value is necessary here because the components may be complex. Intuitively, this means that the way over a detour is always longer or equal to the direct way.
The following discussion is based on the statements of these slides. Overview 1 article found. Please send a mail to you can use my PGP key for encryption.
Gershgorin circle theorem
This may confuse people and questioning the concept of continuous. The proof given above is arguably in correct There are two types of continuity concerning eigenvalues: 1 each individual eigenvalue is a usual continuous function such a representation does exist on a real interval but may not exist on a complex domain , 2 eigenvalues are continuous as a whole in the topological sense a mapping from the matrix space with metric induced by a norm to unordered tuples, i. Whichever continuity is used in a proof of the Gerschgorin disk theorem, it should be justified that the sum of algebraic multiplicities of eigenvalues remains unchanged on each connected region. A proof using the argument principle of complex analysis requires no eigenvalue continuity of any kind. In this kind of problem, the error in the final result is usually of the same order of magnitude as the error in the initial data multiplied by the condition number of A. For instance, if b is known to six decimal places and the condition number of A is then we can only be confident that x is accurate to three decimal places.
Subscribe to RSS
Visualize the Gerschgorin Circle Theorem