Pular para o conteúdo principal

Fatoração LU: como fazer?

A fatoração LU de uma matriz A surge da necessidade de resolver um conjunto de sistemas do tipo Ax = b1, Ax = b2, Ax = b3 e assim por diante. Evidentemente, poderíamos resolver cada um desses sistemas escalonando a matriz completa [A b] correspondente até sua forma escalonada reduzida mas, computacionalmente, o escalonamento é um processo muito demorado e, como se não bastasse, imagine que tivéssemos centenas ou milhares de b's para resolver. Você ficaria escalonando sistema por sistema?



A fatoração LU surge para resolver esse problema. Basicamente, supondo-se que A seja uma matriz mxn que pode ser escalonada até sua forma reduzida sem trocar linhas, a Álgebra Linear nos diz que ela pode ser escrita na forma A = LU, onde L é uma matriz triangular inferior mxm cuja diagonal principal possui apenas 1's e U é uma matriz triangular superior mxn que nada mais é do que a própria forma escalonada reduzida de A.


Caso o leitor ainda não tenha percebido, o nome "fatoração LU" se dá devido a essas duas matrizes triangulares: L vem de "lower" que, em inglês, significa "inferior" e U vem de "upper" que, nesse mesmo idioma. quer dizer "superior".


A importância de escrevermos uma matriz como o produto de duas outras matrizes triangulares, uma inferior e a outra superior, se dá pelo fato de que, ao assumirmos que A = LU, podemos reescrever a equação Ax = b como LUx = B ou, pela propriedade associativa, L(Ux) = B. Tomando-se Ux = y, temos Ly = b e  Ux = y. Resolvendo-se a primeira equação para y e a segunda para x, obteremos a resposta procurada de uma maneira bem mais simples do que fazer pelo método tradicional, visto que as matrizes são triangulares.


Para calcular as matrizes, tudo que precisamos fazer é escalonar a matriz A com operações de substituição de linhas. A matriz resultante será a matriz U. A matriz L é composta pelas colunas pivô de cada passo do escalonamento, com os elementos de cada coluna divididos pelo pivô correspondente.


Para exemplificar, vamos escrever a matriz A = [3, -1, 2; -3, -2, 10; 9, -5, 6] em sua forma fatorada A = LU.


Como A possui três linhas, a matriz L será 3x3. Note que a matriz A não precisa ser quadrada, como no exemplo. Realizando o escalonamento de A através das operações elementares, obtemos:


Sequência de operações elementares em A.


Neste momento, já sabemos que a última matriz obtida é a nossa matriz U, ou seja, U = [3, -1, 2; 0, -3, 12; 0, 0, -8]. Perceba que U é, de fato, uma matriz triangular superior ("upper").


Agora, como encontramos a matriz L? Sabemos que ela é triangular inferior. Os elementos de suas colunas, então, serão os elementos das colunas pivô de cada estágio do escalonamento de A, abaixo do pivô daquela coluna, divididos pelo mesmo, a fim de formarmos a diagonal principal só de 1's.


A primeira coluna da matriz L será composta pelos elementos da primeira coluna de A divididos pelo pivô que, neste caso, é 3. Assim, como a primeira coluna de A é (3, -3, 9), sabemos que a primeira coluna de L deverá ser (1, -1, 3).


Assim, a primeira coluna de L será (1, -1, 3), pois esses são os elementos da primeira coluna de A divididos pelo pivô 3; O pivô da segunda coluna, no segundo estágio, é -3 e, abaixo dele, temos -2. Dividamos esses elementos por -3 e obtemos a segunda coluna, (0, 1, 2/3). O pivô da terceira coluna, no terceiro estágio, é -8, sem elementos abaixo dele. Dividindo-o por -8, obtemos a terceira coluna, (0, 0. 1). Dessa forma, nossa matriz L será .


Faça a multiplicação de L por U e verifique que a mesma resulta em A.

Comentários

  1. Obrigado por ter explicado de forma tao simples e clara a formação da Matriz L...
    Nunca antes ninguém tinha conseguido fazer com que eu a percebesse, e graças a sim, nunca mais ninguém vai ter de o fazer ;-)

    ResponderExcluir
  2. Obrigado pelo artigo.
    A matriz L é formada pelos multiplicadores em cada passo no escalonamento de A para chegarmos à matriz U.

    ResponderExcluir
  3. A multiplicação deu errado na minha!

    ResponderExcluir
  4. Muito Obrigada pelo artigo, muito clara sua explicação.
    Foi de grande ajuda!
    :D

    ResponderExcluir
  5. Melhor explicação não há! Parabéns pela sua didática!

    ResponderExcluir
  6. olá, gostei muito da sua explicação! mas não consegui chegar no valor de -8 na matriz u33, poderia me indicar qual foi a operação realizada?
    obrigado!

    ResponderExcluir
  7. Parabéns pelo artigo !

    ResponderExcluir
  8. Pode escalonar matriz sem realizar o pivotamento parcial da mesma?

    ResponderExcluir
  9. HAHA. Finalmente entendi fatoração LU! :D

    PS: 3º ano de engenharia em uma UF e ainda não tinha conseguido entender isso. Bom... Antes tarde do que mais tarde. hehehe... Excelente explicação!

    ResponderExcluir
  10. Salvou meu período haha

    ResponderExcluir
  11. Muito obrigada!! Enfim consegui entender rsrs

    ResponderExcluir
  12. Parabéns! Explicação perfeita, clara, simples e objetiva. TOP!
    Muito obrigado.

    ResponderExcluir

Postar um comentário

Postagens mais visitadas deste blog

Como acessar configurações avançadas no Sagemcom F@st 2704N

NOVO TUTORIAL: GUIA DEFINITIVO DAS CONFIGURAÇÕES AVANÇADAS DO SAGEMCOM F@ST 2704N!
Atualização 23/01/2015: Alguns problemas apontados e descobertos nesse modem:
1. Alguns usuários relatam dificuldade em salvar alterações na configuração ADSL;
2. Não sei como acessar os logs do modem; mesmo habilitando, eles não aparecem;
3. Se você trocar o DNS do modem, ele voltará ao da Oi ao ser reiniciado;
4. Estou enfrentando alguns problemas sérios de lentidão. Não sei se isso é relacionado ao modem ou a algum dispositivo na minha rede interna.
-----
Os modens da marca Sagemcom estão se tornando muito populares no Brasil, não, quiçá, por sua qualidade, mas porque eles são os atuais queridinhos das operadoras: quando você assina um plano ADSL, geralmente a operadora envia um modem wireless para sua casa a fim de que você possa navegar sem precisar ter gastos extras com esse equipamento. É claro que os equipamentos fornecidos pelas operadoras são básicos, mas saciam as necessidades dos usuários comuns - …

O Guia Definitivo das configurações avançadas no Sagemcom F@st 2704N

Há alguns meses, eu contei minha experiência com o Sagemcom F@st 2704N e tenho recebido diversos comentários sobre suas configurações avançadas. Agora que minhas aulas na faculdade estão acabando, resolvi reservar um tempinho para explorar melhor esse modem que, diga-se de passagem, é muito bom.