Unidade IV

Prévia do material em texto

�PAGE �
�PAGE �52�
 UERJ - CTC - IME - Departamento de Informática e Ciência da Computação 
Cálculo Numérico — Professora Mariluci Ferreira Portes
�
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:
��� EMBED Equation.2 �
�
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
�
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,010,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: 
�
_919683051.unknown
_999934126.unknown
_999935481.unknown
_999936151.unknown
_999938410.unknown
_1271778737.unknown
_1271778841.unknown
_1271778677.unknown
_999938614.unknown
_999936489.unknown
_999938071.unknown
_999936473.unknown
_999935742.unknown
_999936087.unknown
_999935673.unknown
_999934775.unknown
_999935010.unknown
_999935106.unknown
_999934888.unknown
_999934486.unknown
_999934197.unknown
_919683062.unknown
_919683067.unknown
_919683070.unknown
_919683072.unknown
_919683069.unknown
_919683065.unknown
_919683066.unknown
_919683063.unknown
_919683056.unknown
_919683059.unknown
_919683061.unknown
_919683058.unknown
_919683054.unknown
_919683055.unknown
_919683052.unknown
_919683027.unknown
_919683040.unknown
_919683045.unknown
_919683048.unknown
_919683049.unknown
_919683047.unknown
_919683043.unknown
_919683044.unknown
_919683041.unknown
_919683033.unknown
_919683036.unknown
_919683037.unknown
_919683034.unknown
_919683030.unknown
_919683031.unknown
_919683028.unknown
_919683015.unknown
_919683021.unknown
_919683024.unknown
_919683026.unknown
_919683023.unknown
_919683019.unknown
_919683020.unknown
_919683016.unknown
_919682984.unknown
_919682994.unknown
_919683012.unknown
_919683013.unknown
_919683010.unknown
_919682990.unknown
_919682991.unknown
_919682986.unknown
_919682979.unknown
_919682982.unknown
_919682983.unknown
_919682980.unknown
_905156767.unknown
_919682976.unknown
_919682978.unknown
_905156922.unknown
_905156983.unknown
_919682972.unknown
_905156872.unknown
_905156573.unknown
_905156662.unknown
_905156450.unknown