A preconditioner for least squares problems

Abstract

Resumo: Esta dissertação enfoca o problema de minimos quadrados, min ||Ax — b\\2j e seus métodos de solução. Dentre eles, estudamos os métodos iterativos precondicionados que utilizam como precondicionador uma submatriz A\ da matriz de coeficientes A. O método do gradiente conjugado precondicionado, bem como os métodos SOR em blocos tanto para o caso em que a matriz A tem posto cheio como quando tem posto deficiente, são analisados e seus algoritmos são apresentados. Nesses algoritmos existe a necessidade de se resolver sistemas lineares envolvendo a matriz A\. O objetivo desta dissertação é desenvolver métodos para se encontrar tal matriz precondicionadora Ai, levando-se em conta tanto o custo de sua obtenção como o de sua aplicação nos sistemas citados acima. Para tanto, duas alternativas são sugeridas. Primeiro, desenvolvemos um método baseado nos métodos de projeção para resolução de sistemas de equações lineares. Alguns teoremas são propostos, e demonstramos como é possivel usar a idéia dos métodos de projeção para se determinar o conjunto de linhas linearmente independentes de A. (Estamos supondo que A £ R mXn com m > n e posto(A)= k < n). Em seguida, um algoritmo é formulado e sua aplicabilidade é analisada. Um segundo método é sugerido. Este método se baseia na decomposição QR da matriz AT. Esta decomposição é feita usando-se transformações de Householder. Durante a fatorização, selecionamos as colunas linearmente independentes de AT, e, na verdade, decompomos apenas a matriz Af (Af =QR). A vantagem de se aplicar este procedimento ao método SOR em dois blocos para problemas onde a matriz A tem posto deficiente é analisada e explorada. Estes dois métodos são implementados computacionalmente em Fortran 90. São realizados experimentos numéricos com matrizes de teste retiradas da coleção Harwell-Boeing e com algumas matrizes retiradas de problemas de programação linear, todas disponiveis num site na Internet. O objetivo desses experimentos é o de avaliar a viabilidade dos métodos aqui desenvolvidos, analisar seu comportamento e comparar sua eficiência. São coletados os tempos de CPU gastos para se encontrar a submatriz A\ por ambos os métodos. (O primeiro denominado BS Algorithm e o segundo denominado HQR Algorithm). O BS Algorithm se mostrou sempre mais rápido que o HQR Algorithm; explicações para este fato são citadas e analisadas. Por fim, assuntos correlatos e complementares a esta dissertação são propostos como trabalhos futuros

Abstract: It is well known that the 2-block SOR method and some preconditioned conjugate gradient methods for solving linear least squares problems have very good convergency property. The key problem of the implementation of these methods is to obtain the preconditioner A\, which is some row full-rank submatrix of the original matrix A. The purpose of this dissertation is to establish some numerical methods to find the desired preconditioner A\ directly from A such that these methods save costs both in the construction of the preconditioner A\ and in the implementation of the preconditioned iterative methods for solving least squares problems. With this goal in mind, two methods are presented and studied, and two algorithms are developed, namely, BS Algorithm and HQR Algorithm. The implementation of these algorithms has been considered and both algorithms have been coded in Fortran 90. Numerical experiments based on realistic problems are performed to evaluate the viability of the discussed methods, to analyse their behavior and to compare their efhciency. The algorithms are tested on a set of sparse test matrices from the Harwell-Boeing collection and from a collection of linear programming problems