quarta-feira, 8 de maio de 2013

Decomposição de matrizes (LU)

A decomposição de matrizes LU é um método de resolver sistemas que permite um resultado mais refinado, digamos assim, e nos permite calcular a margem de erro desse resultado. Pra muitas matrizes, escalonar seria a forma mais fácil, mas nem sempre a mais precisa. A forma de resolver o sistema com decomposição se chama Dispositivo Prático. Fica mais fácil explicar o passo a passo com um exemplo:
Sobre o desenho acima, que eu esqueci de colocar e agora to com preguiça de fazer outro: o vetor transposto resultado do sistema se chama b. b = [1, 2, 3] nesse sistema. Vamos usar isso lá em baixo. Agora voltando.
A matriz A vai ser decomposta em duas matrizes: L e U. A matriz L é triangular inferior unitária e U é triangular superior.
O dispositivo prático serve para descobrir os números que faltam nas matrizes L e U para que o produto delas seja a matriz A. Depois de decompor, tem que resolver outros sistemas (Ly = b e Ux = y), mas por enquanto vamos ficar nesse aqui. O dispositivo se parece com uma tabela. O primeiro passo é colocar a matriz lá e numerar as linhas:
Feito isso, devemos começar o procedimento definindo um pivô da primeira coluna. O pivô é o primeiro elemento, de cima pra baixo, e deve ser diferente de 0. Ele é usado para calcular multiplicadores que irão zerar o resto da coluna, como no processo de escalonamento mesmo. Após zerar essa primeira coluna, eis o que temos:
Ok, zeramos a primeira coluna. Agora, seguindo o modelo do escalonamento, temos que zerar a segunda (precisamente, a posição 3x2, ou seja, o 1/3 da linha 5). Pra fazer isso, definimos o pivô pra essa coluna e repetimos o procedimento.
Prontinho! Agora devem estar se perguntando qual o objetivo disso. É simples: os multiplicadores que descobrimos são os elementos das posições correspondentes na matriz L e as linhas (nesse exemplo) 1, 4 e 6 formam a matriz U. Assim temos
Pronto. Agora lembra do Ly = b e Ux = y? São os dois sistemas abaixo (lembrar do b lá de cima, resultado do primeiro sistema):
Taí, a resposta do primeiro sistema marcada em azul!
Agora só falta o cálculo do erro (que nesse sistema vai dar 0 porque só temos números bonitinhos):
















Como eu disse, nesse exemplo o erro é 0. Mas trabalhando com números decimais, provavelmente ele será maior que 0. E o negócio do módulo do máximo valor é tipo assim: vamos supor que r = [-4, 2, 3] => o erro será 4 (módulo máximo). Fim!

3 comentários:

  1. Super legal o blog, ótima explicação!

    ResponderExcluir
    Respostas
    1. Que ótimo que vc gostou! Aceito contribuições e publicidade hahaha

      Excluir
  2. muito bom, mas teria como colocar o dispositivo pratico da decomposiçao de cholesky?

    ResponderExcluir