Por que as reflexões domésticas não podem diagonalizar uma matriz?

16

Ao calcular a fatoração QR na prática, utiliza-se as reflexões de Householder para zerar a parte inferior de uma matriz. Eu sei que, para calcular valores próprios de matrizes simétricas, o melhor que você pode fazer com as reflexões de Household é obtê-lo na forma tridiagonal. Existe uma maneira óbvia de ver por que não pode ser totalmente diagonalizada dessa maneira? Estou tentando explicar isso de forma simples, mas não consigo apresentar uma apresentação clara.

linear-algebra matrix Victor Liu
fonte

Respostas:

12

Ao calcular os autovalores da matriz simétrica o melhor que você pode fazer com o refletor Household é conduzir M para uma forma tridiagonal. Como foi mencionado em uma resposta anterior porque H é simétrico há uma transformação de semelhança ortogonal que resulta em uma matriz diagonal, isto é, D = S T M S . Seria conveniente se pudéssemos encontrar a ação da matriz ortogonal desconhecida S estritamente usando refletores de Household calculando uma sequência de refletores e aplicando H T da esquerda para M e HM∈Rn×nMMD=STMSSHTMHdo direito de . No entanto, isso não é possível devido à maneira como o refletor Household é projetado para zerar as colunas. Se calcularmos o refletor do agregado familiar para zerar todos os números abaixo de M 11 , encontraremos M = (MM11 Mas agora as entradas M 12 - M 1 n foram alteradas pelo refletor H T 1 aplicado à esquerda. Assim, quando aplicarmos H 1 à direita, ele não zerará mais a primeira linha deM,deixando apenas M 11 . Em vez disso, obteremos H T 1 M= (

M=(∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗)→H1 1TM=(∗∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′).
M12-M1 1nH1 1TH1 1MM11 Onde não apenas não zeramos a linha, mas podemos destruir a estrutura zero que acabamos de introduzir com o refletor H T 1 .
H1 1TM=(∗∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′)→H1 1TMH1 1=(∗∗″∗″∗″∗″∗′∗″∗″∗″∗″∗′∗″∗″∗″∗″∗′∗″∗″∗″∗″∗′∗″∗″∗″∗″).
H1 1T

No entanto, quando você escolhe conduzir para uma estrutura tridiagonal, você deixará a primeira linha intocada pela ação de H T 1 , então M = (MH1 1T

M=(∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗)→H1 1TM=(∗∗∗∗∗∗′∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′).
H1 1TM=(∗∗∗∗∗∗′∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′0 0∗′∗′∗′∗′)→H1 1TMH1 1=(∗∗′0 00 00 0∗′∗″∗″∗″∗″0 0∗″∗″∗″∗″0 0∗″∗″∗″∗″0 0∗″∗″∗″∗″).

Aplicado recursivamente, isso nos permite dirigir M para uma matriz tridiagonal T. Você pode concluir a diagonalização deMeficientemente, como mencionado anteriormente, usando rotações de Jacobi ou Givens, ambas encontradas no livro Matrix Computations, de Golub e Van Loan . As ações acumuladas da sequência de refletores de Household e rotações de Jacobi ou Givens nos permitem encontrar a ação das matrizes ortogonaisST e S sem formar explicitamente.

Andrew Winters
fonte
11

Como os Comentários a outras respostas esclarecem, o problema real aqui não é uma lacuna nas matrizes de agregado familiar, mas uma questão de por que métodos iterativos e não diretos ("forma fechada") são usados ​​para diagonalizar matrizes simétricas (reais) (via ortogonal semelhança).

De fato, qualquer matriz ortogonal pode ser expressa como um produto das matrizes de Householder ; portanto, se soubéssemos a forma diagonal de uma matriz simétrica (seus valores próprios), poderíamos resolver um conjunto completo de vetores próprios ortonormalizados e representar a mudança correspondente da matriz básica como uma matriz. produto de transformações domésticas em tempo polinomial.

Então, voltemos ao comentário entre parênteses de Victor "diferente do teorema de Abel", porque estamos efetivamente perguntando por que métodos iterativos devem ser usados ​​para encontrar as raízes de um polinômio e não de um método direto . É claro que os autovalores de uma matriz simétrica real são as raízes de seu polinômio característico, e é possível ir na outra direção também. Dado um polinômio real com apenas raízes reais, é possível construir uma matriz companheira simétrica tridiagonal a partir de uma sequência Sturm para o polinômio . Veja também o cartaz Exercício 92 de Denis Serre neste conjunto. Isso é bastante bom para mostrar a equivalência desses problemas, já que vimos (@AndrewWinters) que a aplicação direta de matrizes de Householder tridiagonalizará uma matriz simétrica real.

A análise da complexidade aritmética de um método iterativo (isolamento da raiz) é apresentada em Reif (1999), um algoritmo eficiente para os problemas de raiz real e autovalor tridiagonal simétrico . A abordagem de Reif aprimora as versões personalizadas do QR para matrizes complementares , fornecendoO(nregistro3⁡n) ao invés de O(n2) complexidade.

O Teorema de Abel-Galois-Ruffini diz que nenhuma fórmula geral para raízes de polinômios acima do grau quatro pode ser dada em termos de radicais (e aritmética usual). No entanto, existem formas fechadas de raízes em termos de operações mais exóticas . Em princípio, pode-se basear os métodos de autovalor / diagonalização em tais abordagens , mas encontramos algumas dificuldades práticas:

  1. O radical Bring (também conhecido como ultraradical) é uma função de uma variável, a esse respeito, como fazer uma raiz quadrada. Jerrad (c. 1835) mostrou que resolver o quintic geral poderia ser reduzido a resolvert5+t-uma=0 0, para que a função univariada t(uma) (usado além de radicais e outras aritméticas comuns) permite que todos os quintics sejam resolvidos.

  2. Isso se divide em polinômios de grau seis e acima, embora várias maneiras possam ser encontradas para resolvê-los usando funções de apenas duas variáveis. O 13º problema de Hilbert era a conjectura de que polinômios de grau geral sete não poderiam ser resolvidos usando apenas funções de no máximo duas variáveis, mas em 1957, VI Arnold mostrou que sim. Entre as famílias de funções multivariáveis ​​que podem ser usadas para obter soluções para polinômios de grau arbitrário estão as integrais de Mellin, as funções hipergeométricas e teta de Siegel.

  3. Além de implementar funções especiais um tanto exóticas de mais de um argumento, precisamos de métodos diretos para resolver polinômios que funcionam em geral nem vez de métodos específicos ou específicos. Guàrdia (2002) fornece "uma expressão muito simples das raízes de um polinômio de grau arbitrário em termos de derivadas de funções teta hiperelípticas". No entanto, essa abordagem exige a escolha de pontos de Weierstrass na curva hiperelípticaCf:Y2=f(x) onde todas as raízes do polinômio f(x)são procurados. Uma boa opção leva a expressar menos da metade dessas raízes, e parece que essa abordagem exige testes repetidos para obter todas elas. Cada tentativa envolve resolver um sistema linear homogêneo emO(n3) custo.

Portanto, os métodos indiretos / iterativos para isolar raízes reais (valores próprios equivalentes de matrizes simétricas), mesmo com alta precisão, atualmente têm vantagens práticas sobre os métodos diretos / exatos conhecidos para esses problemas.

hardmath
fonte
Algumas notas: 1. um método prático para construir a matriz companheira tridiagonal a partir das seqüências de Sturm foi esboçado em artigos de Fiedler e Schmeisser ; Eu dei uma implementação do Mathematica aqui e não deve ser muito difícil de implementar em uma linguagem mais tradicional.
JM
2. Com relação à abordagem "função teta" para raízes polinomiais (que eu concordo é um pouco pesada para uso prático), Umemura descreve uma abordagem usando as funções teta de Riemann .
JM
2

Por que razão você acha que isso é impossível?

Qualquer matriz real simétrica S pode ser diagonalizado ortogonalmente, S=GDGt, Onde G é ortogonal e D é diagonal.

Qualquer matriz ortogonal de tamanho n × n pode ser construída como um produto de no máximo n dessas reflexões. Wikipedia . Portanto, você tem essa decomposição.

Não tenho certeza da última afirmação, apenas a cito (e acho que está correta). Tanto quanto eu entendo sua pergunta, tudo se resume a se alguma matriz ortogonal pode ser decomposta em uma sequência de transformações de Household.

shuhalo
fonte
2
Eu deveria ter sido mais específico. O primeiro passo para diagonalizar uma matriz simétrica é aplicar Household até que seja tridiagonal. Em seguida, as iterações QR são executadas. Esse processo não pode ser concluído usando apenas transformações de proprietário de formulário fechado. Por quê? (excepto o teorema de Abel)
Victor Liu
11
Você pode fazer isso com rotações de Jacobi. Golub e Van Loan escrevem que Jacobi é o mesmo que Givens. O chefe de família é apenas outra maneira de fazer o Givens. Na prática, a maneira "correta" pode ser com o QR se for mais rápido.
poder
1

Se os valores próprios já são conhecidos (a partir de um cálculo preliminar com base na abordagem usual), é possível usá-los para triangular uma matriz não simétrica (ou diagonalizar uma matriz simétrica) por um produto em n-1 1Reflexões domésticas. Noko passo ka coluna é trazida para a forma triangular. (Isso também fornece uma prova indutiva simples da existência da fatoração de Schur.)

Na verdade, é útil para métodos em que é necessário repetidamente a matriz ortoginal em uma forma fatorada numericamente estável.

Arnold Neumaier
fonte