Sistemas Lineares (LU)

Prévia do material em texto

Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Fatoração LU
● Método Direto
– Solução exata após um numero finito de operações pré-determinadas
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Fatoração LU
● Método Direto
– Solução exata após um numero finito de operações pré-determinadas
● Consiste na decomposição da matriz dos coeficientes num produto de 
duas matrizes 
– A = LxU
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Fatoração LU
● Método Direto
– Solução exata após um numero finito de operações pré-determinadas
● Consiste na decomposição da matriz dos coeficientes num produto de 
duas matrizes 
– A = LxU
● Onde as Matrizes L e U possuem características específicas
– L → Triangular inferior (c/ diagonal unitária)
– U → Trianular superior
Prof. Rômulo Nunes
Métodos Numéricos
●Resolução de Sistemas Lineares
– Fatoração LU
● Método Direto
– Solução exata após um numero finito de operações pré-determinadas
● Consiste na decomposição da matriz dos coeficientes num produto de 
duas matrizes 
– A = LxU
● Onde as Matrizes L e U possuem características específicas
– L → Triangular inferior (c/ diagonal unitária)
– U → Trianular superior
● A decomposição de A em L e U procede efetivamente como uma 
variante do processo de Eliminação de Gauss.
● A solução do Sistema será obtida a partir da solução de 2 sistemas 
simplificados.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
Ak≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
Ak≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
●Temos que A pode ser escrita de forma:
A= L .U
● Onde L é uma matriz triangular Inferior com os 
elementos da diagonal iguais a 1.
● E U é uma matriz triangular superior
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
Ak≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
●Temos que A pode ser escrita de forma:
A= L .U
● Onde L é uma matriz triangular Inferior com os 
elementos da diagonal iguais a 1.
● E U é uma matriz triangular superior
A L U
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
Ak≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
●Podemos então reescrever o sistema da seguinte forma:
Ax = b
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
Ak≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
●Podemos então reescrever o sistema da seguinte forma:
Ax = b  L.U  x = b
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
Ak≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
●Podemos então reescrever o sistema da seguinte forma:
Ax = b  L.U  x = b
●Ou de forma equivalente:
L U.x = b
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas tal que 
det [Ak ]≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
k = n−1
...
●Podemos então reescrever o sistema da seguinte forma:
Ax = b  L.U  x = b
●Ou de forma equivalente:
L U.x = b
●Podemos obter:
y = U.x
E desta forma decompor o sistema original em dois 
sistemas triangulares:
U x = y
L y = b{
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Equivalência dos Sistemas
Seja Ax = b um sistema de n equações e n incógnitas
●Assim após a decomposição da matriz A nas matrizes L e U a resolução do sistema se dá da 
seguinte forma:
U x = y
L y = b{
●O segundo sistema (triangular superior) é resolvido por substituição direta;
− Resultando no vetor y;
●Com o resultado de y o primeiro sistema (triangular inferior) é resolvido 
por substituição inversa;
− Resultando no solução x;
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Para o sistema:
Efetuada a seguinte decomposição:
O vetor solução do sistema pode ser obtido da seguinte forma:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– O vetor solução do sistema pode ser obtido da seguinte forma:
●Começamos a resolver (por substituição descendente) o sistema Ly = b
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– O vetor solução do sistema pode ser obtido da seguinte forma:
●Por fim resolvemos (por substituição ascendente) o sistema U x = y
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– O vetor solução do sistema pode ser obtido da seguinte forma:
●Por fim resolvemos (por substituição ascendente) o sistema U x = y
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– O vetor solução do sistema pode ser obtido da seguinte forma:
●Por fim resolvemos (por substituição ascendente) o sistema U x = y
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Os fatores L e U podem ser obtidos através de fórmulas para os 
elementos l
ij
 e u
ij
, ou através do processo básico de eliminação de 
gauss.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Os fatores L e U podem ser obtidos através de fórmulas para os 
elementos l
ij
 e u
ij
, ou através do processo básico de eliminação de 
gauss.
● Considere o seguinte sistema de dimensão 3.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Os fatores L e U podem ser obtidos através de fórmulas para os 
elementos l
ij
 e u
ij
, ou através do processo básico de eliminação de 
gauss.
● Considere o seguinte sistema de dimensão 3.
● Trabalhando apenas com a matriz dos coeficientes temos:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Supondo pivôs diferente de 0 temos os multiplicadores da etapa 1 dados por:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Supondo pivôs diferente de 0 temos os multiplicadores da etapa 1 dados por:
● Para eliminarmos x
1
 das linas 2 e 3 multiplicamos a 
linha 1 por m
i1
 e subtraímos o resultado da linha i
● Os coeficientes a
ij
(0) serão alterados para a
ij
(1), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
Prof.Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
● Desta forma temos a equivalência M(0)A(0) =A(1) 
● Onde A(1) é a matriz obtida ao fnal da etapa 1 do 
processo de Gauss.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(0) pela matriz M(0), onde:
● Desta forma temos a equivalência M(0)A(0) =A(1) 
● Onde A(1) é a matriz obtida ao fnal da etapa 1 do 
processo de Gauss.
● Supondo agora que o pivô da segunda etapa a
22
(1) ≠ 0 
temos o multiplicador da segunda etapa dado por:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Supondo agora que o pivô da segunda etapa a
22
(1) ≠ 0 temos a segunda etapa dado por:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Supondo agora que o pivô da segunda etapa a
22
(1) ≠ 0 temos a segunda etapa dado por:
● Para eliminarmos x
2
 da lina 3 multiplicamos a linha 2 por m
32
 e subtraímos o resultado da linha 3
● Os coeficientes a
ij
(1) serão alterados para a
ij
(2), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
● Desta forma temos a equivalência M(1)A(1) =A(2) 
● Onde A(2) é a matriz obtida ao final da etapa 2 do 
processo de Gauss.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Estas operações correspondem a se pré-multiplicar a matriz A(1) pela matriz M(1), onde:
● Desta forma temos a equivalência M(1)A(1) =A(2) 
● Onde A(2) é a matriz obtida ao final da etapa 2 do 
processo de Gauss.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● O processo de solução LU necessita da representação da matriz dos coeficientes em função de 
uma matriz Triangular inferior e uma matriz triangular superior.
● O resultado da eliminação de Gauss correlaciona uma matriz triangular superior a matriz dos 
coeficientes A.
A L U
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Analisando a operação de inversas das matrizes dos multiplicadores temos:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Analisando a operação de inversas das matrizes dos multiplicadores temos:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● Analisando a operação de inversas das matrizes dos multiplicadores temos:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Cálculo dos Fatores L e U
● TEO: Seja A uma matriz quadrada de ordem n , A
k
 a matriz formada 
pelas primeiras k linhas e primeiras k colunas de A então existe uma 
única matriz triangular inferior L, cujos elementos da diagonal são 
todos iguais a 1, e uma única matriz triangular superior U tal que 
A = LU se e somente se: det [Ak ]≠0 , k = 1, 2, ... , n−1
Ak
k = 1
k = 2
...
k = n−1
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Qual é então a vantagem inerente ao método da fatoração LU para solução 
de sistemas lineares?
– EX:
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Simplificação na solução de sistemas com mesma matriz dos coeficientes 
A.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– É possível a utilização de estratégias de pivoteamento para fatoração LU?
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Quando necessário a estratégia de pivoteamento parcial requer a 
permutação de linhas na matriz A(k).
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Quando necessário a estratégia de pivoteamento parcial requer a 
permutação de linhas na matriz A(k).
– Por este motivo quando utilizamos a estratégia pivoteamento parcial no 
calculo dos fatores L e U devemos analisar os efeitos das permutações 
realizadas na solução dos sistemas Ly = b e Ux = y.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Quando necessário a estratégia de pivoteamento parcial requer a 
permutação de linhas na matriz A(k).
– Por este motivo quando utilizamos a estratégia pivoteamento parcial no 
calculo dos fatores L e U devemos analisar os efeitos das permutações 
realizadas na solução dos sistemas Ly = b e Ux = y.
– Uma matriz quadrada de ordem n é uma matriz de permutação se pode ser 
obtida da matriz identidade de ordem n permutando-se suas linhas (ou 
colunas).
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Quando necessário a estratégia de pivoteamento parcial requer a 
permutação de linhas na matriz A(k).
– Por este motivo quando utilizamos a estratégia pivoteamento parcial no 
calculo dos fatores L e U devemos analisar os efeitos das permutações 
realizadas na solução dos sistemas Ly = b e Ux = y.
– Uma matriz quadrada de ordem n é uma matriz de permutação se pode ser 
obtida da matriz identidade de ordem n permutando-se suas linhas (ou 
colunas).
– Desta forma pré-multiplicando uma matriz A por uma matriz de 
permutação P obtem-se a matriz PA com as linhas permutadas e esta 
permutação de linhas é a mesma efetuada na matriz identidade para se 
obter P
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Desta forma pré-multiplicando uma matriz A por uma matriz de 
permutação P obtem-se a matriz PA com as linhas permutadas e esta 
permutação de linhas é a mesma efetuada na matriz identidade para se 
obter P
A= 3 1 41 5 92 6 5
Trocar L1 por L2 e depois L2 por L3
PA= 1 5 92 6 53 1 4
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Desta forma pré-multiplicando uma matriz A por uma matrizde 
permutação P obtem-se a matriz PA com as linhas permutadas e esta 
permutação de linhas é a mesma efetuada na matriz identidade para se 
obter P
A= 3 1 41 5 92 6 5
Trocar L1 por L2 e depois L2 por L3
PA= 1 5 92 6 53 1 4
PA= 0 1 00 0 11 0 0 3 1 41 5 92 6 5
PA= 1 5 92 6 53 1 4
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Desta forma com a permutação das linhas da matriz A → A' = PA;
– Devemos então efetuar as mesmas permutações sobre o vetor b uma vez 
que permutar as linhas de A implica permutar as eq. de Ax = b;
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– Desta forma com a permutação das linhas da matriz A → A' = PA;
– Devemos então efetuar as mesmas permutações sobre o vetor b uma vez 
que permutar as linhas de A implica permutar as eq. de Ax = b;
– Seja então b' = Pb
● Resolvemos os sistemas Ly = Pb e Ux = y afim de obter a solução do 
sistema original.
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX:
{3x1 −4x2 x3 =9x1 2x2 2x3 =34x1  −3x3 =−2}
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX: {
3x1 −4x2 x3 =9
x1 2x2 2x3 =3
4x1  −3x3 =−2}
L= 1 0 034 1 01
4
−1
2
1 U = 
4 0 −3
0 −4 134
0 0 35
8
 P = 0 0 11 0 00 1 0
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX: {
3x1 −4x2 x3 =9
x1 2x2 2x3 =3
4x1  −3x3 =−2}
L= 1 0 034 1 01
4
−1
2
1 U = 
4 0 −3
0 −4 134
0 0 35
8
 P = 0 0 11 0 00 1 0
Resolvendo-se Ly = Pb
Pb = 0 0 11 0 00 1 0  93−2= −293 
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX: {
3x1 −4x2 x3 =9
x1 2x2 2x3 =3
4x1  −3x3 =−2}
L= 1 0 034 1 01
4
−1
2
1 U = 
4 0 −3
0 −4 134
0 0 35
8
 P = 0 0 11 0 00 1 0
Resolvendo-se Ly = Pb
Pb = 0 0 11 0 00 1 0  93−2= −293  y = −293 
Prof. Rômulo Nunes
Métodos Numéricos
●Fatoração LU:
– EX: {
3x1 −4x2 x3 =9
x1 2x2 2x3 =3
4x1  −3x3 =−2}
L= 1 0 034 1 01
4
−1
2
1 U = 
4 0 −3
0 −4 134
0 0 35
8
 P = 0 0 11 0 00 1 0
Resolvendo-se Ly = Pb
Pb = 0 0 11 0 00 1 0  93−2= −293  y = −293 
Resolvendo-se Ux = y
x =  1−12 
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73