Connection between gaussian elimination and conjugate gradient type methods

Abstract

Resumo: No presente trabalho é proposto uma análise dos métodos Eliminação de Gauss (GE), Gradiente Conjugado a Esquerda (LCG), para sistema não simétrico e Gradiente Conjugado (CG), para sistema simétrico c definido positivo, com o objetivo de estabelecermos uma conecção entre a Eliminação de Gauss e Métodos do Tipo Gradiente Conjugado. Utilizando notação matricial, uma nova prova da equivalência entre o Método Gradiente Conjugado e o Método de Eliminação de Gauss é apresentada, para tanto provamos alguns resultados preliminares. Através da construção de um sistema conjugado a esquerda e da utilização de matrizes, elaboramos e implementamos um algoritmo que mostra a relação entre os vetores gradiente conjugado a esquerda e a matriz resultante da Eliminação de Gauss. Foram realizados testes numéricos com três tipos de matrizes: não simétrica definida positiva, não simétrica com autovalores negativos e complexos e simétrica definida positiva, provando a equivalência dos métodos Gradiente Conjugado a esquerda e Eliminação de Gauss. O estudo de algumas propriedades do método LCG resultou em um novo Teo rema que mostra a relação de ortogonalidade entre a diferença dos vetores residu ais e os vetores direção durante o processo iterativo do método LCG e uma nova técnica para superar o problema de breakdown para matrizes anti-simétricas. Implementamos os métodos Gradiente Conjugado a Esquerda e Eliminação de Gauss em Matlab, após a implementação foram realizados dois tipos dc exemplos numéricos: um mostra a equivalência e o outro mostra a performance do método Gradiente Conjugado a Esquerda para vários vetores iniciais

Abstract: Large svstems of linear equations arise in manv scientific applications, notably, partial differential equations discretized with Finite Difference, Finite Element and Boundary Element Methods. The most popular iterative method for sym- metric and positive definite systems of linear equations is the Conjugate Gradient Method, which has several nice properties: approximation iteratively by Krylov subspaces, nice convergence property, the short recurrence scheme and an optimal solution in the certain Krylov subspace. But for nonsymmetric systems, there is no short recurrence for computing the conjugate gradient vectors (in fact, there is no conjugate gradient vectors for nonsymmetric matrices). Research on nonsym metric system solvers has attracted much attention in recent years. The choice for the method is not so clear in the nonsymmetric case. Large systems can be solved with either direct methods or iterative methods. Very few papers treat the rela- tionship between iterative methods and direct methods for nonsymmetric matrix. Hestenes and Stiefel (1952 and 1980) showed that the Gradient Conjugate Method (CG) is equivalent to the Gaussian elimination (GE) for symmetric and positive definite matrix. Here, we give a new proof for this result. Besides this we will show that there is a connection between the Left Conjugate Gradient Method (LCG) proposed by Yuan, Golub and Plemons in 1999 and the Gaussian Elimination Method for nonsymmetric matrices. We derive a new theorem about relationship between residual vectors and left conjugate gradient vectors and have presented a special treatment to overcome the breakdown problem of the LCG method for skew-symmetric matrices. We have implemented the LCG method and the GE method in Ma,tlab and have given two types of numerical experiments: one to verify the equivalence, another to show the performance of the LCG method