Gershgorin circle theorem

Gershgorin circle theorem

In mathematics, the Gershgorin circle theorem may be used to bound the spectrum of a square matrix. It was first published by the Belarusian mathematician Semyon Aranovich Gershgorin in 1931. The spelling of S. A. Gershgorin's name has been transliterated in several different ways, including Geršgorin, Gerschgorin and Gershgorin.

tatement and proof

Let "A" be a complex "n"×"n" matrix, with entries ("a""ij"). For "i" ∈ {1, … "n"} write "R""i" = ∑"j" ≠ "i" |"a""ij"| where |"a""ij"| denotes the absolute value of "a""ij". Let "D"("a""ii", "R""i") be the closed disc centered at "a""ii" with radius "R""i". Such a disc is called a "Gershgorin disc".

Theorem: Every eigenvalue of "A" lies within at least one of the Gershgorin discs "D"("a""ii", "R""i").

"Proof": Let λ be an eigenvalue of "A" and let x = ("x""j") be a corresponding eigenvector. Let "i" ∈ {1, … "n"} be chosen so that |"x""i"| = max"j" |"x""j"|. Then |"x""i"| > 0, otherwise x = 0. Since x is an eigenvector, "A"x = λx or equivalent

: sum_{j} a_{ij} x_{j} = lambda x_{i} quad forall i in 1 ldots n

so, splitting the sum, we get

: sum_{j eq i} a_{ij} x_{j} = lambda x_{i}-a_{ii} x_{i}

We may then divide both sides by x_{i} (choosing i as we explained we can be sure that x_{i} eq 0 ) and take the absolute value to obtain

: |lambda - a_{ii}| = left|frac{sum_{j e i} a_{ij} x_{j{x_{i ight| le sum_{j e i} |a_{ij}| = R_i.

where the last inequality is valid because left| frac{x_{j{x_{i ight| leq 1 quad forall j eq i

Corollary: The eigenvalues of "A" must also lie within the Gershgorin discs "C""j" corresponding to the columns of "A".

"Proof": Apply the Theorem to "A"T.

Example For a diagonal matrix, the Gershgorin discscoincide with the spectrum. Conversely, if the Gershgorin discs coincidewith the spectrum, the matrix is diagonal.

Discussion

One way to interpret this theorem is that if the off-diagonal entries of a square matrix over the complex numbers have small norms, the eigenvalues of the matrix cannot be "far from" the diagonal entries of the matrix. Therefore, by reducing the norms of off-diagonal entries one can attempt to approximate the eigenvalues of the matrix. Of course, diagonal entries may change in the process of minimizing off-diagonal entries.

Application

The Gershgorin circle theorem is useful in solving matrix equations of the form "Ax" = "b" for "x" where "b" is a vector and "A" is a matrix with a large condition number.

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 1000 then we can only be confident that "x" is accurate to three decimal places. For very high condition numbers, even very small errors due to rounding can be magnified to such an extent that the result is meaningless.

It would be good to reduce the condition number of "A". This can be done by preconditioning: A matrix "P" such that "P" ≈ "A"−1 is constructed, and then the equation "PAx" = "Pb" is solved for "x". Using the "exact" inverse of "A" would be nice but finding the inverse of a matrix is generally very difficult.

Now, since "PA" ≈ "I" where "I" is the identity matrix, the eigenvalues of "PA" should all be close to 1. By the Gerschgorin circle theorem, every eigenvalue of "PA" lies within a known area and so we can form a rough estimate of how good our choice of "P" was.

References

* Gerschgorin, S. "Über die Abgrenzung der Eigenwerte einer Matrix." Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk 7, 749-754, 1931
* Varga, R. S. "Geršgorin and His Circles." Berlin: Springer-Verlag, 2004. ISBN 3-540-21100-4. [http://www.math.kent.edu/~varga/pub/corrections.pdf Errata] .

External links

*planetmath reference|id=3709|title=Gershgorin's circle theorem
* Eric W. Weisstein. " [http://mathworld.wolfram.com/GershgorinCircleTheorem.html Gershgorin Circle Theorem] ." From MathWorld--A Wolfram Web Resource.
* Semyon Aranovich Gershgorin biography at [http://www-history.mcs.st-andrews.ac.uk/Mathematicians/Gershgorin.html MacTutor]


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • List of circle topics — This list of circle topics includes things related to the geometric shape, either abstractly, as in idealizations studied by geometers, or concretely in physical space. It does not include metaphors like inner circle or circular reasoning in… …   Wikipedia

  • Perron–Frobenius theorem — In linear algebra, the Perron–Frobenius theorem, proved by Oskar Perron (1907) and Georg Frobenius (1912), asserts that a real square matrix with positive entries has a unique largest real eigenvalue and that the corresponding… …   Wikipedia

  • Semyon Aranovich Gershgorin — (August 24, 1901 – May 30, 1933) was a Soviet (born in Belarus) mathematician. He began as a student at the Petrograd Technological Institute in 1923, became a Professor in 1930, and was given an appointment at the Leningrad Mechanical… …   Wikipedia

  • Theoreme de Gershgorin — Théorème de Gerschgorin En analyse numérique, le théorème de Gerschgorin est un résultat permettant de borner a priori les valeurs propres d une matrice carrée. Il a été publié en 1931 par le mathématicien biélorusse Semion Aronovitch Gershgorin …   Wikipédia en Français

  • Théorème de Gershgorin — Théorème de Gerschgorin En analyse numérique, le théorème de Gerschgorin est un résultat permettant de borner a priori les valeurs propres d une matrice carrée. Il a été publié en 1931 par le mathématicien biélorusse Semion Aronovitch Gershgorin …   Wikipédia en Français

  • Théorème de gershgorin — Théorème de Gerschgorin En analyse numérique, le théorème de Gerschgorin est un résultat permettant de borner a priori les valeurs propres d une matrice carrée. Il a été publié en 1931 par le mathématicien biélorusse Semion Aronovitch Gershgorin …   Wikipédia en Français

  • List of mathematics articles (G) — NOTOC G G₂ G delta space G networks Gδ set G structure G test G127 G2 manifold G2 structure Gabor atom Gabor filter Gabor transform Gabor Wigner transform Gabow s algorithm Gabriel graph Gabriel s Horn Gain graph Gain group Galerkin method… …   Wikipedia

  • Diagonally dominant matrix — In mathematics, a matrix is said to be diagonally dominant if for every row of the matrix, the magnitude of the diagonal entry in a row is larger than or equal to the sum of the magnitudes of all the other (non diagonal) entries in that row. More …   Wikipedia

  • Гершгорин, Семён Аронович — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете …   Википедия

  • Théorème de Gerschgorin — En analyse numérique, le théorème de Gerschgorin est un résultat permettant de borner a priori les valeurs propres d une matrice carrée. Il a été publié en 1931 par le mathématicien biélorusse Semyon Aranovich Gershgorin (en). Son nom peut… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”