Responde Aí
Acesse com GoogleAcesse com AppleAcesse com Facebook

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

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 409, exercício 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

Márcia A. Gomes Ruggiero e Vera Lúcia da Rocha Lopes, Cálculo Numérico – Aspectos Teóricos e Computacionais, 2ª ed. São Paulo: MAKRON Books, 1996, pag 183, exercício 10.

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

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 410, exercício 5.

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

Lista 4 – Professora Suzana – Questão 6

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

Richard L. Burden e J. Douglas Faires, Numerical Analysis, 9ª ed. Brooks/Cole, Cengage Learning, pag 410, exercício 8.

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

Passo 1

a Passando para a forma matricial:

1 - 1 0 2 2 3 - 1 3 2 x 1 x 2 x 3 = 2 - 1 4

E 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 0 2 2 3 - 1 3 2

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

1 - 1 0 0 4 3 - 1 3 2

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

1 - 1 0 0 4 3 0 2 2

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

1 - 1 0 0 4 3 0 0 0.5

Passo 3

Ou seja, temos que:

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

Ficamos então com:

1 0 0 2 1 0 - 1 0.5 1 1 - 1 0 0 4 3 0 0 0.5 x 1 x 2 x 3 = 2 - 1 4

Passo 4

Resolvendo o sistema L y = b :

1 0 0 2 1 0 - 1 0.5 1 y 1 y 2 y 3 = 2 - 1 4

y 1 = 2

4 + y 2 = - 1

y 2 = - 5

- 2 - 2.5 + y 3 = 4

y 3 = 8.5

Resolvendo U x = y :

1 - 1 0 0 4 3 0 0 0.5 x 1 x 2 x 3 = 2 - 5 8.5

x 3 = 17

4 x 2 + 51 = - 5

x 2 = - 14

x 1 + 14 = 2

x 1 = - 12

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

Passo 5

b Passando para a forma matricial:

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

E temos que:

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

U = * * * 0 * * 0 0 *

Passo 6

Aplicando a Eliminação de Gauss:

1 3 1 2 - 1 4 1 3 2 3 3 8 2 5 - 2 3 5 8

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

1 3 1 2 - 1 4 0 1 6 5 8 2 5 - 2 3 5 8

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

0.333 0.5 - 0.25 0 0.167 0.625 0 - 1.267 0.925

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

0.333 0.5 - 0.25 0 0.167 0.625 0 0 5.675

Passo 7

Ou seja, temos que:

L = 1 0 0 1 1 0 1.2 - 7.6 1 ; U = 0.333 0.5 - 0.25 0 0.167 0.625 0 0 5.675

Ficamos então com:

1 0 0 1 1 0 1.2 - 7.6 1 0.333 0.5 - 0.25 0 0.167 0.625 0 0 5.675 x 1 x 2 x 3 = 1 2 - 3

Passo 8

Resolvendo o sistema L y = b :

1 0 0 1 1 0 1.2 - 7.6 1 y 1 y 2 y 3 = 1 2 - 3

y 1 = 1

1 + y 2 = 2

y 2 = 1

1.2 - 7.6 + y 3 = - 3

y 3 = 3.4

Resolvendo U x = y :

0.333 0.5 - 0.25 0 0.167 0.625 0 0 5.675 x 1 x 2 x 3 = 1 1 3.4

x 3 = 0.599

0.167 x 2 + 0.373249 = 1

x 2 = 3.753

0.333 x 1 + 1.8765 - 0.14975 = 1

x 1 = - 2.181

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

Passo 9

c Passando para a forma matricial:

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

E 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 10

Aplicando a Eliminação de Gauss:

2 1 0 0 - 1 3 3 0 2 - 2 1 4 - 2 2 2 5

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

2 1 0 0 0 3.5 3 0 2 - 2 1 4 - 2 2 2 5

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

2 1 0 0 0 3.5 3 0 0 - 3 1 4 - 2 2 2 5

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

2 1 0 0 0 3.5 3 0 0 - 3 1 4 0 3 2 5

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

2 1 0 0 0 3.5 3 0 0 0 3.571 4 0 3 2 5

L 4 ← L 4 - 0.857 L 2 m 42 = 0.857 :

2 1 0 0 0 3.5 3 0 0 0 3.571 4 0 0 - 0.571 5

L 4 ← L 4 - - 0.16 L 3 m 43 = - 0.16 :

2 1 0 0 0 3.5 3 0 0 0 3.571 4 0 0 0 5.64

Passo 11

Ou seja, temos que:

L = 1 0 0 0 - 0.5 1 0 0 1 - 0.857 1 0 - 1 0.857 - 0.16 1 ; U = 2 1 0 0 0 3.5 3 0 0 0 3.571 4 0 0 0 5.64

Ficamos então com:

1 0 0 0 - 0.5 1 0 0 1 - 0.857 1 0 - 1 0.857 - 0.16 1 2 1 0 0 0 3.5 3 0 0 0 3.571 4 0 0 0 5.64 x 1 x 2 x 3 x 4 = 0 5 - 2 6

Passo 12

Resolvendo o sistema L y = b :

1 0 0 0 - 0.5 1 0 0 1 - 0.857 1 0 - 1 0.857 - 0.16 1 y 1 y 2 y 3 y 4 = 0 5 - 2 6

y 1 = 0

y 2 = 5

- 4.286 + y 3 = - 2

y 3 = 2.286

4.286 - 0.366 + y 4 = 6

y 4 = 2.08

Resolvendo U x = y :

2 1 0 0 0 3.5 3 0 0 0 3.571 4 0 0 0 5.64 x 1 x 2 x 3 x 4 = 0 5 2.286 2.08

x 4 = 0.369

3.571 x 3 + 1.476 = 2.286

x 3 = 0.227

3.5 x 2 + 0.681 = 5

x 2 = 1.234

2 x 1 + 1.234 = 0

x 1 = - 0.617

Então a solução do sistema é x 1 , x 2 , x 3 , x 4 = - 0.617,1.234,0.227,0.369 .

Resposta

a x 1 , x 2 , x 3 = - 12 , - 14,17

b x 1 , x 2 , x 3 = - 2.181,3.753,0.599

c   x 1 , x 2 , x 3 , x 4 = - 0.617,1.234,0.227,0.369

Exercícios de Livros Relacionados

O vetor p que armazena a informação sobre as permutações realzadas durante a fatoração LU pode ser construído como p k = i , se na etapa k a linha i da matriz A ( k - 1 ) for escolhida como a linha pi
Se A = L D U , como fica a resolução de A x = b ?
Mostre que, se A é matriz não singular e A = L U , então A = L D U → , onde D é matriz diagonal U → matriz triangular superior com diagonal unitária.
Mostre que se A é uma matriz simétrica e satisfaz as hipóteses da decomposição L U então A = L D U implica U = L t (transposta de L ).
Mostre que se A é uma matriz simétrica, positiva definida e satisfaz as hipóteses da decomposição L U então A = L D L t onde os elementos diagonais de D são todos positivos.