Decomposição Lu

Ver Todos os Exercícios

Teoria

A decomposição LU, também conhecida como fatoração LU é um método para resolução de sistemas lineares que vai facilitar muito a nossa vida!

📢 Clique para ver mais:

Resolução de Sistemas Lineares usando a Decomposição LU

Eu vou te explicar rapidinho o passo a passo do método de fatoração LU e depois a gente vai resolver alguns exercícios pra fixar, beleza?!

Então considera o seguinte sistema linear:

Concorda comigo que a gente pode escrever o sistema linear acima na forma de uma matriz quadrada :

Agora a gente vai usar o Método de Gauss , então calculamos os multiplicadores :

E chegamos na matriz , que é uma matriz triangular superior:

Agora a gente pega os multiplicadores que calculamos ali em cima e escrevemos a matriz :

Depois de fazermos isso, teremos duas matrizes triangulares tal que :

Ou seja, ideia na decomposição LU é fatorar a matriz A em um produto de matrizes LU, onde L é uma matriz triangular inferior e U é uma matriz triangular superior. Facilitando muito as contas! 🤩

Aplicações da fatoração LU

A fatoração LU tem várias aplicações pra a gente! Entre elas o cálculo de determinante, a inversa de uma matriz e a resolução de sistemas lineares. No vídeo abaixo você pode conferir como usar decomposição LU pra resolver esses problemas!

Algoritmo

Podemos dividir esse algoritmo em três fases bem distintas! Se liga:

Fase 1: Eliminação de Gauss

  • Dados iniciais: Definir a matriz quadrada
  • Definimos uma matriz com apenas na diagonal e atribuímos à variável .
  • Definimos
  • Percorremos as linhas de com uma variável (de a ).
  • Escolher pivô da i-ésima linha de e armazenar na variável . O pivô será sempre o i-ésimo número da i-ésima linha.
  • Para cada , percorremos as linhas de de até com uma variável .
  • Definimos o multiplicador .
  • Guardar na posição linha e coluna de .
  • Para cada , percorremos as colunas de de até com uma variável .

Pronto, tá feito o nosso algoritmo. Daí vamos tirar nossas matrizes e . Agora precisamos criar um algoritmo para a substituição simples.

Fase 2: Receber a matriz vinda da Fase e o vetor para resolver o sistema

  • Dados iniciais:
    • Matriz quadrada triangular
    • Vetor solução
  • Enquanto $j
  • Enquanto , repetimos os Passos ao . Quando , temos a nossa resposta que pode ser dada em forma de uma lista .


Para a Fase 3 teremos exatamente o mesmo algoritmo da retrosubstituição. Só iremos alterar as entradas.

Fase 3: Recebe o resultado da fase , o vetor , e a matriz da Fase

  • Dados iniciais:
    • Matriz quadrada triangular
    • Vetor solução
  • Enquanto $j
  • Enquanto , repetimos os Passos ao . Quando , temos a nossa resposta que pode ser dada em forma de uma lista .

Aplicações da fatoração LU

Algoritmo

Exercícios Resolvidos

Exercício Resolvido #1

Resolva os seguintes sistemas lineares:

a 1 0 0 2 1 0 - 1 0 1 2 3 - 1 0 - 2 1 0 0 3 x 1 x 2 x 3 = 2 - 1 1

b 2 0 0 - 1 1 0 3 2 - 1 1 1 1 0 1 2 0 0 1 x 1 x 2 x 3 = - 1 3 0

Passo 1

a Vamos dividir esse sistema em 2 :

I   1 0 0 2 1 0 - 1 0 1 y 1 y 2 y 3 = 2 - 1 1

I I   2 3 - 1 0 - 2 1 0 0 3 x 1 x 2 x 3 = y 1 y 2 y 3

Passo 2

Resolvendo o sistema I :

1 0 0 2 1 0 - 1 0 1 y 1 y 2 y 3 = 2 - 1 1

y 1 = 2

2 ∙ 2 + y 2 = - 1

y 2 = - 5

- 2 + y 3 = 1

y 3 = 3

Passo 3

Resolvendo o sistema I I :

2 3 - 1 0 - 2 1 0 0 3 x 1 x 2 x 3 = 2 - 5 3

3 x 3 = 3

x 3 = 1

- 2 x 2 + 1 = - 5

x 2 = 3

2 x 1 + 3 ∙ 3 - 1 = 2

x 1 = - 3

Então a solução do sistema é x 1 , x 2 , x 3 = - 3 , 3,1 .

Passo 4

b Novamente, dividimos esse sistema em 2 :

I   2 0 0 - 1 1 0 3 2 - 1 y 1 y 2 y 3 = - 1 3 0

I I   1 1 1 0 1 2 0 0 1 x 1 x 2 x 3 = y 1 y 2 y 3

Passo 5

Resolvendo o sistema I :

2 0 0 - 1 1 0 3 2 - 1 y 1 y 2 y 3 = - 1 3 0

2 y 1 = - 1

y 1 = - 1 2

1 2 + y 2 = 3

y 2 = 5 2

- 3 2 + 5 - y 3 = 0

y 3 = 7 2

Passo 6

Resolvendo o sistema I I :

1 1 1 0 1 2 0 0 1 x 1 x 2 x 3 = - 0.5 2.5 3.5

x 3 = 3.5

x 2 + 7 = 2.5

x 2 = - 4.5

x 1 - 4.5 + 3.5 = - 0.5

x 1 = 0.5

Então a solução do sistema é x 1 , x 2 , x 3 = 0.5 , - 4.5,3.5 .

Resposta

a   x 1 , x 2 , x 3 = - 3,3 , 1

b x 1 , x 2 , x 3 = 0.5 , - 4.5,3.5

Exercício Resolvido #2

Calcule a fatoração L U de A , se possível:

A = 1 1 1 2 1 - 1 3 2 0

Passo 1

Para obtermos a fatoração L U precisamos aplicar a eliminação de Gauss e guardar os multiplicadores. Por enquanto temos que:

L = 1 0 0 m 21 1 0 m 31 m 32 1

U = * * * 0 * * 0 0 *

Passo 2

Aplicando a Eliminação de Gauss:

1 1 1 2 1 - 1 3 2 0

L 2 ← L 2 - 2 L 1 m 21 = 2 :

1 1 1 0 - 1 - 3 3 2 0

L 3 ← L 3 - 3 L 1 m 31 = 3 :

1 1 1 0 - 1 - 3 0 - 1 - 3

L 3 ← L 3 - L 2 m 32 = 1 :

1 1 1 0 - 1 - 3 0 0 0

Passo 3

Ou seja, temos que:

L = 1 0 0 2 1 0 3 1 1 ; U = 1 1 1 0 - 1 - 3 0 0 0

Resposta

L = 1 0 0 2 1 0 3 1 1 ; U = 1 1 1 0 - 1 - 3 0 0 0

Exercício Resolvido #3

Calcule a fatoração L U das seguintes matrizes:

a 2 - 1 1 3 3 9 3 3 5

b 1.012 - 2.132 3.104 - 2.132 4.096 - 7.013 3.104 - 7.013 0.014

c 2 0 0 0 1 1.5 0 0 0 - 3 0.5 0 2 - 2 1 1

Passo 1

a Para obtermos a fatoração L U precisamos aplicar a eliminação de Gauss e guardar os multiplicadores. Por enquanto temos que:

L = 1 0 0 m 21 1 0 m 31 m 32 1

U = * * * 0 * * 0 0 *

Passo 2

Aplicando a Eliminação de Gauss:

2 - 1 1 3 3 9 3 3 5

L 2 ← L 2 - 3 2 L 1 m 21 = 3 2 :

2 - 1 1 0 4.5 7.5 3 3 5

L 3 ← L 3 - 3 2 L 1 m 31 = 3 2 :

2 - 1 1 0 4.5 7.5 0 4.5 3.5

L 3 ← L 3 - L 2 m 32 = 1 :

2 - 1 1 0 4.5 7.5 0 0 - 4

Passo 3

Ou seja, temos que:

L = 1 0 0 1.5 1 0 1.5 1 1 ; U = 2 - 1 1 0 4.5 7.5 0 0 - 4

Passo 4

b Para obtermos a fatoração L U precisamos aplicar a eliminação de Gauss e guardar os multiplicadores. Por enquanto temos que:

L = 1 0 0 m 21 1 0 m 31 m 32 1

U = * * * 0 * * 0 0 *

Passo 5

Aplicando a Eliminação de Gauss:

1.012 - 2.132 3.104 - 2.132 4.096 - 7.013 3.104 - 7.013 0.014

L 2 ← L 2 - - 2.107 L 1 m 21 = - 2.107 :

1.012 - 2.132 3.104 0 - 0.396 - 0.474 3.104 - 7.013 0.014

L 3 ← L 3 - 3.067 L 1 m 31 = 3.067 :

1.012 - 2.132 3.104 0 - 0.396 - 0.474 0 - 0.474 - 9.507

L 3 ← L 3 - 1.198 L 2 m 32 = 1.198 :

1.012 - 2.132 3.104 0 - 0.396 - 0.474 0 0 - 8.939

Passo 6

Ou seja, temos que:

L = 1 0 0 - 2.107 1 0 3.067 1.198 1 ; U = 1.012 - 2.132 3.104 0 - 0.396 - 0.474 0 0 - 8.939

Passo 7

c Para obtermos a fatoração L U precisamos aplicar a eliminação de Gauss e guardar os multiplicadores. Por enquanto temos que:

L = 1 0 0 0 m 21 1 0 0 m 31 m 32 1 0 m 41 m 42 m 43 1

U = * * * * 0 * * * 0 0 * * 0 0 0 *

Passo 8

Aplicando a Eliminação de Gauss:

2 0 0 0 1 1.5 0 0 0 - 3 0.5 0 2 - 2 1 1

L 2 ← L 2 - 0.5 L 1 m 21 = 0.5 :

2 0 0 0 0 1.5 0 0 0 - 3 0.5 0 2 - 2 1 1

L 4 ← L 4 - L 1 m 4 1 = 1 :

2 0 0 0 0 1.5 0 0 0 - 3 0.5 0 0 - 2 1 1

L 3 ← L 3 - - 2 L 2 m 32 = - 2 :

2 0 0 0 0 1.5 0 0 0 0 0.5 0 0 - 2 1 1

L 4 ← L 4 - - 4 3 L 2 m 4 2 = - 4 3 :

2 0 0 0 0 1.5 0 0 0 0 0.5 0 0 0 1 1

L 4 ← L 4 - 2 L 2 m 43 = 2 :

2 0 0 0 0 1.5 0 0 0 0 0.5 0 0 0 0 1

Passo 9

Ou seja, temos que:

L = 1 0 0 0 0.5 1 0 0 0 - 2 1 0 1 - 4 3 2 1 ; U = 2 0 0 0 0 1.5 0 0 0 0 0.5 0 0 0 0 1

Resposta

a L = 1 0 0 1.5 1 0 1.5 1 1 ; U = 2 - 1 1 0 4.5 7.5 0 0 - 4  

b L = 1 0 0 - 2.107 1 0 3.067 1.198 1 ; U = 1.012 - 2.132 3.104 0 - 0.396 - 0.474 0 0 - 8.939

c   L = 1 0 0 0 0.5 1 0 0 0 - 2 1 0 1 - 4 3 2 1 ; U = 2 0 0 0 0 1.5 0 0 0 0 0.5 0 0 0 0 1

Exercício Resolvido #4

Resolva o seguinte sistema A x = b usando decomposição L U , sendo

A = 1 - 4 1 1

i b = 2 1 T

i i b = 1 - 1 T

Passo 1

Vamos começar decompondo A :

1 - 4 1 1

L 2 ← L 2 - L 1   m 21 = 1 :

1 - 4 0 5

Então temos:

L = 1 0 1 1 ; U = 1 - 4 0 5

Passo 2

i Precisamos resolver o sistema:

1 0 1 1 1 - 4 0 5 x 1 x 2 = 2 1

Resolvendo L y = b :

1 0 1 1 y 1 y 2 = 2 1

y 1 = 2

2 + y 2 = 1

y 2 = - 1

Agora resolvemos U x = y :

1 - 4 0 5 x 1 x 2 = 2 - 1

5 x 2 = - 1

x 2 = - 0.2

x 1 + 0.8 = 2

x 1 = 1.2

Então a solução é x 1 , x 2 = 1.2 , - 0.2 .

Passo 3

i i Agora queremos resolver:

1 0 1 1 1 - 4 0 5 x 1 x 2 = 1 - 1

Repare que a decomposição continua a mesma, só trocamos o vetor b !

Resolvendo L y = b :

1 0 1 1 y 1 y 2 = 1 - 1

y 1 = 1

1 + y 2 = - 1

y 2 = - 2

Agora resolvemos U x = y :

1 - 4 0 5 x 1 x 2 = 1 - 2

5 x 2 = - 2

x 2 = - 0 . 4

x 1 + 1.6 = 1

x 1 = - 0.6

Então a solução é x 1 , x 2 = - 0.6 , - 0.4 .

Resposta

a x 1 , x 2 = 1.2 , - 0.2

b x 1 , x 2 = - 0.6 , - 0.4

Exercício Resolvido #5

Resolva os seguintes sistemas usando a fatoração L U .

a x 1 - x 2     = 2 2 x 1 + 2 x 2 + 3 x 3 = - 1 - x 1 + 3 x 2 + 2 x 3 = 4

b 1 3 x 1 + 1 2 x 2 - 1 4 x 3 = 1 1 3 x 1 + 2 3 x 2 + 3 8 x 3 = 2 2 5 x 1 - 2 3 x 2 + 5 8 x 3 = - 3

c 2 x 1 + x 2         = 0 - x 1 + 3 x 2 + 3 x 3     = 5 2 x 1 - 2 x 2 + x 3 + 4 x 4 = - 2 - 2 x 1 + 2 x 2 + 2 x 3 + 5 x 4 = 6