Sistemas lineares
Elementos de Análise Numérica
Resolução de sistemas de equações lineares
Pontos mais importantes:
-matrizes e operações com matrizes
-forma geral de sistemas de equações lineares
-solução gráfica
-métodos directos
-regra de Cramer
-Gauss (pivotagem)
-matriz inversa (Gauss-Jordan)
-factorização LU
-análise dos erros (número de cond. da matriz)
-métodos iterativos
-Gauss-Siedel
-Jacobi
-Sistemas especiais
1
Sistemas lineares
Elementos de Análise Numérica
Representação geral de sistemas lineares
-procuramos os valores de x1, x2,........,xn
simultaneamente as funções seguintes:
f1(x1, x2,........,xn )=0
f2(x1, x2,........,xn )=0
...
fn(x1, x2,........,xn )=0
que
satisfaçam
-sistemas lineares (fi (1<i<n) são lineares):
a 11x1
a 21x1
 a 12 x 2
 a 22 x 2
...  a 1n x n  c1
...  a 2 n x n  c 2

a n1 x 1


 a n2 x2

...  a nn x n  c n
ou
[A]nn*{x}n={c}n
-Exemplos práticos: reactores, solução numérica de eq. diferenciais, optimização,...
2
Sistemas lineares
Elementos de Análise Numérica
Solução gráfica
-aplicação para n=2
a 11x1
a 21x1
x2
a 11
x2  
x1

 a 12 x 2  c1  
a 12
 
a 21
 a 22 x 2  c 2  
 x 2   a x1
22
solução
c1

a 12
c2

a 22
-sistemas singulares:
-sem solução: decl. iguais
-infinit num.de sol.: decl.
e intercep. iguais
-mal condicionados:
-próximo de singulares
-extremamente sens. a
erros
x1
3
Sistemas lineares
Elementos de Análise Numérica
Métodos de solução
1, Métodos directos:
-solução por eliminação de incógnitas
-solução “exacta” num número fin. de op.
aritméticas simples
-regra de Cramer
-eliminação Gaussiana
-matriz inversa (Gauss-Jordan)
-factorização LU
4
Sistemas lineares
Elementos de Análise Numérica
Factorização LU (decomposição triangular)
-só envolve operações com a matriz dos coeficientes
-adequada para resolver sistemas com a mesma matriz dos coef. (várias
vectores de segundos membros)
-consequentemente mais eficiente que o método de Gauss-Jordan
-com certas modificações simples permite calcular a matriz inversa de [A]
-necessita de uma estratégia de pivotagem como os outros métodos
directos
-a eliminação Gaussiana pode ser usada como um método LU
5
Sistemas lineares
Elementos de Análise Numérica
Factorização LU (decomposição triangular)
[A]nn*{x}n-{c}n=0
-suponha que esta eq. pode ser reformulada como:
1 a 12
0 1

 

0 0
 a 1n   x 1   d 1 
 a 2 n   x 2  d 2 
    
     
   
 1  x n  d n 
ou [U]nn*{x}n-{d}n=0
-suponha também que existe uma matriz triangular inferior:
 l11 0
l
122
21

 L 



l n 1 l n 2
0
 0

  

 1nn 

tal que: [L] nn([U]nn*{x}n-{d}n)= [A]nn*{x}n-{c}n
então: [L] nn[U]nn=[A]nn
e [L] nn {d}n ={c}n
6
Sistemas lineares
Elementos de Análise Numérica
Factorização LU (decomposição triangular)
diagrama do método:
[A]nn*{x}n={c}n
decomposição
[U] nn [L]nn
[L] nn* {d}n ={c}n
[U]nn
substituição para
frente
*{x}n={d}n
substituição para
trás
{x}
7
Sistemas lineares
Elementos de Análise Numérica
Decomposição Crout
-resulta uma matriz onde [U] contém 1 na diagonal
-determinação de elementos de [L] e [U] simultaneamente usando
as regras de multiplicação da matrizes:
Algoritmo:
li1=ai1
u1j=a1j/l11
[L] nn[U]nn=[A]nn
1<i<n
1<j<n
1
0



 0
-repetir para j=2,3,,,n-1
j1
lij  aij  lik ukj
para
i = j, j+1,...,n
k 1
u12  u1n 
1  u2 n 

   

0  1 
j1
u jk 
-e
a jk  l ji uik
i 1
l jj
n1
l nn  a nn  l nk ukn
k 1
para
k = j+1, j+2,...,n
 l11 012
l
 21 l 22



 l n1 l n 2
 01n 
 0 2 n 
  

 l nn 
 a 11
a
 21
 

 a n1
a 12
a 22

a n2
 a 1n 
 a 2 n 
  

 a nn 
8
Sistemas lineares
Elementos de Análise Numérica
Substituição para frente: aplicação das regras de multiplicação de matrizes
-algoritmo:
d1 
c1
l11
[L] nn* {d}n ={c}n
i 1
ci  lijd j
di 
j1
lii
para
i = 2,3,...,n
 l11
l
 21
 

l m1
012
l 22

l m2
 01n 
 02 n 

  

 l mn 
 d1 
d 
 2

 
d n 
 c1 
c 
 2

 
c n 
9
Sistemas lineares
Elementos de Análise Numérica
Substituição para trás: aplicação das regras de multiplicação de matrizes
-algoritmo:
[U]nn
xn  d n
*{x}n={d}n
n
xi = di   uijx j para
ji 1
 x1 
x 
 2

 
x n 
i = n-1,n-2,...,1
1
0



 0
u12
1

0
 u 1n 
 u2 n 

  

 1 
 d1 
d 
 2

 
d n 
10
Sistemas lineares
-exemplo:
Elementos de Análise Numérica
 1 3 7   x1   10
 3 1 8  x    9 


 2  
 6 2  2  x 3   0 
- decomposição:
1 u12
0 1

0 0
l11=a11=-1 ; l21=a21=3 ; l31=a31=6
l11u12=a12 ->u12=a12/l11=3/-1=-3
l11u13=a13 ->u13=a13/l11=7/-1=-7
l21u12+ l221 =a22 ->l22=10
l31u12+ l321 =a32 ->l32=20
l21u13+ l22u23 =a23 ->u23=2.9
l31u13+ l32u23 + l331 =a33 ->l33=-18
 l11
l
 21
l31
0
l 22
l32
0
0 
l33 
u13 
u 23 
1 
 1 3 7 
3 1 8 


 6 2  2
11
Sistemas lineares
0 
 1 0
L   3 10 0 
 6 20  18
Elementos de Análise Numérica
1  3  7 
U  0 1 2.9
0 0
1 
-Substituição para frente:
[L] nn* {d}n ={c}n
 d1 
d 
 2

d 3 

0 
 1 0
 3 10

0


 6 20  18
 10


9


 0 


d1=-10/-1=10
d2=(9-310)/10=-2.1
d3=(0-610-20(-2.1))/-18=1
 10 
d   2.1
 1 
12
Sistemas lineares
Elementos de Análise Numérica
Substituição para trás:
x3=1
[U]nn
*{x}n={d}n
x2=-2.1-2.91=-5
1  3  7 
 0 1 2 .9 


0 0
1 
x1=10-(-3)(-5)- (-7)1 =2
 x1 
x 
 2

x3 

 10 
  2.1


 1 
x1  2
x 2  5
x3  1
13
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
-a solução de um sistema linear envolve a propagação dos erros de
arredondamento, por isso deve ser considerada como uma solução
aproximada
-exemplo (solução exacta: x1=8 x2=0,8):
1,05x1  2,00x2  10,0 x1  1,67

1,10x1  2,00x2  10.4 x2  6,35
1,05 2,0010,0
1,05 2,00 10,0 


   

1
,
10
2
,
00
10
,
4
0

0
,
120

0
,
200




a (1) 22  2,00  1,06 2,00  0.120
1,10
f
1, 06
1, 05
 0,200
 1,67
 0,120
10,0  2,001,67
x1 
 6,35
1,05
x2 
c (1) 2  10,4  1,0610,0  0,200
14
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
-erro de aproximação:
-resíduo da solução:
 e   x   x 
 R    A  x   A  x    c   A  x 
 A  e   R 
-além de aplicações em engenharia, a matriz inversa indica se um sistema
é mal condicionado (erros grandes):
- A é normalizada e existem elementos em A-1 que são
várias ordens de magnitude maiores que a unidade
- A* A-1 é muito diferente que I
- [A-1] -1 é muito diferente que A
15
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
Normas de vectores e matrizes: uma função real que mede o “tamanho”
de vectores e matrizes
-a norma tem propriedades semelhantes ao valor absoluto de um número
vectores: -Euclidiana:
 F   a b c  F e  a 2  b 2  c 2
 x   x1x 2 ... x n   x e 
n
x
i 1
2
i
-”uniform vector norm” (elemento de valor maior absoluto):
 x   x1x 2 ... x n   x   max x i
1 i  n
-norma de ordem p:
 x   x1 x 2 ... x n   x p 
n
p
x
i 1
p
i
16
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
n
matrizes: -Frobenius:
A
F

n
a
i 1 j 1
2
ij
-”uniform matrix norms”
-”row sum” (linha com maior somatório):
n
A

 max  a ij
1 i  n
j1
-”column sum”(coluna com maior somatório):
n
A 1  max  a ij
1 j n
i 1
17
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
Características de normas:
( i)
a ( n )
a 0
a 0
sse
( ii)
a ( n )
e  
a  
a
( iii)
a ( n )
e b (n)
a+b  a  b
( iv )
A ( n , n ) e B(n,n)
e
a=0
A*B p  A p * B
p
Resumindo a relação entre erro e resíduo de uma solução aprox.:
 R    A  x   A  x    c   A  x 
 e   A  1  R 
 A  e   R 
ou
então:
R
 e  A 1 R  A 1 R
A
18
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
R
 e  A 1 R  A 1 R
A
e
-erro relativo:
-resíduo relativo:
x
R
c
-combinando estas expressões, os limites superior e inferior do erro
relativo (desconhecido) em termos do resíduo relativo (conhecido)
podem ser escritos:
A 1
R
e


A x c
x
x
c
R
c
c
ou
1
A A 1
R
e
R
1

 A A
c
x
c
onde cond(A)=||A||*||A-1||
19
Sistemas lineares
Elementos de Análise Numérica
Análise dos erros e número de condição de matrizes
-se cond(a) é próx. de 1, então o erro relativo e o resíduo relativo têm
sempre grandezas semelhantes--------> o resíduo relativo pode ser
usado como uma estimativa do erro relativo
-quanto maior for cond(A) maior é a incerteza associada à solução
aproximada, e menos informação é obtida a partir do resíduo relativo
-é obvio que cond(A) depende da norma usada (sempre >1)
-erros de arredondamento (expressão alternativa):
e
E
 cond ( A )
x
A
 E    A   A
 
se os elementos de A têm t algar. sign. (Eij
aprox. 10-t) e cond(A)=10c ----> a solução
pode ser correcta ate t-c dígitos (erro de
arredondamento da ordem 10c-t)
20
Sistemas lineares
Elementos de Análise Numérica
Métodos de solução
2, Métodos iterativos:
-solução por processo iterativo (um número
infinito de operações)
-necessita de estimativas iniciais para cada
incógnita
-mais adequado que os métodos directos no
caso de sistemas muito grandes (n>100)
-vantagem que A nunca é alterada durante o
processo iterativo------> fácil “economizar” a
memória
-a presença de erros de arredondamento
origina um limite de melhoramento
-método de Jacobi
-método de Gauss-Seidel
21
Sistemas lineares
Elementos de Análise Numérica
Métodos iterativos
-métodos iterativos em forma geral:
[M]{x(k+1)}={c}+[N]{x(k)}
-comparando com a expressão para sistemas lineares: [A]*{x}={c}
[A]= [M]- [N]
-a forma particular de [M] e [N] depende de método utilizado
22
Sistemas lineares
Elementos de Análise Numérica
Método de Jacobi
[M]=[D]=diag[A]
e
[N]=[D]-[A]= -([L]+[U])
-onde [L] e [U] são matrizes triagonais (não iguais às matrizes resultantes
de decomp. LU!) com ai i=0.
-o algoritmo em termos de componentes:
n
ci   a ij x kj
x
k 1
i

j1
j i
a ii
n
ou x ik 1  x ik 
ci   a ij x kj
j1
a ii
23
Sistemas lineares
-exemplo
Elementos de Análise Numérica
 7 0.5  3  x1   7 
 2  8 1  x    5

 2   
0.7 1
9   x 3   4 
7  7 x1k  0.5x k2  3x 3k
x x 
7
 5  2x1k  8xk2  x 3k
k 1
k
x2  x2 
-8
4  0.7 x1k  x k2  9x 3k
k 1
k
x3  x3 
9
k 1
1
k
1
k=0
7  7(0)  0.5(0)  3(0)
1
7
 5  2(0)  8(0)  (0)
x12  0 
 0.625
-8
4  0.7(0)  (0)  9(0)
x13  0 
 0.4444
9
x11  0 
 (1.146 1)


0
.
127
 1.146



x 22  0.9531 e a  
0.344



 0.495
x 32  0.2972




3
 0.082
k=2 x1  1.059


3
e

0
.
076


x 2  1.031
a
 0.192


x 33  0.2494
k=1
k=3
x12  1.146
x14  1.033
x  1.019
4
2
x 34  0.2475
 0.025


e a   0.012
 0.008


24
Sistemas lineares
Elementos de Análise Numérica
Método de Gauss-Seidel
-semelhante ao método de Jacobi
-diferença: o novo valor de xi é utilizado logo na equação seguinte para
determinar xi+1 ou por outras palavras, a melhor estimativa disponível é
logo utilizada (em caso de convergência)
[M]=[L]+ [D] e [N]=[D]-[A]= - [U]
algoritmo:
i 1
xik 1 
ci   a ij x kj 1 
j1
a ii
n
a x
j i 1
ij
k
j
ou
xik 1  xik 
i 1
n
j1
j i
ci   a ij x kj 1   a ij x kj
a ii
25
Sistemas lineares
-exemplo
Elementos de Análise Numérica
 7 0.5  3  x1   7 
 2  8 1  x    5

 2   
0.7 1
9   x 3   4 
7  7 x1k  0.5x k2  3x 3k
x x 
7
 5  2x1k 1  8xk2  x 3k
k 1
k
x2  x2 
-8
4  0.7 x1k 1  x k2 1  9x 3k
k 1
k
x3  x3 
9
k 1
1
k
1
k=0
7  7(0)  0.5(0)  3(0)
1
7
 5  2 1  8(0)  (0)
x12  0 
 0.875
-8
4  0.7 1  0.875 9(0)
x13  0 
 0.2694
9
x11  0 
 (1.053 1)


0
.
05
 1.053



x 22  0.9976 e a  
0.123



 0.07
x 32  0.2517




3
 0.015
k=2 x1  1.037


3
e

0
.
011

  1%
x 2  1.009
a
 0 


x 33  0.2517
k=1
k=3
x12  1.053
x14  1.036
x  1.01
4
2
x 34  0.2517
 0.001


ea   0.001  1%
 0 


26
Sistemas lineares
Elementos de Análise Numérica
Convergência de métodos iterativos
-como para o caso de funções simples não há sempre convergência
-a partida semelhança com o método de IPF o critério de conv. pode ser
definido da seguinte forma:
n

i 1
fi
1
x j
n
ou
a ii   a ij
j1
j i
para j=1,2,...,n
-matrizes com esta característica são chamadas diagonalmente dominantes
-condição suficiente mas não necessária
27
Sistemas lineares
Elementos de Análise Numérica
Aceleração de convergência com relaxação
-modificação do processo no sentido de “antecipar” a evolução das
iterações:
xik 1  lxik 1  (1  l) xik
-l é o factor de relaxação e pode variar entre 0-2
-l=0-1, média pesada entre o novo e o valor presente (sub- relaxação),
para evitar oscilações na solução
- l=1-2 , mais peso para o novo valor , só para sistemas muito estáveis
(sobre-relaxação)
-o valor óptimo de l é determinada empiricamente (excepto casos muito
simples)
28
Sistemas lineares
Elementos de Análise Numérica
Sistemas com matrizes especiais
-modificação dos métodos com o objectivo de produzir um algoritmo
mais eficaz a partir da estrutura especial da matriz
-matriz esparsa: muitos coeficientes zeros (<---> matriz densa)
-matrizes em banda: algoritmo de Thomas
-matrizes simétricas: método de Cholesky
29
Sistemas lineares
Elementos de Análise Numérica
Matrizes em banda
HBW
0
- o seu armazenamento requer muito menos
espaço de memória do que no caso geral
-
o
número
de
operações
precisamos para resolver
que
BW
nós
0
o problema é
menor do que no caso geral
BW=2*HBW+1
aij= 0 onde |i-j|>HBW
30
Sistemas lineares
Elementos de Análise Numérica
Sistemas tridiagonais (BW=3 ou HBW=1)
-sistemas tridiagonais são resultado frequente de cálculo de “splines”
e da solução numérica de equações diferenciais 1D.
-exemplo:
-u´´(x)=f(x)
0<x<1
u i  1  2 * u i  u i 1
u ( x) 
h2
0
 2 -1 0
-1 2 -1
0


0
1  0 -1 2 -1


h2        
0 0
-1 2 -1


-1 2 
0 0
u(0)=u(1)=0
 u1   f1 
u  f 
 2  2 
 u 3   f3 
  
     
u n-1  f n-1 
   
 u n   fn 
31
Sistemas lineares
Elementos de Análise Numérica
Sistemas tridiagonais (BW=3 ou HBW=1)
-representação geral:
-algoritmo de Thomas(Gauss):
-eliminação:
d 1  d 1
c1  c1
para i = 2,..., n fazer:
 d 1 e1
a d
 2 2
 0 a3







0 d1 e1 

a d e 
e2

 2  2  2 

d 3 e3
a 3  d 3  e 3 
     
 

      
a n-1 d n-1 e n-1 
a n-1 d n-1 e n-1 

   
an dn 
 a n  d n  0 
-substituição
para trás:
ak
xn  cn / d´n
d k  d k 
e k 1
d k 1
para i = n - 1, n - 2...,1fazer :
a
ck  ek xk 1
c k  c k  k c k 1
x

d k 1
k
d k
-d´k e c´k são os coeficientes modificados
-o núm. de op e proporcional com n em vez de n3
32
no caso de algoritmo geral de Gauss
Sistemas lineares
Elementos de Análise Numérica
Matrizes simétricas
-matrizes simétricas: aij=aji
-desejável trabalhar só com um dos
triângulos, superior ou inferior, da
[A]nn*{x}n={c}n
matriz de coeficientes
decomposição
-o processo de eliminação produz
[L]T nn [L]nn
submatrizes também simétricas
-factorização de Choleski (adaptada
[L] nn* {d}n ={c}n
substituição para
frente
para o método LU): [A]=[L]*[L]T
[L]T nn *{x}n={d}n
substituição para
trás
{x}
33
Sistemas lineares
Elementos de Análise Numérica
Factorização de Choleski
-aplicando das regras de multiplicações de matrizes (para linha k):
n
i
j1
j1
a ki   ljil kj =  lijl kj
ki
-podemos chegar o algoritmo de Choleski:
i 1
l ki 
a ki   lijl kj
j1
para i = 1,2,...,k - 1 e k = 2,...,n
lii
e
k 1
l kk  a kk   l 2kj
j1
-só funciona se a expressão baixo de raiz quadrado é positivo (matrizes
definidas positivas)
34
-quase duas vezes mais rápido do que método geral
-pode ser mostrado que o método é numericamente estável sem pivotagem