Teorema do círculo de Gershgorin - Gershgorin circle theorem

Em matemática , o teorema do círculo de Gershgorin pode ser usado para limitar o espectro de uma matriz quadrada . Foi publicado pela primeira vez pelo matemático soviético Semyon Aronovich Gershgorin em 1931. O nome de Gershgorin foi transliterado de várias maneiras diferentes, incluindo Geršgorin, Gerschgorin, Gershgorin, Hershhorn e Hirschhorn.

Declaração e prova

Let Ser uma matriz complexa , com entradas . Para permitir que a soma dos valores absolutos das entradas não-diagonais na linha -ésimo: ${\ 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 |.}$

Let Ser um disco fechado centrado no raio . Esse disco é chamado de disco de Gershgorin. ${\ displaystyle D (a_ {ii}, R_ {i}) \ subseteq \ mathbb {C}}$${\ displaystyle a_ {ii}}$${\ displaystyle R_ {i}}$

Teorema. Cada autovalor de encontra-se em pelo menos um dos discos de Gershgorin${\ displaystyle A}$${\ displaystyle D (a_ {ii}, R_ {i}).}$

Prova. Let Ser um autovalor de . Escolha um autovetor correspondente de forma que um componente seja igual a e os outros tenham valor absoluto menor ou igual a : e para . Sempre existe um , que pode ser obtido simplesmente dividindo qualquer autovetor por seu componente com o maior módulo. Desde , em particular ${\ displaystyle \ lambda}$${\ displaystyle A}$${\ displaystyle x = (x_ {j})}$${\ displaystyle x_ {i}}$${\ displaystyle 1}$${\ displaystyle 1}$${\ displaystyle x_ {i} = 1}$${\ displaystyle | x_ {j} | \ leq 1}$${\ displaystyle j \ neq i}$${\ displaystyle x}$${\ displaystyle Ax = \ lambda x}$

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

Então, dividindo a soma e levando em consideração mais uma vez , obtemos ${\ displaystyle x_ {i} = 1}$

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

Portanto, aplicando a desigualdade do triângulo ,

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

Corolário. Os valores próprios de uma também deve situar-se dentro do Gershgorin discos C _j correspondente às colunas de Uma .

Prova. Aplique o Teorema de A ^T .

Exemplo. Para uma matriz diagonal , os discos de Gershgorin coincidem com o espectro. Por outro lado, se os discos de Gershgorin coincidem com o espectro, a matriz é diagonal.

Discussão

Uma maneira de interpretar esse teorema é que, se as entradas fora da diagonal de uma matriz quadrada sobre os números complexos têm normas pequenas , os valores próprios da matriz não podem estar "longe" das entradas diagonais da matriz. Portanto, ao reduzir as normas de entradas fora da diagonal, pode-se tentar aproximar os autovalores da matriz. Obviamente, as entradas diagonais podem mudar no processo de minimizar as entradas fora da diagonal.

O teorema não afirma que existe um disco para cada autovalor; se alguma coisa, os discos correspondem antes aos eixos em , e cada um expressa um limite precisamente naqueles autovalores cujos autovalores estão mais próximos de um determinado eixo. Na 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 e 2 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \ end {pmatrix}} ^ {- 1} = {\ begin {pmatrix} -3a + 2b + 2c & 6a-2b-4c & 6a-4b-2c \\ ba & a + (ab) & 2 (ab) \\ ca & 2 ( ac) & a + (ac) \ end {pmatriz}}}$

- que por construção tem valores próprios , e com eigenvectors , e - é fácil ver que o disco para a linha 2 tampas e enquanto o disco para a linha 3 tampas e . No entanto, esta é apenas uma feliz coincidência; se trabalhando através das etapas da prova, descobriremos que em cada autovetor é o primeiro elemento que é o maior (cada autoespaço está mais próximo do primeiro eixo do que de qualquer outro eixo), então o teorema apenas promete que o disco para a linha 1 (cujo raio pode ser o dobro da soma dos outros dois raios) cobre todos os três valores próprios. ${\ 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}$

Fortalecimento do teorema

Se um dos discos for separado dos outros, ele conterá exatamente um valor próprio. Se, no entanto, encontrar outro disco, é possível que não contenha nenhum valor próprio (por exemplo, ou ). No caso geral, o teorema pode ser reforçado da seguinte forma: ${\ displaystyle A = \ left ({\ begin {smallmatrix} 0 & 1 \\ 4 & 0 \ end {smallmatrix}} \ right)}$${\ displaystyle A = \ left ({\ begin {smallmatrix} 1 e -2 \\ 1 & -1 \ end {smallmatrix}} \ right)}$

Teorema : Se a união de k discos é disjoint a partir da união dos outros n  -  k discos depois da ex-União contém exatamente k e os últimos n  -  k autovalores de A .

Prova : Seja D a matriz diagonal com entradas iguais às entradas diagonais de A e seja

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

Usaremos o fato de que os autovalores são contínuos em e mostraremos que se qualquer autovalor se mover de uma das uniões para a outra, então deve estar fora de todos os discos para algumas , o que é uma contradição. ${\ displaystyle t}$${\ displaystyle t}$

A afirmação é verdadeira para . As entradas diagonais de são iguais às de A , portanto os centros dos círculos de Gershgorin são os mesmos, porém seus raios são t vezes o de A. Portanto, a união dos k discos correspondentes de é disjunta da união dos restantes nk para todos . Os discos estão fechados, então a distância das duas uniões para A é . A distância para é uma função decrescente de t , portanto, é sempre pelo menos d . Uma vez que os autovalores de são uma função contínua de t , para qualquer autovalor de na união dos k discos sua distância da união dos outros nk discos também é contínua. Obviamente , e assumir reside na união dos discos nk . Então , existe tal que . Mas isso significa que está fora dos discos de Gershgorin, o que é impossível. Portanto, reside na união dos discos k , e o teorema é comprovado. ${\ 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)}$

Observações:

• A continuidade de deve ser entendida no sentido de topologia . Basta mostrar que as raízes (como um ponto no espaço ) são função contínua de seus coeficientes. Observe que o mapa inverso que mapeia as raízes para os coeficientes é descrito pelas fórmulas de Vieta (nota para Polinômio característico ), que pode ser provado como um mapa aberto . Isso prova que as raízes como um todo são uma função contínua de seus coeficientes. Uma vez que a composição das funções contínuas é novamente contínua, o como uma composição do solucionador de raízes e também é contínua.${\ displaystyle \ lambda (t)}$${\ displaystyle \ mathbb {C} ^ {n}}$ ${\ displaystyle a_ {n} \ equiv 1}$${\ displaystyle \ lambda (t)}$${\ displaystyle B (t)}$
• Os autovalores individuais podem se fundir com outros autovalores ou surgir de uma divisão do autovalor anterior. Isso pode confundir as pessoas e questionar o conceito de contínuo. No entanto, ao visualizar do espaço do conjunto de autovalores , a trajetória ainda é uma curva contínua, embora não necessariamente suave em todos os lugares.${\ displaystyle \ lambda (t)}$${\ displaystyle \ mathbb {C} ^ {n}}$

Comentário adicionado:

• A prova dada acima é indiscutivelmente (in) correta ...... Existem dois tipos de continuidade em relação aos autovalores: (1) cada autovalor individual é uma função contínua usual (tal representação existe em um intervalo real, mas pode não existir em um domínio complexo), (2) os autovalores são contínuos como um todo no sentido topológico (um mapeamento do espaço da matriz com métrica induzida por uma norma para tuplas desordenadas, ou seja, o espaço quociente de C ^ n sob equivalência de permutação com induzido métrica). Qualquer que seja a continuidade usada em uma prova do teorema do disco de Gerschgorin, deve-se justificar que a soma das multiplicidades algébricas de autovalores permanece inalterada em cada região conectada. Uma prova usando o princípio do argumento da análise complexa não requer continuidade de autovalor de qualquer tipo. Para uma breve discussão e esclarecimento, consulte.

Aplicativo

O teorema do círculo de Gershgorin é útil para resolver equações matriciais da forma Ax = b para x, onde b é um vetor e A é uma matriz com um grande número de condição .

Neste tipo de problema, o erro no resultado final é normalmente da mesma ordem de grandeza que o erro nos dados iniciais multiplicado pelo número de condição de A . Por exemplo, se b é conhecido com seis casas decimais e o número de condição de A é 1000, então podemos apenas ter certeza de que x é preciso com três casas decimais. Para números de condição muito altos, mesmo erros muito pequenos devido a arredondamentos podem ser ampliados a tal ponto que o resultado não tem sentido.

Seria bom para reduzir o número de condição de A . Isso pode ser feito pelo pré - condicionamento : Uma matriz P tal que P ≈ A ⁻¹ é construída, e então a equação PAx = Pb é resolvida para x . Usar o inverso exato de A seria bom, mas encontrar o inverso de uma matriz é algo que queremos evitar devido ao gasto computacional.

Agora, como PA ≈ I onde I é a matriz de identidade, os autovalores de PA devem ser todos próximos de 1. Pelo teorema do círculo de Gershgorin, cada autovalor de PA está dentro de uma área conhecida e, portanto, podemos formar uma estimativa grosseira de quão bom nossa escolha de P foi.

Exemplo

Use o teorema do círculo de Gershgorin para estimar os valores próprios de:

Este diagrama mostra os discos em amarelo derivados para os valores próprios. Os primeiros dois discos se sobrepõem e sua união contém dois autovalores. O terceiro e o quarto discos são separados dos outros e contêm um valor próprio cada.

${\ 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}}.}$

Começando com a linha um, pegamos o elemento na diagonal, a _ii, como o centro do disco. Em seguida, pegamos os elementos restantes na linha e aplicamos a fórmula:

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

para obter os quatro discos a seguir:

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

Observe que podemos melhorar a precisão dos dois últimos discos aplicando a fórmula às colunas correspondentes da matriz, obtendo e . ${\ displaystyle D (2,1.2)}$${\ displaystyle D (-11,2.2)}$

Os valores próprios são 9,8218, 8,1478, 1,8995, −10,86. Note-se que este é um (coluna) matriz diagonal dominante : . Isso significa que a maior parte da matriz está na diagonal, o que explica por que os autovalores estão tão próximos dos centros dos círculos e as estimativas são muito boas. Para uma matriz aleatória, esperaríamos que os autovalores estivessem substancialmente mais distantes dos centros dos círculos. ${\ textstyle | a_ {ii} |> \ sum _ {j \ neq i} | a_ {ji} |}$

Veja também

• Para matrizes com entradas não negativas, consulte o teorema de Perron-Frobenius .
• Matriz duplamente estocástica
• Matriz de Hurwitz
• Joel Lee Brenner
• Matriz Metzler
• Desigualdade de Muirhead
• Desigualdade de Bendixson
• Teorema de Schur-Horn

Referências

• Gerschgorin, S. (1931), "Über die Abgrenzung der Eigenwerte einer Matrix" , Izv. Akad. Nauk. USSR Otd. Fiz.-Mat. Nauk (em alemão), 6 : 749-754.
• Varga, Richard S. (2004), Geršgorin and His Circles , Berlin: Springer-Verlag, ISBN 3-540-21100-4. ( Errata ).
• Varga, Richard S. (2002), Matrix Iterative Analysis (2ª ed.), Springer-Verlag. 1ª ed., Prentice Hall, 1962.
• Golub, GH ; Van Loan, CF (1996), Matrix Computations , Baltimore: Johns Hopkins University Press, p. 320, ISBN 0-8018-5413-X.

links externos

• "Teorema do círculo de Gershgorin" . PlanetMath .
• Eric W. Weisstein. " Teorema do círculo de Gershgorin ." Da MathWorld — A Wolfram Web Resource.
• Biografia de Semyon Aranovich Gershgorin em MacTutor