04 - Resolução de Sistemas Lineares

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

�PAGE �
�PAGE �51�
04
RESOLUÇÃO DE SISTEMAS LINEARES - 2
Fatoraçã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.
Por exemplo, se pudermos realizar a fatoração A = CD, o sistema linear Ax = b pode ser escrito:
( CD )x = b
Se y = Dx, então resolver o sistema linear Ax = b é equivalente a resolver o sistema Cy = b e, em seguida, o sistema linear Dx = y.
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.
Cálculo dos Fatores L e U
A obtenção dos fatores L e U pode ser feita através do processo de Gauss.
Usaremos um exemplo teórico de dimensão 3:
Trabalharemos somente com a matriz dos coeficientes. Seja então:
Os multiplicadores da etapa 1 do processo de Gauss são:
 e 
Para eliminar x1 da linha i, i = 2,3, multiplicamos a linha 1 por mi1 e subtraímos o resultado da linha i.
Os coeficientes 
 serão alterados para 
, onde:
		
		para j = 1, 2, 3
		
	para i = 2, 3 e j = 1, 2, 3
Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde
, pois
Portanto, M(0)A(0) = A(1) é a mesma matriz obtida no final da etapa 1 do processo de Gauss.
O multiplicador da etapa 2 será: 
Para eliminar x2 da linha 3, multiplicamos a linha 2 por m32 e subtraímos o resultado da linha 3.
Os coeficientes 
 serão alterados para:
		
		para j = 1, 2, 3
		
		para j = 2, 3
		
	para j = 2, 3
As operações efetuadas em A(1) são equivalentes a pré-multiplicar A(1) por M(1), onde
, pois
Portanto, M(1)A(1) = A(2), onde A(2) é a mesma matriz obtida no final da etapa 2 do método da Eliminação de Gauss.
Temos então que:
A = A(0)
A(1) = M(0)A(0) = M(0)A
A(2) = M(1)A(1) = M(1)M(0)A(0) = M(1)M(0)A
onde A(2) é triangular superior.
Então, 
--------------------------------------------------------------------------------------------------------
DEMONSTRAÇÃO:
Propriedades de Matrizes:
			a) 
			b) 
			c) 
Quero demonstrar que: se 
, então 
Multiplicando ambos os lados por 
 temos:
Propriedade b:	
Propriedade a:	
Propriedade c:	
 cqd
--------------------------------------------------------------------------------------------------------
É fácil verificar que:
 e 
Assim, 
Portanto,
Ou seja: 
 e 
Isto é, fatoramos a matriz A em duas matrizes triangulares L e U, sendo que o fator L é triangular inferior com diagonal unitária e seus elementos lij para i > j são os multiplicadores mij obtidos no processo da Eliminação de Gauss; o fator U é triangular superior e é a matriz triangular superior obtida no final da fase da triangulação do método da Eliminação de Gauss.
Resolução do Sistema Linear Ax = b usando a fatoração LU de A
Dado o sistema linear Ax = b e a fatoração LU da matriz A, temos:
Ax = b ( (LU)x = b
Seja y = Ux. A solução do sistema linear pode ser obtida da resolução dos sistemas lineares triangulares:
i) Ly = b
ii) Ux = y
EXEMPLO: Resolver o sistema linear a seguir usando a fatoração LU:
Usando o processo de Gauss, sem estratégia de pivoteamento parcial, para triangulizar A, temos:
Etapa 1: 
Pivô:	
	Multiplicadores:	
							
Então,
	
 e 
Uma vez que os elementos 
 e 
 são nulos, podemos guardar os multiplicadores nestas posições, então:
Etapa 2: 
Pivô:	
	Multiplicadores:	
							
Teremos,
	
 e 
Os fatores L e U são:
 e 
Resolvendo L(Ux) = b:
i) Ly = b 
 ( 
ii) Ux = y 
Fatoração LU com Estratégia de Pivoteamento Parcial
Uma matriz quadrada de ordem n é uma matriz de permutação se pode ser obtida da matriz identidade de ordem n permutando-se suas linhas (ou colunas).
Pré multiplicando-se uma matriz A por uma matriz de permutação P obtém-se a matriz PA com as linhas permutadas, e esta permutação de linhas é a mesma efetuada na matriz identidade para se obter P.
EXEMPLO:
Sejam 
 e 
Seja o sistema linear Ax = b e sejam os fatores L e U obtidos pelo processo de Eliminação de Gauss com estratégia de pivoteamento parcial.
L e U são fatores da matriz A´, onde A´ é a matriz com as linhas permutadas, isto é, A´ = PA.
As mesmas permutações efetuadas nas linhas de A devem ser efetuadas sobre o vetor b, uma vez que permutar as linhas de A implica permutar as equações de Ax = b.
Seja então b´ = Pb.
O sistema linear A´x = b´ é equivalente ao original e, se A´ = LU, teremos A´x = b´ ( LUx = Pb.
Resolvemos então os sistemas triangulares:
i) Ly = Pb
ii) Ux = y
e obtemos a solução do sistema linear original.
EXEMPLO: Seja o sistema linear:
Etapa 1: 
Pivô:	
, então devemos permutar as linhas 1 e 3:
, 
 e 
Efetuando a eliminação em A´(0):
Etapa 2: 
Pivô:	
, então devemos permutar as linhas 2 e 3:
, 
 e 
Efetuando a eliminação temos:
Os fatores L e U são:
 e 
A matriz P é dada por P = P(1)P(0) 
Resolução dos sistemas lineares triangulares:
i) Ly = Pb onde 
 ( 
ii) Ux = y 
 ( 
A matriz P pode ser determinada por P = P(n – 1) P(n – 2) ... P(0) , onde P(K) representa a troca de linhas efetuada na etapa K.
As permutações de linhas podem ser representadas através de um vetor nx1, que denotaremos por p.
No exemplo anterior, teríamos inicialmente: p = ( 1  2  3 ). No início da etapa 1, a linha 3 é a pivotal, então p = ( 3  2  1 ). No início da etapa 2, a linha 3 da matriz A(1) é a linha pivotal, então p = ( 3  1  2 ).
ALGORITMO: Resolução de Ax = b através da fatoração LU com pivoteamento parcial
Considere o sistema linear Ax = b, A: nxn, o vetor p representará as permutações realizadas durante a fatoração.
( Cálculo dos fatores:
Para i = 1, ..., n
p(i) = i
Para k = 1, ..., (n – 1)
pv = |a(k, k)|
r = k
Para i = (k + 1), ..., n
	Se ( |a(i, k)| > pv ), faça:
		pv = |a(i, k)| 
		r = i
Se pv = 0, parar; não tem solução
	Se r ( k, faça:
		aux = p(k)
		p(k) = p(r)
		p(r) = aux
		Para j = 1, ..., n
			aux = a(k, j)
			a(k, j) = a(r, j)
			a(r, j) = aux
	Para i = (k + 1), ..., n
		m = a(i, k) / a(k, k)
		a(i, k) = 0
		Para j = (k + 1), ..., n
		a(i, j) = a(i, j) – ma(k, j)
( Resolução dos sistemas triangulares:
Para i = 1, ..., n
C = Pb		r = p(i)
		C(i) = b(r)
Para i = 1, ..., n
		soma = 0
Ly = C 	Para j = 1, ..., (i – 1)
soma = soma + a(i, j) y(j)
		y(i) = C(i) – soma
Para i = n, (n – 1), ..., 1
		soma = 0
Ux = y 	Para j = (i + 1), ..., n
soma = soma + a(i, j) x(j)
		x(i) = (y(i) – soma) / a(i, i)
EXERCÍCIOS:
1) 
		Resposta: 
2) 
	Resposta: 
3) 
		Resposta: 
_1136703168.unknown
_1136705126.unknown
_1136707903.unknown
_1136716595.unknown
_1136717171.unknown
_1146570784.unknown
_1149055782.unknown
_1149321634.unknown
_1146571033.unknown
_1146571186.unknown
_1146570973.unknown
_1146570533.unknown
_1146570746.unknown
_1136717236.unknown
_1136716919.unknown
_1136716935.unknown
_1136716743.unknown
_1136715930.unknown
_1136716292.unknown
_1136716335.unknown
_1136716266.unknown
_1136708218.unknown
_1136715882.unknown
_1136708090.unknown
_1136706322.unknown
_1136707509.unknown
_1136707673.unknown
_1136707794.unknown
_1136707619.unknown
_1136707351.unknown
_1136707414.unknown
_1136707303.unknown
_1136705778.unknown
_1136706237.unknown
_1136706315.unknown
_1136705841.unknown
_1136705505.unknown
_1136705697.unknown
_1136705263.unknown
_1136704561.unknown
_1136704858.unknown
_1136705024.unknown
_1136705084.unknown
_1136704978.unknown
_1136704786.unknown
_1136704814.unknown
_1136704705.unknown
_1136704154.unknown
_1136704420.unknown
_1136704490.unknown
_1136704242.unknown
_1136703392.unknown
_1136703409.unknown
_1136703252.unknown
_1136701578.unknown
_1136702652.unknown
_1136702917.unknown
_1136703047.unknown
_1136703163.unknown
_1136702940.unknown
_1136702757.unknown
_1136702840.unknown
_1136702711.unknown
_1136702329.unknown
_1136702491.unknown
_1136702577.unknown
_1136702363.unknown
_1136702143.unknown
_1136702304.unknown
_1136701729.unknown
_1136700720.unknown
_1136701306.unknown
_1136701347.unknown
_1136701572.unknown
_1136701321.unknown
_1136701110.unknown
_1136701272.unknown
_1136700939.unknown
_1136700067.unknown
_1136700307.unknown
_1136700378.unknown
_1136700707.unknown
_1136700265.unknown
_1136699902.unknown
_1136700032.unknown
_1136699585.unknown
_1136634114.unknown