Fatoração LU em Sistemas Lineares

Prévia do material em texto

104 Cálculo Numérico
Exemplo 4.4.1. Use a fatoração LU para resolver o seguinte sistema linear:
x1 + x2 + x3 = −2
2x1 + x2 − x3 = 1
2x1 − x2 + x3 = 3
(4.70)
Solução. Começamos fatorando a matriz A dos coeficientes deste sistema:
A =

1 1 1
2 1 −1
2 −1 1
 . =

1 0 0
0 1 0
0 0 1

︸ ︷︷ ︸
I3,3

1 1 1
2 1 −1
2 −1 1

︸ ︷︷ ︸
A
(4.71)
=

1 0 0
2 1 0
2 0 1


1 1 1
0 −1 −3
0 −3 −1
 (4.72)
=

1 0 0
2 1 0
2 3 1

︸ ︷︷ ︸
L

1 1 1
0 −1 −3
0 0 8

︸ ︷︷ ︸
U
(4.73)
(4.74)
Completada a fatoração LU, resolvemos, primeiramente, o sistema Ly = b:
y1 = −2
2y1 + y2 = 1
2y1 + 3y2 + y3 = 3
(4.75)
o qual no fornece y1 = −2, y2 = 5 e y3 = −8. Por fim, obtemos a solução
resolvendo o sistema Ux = y:
x1 + x2 + x3 = −2
−x2 − 3x3 = 5
8x3 = −8
(4.76)
o qual fornece x3 = −1, x2 = −2 e x1 = 1. ♦
Licença CC-BY-SA-3.0. Contato: reamat@ufrgs.br
https://creativecommons.org/licenses/by-sa/3.0/
reamat@ufrgs.br
4.4. FATORAÇÃO LU 105
4.4.1 Código Python: Fatoração LU
Em Python, podemos implementar o algoritmo para fatoração LU da seguinte
forma:
def fatoraLU(A):
U = np.copy(A)
n = np.shape(U)[0]
L = np.eye(n)
for j in np.arange(n-1):
for i in np.arange(j+1,n):
L[i,j] = U[i,j]/U[j,j]
for k in np.arange(j+1,n):
U[i,k] = U[i,k] - L[i,j]*U[j,k]
U[i,j] = 0
return L, U
Observação 4.4.1. O custo computacional do algoritmo da fatoração LU é
2n3
3 −
n2
2 −
n
6 flops. (4.77)
4.4.2 Custo computacional para resolver um sistema linear
usando fatoração LU
Para calcularmos o custo computacional de um algoritmo completo, uma es-
tratégia é separar o algoritmo em partes menores, mais fáceis de analisar.
Para resolver o sistema, devemos primeiro fatorar a matriz A nas matrizes L e
U . Vimos que o custo é
2n3
3 −
n2
2 −
n
6 flops. (4.78)
Depois devemos resolver os sistemas Ly = b e Ux = y. O custo de resolver os
dois sistemas é (devemos contar duas vezes)
2n2 flops. (4.79)
Somando esses 3 custos, temos que o custo para resolver um sistema linear
usando fatoração LU é
2n3
3 + 3n2
2 −
n
6 flops. (4.80)
Quando n cresce, prevalessem os termos de mais alta ordem, ou seja,
O(2n3
3 + 3n2
2 −
n
6 ) = O(2n3
3 + 3n2
2 ) = O(2n3
3 ) (4.81)
Licença CC-BY-SA-3.0. Contato: reamat@ufrgs.br
https://creativecommons.org/licenses/by-sa/3.0/
reamat@ufrgs.br
	Solução de sistemas lineares
	Fatoração LU
	Código Python: Fatoração LU
	Custo computacional para resolver um sistema linear usando fatoração LU