Fatoração PLU

Teoria Completa

Lembra de quando vimos as técnicas de pivoteamento que iriam resolver aquele problema da eliminação de Gauss?

Então, na fatoração L U nós precisamos aplicar a eliminação de Gauss, ou seja, novamente podemos ter o problema de um pivô ser igual ou muito próximo de zero! E é aí que entra a fatoração P L U , que é simplesmente a fatoração L U com o pivoteamento!

A única diferença é que só vamos estudar o pivoteamento parcial (que bom né!). O que acontece agora é que teremos uma terceira matriz P que guardará essa informação da troca de linhas. Daí o nome fatoração P L U .

E como obtemos essa matriz P ? É bem simples na verdade, é só pegarmos a matriz identidade e fazermos as mesmas trocas de linha que fizermos durante a eliminação de Gauss só que de trás pra frente. É como se tivéssemos desfazendo as trocas. Vamos ver um exemplo 3 × 3 :

1 3 4 5 2 7 - 2 1 - 9

Aplicando o pivoteamento parcial, fazemos L 1 ↔ L 2 :

5 2 7 1 3 4 - 2 1 - 9

E a matriz de pivoteamento P será dada por:

0 1 0 1 0 0 0 0 1

Que é exatamente a matriz identidade com as primeiras duas linhas trocadas. Se mais alguma troca tivesse sido feita depois teríamos de aplicar essa última troca primeiro para dar certo!

Então, seja o sistema linear A x = b , temos:

P L U x = b

L U x = P - 1 b

Onde P - 1 é a inversa de P , que é obtida simplesmente fazendo as mudanças de linhas na matriz identidade na mesma ordem em que fizemos no escalonamento. Ou seja, para obtermos a matriz P da fatoração P L U aplicamos as mudanças de linha na ordem inversa. Se quisermos resolver o sistema encontramos P - 1 aplicando as mudanças de linha na ordem certa. Assim, precisamos resolver dois sistemas triangulares:

L y = P - 1 b

U x = y

E assim vamos obter a solução x do nosso sistema.

Obs.: O chato aqui é que se forem feitas trocas de linhas no depois de já termos definido parte da matriz L , esta será alterada. Então eu recomendo ir completando a matriz L junto da eliminação de Gauss, só não pode aplicar o escalonamento nos multiplicadores sem querer! Vai ficar mais claro no exemplo:

Encontre a fatoração P L U do sistema abaixo:

x 1 + x 2 + x 3 = 1 x 1 - x 2 + x 3 = 2 2 x 1 + x 2 - x 3 = 3

Passando para a forma matricial:

1 1 1 1 - 1 1 2 1 - 1 x 1 x 2 x 3 = 1 2 3

Aplicando a eliminação de Gauss com pivoteamento parcial na matriz A :

1 1 1 1 - 1 1 2 1 - 1

L 1 ↔ L 3 :

2 1 - 1 1 - 1 1 1 1 1

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

2 1 - 1 { 0.5 } - 1.5 1.5 1 1 1

Entendeu o que eu quis dizer agora? Nós vamos botando os multiplicadores junto, mas marcando que eles não fazem parte da matriz em si! Aqui eu estou pondo em chaves, mas vocês podem marcar isso de outra forma! Só não pode confundir haha.

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

2 1 - 1 { 0.5 } - 1.5 1.5 { 0.5 } 0.5 1.5

Já está pivoteado, então continuamos a eliminação.

2 1 - 1 { 0.5 } - 1.5 1.5 { 0.5 } 0.5 1.5

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

2 1 - 1 { 0.5 } - 1.5 1.5 { 0.5 } { - 0.33 } 2

Então ficamos com:

P = 0 0 1 0 1 0 1 0 0

Que foi formada da matriz identidade 1 0 0 0 1 0 0 0 1 com as linhas 1 e 3 trocadas.

L = 1 0 0 0.5 1 0 0.5 - 1 3 1

U = 2 1 - 1 0 - 1.5 1.5 0 0 2

Prontinho! Se tivéssemos que resolver o sistema era só botarmos na forma L U x = P - 1 b e resolver como de costume. Repare que quando fazemos apenas uma troca de linhas, temos P - 1 = P .

Algoritmo

Novamente podemos dividir esse algoritmo em três fases bem distintas. Fase 1 será a eliminação de Gauss. Só que agora com o pivoteamento! E além das matrizes L e U essa fase também teria como saída a matriz P . A Fase 2 receberia a matriz L vinda da Fase 1 e o vetor P b para resolver o sistema L y = P b , que seria resolvido não por retrosubstituição, mas por substituição simples. A Fase 3 receberia o resultado da fase 2 , o vetor y , e a matriz U da Fase 1, e aplicaríamos nosso algoritmo da retrosubstituição. Vamos lá então:

Algoritmo da Fase 1:

Passo 1. Dados iniciais (o que seu programa vai receber de você):

a. Matriz quadrada A n × n

Passo 2. Definimos P como a matriz identidade

Passo 3. Percorremos as linhas de A com uma variável i (de 1 a n ).

Passo 4. l = i + 1

Passo 5. p o s M a i o r = i

Passo 6. m a i o r = a i i

Passo 7. Se a l i > m a i o r , então m a i o r = a l i e p o s M a i o r = l .

Passo 8. l = l + 1

Passo 9. Enquanto l ≤ n , volte para o Passo 6. Caso contrário, continue.

Passo 10. Troque as linhas i e p o s M a i o r de A e de P .

Passo 11. Escolher pivô da i -ésima linha de A   e armazenar na variável p .

Passo 12. Para cada ‘ i ’, percorremos as linhas de A de i + 1 até n com uma variável k .

Passo 13. Definimos o multiplicador m i k = a k i p .

Passo 14. Guardar m i k na posição linha i e coluna k de A .

Passo 15. Para cada ‘ k ’, percorremos as colunas de A i + 1 até n com uma variável j .

Passo 16. a k j = a k j - m i k ∙ a i j

Passo 17. Depois que acabarem todos os ' i ' do Passo 4, é importante separarmos as matrizes L e U da matriz A . A matriz L será uma matriz triangular inferior com 1 na diagonal e elementos a i j com i > j iguais ao da matriz A . Já a matriz U será uma matriz triangular superior com os elementos a i j com i ≤ j iguais ao da matriz A .

Esse último passo é necessário por causa daquela história de armazenar os multiplicadores na própria matriz que estamos escalonando. Então temos que separar no final. Repare também que como o objetivo aqui é resolver sistemas no algoritmo P é o nosso P - 1 da teoria já que fazemos as mudanças na ordem que elas acontecem.

Pronto, tá feito o nosso algoritmo. Daí vamos tirar nossas matrizes P , U e L . Agora o algoritmo da Fase 2 segue igual ao da fatoração L U , mas recebendo o vetor P b ao invés de b , então não vale a pena escrevê-lo aqui de novo.

Para a Fase 3 também temos exatamente a mesma coisa da fatoração L U .

Expandir

Exercício Resolvido #1

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

Considere as seguintes matrizes. Encontre a matriz de permutação P tal que P A pode ser fatorada no produto L U , onde L é uma matriz triangular inferior com 1 s em sua diagonal e U é triangular superior.

a A = 1 2 - 1 2 4 0 0 1 - 1

b A = 0 1 1 1 - 2 - 1 1 - 1 1

c A = 1 1 - 1 0 1 1 4 3 2 - 1 2 4 2 - 1 2 3

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

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

A primeira coisa que temos que perceber é que não devemos usar a fatoração P L U em si! Ele apenas quer que façamos o pivoteamento quando for necessário para a fatoração L U ! Vamos lá.

Passo 2

a Realizando a Eliminação de Gauss:

1 2 - 1 2 4 0 0 1 - 1

L 2 ← L 2 - 2 L 1 :

1 2 - 1 0 0 2 0 1 - 1

Repare que agora, para continuarmos com o processo precisamos fazer a troca das linhas.

L 2 ↔ L 3 :

1 2 - 1 0 1 - 1 0 0 2

Pronto. Repare que aí já terminamos o processo da fatoração. Mas ele não está interessado nas matrizes L e U , apenas na P que é dada pela matriz identidade com as linhas 2 e 3 trocadas.

P = 1 0 0 0 1 0 0 0 1 → L 1 ↔ L 2 1 0 0 0 0 1 0 1 0

Passo 3

b Realizando a Eliminação de Gauss:

0 1 1 1 - 2 - 1 1 - 1 1

L 1 ↔ L 2 :

1 - 2 - 1 0 1 1 1 - 1 1

L 3 ← L 3 - L 1 :

1 - 2 - 1 0 1 1 0 1 2

L 3 ← L 3 - L 2 :

1 - 2 - 1 0 1 1 0 0 1

Trocamos apenas as linhas 1 e 2 , então:

P = 1 0 0 0 1 0 0 0 1 → L 2 ↔ L 3 0 1 0 1 0 0 0 0 1

Passo 4

c Realizando a Eliminação de Gauss:

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

L 2 ← L 2 - L 1 :

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

L 3 ← L 3 - 2 L 1 :

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

L 4 ← L 4 - 2 L 1 :

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

L 2 ↔ L 3 :

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