MetodoLU (1)

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Cálculo Numérico
Prof. Aparecido J. de Souza
aparecidosouza@ci.ufpb.br
Sistemas Lineares - Método LU.
O método LU
Sistema Linear: Ax = b, em que:
An×n: Matriz quadrada inversível (posto máximo).
Decomposição LU:
A= LU, com L triangular inferior tal que lii = 1, i = 1,2, . . . ,n e
U triangular superior.
Daí Ax = b ⇐⇒ LUx = b ⇐⇒ L(Ux) = b
Faz-se y = Ux , resolve-se Ly = b obtendo y∗
e depois resolve-se Ux = y∗, obtendo x∗.
Teorema 1. Dada uma matriz quadrada n×n tal que os seus
menores principais sejam todos não nulos.
Então, existe uma única matriz triangular inferior L= (lij), com
lii = 1, i = 0, . . .n, e uma única matriz triangular superior
U= (uij) tais que A= LU. Além disto, det(A) = u11u22 · · ·unn.
A decomposição LU da matriz A
Pode-se obter L e U por eliminação de Gauss aplicada a A.
Por simplicidade de exposição suponha a eliminação de Gauss
simples (sem pivoteamento parcial) e que não são necessárias
trocas de linhas na escolha dos pivôs.
Ilustração para o caso de uma matriz A3×3.
A≡ A(0) ≡

a(0)11 a
(0)
12 a
(0)
13
a(0)21 a
(0)
22 a
(0)
23
a(0)31 a
(0)
32 a
(0)
33

Etapa k = 1: Pivô a(0)11 6= 0;
Multiplicadores: m21 = a
(0)
21 /a
(0)
11 e m31 = a
(0)
31 /a
(0)
11 .
A decomposição L U
. . .
Etapa k = 1:
Pivô a(0)11 6= 0; Multiplicadores m21 = a(0)21 /a(0)11 e m31 = a(0)31 /a(0)11 .
Daí
A(1) =

a(0)11 a
(0)
12 a
(0)
13
a(0)21 −m21a(0)11 = 0 a(0)22 −m21a(0)12 a(0)23 −m21a(0)13
a(0)31 −m31a(0)11 = 0 a(0)32 −m31a(0)12 a(0)33 −m31a(0)13

Definindo
M(0) =
 1 0 0−m21 1 0
−m31 0 1

então A(1) =M(0)A(0).
A decomposição L U
Etapa k = 1: A(1) =M(0)A(0). Isto é,
A(1) =

1 0 0
−m21 1 0
−m31 0 1


a(0)11 a
(0)
12 a
(0)
13
a(0)21 a
(0)
22 a
(0)
23
a(0)31 a
(0)
32 a
(0)
33
=

a(0)11 a
(0)
12 a
(0)
13
0 a(1)22 a
(1)
23
0 a(1)32 a
(1)
33

em que m21 = a
(0)
21 /a
(0)
11 e m31 = a
(0)
31 /a
(0)
11 .
Etapa k = 2: Pivô a(1)22 6= 0; Multiplicador m32 = a(1)32 /a(1)22 .
Definindo M(1) =
1 0 00 1 0
0 −m32 1
 , então
A(2) =M(1)A(1).
A decomposição L U
Etapa k = 2: A(2) =M(1)A(1). Isto é,
A(2) =

1 0 0
0 1 0
0 −m32 1


a(0)11 a
(0)
12 a
(0)
13
0 a(1)22 a
(1)
23
0 a(1)32 a
(1)
33
=

a(0)11 a
(0)
12 a
(0)
13
0 a(1)22 a
(1)
23
0 0 a(2)33
=U
em que m32 = a
(1)
32 /a
(1)
22 .
Assim, U= A(2) =M(1)A(1) =M(1)M(0)A(0) =M(1)M(0)A.
Portanto,
(
M(1)M(0)
)−1
U= A, ou seja,
A=
(
M(0)
)−1(
M(1)
)−1
U .
A decomposição L U
Portanto, A=
(
M(0)
)−1 (
M(1)
)−1
U com
M(0) =
 1 0 0−m21 1 0
−m31 0 1
, M(1) =
1 0 00 1 0
0 −m32 1
.
Mas
(
M(0)
)−1
=
 1 0 0m21 1 0
m31 0 1
 , (M(1))−1 =
1 0 00 1 0
0 m32 1
 .
Logo,
(
M(0)
)−1(
M(1)
)−1
=
 1 0 0m21 1 0
m31 m32 1
 = L.
A decomposição L U
Portanto, obtivemos A= LU, com
U=

a(0)11 a
(0)
12 a
(0)
13
0 a(1)22 a
(1)
23
0 0 a(2)33
=M(1)M(0)A ,
e com
L=
 1 0 0m21 1 0
m31 m32 1
= (M(0))−1(M(1))−1 ,
M(0) =
 1 0 0−m21 1 0
−m31 0 1
, M(1) =
1 0 00 1 0
0 −m32 1
.
A decomposição L U
Resumindo,
A= LU=

1 0 0
m21 1 0
m31 m32 1


a(0)11 a
(0)
12 a
(0)
13
0 a(1)22 a
(1)
23
0 0 a(2)33
 .
Obs. 1. Note que 0 6= det(A) = det(L)×det(U) = 1×
3
∏
k=1
a(k−1)kk .
Obs. 2. Uma outra forma de obter as matrizes L e U é montar
a própria equação A= LU e determinar as entradas de L e de
U. O resultado será o mesmo, pois o Teorema 1 garante que
elas são únicas.
A decomposição L U
Temos: A= LU, com L=
(
M(0)
)−1 (
M(1)
)−1
e U=M(1)M(0)A.
Assim, Ax = b ⇐⇒ LUx = b. Fazendo Ux = y , a solução do
sistema Ly = b é dada por
y∗ =
((
M(0)
)−1 (
M(1)
)−1)−1
b =M(1)M(0)b ≡ b(2).
Portanto, resolver o sistema Ux = y∗ significa resolver o próprio
sistema triangular superior obtido pelo processo de eliminação
de Gauss da matriz aumentada (A |b), pois ficamos com o
sistema Ux = b(2)!
Questão. Qual é então o benefício da decomposição LU?
A decomposição LU
Questão. Qual é então o benefício da decomposição LU?
Resposta. Por exemplo, no emprego de métodos iterativos
para aproximação de soluções de equações diferenciais é
comum na k−ésima iteração resolver um sistema linear
Ax = b(k) para obter x (k) e na (k +1)−ésima iteração
atualiza-se apenas o termo independente b(k) de tal sistema.
Então faz-se a decomposição LU uma única vez e da k−ésima
iterada para a seguinte faz-se b(k+1) =M(1)M(0)b(k) e
resolve-se recursivamente Ux = b(k+1) obtendo x (k+1).
A decomposição L U
Exemplo 1. (Ex. 5, Ruggiero&Lopes, pg. 138-141): Use a
decomposção LU para determinar a solução do sistema
3x1 +2x2 +4x3 = 1
x1 +x2 +2x3 = 2
4x1 +3x2 +2x3 = 3
.
Solução.
A(0) =
3 2 41 1 2
4 3 2
, b(0) =
12
3
.
Etapa k = 1. Pivô a(0)11 = 3. Multiplicadores: m21 =
1
3 e m31 =
4
3 .
M(0) =
 1 0 0−1/3 1 0
−4/3 0 1
, A(1) =M(0)A(0) =
3 2 40 1/3 2/3
0 1/3 −10/3
.
A decomposição L U
Exemplo 1 (cont.).
Etapa k = 1. Pivô a(0)11 = 3.
Multiplicadores: m21 = 13 e m31 =
4
3 .
M(0) =
 1 0 0−1/3 1 0
−4/3 0 1
, A(1) =M(0)A(0) =
3 2 40 1/3 2/3
0 1/3 −10/3
.
Etapa k = 2. Pivô a(0)22 = 1/3.
Multiplicador: m32 = 1.
M(1) =
1 0 00 1 0
0 −1 1
, A(2) =M(1)A(1) =
3 2 40 1/3 2/3
0 0 −4
≡ U
L=
 1 0 0m21 1 0
m31 m32 1
 =
 1 0 01/3 1 0
4/3 1 1
.
A decomposição L U
Exemplo 1 (cont.). A= LU, com
L=
 1 0 0m21 1 0
m31 m32 1
=
 1 0 01/3 1 0
4/3 1 1
 , U=
3 2 40 1/3 2/3
0 0 −4

M(0) =
 1 0 0−1/3 1 0
−4/3 0 1
, M(1) =
1 0 00 1 0
0 −1 1
.
Solução y∗ de Ly = b:
y∗ =M(1)M(0)b =
1 0 00 1 0
0 −1 1
 1 0 0−1/3 1 0
−4/3 0 1
12
3
= 15/3
0
.
A decomposição L U
Exemplo 1 (cont.). A= LU, com
L=
 1 0 0m21 1 0
m31 m32 1
=
 1 0 01/3 1 0
4/3 1 1
 , U=
3 2 40 1/3 2/3
0 0 −4

Solução y∗ de Ly = b: y∗ =M(1)M(0)b =
 15/3
0
.
Solução de Ux = y∗:
3x1 +2x2 +4x3 = 1
1
3x2 +
2
3 x3 =
5
3
−4x3 = 0.
Assim, x∗3 = 0, x
∗
2 = 3
(5
3 − 23(0)
)
= 5,
x∗1 =
1
3 (1−4(0)−2(5)) =−3.
A decomposição L U
Se usar o pivoteamento parcial, ou mesmo se algum
candidato a pivô se anular?
Deve-se levar em conta as permutações realizadas entre as
linhas da matriz aumentada (A|b), ou equivalentemente das
permutações realizada entre as equações do sistema Ax = b.