Teorema del círculo de Gershgorin

En matemáticas , el teorema del círculo de Gershgorin (también llamado teorema del disco de Gershgorin) se puede utilizar para acotar el espectro de una matriz cuadrada . Fue publicado por primera vez por el matemático soviético Semyon Aronovich Gershgorin en 1931. El nombre de Gershgorin se ha transliterado de diversas maneras, incluyendo Geršgorin, Gerschgorin, Gershgorin, Hershhorn y Hirschhorn.

Dejar${\displaystyle A}$ser un complejo${\displaystyle n\times n}$matriz, con entradas${\displaystyle a_{ij}}$. Para${\displaystyle i\in \{1,\dots ,n\}}$, dejar${\displaystyle R_{i}}$sea ​​la suma de los valores absolutos de las entradas no diagonales en la${\displaystyle i}$-tirar:

${\displaystyle R_{i}=\sum _{j\neq {i}}\left|a_{ij}\right|.}$

Dejar${\displaystyle D(a_{ii},R_{i})\subseteq \mathbb {C} }$ser un disco cerrado centrado en${\displaystyle a_{ii}}$con radio${\displaystyle R_{i}}$Dicho disco se denomina disco de Gershgorin.

Teorema. Cada valor propio de${\displaystyle A}$se encuentra dentro de al menos uno de los discos de Gershgorin${\displaystyle D(a_{ii},R_{i}).}$

Prueba. Dejemos${\displaystyle \lambda }$ser un valor propio de${\displaystyle A}$con el vector propio correspondiente${\displaystyle x=(x_{j})}$. Encuentra i tal que el elemento de x con el mayor valor absoluto sea${\displaystyle x_{i}}$. Desde${\displaystyle Ax=\lambda x}$, en particular tomamos el i -ésimo componente de esa ecuación para obtener:

${\displaystyle \sum _{j}a_{ij}x_{j}=\lambda x_{i}.}$

Tomando${\displaystyle a_{ii}x_{i}}$al otro lado:

${\displaystyle \sum _{j\neq i}a_{ij}x_{j}=(\lambda -a_{ii})x_{i}.}$

Por lo tanto, aplicando la desigualdad triangular y recordando que${\displaystyle {\frac {\left|x_{j}\right|}{\left|x_{i}\right|}}\leq 1}$basado en cómo elegimos i ,

${\displaystyle \left|\lambda -a_{ii}\right|=\left|\sum _{j\neq i}{\frac {a_{ij}x_{j}}{x_{i}}}\right|\leq \sum _{j\neq i}\left|{\frac {a_{ij}x_{j}}{x_{i}}}\right|=\sum _{j\neq i}\left|a_{ij}\right|{\frac {\left|x_{j}\right|}{\left|x_{i}\right|}}\leq \sum _{j\neq i}\left|a_{ij}\right|=R_{i}.}$

Corolario. Los autovalores de A también deben estar dentro de los discos de Gershgorin C j _{correspondientes} a las columnas de A.

Demostración. Aplique el teorema a A ^T teniendo en cuenta que los valores propios de la transpuesta son los mismos que los de la matriz original.

Ejemplo. Los discos de Gershgorin coinciden con el espectro solo para cada matriz diagonal .

Una forma de interpretar este teorema es que si los elementos fuera de la diagonal de una matriz cuadrada sobre los números complejos tienen normas pequeñas , los autovalores de la matriz no pueden estar lejos de los elementos de la diagonal. Por lo tanto, al reducir las normas de los elementos fuera de la diagonal, se puede intentar aproximar los autovalores de la matriz. Claro está, los elementos de la diagonal pueden cambiar al minimizar los elementos fuera de la diagonal.

El teorema no afirma que haya un disco para cada valor propio; en todo caso, los discos corresponden más bien a los ejes en${\displaystyle \mathbb {C} ^{n}}$y cada una expresa una cota sobre precisamente aquellos autovalores cuyos autoespacios están más cerca de un eje particular. En la matriz

${\displaystyle {\begin{pmatrix}3&2&2\\1&1&0\\1&0&1\end{pmatrix}}{\begin{pmatrix}a&0&0\\0&b&0\\0&0&c\end{pmatrix}}{\begin{pmatrix}3&2&2\\1&1&0\\1&0&1\end{pmatrix}}^{-1}={\begin{pmatrix}-3a+2b+2c&6a-2b-4c&6a-4b-2c\\b-a&a+(a-b)&2(a-b)\\c-a&2(a-c)&a+(a-c)\end{pmatrix}}}$

— que por construcción tiene valores propios${\displaystyle a}$,${\displaystyle b}$, y${\displaystyle c}$con autovectores${\displaystyle \left({\begin{smallmatrix}3\\1\\1\end{smallmatrix}}\right)}$,${\displaystyle \left({\begin{smallmatrix}2\\1\\0\end{smallmatrix}}\right)}$, y${\displaystyle \left({\begin{smallmatrix}2\\0\\1\end{smallmatrix}}\right)}$— es fácil ver que el disco para la fila 2 cubre${\displaystyle a}$y${\displaystyle b}$mientras que el disco para la fila 3 cubre${\displaystyle a}$y${\displaystyle c}$Sin embargo, esto es solo una feliz coincidencia; si al seguir los pasos de la demostración se encuentra que en cada vector propio el primer elemento es el más grande (cada espacio propio está más cerca del primer eje que de cualquier otro eje), entonces el teorema solo promete que el disco para la fila 1 (cuyo radio puede ser el doble de la suma de los otros dos radios) cubre los tres valores propios.

Si uno de los discos es disjunto de los demás, entonces contiene exactamente un valor propio. Sin embargo, si se encuentra con otro disco, es posible que no contenga ningún valor propio (por ejemplo,${\displaystyle A=\left({\begin{smallmatrix}0&1\\4&0\end{smallmatrix}}\right)}$o${\displaystyle A=\left({\begin{smallmatrix}1&-2\\1&-1\end{smallmatrix}}\right)}$En el caso general, el teorema se puede reforzar de la siguiente manera:

Teorema : Si la unión de k discos es disjunta de la unión de los otros n  − k discos, entonces la primera unión contiene exactamente k y la segunda n − k autovalores de A , cuando los autovalores se cuentan con sus multiplicidades algebraicas.   

Demostración : Sea D la matriz diagonal con entradas iguales a las entradas diagonales de A y sea

${\displaystyle B(t)=(1-t)D+tA.}$

Utilizaremos el hecho de que los valores propios son continuos en${\displaystyle t}$y demostrar que si algún valor propio se mueve de una de las uniones a la otra, entonces debe estar fuera de todos los discos para algún${\displaystyle t}$, lo cual es una contradicción.

La afirmación es cierta para${\displaystyle D=B(0)}$. Las entradas diagonales de${\displaystyle B(t)}$son iguales al de A , por lo tanto, los centros de los círculos de Gershgorin son los mismos, sin embargo, sus radios son t veces el de A. Por lo tanto, la unión de los k discos correspondientes de${\displaystyle B(t)}$es disjunto de la unión de los nk restantes para todos${\displaystyle t\in [0,1]}$. Los discos están cerrados, por lo que la distancia de las dos uniones para A es${\displaystyle d>0}$. La distancia para${\displaystyle B(t)}$es una función decreciente de t , por lo que siempre es al menos d . Dado que los valores propios de${\displaystyle B(t)}$son una función continua de t , para cualquier valor propio.${\displaystyle \lambda (t)}$de${\displaystyle B(t)}$en la unión de los discos k su distancia${\displaystyle d(t)}$La unión de los otros discos nk también es continua. Obviamente${\displaystyle d(0)\geq d}$y asumir${\displaystyle \lambda (1)}$reside en la unión de los discos nk . Entonces${\displaystyle d(1)=0}$, entonces existe${\displaystyle 0<t_{0}<1}$de tal manera que${\displaystyle 0<d(t_{0})<d}$Pero esto significa${\displaystyle \lambda (t_{0})}$se encuentra fuera de los discos de Gershgorin, lo cual es imposible. Por lo tanto${\displaystyle \lambda (1)}$reside en la unión de los k discos, y el teorema queda demostrado.

Observaciones: Es necesario contar los autovalores con respecto a sus multiplicidades algebraicas. He aquí un contraejemplo  :

Consideremos la matriz, $${\displaystyle {\begin{bmatrix}5&1&0&0&0\\0&5&1&0&0\\0&0&5&0&0\\0&0&0&1&1\\0&0&0&0&1\end{bmatrix}}}$$

La unión de los tres primeros discos no interseca a los dos últimos, pero la matriz tiene solo dos vectores propios, e1 y e4, y por lo tanto solo dos valores propios, lo que demuestra que el teorema es falso en su formulación. La demostración muestra únicamente que los valores propios son distintos; sin embargo, cualquier afirmación sobre su número no encaja, y este es un contraejemplo .

• La continuidad de${\displaystyle \lambda (t)}$debe entenderse en el sentido de la topología . Basta con demostrar que las raíces (como un punto en el espacio)${\displaystyle \mathbb {C} ^{n}}$) es una función continua de sus coeficientes. Nótese que la aplicación inversa que asigna raíces a coeficientes se describe mediante las fórmulas de Vieta (nótese que para los polinomios característicos que${\displaystyle a_{n}\equiv 1}$), que puede demostrarse que es un mapa abierto . Esto demuestra que las raíces en su conjunto son una función continua de sus coeficientes. Dado que la composición de funciones continuas es nuevamente continua, la${\displaystyle \lambda (t)}$como composición de solucionador de raíces y${\displaystyle B(t)}$También es continuo.
• autovalor individual${\displaystyle \lambda (t)}$podría fusionarse con otros autovalores o aparecer a partir de una división de un autovalor anterior. Esto puede confundir a la gente y hacer que cuestionen el concepto de continuidad. Sin embargo, al observar desde el espacio del conjunto de autovalores${\displaystyle \mathbb {C} ^{n}}$La trayectoria sigue siendo una curva continua, aunque no necesariamente suave en todos los puntos.

Nota añadida:

• La demostración anterior es posiblemente (in)correcta... Hay dos tipos de continuidad respecto a los autovalores: (1) cada autovalor individual es una función continua usual (tal representación existe en un intervalo real, pero puede no existir en un dominio complejo), (2) los autovalores son continuos en su conjunto en el sentido topológico (una aplicación del espacio matricial con métrica inducida por una norma a tuplas no ordenadas, es decir, el espacio cociente de C ^n bajo equivalencia de permutación con métrica inducida ). Cualquiera que sea la continuidad utilizada en una demostración del teorema del disco de Gerschgorin, debe justificarse que la suma de las multiplicidades algebraicas de los autovalores permanece invariable en cada región conexa. Una demostración que utiliza el principio del argumento del análisis complejo no requiere ningún tipo de continuidad de autovalores. ^{[ 1 ]} Para una breve discusión y aclaración, véase. ^{[ 2 ]}

El teorema del círculo de Gershgorin es útil para resolver ecuaciones matriciales de la forma Ax = b para x , donde b es un vector y A es una matriz con un número de condición grande .

En este tipo de problemas, el error en el resultado final suele ser del mismo orden de magnitud que el error en los datos iniciales multiplicado por el número de condición de A. Por ejemplo, si b se conoce con seis decimales y el número de condición de A es 1000, solo podemos estar seguros de que x es preciso con tres decimales. Para números de condición muy altos, incluso errores muy pequeños debidos al redondeo pueden magnificarse hasta tal punto que el resultado carezca de sentido.

Sería conveniente reducir el número de condición de A. Esto se puede lograr mediante un precondicionamiento : se construye una matriz P tal que P ≈ A ⁻¹ , y luego se resuelve la ecuación PAx = Pb para x . Sería ideal usar la inversa exacta de A , pero calcular la inversa de una matriz es algo que queremos evitar debido al alto costo computacional.

Ahora bien, dado que PA ≈ I , donde I es la matriz identidad , los valores propios de PA deberían estar todos cerca de 1. Según el teorema del círculo de Gershgorin, cada valor propio de PA se encuentra dentro de un área conocida, por lo que podemos hacer una estimación aproximada de cuán buena fue nuestra elección de P.

Utilice el teorema del círculo de Gershgorin para estimar los valores propios de:

${\displaystyle A={\begin{bmatrix}10&1&0&1\\0.2&8&0.2&0.2\\1&1&2&1\\-1&-1&-1&-11\\\end{bmatrix}}.}$

Comenzando con la primera fila, tomamos el elemento en la diagonal, a _ii , como centro del disco. Luego tomamos los elementos restantes en la fila y aplicamos la fórmula.

${\displaystyle \sum _{j\neq i}|a_{ij}|=R_{i}}$

para obtener los siguientes cuatro discos:

${\displaystyle D(10,2),\;D(8,0.6),\;D(2,3),\;{\text{and}}\;D(-11,3).}$

Nótese que podemos mejorar la precisión de los dos últimos discos aplicando la fórmula a las columnas correspondientes de la matriz, obteniendo${\displaystyle D(2,1.2)}$y${\displaystyle D(-11,2.2)}$.

Los valores propios son -10,870, 1,906, 10,046, 7,918. Nótese que esta es una matriz diagonalmente dominante (por columna) :${\textstyle |a_{ii}|>\sum _{j\neq i}|a_{ji}|}$Esto significa que la mayor parte de la matriz se encuentra en la diagonal, lo que explica por qué los valores propios están tan cerca de los centros de los círculos y las estimaciones son muy buenas. Para una matriz aleatoria , cabría esperar que los valores propios estuvieran considerablemente más alejados de los centros de los círculos.

Si bien el teorema original del círculo de Gershgorin se aplica a todas las matrices cuadradas complejas, se pueden extraer conclusiones más sólidas cuando la matriz tiene una estructura adicional, como ser simétrica o irreducible.

Para una matriz simétrica real${\displaystyle A\in \mathbb {R} ^{n\times n}}$Los discos de Gershgorin se reducen a intervalos en la recta real. En este caso:

• Cada valor propio de${\displaystyle A}$se encuentra dentro de al menos uno de sus intervalos de Gershgorin.
• Si los intervalos${\displaystyle I_{1},\dots ,I_{n}}$se puede dividir en dos grupos disjuntos: uno con${\displaystyle p}$intervalos y el otro con${\displaystyle n-p}$— y la unión de cada grupo es disjunta del otro, entonces el grupo con${\displaystyle p}$intervalos contiene exactamente${\displaystyle p}$valores propios (contando multiplicidades algebraicas), y el otro grupo contiene${\displaystyle n-p}$.

Además, un perfeccionamiento realizado por Olga Taussky proporciona una estructura adicional para matrices irreducibles:

• Si un valor propio se encuentra en un extremo de un intervalo de Gershgorin, y la matriz es irreducible, entonces ese valor propio es un extremo de cada intervalo de Gershgorin.

Este resultado —conocido como el Teorema de Taussky— destaca cómo la geometría de los intervalos de Gershgorin restringe estrictamente las ubicaciones de los valores propios cuando la matriz presenta suficiente conectividad y estructura. ^{[ 3 ]}

• Para matrices con entradas no negativas, véase el teorema de Perron-Frobenius .
• Matriz doblemente estocástica
• Matriz estable de Hurwitz : matriz cuyos valores propios tienen parte real negativa. 
• Joel Lee Brenner
• Matriz de Metzler : matriz cuadrada cuyos elementos fuera de la diagonal son no negativos. 
• La desigualdad de Muirhead
• La desigualdad de Bendixson
• Teorema de Schur-Horn : Caracteriza la diagonal de una matriz hermitiana con valores propios dados. 

• Gerschgorin, S. (1931), "Über die Abgrenzung der Eigenwerte einer Matrix" , Izv. Akád. Nauk. URSS Otd. Fiz.-Mat. Nauk ( en alemán), 6 : 749–754.
• Varga, Richard S. (2004), Geršgorin y sus círculos , Berlín: Springer-Verlag, ISBN 3-540-21100-4( Errata ).
• Varga, Richard S. (2002), Análisis iterativo de matrices (2.ª  ed.), Springer-Verlag1.ª ed., Prentice Hall, 1962.
• Golub, GH ; Van Loan, CF (1996), Matrix Computations , Baltimore: Johns Hopkins University Press, p.  320, ISBN 0-8018-5413-X.

• "Teorema del círculo de Gershgorin" . PlanetMath .
• Eric W. Weisstein. " Teorema del círculo de Gershgorin ". De MathWorld — Un recurso web de Wolfram.
• Biografía de Semyon Aranovich Gershgorin en MacTutor