Sistemas de Equações Lineares

Prévia do material em texto

15/05/20
1
Sistemas de Equações Lineares - Aulas remotas
15.05.2020
Prof. João Paulo
ATENÇÃO
O CONTEÚDO AUDIOVISUAL A SEGUIR É PARA USO 
EXCLUSIVAMENTE ACADÊMICO E ESTÁ PROTEGIDO PELAS 
LEIS DE PROPRIEDADE INTELECTUAL, SENDO VEDADA SUA 
CESSÃO OU OUTRA FORMA DE UTILIZAÇÃO NÃO 
AUTORIZADA, DO TODO OU DE QUALQUER PARTE
1
2
15/05/20
2
AGENDA
Sistemas de Equações Lineares
• Métodos Diretos:
i. Fatoração LU pelo Método de Crout
ii. Fatoração LU por Eliminação de Gauss
• Métodos Iterativos:
i. Método de Jacobi
ii. Método de Gauss-Seidel
iii. Critérios de Convergência
AGENDA
Sistemas de Equações Lineares
• Métodos Diretos:
i. Fatoração LU pelo Método de Crout
ii. Fatoração LU por Eliminação de Gauss
• Métodos Iterativos:
i. Método de Jacobi
ii. Método de Gauss-Seidel
iii. Critérios de Convergência
3
4
15/05/20
3
Introdução
• Métodos diretos:
– “São métodos que ao cabo de um número finito de 
operações apresentam, teoricamente, a solução exata do 
sistema em estudo.”
• Métodos Iterativos:
– “Os métodos iterativos conduzem a uma solução 
aproximada, mas com erro controlado, têm vantagens 
computacionais e implicam menos recursos de memória 
do que os métodos diretos”
Desvantagens dos Métodos Diretos
– “Os métodos diretos não são recomendados 
quando o sistema de equações lineares a ser 
resolvido é muito grande ou se a matriz 
correspondente a ele tem a grande maioria de 
seus elementos nulos (matriz esparsa)”
5
6
15/05/20
4
Métodos iterativos
• Nos casos em que as matrizes são grandes 
e/ou esparsas os métodos iterativos são mais 
indicados.
• Partem de uma aproximação inicial ���� da 
solução do sistema �� � � e geram uma 
sequência ���	�
 de soluções aproximadas de 
�.
Método de Jacobi
– Método do final do século XVIII
• Jacobi
– Matemático Alemão
– 1804-1851
– Esse método pode também ser conhecido 
como Método de Gauss-Jacobi.
Carl Gustav Jakob Jacobi
7
8
15/05/20
5
Método de Gauss-Seidel
• Carl Friedrich Gauss
– Matemático Alemão
– 1777-1855
• Philipp Ludwig Ritter von Seidel
– Matemático Alemão
– 1821-1896
• O método é de Gauss (1823), mas só foi publicado em 
1874 por Seidel.
MÉTODO DE JACOBI
9
10
15/05/20
6
Introdução
• �� � 
:
• Esta equação é utilizada para obter soluções 
���� a partir de ��
– É um processo iterativo em que definimos 
���� a partir de ��. 
– Naturalmente, precisamos de um ��.
Processo iterativo - Jacobi
Ou de forma simples, 
basta isolar cada variável 
do sistema (xi
(k+1)) em sua
linha correspondente em
função das demais
variáveis em (xj
(k)).
11
12
15/05/20
7
Jacobi – Critérios de parada
• Podemos ter vários critérios de parada:
– Ex1: max
����� 
|��
���
��
�
���
|
|�
�
���
|
 !
– Ex2: "#$
%�&�' 
|�&
	�%
( �&
�	�
| )
• ! é a precisão desejada
• Pode-se também estabelecer um número máximo 
de iterações.
Usaremos este
critério!
Método de Jacobi
• Exemplo 1: Resolva o Sistema de Equações Lineares abaixo pelo
Método Iterativo de Jacobi para uma precisão de 0,05 e
x(0)=(0;0;0)t. Utilize um FIX de 4.
13
14
15/05/20
8
Exemplo 1
• Roteiro:
1. Isolar cada equação de acordo com sua linha em xi
(k+1);
2. Montar a Tabela com as colunas das variáveis em xi
(k+1) ; e suas
respectivas precisões em módulo |Exi
(k+1)|;
3. Ir preenchendo cada linha da tabela, calculando cada xi
(k+1) a partir
do valor xi
(k) . A 1a linha é calculada usando a condição inicial x(0) .
4. Continuar com as iterações até que todas as varíaveis atendam o 
critério xi
(k+1) - xi
(k) < precisão.
Exemplo 1
• Roteiro:
1. Isolar cada equação de acordo com sua linha em xi
(k+1);
x1
(k+1) = [8 - 2x2
(k) – x3
(k)]/5
x2
(k+1) = [7 - 3x1
(k) + 2x3
(k)]/6
x3
(k+1) = [8 - 2x1
(k) + 4x2
(k)]/10
15
16
15/05/20
9
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
17
18
15/05/20
10
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
1 0,9733 0,6267 0,6333 0,5334 0,9467 0,1467
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
1 0,9733 0,6267 0,6333 0,5334 0,9467 0,1467
2 1,1573 0,1840 0,9956 0,3623 0,8587 0,0880
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
19
20
15/05/20
11
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
1 0,9733 0,6267 0,6333 0,5334 0,9467 0,1467
2 1,1573 0,1840 0,9956 0,3623 0,8587 0,0880
3 1,0300 0,1273 0,8743 0,1213 0,9668 0,1081
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
1 0,9733 0,6267 0,6333 0,5334 0,9467 0,1467
2 1,1573 0,1840 0,9956 0,3623 0,8587 0,0880
3 1,0300 0,1273 0,8743 0,1213 0,9668 0,1081
4 1,0569 0,0269 0,9740 0,0997 0,9437 0,0231
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
21
22
15/05/20
12
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
1 0,9733 0,6267 0,6333 0,5334 0,9467 0,1467
2 1,1573 0,1840 0,9956 0,3623 0,8587 0,0880
3 1,03000,1273 0,8743 0,1213 0,9668 0,1081
4 1,0569 0,0269 0,9740 0,0997 0,9437 0,0231
5 1,0217 0,0352 0,9528 0,0212 0,9782 0,0345
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 1,1667 1,1667 0,8000 0,8000
1 0,9733 0,6267 0,6333 0,5334 0,9467 0,1467
2 1,1573 0,1840 0,9956 0,3623 0,8587 0,0880
3 1,0300 0,1273 0,8743 0,1213 0,9668 0,1081
4 1,0569 0,0269 0,9740 0,0997 0,9437 0,0231
5 1,0217 0,0352 0,9528 0,0212 0,9782 0,0345
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
X = ±
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
23
24
15/05/20
13
MÉTODO DE GAUSS-SEIDEL
Introdução
• Jacobi usa a equação para obter soluções ���� a 
partir de ��
– É um processo iterativo em que definimos 
���� a partir de ��. 
– Seidel percebeu que quando calculamos por 
exemplo os valores de x2 e x3, já poderíamos 
utilizar os valores já atualizados na mesma 
iteração pelas demais variáveis.
25
26
15/05/20
14
Método de Gauss-Seidel
• Logo, temos a sequência
Ou de forma simples, basta isolar cada variável 
do sistema (xi
(k+1)) em sua linha correspondente
em função das demais novas variáveis em (xj
(k)) e 
as já conhecidas em (xi
(k+1)).
Gauss-Seidel – Critérios de parada
• Podemos ter vários critérios de parada:
– Ex1: max
����� 
|��
���
��
�
���
|
|�
�
���
|
 !
– Ex2: "#$
%�&�' 
|�&
	�%
( �&
�	�
| )
• ! é a precisão desejada
• Pode-se também estabelecer um número máximo 
de iterações.
Usaremos este
critério!
27
28
15/05/20
15
Método de Gauss-Seidel
• Exemplo 1: Resolva o Sistema de Equações Lineares abaixo pelo
Método Iterativo de Gauss-Seidel para uma precisão de 0,05 e
x(0)=(0;0;0)t. Utilize um FIX de 4.
Exemplo 1
• Roteiro:
1. Isolar cada equação de acordo com sua linha em xi
(k+1) (Lembrar de 
usar as variáveis já calculadas como xi
(k+1) ;
2. Montar a Tabela com as colunas das variáveis em xi
(k+1) ; e suas
respectivas precisões em módulo |Exi
(k+1)|;
3. Ir preenchendo cada linha da tabela, calculando cada xi
(k+1) a partir
do valor xi
(k) . A 1a linha é calculada usando a condição inicial x(0) .
4. Continuar com as iterações até que todas as varíaveis atendam o 
critério xi
(k+1) - xi
(k) < precisão.
29
30
15/05/20
16
Exemplo 1
• Roteiro:
1. Isolar cada equação de acordo com sua linha em xi
(k+1);
x1
(k+1) = [8 - 2x2
(k) – x3
(k)]/5
x2
(k+1) = [7 - 3x1
(k+1) + 2x3
(k)]/6
x3
(k+1) = [8 - 2x1
(k+1) + 4x2
(k+1)]/10
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
31
32
15/05/20
17
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 0,3667 0,3667 0,6267 0,6267
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 0,3667 0,3667 0,6267 0,6267
1 1,3280 0,2720 0,7116 0,3449 0,8190 0,1923x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
33
34
15/05/20
18
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 0,3667 0,3667 0,6267 0,6267
1 1,3280 0,2720 0,7116 0,3449 0,8190 0,1923
2 1,1516 0,1764 0,8639 0,1523 0,9152 0,0962
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 0,3667 0,3667 0,6267 0,6267
1 1,3280 0,2720 0,7116 0,3449 0,8190 0,1923
2 1,1516 0,1764 0,8639 0,1523 0,9152 0,0962
3 1,0714 0,0802 0,9360 0,0722 0,9601 0,0449
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
35
36
15/05/20
19
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 0,3667 0,3667 0,6267 0,6267
1 1,3280 0,2720 0,7116 0,3449 0,8190 0,1923
2 1,1516 0,1764 0,8639 0,1523 0,9152 0,0962
3 1,0714 0,0802 0,9360 0,0722 0,9601 0,0449
4 1,0336 0,0379 0,9699 0,0339 0,9813 0,0211
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E)C (C-F)
Exemplo 1
• Exemplo 1: Solução:
*+,-.çã1 x1
(k+1) |Ex1
(k+1)| x2
(k+1) |Ex2
(k+1)| x3
(k+1) |Ex3
(k+1)|
0 1,6000 1,6000 0,3667 0,3667 0,6267 0,6267
1 1,3280 0,2720 0,7116 0,3449 0,8190 0,1923
2 1,1516 0,1764 0,8639 0,1523 0,9152 0,0962
3 1,0714 0,0802 0,9360 0,0722 0,9601 0,0449
4 1,0336 0,0379 0,9699 0,0339 0,9813 0,0211
x(0)=(0;0;0)t
Precisão 
=0,05
FIX=4
A (A-0) B (B-0) C (C-0)
D (D-A) E (E-B) F (F-C)
X = ±
A (A-D) B (B-E) C (C-F)
D (D-A) E (E-B) F (F-C)
A (A-D) B (B-E) C (C-F)
Deu uma iteração a menos que o método de Jacobi!
37
38
15/05/20
20
Observações
• O número de operações nos métodos de Jacobi 
e de Gauss-Seidel depende da quantidade de 
coeficientes não nulos em cada equação.
• Se a i-ésima equação possui 2� coeficientes não-
nulos, os métodos de Jacobi e Gauss-Seidel
necessitam de +&� 3 +&4 3 5 operações em 
cada iteração.
– A: # adições/subtrações
– M: # multiplicações
– D: # divisões
Observações
• Logo, o número total de operações de 
ponto flutuante em cada iteração para um 
sistema de 6 equações é dado por:
39
40
15/05/20
21
Usando o Exemplo 1
• Para cada equação A=2, M=2 e D=1.
• Logo, temos que (3+3+3).2 + 
(3+3+3).2+3.1=39
CRITÉRIOS DE CONVERGÊNCIA
41
42
15/05/20
22
Critério das Linhas
– Seja o sistema linear Ax=b e seja:
– Se ,então os métodos de Jacobi 
e Gauss-Seidel geram uma sequência {x(k)} 
convergente para a solução do sistema, 
independente da escolha de x(0). 
Critério de Sassenfeld
– Seja o sistema linear Ax=b e seja:
, e 
– Se β < 1, então o método de Gauss-Seidel gera uma 
sequência {x(k)} convergente para a solução do sistema, 
independente da escolha de x(0). 
– Quanto menor β, mais rápida a convergência.
β1 é igual ao α1!
43
44
15/05/20
23
Artifícios para garantir Convergência
– Para o Método de Jacobi, sempre que o critério das linhas 
não for satisfeito, devemos tentar uma permutação de 
linhas e/ou colunas de forma a obtermos uma disposição 
para a qual a matriz dos coeficientes satisfaça o critério das 
linhas.
– Em relação ao Método de Gauss-Seidel, podemos fazer 
permutações nas linhas e colunas para encontrar uma 
disposição que satisfaça o critério das linhas ou o critério de 
Sassenfeld.
– No entanto, nem sempre é possível obter tal disposição.
Critérios de Convergência
• Exemplo 1: Verifique se o Sistema de Equações Lineares abaixo 
tem convergência pelos Critérios das Linhas e o de Sassenfeld.
45
46
15/05/20
24
Exemplo 1
• Critério das Linhas:
1. Calcular os αk de cada linha:
α1= [|a12|+ |a13|]/|a11|= (2+1)/5 = 3/5 = 0,60 < 1
α2= [|a21|+ |a23|]/|a22|= (3+2)/6 = 5/6 = 0,83 < 1
α3= [|a31|+ |a32|]/|a33|= (2+4)/10 = 6/10 = 0,60 < 1
*Logo há convergência para os Métodos de Jacobi e Gauss-Seidel pelo 
critério das linhas.
Exemplo 1
• Critério de Sassenfeld:
1. Calcular os βk de cada linha:
β1= α1= [|a12|+ |a13|]/|a11|= (2+1)/5 = 3/5 = 0,60 < 1
β2= [|a21|. β1 + |a23|]/|a22|= [3.0,6+2]/6 = (3,8)/6 = 0,63 < 1
β3= [|a31|. β1 + |a32|. β2 ]/|a33|= [2.0,6+4.0,63]/10 = (3,72)/10 = 0,37 < 1
*Logo há convergência para o Método de Gauss-Seidel pelo critério de 
Sassenfeld.
47
48
15/05/20
25
Exercícios
• Resolva os seguintes Sistemas de Equações Lineares pelos métodos
iterativos de Jacobi e Gauss-Seidel. Antes, verifique o critério de 
convergência e caso necessário faça permutações para garantir a 
convergência:
A)
B) 
Com x(0)=[0,7;-1,6;0,6]t
FIX = 4 e precisão de 0,05
Com x(0)=[0;0;0]t
FIX = 4 e precisão de 0,05
Dúvidas e Sugestões 
?
49
50
15/05/20
26
Referências
51
52