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.
