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 x1, ..., xn é uma sequência ordenada (a1, ...., an) de números tais que as substituições xi=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 x1 de todas as equações a partir da 2ª, depois eliminar a incógnita x2 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 GJ = 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 xi(k) da iteração anterior para obter os valores xi(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 xi(k) da iteração precedente para obter os valores xi(k+1) da iteração seguinte. No entanto, no momento em que se calcula xi(k+1) já são conhecidos valores “mais actuais” para x1(k+1),..., xi-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 xi, 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.