03 - Resolução de Sistemas Lineares

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

�PAGE �
�PAGE �41�
03
RESOLUÇÃO DE SISTEMAS LINEARES - 1
Os métodos numéricos para resolução de um sistema linear podem ser divididos em dois grupos:
Métodos Diretos: são aqueles que, a menos de erros de arrendondamento, fornecem a solução exata do sistema linear, caso ela exista, após um número finito de operações.
Métodos Indiretos: são aqueles que geram uma sequência de vetores {x(k)}, a partir de uma aproximação inicial x(0). Sob certas condições esta sequência converge para a solução x*, caso ela exista.
MÉTODOS DIRETOS
MÉTODO DA ELIMINAÇÃO DE GAUSS
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 são equivalentes quando possuem a mesma solução.
Resolução de Sistemas Triangulares
Seja o sistema linear Ax = b, onde A: matriz nxn, triangular superior, com elementos da diagonal diferentes de zero. Escrevendo as equações deste sistema, temos:
Da última equação temos	
xn–1 pode então ser obtido da penúltima equação	
e assim sucessivamente obtém-se xn–2, ..., x2 e finalmente x1 
ALGORITMO: Resolução de um sistema triangular superior.
Dado um sistema triangular superior nxn com elementos da diagonal da matriz A não nulos, as variáveis xn, xn-1, xn-2, ..., x2, , x1 são assim obtidas:
xn = bn / ann
Para K = (n–1), ...,1
S = 0
Para j = (k + 1), ..., n
S = S + akjxj
xk = (bk – S) / akk
EXEMPLO:
K = 3
j = 4	S = a34x4 					
K = 2
j = 3	S = a23x3 
 j = 4	S = S + a24x4 = a23x3 + a24x4			
 K = 1
j = 2	S = a12x2 
j = 3	S = S + a13x3 = a12x2 + a13x3 		
j = 4	S = S + a14x4 = a12x2 + a13x3 + a14x4	
O método de Gauss consiste em transformar convenientemente o sistema linear original para obter um sistema linear equivalente com matriz dos coeficientes triangular superior. Para isto, o método faz uso do seguinte teorema:
TEOREMA:
Seja Ax = b um sistema linear. Aplicando sobre as equações deste sistema uma sequência de operações elementares escolhidas entre:
a) trocar duas equações;
b) multiplicar uma equação por uma constante não nula;
c) adicionar um múltiplo de uma equação a uma outra equação;
obtemos um novo sistema 
 e os sistemas Ax = b e 
 são equivalentes.
A eliminação é efetuada por colunas e chamaremos de etapa k do processo a fase em que se elimina a variável xk das equações k+1, k+2, ..., n.
Usaremos a notação 
 para denotar o coeficiente da linha i e da coluna j no final da k–ésima etapa, bem como 
 será o i–ésimo elemento do vetor constante no final da etapa k.
Considerando que det(A) ( 0, é sempre possível reescrever o sistema linear de forma que o elemento da posição a11 seja diferente de zero, usando apenas a operação elementar (a).
Seja 
onde 
, 
 e 
ETAPA 1:
A eliminação da variável x1 das equações i = 2, ..., n é feita da seguinte forma: da equação i subtraímos a 1ª equação multiplicada por mi1. Observamos que para que esta eliminação seja efetuada, a única escolha possível é 
, i = 2, ..., n
Os elementos 
, i = 2, ..., n são os multiplicadores e o elemento 
 é o pivô da 1ª etapa.
Ao final desta etapa teremos a matriz:
onde	
		para j = 1, ..., n
		
e		
	i = 2, ..., n e j = 1, ..., n
		
	i = 2, ..., n
ETAPA 2:
Deve-se ter pelo menos um elemento 
, para i = 2, ..., n. Caso seja necessário, devemos reescrever a matriz A(1), sem alterar a posição da linha 1, de forma que o pivô, 
, seja não nulo.
Os multiplicadores desta etapa serão os elementos 
 para i = 3, ..., n. 
A variável x2 é eliminada das equações i = 3, .., n da seguinte forma: da equação i subtraímos a segunda equação multiplicada por mi2.
Ao final, teremos a matriz 
:
onde	
		para i = 1, 2 e j = i, i+1, ..., n
		
		para i = 1, 2
e		
	para i = 3, ..., n e j = 2, ..., n
		
	para i = 3, ..., n
Seguindo raciocínio análogo, procede-se até a etapa (n – 1) e a matriz, ao final desta etapa, será:
e o sistema linear A(n –1)x = b(n –1) é triangular superior e equivale ao sistema linear original.
EXEMPLO:
Seja o sistema linear:
Etapa 1: Eliminar x1 das equações 2 e 3:
De agora em diante usaremos a notação Li para indicar o vetor linha formado pelos elementos da linha i da matriz 
. Assim, neste etapa, L1 = (  3  2  4  1  )
Pivô:	
		
		
		
		
Etapa 1: Eliminar x2 da equação 3:
Pivô:	
		
		
Assim, resolver Ax = b é equivalente a resolver A(2)x = b(2):
A solução deste sistema é o vetor 
ALGORITMO: Resolução de Ax = b através da Eliminação de Gauss
Seja o sistema linear Ax = b, A: nxn, x: nx1, b: nx1.
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), ...,1
S = 0
Para j = (K + 1), ..., n
S = S + akjxj
xk = (bk – S) / akk
Estratégias de Pivoteamento
Vimos que o algoritmo para o método da Eliminação de Gauss requer o cálculo dos multiplicadores:
 i = k + 1, ..., n
em cada etapa k do processo.
Os casos em que o pivô for nulo ou próximo de zero merecem uma atenção especial, pois é impossível trabalhar com um pivô nulo, e um pivô próximo de zero pode conduzir a resultados totalmente imprecisos.
Para se contornar estes problemas deve-se adotar uma estratégia de pivoteamento, ou seja, adotar um processo de escolha da linha e / ou coluna pivotal.
Estratégia de Pivoteamento Parcial
Esta estratégia consiste em:
a) no início da etapa k da fase de eliminação, escolher para pivô o elemento de maior módulo entre os coeficientes: 
 i = k, k + 1, ..., n;
b) trocar as linhas k e i se for necessário
EXEMPLO: n = 4 e k = 2
Início da etapa 2:
a) escolher pivô
 ( pivô = –3
b) trocar linhas 2 e 3
		Assim, 
e os multiplicadores desta etapa serão: 
 e 
A escolha do maior elemento em módulo entre os candidatos a pivô faz com que os multiplicadores, em módulo, estejam entre zero e um, o que evita a ampliação dos erros de arredondamento.
Estratégia de Pivoteamento Completo
Nesta estratégia, no início da etapa k é escolhido para pivô o elemento de maior módulo, entre todos os elementos que ainda atuam no processo de eliminação:
 ( pivô = 
Se no exemplo anterior fosse adotada esta estratégia, o pivô da etapa 2 seria 
, o que acarretaria a troca das colunas 2 e 4 e, em seguida, das linhas 2 e 3, donde:
Esta estratégia não é muito empregada, pois envolve uma comparação extensa entre os elementos 
, i,j ( k e troca de linhas e colunas, o que acarreta um esforço computacional maior que a estratégia de pivoteamento parcial.
EXERCÍCIOS:
1) 
		Resposta: 
2) 
	Resposta: 
3) 
		Resposta: 
_1136374287.unknown
_1136376684.unknown
_1136634531.unknown
_1136636592.unknown
_1145947112.unknown
_1146481656.unknown
_1146570533.unknown
_1146570784.unknown
_1146571033.unknown
_1146571186.unknown
_1146570973.unknown
_1146570746.unknown
_1146570300.unknown
_1145948215.unknown
_1146481537.unknown
_1145947822.unknown
_1136697681.unknown
_1136698002.unknown
_1136698069.unknown
_1136698150.unknown
_1136697986.unknown
_1136697495.unknown
_1136697643.unknown
_1136636929.unknown
_1136634797.unknown
_1136635894.unknown
_1136636239.unknown
_1136634937.unknown
_1136634581.unknown
_1136634640.unknown
_1136634556.unknown
_1136634150.unknown
_1136634213.unknown
_1136634265.unknown
_1136634188.unknown
_1136377402.unknown
_1136634114.unknown
_1136377124.unknown
_1136375080.unknown
_1136376196.unknown
_1136376288.unknown
_1136376431.unknown
_1136376240.unknown
_1136375830.unknown
_1136376110.unknown
_1136375496.unknown
_1136374605.unknown
_1136374892.unknown
_1136375015.unknown
_1136374767.unknown
_1136374384.unknown
_1136374554.unknown
_1136374313.unknown
_1136354269.unknown
_1136354627.unknown
_1136355233.unknown
_1136374207.unknown
_1136355201.unknown
_1136354446.unknown
_1136354497.unknown
_1136354315.unknown
_1136291091.unknown
_1136292625.unknown
_1136292898.unknown
_1136292328.unknown
_1136290622.unknown
_1136290637.unknown
_1136289401.unknown