ufca

Decomposição LU
 Sem permutação
Considere um sistema Ax = b com n equações e n incógnitas
 Sem permutação
Considere um sistema Ax = b com n equações e n incógnitas

Por exemplo,
     
1 2 3 1 2 3 1 2 3
− 4L1 L3 = L3 − 7L1
4 5 6  L = L 2 2
0 −3 −6 0 −3 −6 
7 8 10 7 8 10 0 −6 −11
 
1 2 3
L3 = L3 − 2L2
0 −3 −6
0 0 1
 Sem permutação
Considere um sistema Ax = b com n equações e n incógnitas

Por exemplo,
     
1 2 3 1 2 3 1 2 3
− 4L1 L3 = L3 − 7L1
4 5 6  L = L 2 2
0 −3 −6 0 −3 −6 
7 8 10 7 8 10 0 −6 −11
 
1 2 3
L3 = L3 − 2L2
0 −3 −6
0 0 1
    
1 0 0 1 0 0 1 0 0 1 2 3
= 0 1 0  0 1 0 −4 1 0 4 5 6
0 −2 1 −7 0 1 0 0 1 7 8 10
 Sem permutação
Escrevamos
    
1 0 0 1 0 0 1 0 0 1 2 3
0 1 0  0 1 0 −4 1 0 4 5 6=
0 −2 1 −7 0 1 0 0 1 7 8 10
 
1 2 3
= E3 E2 E1 A = 0 −3 −6 = U
0 0 1
onde E3 , E2 e E1 são matrizes elementares
 Sem permutação
Escrevamos
    
1 0 0 1 0 0 1 0 0 1 2 3
0 1 0  0 1 0 −4 1 0 4 5 6=
0 −2 1 −7 0 1 0 0 1 7 8 10
 
1 2 3
= E3 E2 E1 A = 0 −3 −6 = U
0 0 1
onde E3 , E2 e E1 são matrizes elementares

Proposição. Toda matriz elementar possui inversa.

 Sem permutação
Escrevamos
    
1 0 0 1 0 0 1 0 0 1 2 3
0 1 0  0 1 0 −4 1 0 4 5 6=
0 −2 1 −7 0 1 0 0 1 7 8 10
 
1 2 3
= E3 E2 E1 A = 0 −3 −6 = U
0 0 1
onde E3 , E2 e E1 são matrizes elementares
A = (E3 E2 E1 )−1 U = LU
  
1 0 0 1 2 3
= 4 1 0 0 −3 −6
7 2 1 0 0 1
 Sem permutação
Escrevamos
    
1 0 0 1 0 0 1 0 0 1 2 3
0 1 0  0 1 0 −4 1 0 4 5 6=
0 −2 1 −7 0 1 0 0 1 7 8 10
 
1 2 3
= E3 E2 E1 A = 0 −3 −6 = U
0 0 1
onde E3 , E2 e E1 são matrizes elementares
A = (E3 E2 E1 )−1 U = LU
  
L2 = L2 − 4L1 1 0 0 1 2 3
L3 = L3 − 7L1 = 4 1 0 0 −3 −6
L3 = L3 − 2L2 7 2 1 0 0 1
 Sem permutação
Portanto, supondo que é possı́vel escalonar A sem a
necessidade de permutações, teremos
1 L=I
2 U=A
3 for k = 1 to n − 1
4 for i = k + 1 to n
5 `ik = uik /ukk
6 for j = k + 1 to n
7 uij = uij − `ik ukj
8 uik = 0
 Sem permutação
Portanto, supondo que é possı́vel escalonar A sem a
necessidade de permutações, teremos
1 L=I
2 U=A
3 for k = 1 to n − 1
4 for i = k + 1 to n
5 `ik = uik /ukk
6 for j = k + 1 to n
7 uij = uij − `ik ukj
8 uik = 0

Teorema. Sob esta hipótese, a decomposição LU é única

 Resolvendo um sistema usando A = LU
Dados Ax = b e a fatoração A = LU, resolvemos o sistema
em duas etapas:

1) Ly = b
2) Ux = y

Resolver Ly = b requer uma substituição progressiva, ao

passo que Ux = y é resolvido por substituição regressiva (ou
retrosubstituição)
Substituição progressiva
1 y1 = b1
2 for i = 2 to n
3 s = bi
4 for j = 1 to i − 1
5 s = s − `ij yj
6 yi = s
 LU com pivotamento simples
Considere a matriz
 
0 1 −1 1
1
 1 −1 2 

−1 −1 1 0
1 2 0 2
 LU com pivotamento simples
Considere a matriz
 
0 1 −1 1
1
 1 −1 2 
 L2 ⇐⇒ L1
−1 −1 1 0
1 2 0 2 P1
 LU com pivotamento simples
Considere a matriz
L=I
 
0 1 −1 1
 
1 0 0 0
1
 1 −1 2 
 L2 ⇐⇒ L1
0
 1 0 0
−1 −1 1 0 0 0 1 0
P1 0 0 0 1
1 2 0 2
 
1 1 −1 2
0
 1 −1 1
−1 −1 1 0
1 2 0 2
 LU com pivotamento simples
Considere a matriz
L=I
 
0 1 −1 1
 
1 0 0 0
sem
1
 1 −1 2 
 L2 ⇐⇒ L1 troca
0
 1 0 0
−1 −1 1 0 0 0 1 0
em L
P1 0 0 0 1
1 2 0 2
 
1 1 −1 2
0
 1 −1 1
−1 −1 1 0
1 2 0 2
 LU com pivotamento simples
Considere a matriz
L=I
 
0 1 −1 1
 
1 0 0 0
1
 1 −1 2 
 L2 ⇐⇒ L1
0
 1 0 0
−1 −1 1 0 0 0 1 0
P1 0 0 0 1
1 2 0 2
 
1 1 −1 2 L2 = L2 − (0/1) · L1
0
 1 −1 1
 L3 = L3 − (−1/1) · L1
−1 −1 1 0
1 2 0 2 L4 = L4 − (1/1) · L1
E1
 LU com pivotamento simples
Considere a matriz
L=I
 
0 1 −1 1
 
1 0 0 0
1
 1 −1 2 
 L2 ⇐⇒ L1
0
 1 0 0
−1 −1 1 0 0 0 1 0
P1 0 0 0 1
1 2 0 2
L = E−1
   1
1 1 −1 2 L2 = L2 − (0/1) · L1

1 0 0 0
0
 1 −1 1
 L3 = L3 − (−1/1) · L1
0
 1 0 0

−1 −1 1 0 −1 0 1 0
1 2 0 2 L4 = L4 − (1/1) · L1 1 0 0 1
E1
 LU com pivotamento simples

  (P2 = I) L = P2 E−1
1 P2 E−1
2
1 1 −1 2 
1 0 0 0

0 1 −1 1 L3 = L3 − (0/1) · L2 0 1 0 0
 
L4 = L4 − (1/1) · L2
 
0 0 0 2 −1 0 1 0
0 1 1 0 E2 1 1 0 1
 
1 1 −1 2
0
 1 −1 1
0 0 0 2
0 0 2 −1
 LU com pivotamento simples

  (P2 = I) L = P2 E−1
1 P2 E−1
2
1 1 −1 2 
1 0 0 0

0 1 −1 1 L3 = L3 − (0/1) · L2 0 1 0 0
 
L4 = L4 − (1/1) · L2
 
0 0 0 2 −1 0 1 0
0 1 1 0 E2 1 1 0 1
 
1 1 −1 2 
1 0 0 0

0
 1 −1 1 L3 ⇐⇒ L4 0
 1 0 0

0 0 0 2 −1 0 1 0
P3 1 1 0 1
0 0 2 −1
(E3 = I)

L = P3 P2 E−1
1 P2 E−1
2 P 3 E−1
3
 LU com pivotamento simples

  (P2 = I) L = P2 E−1
1 P2 E−1
2
1 1 −1 2 
1 0 0 0

0 1 −1 1 L3 = L3 − (0/1) · L2 0 1 0 0
 
L4 = L4 − (1/1) · L2
 
0 0 0 2 −1 0 1 0
0 1 1 0 E2 1 1 0 1
 
1 1 −1 2 
1 0 0 0

0
 1 −1 1 L3 ⇐⇒ L4 0
 1 0 0

0 0 0 2 −1 0 1 0
P3 1 1 0 1
0 0 2 −1
  (E3 = I)
−1
 
1 1 2 1 0 0 0
0 1 −1 1 0 1 0 0
 
  1 1 1 0
0 0 2 −1
−1 0 0 1
0 0 0 2
L = P3 P2 E−1
1 P2 E−1
2 P 3 E−1
3
 LU com pivotamento simples
Observe que neste exemplo fizemos o seguinte
E3 P3 E2 P2 E1 P1 A = U
 LU com pivotamento simples
Observe que neste exemplo fizemos o seguinte
E3 P3 E2 P2 E1 P1 A = U

E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )(P3 P2 P1 )A = U

 LU com pivotamento simples
Observe que neste exemplo fizemos o seguinte
E3 P3 E2 P2 E1 P1 A = U

E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )(P3 P2 P1 )A = U

−1
(P3 P2 P1 )A = (E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )) U
 LU com pivotamento simples
Observe que neste exemplo fizemos o seguinte
E3 P3 E2 P2 E1 P1 A = U

E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )(P3 P2 P1 )A = U

−1
(P3 P2 P1 )A = (E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )) U

(P3 P2 P1 )A = P3 P2 E−1
1 P E−1
2 2 P −1
3 3 U
E
 LU com pivotamento simples
Observe que neste exemplo fizemos o seguinte
E3 P3 E2 P2 E1 P1 A = U

E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )(P3 P2 P1 )A = U

−1
(P3 P2 P1 )A = (E3 (P3 E2 P3 )(P3 P2 E1 P2 P3 )) U

(P3 P2 P1 )A = P3 P2 E−1
1 P E−1
2 2 P −1
3 3 U
E

PA = P3 P2 E−1
1 P E−1
2 2 P −1
3 3 U = LU
E
 Resolvendo o sistema
Dados Ax = b e a fatoração PA = LU, resolvemos o sistema
em duas etapas:

1) Ly = Pb
2) Ux = y