cn_sistemas_lineares_LU

Prévia do material em texto

Ca´lculo Nume´rico
Sistemas Lineares
Me´todos Diretos
Decomposic¸a˜o LU
Joa˜o Paulo Gois
Universidade Federal do ABC
1
1
Apresentac¸a˜o baseada nos slides do prof. John Carroll, Dublin City University e no Livro Ana´lise Nume´rica
(Burden & Faires)
Roteiro
1 Aspectos Computacionais
2 Construindo a fatorac¸a˜o matricial
3 Exemplo: Fatorac¸a˜o LU de uma matrix 4× 4
4 O algoritmo de fatorac¸a˜o LU
5 Matrizes de permutac¸a˜o para troca de linhas
Roteiro
1 Aspectos Computacionais
2 Construindo a fatorac¸a˜o matricial
3 Exemplo: Fatorac¸a˜o LU de uma matrix 4× 4
4 O algoritmo de fatorac¸a˜o LU
5 Matrizes de permutac¸a˜o para troca de linhas
Roteiro
1 Aspectos Computacionais
2 Construindo a fatorac¸a˜o matricial
3 Exemplo: Fatorac¸a˜o LU de uma matrix 4× 4
4 O algoritmo de fatorac¸a˜o LU
5 Matrizes de permutac¸a˜o para troca de linhas
Roteiro
1 Aspectos Computacionais
2 Construindo a fatorac¸a˜o matricial
3 Exemplo: Fatorac¸a˜o LU de uma matrix 4× 4
4 O algoritmo de fatorac¸a˜o LU
5 Matrizes de permutac¸a˜o para troca de linhas
Roteiro
1 Aspectos Computacionais
2 Construindo a fatorac¸a˜o matricial
3 Exemplo: Fatorac¸a˜o LU de uma matrix 4× 4
4 O algoritmo de fatorac¸a˜o LU
5 Matrizes de permutac¸a˜o para troca de linhas
Roteiro
1 Aspectos Computacionais
2 Construindo a fatorac¸a˜o matricial
3 Exemplo: Fatorac¸a˜o LU de uma matrix 4× 4
4 O algoritmo de fatorac¸a˜o LU
5 Matrizes de permutac¸a˜o para troca de linhas
Fatorac¸a˜o Matricial
Revisa˜o
A eliminac¸a˜o Gaussiana e´ a principal ferramenta para soluc¸a˜o
direta de sistemas de equac¸o˜es lineares
Veremos agora que os passos para resolver o sistema da forma
Ax = b pode ser usado para fatorar a matriz
A fatorac¸a˜o e´ particularmente u´til quando ela tem a forma
A = LU , onde L e´ uma triangular inferior e U e´ uma
triangular superior
Fatorac¸a˜o Matricial
Revisa˜o
A eliminac¸a˜o Gaussiana e´ a principal ferramenta para soluc¸a˜o
direta de sistemas de equac¸o˜es lineares
Veremos agora que os passos para resolver o sistema da forma
Ax = b pode ser usado para fatorar a matriz
A fatorac¸a˜o e´ particularmente u´til quando ela tem a forma
A = LU , onde L e´ uma triangular inferior e U e´ uma
triangular superior
Fatorac¸a˜o Matricial
Revisa˜o
A eliminac¸a˜o Gaussiana e´ a principal ferramenta para soluc¸a˜o
direta de sistemas de equac¸o˜es lineares
Veremos agora que os passos para resolver o sistema da forma
Ax = b pode ser usado para fatorar a matriz
A fatorac¸a˜o e´ particularmente u´til quando ela tem a forma
A = LU , onde L e´ uma triangular inferior e U e´ uma
triangular superior
Fatorac¸a˜o Matricial
Revisa˜o
A eliminac¸a˜o Gaussiana e´ a principal ferramenta para soluc¸a˜o
direta de sistemas de equac¸o˜es lineares
Veremos agora que os passos para resolver o sistema da forma
Ax = b pode ser usado para fatorar a matriz
A fatorac¸a˜o e´ particularmente u´til quando ela tem a forma
A = LU , onde L e´ uma triangular inferior e U e´ uma
triangular superior
Fatorac¸a˜o Matricial
Considerac¸o˜es sobre o custo computacional
A eliminac¸a˜o Gaussiana aplicada a um sistema linear Ax = b
de n inco´gnitas requer o custo de O(n3/3) operac¸o˜es
aritme´ticas para determinar x
Entretanto, para resolver o sistema linear de n inco´gnitas que
envolve uma matriz triangular superior requer apenas a
retro-substituic¸a˜o, que custa O(n2) operac¸o˜es
O nu´mero de operac¸o˜es para resolver um sistema triangular
inferior e´ similar
Fatorac¸a˜o Matricial
Considerac¸o˜es sobre o custo computacional
A eliminac¸a˜o Gaussiana aplicada a um sistema linear Ax = b
de n inco´gnitas requer o custo de O(n3/3) operac¸o˜es
aritme´ticas para determinar x
Entretanto, para resolver o sistema linear de n inco´gnitas que
envolve uma matriz triangular superior requer apenas a
retro-substituic¸a˜o, que custa O(n2) operac¸o˜es
O nu´mero de operac¸o˜es para resolver um sistema triangular
inferior e´ similar
Fatorac¸a˜o Matricial
Considerac¸o˜es sobre o custo computacional
A eliminac¸a˜o Gaussiana aplicada a um sistema linear Ax = b
de n inco´gnitas requer o custo de O(n3/3) operac¸o˜es
aritme´ticas para determinar x
Entretanto, para resolver o sistema linear de n inco´gnitas que
envolve uma matriz triangular superior requer apenas a
retro-substituic¸a˜o, que custa O(n2) operac¸o˜es
O nu´mero de operac¸o˜es para resolver um sistema triangular
inferior e´ similar
Fatorac¸a˜o Matricial
Considerac¸o˜es sobre o custo computacional
A eliminac¸a˜o Gaussiana aplicada a um sistema linear Ax = b
de n inco´gnitas requer o custo de O(n3/3) operac¸o˜es
aritme´ticas para determinar x
Entretanto, para resolver o sistema linear de n inco´gnitas que
envolve uma matriz triangular superior requer apenas a
retro-substituic¸a˜o, que custa O(n2) operac¸o˜es
O nu´mero de operac¸o˜es para resolver um sistema triangular
inferior e´ similar
Fatorac¸a˜o Matricial
Estrate´gia de Soluc¸a˜o
Suponha que A tem que ser fatorada na forma triangular A = LU ,
onde L e´ a matriz triangular inferior e U a triangular superior. Po-
demos enta˜o resolver para x mais facilmente usando um processo
de dois passos:
Primeiro, fazemos y = Ux e resolvemos o sistema triangular
inferior Ly = b para y. Como L e´ triangular, determinar y
requer apenas O(n2) operac¸o˜es
Uma vez y e´ conhecido, o sistema triangular superior Ux = y
requer um custo adicional de O(n2) operac¸o˜es para
determinar a soluc¸a˜o de x
Resolver o sistema linear Ax = b na forma fatorada significa reduzir
o nu´mero de operac¸o˜es de O(n3/3) para O(2n2) = O(n2)
Fatorac¸a˜o Matricial
Estrate´gia de Soluc¸a˜o
Suponha que A tem que ser fatorada na forma triangular A = LU ,
onde L e´ a matriz triangular inferior e U a triangular superior. Po-
demos enta˜o resolver para x mais facilmente usando um processo
de dois passos:
Primeiro, fazemos y = Ux e resolvemos o sistema triangular
inferior Ly = b para y. Como L e´ triangular, determinar y
requer apenas O(n2) operac¸o˜es
Uma vez y e´ conhecido, o sistema triangular superior Ux = y
requer um custo adicional de O(n2) operac¸o˜es para
determinar a soluc¸a˜o de x
Resolver o sistema linear Ax = b na forma fatorada significa reduzir
o nu´mero de operac¸o˜es de O(n3/3) para O(2n2) = O(n2)
Fatorac¸a˜o Matricial
Estrate´gia de Soluc¸a˜o
Suponha que A tem que ser fatorada na forma triangular A = LU ,
onde L e´ a matriz triangular inferior e U a triangular superior. Po-
demos enta˜o resolver para x mais facilmente usando um processo
de dois passos:
Primeiro, fazemos y = Ux e resolvemos o sistema triangular
inferior Ly = b para y. Como L e´ triangular, determinar y
requer apenas O(n2) operac¸o˜es
Uma vez y e´ conhecido, o sistema triangular superior Ux = y
requer um custo adicional de O(n2) operac¸o˜es para
determinar a soluc¸a˜o de x
Resolver o sistema linear Ax = b na forma fatorada significa reduzir
o nu´mero de operac¸o˜es de O(n3/3) para O(2n2) = O(n2)
Fatorac¸a˜o Matricial
Estrate´gia de Soluc¸a˜o
Suponha que A tem que ser fatorada na forma triangular A = LU ,
onde L e´ a matriz triangular inferior e U a triangular superior. Po-
demos enta˜o resolver para x mais facilmente usando um processo
de dois passos:
Primeiro, fazemos y = Ux e resolvemos o sistema triangular
inferior Ly = b para y. Como L e´ triangular, determinar y
requer apenas O(n2) operac¸o˜es
Uma vez y e´ conhecido, o sistema triangular superior Ux = y
requer um custo adicional de O(n2) operac¸o˜es para
determinar a soluc¸a˜o de x
Resolver o sistema linear Ax = b na forma fatorada significa reduzir
o nu´mero de operac¸o˜es de O(n3/3) para O(2n2) = O(n2)
Fatorac¸a˜o Matricial
Construindo L & U
Primeiro, suponha que a eliminac¸a˜oGaussiana pode ser
realizada sobre o sistema linear Ax = b sem trocas de linhas
Com a notac¸a˜o usada anteriormente, isto e´ equivalente a ter
elementos pivoˆ na˜o-zero a
(i)
i,i , para i = 1, 2, · · · , n.
O primeiro passo na eliminac¸a˜o Gaussiana consiste em realizar
para cada j = 2, 3, · · · , n as operac¸o˜es:
Ej ← Ej −mj,1E1, onde mj,1 =
a
(1)
j,1
a
(1)
1,1
Estas operac¸o˜es transformam o sistema em um em que todas
as entradas abaixo da diagonal sa˜o zero
Fatorac¸a˜o Matricial
Construindo L & U
Primeiro, suponha que a eliminac¸a˜o Gaussiana pode ser
realizada sobre o sistema linear Ax = b sem trocas de linhas
Com a notac¸a˜o usada anteriormente, isto e´ equivalente a ter
elementos pivoˆ na˜o-zero a
(i)
i,i , para i = 1, 2, · · · , n.
O primeiro passo na eliminac¸a˜o Gaussiana consiste em realizar
para cada j = 2, 3, · · · , n as operac¸o˜es:
Ej ← Ej −mj,1E1, onde mj,1 =
a
(1)
j,1
a
(1)
1,1
Estas operac¸o˜es transformam o sistema em um em que todas
as entradas abaixo da diagonal sa˜o zero
Fatorac¸a˜o Matricial
Construindo L & U
Primeiro, suponha que a eliminac¸a˜o Gaussiana pode ser
realizada sobre o sistema linear Ax = b sem trocas de linhas
Com a notac¸a˜o usada anteriormente, isto e´ equivalente a ter
elementos pivoˆ na˜o-zero a
(i)
i,i , para i = 1, 2, · · · , n.
O primeiro passo na eliminac¸a˜o Gaussiana consiste em realizar
para cada j = 2, 3, · · · , n as operac¸o˜es:
Ej ← Ej −mj,1E1, onde mj,1 =
a
(1)
j,1
a
(1)
1,1
Estas operac¸o˜es transformam o sistema em um em que todas
as entradas abaixo da diagonal sa˜o zero
Fatorac¸a˜o Matricial
Construindo L & U
Primeiro, suponha que a eliminac¸a˜o Gaussiana pode ser
realizada sobre o sistema linear Ax = b sem trocas de linhas
Com a notac¸a˜o usada anteriormente, isto e´ equivalente a ter
elementos pivoˆ na˜o-zero a
(i)
i,i , para i = 1, 2, · · · , n.
O primeiro passo na eliminac¸a˜o Gaussiana consiste em realizar
para cada j = 2, 3, · · · , n as operac¸o˜es:
Ej ← Ej −mj,1E1, onde mj,1 =
a
(1)
j,1
a
(1)
1,1
Estas operac¸o˜es transformam o sistema em um em que todas
as entradas abaixo da diagonal sa˜o zero
Fatorac¸a˜o Matricial
Construindo L & U
Primeiro, suponha que a eliminac¸a˜o Gaussiana pode ser
realizada sobre o sistema linear Ax = b sem trocas de linhas
Com a notac¸a˜o usada anteriormente, isto e´ equivalente a ter
elementos pivoˆ na˜o-zero a
(i)
i,i , para i = 1, 2, · · · , n.
O primeiro passo na eliminac¸a˜o Gaussiana consiste em realizar
para cada j = 2, 3, · · · , n as operac¸o˜es:
Ej ← Ej −mj,1E1, onde mj,1 =
a
(1)
j,1
a
(1)
1,1
Estas operac¸o˜es transformam o sistema em um em que todas
as entradas abaixo da diagonal sa˜o zero
Fatorac¸a˜o Matricial
O Sistema das Operac¸o˜es em
Ej ← Ej −mj,1E1 onde mj,1 =
a
(1)
j,1
a
(1)
1,1
pode ser visto de outra forma.
Ela e´ obtida por multiplicar a matriz
original A a esquerda pela matriz
M (1) =

1 0 · · · · · · 0
−m2,1 1 . . .
...
... 0
. . .
...
...
...
. . .
. . . 0
−mn,1 0 · · · 0 1

Esta e´ chamada de Primeira Transformac¸a˜o Matricial Gaussiana
Fatorac¸a˜o Matricial
O Sistema das Operac¸o˜es em
Ej ← Ej −mj,1E1 onde mj,1 =
a
(1)
j,1
a
(1)
1,1
pode ser visto de outra forma. Ela e´ obtida por multiplicar a matriz
original A a esquerda pela matriz
M (1) =

1 0 · · · · · · 0
−m2,1 1 . . .
...
... 0
. . .
...
...
...
. . .
. . . 0
−mn,1 0 · · · 0 1

Esta e´ chamada de Primeira Transformac¸a˜o Matricial Gaussiana
Fatorac¸a˜o Matricial
O Sistema das Operac¸o˜es em
Ej ← Ej −mj,1E1 onde mj,1 =
a
(1)
j,1
a
(1)
1,1
pode ser visto de outra forma. Ela e´ obtida por multiplicar a matriz
original A a esquerda pela matriz
M (1) =

1 0 · · · · · · 0
−m2,1 1 . . .
...
... 0
. . .
...
...
...
. . .
. . . 0
−mn,1 0 · · · 0 1

Esta e´ chamada de Primeira Transformac¸a˜o Matricial Gaussiana
Exerc´ıcio
Considere a matriz:
M (1) =

1 0 0 0
−m2,1 1 0 0
−m3,1 0 1 0
−m4,1 0 0 1

Calcule M (1)A, onde A = [ai,j ]4×4 e mj,1 =
a
(1)
j,1
a
(1)
1,1
=
aj,1
a1,1
.
Fatorac¸a˜o Matricial
Construindo L&U
Denotamos o produto desta matriz por A(1) ≡ A por A(2) e
com b por b(2), o que implica:
A(2)x = M (1)Ax = M (1)b = b(2)
De maneira similar, constru´ımos M (2), a matriz identidade
com entradas abaixo da diagonal na segunda coluna trocada
pelos valores negativos de:
mj,2 =
a
(2)
j,2
a
(2)
2,2
Fatorac¸a˜o Matricial
Construindo L&U
Denotamos o produto desta matriz por A(1) ≡ A por A(2) e
com b por b(2), o que implica:
A(2)x = M (1)Ax = M (1)b = b(2)
De maneira similar, constru´ımos M (2), a matriz identidade
com entradas abaixo da diagonal na segunda coluna trocada
pelos valores negativos de:
mj,2 =
a
(2)
j,2
a
(2)
2,2
Fatorac¸a˜o Matricial
Construindo L&U
Denotamos o produto desta matriz por A(1) ≡ A por A(2) e
com b por b(2), o que implica:
A(2)x = M (1)Ax = M (1)b = b(2)
De maneira similar, constru´ımos M (2), a matriz identidade
com entradas abaixo da diagonal na segunda coluna trocada
pelos valores negativos de:
mj,2 =
a
(2)
j,2
a
(2)
2,2
Fatorac¸a˜o Matricial
Construindo L&U
O produto de M (2) com A(2) tem zeros abaixo da diagonal
nas duas primeiras colunas. Fazemos enta˜o:
A(3)x = M (2)A(2)x = M (2)M (1)Ax = M (2)M (1)b = b(3)
Fatorac¸a˜o Matricial
Construindo L&U
O produto de M (2) com A(2) tem zeros abaixo da diagonal
nas duas primeiras colunas.
Fazemos enta˜o:
A(3)x = M (2)A(2)x = M (2)M (1)Ax = M (2)M (1)b = b(3)
Fatorac¸a˜o Matricial
Construindo L&U
O produto de M (2) com A(2) tem zeros abaixo da diagonal
nas duas primeiras colunas. Fazemos enta˜o:
A(3)x = M (2)A(2)x = M (2)M (1)Ax = M (2)M (1)b = b(3)
Fatorac¸a˜o Matricial
Construindo L&U
Em geral, com A(k)x = b(k) ja´ formada, multiplicada pela k-e´sima
matriz de transformac¸a˜o Gaussiana
M (k) =

1 0 · · · · · · · · · · · · · · · 0
0 1
. . .
...
...
. . .
. . .
. . .
...
... 0
. . .
. . .
...
...
... −mk+1,k . . . . . .
...
...
...
...
...
...
...
...
...
... 1 0
0 · · · 0 −mn,k 0 · · · 0 1

Fatorac¸a˜o Matricial
Construindo L&U
para obter:
A(k+1)x = M (k)A(k)x
= M (k) · · ·M (1)Ax
= M (k)b(k)
= b(k+1)
= M (k) · · ·M (1)b
Fatorac¸a˜o Matricial
Construindo L&U
para obter:
A(k+1)x = M (k)A(k)x
= M (k) · · ·M (1)Ax
= M (k)b(k)
= b(k+1)
= M (k) · · ·M (1)b
Fatorac¸a˜o Matricial
Construindo L&U
para obter:
A(k+1)x = M (k)A(k)x
= M (k) · · ·M (1)Ax
= M (k)b(k)
= b(k+1)
= M (k) · · ·M (1)b
Fatorac¸a˜o Matricial
Construindo L&U
para obter:
A(k+1)x = M (k)A(k)x
= M (k) · · ·M (1)Ax
= M (k)b(k)
= b(k+1)
= M (k) · · ·M (1)b
Fatorac¸a˜o Matricial
Construindo L&U
para obter:
A(k+1)x = M (k)A(k)x
= M (k) · · ·M (1)Ax
= M (k)b(k)
= b(k+1)
= M (k) · · ·M (1)b
Fatorac¸a˜o Matricial
Construindo L&U
O processo termina com a formac¸a˜o A(n)x = b(n), onde A(n) e´ a
matriz triangular superior:
A(n) =

a
(1)
1,1 a
(1)
1,2 · · · · · · a(1)1,n
0 a
(2)
2,2
. . .
...
...
. . .
. . .
. . .
...
...
. . .
. . . a
(n−1)
n−1,n
0 · · · · · · 0 a(n)n,n

dado por
A(n) = M (n−1)M (n−2) · · ·M (1)A
Fatorac¸a˜o Matricial
Construindo L&U
Este processo forma a porc¸a˜o U = A(n) da fatorac¸a˜o matricial
A = LU
Para determinar a matriz triangular inferior L, primeiro
lembremos da multiplicac¸a˜o A(k)x = b(k) pela transformac¸a˜o
Gaussiana M (k)usada para obter:
A(k+1)x = M (k)A(k)x = M (k)b(k) = b(k+1)
onde M (k) gera as operac¸o˜es por linha
Ej ← Ej −mj,kEk para j = k + 1, · · · , n
Fatorac¸a˜o Matricial
Construindo L&U
Este processo forma a porc¸a˜o U = A(n) da fatorac¸a˜o matricial
A = LU
Para determinar a matriz triangular inferior L, primeiro
lembremos da multiplicac¸a˜o A(k)x = b(k) pela transformac¸a˜o
Gaussiana M (k) usada para obter:
A(k+1)x = M (k)A(k)x = M (k)b(k) = b(k+1)
onde M (k) gera as operac¸o˜es por linha
Ej ← Ej −mj,kEk para j = k + 1, · · · , n
Fatorac¸a˜o Matricial
Construindo L&U
Este processo forma a porc¸a˜o U = A(n) da fatorac¸a˜o matricial
A = LU
Para determinar a matriz triangular inferior L, primeiro
lembremos da multiplicac¸a˜o A(k)x = b(k) pela transformac¸a˜o
Gaussiana M (k) usada para obter:
A(k+1)x = M (k)A(k)x = M (k)b(k) = b(k+1)
onde M (k) gera as operac¸o˜es por linha
Ej ← Ej −mj,kEk para j = k + 1, · · · , n
Fatorac¸a˜o Matricial
Construindo L&U
Para se reverter os efeitos dessa transformac¸a˜o e se retornar a A(k)
e´ necessa´rio que as operac¸o˜es Ej ← Ej +mj,kEk sejam executadas
para cada j = k + 1, · · · , n.
Isto e´ equivalente a multiplicar por[
M (k)
]−1
L(k) =
[
M (k)
]−1
=

1 0 · · · · · · · · · · · · · · · 0
0 1
. . .
...
...
. . .
. . .
. . .
...
... 0
. . .
. . .
...
...
... mk+1,k
. . .
. . .
...
...
...
...
...
...
...
...
...
... 1 0
0 · · · 0 mn,k 0 · · · 0 1

Fatorac¸a˜o Matricial
Construindo L&U
Para se reverter os efeitos dessa transformac¸a˜o e se retornar a A(k)
e´ necessa´rio que as operac¸o˜es Ej ← Ej +mj,kEk sejam executadas
para cada j = k + 1, · · · , n. Isto e´ equivalente a multiplicar por[
M (k)
]−1
L(k) =
[
M (k)
]−1
=

1 0 · · · · · · · · · · · · · · · 0
0 1
. . .
...
...
. . .
. . .
. . .
...
... 0
. . .
. . .
...
...
... mk+1,k
. . .
. . .
...
...
...
...
...
...
...
...
...
... 1 0
0 · · · 0 mn,k 0 · · · 0 1

Fatorac¸a˜o Matricial
Construindo L&U
Para se reverter os efeitos dessa transformac¸a˜o e se retornar a A(k)
e´ necessa´rio que as operac¸o˜es Ej ← Ej +mj,kEk sejam executadas
para cada j = k + 1, · · · , n. Isto e´ equivalente a multiplicar por[
M (k)
]−1
L(k) =
[
M (k)
]−1
=

1 0 · · · · · · · · · · · · · · · 0
0 1
. . .
...
...
. . .
. . .
. . .
...
... 0
. . .
. . .
...
...
... mk+1,k
. . .
. . .
...
...
...
...
...
...
...
...
...
... 1 0
0 · · · 0 mn,k 0 · · · 0 1

Exerc´ıcio
Considere as Matrizes
M (1) =

1 0 0 0 0
−m2,1 1 0 0 0
−m3,1 0 1 0 0
−m4,1 0 0 1 0
−m5,1 0 0 0 1
 L(1) =

1 0 0 0 0
m2,1 1 0 0 0
m3,1 0 1 0 0
m4,1 0 0 1 0
m5,1 0 0 0 1

Verifique que L(1)M (1) = I = M (1)L(1).
Fatorac¸a˜o Matricial
Construindo L&U
A matriz triangular inferior L na fatorac¸a˜o de A e´ enta˜o o produto
das matrizes L(k):
L = L(1)L(2) · · ·L(n−1) =
=

1 0 · · · · · · 0
m2,1 1
. . .
...
...
. . .
. . .
. . .
...
...
...
. . .
. . . 0
mn,1 · · · · · · mn,n−1 1

como o produto da matriz de L com a triangular superior U =
M (n−1) · · ·M (2)M (1)A temos
Fatorac¸a˜o Matricial
Construindo L&U
A matriz triangular inferior L na fatorac¸a˜o de A e´ enta˜o o produto
das matrizes L(k):
L = L(1)L(2) · · ·L(n−1) =
=

1 0 · · · · · · 0
m2,1 1
. . .
...
...
. . .
. . .
. . .
...
...
...
. . .
. . . 0
mn,1 · · · · · · mn,n−1 1

como o produto da matriz de L com a triangular superior U =
M (n−1) · · ·M (2)M (1)A temos
Fatorac¸a˜o Matricial
Construindo L&U
LU = L(1)L(2) · · ·L(n−2)L(n−1)M (n−1)M (n−2) · · ·M (2)M (1)A
=
[
M (1)
]−1 [
M (2)
]−1 · · · [M (n−2)]−1 [M (n−1)]−1 ·
·M (n−1)M (n−2) · · ·M (2)M (1)A =
= A
O seguinte teorema resume estas observac¸o˜es
Fatorac¸a˜o Matricial
Construindo L&U
LU = L(1)L(2) · · ·L(n−2)L(n−1)M (n−1)M (n−2) · · ·M (2)M (1)A
=
[
M (1)
]−1 [
M (2)
]−1 · · · [M (n−2)]−1 [M (n−1)]−1 ·
·M (n−1)M (n−2) · · ·M (2)M (1)A =
= A
O seguinte teorema resume estas observac¸o˜es
Fatorac¸a˜o Matricial
Construindo L&U
LU = L(1)L(2) · · ·L(n−2)L(n−1)M (n−1)M (n−2) · · ·M (2)M (1)A
=
[
M (1)
]−1 [
M (2)
]−1 · · · [M (n−2)]−1 [M (n−1)]−1 ·
·M (n−1)M (n−2) · · ·M (2)M (1)A =
= A
O seguinte teorema resume estas observac¸o˜es
Exerc´ıcio
Considere as matrizes:
M (1) =

1 0 0 0
m2,1 1 0 0
m3,1 0 1 0
m4,1 0 0 1

M (2) =

1 0 0 0
0 1 0 0
0 m3,2 1 0
0 m4,2 0 1
 ,M (3) =

1 0 0 0
0 1 0 0
0 0 1 0
0 0 m4,3 1

Calcule M (1)M (2)M (3).
Fatorac¸a˜o Matricial
Teorema
Se a Eliminac¸a˜o Gaussiana pode ser realizada sobre um sistema linear
Ax = b sem troca de linhas, enta˜o a matriz A pode ser fatorada no
produto de duas matrizes triangulares, uma superior U e outra inferior L
de modo que A = LU , onde mj,i = a
(i)
j,i/a
(i)
i,i ,
U =

a
(1)
1,1 a
(1)
1,2 · · · · · · a
(1)
1,n
0 a
(2)
2,2
. . .
.
.
.
.
.
.
. . .
. . .
. . .
.
.
.
.
.
.
. . .
. . . a
(n−1)
n−1,n
0 · · · · · · 0 a(n)n,n
 L =

1 0 · · · · · · 0
m2,1 1
. . .
.
.
.
.
.
.
. . .
. . .
. . .
.
.
.
.
.
.
.
.
.
. . .
. . . 0
mn,1 · · · · · · mn,n−1 1

Exemplo
Determine a fatorac¸a˜o LU para a matriz A no sistema linear
Ax = b abaixo e encontre x.
A =

1 1 0 3
2 1 −1 1
3 −1 −1 2
−1 2 3 −1
 b =

8
7
14
−7

Exemplo - Soluc¸a˜o
Realizamos primeiramente a sequeˆncia de operac¸o˜es:
E2 ← E2 − 2E1
E3 ← E3 − 3E1
E4 ← E4 − (−1)E1
E3 ← E3 − 4E2
E4 ← E4 − (−3)E2
Exemplo - Soluc¸a˜o
Os multiplicadores mij e a matriz triangular superior produzem a
fatorac¸a˜o:
A =

1 1 0 3
2 1 −1 1
3 −1 −1 2
−1 2 3 −1
 =
=

1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1


1 1 0 3
0 −1 −1 −5
0 0 3 13
0 0 0 −13

= LU (1)
Exemplo - Soluc¸a˜o
Resolvendo o sistema Linear
Ax = LUx =

1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1


1 1 0 3
0 −1 −1 −5
0 0 3 13
0 0 0 −13


x1
x2
x3
x4

=

8
7
14
−7

primeiro fazemos a substituic¸a˜o y = Ux; para enta˜o resolver
L(Ux) = Ly = b
Exemplo - Soluc¸a˜o
Resolvendo o sistema Linear
Ax = LUx =

1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1


1 1 0 3
0 −1 −1 −5
0 0 3 13
0 0 0 −13


x1
x2
x3
x4

=

8
7
14
−7

primeiro fazemos a substituic¸a˜o y = Ux; para enta˜o resolver
L(Ux) = Ly = b
Exemplo - Soluc¸a˜o
Resolvendo o sistema Linear
Primeiro resolvemos Ly = b, onde y = Ux:
Ly =

1 0 0 0
2 1 0 0
3 4 1 0
−1 −3 0 1


y1
y2
y3
y4
 =

8
7
14
−7


y1
y2
y3
y4
 =

8
−9
26
−26

Exemplo - Soluc¸a˜o
Resolvendo o sistema Linear
No´s enta˜o resolvemos Ux = y para x:

1 1 0 3
0 −1 −1 −5
0 0 3 13
0 0 0 −13


x1
x2
x3
x4
 =

8
−9
26
−26

Obtemos x1 = 3;x2 = −1;x3 = 0;x4 = 2.
Exemplo - Soluc¸a˜o
Resolvendo o sistema Linear
No´s enta˜o resolvemos Ux = y para x:
1 1 0 3
0 −1 −1 −5
0 0 3 13
0 0 0 −13


x1
x2
x3
x4
 =

8
−9
26
−26

Obtemos x1 = 3;x2 = −1;x3 = 0;x4 = 2.
Algoritmo
Queremos fatorar uma matriz n × n A = [ai,j ] em uma triangularinferior L = [`i,j ] e uma triangular superior U = [ui,j ] tal que
A = LU
Entrada dimensa˜o n e os ai,j de A
Sa´ıda os `i,j , 1 ≤ j ≤ i; 1 ≤ i ≤ n de L e ui,j , i ≤ j ≤ n; 1 ≤ i ≤ n
de U
Algoritmo:
ui,j = ai,j −
i−1∑
k=1
`i,kuk,j i ≤ j
`i,j = `i,j =
(
ai,j −
j−1∑
k=1
`i,kuk,j
)
i > j
Algoritmo
Queremos fatorar uma matriz n × n A = [ai,j ] em uma triangular
inferior L = [`i,j ] e uma triangular superior U = [ui,j ] tal que
A = LU
Entrada dimensa˜o n e os ai,j de A
Sa´ıda os `i,j , 1 ≤ j ≤ i; 1 ≤ i ≤ n de L e ui,j , i ≤ j ≤ n; 1 ≤ i ≤ n
de U
Algoritmo:
ui,j = ai,j −
i−1∑
k=1
`i,kuk,j i ≤ j
`i,j = `i,j =
(
ai,j −
j−1∑
k=1
`i,kuk,j
)
i > j
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Limitac¸o˜es da Fatorac¸a˜o LU
Assumimos que Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana sem troca de linhas
Do ponto de vista pra´tico, esta fatorac¸a˜o e´ u´til apenas quando
a troca de linhas na˜o e´ necessa´ria para controlar erros de
arredondamento
No´s agora consideraremos as modificac¸o˜es que devemos fazer
quando a troca de linhas sa˜o necessa´rias.
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Limitac¸o˜es da Fatorac¸a˜o LU
Assumimos que Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana sem troca de linhas
Do ponto de vista pra´tico, esta fatorac¸a˜o e´ u´til apenas quando
a troca de linhas na˜o e´ necessa´ria para controlar erros de
arredondamento
No´s agora consideraremos as modificac¸o˜es que devemos fazer
quando a troca de linhas sa˜o necessa´rias.
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Limitac¸o˜es da Fatorac¸a˜o LU
Assumimos que Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana sem troca de linhas
Do ponto de vista pra´tico, esta fatorac¸a˜o e´ u´til apenas quando
a troca de linhas na˜o e´ necessa´ria para controlar erros de
arredondamento
No´s agora consideraremos as modificac¸o˜es que devemos fazer
quando a troca de linhas sa˜o necessa´rias.
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Limitac¸o˜es da Fatorac¸a˜o LU
Assumimos que Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana sem troca de linhas
Do ponto de vista pra´tico, esta fatorac¸a˜o e´ u´til apenas quando
a troca de linhas na˜o e´ necessa´ria para controlar erros de
arredondamento
No´s agora consideraremos as modificac¸o˜es que devemos fazer
quando a troca de linhas sa˜o necessa´rias.
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
No´s iniciamos com a introduc¸a˜o de uma classe de matrizes que sa˜o
usadas para trocar linhas de uma matriz
Matriz de Permutac¸a˜o
Uma matriz de permutac¸a˜o n × n P = [pi,j ] e´ obtida pela per-
mutac¸a˜o de linhas da matriz identidade In.
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A Matriz
P =
1 0 00 0 1
0 1 0

e´ uma matriz de permutac¸a˜o 3× 3.
Para qualquer matriz A 3× 3,
multiplicando a esquerda por P tem o efeito de trocar as linhas da
segunda e terceira coluna de A:
PA =
1 0 00 0 1
0 1 0
a1,1 a1,2 a1,3a2,1 a2,2 a2,3
a3,1 a3,2 a3,3
 =
a1,1 a1,2 a1,3a3,1 a3,2 a3,3
a2,1 a2,2 a2,3

Similarmente, multiplicar A a direita por P troca a segunda e ter-
ceiras colunas de A.
Obs. Importante!
P−1 existe e P−1 = P t
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A Matriz
P =
1 0 00 0 1
0 1 0

e´ uma matriz de permutac¸a˜o 3× 3. Para qualquer matriz A 3× 3,
multiplicando a esquerda por P tem o efeito de trocar as linhas da
segunda e terceira coluna de A:
PA =
1 0 00 0 1
0 1 0
a1,1 a1,2 a1,3a2,1 a2,2 a2,3
a3,1 a3,2 a3,3
 =
a1,1 a1,2 a1,3a3,1 a3,2 a3,3
a2,1 a2,2 a2,3

Similarmente, multiplicar A a direita por P troca a segunda e ter-
ceiras colunas de A.
Obs. Importante!
P−1 existe e P−1 = P t
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A Matriz
P =
1 0 00 0 1
0 1 0

e´ uma matriz de permutac¸a˜o 3× 3. Para qualquer matriz A 3× 3,
multiplicando a esquerda por P tem o efeito de trocar as linhas da
segunda e terceira coluna de A:
PA =
1 0 00 0 1
0 1 0
a1,1 a1,2 a1,3a2,1 a2,2 a2,3
a3,1 a3,2 a3,3
 =
a1,1 a1,2 a1,3a3,1 a3,2 a3,3
a2,1 a2,2 a2,3

Similarmente, multiplicar A a direita por P troca a segunda e ter-
ceiras colunas de A.
Obs. Importante!
P−1 existe e P−1 = P t
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A Matriz
P =
1 0 00 0 1
0 1 0

e´ uma matriz de permutac¸a˜o 3× 3. Para qualquer matriz A 3× 3,
multiplicando a esquerda por P tem o efeito de trocar as linhas da
segunda e terceira coluna de A:
PA =
1 0 00 0 1
0 1 0
a1,1 a1,2 a1,3a2,1 a2,2 a2,3
a3,1 a3,2 a3,3
 =
a1,1 a1,2 a1,3a3,1 a3,2 a3,3
a2,1 a2,2 a2,3

Similarmente, multiplicar A a direita por P troca a segunda e ter-
ceiras colunas de A.
Obs. Importante!
P−1 existe e P−1 = P t
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Mais cedo vimos que para qualquer matriz na˜o-singular A, o
sistema linear Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana com a possibilidade de troca de linhas
Se no´s conheceˆssemos as trocas de linhas necessa´rias para
resolver o sistema por eliminac¸a˜o Gaussiana, no´s poder´ıamos
arranjar as equac¸o˜es originais com o objetivo de assegurar que
nenhuma troca de linhas e´ necessa´ria
Portanto existe uma permutac¸a˜o das equac¸o˜es no sistema que
permite realizar a eliminac¸a˜o Gaussiana sem necessitar das
trocas de linhas
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Mais cedo vimos que para qualquer matriz na˜o-singular A, o
sistema linear Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana com a possibilidade de troca de linhas
Se no´s conheceˆssemos as trocas de linhas necessa´rias para
resolver o sistema por eliminac¸a˜o Gaussiana, no´s poder´ıamos
arranjar as equac¸o˜es originais com o objetivo de assegurar que
nenhuma troca de linhas e´ necessa´ria
Portanto existe uma permutac¸a˜o das equac¸o˜es no sistema que
permite realizar a eliminac¸a˜o Gaussiana sem necessitar das
trocas de linhas
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Mais cedo vimos que para qualquer matriz na˜o-singular A, o
sistema linear Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana com a possibilidade de troca de linhas
Se no´s conheceˆssemos as trocas de linhas necessa´rias para
resolver o sistema por eliminac¸a˜o Gaussiana, no´s poder´ıamos
arranjar as equac¸o˜es originais com o objetivo de assegurar que
nenhuma troca de linhas e´ necessa´ria
Portanto existe uma permutac¸a˜o das equac¸o˜es no sistema que
permite realizar a eliminac¸a˜o Gaussiana sem necessitar das
trocas de linhas
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Mais cedo vimos que para qualquer matriz na˜o-singular A, o
sistema linear Ax = b pode ser resolvido pela eliminac¸a˜o
Gaussiana com a possibilidade de troca de linhas
Se no´s conheceˆssemos as trocas de linhas necessa´rias para
resolver o sistema por eliminac¸a˜o Gaussiana, no´s poder´ıamos
arranjar as equac¸o˜es originais com o objetivo de assegurar que
nenhuma troca de linhas e´ necessa´ria
Portanto existe uma permutac¸a˜o das equac¸o˜es no sistema que
permite realizar a eliminac¸a˜o Gaussiana sem necessitar das
trocas de linhas
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Isto implica que para uma matriz na˜o-singular A, a matriz de
permutac¸a˜o exista para que o sistema:
PAx = Pb
possa ser resolvido sem troca de linhas. Como consequeˆncia,
esta matriz PA pode ser fatorada para a forma PA = LU .
Como P−1 = P t,esta produz uma fatorac¸a˜o do tipo:
A = P−1LU = (P tL)U
A matriz U ainda e´ a triangular superior, mas a matriz P tL
na˜o e´ mais uma triangular inferior, a menos que P = I
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Isto implica que para uma matriz na˜o-singular A, a matriz de
permutac¸a˜o exista para que o sistema:
PAx = Pb
possa ser resolvido sem troca de linhas. Como consequeˆncia,
esta matriz PA pode ser fatorada para a forma PA = LU .
Como P−1 = P t, esta produz uma fatorac¸a˜o do tipo:
A = P−1LU = (P tL)U
A matriz U ainda e´ a triangular superior, mas a matriz P tL
na˜o e´ mais uma triangular inferior, a menos que P = I
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Isto implica que para uma matriz na˜o-singular A, a matriz de
permutac¸a˜o exista para que o sistema:
PAx = Pb
possa ser resolvido sem troca de linhas. Como consequeˆncia,
esta matriz PA pode ser fatorada para a forma PA = LU .
Como P−1 = P t, esta produz uma fatorac¸a˜o do tipo:
A = P−1LU = (P tL)U
A matriz U ainda e´ a triangular superior, mas a matriz P tL
na˜o e´ mais uma triangular inferior, a menos que P = I
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Permutac¸a˜o de Matrizes e Eliminac¸a˜o de Gauss
Isto implica que para uma matriz na˜o-singular A, a matriz de
permutac¸a˜o exista para que o sistema:
PAx = Pb
possa ser resolvido sem troca de linhas. Como consequeˆncia,
esta matriz PA pode ser fatorada para a forma PA = LU .
Como P−1 = P t, esta produz uma fatorac¸a˜o do tipo:
A = P−1LU = (P tL)U
A matriz U ainda e´ a triangular superior, mas a matriz P tL
na˜o e´ mais uma triangular inferior, a menos que P = I
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
Determine a fatorac¸a˜o na forma A = (P tL)U para a matriz:
A =

0 0 −1 1
1 1 −1 2
−1 −1 2 0
1 2 0 2

OBS
A matrix A na˜o pode ser fatorada na forma LU pois a1,1 = 0
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
Determine a fatorac¸a˜o na forma A = (P tL)U para a matriz:
A =

0 0 −1 1
1 1 −1 2
−1 −1 2 0
1 2 0 2

OBS
A matrix A na˜o pode ser fatorada na forma LU pois a1,1 = 0
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
Entretando, usando a troca de linhas E1 ↔ E2, seguido por E3 ←
E3 + E1 e E4 ← E4 − E1 temos:
1 1 −1 2
0 0 −1 1
0 0 1 2
0 1 1 0

Enta˜o trocamos as linhas E2 ↔ E4 e fazemos E4 ← E4 + E3:
U =

1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3

Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
Entretando, usando a troca de linhas E1 ↔ E2, seguido por E3 ←
E3 + E1 e E4 ← E4 − E1 temos:
1 1 −1 2
0 0 −1 1
0 0 1 2
0 1 1 0

Enta˜o trocamos as linhas E2 ↔ E4 e fazemos E4 ← E4 + E3:
U =

1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3

Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A permutac¸a˜o associada com as trocas de linhas sa˜o E1 ↔ E2 e
E2 ↔ E4:
P =

0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0

e
PA =

1 1 −1 2
1 2 − 2
−1 −1 2 0
0 0 −1 1

Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A permutac¸a˜o associada com as trocas de linhas sa˜o E1 ↔ E2 e
E2 ↔ E4:
P =

0 1 0 0
0 0 0 1
0 0 1 0
1 0 0 0

e
PA =

1 1 −1 2
1 2 − 2
−1 −1 2 0
0 0 −1 1

Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A eliminac¸a˜o Gaussiana e´ realizada em PA usando as mesmas
operac¸o˜es que em A, exceto sem a troca de linhas
Isto e´: E2 ← E2 − E1, E3 ← E3 + E1 e E4 ← E3 + E4
Os multiplicadores na˜o-nulos por PA sa˜o consequentemente
m2,1 = 1;m3,1 = 1;m4,3 = −1
e a fatorac¸a˜o LU de PA e´:
PA =

1 0 0 0
1 1 0 0
−1 0 1 0
0 0 −1 1


1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3
 = LU
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A eliminac¸a˜o Gaussiana e´ realizada em PA usando as mesmas
operac¸o˜es que em A, exceto sem a troca de linhas
Isto e´: E2 ← E2 − E1, E3 ← E3 + E1 e E4 ← E3 + E4
Os multiplicadores na˜o-nulos por PA sa˜o consequentemente
m2,1 = 1;m3,1 = 1;m4,3 = −1
e a fatorac¸a˜o LU de PA e´:
PA =

1 0 0 0
1 1 0 0
−1 0 1 0
0 0 −1 1


1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3
 = LU
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A eliminac¸a˜o Gaussiana e´ realizada em PA usando as mesmas
operac¸o˜es que em A, exceto sem a troca de linhas
Isto e´: E2 ← E2 − E1, E3 ← E3 + E1 e E4 ← E3 + E4
Os multiplicadores na˜o-nulos por PA sa˜o consequentemente
m2,1 = 1;m3,1 = 1;m4,3 = −1
e a fatorac¸a˜o LU de PA e´:
PA =

1 0 0 0
1 1 0 0
−1 0 1 0
0 0 −1 1


1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3
 = LU
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
A eliminac¸a˜o Gaussiana e´ realizada em PA usando as mesmas
operac¸o˜es que em A, exceto sem a troca de linhas
Isto e´: E2 ← E2 − E1, E3 ← E3 + E1 e E4 ← E3 + E4
Os multiplicadores na˜o-nulos por PA sa˜o consequentemente
m2,1 = 1;m3,1 = 1;m4,3 = −1
e a fatorac¸a˜o LU de PA e´:
PA =

1 0 0 0
1 1 0 0
−1 0 1 0
0 0 −1 1


1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3
 = LU
Fatorac¸a˜o Matricial: Permutac¸a˜o Matricial
Exemplo
Multiplicando por P−1 = P t produz a fatorac¸a˜o:
A = P−1(LU) = P t(LU) = (P tL)U
=

0 0 −1 1
1 0 0 0
−1 0 1 0
1 1 0 0


1 1 −1 2
0 1 1 0
0 0 1 2
0 0 0 3
