CCI-22 Matemática Computacional CCI

CCI-22
Matemática Computacional
CCI-22
3) Raízes de Sistemas Lineares
Carlos Alberto Alonso Sanches
Eliminação de Gauss, Gauss-Jordan,
Decomposição LU, Gauss-Jacobi, Gauss-Seidel
CCICCI-22
CCICCI-22
Introdução
Introdução
Métodos diretos
Métodos diretos
Regra de Cramer
Regra de Cramer
Eliminação de Gauss
Eliminação de Gauss
Gauss-Jordan
Gauss-Jordan
Decomposição LU
Decomposição LU
Métodos iterativos
Métodos iterativos
Gauss-Jacobi
Gauss-Jacobi
Gauss-Seidel
Gauss-Seidel
Considerações finais
Considerações finais
Métodos de resoluç
resolução
Para a resolução de um sistema linear de
equações, há dois grupos de métodos:
Métodos diretos: a solução é obtida através da
aplicação de um número finito de operações
aritméticas
Regra de Cramer
Eliminação de Gauss e de Gauss-Jordan
Decomposição LU
Métodos iterativos: a solução é obtida através de
uma sequência de aproximações sucessivas, até se
alcançar uma resposta que satisfaça a precisão
exigida
Gauss-Jacobi
Gauss-Seidel
Exemplo
Sistemas de Equaç
Equações Lineares
Forma geral:
onde:
a11x1 + a12 x2 + ... + a1n xn = b1
aij são os coeficientes
xi são as incógnitas
bi são os termos independentes
n é a ordem do sistema
a 21x1 + a 22 x2 + ... + a 2 n xn = b2
M
an 1x1 + an 2 x2 + ... + ann xn = bn
Forma matricial:
Ax = b
 a11 a12
a
a
A =  21 22
 M
M

 an1 an 2
onde:
L a1n 
L a2n 
O M 

L ann 
 x1 
x 
x =  2
M
 
xn 
b1 
b 
b =  2
M
 
bn 
Cálculo das forç
forças em uma treliç
treliça
Forma geral:
1
Fh
3
2
4
4
5
1
2x1 + 4x2 − 5x3 = 5
4x1 + 1x2 − 5x3 = 2
2x1 + 4x2 + 5x3 = −1
2
Um exemplo:
7
6
3
F1
6
8
9
11
13
15
14
10
5
8
12
7
F2
16
17
10
9
Fh
F3
Condições de equilíbrio:
Forma matricial:
2 4 − 5  x1   5 
4 1 − 5.x  =  2 

  2  
2 4 5  x3  − 1
Na junção 2:
∑ Fx = −f1cos
1
4245
4
3° + f4 + f5 cos
1
4245
4
3° = 0

a
a

∑ Fx = − a f1 + f4 + a f5 = 0

∑ Fy = − a f1 − f3 − a f5 = 0

Na junção 3:
∑ Fx = − f2 + f6 = 0

∑ Fy = − F1 + f3 = 0
Idem para demais junções
Gerará um sistema de ordem 17
CCICCI-22
Introdução
Métodos diretos
Regra de Cramer
Eliminação de Gauss
Regra de Cramer
A aplicação da regra de Cramer, em um
sistema de ordem n, exige o cálculo de quantos
determinantes?
n para os numeradores e 1 para o denominador
Gauss-Jordan
Decomposição LU
Métodos iterativos
Gauss-Jacobi
Gauss-Seidel
Considerações finais
Tempo de processamento
Tempo de processamento
Número m de multiplicações, no caso de 17
equações:
= 18 ( 17m + 17 ( 16m + 16 ( 15m + 15 ( 14m +
14 (.... ( 3m + 3 ( 2m )....)))))
multiplicações
18 det17 = 18 ( 17m + 17 det16 )
= 18 ( 17m + 17 ( 16m + 16 det15 ))
= 18 ( 17m + 17 ( 16m + 16 ( 15m + 15 det14 )))
= 18 ( 17m + 17 ( 16m + 16 ( 15m + 15 ( 14m +
14 (.... ( 3m + 3 ( 2m )....)))))
= m(
Lembrando:
+
+
+
:
+
+
2 x 3 x 4 x 5 x
3 x 4 x 5 x
4 x 5 x
5 x
....
....
....
....
x
x
x
x
17
17
17
17
x
x
x
x
18
18
18
18
+
+
+
+
:
16 x 17 x 18 +
17 x 18 )
= 18! (1 + (1/2!) + (1/3!) + ... + (1/16!) ) multiplicações
≈ 9,6 x 1015 multiplicações
Tempo de processamento
CCICCI-22
Quantidade de multiplicações: ≈ 9,6 x 1015
Introdução
Utilizando um supercomputador atual:
Métodos diretos
1011 multiplicações por segundo
Regra de Cramer
Tempo gasto: 9,6 x 104 s ≈ 1 dia
Eliminação de Gauss
Se o sistema fosse de ordem 20, exigiria
cerca de 28 anos de processamento nesse
mesmo computador!
Um algoritmo bem mais eficiente é o
Método da Eliminação de Gauss, que gasta
tempo O(n3)
Método da Eliminaç
Eliminação de Gauss
Objetivo
Transformação do sistema linear a ser resolvido
em um sistema linear triangular
Operações válidas:
Troca da ordem das linhas
Troca da ordem das colunas (com exceção dos
termos independentes)
Multiplicação de uma equação por um número real
não nulo
Substituição de uma equação por uma combinação
linear entre ela mesma e outra equação
Gauss-Jordan
Decomposição LU
Métodos iterativos
Gauss-Jacobi
Gauss-Seidel
Considerações finais
Sistemas Lineares Triangulares
Triangular superior:
 a11 0
a
 21 a22
A = a31 a32

M
 M
 an1 an 2
0
0
a33
M
an 3
K 0
K 0 
K 0

O M 
K ann 
Triangular inferior:
a11 a12 a13
0 a
a23
22

A=0
0 a33

M
M
 M
 0
0
0
K a1n 
K a2n 
K a3n 

O M 
K ann 
Resoluç
Resolução de um sistema triangular
Exemplo:
3x1 + 4x2 − 5x3
x2
+ x3
4x3
+ x4
− 2x4
= −10
= −1
− 5x4
2x4
= 3
= 2
Passos
Considere a matriz aumentada [Ab]:
a11 a12
a a
[Ab] =  21 22
M
M

an1 an2
Passos da resolução:
Continuar analogamente para linhas Lj , 2 < j ≤ n
3x1 + 4 ⋅ (−1) − 5 ⋅ 2 + 1 = −10
x1 = 1
Passo i, 1 < i < n: anular os coeficientes de xi nas linhas
Li+1 a Ln
Exemplo 1
Exemplo 1
2x1 + 3x2 − x3 = 5
2x1 − 3x2 + x3 = −1
L3 = L3 − m31 ⋅ L1, m31 =
2
3 −1 5 
− 2 − 1 − 7
0 − 6 2 − 6
2 3 − 1 5 
[Ab] = 4 4 − 3 3 
2 − 3 1 − 1
4x1 + 4x2 − 3x3 = 3
L2 = L2 − m21 ⋅ L1, m21 =
Linha Ln
Se Lk não existir, então o sistema não tem solução
3x1 + 4x2 − 5x3 + x4 = −10
x2 = −1
Linha L2
Substituir a linha L2 pela combinação linear:
a
L2 − m21 ⋅ L1, onde m21 = 21
a11
Se a11 = 0, trocar L1 com Lk, onde ak1 ≠ 0
4x3 − 5 ⋅ 1 = 3
x3 = 2
x2 + x3 − 2x4 = −1
x2 + 2 − 2 ⋅ 1 = −1
Linha L1
Passo 1: anular os coeficientes de x1 nas linhas L2 a Ln
4x3 − 5x4 = 3
2
x4 = = 1
2
K a1n b1 
K a2n b2 
O M M

an3 ann bn 
a21
=2
a11
L2 = [0 − 2 − 1 − 7]
a31
=1
a11
L 3 = [2
−3
1
− 1] − 1 ⋅ [2
L 3 = [0
−6
2
− 6]
2
L2 = [4 4 − 3 3] − 2 ⋅ [2 3 − 1 5]
3 −1 5 
− 2 − 1 − 7
0 − 6 2 − 6
[Ab] = 0
[Ab] = 0
L3 = L3 − m32 ⋅ L2 , m32 =
a32
=3
a22
L3 = [0 − 6 2 − 6] − 3 ⋅ [0 − 2 − 1 − 7]
3
−1
5]
L3 = [0 0 5 15]
2
3 −1 5 
− 2 − 1 − 7
0 0 5 15 
[Ab] = 0
5x3 = 15 ⇒ x3 = 3

− 2x2 − x3 = −7 ⇒ −2x2 − 3 = −7 ⇒ x2 = 2
2x + 3 ⋅ x − x = 5 ⇒ 2x +6 − 3 = 5 ⇒ 2x = 2 ⇒ x = 1
2
3
1
1
1
 1
Exemplo 2
x1 + 4x2 + 52x3 = 57
27x1 + 110x2 − 3x3 = 134
22x1 + 2x2 + 14x3 = 38
Exemplo 2
4
52 57 
1

[Ab] = 27 110 − 3 134
22 2 14 38 
Nos cálculos a seguir, consideraremos F(10,3,-5,5):
L2 = L2 − m21 ⋅ L1 = [27 110 − 3 134] − (27 / 1) ⋅ [1 4 52 57]
L2 = [0 2 − 1400 − 1410]
L3 = L3 − m31 ⋅ L1 = [22 2 14 38] − (22 / 1) ⋅ [1 4 52 57]
L3 = [0 − 86 − 1130 − 1210]
52
57 
1 4
[Ab] = 0 2 − 1400 − 1410
0 − 86 − 1130 − 1210
Pivoteamentos parcial e completo
Pivôs pequenos geram multiplicadores grandes, que
aumentam os erros de arredondamento...
Uma simples alteração no método de Gauss é escolher
como pivô o elemento de maior módulo:
em cada coluna (pivoteamento parcial)
dentre todos os elementos possíveis no processo de eliminação
(pivoteamento completo): exige um maior esforço
computacional
Voltemos a resolver o exemplo anterior com precisão
de 3 casas decimais, mas com pivoteamento parcial:
4 52 57 
1
27 110 − 3 134


22 2 14 38 
27 110 − 3 134
1
4 52 57 

22 2 14 38 
52
57 
1 4

[Ab] = 0 2 − 1400 − 1410
0 − 86 − 1130 − 1210
L3 = L3 − m32 ⋅ L2 = [0 − 86 − 1130 − 1210] − (− 86 / 2) ⋅ [0 2 − 1400 − 1410]
L3 = [0 0 − 61300 − 61800]
52
57 
1 4
[Ab] = 0 2 − 1400
− 1410 
0 0 − 61300 − 61800 
x3 = -61800/(-61300) = 1,01
x2 = [-1410 – (-1400)⋅1,01]/2 = 0,0
x1 = [57 - 52⋅1,01 - 4⋅0,0]/1 = 4,5
No entanto, a solução exata é:
x1 = 1
x2 = 1
x3 = 1
Exemplo 2 com pivoteamento parcial
L2 = L2 − m21 ⋅ L1 = [1 4 52 57] − (1/ 27) ⋅ [27 110 − 3 134]
L2 = [0 − 0,07 52,1 52]
L3 = L3 − m31 ⋅ L1 = [22 2 14 38] − (22 / 27) ⋅ [27 110 − 3 134]
L3 = [0 − 87,6 16.5 − 71]
− 3 134
27 110
 0 − 0.07 52,1 52 


 0 − 87,6 16,5 − 71
− 3 134
27 110
 0 − 87,6 16,5 − 71


 0 − 0,07 52,1 52 
L3 = L3 −m32 ⋅ L2 = [0 −0,07 52,1 52] −(0,07/ 87,6)⋅ [0 −87,6 16,5 −71]
L3 = [0 0 52,1 52,1]
− 3 134
27 110
 0 − 87,6 16,5 − 71


 0
0
52,1 52,1
x3 = 52,1/52,1 = 1
x2 = [-71-16,5⋅1]/(-87,6) = 0,999
x1 = [134 – (-3)⋅1 – 110⋅0,999]/27 = 1,00
Exercí
Exercício
CCICCI-22
Considere o sistema linear abaixo:
Introdução
Métodos diretos
0,0002x1 + 2x2 = 5
2x1 + 2x2 = 6
Regra de Cramer
Utilizando aritmética de três dígitos decimais,
resolva-o através da eliminação de Gauss:
sem pivoteamento parcial
com pivoteamento parcial
Eliminação de Gauss
Gauss-Jordan
Decomposição LU
Métodos iterativos
Confira os resultados encontrados
Gauss-Jacobi
Gauss-Seidel
Considerações finais
Método de GaussGauss-Jordan
Exemplo
Consiste em efetuar operações sobre as
equações do sistema com a finalidade de
transformá-lo em um sistema diagonal
equivalente, isto é, são nulos todos os
coeficientes aik, quando i≠k
0
a11 0
0 a
0
22

A =  0 0 a33

M
M
M
 0 0
0
K
K
L
O
K
0
0 
0

K
ann 
x1 + 5x2 + x3 = 1
5x1 + 2x2 + 3x3 = 2
1 5 1 1 
2 3 2 
2 3 2 4 
[Ab] = 5
2x1 + 3x2 + 2x3 = 4
5 2 3 2 
1 5 1 1 


2 3 2 4 
L2 = L2 − m21 ⋅ L1 = [1 5 1 1] − (1 / 5) ⋅ [5 2 3 2]
L2 = [0 4,6 0,4 0,6]
L3 = L3 − m31 ⋅ L1 = [2 3 2 4] − (2 / 5) ⋅ [5 2 3 2]
L3 = [0 2,2 0,8 3,2]
3
1 
5 2

[Ab] = 0 4,6 0,4 0,6
0 2,2 0,8 3,2 
Exemplo
Exemplo
5
2
3
1 
4,6
0
− 1,313
0 0 0,609 2,913 
5
2
3
1 
4,6 0,4 0,6
0 2,2 0,8 3,2
[Ab] = 0
[Ab] = 0
L3 = L3 − m32 ⋅ L2 = [0 2,2 0,8 3,2] − (2,2 / 4,6) ⋅ [0 4,6 0,4 0,6]
L3 = [0 0 0,609 2,913]
L1 = [5 0 3 1,571]
5
2
3
1 
4,6 0,4
0,6 
0 0 0,609 2,913
[Ab] = 0
L2 = L2 − m23 ⋅ L3 = [0 4,6 0,4 0,6] − (0,4 / 0,609) ⋅ [0 0 0,609 2,913]
L2 = [0 4,6 0 −1,313]
Outra aplicaç
aplicação
[A|I]
L1 = [5 0 3 1,571] − (3 / 0,609) ⋅ [0 0 0,609 2,913]
L1 = [5 0 0 − 12,78]
0
− 12,78
5 0
[Ab] = 0 4,6 0 − 1,313 
0 0 0,609 2,913 
A solução é:
x1 = -2,556
x2 = -0,2854
x3 = 4,783
Refinamento por resí
resíduos
Uma variação do método de Gauss-Jordan
pode ser utilizada para se encontrar a inversa
de uma matriz A quadrada de ordem n
Basta transformar a matriz A na
correspondente matriz identidade, aplicando
essas mesmas operações em uma matriz
identidade de ordem n
Gauss-Jordan
L1 = [5 2 3 1] − (2 / 4,6) ⋅ [0 4,6 0 − 1,313]
[I|A-1]
Se x(1) for encontrado como solução do sistema
Ax = b, então o erro dessa solução é x – x(1)
Multiplicando o erro por A:
A(x- x(1)) = Ax – Ax(1) = b – b(1) = r(1)
resíduo
O resíduo pode ser utilizado para se encontrar
uma solução melhorada x(2):
x(2) = x(1) + δ(1), onde δ(1) é um vetor de correção
Ax(2) = b ⇔ A(x(1) + δ(1)) = b ⇔ Aδ(1) = b - Ax(1) = r(1)
δ(1) é solução do sistema Aδ = r(1)
Esses cálculos permitem um processo de
refinamento da solução do sistema Ax = b
Exemplo
Exemplo
Vamos refinar o sistema abaixo:
Cálculo do vetor de correção δ(1):
8,7x1 + 3,0x2 + 9,3x3 + 11,0x4 = 16,4
3,0
 8,7
24 ,5 − 8,8

 53,3 − 8,8

 21,0 − 81,0
24,5x1 − 8,8x2 +11,5x3 − 45,1x4 = −49,7
53,3x1 − 8,8x2 −23,5x3 +11,4x4 = −80,8
21,0x1 − 81,0x2 −13,2x3 + 21,5x4 = −106,3
Solução:
Através do método de Gauss, podemos
encontrar a solução abaixo:
x (1 ) = [ 0,97
1,98
− 0,97
Cálculo do resíduo:
r (1 ) = b − Ax (1 )
1,00 ]T
 0,042 
 0,214 

=
 0,594 


 − 0,594 
9,3
11,0   δ 1   0,042 
 
11,5
− 45,1   δ 2   0,214 
=
− 23,5 11,4   δ 3   0,594 
  

− 13,2 21,5   δ 4   − 0,594 
δ
Não está
bom...
 0,0295 


(1 ) =  0,0195 
 − 0,0294 


 0,0000 
Solução melhorada:
x
Exemplo
(2 )
=x
(1 )
+δ
(1 )
 1,0000 
 2,0000 

=
 − 0,9999 


 1,0000 
Melhor aproximaç
aproximação
Novo resíduo:
r ( 2 ) = b − Ax ( 2 )
Cálculo do novo
vetor de correção:
 − 0,009 
 − 0,011 

=
 0,024 


 0,013 
δ
 1,0000 
Outra
 2,0000 
(3)

x =
solução
 − 1,0000 


melhorada:
1,0000


(2 )
=
Melhor que
o anterior
 − 0,0002 
 − 0,0002 


 − 0,0007 


 0,0000 
Novo
resíduo:
Dado um sistema Ax = b, sejam y e z duas aproximações
da solução exata x. Como saber qual delas é a melhor?
A estratégia mais lógica parece ser comparar os
respectivos resíduos: o menor seria da melhor solução
Infelizmente, isso nem sempre é verdade...
Exemplo:
0,24x1 + 0,36x2 + 0,12x3 = 0,84

0,12x1 + 0,16x2 + 0,24x3 = 0,52
0,15x + 0,21x + 0,25x = 0,64
1
2
3

r (3 )
0 
0 
=  
0 
 
0 
 25 
y = − 14
 − 1 
− 3
z =  4 
 0 
0,00
ryy = 0,00
0,08
 0,12 
rzz = 0,24
0,25
− 3
x =  4 
 1 
Conclusão: nem sempre a aproximação de menor
resíduo é a melhor ou a mais exata
Se a busca por resíduos menores não garante melhores
soluções, como saber se o processo de refinamento por
resíduos funciona?
Condicionamento de problemas
Um problema é dito mal condicionado se pequenas
alterações nos dados de entrada ocasionam grandes
erros no resultado final
Exemplo:
0,992x + 0,873y = 0,119

0,481x + 0,421y = 0,060
Solução: x=1 e y=-1
Suponha que os valores desse sistema sejam obtidos
experimentalmente, e por isso os termos independentes
possam variar de ±0,001:
Valor perturbado
0,992x + 0,873y = 0,120

0,481x + 0,421y = 0,060
Solução: x=0,815 e y=-0,789
Outro exemplo
Considere os seguintes sistemas:
x + 3y = 11
(a)

1,5x + 4,501y = 16,503 (b)
(a)
x + 3y = 11

1,5x + 4,501y = 16,500 (c)
Solução: x=2 e y=3
Solução: x=10,28 e y=0,24
y
(a)
(b)
(c)
Erro na entrada: (|0,119-0,120|/|0,119|) ≈ 0,8%
x
Erro no resultado: (|1,0-0,815|/|1,0|) ≈ 18,5%
Métricas de condicionamento
Há métricas para o condicionamento de sistemas
lineares, baseadas em normas de vetores e matrizes
(vide Cláudio & Marins)
No entanto, esses cálculos são difíceis...
Também é possível identificar o condicionamento de um
sistema linear apenas com o uso dos refinamentos:
Se os resíduos r(1), r(2), ..., r(n) são pequenos, mas as correções
δ(1), δ(2), ..., δ(n) são grandes, então o sistema é mal condicionado
Para sistemas bem condicionados, bastam no máximo dois
refinamentos (ou seja, δ(2) é muito pequeno)
Ao longo desse processo, os resíduos e as correções
devem ser calculados com precisão dupla
Exemplo
Considere o sistema abaixo em F(10,5,-98,100):
2,4759x1 +1,6235x2 + 4,6231x3 = 0,064700

1,4725x1 + 0,95890x2 −1,3253x3 = 1,0473
2,6951x + 2,8965x −1,4794x = −0,67890
1
2
3

 1,8406
x(1) =  −2,0717
−0,24419

Primeiro refinamento em F(10,10,-98,100):
 0,0648   0,064821801
r ((11)) = b − Ax ((11)) =  1,0473  −  1,047355377
 − 0,6789   − 0,678823304
Resolução de
Aδ(1) = r(1):
− 0,0000042282
δ((11)) =  0,000025110 
 − 0,000057765 
  − 0,000121801
 =  − 0,000055377
 
  − 0,000076696




Resíduos
pequenos
Solução melhorada
x(2) = x(1) + δ(1):
Correções
pequenas
 1,8405 
x((22)) =  − 2,0717 
− 0,24419
CCICCI-22
Uma outra forma de ver...
Introdução
Consideremos o sistema de 3 equações Ax = b:
 a11 a12 a13 
A = a21 a22 a23  = A(0 )
a31 a32 a33 
Métodos diretos
Regra de Cramer
Eliminação de Gauss
(1 )
(1 )
a11(1 ) a12

a13

(1 )
(1 ) 
A =  0 a22 a23  = M( 0 ) .A( 0 ) ,
(1 )
(1 ) 
 0 a32
a33


(1 )
Decomposição LU
Métodos iterativos
Gauss-Seidel
(2 )
A
Considerações finais
Uma outra forma de ver...
(2)
(2 )
a11(2) a12

a13

(2)
(2 ) 
=  0 a22 a23  = M(1 ) .A(1 ) ,
(2 ) 
 0
0 a33


0
0
1
onde M(1 ) = 0
1
0 
0 − m32 1 
Decomposiç
Decomposição LU
Resumindo:
A comprovação anterior pode ser generalizada em um
teorema
A = A(0)
A(1) = M(0).A(0) = M(0).A
A(2) = M(1).A(1) = M(1).M(0).A
A = (M(1).M(0))-1.A(2)
A = (M(0))-1.(M(1))-1.A(2)
0
0
 1
m
0
 21 1
A = L.U = m31 m32 1

M
M
 M
mn1 mn2 mn3
0 0
 1

(M ) (M ) = m21 1 0
m31 m32 1
( 0 ) −1
Portanto:
0 0
 1
onde M( 0 ) = − m21 1 0
− m31 0 1 
Após a segunda fase da eliminação de Gauss:
Gauss-Jacobi
É fácil comprovar que:
b1 
b = b2 
b3 
Após a primeira fase da eliminação de Gauss:
Gauss-Jordan
 x1 
x = x2 
x3 
(1) −1
(2 )
0 0 a11( 2) a12
 1



(2 )
A = m21
1 0  0 a22

0
m31 m32 1   0
(2 )

a13
(2 ) 
a23
 = L.U
(2 ) 
a33 
K 0 u11 u12 u13
K 0  0 u22 u23
K 0 ⋅  0 0 u33
 
O 0  M
M
M
K 1   0 0 0
K u1n 
K u2n 
K u3n 

O M 
K unn 
Dada uma matriz quadrada de ordem n, seja Ak a matriz
constituída das primeiras k linhas e colunas de A.
Suponha que det(Ak) ≠ 0, 0 ≤ k ≤ n-1. Então:
Existe uma única matriz triangular inferior L=(mij), com mii = 1,
1 ≤ i ≤ n. Os demais são os multiplicadores da Eliminação de Gauss
Existe uma única matriz triangular superior U=(uij), tais que
L.U = A
det(A) = u11.u12. ... .unn
Decomposiç
Decomposição LU
Exemplo
Portanto, dados o sistema linear Ax = b e a
decomposição (ou fatoração) LU da matriz A, temos:
3x1 + 2x2 + 4x3 = 1
x1 + x2 + 2x3 = 2
Ax = b ⇔ (L.U)x = b
Chamando Ux = y, o sistema original passa a ser Ly = b,
ou seja, surgem dois sistemas triangulares
Por outro lado, é fácil verificar que y = L-1.b é o vetor b
acumulando as operações da Eliminação de Gauss
Por exemplo, no caso de um sistema com 3 equações:
Como L = (M(0))-1.(M(1))-1, então L-1 = M(1).M(0)
Portanto, y = M(1).M(0).b
Vantagem da decomposição A = L.U: uma vez calculadas
as matrizes L e U, resolvemos mais rapidamente
qualquer sistema com a matriz A. Isso é útil, por
exemplo, no refinamento por resíduos
Exemplo
4x1 + 3x2 − 2x3 = 3
 1 0 0
L =  1 / 3 1 0
4 / 3 1 1 
Ax = b
4 
3 2
U = 0 1 / 3 2 / 3
0 0 − 4 
LUx = b
y1 = 1
Ux = y
3 2 4
A = 1 1 2
4 3 2
4 
3 2
0 1 / 3 2 / 3 


0 1 / 3 − 10/ 3
 1 0 0
L =  1 / 3 1 0
4 / 3 1 1 
multiplicadores
2
4 
 3
1 / 3 1 / 3 2 / 3 


4 / 3 1 / 3 − 10/ 3
2
4 
 3
1 / 3 1 / 3 2 / 3


4 / 3 1 − 4 
4 
3 2

U = 0 1 / 3 2 / 3
0 0 − 4 
Outra aplicaç
aplicação
3x1 + 2x2 + 4x3 = 1
x1 + x2 + 2x3 = 2
Ly = b
4x1 + 3x2 + 2x3 = 3
1 / 3y1 + y2 = 2
4 / 3y1 + y2 + y3 = 3
3x1 + 2x2 + 4x3 = 1
1 / 3 x2 + 2 / 3 x3 = 5 / 3
− 4x3 = 0
 1 
y = 5 / 3
 0 
− 3
x =  5 
 0 
A decomposição LU também é útil no cálculo
da matriz inversa
Resolver o sistema AX = B, onde A, X e B são
matrizes de ordem n, é o mesmo que resolver
n sistemas Ax = b, onde x e b são vetores de
tamanho n
A inversa A-1 da matriz A pode ser
encontrada através da resolução do sistema
AX = I, onde I é a matriz identidade
Nesse caso, basta realizar uma única vez a
decomposição LU da matriz A, e depois
utilizá-la na resolução de n sistemas
Decomposiç
Decomposição LU com pivoteamento
É possível incorporar as estratégias de pivoteamento
parcial ou completo à decomposição LU
Uma matriz quadrada P de ordem n é uma matriz de
permutação se for obtida da correspondente matriz
identidade através de permutações em suas linhas ou
colunas
As eventuais permutações de linhas ou colunas na
matriz A(k), obtida em um passo intermediário da
Eliminação de Gauss, podem ser realizadas através da
multiplicação por uma matriz de permutação
Exemplo:
3 1 4
A(k) = 1 5 9
2 6 5
0 1 0 3 1 4 1 5 9
P.A(k) = 0 0 1 .1 5 9 = 2 6 5
1 0 0 2 6 5 3 1 4
Exemplo com pivoteamento parcial
0
−3 
 4
A(2) = 3 / 4 − 4 13/ 4
1 / 4 − 1 / 2 35/ 8
0
0
 1
L = 3/ 4
1
0
1 / 4 − 1 / 2 1 
Exemplo com pivoteamento parcial
3x1 − 4x2 + x3 = 9
x1 + 2x2 + 2x3 = 3
4x1 − 3x3 = −2
3 − 4 1 
A(0) = 1 2 2 
4 0 − 3
0
−3 
 4
1 0 0
A(1) = 1 / 4 2 11/ 4 P(1) = 0 0 1 


3 / 4 − 4 13/ 4
0 1 0
0 0 1  3 − 4 1  4 0 3
A' = P.A = 1 0 0.1 2 2  = 3 − 4 1
0 1 0 4 0 − 3 1 2 2
A’x = b’ ⇔ PAx = Pb ⇔ LUx = Pb
4 0 3
A'(0) = P(0).A(0) = 1 2 2
3 − 4 1 
−3 
0
 4
A'(1) = P(1).A(1) = 3 / 4 − 4 13/ 4
1 / 4 2 11/ 4
Exemplo com pivoteamento parcial
3x1 − 4x2 + x3 = 9
x1 + 2x2 + 2x3 = 3
4x1 − 3x3 = −2
−3 
4 0
U = 0 − 4 13/ 4
0 0 35/ 8
L.U = A’ = P.A, onde P = P(1).P(0):
0 0 1 
P(0) = 0 1 0
1 0 0
0
0
 1
L = 3 / 4
1
0
1 / 4 − 1 / 2 1 
Ax = b
Ly = Pb
Ux = y
−3 
4 0
U = 0 − 4 13/ 4
0 0 35/ 8
LUx = Pb
0
0  y1  0 0 1   9 
 1
3 / 4
1
0.y2  = 1 0 0. 3 

1 / 4 − 1 / 2 1  y3  0 1 0 − 2
− 3  x1   2 
4 0
0 − 4 13/ 4.x  =  21/ 2 

  2 

0 0 35/ 8 x3  35/ 4
 −2 
y =  21/ 2 
35/ 4
1
x = − 1
 2 
CCICCI-22
Introdução
Métodos iterativos
Como foi inicialmente comentado, os métodos iterativos
para resolução de sistemas lineares consistem em
encontrar uma sequência de aproximações sucessivas
Dada uma estimativa inicial x(0), calcula-se a sequência
x(1), x(2), x(3) ..., até que determinado critério de parada
seja satisfeito
O sistema Ax = b é transformado em x(k) = Cx(k-1) + g,
k>0, onde C é uma matriz e g um vetor
Possíveis critérios de parada:
Métodos diretos
Regra de Cramer
Eliminação de Gauss
Gauss-Jordan
Decomposição LU
Métodos iterativos
máximo erro absoluto ou relativo
número de iterações
Gauss-Jacobi
Gauss-Seidel
Principais métodos: Gauss-Jacobi e Gauss-Seidel
Considerações finais
CCICCI-22
Introdução
Método de GaussGauss-Jacobi
Considere o sistema linear em sua forma inicial:
Métodos diretos
a11 x1 + a12 x2 + ... + a1n xn = b1
Regra de Cramer
a21 x1 + a22 x2 + ... + a2n xn = b2
M
M
O M M
Eliminação de Gauss
Gauss-Jordan
an 1 x1 + an 2 x2 + ... + ann xn = bn
Decomposição LU
Métodos iterativos
Gauss-Jacobi
Gauss-Seidel
Considerações finais
Isolando a i-ésima incógnita na i-ésima equação:
x1 = (b1 - a12 x2 - ... - a1n x2)/a11
x2 = (b2 - a21 x1 - ... - a2n xn)/a22
...
xn = (bn - an1 x1 - ... - an,n-1 xn-1)/ann
Método de GaussGauss-Jacobi
Exemplo
Dessa forma, para x(k) = Cx(k-1) + g:
0

− a / a
21
22
C=

M

 − an1 / ann
− a12 / a11
0
M
− an 2 / ann
L − a1n / a11 
L − a2n / a22 

O
M

L
0

10x1 + 2x2 + x3 = 7
 b1 / a11 
b / a 
g =  2 22
 M 


bn / ann 
Exemplos de critérios de parada:
Erro absoluto: d(k) = maxi |x(k) – x(k-1)| < ε
Erro relativo: dr(k) = d(k)/(maxi |x(k)|) < ε
x1 + 5x2 + x3 = 8
2x1 + 3x2 + 10x3 = 6
− 2 / 10 − 1 / 10
 0
C = − 1 / 5
0
− 1 / 5 
− 1 / 5 − 3 / 10
0 
 0,7 
x(0) = − 1,6
 0,6 
ε = 0,05
7 / 10
g =  8 / 5 
6 / 10
 0,96 
x(1) = Cx(0) + g = − 1,86
 0,94 
|x1(1) – x1(0)| = 0,26
|x2(1) – x2(0)| = 0,26
dr(1) = 0,34/(max |xi(1)|) = 0,1828 > ε
|x3(1) – x3(0)| = 0,34
Exemplo
− 2 / 10 − 1 / 10
 0
0
− 1 / 5 
C = − 1 / 5
− 1 / 5 − 3 / 10
0 
0,978
x(2) = Cx(1) + g =  − 1,98
0,966
Crité
Critério das linhas
7 / 10
g =  8 / 5 
6 / 10
 0,96 
x(1) = − 1,86
 0,94 
dr(2) = 0,12/1,98 = 0,0606 > ε
Em um método iterativo, a convergência para a
solução exata não é garantida: é preciso que o
sistema satisfaça alguns requisitos
Há uma condição suficiente para a convergência
do Método de Gauss-Jacobi, conhecido como o
critério das linhas :
n
∑a
ij
 0,9994
x(3) = Cx(2) + g = − 1,9888
 0,9984
j=1
j ≠i
dr(3) = 0,0324/1,9888 = 0,0163 < ε
< aii , para i = 1,2,...,n
Exemplos
Demonstraç
Demonstração
Considere o exemplo anterior:
Sejam:
10x1 + 2x2 + x3 = 7
2+1 < 10
x1 + 5x2 + x3 = 8
2x1 + 3x2 + 10x3 = 6
1+1 < 5
x* = [x1, x2, ..., xn]T: a solução exata de Ax = b
Garantia de
convergência
2+3 < 10
1=1
x1 − 3x2 = −3
1<3
e(k) = x(k) – x*: o erro na k-ésima aproximação
Queremos garantir que limk→∞ e(k)i = 0, 1≤i≤n
Considere o exemplo abaixo:
x1 + x2 = 3
x(k) = [x(k)1, x(k)2, ..., x(k)n]T: a k-ésima aproximação de x*
No Método de Gauss-Jacobi, pode-se constatar que:
e(k+1)1 = -(a12e(k)2 + a13e(k)3 + ... + a1ne(k)n)/a11
Não há garantia
de convergência
e(k+1)2 = -(a21e(k)1 + a23e(k)3 + ... + a2ne(k)n)/a22
e(k+1)n = -(an1e(k)1 + an2e(k)2 + ... + an(n-1)e(k)n-1)/ann
No entanto, o método de Gauss-Jacobi converge neste sistema
para a solução exata x1 = x2 = 3/2. Verifique!
Isso mostra que o critério das linhas é suficiente, mas não
necessário
Sejam:
E(k) = máx1≤i≤n{|e(k)i|}
αi = (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|, 1≤i≤n
Quando o critério das linhas é satisfeito, αi < 1
Demonstraç
Demonstração (continuaç
(continuação)
Mais um exemplo
Quando k→∞, x(k)→x* é equivalente a E(k)→0
Considere o sistema a seguir:
Demonstraremos que
E(k+1)
≤
α.E(k),
onde α = máx1≤i≤n{αi}
Para 1 ≤ i ≤ n:
e(k+1)i = -(ai1e(k)1 + ... + ai(i-1)e(k)i-1 + ai(i+1)e(k)i+1 + ... + aine(k)n)/aii
|e(k+1)i|
(|ai1|.|e(k)1|
≤
|ain|.|e(k)n|)/|aii|
+ ... +
|ai(i-1)|.|e(k)i-1|
+
|ai(i+1)|.|e(k)i+1|
+ ... +
|e(k+1)i| ≤ (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|).E(k)/|aii|
|e(k+1)i| ≤ αi.E(k)
Portanto, E(k+1) ≤ α.E(k)
Consequentemente, E(k+1)/E(k) ≤ α
Como α<1, então E(k)→0 quando k→∞: há convergência!
x1 + 3x2 + x3 = −2
3+1 > 1
5x1 + 2x2 + 2x3 = 3
6x2 + 8x3 = −6
5+2 > 2
6<8
Não há garantia
de convergência
No entanto, uma permutação entre as duas primeiras linhas
garante a convergência:
5x1 + 2x2 + 2x3 = 3
2+2 < 5
x1 + 3x2 + x3 = −2
1+1 < 3
6x2 + 8x3 = −6
6<8
Garantia de
convergência
Quando o critério das linhas não for satisfeito, convém tentar
uma permutação de linhas e/ou colunas
CCICCI-22
Método de GaussGauss-Seidel
Introdução
Analogamente ao Método de Gauss-Jacobi,
calcula-se x(k) = Cx(k-1) + g:
Métodos diretos
Regra de Cramer
0

− a / a
C =  21 22

M

 − an1 / ann
Eliminação de Gauss
Gauss-Jordan
Decomposição LU
Métodos iterativos
 b1 / a11 
b / a 
g =  2 22
 M 


bn / ann 
valores calculados na mesma iteração: x1(k +1) ,..., xj(−k1+1)
Gauss-Seidel
valores da iteração anterior: xj(k+1) ,..., xn(k )
Considerações finais
Exemplo
Exemplo
5 x1 + x2 + x3 = 5
ε = 0,05
3x1 + 4 x2 + x3 = 6
3x1 + 3x 2 + 6 x3 = 0
= 1,5 − 0,75 x
(k )
3
− 0,25 x
x3( k +1 ) = − 0,5 x1( k +1 ) − 0,5 x2( k +1 )
x1(k +1 ) = 1 − 0,2x2(k ) − 0,2x3(k )
x2(k +1 ) = 1,5 − 0,75x1(k +1 ) − 0,25x3(k )
x3(k +1 ) = −0,5x1(k +1 ) − 0,5x2(k +1 )
x1(1 ) = 1 − 0 − 0 = 1
x1( k +1 ) = 1 − 0,2x2( k ) − 0,2x3( k )
( k +1 )
1
x(0)
0
= 0
0
Primeira iteração (k=0):
Processo iterativo:
x
L − a1n / a11 
L − a2n / a22 

O
M

0
L

No entanto, utiliza-se no cálculo de xj( k +1) :
Gauss-Jacobi
( k +1 )
2
− a12 / a11
0
M
− an 2 / ann
x2(1 ) = 1,5 − 0,75 .1 − 0 = 0,75
x3(1 ) = −0,5.1 − 0,5.0,75 = −0,875
 1 
x(1) =  0,75 
− 0,875
|x1(1) – x1(0)| = 1
|x2(1) – x2(0)| = 0,75
|x3(1) – x3(0)| = 0,875
dr(1) = 1/(max |xi(1)|) = 1 > ε
Exemplo
Exemplo
x1(k +1 ) = 1 − 0,2x2(k ) − 0,2x3(k )
x1(k +1 ) = 1 − 0,2x2(k ) − 0,2x3(k )
x2(k +1 ) = 1,5 − 0,75x1(k +1 ) − 0,25x3(k )
x2(k +1 ) = 1,5 − 0,75 x1(k +1 ) − 0,25 x3(k )
( k +1 )
3
x
( k +1 )
1
= −0,5x
( k +1 )
2
x3(k +1 ) = 0 − 0,5x1(k +1 ) − 0,5x2(k +1 )
− 0,5x
Segunda iteração (k=1):
(2)
1
x
(2)
2
x
= 1 − 0,2.0,75 − 0,2.( −0,875 ) = 1,025
= 1,5 − 0,75 .1,025 − 0,25 .( −0,875 ) = 0,95
x3( 2 ) = −0,5.1,025 − 0,5.0,95 = −0,9875
Terceira iteração (k=2):
 1,025 
x =  0,95 
− 0,9875
(2)
|x1(2) – x1(1)| = 0,025
|x2(2) – x2(1)| = 0,20
x1( 3 ) = 1 − 0,2.0,95 − 0,2.( −0,9875 ) = 1,0075
x2( 3 ) = 1,5 − 0,75 .1,0075 − 0,25 .( −0,9875 ) = 0,9912
x3( 3 ) = −0,5.1,0075 − 0,5.0,9912 = −0,9993
|x1(3) – x1(2)| = 0,0175
dr(2) = 0,2/(max |xi(2)|) = 0,1951 > ε
|x2(3) – x2(2)| = 0,0412
dr(3) = 0,0412/(max |xi(3)|) = 0,0409 < ε
|x3(2) – x3(1)| = 0,1125
|x3(3) – x3(2)| = 0,0118
Interpretaç
Interpretação geomé
geométrica
Crité
Critério de Sassenfeld
No caso de um sistema linear de ordem 2, é
possível visualizar a convergência do método:
Sejam os seguintes valores:
x2
x*
x1
Os pontos (x1(k+1), x2(k))
satisfazem a primeira equação,
enquanto os pontos (x1(k+1), x2(k+1))
satisfazem a segunda
No mesmo sistema, a
convergência pode não ocorrer...
x1
β1 =
βi =
1
aii
1 n
⋅ ∑ a1 j
a11 j=2
n
 i−1

⋅ ∑ aij ⋅ β j + ∑ aij 
 j=1
j=i+1

, para 1 < i ≤ n
β = max {βj}, 1 ≤ j ≤ n
x2
x*
 1,0075 
x(3) =  0,9912 
− 0,9993
Se β < 1, então o Método de Gauss-Seidel gera
uma sequência convergente, qualquer que seja
x(0)
Quanto menor for β, mais rápida será a convergência
Exemplo
2 x1 + x2 − 0,2 x3 + 0,2 x 4 = 0,4
0,6 x1 + 3x2 − 0,6 x3 − 0,3x 4 = − 7 ,8
− 0,1 x1 − 0,2 x 2 + x3 + 0,2 x 4 = 1,0
0,4 x1 + 1,2 x2 + 0,8 x3 + 4 x 4 = − 10 ,0
1
⋅ (1 + 0,2 + 0,2) = 0,7
2
1
β2 = ⋅ (0,6 ⋅ 0,7 + 0,6 + 0,3) = 0,44
3
1
β3 = ⋅ (0,1 ⋅ 0,7 + 0,2 ⋅ 0,44 + 0,2) = 0,358
1
1
β 4 = ⋅ (0,4 ⋅ 0,7 + 1,2 ⋅ 0,44 + 0,8 ⋅ 0,358) = 0,2736
4
β = 0,7 < 1
β1 =
Demonstraç
Demonstração (continuaç
(continuação)
Quando k→∞, x(k)→x* é equivalente a E(k)→0
Demonstraremos por indução em i (1≤i≤n) que E(k+1) ≤ β.E(k), onde
β = máx1≤i≤n{βi}
Base (i=1):
|e(k+1)1| ≤ (|a12|.|e(k)2| + |a13|.|e(k)3| + ... + |a1n|.|e(k)n|)/|a11|
|e(k+1)1| ≤ [(|a12| + |a13| + ... + |a1n|)/|a11|]. máx1≤i≤n{|e(k)i|}
|e(k+1)1| ≤ β1.E(k) ≤ β.E(k)
Hipótese: |e(k+1)i-1| ≤ βi-1.E(k) ≤ β.E(k)
Passo:
|e(k+1)i| ≤ (|ai1|.|e(k+1)1| + ... + |ai(i-1)|.|e(k+1)i-1| + |ai(i+1)|.|e(k)i+1| + ... +
|ain|.|e(k)n|)/|aii|
|e(k+1)i| ≤ (|ai1|.β1 + ... + |ai(i-1)|.βi-1 + |ai(i+1)| + ... + |ain|).E(k)/|aii|
|e(k+1)i| ≤ βi.E(k) ≤ β.E(k)
Portanto, E(k+1)/E(k) ≤ β
Como β<1, então E(k)→0 quando k→∞: há convergência!
Demonstraç
Demonstração
Sejam:
x* = [x1, x2, ..., xn]T: a solução exata de Ax = b
x(k) = [x(k)1, x(k)2, ..., x(k)n]T: a k-ésima aproximação de x*
e(k) = x(k) – x*: o erro na k-ésima aproximação
Queremos garantir que limk→∞ e(k)i = 0, 1≤i≤n
No Método de Gauss-Seidel, pode-se constatar que:
e(k+1)1 = -(a12e(k)2 + a13e(k)3 + ... + a1ne(k)n)/a11
e(k+1)2 = -(a21e(k+1)1 + a23e(k)3 + ... + a2ne(k)n)/a22
e(k+1)n = -(an1e(k+1)1 + an2e(k+1)2 + ... + an(n-1)e(k+1)n-1)/ann
Sejam:
E(k) = máx1≤i≤n{|e(k)i|}
β1 = (|a12| + |a13| + ... + |a1n|)/|a11|
βi = (β1.|ai1| + ... + βi-1.|ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|, 1<i≤n
Exemplos
Considere o sistema abaixo, anteriormente visto:
x1 + x2 = 3
x1 − 3x2 = −3
β1 = 1 / 1 = 1
β2 = (1.1) / 3 = 1 / 3
β=1
Não há garantia
de convergência
No entanto, o Método de Gauss-Seidel converge neste sistema
para a solução exata x1 = x2 = 3/2. Verifique!
Isso mostra que o critério de Sassenfeld, como o critério das
linhas, é suficiente, mas não necessário
Considere outro sistema:
10x1 + x2 = 23
6x1 − 2x2 = 18
β1 = 1 / 10 = 0,1
β2 = (6.0,1) / 2 = 0,3
β = 0,3 < 1
Neste caso, o critério de Sassenfeld garante a convergência,
mas o critério das linhas, não...
CCICCI-22
Introdução
Métodos diretos
Regra de Cramer
Eliminação de Gauss
Gauss-Jordan
Decomposição LU
Métodos iterativos
Gauss-Jacobi
Gauss-Seidel
Considerações finais
Relaç
Relação entre os crité
critérios
Se um sistema satisfaz o critério das linhas, então
também satisfará o critério de Sassenfeld
Demonstração:
Seja α = máx1≤i≤n{αi} < 1,
onde αi = (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|
Vamos provar por indução em i que βi ≤ αi < 1, 1≤i≤n
Base (i=1):
β1 = (|a12| + |a13| + ... + |a1n|)/|a11| = α1 < 1
Hipótese: βi ≤ αi < 1, 1≤i<n
Passo (1≤i≤n):
βi = (β1.|ai1| + ... + βi-1.|ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii|
βi ≤ (|ai1| + ... + |ai(i-1)| + |ai(i+1)| + ... + |ain|)/|aii| = αi < 1
Portanto, α < 1 ⇒ β < 1
A volta nem sempre é verdadeira...
Consideraç
Considerações finais
Métodos diretos versus iterativos
Tanto o critério das linhas como o critério de
Sassenfeld são condições suficientes para a
convergência, mas não necessárias
Em sistemas esparsos (com grande número de
coeficientes nulos), o Método da Eliminação de
Gauss não é apropriado, pois não preserva esta
vantajosa qualidade. Nesses casos, convém
utilizar métodos iterativos
Os métodos iterativos são menos suscetíveis ao
acúmulo de erros de arredondamento
Convergência
Diretos: não faz sentido considerar essa questão,
pois calculam a solução exata
Iterativos: ocorre sob determinadas condições
Esparsidade da matriz de coeficientes
Diretos: alteram a estrutura da matriz
Iterativos: utilizam sempre a matriz inicial
Erros de arredondamento
Diretos: ocorrem a cada etapa e acumulam-se
Iterativos: somente os erros da última etapa
afetam a solução