The unsymmetric tridiagonal eigenvalue problem

Abstract

The development of satisfactory methods for reducing an unsymmetric matrix to tridiagonal form has been greatly hampered by the fact that there is not an accepted good algorithm for exploiting this form. Nevertheless, recently, promising elimination techniques for achieving a stable reduction to this form have been developed. But the standard QR algorithm destroys it immediately. Our work aims to fill this gap in the armoury of software tools for the matrix eigenvalue problem and so encourage the refinement of methods to reduce a matrix to tridiagonal form. The progressive quotient difference algorithm with shifts (qds) was presented by Rutishauser as early as 1954. It is equivalent to the shifted LR algorithm written in a special notation for tridiagonals. The much more recent differential qds (dqds) is a sophisticated variant of qds. The first contribution of this thesis is a new algorithm, 3dqds, that consists of three dqds steps performed implicitly and such that real arithmetic is maintained in the presence of complex eigenvalues. One advantage of our algorithm over the Hessenberg QR algorithm is that it preserves the tridiagonal form and thus reduces both storage and time. We present some accuracy results comparing a Matlab implementation of 3dqds with the function eig of that software. These preliminary results suggest the robustness of 3dqds algorithm. In contrast to the symmetric case, unsymmetric matrices can have a mixture of eigenvalues, some robust in the face of perturbations while others extremely sensitive. We present several condition numbers, some new, that take advantage of tridiagonal form. Ideally an algorithm should report these numbers along with each computed eigenvalue. On the theoretical side, we present a rigorous proof of a surprising result. It is well known that the greater the ratio of adjacent eigenvalues, the faster LR converges. Nevertheless, in exact arithmetic, LR still converges even when all the eigenvalues are equal and the Jordan form is one big block.

O desenvolvimento de métodos satisfatórios para reduzir uma matriz não simétrica à forma tridiagonal tem sido fortemente travado pelo facto de que não existe um bom algoritmo aceite para explorar esta forma. Contudo, recentemente, promissoras técnicas de eliminação para realizar esta redução de maneira estável foram desenvolvidas. Mas o algoritmo QR standard destrói a forma tridiagonal imediatamente. O nosso trabalho pretende colmatar esta lacuna no conjunto das ferramentas computacionais para o problema de cálculo de valores próprios e assim encorajar o aperfeiçoamento de métodos para redução de uma matriz à forma tridiagonal.

O algoritmo qds (progressive quotient difference with shifts) foi introduzido por Rutishauser e remonta a 1954. É equivalente à versão shifted do algoritmo LR escrita numa notação especial para matrizes tridiagonais. O muito mais recente algoritmo dqds (differential qds) é uma versão sofisticada do qds. Uma contribuição desta tese é um novo algoritmo, 3dqds, que consiste em três passos do dqds realizados implicitamente e tal que a aritmética real é mantida na presença de valores próprios complexos. Uma vantagem do nosso algoritmo em relação ao Hessenberg QR é que preserva a forma tridiagonal e assim reduz a necessidade de espaço em memória e o tempo de execução. Apresentamos alguns resultados numéricos comparando uma implementação do 3dqds em MATLAB com a função eig daquele software. Estes resultados preliminares sugerem a robustez do algoritmo 3dqds.

Em contraste com o caso simétrico, matrizes não simétricas podem ter um misto de valores próprios, alguns resistentes em face de perturbações enquanto outros extremamente sensíveis. Apresentamos vários números de condição, alguns novos, que tiram partido da forma tridiagonal. Idealmente, um algoritmo deve fazer acompanhar com estes números cada valor próprio calculado.

Do ponto de vista teórico, apresentamos também uma demonstração rigorosa de um resultado surpreendente. É bem conhecido que quanto maior for a razão entre valores próprios adjacentes, mais rapidamente o algoritmo LR converge. No entanto, em aritmética exacta, o algoritmo LR também converge mesmo quando todos os valores próprios são iguais e a forma de Jordan é um único bloco.