aula10 sistemas

Prévia do material em texto

Ca´lculo Nume´rico
Resoluc¸a˜o de Sistemas de Equac¸o˜es Lineares
Heder S. Bernardino
Heder S. Bernardino Ca´lculo Nume´rico
Suma´rio
1 Aula Anterior
2 Eliminac¸a˜o de Gauss
3 Estrate´gias de Pivotamento
4 Decomposic¸a˜o LU
5 Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior – Alterac¸a˜o de Data de Avaliac¸o˜es
◮ Lab2a – 05/12 (quinta-feira)
◮ Lab2b – 09/12 (segunda-feira)
◮ TVC2 – 12/12 (quinta-feira)
◮ Excepcionalmente, pela alterac¸a˜o da data do TVC2 e pela dificuldade
em determinar uma nova data, aqueles que realizara˜o outra avaliac¸a˜o
no dia 12/12 podera˜o solicitar a segunda chamada do TVC2
◮ A segunda chamada sera´ realizada no dia 19/12 a`s 12h na sala 3501
◮ Neste caso, deve-se entregar ate´ o dia 29/11 uma requisic¸a˜o de
segunda chamada indicando a disciplina (com o co´digo) e o hora´rio da
avaliac¸a˜o que fara˜o no dia 12/12
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Introduc¸a˜o
◮ Alguns Conceitos de A´lgebra Linear
◮ Sistemas Lineares
◮ Classificac¸a˜o
◮ Existeˆncia e unicidade de soluc¸a˜o
◮ Me´todos Computacionais
◮ Me´todos Diretos
◮ Me´todos Iterativos
Heder S. Bernardino Ca´lculo Nume´rico
Aula Anterior
Aula Anterior
◮ Sistemas Triangulares
◮ Substituic¸o˜es Sucessivas
xi =
bi −
∑i−1
j=1 lijxj
lii
, i = 1, . . . , n
◮ Substituic¸o˜es Retroativas
xi =
bi −
∑n
j=i+1 uijxj
uii
, i = n, . . . , 1
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ O sistema e´ transformado em um sistema equivalente com a matriz
de coeficientes A sendo triangular superior
◮ Operac¸o˜es elementares sa˜o utilizadas para zerar os elementos abaixo da
diagonal principal da matriz de coeficientes A
◮ Ilustrac¸a˜o do procedimento:


a a a a b
a a a a b
a a a a b
a a a a b

 ⇒


a a a a b
0 a a a b
0 a a a b
0 a a a b

 ⇒


a a a a b
0 a a a b
0 0 a a b
0 0 a a b

 ⇒


a a a a b
0 a a a b
0 0 a a b
0 0 0 a b


◮ Finalmente, o sistema resultante pode ser resolvido por meio de
substituic¸o˜es retroativas
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Definic¸a˜o (Sistema Equivalente):
Dois sistemas de equac¸o˜es lineares Ax = b e Aˆx = bˆ sa˜o
equivalentes quando possuem a mesma soluc¸a˜o x∗.
◮ Teorema:
Seja Ax = b um sistema linear. Um sistema Aˆx = bˆ equivalente
pode ser obtido aplicando as seguintes operac¸o˜es elementares:
◮ trocar a ordem de duas equac¸o˜es
◮ multiplicar uma equac¸a˜o por uma constante na˜o nula
◮ somar uma equac¸a˜o com um mu´ltiplo de outra
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Por exemplo {
x1 + x2 = 2
x1 − x2 = 0
0.0 0.5 1.0 1.5 2.0 2.5 3.0
x
1
−1.0
−0.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
x
2
x
1
+x
2
=2
x
1
−x
2
=0
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Fazendo L′2 = L2 − L1, obte´m-se o seguinte sistema equivalente{
x1 + x2 = 2
−2x2 = −2
0.0 0.5 1.0 1.5 2.0 2.5 3.0
x
1
−1.0
−0.5
0.0
0.5
1.0
1.5
2.0
2.5
3.0
x
2
x
1
+x
2
=2
−2x
2
=−2
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Seja o sistema Ax = b representado por uma matriz estendida na
forma 

a11 a12 a13 . . . a1n b1
a21 a22 a23 . . . a2n b2
a31 a32 a33 . . . a3n b3
...
...
...
. . .
...
...
an1 an2 an3 . . . ann bn


◮ Os passos que seguem podem ser realizados para obter um sistema
linear equivalente com a matriz de coeficientes triangular superior
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Passo 1 (k=1): os elementos abaixo da diagonal principal na
primeira coluna sa˜o eliminados fazendo
m21 =
a21
a11
(supo˜em-se que a11 6= 0)
m31 =
a31
a11
...
mn1 =
an1
a11
,
◮ ou seja,
mi1 =
ai1
a11
; i = 2, . . . , n
◮ O elemento utilizado nos denominadores e´ chamado de pivoˆ
◮ a11, neste caso
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Em seguida faz-se
L
(1)
i = L
(0)
i −mi1L
(0)
1 ; L
(k)
i e´ a linha i no passo k
◮ ou seja,
a
(1)
ij = a
(0)
ij −mi1a
(0)
1j ; j = 1, . . . , n
b
(1)
i = b
(0)
i −mi1b
(0)
1
◮ Assim, apo´s a primeira etapa tem-se

a
(0)
11 a
(0)
12 a
(0)
13 . . . a
(0)
1n b
(0)
1
0 a
(1)
22 a
(1)
23 . . . a
(1)
2n b
(1)
2
0 a
(1)
32 a
(1)
33 . . . a
(1)
3n b
(1)
3
...
...
...
. . . . . .
...
0 a
(1)
n2 a
(1)
n3 . . . a
(1)
nn b
(1)
n


Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Passo 2 (k=2): os elementos abaixo da diagonal principal na coluna
2 sa˜o eliminados fazendo
mi2 =
ai2
a22
; i = 3, . . . , n e assumindo a22 6= 0
◮ Em seguida faz-se
L
(2)
i = L
(1)
i −mi2L
(1)
2
◮ ou seja,
a
(2)
ij = a
(1)
ij −mi2a
(1)
2j ; j = 2, . . . , n
b
(2)
i = b
(1)
i −mi2b
(1)
2
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Assim, apo´s a segunda etapa tem-se

a
(0)
11 a
(0)
12 a
(0)
13 . . . a
(0)
1n b
(0)
1
0 a
(1)
22 a
(1)
23 . . . a
(1)
2n b
(1)
2
0 0 a
(2)
33 . . . a
(2)
3n b
(2)
3
...
...
...
. . . . . .
...
0 0 a
(2)
n3 . . . a
(2)
nn b
(2)
n


◮ O procedimento e´ enta˜o repetido ate´ o passo n− 1
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
◮ Passo k (k=1, . . . , n-1):
mik =
aik
akk
; i = k + 1, . . . , n e supondo akk 6= 0
◮ Em seguida faz-se
L
(k)
i = L
(k−1)
i −mikL
(k−1)
k
◮ ou seja,
a
(k)
ij = a
(k−1)
ij −mika
(k−1)
kj ; j = k, . . . , n
b
(k)
i = b
(k−1)
i −mikb
(k−1)
k
◮ Nota-se que as linhas 1, . . . , k na˜o sa˜o alteradas
◮ Por fim, aplica-se o me´todo de substituic¸o˜es retroativas ao sistema
equivalente
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss
Entrada: Matriz A, vetor b, n
1 inicio
2 para k = 1, . . . , n− 1 fac¸a /* Para cada passo */
3 para i = k + 1, . . . , n fac¸a /* Linhas abaixo da k-e´sima */
4 m←− A[i][k]/A[k][k] ;
5 para j = k, . . . , n fac¸a /* Colunas */
6 A[i][j]←− A[i][j]−m ∗A[k][j] ;
7 b[i]←− b[i]−m ∗ b[k] ;
8 x←− retroSubstituicao(A,b, n) ; /* Resolve o sistema */
9 retorna x
Algoritmo 1: Eliminac¸a˜o de Gauss - Complexidade O(n3)
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Exemplo
◮ Exemplo 1
Resolva o sistema linear que segue utilizando o Me´todo de Eliminac¸a˜o
de Gauss. 
1 0 11 1 0
2 3 1



x1x2
x3

 =

01
1


◮ Soluc¸a˜o:
x =

 10
−1


Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss – Exemplo em Python
1 from pylab import *
2
3 def gauss(A,b):
4 n = b.shape[ 0 ]
5 # Etapa de eliminacao
6 for k in range(0,n-1):
7 for i in range(k+1,n):
8 if A[i,k] != 0.0:
9 m = A[i,k]/A[k,k]
10 for j in range(k,n):
11 A[i,j] = A[i, j] - m * A[k,j]
12 b[i] = b[i] - m * b[k]
13
14 # Resolve o sistema triangular (funcao deve ser definida)
15 x = substituicoesRetroativas(A, b )
16 return x
Heder S. Bernardino Ca´lculo Nume´rico
Eliminac¸a˜o de Gauss
Eliminac¸a˜o de Gauss – Exemplo em Python – cont.
1 # inicializa o vetor de coeficientes A
2 A = np.matrix([[ 1, 0, 1 ],
3 [ 1, 1, 0 ],
4 [ 2, 3, 1 ]])
5
6 # inicializa o vetor b
7 b = np.matrix( [ [0.0], [1.0], [1.0] ] )
8
9 #Resolve o sistema
10 x = gauss( A, b )
11
12 print( x )
Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Estrate´gias de Pivotamento
Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Estrate´gias de Pivotamento
◮ O Me´todo de Eliminac¸a˜o de Gauss requer o calculo de mik =
aik
akk
◮ O pivoˆ akk pode ser escolhido adequadamente
◮ Estrate´gias de pivotamento ajudam a evitar
◮ que o pivoˆ seja nulo
◮ a propagac¸a˜o de erros nume´ricos
◮ se akk for um nu´mero muito pequeno (em mo´dulo), o multiplicador
mik pode ficar muito grande, ampliando erros de arredondamento ao
multiplicar mik ou gerando erros ao subtrair/somar nu´meros pequenos
de grandes
◮ O pivotamento garante que |mik| ≤ 1
◮ Existem duas formas de pivotamento
◮ Pivotamento Parcial
◮ Pivotamento Total
Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Pivotamento Parcial
◮ No in´ıcio de cada passo k
procura-se r tal que |ark| = max
i∈[k,n]
|aik|
◮ Em seguida, as linhas k e r sa˜o trocadas e o algoritmo continua
◮ Ou seja, o pivoˆ e´ escolhido de modo que seja o elemento de maior
valor absoluto na coluna k
◮ considerando as linhas (i ≥ k) que ainda podem ser operadas
◮ Nota-se que se houver apenas candidatos a pivoˆ nulos enta˜o
◮ det(U) = 0⇒ U e´ singular ⇒ A e´ singular
U =

a a a0 0 a
0 0 a


Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Exemplo
◮ Exemplo 2
O sistema linear que segue na˜o pode ser resolvido utilizando o
Me´todo de Eliminac¸a˜o de Gauss sem Pivotamento (verifique).
Resolva esse sistema linear via o Me´todo de Eliminac¸a˜o de Gauss com
Pivotamento Parcial.
2 2 −13 3 1
1 −1 5



x1x2
x3

 =

37
5


◮ Soluc¸a˜o:
x =

11
1


Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Exemplo
◮ Exemplo 3
As operac¸o˜es aritme´ticas devem ser realizadas numa ma´quina
F (10, 3,−10, 10) com arredondamento e com representac¸a˜o para o
zero. Ao resolver o sistema linear que segue utilizando o Me´todo de
Eliminac¸a˜o de Gauss sem Pivotamento obte´m-se xT = [0 2,5]
(verifique). Entretanto, essa soluc¸a˜o e´ inva´lida. Resolva o sistema
usando o Me´todo de Eliminac¸a˜o de Gauss com Pivotamento Parcial.[
0,0002 2
2 2
] [
x1
x2
]
=
[
5
6
]
◮ Soluc¸a˜o:
x =
[
0,5
2,5
]
Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Pivotamento Total
◮ O pivoˆ e´ o maior elemento (em mo´dulo) entre os que ainda atuam no
processo de eliminac¸a˜o
◮ No in´ıcio de cada passo k
procura-se a linha r e a coluna s tal que |ars| = max
i∈[k,n],j∈[k,n]
|aij |
◮ Em seguida, as linhas k e r, e as colunas k e s sa˜o trocadas e o
algoritmo continua
◮ Observac¸o˜es
◮ a troca das colunas afeta a ordem das varia´veis
◮ o pivotamento total na˜o e´ muito adotado por causa do alto esforc¸o
computacional requerido na busca pelo pivoˆ
◮ o pivotamento parcial e´ geralmente satisfato´rio
Heder S. Bernardino Ca´lculo Nume´rico
Estrate´gias de Pivotamento
Estrate´gias de Pivotamento
Pivotamento Parcial Pivotamento Total
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Uma matriz quadrada A pode ser decomposta como
A = LU
onde
◮ L e´ uma matriz triangular inferior com diagonal principal unita´ria
◮ U e´ uma matriz triangular superior
◮ Assim,
Ax = b⇒ LUx = b
◮ Definindo Ux = y, enta˜o pode-se resolver
Ly = b (por substituic¸o˜es sucessivas)
◮ e depois
Ux = y (por substituic¸o˜es retroativas)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Teorema (LU):
Sejam A uma matriz quadrada de ordem n e Ak o menor principal,
constitu´ıdo das k primeiras linhas e k primeiras colunas de A. Sendo
det(Ak) 6= 0 para k = 1, . . . , n− 1, enta˜o existe
◮ uma u´nica matriz triangular inferior L com elementos da diagonal
principal iguais a 1
◮ uma u´nica matriz triangular superior U
tal que A = LU.
◮ Ale´m disso, det(A) = u11u22 . . . unn
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Demonstrac¸a˜o (por induc¸a˜o):
◮ Para n = 1 tem-se que
a11 = 1 a11 = 1 u11 ⇒ u11 = a11 e l11 = 1
◮ Ale´m disso, det(A) = u11
◮ Assumindo que o teorema e´ va´lido para n = k − 1, ou seja,
Ak−1 = Lk−1Uk−1
◮ Sera´ mostrado que A pode ser decomposta em LU para n = k
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Demonstrac¸a˜o
◮ Seja A uma matriz de ordem k e escrita na forma
A =
[
Ak−1 r
s akk
]
◮ Pela hipo´tese de induc¸a˜o
Ak−1 = Lk−1Uk−1
◮ Fazendo
LU =
[
Lk−1 0
m 1
] [
Uk−1 p
0 ukk
]
=
[
Lk−1Uk−1 Lk−1p
mUk−1 mp+ ukk
]
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Demonstrac¸a˜o
◮ Ao igualar A com LU, obte´m-se
A =
[
Ak−1 r
s akk
]
=
[
Lk−1Uk−1 Lk−1p
mUk−1 mp+ ukk
]
◮ Assim,
Ak−1 = Lk−1Uk−1
r = Lk−1p
s = mUk−1
akk = mp+ ukk
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Demonstrac¸a˜o
◮ Sendo Lk−1 e Uk−1
◮ unicamente determinadas (pela hipo´tese de induc¸a˜o)
◮ na˜o singulares (Ak−1 e´ na˜o singular)
enta˜o
r = Lk−1p ⇒ p = L
−1
k−1r
s = mUk−1 ⇒ m = sU
−1
k−1
akk = mp+ ukk ⇒ ukk = akk −mp
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Demonstrac¸a˜o
◮ Assim, p, m e ukk podem ser unicamente determinados e,
consequentemente, L e U sa˜o unicamente determinados
◮ Ale´m disso,
det(A) = det(LU) = det(L) det(U) = 1 det(U) = u11u22 . . . unn
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Obtenc¸a˜o das Matrizes L e U
◮ As matrizes L e U podem ser obtidas pela definic¸a˜o de produto e
igualdade de matrizes


a11 a12 a13 . . . a1n
a21 a22 a23 . . . a2n
a31 a32 a33 . . . a3n
...
...
...
. . .
...
an1 an2 an3 . . . ann


=


1 0 0 . . . 0
l21 1 0 . . . 0
l31 l32 1 . . . 0
...
...
...
. . .
...
ln1 ln2 ln3 . . . 1




u11 u12 u13 . . . u1n
0 u22 u23 . . . u2n
0 0 u33 . . . u3n
...
...
...
. . .
...
0 0 0 . . . unn


◮ As matrizes podem enta˜o ser obtidas na ordem:
◮ 1a linha de U
◮ 1a coluna de L
◮ 2a linha de U
◮ 2a coluna de L
◮
...
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Obtenc¸a˜o das Matrizes L e U
◮ 1a linha de U
a11 = 1u11 ⇒ u11 = a11
a12 = 1u12 ⇒ u12 = a12
...
a1n = 1u1n ⇒ u1n = a1n
◮ 1a coluna de L
a21 = l21u11 ⇒ l21 =
a21
u11
a31 = l31u11 ⇒ l31 =
a31
u11
...
an1 = ln1u11 ⇒ ln1 =
an1
u11
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Obtenc¸a˜o das Matrizes L e U
◮ 2a linha de U
a22 = l21u12 + 1u22 ⇒ u22 = a22 − l21u12
a23 = l21u13 + 1u23 ⇒ u23 = a23 − l21u13
...
a2n = l21u1n + 1u2n ⇒ u2n = a2n − l21u1n
◮ 2a coluna de L
a32 = l31u12 + l32u22 ⇒ l32 =
a32 − l31u12
u22
a42 = l41u12 + l42u22 ⇒ l42 =
a42 − l41u12
u22
...
an2 = ln1u12 + ln2u22 ⇒ ln2 =
an2 − ln1u12
u22
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜oLU – Obtenc¸a˜o das Matrizes L e U
◮ De forma geral, tem-se que
uij = aij −
i−1∑
k=1
likukj ; i ≤ j
lij =
aij −
j−1∑
k=1
likukj
ujj
; i > j
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
Entrada: Matriz A, n
1 inicio
2 para i = 1, . . . , n fac¸a
3 para j = i, . . . , n fac¸a
4 uij ←− aij −
i−1∑
k=1
likukj ;
5 para j = i+ 1, . . . , n fac¸a
6 lij ←−
aij−
j−1∑
k=1
likukj
ujj
;
Algoritmo 2: Decomposic¸a˜o LU - Complexidade O(n3)
◮ Na pra´tica, L e U podem ser armazenadas sobre a matriz A
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Via Eliminac¸a˜o de Gauss
◮ A Eliminac¸a˜o de Gauss pode ser utilizada para decompor A nas
matrizes L e U
◮ Seja
M1 =


1 0 0 . . . 0
−m21 1 0 . . . 0
−m31 0 1 . . . 0
...
...
...
. . .
...
−mn1 0 0 . . . 1


onde mij os multiplicadores gerados durante a eliminac¸a˜o de Gauss
◮ O primeiro passo da Eliminac¸a˜o de Gauss e´ equivalente a multiplicar
(A|b)(0) por M1
◮ Obte´m-se assim (A|b)(1)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Via Eliminac¸a˜o de Gauss
◮ Ou seja
M1 (A|b)
(0) =


1 0 0 . . . 0
−m21 1 0 . . . 0
−m31 0 1 . . . 0
...
...
...
. . .
...
−mn1 0 0 . . . 1




a11 a12 a13 . . . a1n b1
a21 a22 a23 . . . a2n b2
a31 a32 a33 . . . a3n b3
...
...
...
. . .
...
...
an1 an2 an3 . . . ann bn


=


a
(0)
11 a
(0)
12 a
(0)
13 . . . a
(0)
1n b
(0)
1
0 a
(1)
22 a
(1)
23 . . . a
(1)
2n b
(1)
2
0 a
(1)
32 a
(1)
33 . . . a
(1)
3n b
(1)
3
...
...
...
. . . . . .
...
0 a
(1)
n2 a
(1)
n3 . . . a
(1)
nn b
(1)
n


= (A|b)(1)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Via Eliminac¸a˜o de Gauss
◮ No passo seguinte, tem-se que
M2 (A|b)
(1) =


1 0 0 . . . 0
0 1 0 . . . 0
0 −m32 1 . . . 0
...
...
...
. . .
...
0 −mn2 0 . . . 1




a
(0)
11 a
(0)
12 a
(0)
13 . . . a
(0)
1n b
(0)
1
0 a
(1)
22 a
(1)
23 . . . a
(1)
2n b
(1)
2
0 a
(1)
32 a
(1)
33 . . . a
(1)
3n b
(1)
3
...
...
...
. . . . . .
...
0 a
(1)
n2 a
(1)
n3 . . . a
(1)
nn b
(1)
n


=


a
(0)
11 a
(0)
12 a
(0)
13 . . . a
(0)
1n b
(0)
1
0 a
(1)
22 a
(1)
23 . . . a
(1)
2n b
(1)
2
0 0 a
(2)
33 . . . a
(2)
3n b
(2)
3
...
...
...
. . . . . .
...
0 0 a
(2)
n3 . . . a
(2)
nn b
(2)
n


= (A|b)(2)
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Via Eliminac¸a˜o de Gauss
◮ Ao fim do processo obte´m-se (A|b)(n−1), de modo que
(A|b)(n−1) = Mn−1 (A|b)
(n−2)
= · · · = Mn−1Mn−2 . . .M2M1︸ ︷︷ ︸
M
(A|b)(0)
◮ Portanto, tem-se que
MA = (A)(n−1) = U
onde U e´ a matriz triangular superior da decomposic¸a˜o LU
◮ Sendo M e´ um produto de matrizes na˜o singulares, enta˜o M e´ na˜o
singular
◮ Logo, M e´ invers´ıvel
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Via Eliminac¸a˜o de Gauss
◮ Assim,
MA = U⇒ A = M−1︸ ︷︷ ︸
L
U
onde
M−1 = L =


1 0 0 . . . 0
m21 1 0 . . . 0
m31 m32 1 . . . 0
...
...
...
. . .
...
mn1 mn2 mn3 . . . 1


◮ Logo, as matrizes L e U podem ser obtidas aplicando a Eliminac¸a˜o
de Gauss sobre a matriz A
◮ U e´ a matriz triangular superior resultante
◮ L e´ a matriz triangular inferior formada pelos multiplicadores mij e
com diagonal principal unita´ria
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU
◮ Nota-se que
◮ A decomposic¸a˜o e´ realizada com complexidade O(n3)
◮ Os sistemas lineares com matrizes de coeficientes triangulares podem
ser resolvidos com complexidade O(n2)
◮ A vantagem da Decomposic¸a˜o LU e´ que a matriz A somente precisa
ser decomposta uma vez para resolver diversos sistemas na forma
Ax = b1
Ax = b2
...
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Exemplo
◮ Exemplo 4
Decomponha a matriz de coeficientes que segue em matrizes L e U
usando a Eliminac¸a˜o de Gauss.
A =


2 1 1 0
4 3 3 1
8 7 9 5
6 7 9 8


◮ Soluc¸a˜o:
L =


1 0 0 0
2 1 0 0
4 3 1 0
3 4 1 1

 e U =


2 1 1 0
0 1 1 1
0 0 2 2
0 0 0 2


Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Exemplo
◮ Exemplo 5
Resolva o sistema linear que segue utilizando a Decomposic¸a˜o LU e
calcule o determinante da matriz de coeficientes utilizando a
decomposic¸a˜o. 
1 2 −12 3 −2
1 −2 1



x1x2
x3

 =

23
0


◮ Soluc¸a˜o:
L =

1 0 02 1 0
1 4 1

 , U =

1 2 −10 −1 0
0 0 2

 , x =

11
1

 e
det(A) = u11u22u33 = −2
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Exemplo em Python
1 from pylab import *
2
3 def lu(A):
4 n = A.shape[ 0 ]
5 for k in range(0,n-1):
6 for i in range(k+1,n):
7 if A[i,k] != 0.0:
8 m = A[i,k]/A[k,k]
9 A[i,k] = m
10 for j in range(k+1,n):
11 A[i,j] = A[i, j] - m * A[k,j]
12 return x
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Exemplo em Python – cont.
1 def substituicoesSucessivasDiagonalUnitaria(A, b):
2 n = len(b)
3 x = zeros(n)
4 for i in range(n):
5 soma = 0
6 for j in range(i):
7 soma += A[i,j] * x[j]
8 x[i] = b[i] - soma
9 return np.matrix(x).transpose()
Heder S. Bernardino Ca´lculo Nume´rico
Decomposic¸a˜o LU
Decomposic¸a˜o LU – Exemplo em Python – cont.
1 #inicializa a matriz A
2 A = np.matrix([[ 1, 2, -1 ],
3 [ 2, 3, -2 ],
4 [ 1, -2, 1 ]])
5
6 # inicializa o vetor b
7 b = np.matrix( [ [2.0], [3.0], [0.0] ] )
8
9 #Decomposicao LU
10 lu( A )
11
12 #Resolve o sistema Ly=b
13 y = substituicoesSucessivasDiagonalUnitaria( A, b )
14
15 #Resolve o sistema Ux=y
16 x = substituicoesRetroativas( A, y )
17
18 print( x )
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Eliminac¸a˜o de Gauss
◮ Transforma o sistema linear num sistema equivalente com matriz de
coeficientes triangular superior
◮ Resolve o sistema equivalente utilizando substituic¸o˜es retroativas
◮ Eliminac¸a˜o de Gauss com estrate´gias de pivotamento
◮ Evita que o pivoˆ seja nulo e evita efeitos nume´ricos
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Revisa˜o
◮ Decomposic¸a˜o LU
◮ A matriz de coeficientes e´ decomposta em L e U
◮ L e´ uma matriz triangular inferior com elementos da diagonal principal
unita´rios
◮ U e´ uma matriz triangular superior
◮ Substituindo A por LU enta˜o a soluc¸a˜o pode ser obtida resolvendo
dois sistemas triangulares
◮ Ly = b
◮ Ux = y
◮ A decomposic¸a˜o na˜o envolve o vetor b
Heder S. Bernardino Ca´lculo Nume´rico
Revisa˜o
Du´vidas?
Heder S. Bernardino Ca´lculo Nume´rico
	Aula Anterior
	Eliminação de Gauss
	Estratégias de Pivotamento
	Decomposição LU
	Revisão