Teorema del círculo de Gershgorin

Limitado a valores propios

En matemáticas , el teorema del círculo de Gershgorin puede utilizarse para limitar 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 ha sido transliterado de varias maneras diferentes, incluidas Geršgorin, Gerschgorin, Gershgorin, Hershhorn y Hirschhorn.

Declaración y prueba

Sea una matriz compleja , con entradas . Porque sea la suma de los valores absolutos de las entradas no diagonales en la -ésima fila: ${\displaystyle A}$ ${\displaystyle n\times n}$ ${\displaystyle a_{ij}}$ ${\displaystyle i\in \{1,\dots ,n\}}$ ${\displaystyle R_{i}}$ ${\displaystyle i}$

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

Sea un disco cerrado centrado en con radio . Un disco de este tipo se llama disco de Gershgorin. ${\displaystyle D(a_{ii},R_{i})\subseteq \mathbb {C} }$ ${\displaystyle a_{ii}}$ ${\displaystyle R_{i}}$

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

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

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

Llevando al otro lado: ${\displaystyle a_{ii}}$

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

Por lo tanto, aplicando la desigualdad del triángulo y recordando que según cómo elegimos i , ${\displaystyle {\frac {\left|x_{j}\right|}{\left|x_{i}\right|}}\leq 1}$

${\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|a_{ij}\right|=R_{i}.}$

Corolario. Los valores propios de A también deben encontrarse dentro de los discos de Gershgorin _Cj correspondientes a las columnas de A.

Prueba. Aplique el teorema a A ^T reconociendo que los valores propios de la transpuesta son los mismos que los de la matriz original.

Ejemplo. Para una matriz diagonal , los discos de Gershgorin coinciden con el espectro. Por el contrario, si los discos de Gershgorin coinciden con el espectro, la matriz es diagonal.

Discusión

Una forma de interpretar este teorema es que si las entradas fuera de la diagonal de una matriz cuadrada sobre números complejos tienen normas pequeñas , los valores propios de la matriz no pueden estar "lejos de" las entradas diagonales de la matriz. Por lo tanto, al reducir las normas de las entradas fuera de la diagonal se puede intentar aproximar los valores propios de la matriz. Por supuesto, las entradas diagonales pueden cambiar en el proceso de minimizar las entradas 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 , y cada uno expresa un límite precisamente en aquellos valores propios cuyos espacios propios están más cerca de un eje en particular. en la matriz ${\displaystyle \mathbb {C} ^{n}}$

${\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 , , y con vectores propios , , y — es fácil ver que el disco de la fila 2 cubre y mientras que el disco de la fila 3 cubre y . Sin embargo, esto es sólo una feliz coincidencia; Si sigue los pasos de la prueba, 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), por lo que el teorema solo promete que el disco de la fila 1 (cuyo radio puede ser el doble de la suma de los otros dos radios) cubre los tres valores propios. ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle c}$ ${\displaystyle \left({\begin{smallmatrix}3\\1\\1\end{smallmatrix}}\right)}$ ${\displaystyle \left({\begin{smallmatrix}2\\1\\0\end{smallmatrix}}\right)}$ ${\displaystyle \left({\begin{smallmatrix}2\\0\\1\end{smallmatrix}}\right)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle c}$

Fortalecimiento del teorema.

Si uno de los discos está separado 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, o ). En el caso general el teorema se puede reforzar de la siguiente manera: ${\displaystyle A=\left({\begin{smallmatrix}0&1\\4&0\end{smallmatrix}}\right)}$ ${\displaystyle A=\left({\begin{smallmatrix}1&-2\\1&-1\end{smallmatrix}}\right)}$

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 última n  -  k valores propios de A , cuando los valores propios se cuentan con sus multiplicidades algebraicas.

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

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

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

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

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

Considere 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 primeros 3 discos no intersecta a los últimos 2, pero la matriz tiene solo 2 vectores propios, e1,e4, y por lo tanto solo 2 valores propios, lo que demuestra que el teorema es falso en su formulación. La demostración de muestra sólo que los valores propios son distintos, sin embargo cualquier afirmación sobre el número de ellos es algo que no encaja, y este es un contraejemplo.

• La continuidad de debe entenderse en el sentido de topología . Basta demostrar que las raíces (como punto en el espacio ) son función continua de sus coeficientes. Tenga en cuenta que el mapa inverso que asigna raíces a coeficientes se describe mediante las fórmulas de Vieta (nota para los polinomios característicos que ), que se puede demostrar como 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, el solucionador de composición de raíces también es continua. ${\displaystyle \lambda (t)}$ ${\displaystyle \mathbb {C} ^{n}}$ ${\displaystyle a_{n}\equiv 1}$ ${\displaystyle \lambda (t)}$ ${\displaystyle B(t)}$
• El valor propio individual podría fusionarse con otros valores propios o aparecer a partir de una división del valor propio anterior. Esto puede confundir a la gente y cuestionar el concepto de continuo. Sin embargo, cuando se ve desde el espacio del conjunto de valores propios , la trayectoria sigue siendo una curva continua, aunque no necesariamente suave en todas partes. ${\displaystyle \lambda (t)}$ ${\displaystyle \mathbb {C} ^{n}}$

Observación agregada:

• La prueba proporcionada anteriormente es posiblemente (in)correcta... Hay dos tipos de continuidad con respecto a los valores propios: (1) cada valor propio individual es una función continua habitual (tal representación existe en un intervalo real pero puede no existir en un dominio complejo), (2) los valores propios son continuos como un todo en el sentido topológico (un mapeo del espacio matricial con métrica inducida por una norma a tuplas desordenadas, es decir, el espacio cociente de C ^n bajo equivalencia de permutación con inducida métrico). Cualquiera que sea la continuidad que se utilice en una prueba del teorema del disco de Gerschgorin, debería justificarse que la suma de multiplicidades algebraicas de valores propios permanezca sin cambios en cada región conectada. Una prueba que utiliza el principio argumental del análisis complejo no requiere continuidad de valores propios de ningún tipo. ^[1] Para una breve discusión y aclaración, ver. ^[2]

Solicitud

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 problema, 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, entonces sólo podemos estar seguros de que x tiene una precisión de tres decimales. Para números de condición muy altos, incluso los errores más pequeños debidos al redondeo pueden magnificarse hasta tal punto que el resultado no tenga sentido.

Sería bueno reducir el número de condición de A . Esto se puede hacer precondicionando : Se construye una matriz P tal que P ≈ A ⁻¹ , y luego se resuelve la ecuación PAx = Pb para x . Usar la inversa exacta de A sería bueno, pero encontrar la inversa de una matriz es algo que queremos evitar debido al gasto computacional.

Ahora, dado que PA ≈ I donde I es la matriz identidad, todos los valores propios de PA deberían estar cercanos a 1. Según el teorema del círculo de Gershgorin, cada valor propio de PA se encuentra dentro de un área conocida y, por lo tanto, podemos formar una estimación aproximada de qué tan bueno es. nuestra elección de P fue.

Ejemplo

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

Este diagrama muestra los discos en amarillo derivados de los valores propios. Los dos primeros discos se superponen y su unión contiene dos valores propios. El tercer y cuarto disco están separados de los demás y contienen un valor propio cada uno.

${\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 fila uno, tomamos el elemento en diagonal, a _ii como centro del disco. Luego tomamos los elementos restantes de 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).}$

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

Los valores propios son -10,870, 1,906, 10,046, 7,918. Tenga en cuenta que esta es una matriz diagonalmente dominante (de columna) : . Esto significa que la mayor parte de la matriz está en 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, esperaríamos que los valores propios estuvieran sustancialmente más lejos de los centros de los círculos. ${\textstyle |a_{ii}|>\sum _{j\neq i}|a_{ji}|}$

Ver también

• Para matrices con entradas no negativas, consulte el teorema de Perron-Frobenius .
• Matriz doblemente estocástica
• matriz de hurwitz
• Joel Lee Brenner
• matriz de metzler
• La desigualdad de Muirhead
• La desigualdad de Bendixson
• Teorema de Schur-Horn

Referencias

1. Roger A. Horn y Charles R. Johnson (2013), Matrix Analysis , segunda edición, Cambridge University Press ISBN  9780521548236 [https://www.cambridge.org/ca/academic/subjects/mathematics/algebra/matrix-analysis- 2da edición
2. Chi-Kwong Li y Fuzhen Zhang (2019), Continuidad de valores propios y teorema de Gersgorin , Electronic Journal of Linear Algebra (ELA) {Vol.35, pp.619-625|2019} [DOI: https://doi.org/ 10.13001/ela.2019.5179]

• 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. (Fe de erratas).
• Varga, Richard S. (2002), Análisis iterativo matricial (2ª ed.), Springer-Verlag. 1ª ed., Prentice Hall, 1962.
• Golub, GH ; Van Loan, CF (1996), Computaciones matriciales , Baltimore: Johns Hopkins University Press, p. 320, ISBN 0-8018-5413-X.

enlaces externos

• "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