JULIOSYSTEM_ONE

Prévia do material em texto

1
Cálculo NuméricoCálculo Numérico
Resolução Numérica de
Sistemas Lineares – Parte I
Profº.: Doutor JÚLIO CÉSAR 
Mestre in “Civil Engineering”
Doctor in “Civil Engineering”
Researcher: “Computational and Numerical 
Methods for Engineering”
Numerical Methods: Finte Elemet Method 
and Boundary Element Method
UFRB January 2012
Sistemas Lineares
� Forma Geral
2nn2222121
1nn1212111
bxa...xaxa
bxa...xaxa
====++++++++++++
====++++++++++++
2
onde:
aaijij ���� coeficientes
xxii ���� incógnitas
bbii ���� termos independentes
nnnn22n11n bxa...xaxa ====++++++++++++
MMOMM
� Exemplo 01
Sistemas Lineares
2x5x1x4
5x5x4x2
321
321
====−−−−++++
====−−−−++++
3
2, 4, -5, 4, 1, -5, 2, 4 e 5 ���� coeficientes
x1, x2 e x3 ���� incógnitas
5, 2 e -1 ���� termos independentes
1x5x4x2 321 −−−−====++++++++
Sistemas Lineares
� Forma Matricial
na qual:
AxAx = b= bAxAx = b= b
4
na qual:
4
















====
nn3n2n1n
n22221
n112
aaaa
aaa
aaa
A
11
MOMM
K
K










====
n
2
1
b
b
b
b
M 









====
n
2
1
x
x
x
x
M
� Onde:
�
�
Sistemas Lineares








====
n22221
n112
aaa
aaa
A
11
K
K
�
�
� Matriz dos Coeficientes
5









====
nn3n2n1n aaaa
A
MOMM
� Onde:
� Vetor das variáveis
Sistemas Lineares








==== 2
1
x
x
x
x
M
�
� Vetor termos independentes
6










====
n
2
1
b
b
b
b
M



 nx
M
Sistemas Lineares
2x5x1x4
5x5x4x2
321
321
====−−−−++++
====−−−−++++
� Exemplo 02
�Forma Geral
7
1x5x4x2
2x5x1x4
321
321
−−−−====++++++++
====−−−−++++
7
�Forma Matricial








−−−−
====
















−−−−
−−−−
1
2
5
x
x
x
.
542
514
542
3
2
1
Sistemas Lineares
� Classificação I
��PossívelPossível���� Possui 1 ou mais soluções
�� DeterminadoDeterminado ���� Solução únicaúnica
Exemplo 03
8
� Exemplo 03
� Graficamente estas 02 equações
representam 02 retas concorrentes





−−−−====−−−−
====
====++++
23
)11(
32
21
*
21
xx
xcom
xx
T
� Classificação II
��PossívelPossível���� Possui 1 ou mais soluções
�� IndeterminadoIndeterminado ���� InfinitasInfinitas soluções
Exemplo 04
Sistemas Lineares
9
� Exemplo 04
� Graficamente estas 02 equações
representam 02 retas coincidentes




====++++
====++++
624
32
21
21
xx
xx (((( ))))αααααααα 23,* −−−−====x
Sistemas Lineares – Nr. Solução
� Classificação III
��ImpossívelImpossível���� NenhumaNenhuma solução
� Exemplo 05
10
� Estas 02 equações representam 02 retas
paralelas
10




====++++
====++++
224
32
21
21
xx
xx
Métodos Numéricos
�� DiretosDiretos
�Fornecem a Solução Exata, a menos
erros de arredondamento, caso ela
exista, após um número finito de
11
exista, após um número finito de
operações
�� MétodoMétodo dada EliminaçãoEliminação dede GaussGauss
�� FatoraçãoFatoração LULU
�� FatoraçãoFatoração dede CholeskyCholesky
Métodos Numéricos
�� MétodosMétodos IterativosIterativos
Geram uma seqüência de vetores ,
a partir de uma aproximação inicial ,
que converge para solução , caso ela
{ })(kx
*x
)0(x
12
que converge para solução , caso ela
exista.
�� MétodoMétodo dede GaussGauss -- JacobiJacobi
�� MétodoMétodo dede GaussGauss –– SeidelSeidel
*x
Método da Eliminação de Gauss
� OBJETIVO:
�Transformar o sistema linear original
num sistemasistema linearlinear equivalenteequivalente comcom
matrizmatriz dosdos coeficientescoeficientes triangulartriangular
13
matrizmatriz dosdos coeficientescoeficientes triangulartriangular
superiorsuperior; pois estes são de resolução
imediata
�A Resolução do Sistema Linear
Triangular Superior se dá de forma
retroativaretroativa.
� Resolução de sistemas Lineares
Triangulares: A x = b; A: n x n; akk ≠≠≠≠ 0
Método da Eliminação de Gauss
nn bxaxaxaxa ====++++++++++++++++ K 11313212111
14
nnnn
nn
nn
nn
bxa
bxaxa
bxaxaxa
bxaxaxaxa
====
====++++++++
====++++++++++++
====++++++++++++++++
MO
K
K
K
33333
22323222
11313212111
Resolução de sistemas Lineares
Triangulares Superiores
� Da última equação:
xab
a
b
x
nn
n
n
−−−−
====
15
11
13132121
1
1,1
,11
1
...
a
xaxaxab
x
a
xab
x
nn
nn
nnnn
n
−−−−−−−−−−−−−−−−
====
−−−−
====
−−−−
−−−−
−−−−−−−−
−−−−
M
� Algoritmo 1:
1) Dados de Entrada: A: n x n; akk≠≠≠≠0
2) xn= bn/ ann
Resolução de sistemas Lineares
Triangulares Superiores
3) Para k = (n-1),...,1
4) s = 0
5) Para j = (k+1),...,n
6) s = s + akjxj
7) xk=(bk - s)/ akk
�
16
Descrição do Método da
Eliminação de Gauss
Teorema 1: Seja um sistema linear.
Aplicando sobre as equações deste uma
seqüência de operações elementares
escolhidas entre:
bAx=
escolhidas entre:
a) trocar a ordem das equações,
b) multiplicar uma equação por constante,
c) adicionar um mútiplo de uma equação a
outra;
obtemos um novo sistema equivalente.
17
bxA ~~ =
� O Método da Eliminação de Gauss usa
este Teorema para Triangularizar a matriz
A. Vamos Supor que det.(A)≠≠≠≠0.
� A Eliminação é feita por Colunas.
Descrição do Método da
Eliminação de Gauss
� Chamamos de etapa k do processo a fase
em que se elimina xk das equações
i=(k+1),(k+2),...,n.
� Como det.(A)≠≠≠≠0 é sempre possível
reescrever o sistema de forma que a11 ≠≠≠≠0.
18
Método de Gauss
� Passos do Método de Gauss
�Construção da matriz aumentada A/bA/b
 )0()0()0()0(
1919
[[[[ ]]]]














====
)0()0()0(
2
)0(
2
)0(
1
)0(
2
)0(
2
)0(
22
)0(
21
)0(
1
)0(
1
)0(
12
)0(
11
)0()0( /
nnnnnn
n
n
baaaa
baaa
baaa
bA
MMOMM
K
K
� Etapa 1:
� Eliminar x1 das equações i=2,...,n.
� Da equação i subtraimos a 1ª equação
Método de Gauss
� Da equação i subtraimos a 1ª equação
multiplicada por mi1.
� A Linha i, Li , é substituída por:
a11 é denominado pivô da Etapa 1
20
ni
a
a
mqualnaLmL iiii ,...,2:, )0(
11
)0(
111
1
========⋅⋅⋅⋅−−−−
� Ao final da etapa 1 teremos a Matriz
�
Método de Gauss



 )1(1
)1(
1
)1(
12
)1(
11 n baaa K
21
[[[[ ]]]]











====
)1()1()1(
3
)1(
2
)1(
1
)1(
2
)1(
22
111211
)1()1(
0
0/
nnnnn
n
n
baaa
baabA
MMOMM
K
� Etapa 2:
� Eliminar x2 das equações i=3,...,n.
� Da equação i subtraimos a 2ª equação
Método de Gauss
� Da equação i subtraimos a 2ª equação
multiplicada por mi2.
� A Linha i, Li , é substituída por:
a22 é denominado pivô da Etapa 2
22
ni
a
a
mqualnaLmLiiii ,...,3:, )1(
22
)1(
2
222 ========⋅⋅⋅⋅−−−−
� Ao final da etapa 2 teremos a Matriz
�
Método de Gauss






)2(
2
)2(
2
)2(
23
)2(
22
)2(
1
)2(
1
)2(
13
)2(
12
)2(
11
0 n
n
baaa
baaaa
KK
KK
23
[[[[ ]]]]















====
)2()2()2(
3
)2(
3
)2(
3
)2(
33
222322
)2()2(
00
00/
nnnn
n
n
baa
baabA
KK
MMKKMMM
MMKKMMM
KK
� Caso algum elemento app=0, achar outra
linha k onde akp≠ 0 e trocar tais linhas. Caso
a linha k não exista, o sistema linear não
possui solução.
Método de Gauss
� E assim procede-se até a etapa (n-1) e a
Matriz ao final desta etapa, será:
24
� Matriz A(n-1)/b(n-1)
Método de Gauss








−−−−−−−−−−−−
−−−−−−−−−−−−−−−−
−−−−−−−−−−−−−−−−−−−−
)1()1()1(
)1(
2
)1(
2
)1(
23
)1(
22
)1(
1
)1(
1
)1(
13
)1(
12
)1(
11
00
0
nnn
nn
n
nn
nn
n
nnn
baa
baaa
baaaa
K
K
K
� O Sistema Linear A(n-1)x = b(n-1) é triangular
superior e equivalente ao sistema original
25












====
−−−−−−−−
−−−−−−−−−−−−
−−−−−−−−
)1()1(
)1(
3
)1(
3
)1(
33)1()1(
000
00/
n
n
n
nn
nn
n
n
nn
ba
baabA
K
M
M
M
M
M
M
M
M
K
Método de Gauss
� Exemplo 6:
�Resolver o sistema:



====++++++++
====++++++++
22
1423 321
xxx
xxx
26
� Matriz aumentada A/b
[[[[ ]]]]










−−−−
====
3234
2211
1423
/ bA




====−−−−++++
====++++++++
3234
22
321
321
xxx
xxx
Método de Gauss
� Exemplo 6: Etapa 1 pivô = a11 = 3
�Faz-se:
1
,
21
2112122 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
27
�Assim:
3
,
11
2112122 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]3/53/23/10
14233/12211
2
2
====
⋅⋅⋅⋅−−−−←←←←
L
L
Método de Gauss
� Exemplo 6: Etapa 1: pivô = a11 = 3
�Faz-se:
4
,
31
3113133 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
28
�Assim:
3
,
11
3113133 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]3/53/223/10
14233/43234
3
3
−−−−====
⋅⋅⋅⋅−−−−−−−−←←←←
L
L
Método de Gauss
� Exemplo 6:
�Obtém-se no final Etapa 1 a Matriz:

29
[[[[ ]]]]










−−−−
====
3/53/223/10
3/53/23/10
1423
/ )1()1( bA
Método de Gauss
� Exemplo 6: Etapa 2: pivô = a22 = 1/3 
�Substituindo a linha 3 por: 
1, 323223233 ========⋅⋅⋅⋅−−−−←←←←
a
a
mLmLL
30
�Têm-se:
1,
22
3223233 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]08-00L
5/32/31/3015/322/3-1/30L
3
3
====
⋅⋅⋅⋅−−−−====
Método de Gauss
� Exemplo 6:
�A matriz [A/b] ao final etapa 2 fica assim
com os seguintes valores:
31
[[[[ ]]]]










−−−−
====
0800
3/53/23/10
1423
/ )2()2( bA
Método de Gauss
� Exemplo 6: Resolver Ax=b⇔⇔⇔⇔ A(2) x=b (2)
�Usa-se a solução retroativa:
 ====++++++++ 14x2x3x
32





====−−−−
====++++
====++++++++
08x
52/3x1/3x
14x2x3x
3
32
321
3/
Método de Gauss
� Exemplo 8:
�Usa-se a solução retroativa:


 ====⇒⇒⇒⇒==== 0x08x- 33
33
(((( ))))












−−−−====⇒⇒⇒⇒
====⇒⇒⇒⇒====++++⋅⋅⋅⋅++++⇒⇒⇒⇒====++++⋅⋅⋅⋅++++
====⇒⇒⇒⇒====−−−−⇒⇒⇒⇒====++++
T
053x
-3x14.0523x14xx23x
5x5/30 2/3.1/3x5/3x21/3x
*
11321
2232 3/
� Algoritmo 2: Eliminação de Gauss
1)Dados de Entrada:A: n x n; x: n x 1; b: nx1
2) Para k =1,... (n-1)
3) Para i= k+1,...,n
Resolução de sistemas Lineares
Triangulares Superiores
3) Para i= k+1,...,n
4) m =aik/akk
5) aik=0
6) Para j= k+1,...,n
7) aij= aij - m. akj
8) bi=bi- m bk
�
34
� Algoritmo 2: Resolução Syst. Triangular
9) xn= bn/ ann
10) Para k = (n-1),...2,1
Resolução de sistemas Lineares
Triangulares Superiores
11) s = 0
12) Para j = (k+1),...,n
13) s = s + akjxj
14) xk=(bk - s)/ akk
�
�
35
Método de Gauss
� Exemplo 7:
�Resolver o sistema:
3x3x4x4
5xx3x2 321
====−−−−++++
====−−−−++++
36
� Matriz aumentada Ab
1xx3x2
3x3x4x4
321
321
−−−−====++++−−−−
====−−−−++++
[[[[ ]]]]








−−−−−−−−
−−−−
−−−−
====
1132
3344
5132
Ab
Método de Gauss
� Exemplo 7 :
�Faz-se:
2
a
a
m,LmLL 212112122 ========⋅⋅⋅⋅−−−−====
37
�Assim:
2
a
m,LmLL
11
2112122 ========⋅⋅⋅⋅−−−−====
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]7120L
513223344L
2
2
−−−−−−−−−−−−====
−−−−⋅⋅⋅⋅−−−−−−−−====
Método de Gauss
� Exemplo 7:
�Faz-se:
1, 313113133 ========⋅⋅⋅⋅−−−−====
a
a
mLmLL
38
�Assim:
1,
11
3113133 ========⋅⋅⋅⋅−−−−====
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]6260L
513211132L
3
3
−−−−−−−−====
−−−−⋅⋅⋅⋅−−−−−−−−−−−−====
Método de Gauss
� Exemplo 7:
�Obtém-se a matriz:
[[[[ ]]]]  −−−− 5132
39
[[[[ ]]]]








−−−−−−−−
−−−−−−−−−−−−
−−−−
====
6260
7120
5132
Ab
Método de Gauss
� Exemplo 7:
�Substituindo a linha 3 por: 
3
a
a
m,LmLL 323213233 ========⋅⋅⋅⋅−−−−====
40
�Têm-se:
3
a
m,LmLL
22
3213233 ========⋅⋅⋅⋅−−−−====
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]15500L
712036260L
3
3
====
−−−−−−−−−−−−⋅⋅⋅⋅−−−−−−−−−−−−====
Método de Gauss
� Exemplo 7:
�A matriz [Ab] fica assim com os seguintes
valores:
 −−−− 5132
41
[[[[ ]]]]








−−−−−−−−−−−−
−−−−
====
15500
7120
5132
Ab
Método de Gauss
� Exemplo 7:
�Usa-se a solução retroativa:

 ====⇒⇒⇒⇒==== 3x155x 33
42














====⇒⇒⇒⇒====⇒⇒⇒⇒====−−−−++++⇒⇒⇒⇒
⇒⇒⇒⇒====−−−−⋅⋅⋅⋅++++
====⇒⇒⇒⇒−−−−====−−−−−−−−⇒⇒⇒⇒−−−−====−−−−−−−−
1x22x5362x
5xx32x
2x732x7x2x
111
321
2232
Método de Gauss
� Exemplo 8:
�Resolver o sistema.
7,11x5,4x3,2x2,4
10x3,3x4,5x5,1
321
321
====++++++++
====++++++++
43
�Representando o sistema pela matriz
aumentada:
9,8x8,7x7,5x7,2
7,11x5,4x3,2x2,4
321
321
====++++++++
====++++++++








====
9,88,77,57,2
7,115,43,22,4
103,34,55,1
]AB[
Método de Gauss
� Exemplo 8:
�Escolhendo a primeira linha como pivô,
obtém-se:
[[[[ ]]]]11,74,52,34,2LmLL 12122 −−−−====⋅⋅⋅⋅−−−−====
44
[[[[ ]]]][[[[ ]]]]
[[[[ ]]]]
[[[[ ]]]][[[[ ]]]]
[[[[ ]]]] 9,11,864,020 L
103,35,41,5(2,7/1,5)
8,97,85,72,7LmLL
 16,34,7412,820 L
103,35,41,5(4,2/1,5)
11,74,52,34,2LmLL
3
13133
2
12122
−−−−−−−−−−−−====
⋅⋅⋅⋅
−−−−====⋅⋅⋅⋅−−−−====
−−−−−−−−−−−−====
⋅⋅⋅⋅
−−−−====⋅⋅⋅⋅−−−−====
Método de Gauss
� Exemplo 8:
�Representando o sistema pela matriz
aumentada:
45










−−−−−−−−−−−−
−−−−−−−−−−−−====
9,11,864,020
16,34,7412,820
103,35,41,5
[AB]
� Exemplo 8:
�Escolhendo agora a segunda linha como
pivô, têm-se:
Métodode Gauss
LmLL ⋅⋅⋅⋅−−−−====
46
[[[[ ]]]](((( )))) [[[[ ]]]]
[[[[ ]]]]3,98883,346300L
16,34,7412,82012,824,02/
9,11,864,020L
LmLL
3
3
13233
−−−−====
−−−−−−−−−−−−⋅⋅⋅⋅−−−−−−−−
−−−−−−−−−−−−−−−−====
⋅⋅⋅⋅−−−−====
� Exemplo 8:
�Obtêm-se a seguinte matriz ampliada:
Método de Gauss



 103,35,41,5
47










−−−−
−−−−−−−−−−−−====
3,98883,346300
16,34,7412,820
103,35,41,5
[AB]
Método de Gauss
� Exemplo 8:
�O que termina com a triangulação:
 ====⋅⋅⋅⋅++++⋅⋅⋅⋅++++ 10x3,3x5,41,5x 321
48





−−−−====⋅⋅⋅⋅++++⋅⋅⋅⋅++++⋅⋅⋅⋅
−−−−====⋅⋅⋅⋅−−−−⋅⋅⋅⋅−−−−⋅⋅⋅⋅
====⋅⋅⋅⋅++++⋅⋅⋅⋅++++
3,9888x3,3463x0x0
16,3x4,74x12,82x0
10x3,3x5,41,5x
321
321
321
Método de Gauss
� Exemplo 8:
�Com solução:
x3 = -3,9888/3,3463=-1,1918
49
x2 =[ -16,3 - (-4,74)⋅⋅⋅⋅(-1,1920)]/(-12,82) = 1,7121
x1 = [10 - 5,4(1,7122) - 3,3(-1,1920)]/1,5 = 3,1251
Estratégia de Pivoteamento
� Problema: O que acontece se o Pivô for
nulo? E se o pivô estiver próximo de
zero?
� É impossível trabalhar com pivô nulo. E
pivô próximo de zero pode conduzir apivô próximo de zero pode conduzir a
resultados totalmente imprecisos. Isto
porque eles dão origem a multiplicadores
maiores que um que ampliam os erros de
arredondamento.
� Contornar problema: uso Estratégia
Pivoteamento.
50
Método do Pivoteamento Parcial
� Minimiza a amplificação de erros de
arredondamento durante as eliminações;
� Consiste em no início da etapa k da fase
51
� Consiste em no início da etapa k da fase
de eliminação , escolher para pivô o
elemento de maior módulo entre os
coeficientes:
� Trocar as linhas k e i se necessário
;,....,1,)1( nkkia k
ik
++++====−−−−
Método do Pivoteamento Parcial
� Exemplo 9:
�Resolver o sistema com precisão de 4
casas decimais
10x3,3x4,5x5,1 ====++++++++
52
9,8x8,7x7,5x7,2
7,11x5,4x3,2x2,4
10x3,3x4,5x5,1
321
321
321
====++++++++
====++++++++
====++++++++
Método do Pivoteamento Parcial
� Exemplo 9:
�Matriz aumentada original deve ser
ajustada:
 103,34,55,1
53








9,88,77,57,2
7,115,43,22,4
103,34,55,1








9,88,77,57,2
103,34,55,1
7,115,43,22,4
Método do Pivoteamento Parcial
� Exemplo 9:
�Sistema inalterado, elemento pivô 44,,22.
�Encontrar as novas linhas:
54
�Encontrar as novas linhas:
]1,37864,90714,22140[L
]11,74,52,34,2[(2,7/4,2)
]8,97,85,72,7[LmLL
]5,82141,69294,57860[L
]11,74,52,34,2[1,5/4,2)
]103,35,41,5[LmLL
3
13133
2
12122
====
⋅⋅⋅⋅
−−−−====⋅⋅⋅⋅−−−−====
====
⋅⋅⋅⋅
−−−−====⋅⋅⋅⋅−−−−====
(
Método do Pivoteamento Parcial
� Exemplo 9:
�A matriz ampliada fica da forma:




5,82141,69294,57860
11,74,52,34,2
55
�Como o elemento já é o pivô da 2ª
coluna, tem-se:






 1,37864,90714,22140
5,82141,69294,57860
]3,98863,346300[L
]5,82141,69294,57860[5786)(4,2214/4, 
 ]1,37864,90714,22140[LmLL
3
23233
−−−−====
⋅⋅⋅⋅
−−−−====⋅⋅⋅⋅−−−−====
4,5786
Método do Pivoteamento Parcial
� Exemplo 9:
�A matriz ampliada fica na forma:
 11,74,52,34,2
56










3,9886-3,346300
5,82141,69294,57860
11,74,52,34,2
Método do Pivoteamento Parcial
� Exemplo 9:
�A solução do sistema triangular que
resultou dessas operações é:
x = -3,9886/3,3463 = -1,1919
57
x3 = -3,9886/3,3463 = -1,1919
x2 = [5,8214-1,6929⋅(-1,1919)]/(4,5786) = 1,7121
x1 = [11,7- 2,3(1,7121)- 4,5(-1,1919)]/4,2 = 3,1252
Método do Pivoteamento Parcial
Exemplo 8: Exemplo 9 (com pivoteamento):
x3 = -1,1918 x3 = -1,1919
x2 = 1,7121 x2 = 1,7121
x1 = 3,1252 x1 = 3,1251
58
x1 = 3,1252 x1 = 3,1251
Solução encontrada no Matlab:
x1 = -1,19198135198135 
x2 = 1,71216783216783
x3 = 3,12522144522145
Seja o sistema linear . Este processo de
fatoração consiste em decompor a matriz em
Um produto de dois ou mais fatores.
bxA =
A
Método Direto Decomposição LU
Exemplo: Seja , então resolver
É equivalente a resolver .
Se então resolve-se 1°
e em seguida
bxA =ULA ====
bxUL ====
yxU ==== byL ====
yxU ====
Teorema 2: Fatoração LU
Dada uma matriz quadrada A n x n, seja Ak a
matriz constituída das primeiras k linhas e
colunas de A. Suponha que det(A )≠≠≠≠0 para
Método Direto Decomposição LU
colunas de A. Suponha que det(Ak)≠≠≠≠0 para
k=1,2,...,(n-1). Então existe uma única
Matriz triangular inferior L=(mij), com mii
=1, 1≤≤≤≤i ≤≤≤≤n e uma única matriz triangular
superior U = (uij) tais que LU = A. Ainda
mais, det(A) = u11 u22... unn.
Na fatoração LU o fator L é triangular
inferior com diagonal unitária , e é tal que
seus elementos lij para i>j são os
multiplicadores mij obtidos na fase de
Método Direto Decomposição LU
multiplicadores mij obtidos na fase de
Eliminação de Gauss. O fator U é triangular
superior obtida no final da Fase de
Eliminação de Gauss.
Exemplo de fatoração LU. Considere
onde1423 321 ====++++++++ xxx 
423
Método Direto Decomposição LU
onde
Do método de Gauss sem pivoteamento:
3234
22
1423
321
321
321
====++++++++
====++++++++
====++++++++
xxx
xxx
xxx










====
234
211
423
A
� Etapa 1 pivô = a11 = 3
�Faz-se:
1
,
21
2112122 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
Método Direto Decomposição LU
63
�Assim:
3
,
11
2112122 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]3/23/10
4233/1211
2
2
←←←←
⋅⋅⋅⋅−−−−←←←←
L
L
� Etapa 1: pivô = a11 = 3
�Faz-se:
4
,
31
3113133 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
Método Direto Decomposição LU
64
�Assim:
3
,
11
3113133 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]3/103/10
4233/4234
3
3
−−−−====
⋅⋅⋅⋅−−−−←←←←
L
L
� Exemplo 6:
�Obtém-se no final Etapa 1 a Matriz:

Método Direto Decomposição LU
65
[[[[ ]]]]










−−−−
====
3/103/10
3/23/10
423
)1(A
� Uma vez que os elementos a21 e a31 na
etapa 1 são nulos, guardamos os
multiplicadores nestas posições.
�Obtém-se no final Etapa 1 a Matriz:
Método Direto Decomposição LU
66
�Obtém-se no final Etapa 1 a Matriz:
[[[[ ]]]]










−−−−
====
3/103/13/4
3/23/13/1
423
)1(A
� Etapa 2: pivô = a22 = 1/3 
�Substituindo a linha 3 por: 
1, 323223233 ========⋅⋅⋅⋅−−−−←←←←
a
a
mLmLL
Método Direto Decomposição LU
67
�Têm-se:
1,
22
3223233 ========⋅⋅⋅⋅−−−−←←←←
a
mLmLL
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]4-00L
2/31/30110/3-1/30L
3
3
====
⋅⋅⋅⋅−−−−====
� Exemplo 6:
�A matriz [A] ao final etapa 2 fica assim
com os seguintes valores:
Método Direto Decomposição LU
68
[[[[ ]]]]










−−−−
====
413/4
3/23/13/1
423
)2(A










=
234
211
423
A










− 3/103/13/4
3/23/13/1
423










−413/4
3/23/13/1
423
Método Direto Decomposição LU
Assim, as matrizes L e U são










=
113/4
013/1
001
L









−
=
400
3/23/10
423
U AUL =
Resolvendo o sistema por fatoração LU:
3234
22
1423
321
321
=−+
=++
=++
xxx
xxx
xxx
bxA =
byL =
33/4
23/1
1
21
1
=++
=+
=
yyy
yy
y








= 3/5
1
y
Método Direto Decomposição LU
Continuando









−
=
0
5
3
x
3234 321 =−+ xxx 33/4 321 =++ yyy
yxU =
04
3/53/23/1
1423
3
32
321
=−
=+
=++
x
xx
xxx



 0
Fatoração LU com Pivoteamento
Parcial
� Para aplicar a estratégia de pivoteamento
parcial faz-se necessário armazenar um
vetor de permutação P.
� As permutações de linhas efetuadas
durante a fatoração podem serdurante a fatoração podem ser
representadas por um vetor n x 1,
denotado por P, definido por p(k)=i se na
etapa k a linha i da matriz original A(0) for
a linha pivotal.
71
� Exemplo 10:
� Resolver o sistema:
Fatoração LU com Pivoteamento
Parcial
943 321 ====++++−−−− xxx
72
234
322
31
321
321
====−−−−
====++++++++
xx
xxx
� Matriz e Vetor permutação na etapa Zero.
[[[[ ]]]] 






 −−−− 1143
Fatoração LU com Pivoteamento
Parcial
73
[[[[ ]]]]







====






 −−−−
====
3
2
304
221 )0()0( PA
� Fatoração LU
� Etapa 1: pivô=a31=4 permutar linha 1 e 3
�
Fatoração LU com Pivoteamento
Parcial
 −−−− 3304
74
[[[[ ]]]]










====










−−−−
−−−−
====
1
2
3
143
221
304
)1()'0( PA
� Fatoração LU
� Etapa 1: pivô=a11=4 permutar linha 1 e 3
� m21= m21/a11=1/4; m31= a31/a11=3/4
Fatoração LU com Pivoteamento
Parcial
 −−−− 3304
75
[[[[ ]]]]










====










−−−−
−−−−
====
1
2
3
143
221
304
)1()'0( PA
� Etapa 1:
4
1
,
11
21
2112122 ========⋅⋅⋅⋅−−−−←←←←
a
a
mLmLL
Fatoração LU com Pivoteamento
Parcial
76
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]4/120
3044/1221
2
2
←←←←
−−−−⋅⋅⋅⋅−−−−←←←←
L
L
� Etapa 1:
4
3
,
11
31
3113133 ========⋅⋅⋅⋅−−−−←←←←
a
a
mLmLL
Fatoração LU com Pivoteamento
Parcial
77
11
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]4/1340
3044/3143
3
3
−−−−====
−−−−⋅⋅⋅⋅−−−−−−−−←←←←
L
L
� Ao final da etapa 1:Guardamos os
multiplicadores desta etapa
Fatoração LU com Pivoteamento
Parcial
[[[[ ]]]] 


 −−−−



 −−−− 304304
78
[[[[ ]]]]






 −−−−
⇒⇒⇒⇒






 −−−−
====
4/1344/3
4/1124/1
4/1340
4/1120)1(A
� Etapa 2: pivô: a32=-4 ⇒⇒⇒⇒Trocar linhas 2 e 3
�
Fatoração LU com Pivoteamento
Parcial
 −−−− 3304
79
[[[[ ]]]]










====










−−−−
−−−−
====
2
1
3
4/1124/1
4/1344/3
304
)2()'1( PA
� Etapa 2:
Fatoração LU com Pivoteamento
Parcial
2
1
,
32
3223233 −−−−========⋅⋅⋅⋅−−−−←←←←
a
a
mLmLL
80
222
3223233
a
[[[[ ]]]] [[[[ ]]]]
[[[[ ]]]]35/800L
13/44-0111/420L
3
3
====
⋅⋅⋅⋅−−−−−−−−==== )2/(
Fatoração LU com Pivoteamento
Parcial
� Ao final etapa 2 temos:
 −−−− 304
81
[[[[ ]]]]










−−−−
−−−−
−−−−
====
8/352/14/1
4/1344/3
304
)2(A
� Os fatores L e U são:
Fatoração LU com Pivoteamento
Parcial
[[[[ ]]]] [[[[ ]]]] 


 −−−−



 304001
82
[[[[ ]]]] [[[[ ]]]]







−−−−====






 −−−−
====
8/3500
4/1340
12/14/1
014/3 UL
� Resolvendo o sistema Ly = b’
� b’ é resultado da aplicação do vetor
permutação P ao vetor b.
� Aplicando ao vetor
Fatoração LU com Pivoteamento
Parcial
[[[[ ]]]]213)2( ====P [[[[ ]]]]239 −−−−====bAplicando ao vetor
� Obtemos
83
[[[[ ]]]]213====P [[[[ ]]]]239 −−−−====b
[[[[ ]]]]392' −−−−====b
32/14/1
94/3
2
321
21
1
====++++−−−−
====++++
−−−−====
yyy
yy
y
[[[[ ]]]]4/352/212−−−−====y
� Resolvendo o Sistema: Ux = y
Fatoração LU com Pivoteamento
Parcial
2304 321 −−−−====−−−−++++ xxx
84
[[[[ ]]]]211 −−−−====x
4/358/35
2/214/134
3
32
====
====++++−−−−
x
xx
Decomposição LU Pivoteamento
Parcial –Algoritmo Sol. Ax = b
� (Cálculo dos Fatores)
� Para i = 1, . . ., n
� P(i) = i
� Para k = 1,...,(n-1)
� Pivo=|||| a(k,k) ||||� Pivo=|||| a(k,k) ||||
� r=k
� Para i=k,n
� se |||| a(i,k) |||| > Pivo
� Pivo= |||| a(i,k) ||||
� r=i
85
Decomposição LU com Pivoteamento
Parcial –Algoritmo Sol. Sist. Ax = b
� Se pivo=0 pare ‘A Matriz A é Singular’
� Se r ≠≠≠≠ k faça:
� aux=p(k)
� p(k)=p(r)
� p(r)=aux� p(r)=aux
� Para j=1,n
� aux=a(k,j)
� a(k,j) = a(r,j)
� a(r,j)=aux
�
86
Decomposição LU com Pivoteamento
Parcial –Algoritmo Sol. Sist. Ax = b
� Para i=(k+1),n
� m=a(i,k)/a(k,k)
� a(i,k) = m
� j=k+1,n
� a(i,j)=a(i,j)-m a(k,j)� a(i,j)=a(i,j)-m a(k,j)
� Determinação do vetor c
� Para i=1,n
� r=P(i)
� c(i)=b(r)
� 87
Decomposição LU com Pivoteamento
Parcial –Algoritmo Sol. Sist. Ax = b
� Resolução dos Sistemas:
� Ly = c (Triangular Inferior)
� Para i=1,n� Para i=1,n
� soma=0
� para j=1,(i-1)
� soma = soma + a(i,j)y(j)
� y(i) = c(i) – soma
88
Decomposição LU com Pivoteamento
Parcial –Algoritmo Sol. Sist. Ax = b
� Resolução dos Sistemas:
� Ux = y (Triangular Superior)
� Para i=n,1� Para i=n,1
� soma=0
� para j=(i+1),n
� soma = soma + a(i,j)x(j)
� x(i) = (y(i) – soma)/a(i,i)
89