Iterative methods for rank deficient least squares problems

Abstract

Resumo: No presente trabalho estudamos as possibilidades de uso de diferentes métodos iterativos para tratar o problema dos mínimos quadrados de posto não cheio, a saber, min^Rn || b — Ax\\2, onde A é uma matriz m x n, n < m, tal que rank A — k <n. Este problema surge em muitas situações da Matemática Aplicada como, por ex emplo, na obtenção de soluções numéricas para equações diferenciais. As técnicas mais usualmente utilizadas para tratar este problema são as eficientes decomposições em valores singulares e a decomposição QR. Quando o problema envolve matrizes esparsas de grande porte as multiplicações efetuadas nos processos diretos citados podem destruir a esparsidade da matriz. Neste caso, os métodos iterativos são pre feríveis. Muito pouca referência tem sido feita aos métodos iterativos na literatura espe cializada. Miller e Neumann (1987) utilizaram o método SOR em blocos, subdividindo a matriz A em quatro blocos, obtendo uma sequüência semi-convergente. Neste trabalho, usando precondicionadores, combinamos o uso de métodos di retos com a utilização do método iterativo SOR em blocos bem como com uso do método do gradiente conjugado. Para tanto provamos alguns resultados preliminares nos quais estabelecemos uma equivalência, na norma 2, entre o problema original e um problema relacionado, porém de dimensão menor. Como o problema original não ( A i\ tem solução única, utilizando uma partição da matriz A em V A2 ) com rank Ai = k e, considerando a transformação dada por x = Ajy, com y G Rfe, obtemos um novo sistema de equações, com solução única y obtida por métodos iterativos. A solução x, de 2-norma mínima é, então, obtida pela relação x = A^y. A solução geral do problema é dada por x = Ajy + 2, onde 2 E Aí (A). Aplicando os método SOR para dois e três blocos, respectivamente, construimos os algoritmos correspondentes e analisamos a convergência dos métodos utilizados verificando que, para o método SOR em 2 blocos, sempre existe um intervalo de convergência enquanto que, no caso do método SOR de 3 blocos a existência de intervalo de convergência depende de condições extras. Outra vantagem do método VI SOR em 2 blocos é que o raio espectral da matriz iterativa correspondente é menor que o raio espectral da matriz iterativa correspondente do método de 3 blocos. Isto é, o método SOR em dois blocos converge assintoticamente mais rápido do que o método SOR em três blocos. Assim como para o caso do método SOR, para a aplicação do método do gradi ente conjugado desenvolvemos uns conceitos básicos e alguns resultados preliminares. Aqui apresentamos provas com abordagem diferente para alguns dos resultados bem conhecidos. Usando precondicionadores construimos três algoritmos distintos para resolver o problema dos mínimos quadrados de posto cheio equivalente ao problema dado. São estabelecidas limitações para as aproximações encontradas mostrando que a convergência do método do gradiente conjugado é de mesma ordem que a do SOR em 2 blocos. Além disso mostramos que, em cada passo do método do gradiente conju gado, obtemos uma aproximação melhor que a aproximação obtida no passo seguinte pelo método SOR em 2 blocos. Isto nos leva a concluir que, pelo menos teoricamente o método do gradiente conjugado precondicionado é superior aos métodos SOR estu dados. Futuramente temos intenção de realizar testes numéricos para avaliar a factibili- dade dos métodos propostos bem como para averiguar a eficácia, em termos práticos, dos resultados referentes às comparações entre os diferentes métodos iterativos estu dados

Abstract: The rank deficient least squares problem appears in many branches of the Applied Mathematics as, for example, in obtaining numerical Solutions to differential equa- tions, computational genetics and others. The usual and efficient methods to solve this problem are QR decomposition and singular value decomposition. But, for large sparse problems the iterative methods are preferable. Very few papers treat the it- erative methods for rank deficient problems. Miller and Neumann (1987) proposed 4-block SOR method to solve the problem but they reached semi-convergence. Here, using preconditioning techniques, we propose the 2-block SOR and the 3-block SOR methods and we establish that, analogous to the full rank case, there exists a relax- ation parameter to which the 2-block SOR method is always convergent. Besides this we apply the preconditioned gradient method to solve the rank deficient least squares problems. We derive three different algorithms and establish the convergence analysis for the method. Similarly to the work of Freund (1987), we conclude that the best iterative method to treat rank deficient least squares problems is the preconditioned gradient method