Sistemas de
equações lineares
Métodos Directos
1
Análise Numérica - Resolução de Sistemas Métodos Directos
Decomposição LU

A=LU
L – matriz triangular inferior
U – matriz triangular superior
 Ly  b
U x  b  
Ax  b  L
Ux

y

y
Resolução de 1
sistema quadrado
2
Resolução de 2 sistemas
triangulares
Análise Numérica - Resolução de Sistemas Métodos Directos
Método de Gauss


Pivot – elemento da diagonal akk
Para anular os elementos abaixo da
diagonal aik
 Multiplicar (mantêm a.s.) a linha pivot
pelo factor
aik

akk

3
Adicionar (mantêm c.d.) a linha obtida à
linha i
Análise Numérica - Resolução de Sistemas Métodos Directos
Estabilidade do método

Solução aproximada de Ax=b
Que é solução exacta de


4
~
A  A
~
A  A
~
x
~~ ~
Ax b
Método estável (2º caso)
Método instável (1º caso)
Análise Numérica - Resolução de Sistemas Métodos Directos
Para o método ser estável

Escolha Total de pivot.
O maior elemento em valor absoluto
da matriz reduzida .
Desvantagens :

• Demora muito tempo a calcular o maior
elemento da matriz reduzida em cada
iteração.
• Troca de colunas  troca de variáveis.
• Não ganha muito em estabilidade quando
comparado com o 2ºcaso.
5
Análise Numérica - Resolução de Sistemas Métodos Directos
Para o método ser estável

Escolha parcial de pivot (2ºcaso).
 O maior elemento em valor absoluto
da 1ª coluna da matriz reduzida.
Vantagens :
• É rápido determinar o maior elemento em
valor absoluto da primeira coluna da matriz
reduzida.
• Não precisa de guardar a ordem das
variáveis.
Desvantagens :
• Nem sempre é estável.
6
Análise Numérica - Resolução de Sistemas Métodos Directos
Escolha parcial escalonada

O elemento a*ik , da 1ª coluna da matriz
reduzida, cuja razão absoluta entre a*ik e
o maior elemento, em valor absoluto, da
linha i de A é máxima.
*
a*sk
aik
 max
ds
i  k di
7
onde
di  max aij
Análise Numérica - Resolução de Sistemas Métodos Directos
1 j  n
Condição de um sistema

Num sistema mal condicionado uma
pequena variação nos dados pode
provocar uma grande alteração na
solução final
Sistema mal condicionado
8
Sistema bem condicionado
Análise Numérica - Resolução de Sistemas Métodos Directos
Como se mede a condição?

Se b é exacto:
x
A
 A  A1 
x

 A
cond  A k
Demonstração:
~~
1
Se A é não singular Ax  b  x  A b. E A x  b





~ ~ 1
~
~
1
~
~
 x  A  A x A  A A  A  x  x  A  A  A  ~
x
1
x~
x  A1  A  ~
x
e
9
 x~
x  A1  A  ~
x
x~
x
A
1
 A  A

~
x
A
Análise Numérica - Resolução de Sistemas Métodos Directos
Definição de norma

10
∥.∥:ℂnm→ℜ+0:

∥A∥=0 sse A=0

A  A
  C

A B  A  B

A B  A  B
Análise Numérica - Resolução de Sistemas Métodos Directos
Normas compatíveis
A  max A x
x 1
Vector
Matriz
x e  x 2   xi2
A 2   ( AH  A)
x 1   xi
i
A 1  max  aij
j
i
x   max xi
A   max  aij
i
i
Ae 
?
x
11
p

   xi
 i
p



i
1
p
Análise Numérica - Resolução de Sistemas Métodos Directos
j
2
 aij
ij
?
k – número de condição
k  cond( A)  A  A

1
1
Se b não é exacto
x

x
12
 A
b



A  A
b
1 k 
A
k
Análise Numérica - Resolução de Sistemas Métodos Directos




Métodos Iterativos
Ax  b  x  Cx  d
x ( 0)
x ( n1)  Cx ( n)  d
A=M–N
x    x
n
?
e M facilmente invertível
A x = b  (M – N) x = b  M x= N x + b  x=M –1 (N x + b)
C=M –1 N
13
d=M –1 b
Análise Numérica - Resolução de Sistemas Métodos Iterativos
Métodos Iterativos
Exemplo
 x1  2 x2  5 x3  9
 Resolva o sistema 
 x1  x2  3 x3  2
3 x  6 x  x  25
(solução exacta xT=(2,-3,-1))
2
3
 1
 2 x2  5 x3  9
 x1 

 3 x3  2
 x2  x1
 x  3x  6 x
 25
1
2
 3
14
Análise Numérica - Resolução de Sistemas Métodos Iterativos
Exemplo
(solução exacta xT=(2,-3,-1))
 x10    9 
 0 

x


2
 2 

0
 x3   25
 
 x1k  0  2  5  x1k 1    9 
 k 
   x k 1     2 
x

1
0
3
 2 
  2  

k
k

1
 x3  3  6 0   x3   25
 


x0
║xk-xk-1║
 2 x2  5 x3  9
 x1 

 3 x3  2
 x2  x1
 x  3x  6 x
 25
1
2
 3
x1
x2
x3
-9
120
363
-4260
-2
-86
-2
2914
-25
-40
851
1076
129
891
Processo divergente
15
Análise Numérica - Resolução de Sistemas Métodos Iterativos
4623
Teorema do ponto fixo

Para sistemas  (x) = M –1 (N x + b)
 = ║M-1N║
e 0 <  < 1 (  - constante de Lipschitz)

Cálculo do erro
x  x (k)   x  x (k 1)
xx
16
(k)


1
x
(k)
x
(k 1)
k

x (1)  x (0)
1 
Análise Numérica - Resolução de Sistemas Métodos Iterativos
Teoremas

Se existir uma norma para a qual
║C║= ║M-1N

║ <1
Condição
suficiente
então o processo é convergente.
O processo é convergente sse o raio
espectral de C
Condição
necessária e
(  (C)) <1
suficiente
(C )=maior valor próprio de C em módulo

17
Se (C )>1 o processo é divergente
Análise Numérica - Resolução de Sistemas Métodos Iterativos
Como obter boas fórmulas
de recorrência?

Os métodos mais comuns usam as submatrizes:
A  L  D U
0
 0
a
0
21

L
 


 an1 an 2




0
0



0
a11 0  0 
 0 a
 0 
22

D
 
   


a

0
0

nn 
0 a12
0 0
U 



0 0
18
 a1n 
 a2 n 

  

 0 
Análise Numérica - Resolução de Sistemas Métodos Iterativos
Método de Jacobi
M=D N=-(L+U)
 Condição suficiente de convergência
|| M-1N || = || D-1(L+U) || < 1
 Fórmula de recorrência

x(k )  C x(k 1)  d
C=-D-1(L+U)
d=D-1b
19
Resolver cada
equação i em
ordem a xi
Análise Numérica - Resolução de Sistemas Métodos Iterativos
Condições suficientes de
convergência
Definição

Uma matriz é estritamente diagonal dominante
por linhas (colunas) se
aii   aij
j i

 a jj   aij

i j

Matriz estritamente dominante
20
Análise Numérica - Resolução de Sistemas Métodos Iterativos




Jacobi convergente