Sistemas Lineares

Prévia do material em texto

UNIVERSIDADE FEDERAL DO OESTE DO PARÁ 
INSTITUTO DE ENGENHARIA E GEOCIÊNCIAS 
PROGRAMA DE CIÊNCIA E TECNOLOGIA 
ENGENHARIA FÍSICA 
 
 
 
 
SISTEMAS LINEARES 
 
 
Ana Karina Monteiro Bentes 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Santarém – Pará 
 
Ana Karina Monteiro Bentes 
 
 
 
SISTEMAS LINEARES 
 
 
 
 Trabalho avaliativo para a disciplina Cálculo Numérico 
 Ministrada pelo Prof. Dr. Rodolfo Maduro do Instituto de Engenharia 
Geociência e Programa de Ciência e Tecnologia da Universidade Federal do Oeste do 
Pará – UFOPA. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Santarém – Pará 
 
1. Introdução 
Os Cálculos numéricos são técnicas pelas quais os problemas matemáticos são 
formulados de modo que possam ser resolvidos com operações aritméticas. 
Embora existam muitos tipos de métodos, eles têm algo em comum, geralmente 
envolvem grandes números de cálculos aritméticos que podem durar horas, dias, 
ou até mesmo meses. Tendo isso como fator limitante para cálculos numéricos, 
foram criados os métodos numéricos para a resolução de sistemas de equações 
lineares que são nada mais que técnicas (algoritmos) e tecnologias (uso do meio 
computacional para os cálculos). 
Na disciplina Cálculo Numérico, o uso da ferramenta computacional Scilab 
terá grande importância para incrementos dos cálculos numéricos. Tendo como 
passo inicial os métodos diretos (eliminação de Gauss e decomposição LU) e os 
métodos iterativos (Jacobi e Seidel). No final será feita uma análise comparando os 
métodos, obtendo um ranking do método que teve melhor desempenho, ou seja, 
convergência mais rápida. 
2. Métodos Diretos 
São aqueles que conduzem à solução, exata a menos de erros de 
arredondamento introduzidos pela máquina, após um número finito de passos. 
Ax = b  x = A-1b 
Pertencem a esta classe todos os métodos estudados no 1º e 2º graus. No 
entanto, esses métodos não são usados em problemas práticos quando o número de 
equações é elevado, pois apresentam problemas de desempenho. Surge então, a 
necessidade de utilizar técnicas mais avançadas e eficientes como: Método de 
Eliminação de Gauss e Decomposição LU. 
2.1.Método de Eliminação de Gauss 
Entre os métodos diretos, destacam-se os métodos de eliminação que evitam o 
cálculo direto da matriz inversa de A e, além disto, não apresentam problemas com 
o tempo de execução como a regra de Cramer. 
O método da Eliminação de Gauss consiste em transformar o sistema linear 
original num sistema linear equivalente com matriz dos coeficientes triangular 
superior, pois estes são de resolução imediata. Dizemos que dois sistemas lineares 
são equivalentes quando possuem a mesma solução. 
Algoritmo para a resolução de um Sistema Triangular Superior: 
Dado um sistema triangular n x n com elementos da diagonal da matriz A não 
nulos, as variáveis xn, xn-1, xn-2, ... x2, x1 são obtidas assim: 
Xn = bn/ann 
Para k = (n -1), ...., 1 
s = 0 
Para j = (k +1), ..., n 
s = s + akjxj 
xk = (bk - s)/akk 
 
Algoritmo para a resolução de Ax = b através da Eliminação de Gauss: 
Seja o sistema linear Ax = b, A: n x n, x: n x 1, b: n x 1. 
Supor que o elemento que está na posição akk é diferente de zero no início da 
etapa k. 
Eliminação: 
Para k = 1, ..., n – 1 
Para i = k + 1, ..., n 
m = aik/akk 
aik = 0 
Para j = k + 1, ..., n 
aij = aij - makj 
bi = bi - mbk 
Resolução do sistema: 
xn = bn/ann 
Para k = (n -1), ...., 2, 1 
s = 0 
Para j = (k +1), ..., n 
s = s + akjxj 
xk = (bk - s)/akk 
 
 
2.2.Método da Decomposição LU 
Seja o sistema linear Ax = b. 
O processo de fatoração para resolução deste sistema consiste em decompor a 
matriz A dos coeficientes em um produto de dois ou mais fatores e, em seguida, 
resolver uma sequência de sistemas lineares que nos conduzirá á solução do 
sistema linear original. 
A vantagem dos processos de fatoração é que podemos resolver qualquer 
sistema linear que tenha A como matriz dos coeficientes. Se o vetor b for alterado, 
a resolução do novo sistema linear será quase que imediata. A fatoração LU é um 
dos processos de fatoração mais empregados. Nesta fatoração a matriz L é 
triangular inferior com diagonal unitária e matriz U é triangular superior. 
Os cálculos dos fatores L e U podem ser obtidos através de fórmulas para os 
elementos lij e uij, ou então, podem ser construídos usando a ideia básica do método 
da Eliminação de Gauss. 
3. Métodos Iterativos ou Indiretos 
São aqueles que se baseiam na construção de sequências de aproximações. A 
cada passo, os valores calculados anteriormente são utilizados para reforçar a 
aproximação. 
Ax = b  xk+1 = xk + d 
O resultado obtido é aproximado. 
Geralmente são utilizados os seguintes critérios de parada para as iterações: 
Limitação no número de iterações e Determinação de uma tolerância para a 
exatidão da solução. Tem como desvantagem não convergir para a solução exata e 
podem ser inviáveis quando o sistema é muito grande ou mal condicionado. 
Os métodos iterativos são: Método de Jacobi e Método de Seidel. 
3.1.Método de Jacobi 
Cada coordenada do vetor correspondente à nova aproximação é calculada a 
partir da respectiva equação do sistema, utilizando-se as demais coordenadas do 
vetor aproximação da iteração anterior. 
De forma genérica tem-se o sistema n x n abaixo: 
 
Onde a ≠ 0, i = 1, ..., n. 
Pode-se então, isolar os termos do vetor de incógnitas x, da seguinte forma: 
 
Desta forma, podemos montar a matriz C e o vetor g: 
 
Então, pode-se calcular o vetor solução para cada iteração k, como sendo: 
x
(k)
 = C x
(x-1)
 + g 
Ou generalizando para os termos xi do vetor solução de uma iteração k: 
 
 
 Algoritmo 
Enquanto 
 dist > tolerância 
 nite < número máximo de iterações 
 então: 
 nite = nite + 1 
 Para i = 1,..., n 
 s = bi 
 Para j = 1,..., n 
 Se i for diferente de j 
 s = s – aij * x0j 
 Fim 
 Fim 
 xi = s/aii 
 Fim 
 dist = norma (x – x0) 
 x0 = x 
 Fim 
3.2. Método de Seidel 
Cada coordenada do vetor correspondente à nova aproximação é calculada a 
partir da respectiva equação do sistema, utilizando-se as coordenadas do vetor 
aproximação da iteração anterior, quando essas ainda não foram calculadas na 
iteração corrente, e as coordenadas do vetor aproximação da iteração corrente, no 
caso contrário. 
De forma genérica tem-se o sistema n x n abaixo: 
 
Onde a ≠ 0, i = 1,...,n. 
Isolando x, através da separação pela diagonal, conforme foi feito no método 
anterior: 
 
Numa dada iteração (k), ao calcular-se x1, ainda não se tem posse dos demais 
valores do vetor solução do sistema (x2, x3, ..., xn). Por esse motivo, utilizam-se 
valores do vetor solução da iteração (k - 1). Já para os outros elementos de x
(k)
, 
pode-se fazer uso de valores já calculados na iteração corrente, por exemplo, ao 
calcular-se x2 já se conhece previamente o valor de x1, e ao calcular-se x3, já se 
conhece os valores de x1 e x2. 
Este fato constitui a principal diferença entre os métodos de Jacobi e Seidel. 
Generalizando, parauma iteração (k) qualquer, um elemento i do vetor do 
vetor solução pode ser representado da seguinte forma: 
 
 
 Algoritmo 
Enquanto 
 dist > tolerância 
 nite < número máximo de iterações 
 então: 
 nite = nite + 1 
 Para i = 1,..., n 
 s0 = bi 
 s1 = 0; 
 Para j = 1,...,(i-1) 
 s0 = s0 – aij * xj 
 Fim 
 Para j = (i+1),..., n 
 s1 = s1 – aij * x0j 
 Fim 
 xi = (s0 + s1)/aii 
 Fim 
 dist = norma (x – x0) 
 x0 = x 
 Fim 
3.3.Comparação, Vantagens e Desvantagens dos Métodos de Solução de 
Sistemas Lineares 
 
3.3.1. Métodos Diretos: 
o Processos finitos (convergência para qualquer sistema não singular); 
o Apresentam problemas com erros de arredondamento; 
o Utilizam-se técnicas de pivoteamento para amenizar os problemas de 
arredondamento; 
o O processo de triangularização destrói a esparsidade da matriz de 
coeficientes. Técnicas de Esparsidade são utilizadas para amenizar o 
enchimento da matriz. 
o Redução de esforço computacional é conseguida em soluções para 
vetores independentes adicionais com a matriz de coeficientes mantida 
constante, com a utilização da fatoração LU; 
o Para matrizes cheias a solução requer 
3n
operações sem considerar o 
pivoteamento. 
 
3.3.2. Métodos Iterativos 
o Provavelmente mais eficientes para sistemas de grande porte, 
principalmente com a utilização de computação de alto desempenho 
(vetorial e paralela); 
o Tem convergência assegurada apenas sob certas condições; 
o Conserva a esparsidade da matriz de coeficientes; 
o Os métodos de Jacobi e Seidel requerem 
22n
operações por iterações; 
o Poucas vantagens adicionais são conseguidas em soluções para vetores 
independentes adicionais com a matriz de coeficientes mantida 
constante, como no caso da fatoração LU; 
o Carregam menos erros de arredondamento no processo, tendo em vista 
que a convergência uma vez assegurada independe da aproximação 
inicial. Somente os erros da última iteração afetam a solução. 
3.4.Matriz Inversa 
A · [x V Y] = [b V I] 
 
A partir daqui, elimina-se os elementos superiores e inferiores ao pivô: 
 
Finalmente, normaliza-se a matriz, de forma que à esquerda ficamos com uma 
matriz identidade. Obtém-se, assim, o vetor solução do problema e a matriz inversa 
de A. 
 
3.4.1. Cálculo do determinante de uma matriz A 
Pelas propriedades do determinante, o determinante não se altera se somarmos 
um múltiplo de uma linha da matriz à outra, ou seja, se efetuarmos uma 
combinação linear entre as linhas. Assim, a eliminação de Gauss para se obtiver 
uma matriz triangular superior não afeta o valor do determinante. 
 
Mas o determinante de uma matriz triangular é o produto dos elementos da 
matriz. Portanto, det A = det U = a’11 a’12 ... ha’nn . 
3.4.2. Procedimentos 
I. Escolha um sistema linear de sua preferência com o mínimo quatro 
equações e quatro incógnitas, cuja solução seja conhecida. 
II. Implementar no programa SCILAB, os seguintes algoritmos dos 
métodos para resolver o sistema linear escolhido: Método da 
Eliminação Gaussiana, Método da Decomposição LU, Método de 
Jacobi e Método de Seidel. 
III. Apresente as soluções numéricas obtidas pelos métodos e compare-as. 
4. Resultado e Discussão 
O sistema escolhido foi 
3x1 + 2x2 + 0x3 + x4 = 3 
9x1 + 8x2 - 3x3 + 4x4 = 6 
-6x1 + 4x2 - 8x3 + 0x4 = -16 
3x1 - 8x2 + 3x3 - 4x4 = 18 
Que apresenta como solução {0, 0, 2, 3}. 
Na tabela abaixo as soluções numéricas obtidas pelos métodos. 
Tabela 1. Soluções numéricas dos métodos diretos e iterativos. 
MÉTODO SOLUÇÃO NUMÉRICA 
Eliminação Gaussiana {0, 1,5, 2, 0} 
Decomposição LU {2, -1, 0, -1} 
Jacobi Método não convergiu 
Seidel {1, -0,375, 1,0625, -2, 2031} iteração 5 
O método da Eliminação de Gauss é o mais simples para a solução de 
equações. O método de Gauss possui várias características que o tornam 
interessantes, mesmo que haja métodos mais eficientes. Uma característica 
interessante do método é que quando aplicado para resolver um conjunto de 
equações lineares, a eliminação de Gauss produz tanto a solução das equações 
(para um ou mais vetores de termos independentes) quanto a inversa da matriz A. 
outra característica importante é que o método é tão estável quanto outro método 
direto, desde que seja empregado o pivoteamento. Por outro, possui algumas 
deficiências como: se a matriz inversa não for desejada, a eliminação de Gauss é 
tipicamente 3 (três) vezes mais lenta que a melhor alternativa disponível. Quanto o 
empregamos para mais de equação matricial (Axj = bj), todos os vetores de termos 
independentes devem ser armazenados na memória e manipulados 
simultaneamente. 
O método de decomposição LU apresenta como vantagem a solução de um 
sistema triangular trivial. Dessa forma, o sistema é resolvido por substituição para 
frente e substituição para trás. 
O número de operações necessárias para efetuar a decomposição é da ordem 
de 1/3n
3
, exatamente o mesmo número de passos necessários para fazer a 
eliminação de Gauss. Na literatura, frequentemente cita-se uma vantagem da 
decomposição LU que é o fato de que uma vez tendo-se L e U é trivial obter a 
solução para um número arbitrário de vetores de termos independentes (ou seja, 
resolve-se facilmente um conjunto de sistema de equações lineares). Entretanto, o 
mesmo procedimento pode ser feito de forma igualmente eficiente a partir do 
procedimento de solução simultânea de várias equações matriciais. 
Então, dos métodos diretos pode-se concluir que o método da Eliminação de 
Gauss e o método da Decomposição LU são igualmente eficientes quando se trata 
de resolver um sistema de equações lineares, ou um conjunto de sistemas de 
equações lineares. Porém, do sistema linear escolhido, o método da Eliminação de 
Gauss é o que mais se aproximou da solução real do sistema. 
Partindo da premissa C = M
-1
N = M
-1
(A-M) = I – M-1 quanto mais próxima de 
A for a matriz M, mais próximo da matriz zero será o valor C, e consequentemente, 
mais rápida será a convergência do método iterativo. Então, normalmente M está 
“mais próxima” de A no caso do Método de Seidel (M = L+D) do que no caso do 
Método de Jacobi (M = D). Portanto, habitualmente o método de Seidel converge 
mais rapidamente. Há, no entanto, casos em que isso não acontece, e um método 
podem convergir e o outro não (como o de Jacobi). 
A menos que as matrizes possuam zonas apreciáveis com elementos nulos, 
ambos os métodos iterativos exigem um cálculo total de 2n
2
 operações, por cada 
iterada, o que implica que, se forem necessárias mais que n/3 iterações, exigimos 
mais operações do que num método direto. 
A diferença entre os dois métodos é que, em Jacobi, utilizam-se todos os 
valores da iteração anterior para calcular o valor da variável da diagonal, e no 
Seidel, também se utiliza dos valores já calculados na mesma iteração o que 
permite uma convergência mais rápida. 
5. BIBLIOGRÁFIA 
RUGGIERO, M. e LOPES, V. Cálculo Numérico: Aspectos Teóricos e 
Computacionais. McGraw-Hill, 1996. 
BARROSO, CAMPOS FILHO, CARVALHO, M. Cálculo Numérico Com 
Aplicações. Editora Harbra, 1987.