iteração inversa - Inverse iteration

Na análise numérica , iteração inversa (também conhecido como o método de potência inversa ) é um iterativo algoritmo valor próprio . Ele permite que se encontrar um valor aproximado eigenvector quando uma aproximação a um correspondente valor próprio já é conhecido. O método é conceptualmente semelhante ao método de alimentação . Ele parece ter sido originalmente desenvolvido para calcular as frequências de ressonância no campo da mecânica estrutural.

O algoritmo de iteração de potência inversa começa com uma aproximação para o valor próprio correspondente para o desejado vector próprio e um vector , ou num vector seleccionado aleatoriamente ou uma aproximação para o vector próprio. O método é descrito por iteração ${\ Displaystyle \ mu}$${\ B_ displaystyle {0}}$

${\ Displaystyle b_ {k + 1} = {\ frac {(A- \ mu I) ^ {- 1} b_ {k}} {C_ {k}}},}$

onde estão algumas constantes normalmente escolhidos como Desde eigenvectors são definidos até à multiplicação por constantes, a escolha pode ser arbitrária, em teoria; aspectos práticos da escolha de são discutidas abaixo. ${\ Displaystyle C_ {k}}$${\ Displaystyle C_ {k} = \ | (A- \ mu I) ^ {- 1} b_ {k} \ |.}$${\ Displaystyle C_ {k}}$${\ Displaystyle C_ {k}}$

Em cada iteração, o vector é multiplicado pela matriz e normalizada. É exactamente a mesma fórmula como no método da potência , excepto a substituição da matriz por Quanto mais próxima a aproximação para o valor próprio é escolhido, o mais rápido o algoritmo converge; no entanto, a escolha incorreta de pode levar a convergência lenta ou para a convergência para um autovetor diferente daquele desejado. Na prática, o método é usado quando uma boa aproximação para o valor próprio é conhecido e, portanto, a pessoa precisa apenas algumas (muitas vezes apenas um) iterações. ${\ Displaystyle b_ {k}}$${\ Displaystyle (A- \ mu I) ^ {- 1}}$${\ Displaystyle A}$${\ Displaystyle (A- \ mu I) ^ {-. 1}}$${\ Displaystyle \ mu}$${\ Displaystyle \ mu}$

Teoria e convergência

A idéia básica do método das potências é escolher um vetor inicial (um eigenvector aproximação ou um aleatório vector) e iterativa cálculo . Excepto para um conjunto de zero, medida , para qualquer vector inicial, o resultado irá convergir para um vector próprio correspondente ao dominante valor próprio . ${\ Displaystyle b}$${\ Displaystyle Ab, A ^ {2} b, A ^ {3} b, ...}$

A iteração inverso faz o mesmo para a matriz , de modo que converge para o vector próprio correspondente ao valor próprio dominante da matriz . Valores próprios desta matriz são onde são valores próprios de . O maior desses números corresponde ao menor dos Os vectores próprios de e são os mesmos, uma vez que ${\ Displaystyle (A- \ mu I) ^ {- 1}}$${\ Displaystyle (A- \ mu I) ^ {- 1}}$${\ Displaystyle (\ lambda _ {1} - \ mu) ^ {- 1}, ..., (\ lambda _ {n} - \ mu) ^ {- 1},}$${\ Displaystyle \ lambda _ {i}}$${\ Displaystyle A}$${\ Displaystyle (\ lambda _ {1} - \ mu), ..., (\ lambda _ {n} - \ mu).}$${\ Displaystyle A}$${\ Displaystyle (A- \ mu I) ^ {- 1}}$

${\ Displaystyle Av = \ lambda v \ Leftrightarrow (A- \ eu mu) v = \ lambda v- \ mu v \ Leftrightarrow (\ lambda - \ mu) ^ {-} 1 v = (A- \ mu I) ^ {-1} v}$

Conclusão : O método converge para o vector próprio da matriz correspondente ao valor próprio para mais próximo ${\ Displaystyle A}$${\ Displaystyle \ mu.}$

Em particular, tendo vemos que converge para o vector próprio correspondente ao valor próprio de com o menor valor absoluto. ${\ Displaystyle \ mu = 0}$${\ Displaystyle (A) ^ {- k} b}$${\ Displaystyle A}$

Velocidade de convergência

Vamos analisar a taxa de convergência do método.

O método de alimentação é conhecida a convergir linearmente ao limite, mais precisamente:

${\ Displaystyle \ mathrm {Distância} (b ^ {\ mathrm {ideal}}, b _ {\ mathrm {Poder ~ Método}} ^ {k}) = O \ left (\ left | {\ frac {\ lambda _ { \ mathrm {subdominant}}} {\ lambda _ {\ mathrm {dominante}}}} \ right | ^ {k} \ right),}$

por conseguinte, para o método inverso iteração resultado semelhante sons como:

${\ Displaystyle \ mathrm {Distância} (b ^ {\ mathrm {ideais}}, b _ {\ mathrm {inversas ~ iteração}} ^ {k}) = O \ left (\ left | {\ frac {\ mu - \ lambda _ {\ mathrm {mais próximo ~ to ~} \ mu}} {\ mu - \ lambda _ {\ mathrm {segunda ~ mais próximo ~ to ~} \ mu}}} \ right | ^ {k} \ right)}.$

Esta é uma fórmula chave para a compreensão de convergência do método. Ele mostra que, se for escolhido perto o suficiente para alguns valores próprios , por exemplo cada iteração irá melhorar a precisão vezes. (Nós usamos isso para pequenos o suficiente "mais próximo " e "mais próximo " é a mesma.) Para pequenas o suficiente que é aproximadamente o mesmo que . Portanto, se alguém é capaz de encontrar , de modo que o será pequeno o suficiente, então muito poucas iterações pode ser satisfatório. ${\ Displaystyle \ mu}$${\ Displaystyle \ lambda}$${\ Displaystyle \ mu - \ lambda = \ epsilon}$${\ Displaystyle | \ epsilon | / | \ lambda + \ epsilon - \ lambda _ {\ mathrm {mais próximo ~ to ~} \ lambda} |}$${\ Displaystyle \ epsilon}$${\ Displaystyle \ mu}$${\ Displaystyle \ lambda}$${\ Displaystyle | \ epsilon |}$${\ Displaystyle | \ epsilon | / | \ lambda - \ lambda _ {\ mathrm {mais próximo ~ to ~} \ lambda} |}$${\ Displaystyle \ mu}$${\ Displaystyle \ epsilon}$

Complexidade

O algoritmo de iteração inversa requer a solução de um sistema linear ou cálculo da matriz inversa. Para matrizes não-estruturados (não escassa, não Toeplitz, ...) isso requer operações. ${\ Displaystyle O (n ^ {3})}$

opções de implementação

O método é definido pela fórmula:

${\ Displaystyle b_ {k + 1} = {\ frac {(A- \ mu I) ^ {- 1} b_ {k}} {C_ {k}}},}$

Há, no entanto, várias opções para a sua implementação.

Calcular matriz inversa ou sistema de equações lineares resolver

Podemos reescrever a fórmula da seguinte maneira:

${\ Displaystyle (A- \ mu I) b_ {k + 1} = {\ frac {b_ {k}} {C_ {k}}},}$

enfatizando que para encontrar a próxima aproximação podemos resolver um sistema de equações lineares. Existem duas opções: pode-se escolher um algoritmo que resolve um sistema linear, ou pode-se calcular a inversa e depois aplicá-lo ao vetor. Ambas as opções têm complexidade O (n ³ ) , o número exacto depende do método escolhido. ${\ Displaystyle b_ {k + 1}}$${\ Displaystyle (A- \ mu I) ^ {- 1}}$

A escolha depende também do número de iterações. Ingènua, se em cada iteração um resolve um sistema linear, a complexidade será K * O (N ³ ) , onde k é o número de iterações; Da mesma forma, o cálculo da matriz inversa e aplicá-lo em cada iteração é de complexidade K * O (n ³ ) . Note-se, no entanto, que se a estimativa de valores próprios mantém-se constante, então pode reduzir a complexidade para o (n ³ ) + k * O (N ² ) com um ou outro método. Calculando a matriz inversa uma vez, e armazená-lo a aplicar em cada iteração é de complexidade O (n ³ ) + k * O (N ² ) . Armazenar uma decomposição LU de e utilizando para a frente e para trás substituição para resolver o sistema de equações em cada iteração também é de complexidade O (n ³ ) + k * O (N ² ) . ${\ Displaystyle \ mu}$${\ Displaystyle (A- \ mu I)}$

Invertendo a matriz terá tipicamente um maior custo inicial, mas custo inferior em cada iteração. Por outro lado, os sistemas de resolução de equações lineares terá tipicamente um custo inicial menor, mas requerem mais operações para cada iteração.

Tridiagonalization, forma Hessenberg

Se for necessário para executar muitas iterações (ou algumas iterações, mas para muitos eigenvectors), então ele pode ser sábio para trazer da matriz para o superior forma Hessenberg primeiro (de matriz simétrica este será forma tridiagonal ). Que custa de operações aritméticas que utilizam uma técnica com base na redução dono da casa ), com uma sequência finita de transformadas ortogonais de similaridade, um pouco como uma decomposição de QR de dois lados. (Para a decomposição QR, as rotações Householder são multiplicados apenas na esquerda, mas para o caso Hessenberg se multiplicam em ambos esquerda e direita). Para matrizes simétricas este procedimento custa operações aritméticas usando uma técnica baseada na redução de Householder.${\ Displaystyle {\ begin {matriz} {\ frac {10} {3}} \ final {matriz}} n ^ {3} + O (n ^ {2})}$${\ Displaystyle {\ begin {matriz} {\ frac {4} {3}} \ final {matriz}} n ^ {3} + O (n ^ {2})}$

Solução do sistema de equações lineares para a matriz tridiagonal custa operações, de modo a complexidade cresce como , onde é o número de iteração, que é melhor do que para a inversão direta. No entanto, para algumas iterações tal transformação pode não ser prático. ${\ Displaystyle O (n)}$${\ Displaystyle O (n ^ {3}) + kO (n)}$${\ Displaystyle k}$

Também transformação para a forma Hessenberg envolve raízes quadradas e a operação de divisão, que não são universalmente suportado pelo hardware.

Escolha da constante de normalização ${\ Displaystyle C_ {k}}$

Em processadores de uso geral (por exemplo, produzido pela Intel) o tempo de execução de adição, multiplicação e divisão é aproximadamente igual. Mas em incorporado e / ou hardware que consome pouca energia ( processadores de sinal digital , FPGA , ASIC ) divisão não podem ser suportadas pelo hardware, e assim deve ser evitado. Escolha permite a divisão rápida, sem suporte de hardware explícita, como a divisão por uma potência de 2 pode ser implementado tanto como um desvio pouco (para aritmética de ponto fixo ) ou subtração de partir o expoente (para ponto flutuante aritmética ). ${\ Displaystyle C_ {k} = 2 ^ {n_ {k}}}$${\ Displaystyle k}$

Ao implementar o algoritmo usando aritmética de ponto fixo , a escolha da constante é especialmente importante. Pequenos valores levará a um crescimento rápido da norma de e para transbordar ; grandes valores de vai fazer com que o vector de tender para zero. ${\ Displaystyle C_ {k}}$${\ Displaystyle b_ {k}}$${\ Displaystyle C_ {k}}$${\ Displaystyle b_ {k}}$

Uso

A principal aplicação do método é a situação quando uma aproximação a um valor próprio é encontrado e é preciso encontrar o vector próprio aproximado correspondente. Em tal situação, a iteração inversa é a principal e, provavelmente, o único método para usar.

Métodos para encontrar valores próprios aproximados

Então, tipicamente, o método é utilizado em combinação com qualquer outro método que encontra valores próprios aproximados: o exemplo padrão é o algoritmo de bissecção valor próprio , outro exemplo é a iteração quociente de Rayleigh , o que é, na verdade, o mesmo iteração inversa com a escolha do valor próprio aproximado como o quociente Rayleigh correspondente ao vector obtido na etapa anterior da iteração.

Existem algumas situações em que o método pode ser usado por si só, no entanto, eles são bastante marginal.

Norma da matriz como aproximação para a dominante autovalor

O valor próprio dominante pode ser facilmente estimado para qualquer matriz. Para qualquer norma induzida é verdade que para qualquer valor próprio . Assim, tendo a norma da matriz como um autovalor aproximado pode ver que o método irá convergir para o vector próprio dominante. ${\ Displaystyle \ left \ | A \ right \ | \ geq | \ lambda |,}$${\ Displaystyle \ lambda}$

Estimativas baseadas em estatísticas

Em algumas aplicações em tempo real é preciso encontrar autovetores para matrizes com uma velocidade de milhões de matrizes por segundo. Em tais aplicações, tipicamente as estatísticas de matrizes é conhecido com antecedência e pode-se tomar como um valor próprio aproximado do valor próprio média para alguns grande amostra de matriz. Melhor, pode-se calcular a razão da média dos valores próprios para o rastreio ou a norma da matriz e estimar o valor próprio média como o rastreio ou norma multiplicado pelo valor médio desse rácio. É evidente que um tal método pode ser utilizado apenas com prudência e apenas quando alta precisão não é crítica. Esta abordagem de estimar um valor próprio média pode ser combinado com outros métodos para evitar excessivamente grande erro.

Veja também

• método das potências
• Rayleigh iteração quociente
• Lista de algoritmos de valores próprios

Referências

links externos

• Iteração inversa para encontrar autovetores , physics.arizona.edu