Um dos problemas que aparece com elevada frequência nas aplicações é a resolução de sistemas de equações lineares.

        Um sistema de equações lineares é uma colecção finita de equações lineares (todas nas mesmas incógnitas) consideradas em conjunto e apresenta-se abreviadamente na forma Ax = b, ou A é a matriz do sistema, x é a matriz-coluna das incógnitas e b a matriz coluna dos segundos membros ou abreviadamente o segundo membro do sistema.

        Uma solução de um sistema de equações lineares nas incógnitas x₁, ..., x_n é uma sequência ordenada (a_1, ...., a_n) de números tais que as substituições x_i=a; i= 1,...,n transforma todas as equações do sistema em identidades verdadeiras.

         Resolver um sistema de equações lineares é determinar todas as suas soluções ou provar que não existe nenhuma. 

        Um sistema de equações lineares que tenha pelo menos uma solução diz-se possível (determinado se só tiver uma , indeterminado se tiver mais do que uma). Um sistema de equações lineares que não tenha nenhuma solução diz-se impossível. 

        Deste modo torna-se imprescindível dispor de vários métodos que sejam eficazes no que respeita à solução desse sistema, sobretudo quando o sistema possui uma dimensão n grande. Este “problema” é de tal importância que accionou os mecanismos que estiveram na base da criação e desenvolvimento de computadores digitais que fossem capazes de resolver os sistemas de equações mencionados. É de referir que muitos modelos foram concebidos especialmente para este efeito, o que fez com que hoje em dia, a resolução de sistemas com um enorme número de equações (na ordem das centenas ou milhares) seja fácil e relativamente vulgar. 

        Geralmente os sistemas de equações lineares são classificados em duas categorias: métodos directos e métodos indirectos.

         Diz-se que um método é directo se permitir a obtenção de uma solução de um sistema que apresente um número finito de operações aritméticas. Se a solução do sistema apresentar um número infinito de operações, então o método diz-se iterativo.

         A escolha do método a utilizar está dependente do problema concreto que se pretende ver resolvido, bem como do conhecimento (aprofundado!) das várias opções disponíveis, seguido de um balanço enter as respectivas vantagens e desvantagens que o método apresente. 

        Existem como já foi referido, diferentes métodos, que permite a resolução de sistemas de equações lineares. De entre eles destacam-se: Método Directo e Método de Gauss.

      Método de Gauss

        Consiste essencialmente em transformar por etapas sucessivas a matriz original do sistema numa matriz triangular superior. Após obtenção da matriz transformada (matriz triangular superior) o sistema pode ser resolvido por substituição ascendente.

         Algoritmo de eliminação de Gauss

         Este é um método geral de resolver sistemas de equações lineares e consiste numa sequência de passos “elementares” que transformam o sistema dado num sistema muito fácil de resolver.

         Um passo elementar do método de eliminação de Gauss consiste na “adição membro a membro a uma equação de um múltiplo de outra”, de forma que na equação obtida, seja nulo o coeficiente de certa incógnita. Diz-se que se eliminou essa incógnita da equação.

         Os passos elementares são conduzidos de maneira a eliminar a incógnita x₁ de todas as equações a partir da 2ª, depois eliminar a incógnita x₂ de todas as equações a partir da 3ª, etc ...

         Deste processo resulta um novo sistema, digamos Ux = c equivalente ao sistema original, e cuja matriz U é uma matriz em escada.

         Com a obtenção de uma matriz em escada U termina a parte descendente do método de eliminação de Gauss. Neste momento verifica-se se o sistema obtido, Ux = c é possível, isto é , se não há equações com o primeiro membro nulo e o segundo não nulo.

         Se o sistema for possível resolve-se de “baixo para cima” (parte “ascendente” do algoritmo) obtendo se necessário algumas incógnitas em função das outras.

          Factorização LU

         O processo de condensação de Gauss (que consiste numa sequência de operações elementares sobre as linhas das matrizes A^(k), as quais podem ser expressas sob a forma de pré-multiplicações  desta matriz por matrizes triangulares elementares) conduz a uma expressão em que a matriz A surge sob a forma do produto de uma matriz L triangular inferior de diagonal unitária e de uma matriz U triangular superior – factorização triangular ou factorização LU da matriz A.

         A determinação da solução x, tendo determinado LU consiste na solução em solução de dois sistemas triangulares, sendo um inferior e outro superior..

         A factorização envolve apenas a matriz A e não o segundo membro b, intervindo este exclusivamente na fase de solução dos sistemas triangulares.

         Assim sendo, uma vez factorizada a matriz A, podemos resolver com esta matriz tantos sistemas de equações quantos quisermos, apenas à custa de substituições (ascendentes e descendentes). Isto revela uma vantagem sobre o método de eliminação de Gauss.

         Método de Doolittle

         Pretende-se factorizar uma matriz em termos de uma matriz L triangular inferior de diagonal unitária, e uma matriz U triangular superior.

       Difere da factorização proporcionada pelo método de Gauss na medida em que a factorização triangular quando existe é única residindo a diferença na ordem dos cálculos necessários à obtenção da factorização.

       Enquanto no método de Gauss os elementos de L e U vão sendo determinados por etapas à medida que a condensação avança, só ficando completamente calculados na sua forma final quando a frente de condensação passa por eles e os deixa para trás, no método de Doolittle os elementos de L e U são calculados de forma explícita e de uma única vez. Por esta razão, as formas de factorização do tipo da de Doolittle são designadas por compostas.

         Método de Crout

           É uma variante da factorização triangular da matriz A. Toma-se a matriz U como triangular de diagonal unitária e L como triangular inferior.

         Este método permite uma escolha de pivot com maior facilidade que no Método de Doolittle.

          Factorização LDU

          Consiste numa pequena alteração das factorizações de Doolittle e de Crout e tem a vantagem de atribuir às matrizes triangulares L e U um papel totalmente idêntico. Consiste em considerar que estas são ambas matrizes triangulares com diagonal unitária e tomar a factorização na seguinte forma A = LDU em que D é uma matriz diagonal.

         O método de Doolittle consiste em absorver a matriz D em U, ou seja A = L (DU) enquanto que o de Crout consiste em absorver D em L, ou seja A = (LD)U.

         Métodos Iterativos

         Os métodos iterativos distinguem-se dos métodos directos pelo facto de necessitarem de um número infinito de operações aritméticas para obter a solução.

         Como na realidade isto não é possível, os métodos iterativos estão condenados a terem de ser interrompidos, o que implica que poderão fornecer apenas uma solução aproximada para o sistema. No entanto os métodos iterativos são valiosos porque podem produzir boas aproximações com relativamente poucas iterações. Também é relevante o facto de a matriz A nunca ser alterada durante o processo iterativo (ao contrário do que acontece com os métodos directos).

         Assim sendo tira-se partido desta estrutura para economizar memória e tempo de cálculo.

       Método de Jacobi

         O método de Jacobi consiste em escolher ma matriz M a diagonal de A, ou seja M = D = diag A  e N = D - A =  - (L + U) em que L e U designam matrizes estritamente triangulares inferior e superior respectivamente (nota: é importante não confundir estas matrizes com as matrizes L e U da factorização triangular).

         Nesta decomposição supomos que D é uma matriz invertível, o que implica que os seus elementos diagonais sejam todos diferentes de zero. Se tal não acontecer, é possível colocar na diagonal elementos diferentes de zero por permutação de linhas e/ou colunas (designando-se a matriz resultante destas trocas por A.

           A matriz de iteração do método de Jacobi é dada por G_J = I – D^-1 (L+U).

         É relativamente fácil nos métodos iterativos tirar partido da espansidade da matriz A

         Neste método utilizam-se os valore x_i^(k) da iteração anterior para obter os valores x_i^(k+1) da iteração seguinte.

            Método de Gauss-Seidel

          Como foi anteriormente referido, no método de Jacobi são utilizados os valores x_i^(k) da iteração precedente para obter os valores x_i^(k+1) da iteração seguinte. No entanto, no momento em que se calcula x_i^(k+1) já são conhecidos valores “mais actuais” para x₁^(k+1),..., x_i-1^(k+1).

          O método de Gauss-Seidel adopta imediatamente estes valores, ou seja, logo a partir do momento em que é obtido um valor mais actualizado de uma incógnita x_i, este é usado sem ser necessário esperar pela actualização dos outros valores.

          No método de Gauss-Seidel a matriz M, conforme se pode verificar, é identificado com o triângulo inferior da matriz A, ou seja M = L+D; V = -U.

          É de referir que tanto o método de Gauss-Seidel como o método de Jacobi convergem quando as matrizes possuem diagonal estritamente dominante por linhas.

          Referências Bibliográficas:

          - Valença, Maria Raquel; "Análise Numérica", Universidade Aberta;

          - Pina, Heitor; "Métodos Numéricos", MacGrawHill. 

  Retroceder                             Inicio                            Avançar