Analise Numérica em Sistemas Lineares

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

Unidade IV - Sistemas Lineares
IV.1 - Introdução
O Problema que aparece no cálculo de estruturas, em redes elétricas, e em solução de equações diferenciais é o da resolução de um sistema linear de “ n ” equações a “ n ” incógnitas. Sn é um sistema tal que:
 
Sob a forma matricial Sn pode ser escrito como A x = b, onde A é uma matriz de ordem “ n ” , b e x são matrizes n 1.
A matriz B = é chamada de matriz estendida do sistema Sn .
Definição: 
O vetor = ( 1 , 2 , ... , n ) t constitui uma solução para Sn se para xi = i (1 i n) as equações de Sn forem satisfeitas.
Um sistema linear pode ser classificado do seguinte modo:
1. Compatível (quando possuí solução):
a. Determinado (única solução)
b. Indeterminado (infinitas soluções)
2. Incompatível (quando NÃO possuí solução)
Exemplos: 
1) O sistema Ax = 0 é homogêneo e todo sistema homogêneo é compatível, pois admite pelo a solução trivial.
2) O sistema S2 = é incompatível. Geometricamente temos:
				 x 2
x1 + x2 = 0
							 x 1
							 x1 + x2 = 1
As retas são paralelas
3) O sistema S2 = 
O sistema é incompatível e determinado. Geometricamente temos:
			 x 2
				 x1 - x2 = 0
 
	
							 x 1
						 x1 + x2 = 0
													
4) O sistema S2 = é incompatível indeterminado. Geometricamente temos:
					 x 2 
										x 1 
Retas Coincidentes
								 x1 + x2 = 0
								2x1 + 2x2 = 0
IV.1.1 - Sistemas triangulares
 
Seja Sn um sistema da forma Ax = b, onde A = ai j tal que:
 Um sistema deste tipo é dito triangular superior.
Observe que os sistemas triangulares superiores determinados, isto é, quando ai j 0 (i, j = 1,n) são facilmente resolvidos pelo processo retroativo, que consiste em:
a) Obter o valor de xn da n-ésima equação por meio da relação:
xn = 
b) Substituir o valor de xn na equação de ordem (n-1) para obter xn - 1 . E assim sucessivamente, até calcular x1 .
Se algum elemento da diagonal principal for zero, teremos a situação:
 sistema indeterminado
 sistema incompatível
Exemplo: 
Resolver o S4 pelo processo retroativo: 
Solução:
Da 4a. equação vem: 
Da 3a. equação vem: 
Da 2a. equação vem: 
Da 1a. equação vem: Resposta : = (1 -1 2 1)
IV.1.2 - Norma de um vetor
Norma de um vetor x = (x1 , x2 , x3 ,..., xn) é todo número real denotado por || ||, associado a x, que satisfaz a:
 || x || > 0 e || x || = 0 x = 
 || x + y || || x || + || y || onde x, y n
 || c · x || = | c | · || x || onde c 
Definição 1: A maior componente em módulo do vetor x é uma norma para x.
|| x || = máx | xi | onde 1 i n
x = (3 – 50) x + y = (5 – 4 3 ) x = 5 x + y = 5 ... x + y = 8
y = (2 1 3) y = 3 
Seja c = -2
c · x = (-6 10 0) || c x || = 10 = | c | · || x ||
Definição 2: O também é uma norma para o vetor x. É conhecida como norma c.
IV.1.3 - Transformações elementares
São operações sobre as equações dos sistemas lineares, tais como:
a) Trocar a ordem de duas equações do sistema;
b) Multiplicar uma equação do sistema por uma constante não nula;
c) Adicionar duas equações do sistema.
Definição : Dois sistemas lineares Sn e Sn’ são equivalentes quando Sn’ é obtido de Sn por meio de transformações elementares. Nesse caso, Sn tendo solução, Sn’ também terá.
Os métodos para resolução de sistemas lineares são: 
I - Métodos de eliminação.
II - Métodos iterativos.
IV.2 - Método de eliminação de Gauss
Dado o sistema Sn , a matriz estendida é: 
O método de Gauss consiste em transformar a matriz B em uma matriz triangular superior, da seguinte forma: , onde os índices superiores indicam o número de modificações realizadas em cada linha.
Aplica-se o processo retroativo para se obter a solução desejada.
Algoritmo do método: 
Eliminação de ordem k:
 Supondo akk( k - 1) 0, dividir a linha lk( k -1) por akk( k - 1) (“pivô”), obtendo-se assim uma nova linha lk( k ) .
 “Zerar” os elementos aik (i = i +1, n) usando-se a transformação: 
li (k) = li (k - 1) - ai k · lk (k) , com (k = i +1, n) e (i = 2, n) .
IV.2.1 - Condensação pivotal parcial
Os métodos de eliminação são exatos, mas podem conduzir a soluções errôneas devido ao erro de arredondamento.
Para evitar isto, usaremos a condensação pivotal parcial, cujo procedimento é redispor as linhas de tal forma que a linha do elemento pivô permaneça fixa e que o elemento pivô seja escolhido dentre os elementos da coluna que tem o maior valor absoluto.
A finalidade da condensação pivotal parcial é:
 Minimizar o erro de arredondamento.
 Evitar a divisão por zero.
 Testar a singularidade do sistema.
Exemplo: Resolver o sistema pelo método de eliminação de Gauss com condensação pivotal parcial.
Solução:
Pelo Processo Retroativo:
x3 = 1
x2 = - 1,106 + 0,106 = -1
x1 = -1,75 - 0,19 + 2,94 = 1 Resp.: = (1 -1 1)t
IV.3 - Métodos Iterativos
A solução de um sistema linear AX = B pode ser obtida utilizando-se um método iterativo, que consiste em gerar uma seqüência de soluções x(1), x(2), x(3), ..., x(k), aproximações de , sendo dada uma aproximação inicial x(0).
Para se aplicar o método é necessário transformar o sistema dado em: x = F (x) + d , onde:
	F é uma matriz de ordem n, chamada de matriz iteração;
	x, d são matrizes n 1
Sendo x(0) = (x1(0), x2(0), ..., xn(0)) a aproximação inicial, determinamos:
O critério de parada é dado por . Neste caso, temos x(k) como solução aproximada. 
Obs.: 
IV.3.1 - Método de Jacobi
Considere o sistema: 
Explicitemos x1 na 1ª equação 
 x2 na 2ª equação
 
 x n na n-ésima equação
Daí resulta: 
x = 1 (b1 – a12 x2 – a13 x - ... – a1n x 
 a11
 
x = 1 (b2 – a21 x – a23 x - ... – a2n x É necessário que aii 0 (i = 1,n).
 a22
 .
 .
 .
xn(k) = 1 (bn– an1 x – an2 x2(k-1) - ... – an n-1 x
 ann
Desse modo, podemos escrever o sistema da forma x = F x + d.
x = (x1 , x2, ..., xn )t 
O método de Jacobi consiste em:
	partindo-se da aproximação inicial x(0) 
	gera-se a seqüência de aproximações x(1), x(2), ..., x(k)
	como critério de parada, utilizamos , onde = precisão desejada para raiz.
Exemplo: Resolver o sistema: pelo método de Jacobi, com 2 casas decimais exatas.
Solução: Equações de iteração:
1ª. Iteração
x= ½ (1+0,9) = 0,95
x= ½ (3- 0,9) = 1,05
x(1) – x(0) = 0,95 – 0,9) (1,05 – 0,9) = (0,5) (0,15) = 0,15 > 10-3
52
 UERJ - CTC - IME - Departamento de Informática e Ciência da Computação 
Cálculo Numérico — Professora Mariluci Ferreira Portes
2ª. Iteração
 x = ½ (1+1,05) = 1,025
 x = ½ (3 – 0,95) = 1,025
 x(2) – x(1) = 0,075 > 10-3
3ª.Iteração
 x = ½ (1+ 1,025) = 1,0125
 x = ½ (3 – 1,025) = 0,9875
x3 – x2 = 0,0375 > 10-3
4ª. Iteração
 x1(4) = ½ (1+ 0,9875) = 0,99375
 x2(4) = ½ (3 – 0,9875) = 0,99375
 x4 – x3 = 0,01875 > 10-3
5ª. Iteração
 x1(5) = ½ (1+ 0,99375) = 0,996875
 x2(5) = ½ (3 – 0,99375) = 1,003125
 x(5) – x(4) = 0,009375 > 10-3
6ª. Iteração
 x1(6) = ½ (1+ 1,003125) = 1,0015625
 x2(6) = ½ ( 3 – 0,996875) = 1,0015625
 x(6) – x(5) = 0,0046875 > 10-3
 
7ª. Iteração
 x1(7) = ½ (1 + 1, 003125) = 1,00078125
 x2(7) = ½ (3 – 0.996875) = 0,99921875
x(7) – x(6) = 0,00234375 > 10-3
8ª. Iteração
x1(8) = ½ (1 + 0,99921875) = 0,99960938
x2(8) = ½ (3 – 1,00078125) = 0,99960938
x(8) – x(7) = 0,00117187 > 10-3
9ª. Iteração
x1(9) = ½ (1 + 0,99960938) = 0,99980469
x2(9)= ½ (3 – 0,99960938) = 1,00019531
x(9) – x(8) = 0,00058593 < 10-3
 
Resp:
x = ( 0,99 1,00)t (0,01 0,01)t
 
IV.3.2 - Método de Gauss-Seidel
Seja o sistema AX = b, na forma X = F X + b.
O método iterativo de Gauss-Seidel consiste em:
	partindo-se da solução inicial x(0) = ( x1(0) x2(0) x3(0) ... xn(0) ) 
	gerar a seqüência de aproximações x(1), x(2), ..., x(k) através das equações de iteração: 
	Como critério de parada utilizamos || x(k) - x(k - 1) || < a precisão desejada.
 Obs.: Este método converge mais rápido que o de Jacobi.
Exemplo: Resolver o sistema: pelo método de Gauss-Seidel com 2 casas decimais.
1ª. Iteração
x(0) = (0,9 0,9) = 0,001
 
	2ª. Iteração
	3ª. Iteração
	4ª. Iteração
	5ª. Iteração
Resp: = (0,99 1,00)t (0,01 0,01)t
IV.3.3 - Convergência dos métodos iterativos
Seja o sistema AX = b, na forma:
(1) x = F x + d , e a iteração definida por:
(2) x (k + 1) = F x (k) + d
Subtraindo (1) de (2) x (k + 1) - x = F (x (k) - x)
Fazendo e(k + 1) = x (k + 1) - x e(k + 1) = F e(k) 
Teorema : A condição suficiente para que a iteração dada em (2) convirja é que os elementos f i j da matriz F satisfaçam a desigualdade: 
Corolário 1: (Critério das linhas)
A condição suficiente para que a iteração dada em (2) convirja é que:
Corolário 2: (Critério das colunas)
A condição suficiente para que a iteração dada em (2) convirja é que:
Observações: 
 A matriz que satisfaz a hipótese dos corolários 1 ou 2 é chamada de matriz diagonal dominante estrita.
 Na prática são usados os critérios de suficiência expressos nos corolários 1 ou 2, tanto para o método de Jacobi quanto para o método de Gauss-Seidel. Basta que o sistema satisfaça apenas a um desses critérios para se ter a convergência garantida, independente da escolha do vetor inicial.
IV.3.4 - Qual o método melhor ?
Não se pode garantir de início que método será mais eficiente.
Os métodos de eliminação se prestam a sistemas de pequeno porte com matrizes de coeficientes densos; também resolvem satisfatoriamente vários sistemas lineares com a mesma matriz de coeficientes.
Os métodos iterativos, quando a convergência é garantida, são bastante vantajosos na resolução de sistemas de grande porte com matrizes de coeficientes esparsos ( grande quantidade de zeros entre seus elementos ).
Os sistemas oriundos da discretização de equações diferenciais parciais são exemplos típicos.
IV.3.5 - Noções de matrizes mal condicionadas
Considere o sistema .
Uma das soluções é = (1 1)t .
Se utilizarmos o método de Jacobi, na 5ª. Iteração encontraríamos como solução aproximada 1 = (2,000 0,001)t , que diverge da solução.
Isto aconteceu porque os coeficientes da matriz associada estão mal condicionados.
Uma forma de se detectar o mal condicionamento é através do determinante normalizado de uma matriz. Se esse determinante for, sensivelmente, menor que 1 dizemos que a matriz está mal condicionada.
Definição: Para a matriz A, associada ao sistema Sn , definimos determinante normalizado de A, e denotamos por det (norm A) a: 
, onde: 
Obs.: No sistema S2 dado:
Lista de exercícios sobre a Unidade IV
1) Resolva pelo processo retroativo os seguintes sistemas : 
a) b)
2) Resolva pelo método de Gauss, com condensação pivotal parcial.
a)
b)
c)
3) Resolva os sistemas abaixo usando o método de Gauss-Seidel.
a) b) 
Trabalho Computacional: Programar o método de Gauss com condensação pivotal parcial para resolver o sistema: