Algoritmo QR

O algoritmo QR é um método numérico para calcular todos os autovalores e possivelmente os autovetores de uma matriz quadrada . O método QR ou iteração QR, também conhecido como método QR, é baseado na decomposição QR e foi introduzido em 1961–1962 independentemente um do outro por John GF Francis e Vera Nikolajewna Kublanowskaja . Um precursor foi o algoritmo LR de Heinz Rutishauser (1958), mas é menos estável e é baseado na decomposição LR . Freqüentemente, as iterações do algoritmo QR convergem para a forma Schur da matriz. O método original é bastante complexo e, portanto, impraticável - mesmo nos computadores de hoje - para matrizes com centenas de milhares de linhas e colunas.

Variantes derivadas como o método Multishift de Z. Bai e James Demmel 1989 e a variante numericamente mais estável de K. Braman, R. Byers e R. Mathias 2002 têm tempos de execução práticos que são cúbicos no tamanho da matriz. O último método é implementado na biblioteca de software numérica LAPACK , que por sua vez é usada em muitos sistemas de álgebra computacional (CAS) para os algoritmos de matriz numérica.

Descrição do algoritmo QR

Objetivo do processo de cálculo

Partindo de uma matriz real ou complexa ou uma sequência de matrizes ortogonais ou unitárias é determinado de modo que a sequência da matriz recursiva converge amplamente para uma matriz triangular superior. Uma vez que todas as transformações na recursão são transformações de similaridade, todas as matrizes da sequência da matriz têm os mesmos valores próprios com os mesmos múltiplos. ${\ displaystyle A \ in \ mathbb {R} ^ {n \ times n}}$${\ displaystyle A \ in \ mathbb {C} ^ {n \ times n}}$${\ displaystyle Q_ {1}, Q_ {2}, \ dots,}$${\ displaystyle A_ {1} = A, \, A_ {2} = Q_ {1} ^ {- 1} A_ {1} Q_ {1}, \ dots, A_ {k + 1} = Q_ {k} ^ {-1} A_ {k} Q_ {k}, \ pontos}$${\ displaystyle A_ {1}, A_ {2}, \ dots,}$

Se uma matriz triangular superior for alcançada no valor limite, uma forma de Schur de , os autovalores podem ser lidos a partir dos elementos diagonais. No caso de uma matriz real com transformações ortogonais, entretanto, também podem haver autovalores complexos. Então, o resultado do método é uma matriz de triângulo de bloco superior, cujos blocos diagonais têm o tamanho dos autovalores reais ou o tamanho dos autovalores complexos. O bloco diagonal da extensão rotacional correspondente corresponde a um autovalor e seu autovalor conjugado complexo . ${\ displaystyle A}$${\ displaystyle 1}$${\ displaystyle 2}$${\ displaystyle \ lambda = a + ib}$${\ displaystyle \ left ({\ begin {smallmatrix} a & -b \\ b & a \ end {smallmatrix}} \ right)}$

Esquema geral do procedimento

A partir de uma matriz (ou ), uma sequência de matrizes é determinada de acordo com a seguinte regra: ${\ displaystyle A_ {1} = A \ in \ mathbb {R} ^ {n \ vezes n}}$${\ displaystyle A \ in \ mathbb {C} ^ {n \ times n}}$${\ displaystyle A_ {i}}$

1. para fazer${\ displaystyle i \ in \ mathbb {N}}$
2. Encontre um polinômio e avalie-o na matriz .${\ displaystyle p_ {i}}$${\ displaystyle A_ {i}}$
3. Calcule a decomposição QR de .${\ displaystyle p_ {i} (A_ {i}) = Q_ {i} R_ {i}}$
4. Calcule a nova iteração: .${\ displaystyle A_ {i + 1} = Q_ {i} ^ {- 1} A_ {i} Q_ {i}}$
5. fim para

As variantes com turnos (implícitos) e vários turnos também podem ser exibidos e analisados ​​nesta forma geral.

A função de matriz é freqüentemente um polinômio (aqui uma combinação linear de potências de matriz) com coeficientes reais (ou complexos). No caso mais simples, um polinômio linear é escolhido, que então tem a forma . Neste caso, o algoritmo é simplificado para a versão clássica (com deslocamento único): ${\ displaystyle p_ {i}}$${\ displaystyle p_ {i} (A_ {i}) = A_ {i} - \ kappa _ {i} I}$

1. para fazer${\ displaystyle i \ in \ mathbb {N}}$
2. Encontre um número apropriado ${\ displaystyle \ kappa _ {i}}$
3. Calcule a decomposição QR de${\ displaystyle A_ {i} - \ kappa _ {i} I = Q_ {i} R_ {i}}$
4. Calcule a nova iteração: ${\ displaystyle A_ {i + 1} = Q_ {i} ^ {- 1} A_ {i} Q_ {i} = Q_ {i} ^ {- 1} (Q_ {i} R_ {i} + \ kappa _ {i} I) Q_ {i} = R_ {i} Q_ {i} + \ kappa _ {i} I}$
5. fim para

Em cada iteração definida, o método é consistente com a correspondência de método de potência estendida em subespaços (aqui o espaço vetorial completo) . ${\ displaystyle \ kappa _ {i} = 0}$

O polinômio que controla a decomposição QR pode ser corrigido desde o início ou adaptado dinamicamente à matriz atual em cada etapa de iteração . Existem também tentativas de uso para funções de matriz racional, i. H. Funções da forma com polinômios e . ${\ displaystyle A_ {i}}$${\ displaystyle p_ {i}}$${\ displaystyle p (A) = h (A) ^ {- 1} g (A)}$${\ displaystyle g}$${\ displaystyle h}$

deflação

Se for descoberto em uma etapa de iteração que um bloco inferior esquerdo das colunas e suas linhas cai abaixo de um limite predeterminado nas quantidades de todos os seus componentes, o método é continuado nos dois sub-blocos quadrados diagonais das linhas / colunas e separadamente. Se as matrizes resultantes da divisão forem suficientemente pequenas, a determinação dos valores próprios pode, e. B. ser encerrado calculando o polinômio característico e seus zeros. ${\ displaystyle 1, \ dots, i}$${\ displaystyle i + 1, \ dots, n}$${\ displaystyle 1, \ dots, i}$${\ displaystyle i + 1, \ dots, n}$

Transformação para a forma Hessenberg

O objetivo do algoritmo QR é criar uma forma de triângulo superior, ou uma forma de triângulo de bloco, na qual os blocos do tamanho correspondem a autovalores complexos. Isso pode ser feito quase de maneira simples por uma transformação de similaridade para a forma de Hessenberg , i. H. em uma matriz com apenas uma diagonal inferior secundária (não desaparecendo de forma idêntica). ${\ displaystyle 2}$

• Sentar-se ${\ displaystyle {\ tilde {A}} = A}$
• para k = 1 a n-1 faça

1. Forme o segmento da coluna ${\ displaystyle u = {\ tilde {A}} _ {k + 1: n, \, k}}$
2. Encontre a reflexão de Householder que mapeia para o primeiro vetor de base canônica,${\ displaystyle {\ tilde {P}} _ {k} = I-2vv ^ {T}}$${\ displaystyle u}$
3. Use a matriz de bloco para substituir por uma matriz semelhante .${\ displaystyle P_ {k} = \ left ({\ begin {smallmatrix} I_ {k} & 0 \\ 0 & {\ tilde {P}} _ {k} \ end {smallmatrix}} \ right)}$${\ displaystyle {\ tilde {A}}}$${\ displaystyle P_ {k} ^ {- 1} {\ til {A}} P_ {k} = P_ {k} {\ tilde {A}} P_ {k}}$

• Observe a matriz de transformação geral .${\ displaystyle Q_ {0} = P_ {1} P_ {2} \ cdots P_ {n-1}}$
• ${\ displaystyle A_ {1} = {\ tilde {A}} = Q_ {0} ^ {- 1} AQ_ {0}}$ está agora na forma de Hessenberg.

A forma de Hessenberg torna mais fácil determinar os polinômios característicos de matrizes parciais . A forma de Hessenberg de uma matriz simétrica é uma forma tridiagonal , o que acelera significativamente outros cálculos.

Além disso, a forma de Hessenberg é obtida em todas as etapas do algoritmo QR. A base para isso é a aritmética de matrizes triangulares generalizadas nas quais todas as entradas abaixo de uma diagonal secundária inferior desaparecem. Uma matriz de Hessenberg é, portanto, uma matriz triangular generalizada com uma diagonal secundária. Com a multiplicação, os números das diagonais secundárias que não desaparecem se somam; com a adição, o número maior geralmente é retido.

Portanto, como a matriz ortogonal, eles têm o número de diagonais secundárias inferiores. Bem, por causa de , também se aplica${\ displaystyle p_ {i} (A_ {i})}$${\ displaystyle Q_ {i} = p_ {i} (A_ {i}) R_ {i} ^ {- 1}}$${\ displaystyle m = \ deg p_ {i}}$${\ displaystyle A_ {i + 1} = Q_ {i} ^ {- 1} A_ {i} Q_ {i}}$

${\ displaystyle p_ {i} (A_ {i + 1}) = Q_ {i} ^ {- 1} p_ {i} (A_ {i}) Q_ {i} = R_ {i} Q_ {i}}$,

e o último produto também tem diagonais secundárias. Em geral, isso só é possível se tiver exatamente uma diagonal secundária, ou seja, estiver novamente na forma de Hessenberg. Da decomposição de em fatores lineares, segue-se (veja abaixo) que este é sempre o caso. ${\ displaystyle m}$${\ displaystyle A_ {i + 1}}$${\ displaystyle Pi (x)}$

Com base nisso, pode-se mostrar (Francis 1962 segundo Bai / Demmel) que a primeira coluna de , que também é proporcional à primeira coluna de , determina completamente a matriz subsequente . Mais precisamente, uma matriz ortogonal cuja primeira coluna é proporcional a é criada trazendo a matriz transformada de volta à forma de Hessenberg. Uma vez que apenas os componentes das linhas diferem de zero em, uma modificação da matriz de identidade pode estar no bloco superior esquerdo , com a . ${\ displaystyle x}$${\ displaystyle p_ {i} (A_ {i})}$${\ displaystyle Q_ {i}}$${\ displaystyle A_ {i + 1} = Q_ {i} ^ {- 1} A_ {i} Q_ {i}}$${\ displaystyle U}$${\ displaystyle x}$${\ displaystyle A_ {i + 1}}$${\ displaystyle U ^ {- 1} A_ {i} U}$${\ displaystyle x}$${\ displaystyle 1, \ ldots, m + 1}$${\ displaystyle U}$${\ displaystyle s \ times s}$${\ displaystyle s> m}$

Variantes do algoritmo QR

Iteração QR simples

Ele é eleito. O método pode ser fornecido resumidamente como decomposição QR seguida pela multiplicação na ordem inversa. Este procedimento é a generalização direta do método das potências simultâneas para determinar os primeiros autovalores de uma matriz. Esta conexão é derivada da iteração do subespaço . Um método de potência inversa simultânea também é executado indiretamente. ${\ displaystyle p_ {i} (A) = A}$${\ displaystyle A_ {i} = Q_ {i} R_ {i}}$${\ displaystyle A_ {i + 1} = R_ {i} Q_ {i}}$${\ displaystyle k}$

Algoritmo QR com mudanças simples

Está definido. Isso significa que o método também pode ser exibido como uma decomposição QR seguida pela multiplicação corrigida para o deslocamento . Normalmente, é feita uma tentativa de aproximar o menor autovalor com o deslocamento . O último elemento diagonal pode ser selecionado para isso. A iteração QR simples resulta da definição de todos os turnos para zero. ${\ displaystyle p_ {i} (A) = A- \ kappa _ {i} I}$${\ displaystyle A_ {i} - \ kappa _ {i} I = Q_ {i} R_ {i}}$${\ displaystyle A_ {i + 1} = R_ {i} Q_ {i} + \ kappa _ {i} I}$${\ displaystyle \ kappa _ {i}}$${\ displaystyle \ kappa _ {i} = (A_ {i}) _ {n, n}}$

Tem assim deve formulário Hessenberg como um produto de uma matriz e uma matriz sem diagonais secundárias também têm forma Hessenberg. O mesmo, portanto, também se aplica a . Se o algoritmo QR for colocado na forma de Hessenberg na preparação , isso será mantido em todo o algoritmo. ${\ displaystyle A_ {i}}$${\ displaystyle Q_ {i} = (A_ {i} - \ kappa _ {i} I) R_ {i} ^ {- 1}}$${\ displaystyle A_ {i + 1} = R_ {i} Q_ {i} + \ kappa _ {i} I}$${\ displaystyle A_ {1} = Q_ {0} ^ {- 1} AQ_ {0}}$

Mudanças simples para matrizes simétricas

Uma matriz real simétrica possui apenas autovalores reais. A simetria é preservada em todos eles durante o algoritmo QR . Para matrizes simétricas, Wilkinson (1965) sugeriu que o valor próprio da submatriz inferior direita${\ displaystyle A_ {1} = A}$${\ displaystyle A_ {i}}$${\ displaystyle 2 \ vezes 2}$

${\ displaystyle {\ begin {pmatrix} a_ {n-1, n-1} & a_ {n-1, n} \\ a_ {n, n-1} & a_ {n, n} \ end {pmatrix} }}$

do que escolher uma mudança que está mais perto . Wilkinson mostrou que a sequência da matriz determinada dessa forma converge para uma matriz diagonal cujos elementos da diagonal são os autovalores de . A velocidade de convergência é quadrática. ${\ displaystyle a_ {n, n}}$${\ displaystyle (A_ {i}) _ {i \ in \ mathbb {N}}}$${\ displaystyle A = A_ {1}}$

Algoritmo QR com turnos duplos

Um par de mudanças simples pode ser combinado em uma etapa de iteração. Como consequência, isso significa que deslocamentos complexos podem ser dispensados ​​para matrizes reais. Na notação dada acima é

${\ displaystyle (A_ {1} - \ kappa _ {2} I) (A_ {1} - \ kappa _ {1} I) = (A_ {1} - \ kappa _ {2} I) Q_ {1} R_ {1} = Q_ {1} (A_ {2} - \ kappa _ {2} I) R_ {1} = Q_ {1} Q_ {2} R_ {2} R_ {1}}$

uma decomposição QR para o polinômio quadrático , avaliado em . Os coeficientes deste polinômio são reais mesmo para um par conjugado de deslocamentos complexos. Assim, autovalores complexos de matrizes reais também podem ser aproximados sem que números complexos apareçam no cálculo. ${\ displaystyle p_ {1} (x) = x ^ {2} - (\ kappa _ {1} + \ kappa _ {2}) x + \ kappa _ {1} \ kappa _ {2}}$${\ displaystyle A_ {1}}$

Uma escolha comum para este deslocamento duplo consiste nos valores próprios da submatriz inferior direita , ou seja, H. o polinômio quadrático é a característica deste bloco, ${\ displaystyle 2 \ vezes 2}$

${\ displaystyle p_ {i} (x) = x ^ {2} - (a_ {n-1, n-1} + a_ {n, n}) x + a_ {n-1, n-1} a_ { n, n} -a_ {n-1, n} a_ {n, n-1}}$.

Algoritmo QR com vários turnos

É especificado um número maior, mas significativamente menor do que o tamanho da matriz . O polinômio pode ser escolhido como o polinômio característico da submatriz quadrática inferior direita da matriz atual . Outra estratégia são os autovalores do mais baixo para determinar -Teilmatriz e a quantidade que os menores autovalores selecionam entre eles. Com eles, uma decomposição QR de ${\ displaystyle m}$${\ displaystyle 2}$${\ displaystyle n}$${\ displaystyle A}$${\ displaystyle p_ {i} (x)}$${\ displaystyle m \ times m}$${\ displaystyle A_ {i}}$${\ displaystyle s> m}$${\ displaystyle s \ times s}$${\ displaystyle m}$${\ displaystyle s_ {1}, \ dots, s_ {m}}$

${\ displaystyle p_ {i} (A_ {i}) = (A_ {i} -s_ {1} I) (A_ {i} -s_ {2} I) \ cdots (A_ {i} -s_ {m} I) = Q_ {i} R_ {i}}$ e ${\ displaystyle A_ {i + 1} = Q_ {i} ^ {- 1} A_ {i} Q_ {i}}$

certamente.

Com um método multishift, muitas vezes consegue-se que os componentes do bloco inferior esquerdo se tornem pequenos, particularmente rapidamente na sequência das matrizes iteradas, dividindo assim o problema dos autovalores. ${\ displaystyle (n-m + 1, \ dots, n) \ times (1, \ dots, nm)}$

Iteração multishift implícita

Combinar vários turnos na forma geral consome muito tempo. Como mencionado acima, o esforço pode ser reduzido produzindo a forma de Hessenberg em uma etapa preparatória . Uma vez que cada etapa multishift pode ser composta de turnos individuais (mesmo complexos), a forma de Hessenberg é mantida em todo o algoritmo. ${\ displaystyle A_ {1} = Q_ {0} ^ {- 1} AQ_ {0}}$

Isso permite que o algoritmo QR seja convertido em um algoritmo de "perseguição de protuberância" , que cria uma depressão na forma de Hessenberg na extremidade superior da diagonal e, em seguida, "persegue" na diagonal e para fora da matriz na extremidade inferior .

1. para fazer${\ displaystyle j \ in \ mathbb {N} _ {0}}$
2. Calcule o polinômio de acordo com uma das variantes fornecidas,${\ displaystyle p (x)}$
3. Encontre o vetor .${\ displaystyle x = p (A_ {j}) e_ {1}}$
4. Encontre um reflexo do primeiro vetor unitário. Uma vez que apenas os primeiros componentes não desaparecem, esta reflexão tem uma forma de bloco simples.${\ displaystyle x}$${\ displaystyle x}$${\ displaystyle m + 1}$
5. Forme a matriz e transforme-a para que fique na forma de Hessenberg novamente.${\ displaystyle {\ tilde {A}} = U ^ {- 1} A_ {j} U}$${\ displaystyle A_ {j + 1} = Q ^ {- 1} U ^ {- 1} A_ {j} UQ}$
6. fim para

Se os reflexos domésticos forem colocados juntos , eles terão uma forma diagonal em bloco . ${\ displaystyle Q}$${\ displaystyle Q = P_ {1} P_ {2} \ cdots P_ {n-1}}$${\ displaystyle P_ {k} = \ mathrm {diag} (I_ {k}, {\ tilde {P}} _ {k}, I _ {\ max (0, nkm)})}$

Notas sobre a funcionalidade

Transformações de similaridade

As matrizes calculadas no algoritmo QR são unitariamente semelhantes entre si, uma vez que devido a ${\ displaystyle A_ {i} - \ kappa _ {i} I = Q_ {i} R_ {i} \ quad \ Leftrightarrow \ quad R_ {i} = Q_ {i} ^ {H} (A_ {i} - \ kappa _ {i} I)}$

${\ displaystyle A_ {i + 1} = R_ {i} Q_ {i} + \ kappa _ {i} I = Q_ {i} ^ {H} (A_ {i} - \ kappa _ {i} I) Q_ {i} + \ kappa _ {i} I = Q_ {i} ^ {H} A_ {i} Q_ {i} - \ kappa _ {i} Q_ {i} ^ {H} Q_ {i} + \ kappa _ {i} I = Q_ {i} ^ {H} A_ {i} Q_ {i}}$

se aplica. Isso significa que todas as matrizes têm os mesmos autovalores (contados com a multiplicidade algébrica e geométrica). ${\ displaystyle A_ {i}}$

Escolha de turnos, convergência

Uma escolha simples, mas não muito eficaz, é escolher turnos iguais a zero. As iterações do algoritmo resultante, o algoritmo QR em sua forma básica, convergem parcialmente, se todos os autovalores diferirem em seu valor absoluto, para uma matriz triangular superior com os autovalores na diagonal. Convergência parcial aqui significa que os elementos do triângulo inferior vão em direção a zero e os elementos diagonais em direção aos autovalores. Portanto, nada é dito sobre os elementos do triângulo superior . ${\ displaystyle A_ {i}}$${\ displaystyle A_ {i}}$

Se os deslocamentos forem selecionados como o elemento da matriz na parte inferior direita da iteração atual, ou seja , o algoritmo converge de forma quadrada ou mesmo cúbica sob circunstâncias adequadas. Essa mudança é conhecida como mudança de quociente de Rayleigh porque está relacionada a um quociente de Rayleigh por meio da iteração inversa . ${\ displaystyle \ kappa _ {i} = a_ {nn} ^ {(i)}}$

Ao calcular em real ( ), gostaria de calcular a forma Schur real e ainda ser capaz de trabalhar com autovalores complexos conjugados. Existem várias estratégias de mudança para isso. ${\ displaystyle A \ in \ mathbb {R} ^ {n \ times n}}$

Uma extensão das mudanças simples é a mudança de Wilkinson em homenagem a James Hardy Wilkinson . Para a mudança de Wilkinson, o valor próprio mais próximo do último elemento da matriz torna-se a última matriz de subseção principal ${\ displaystyle 2 \ vezes 2}$

${\ displaystyle {\ begin {pmatrix} a_ {n-1, n-1} ^ {(i)} & a_ {n-1, n} ^ {(i)} \\ a_ {n, n-1} ^ {(i)} & a_ {n, n} ^ {(i)} \ end {pmatriz}}}$

usava.

O algoritmo QR como uma extensão do método de potência

Para a análise do algoritmo, os efeitos de matriz adicionais dos produtos são acumulados e , definido. Os produtos de matrizes ortogonais ou unitárias são novamente matrizes ortogonais ou unitárias, e os produtos de matrizes triangulares superiores direitas são novamente matrizes triangulares superiores direitas. As matrizes da iteração QR resultam de transformações de similaridade , porque ${\ displaystyle {\ tilde {Q}} _ {k} = Q_ {1} Q_ {2} \ cdots Q_ {k}}$${\ displaystyle {\ tilde {R}} _ {k} = R_ {k} R_ {k-1} \ cdots R_ {2} R_ {1}}$${\ displaystyle k \ in \ mathbb {N}}$${\ displaystyle {\ tilde {Q}} _ {k}}$${\ displaystyle {\ tilde {R}} _ {k}}$${\ displaystyle A}$

${\ displaystyle A_ {1} = A, \; A_ {2} = R_ {1} Q_ {1} = Q_ {1} ^ {- 1} A_ {1} Q_ {1}, \; A_ {3} = Q_ {2} ^ {- 1} A_ {2} Q_ {2} = {\ til {Q}} _ {2} ^ {- 1} A {\ tilde {Q}} _ {2}, \ pontos , \; A_ {k} = {\ tilde {Q}} _ {k} ^ {- 1} A {\ tilde {Q}} _ {k}, \ dots}$.

Isso leva a decomposições QR dos poderes de : ${\ displaystyle A}$

${\ displaystyle {\ begin {align} A = &&& Q_ {1} R_ {1} & = & {\ tilde {Q}} _ {1} {\ tilde {R}} _ {1} \\ A ^ { 2} = & AQ_ {1} R_ {1} = Q_ {1} A_ {2} R_ {1} & = & Q_ {1} Q_ {2} R_ {2} R_ {1} & = & {\ til {Q}} _ {2} {\ tilde {R}} _ {2} \\\ vdots & \\ A ^ {k} = & A {\ tilde {Q}} _ {k-1} {\ til {R}} _ {k-1} = {\ tilde {Q}} _ {k-1} A_ {k} {\ tilde {R}} _ {k-1} & = & {\ tilde {Q} } _ {k -1} Q_ {k} R_ {k} {\ tilde {R}} _ {k-1} & = & {\ tilde {Q}} _ {k} {\ tilde {R}} _ {k} \ end {alinhado}}}$

No decorrer do algoritmo, as decomposições QR das potências da matriz são determinadas implicitamente . Devido à forma dessas decomposições, é verdade que, para cada uma, as primeiras colunas da matriz abrangem o mesmo subespaço que as primeiras colunas da matriz ; além disso, as colunas são ortonormais entre si. No entanto, essa é exatamente a situação após a -ésima etapa de uma iteração de potência simultânea. Os elementos diagonais de são as aproximações dos autovalores de . Portanto, as propriedades de convergência da iteração de energia podem ser transportadas: ${\ displaystyle A}$${\ displaystyle j = 1,2, \ ldots, n}$${\ displaystyle j}$${\ displaystyle A ^ {k}}$${\ displaystyle j}$${\ displaystyle {\ tilde {Q}} _ {k}}$${\ displaystyle {\ tilde {Q}} _ {k}}$${\ displaystyle k}$${\ displaystyle R_ {k}}$${\ displaystyle A {\ tilde {Q}} _ {k-1} = {\ tilde {Q}} _ {k} R_ {k}}$${\ displaystyle A}$

O algoritmo QR simples converge apenas se todos os autovalores diferirem uns dos outros em seus valores. São os autovalores após

${\ displaystyle | \ lambda _ {1} | <| \ lambda _ {2} | <\ dots <| \ lambda _ {n} |}$

ordenado, a velocidade de convergência é linear com um fator de contração que corresponde ao mínimo dos quocientes . ${\ displaystyle {\ tfrac {| \ lambda _ {k} |} {| \ lambda _ {k + 1} |}}}$

Em particular para matrizes reais, este algoritmo só pode convergir se todos os autovalores forem reais (visto que, de outra forma, pares conjugados complexos existiriam com a mesma quantidade). Esta situação é dada para todas as matrizes simétricas.

O algoritmo QR como uma iteração simultânea de potência inversa

Se for invertível, vale para transpor (para matrizes complexas o adjunto de Hermit ) o inverso de e todos os seus poderes ${\ displaystyle A}$${\ displaystyle A}$

${\ displaystyle (A ^ {- T}) ^ {k} = (A ^ {k}) ^ {- T} = ({\ tilde {R}} _ {k} ^ {- 1} {\ tilde { Q}} _ {k} ^ {- 1}) ^ {T} = {\ tilde {Q}} _ {k} {\ tilde {R}} _ {k} ^ {- T}}$

O inverso de uma matriz triangular direita superior é novamente uma matriz triangular direita superior, a transposta da qual é uma matriz triangular esquerda inferior. O algoritmo QR, portanto, também determina uma decomposição QL das potências de . Pela forma dessa decomposição, é evidente que para cada uma das últimas colunas de abrangem o mesmo subespaço que as últimas colunas de . Na última coluna de , uma iteração de potência inversa para é realizada, de modo que essa coluna converge para o autovetor dual para o menor autovalor de . No produto , o componente inferior esquerdo é o chamado quociente de Rayleigh da iteração de potência inversa. As propriedades de convergência são análogas às fornecidas acima. ${\ displaystyle A ^ {- T}}$${\ displaystyle j = 1,2, \ ldots, n}$${\ displaystyle j}$${\ displaystyle {\ tilde {Q}} _ {k}}$${\ displaystyle j}$${\ displaystyle (A ^ {- T}) ^ {k}}$${\ displaystyle {\ tilde {Q}} _ {k}}$${\ displaystyle A ^ {T}}$${\ displaystyle A}$${\ displaystyle {\ tilde {Q}} _ {k} ^ {T} A {\ tilde {Q}} _ {k} = A_ {k}}$${\ displaystyle (A_ {k}) _ {nn}}$

Links da web

• LP: Procedimento QR para EWP geral , Georg-August-Universität Göttingen

literatura

• Gisela Engeln-Müllges, Klaus Niederdrenk, Reinhard Wodicka: Algoritmos Numéricos . 10ª edição. Springer-Verlag, Berlin, Heidelberg 2011, ISBN 978-3-642-13472-2 , Seção 7.6 'Determinação dos valores próprios de matrizes tridiagonais simétricas positivamente definidas usando o algoritmo QD' e 7.7 'Transformações na forma de Hessenberg, Procedimento LR e QR '. 
• JGF Francis (1961): The QR Transformation: A Unitary Analogue to the LR Transformation - Part 1 . The Computer Journal Vol. 4 (3), pp. 265-271. doi : 10.1093 / comjnl / 4.3.265
• JGF Francis (1962): The QR Transformation - Part 2 . The Computer Journal 1962 4 (4): 332-345; ( online )
• David S. Watkins (1982): Compreendendo o algoritmo QR , SIAM Review, Vol. 24, pp. 427-440 ( JSTOR )
• Z. Bai; J. Demmel (1989): Em uma implementação de bloco da iteração QR multishift de Hessenberg , International Journal of High Speed ​​Computing, Vol. 1 (1), pp. 97-112. (veja as notas de trabalho do LAPACK )
• AA Dubrulle; GH Golub (1994): Uma iteração QR multishift sem cálculo dos deslocamentos . Numerical Algorithms, Vol 7, pp 173-181
• K. Braman; R. Byers; R. Mathias (2002): The Multishift QR Algorithm. Parte I: Mantendo Mudanças Bem Focadas e Desempenho de Nível 3 (PDF; 224 kB). SIAM Journal on Matrix Analysis and Applications, Vol. 23, No. 4, pp. 929-947
• K. Braman; R. Byers; R. Mathias (2002): The Multishift QR Algorithm. Parte II: Deflação Antecipada Agressiva (PDF; 265 kB). SIAM Journal on Matrix Analysis and Applications, Vol. 23, No. 4, pp. 948-989
• David S. Watkins: O algoritmo QR revisitado (PDF; 417 kB), SIAM Review, Vol. 50, No. 1, pp. 133-145