Decomposição de Cholesky
Teoria
Introdução
Opa, tudo bem? Bora começar mais um assuntinho de Cálculo Numérico? Então vamos lá!!!
Até agora, nós vimos alguns tipos de decomposição e fatoração de matrizes, como foi o caso das nossas digníssimas LU e LPU. Essas fatorações nos permitiam resolver sistemas de equações lineares.
Vamos estudar agora um outro método, até que bem parecido, e que pode ser beeeeeeeem mais eficiente que a LU quando se trata de achar soluções reais.
Mas, só pra relembrar, na fatoração LU a nossa matriz A é decomposta em L e U.
E tipos assim, L será uma matriz triangular inferior de coeficientes e tem a diagonal principal unitária. Já no caso de U a matriz triangular inferior é nula.
No caso de Cholesky, nós conseguimos simplificar as operações usadas na fatoração LU explorando a matriz dos coeficientes.
Basicamente, a teoria de Cholesky diz que toda matriz que é simétrica e positiva definida, tem uma única decomposição de Cholesky.
Então, o primeiro ponto importante aqui é a matriz do nossos sitema deve ser simétrica e positiva, bora relembrar esses conceitos?
Simetria
Relembrando um conceito laaaaaaaaaaaaaaaá da Geometria Analítica : uma matriz real A quadrada de ordem é simétrica se : .
Ou seja, quando tiramos a chamada “transposta” de uma matriz e ela acaba sendo igualzinha a próxima matriz. Lembra como faz isso?
Nesse caso,
Então, meus amigos se tu precisa de uma ajudinha em geometria analítica, da uma olhada no conteúdo da plataforme que pode te ajudar muuuuuito!
Nós temos uma matriz
Imagine uma matriz 3X3, mais ou menos assim:
A transposta é basicamente quando invertemos as colunas com as linhas, assim:
E no caso de :
Tranquilo né? Bora relembrar o outro tópico!
Determinante positivo
Vamos ver como se calcula se a matriz é positiva ou não, já que é um ponto importante para calcular a Decomposição de Cholesky. O método que vamos usar aqui é bem tranquilinho, vamos separar a nossa matriz A em E calcular os determinantes dessas submatrizes. Como nós usamos uma matriz 3X3 no exemplo passado, faremos assim:
Vamos separar as matrizes em , e .
Aí calculamos os determinante de cada submatriz, cada um deles deve ser maior que zero para a matriz ser considerada positiva. O nome do critério que usamos agora é Critério de Sylvestre:
Decomposição de Cholesky
Nós calculamos e decompomos a matriz A no produto . O teorema é “ se A é uma matriz real simétrica e positiva definida, então existe uma única matriz triangular inferior com elementos da diagonal principal positivo, de forma que: .
Pra isso existem alguns métodos. Mas antes, vou começar pelo conhecido. Pra faciliar a nossa vida, vamos pular a dedução e ir direto para o que interessa. Consegue adivinhar que método vamos usar?
Vamos usar a fatoração LU, para calcular a matriz:
Hmmm... mas de onde surgiu o termo ?
O termo é fácil de achar, ele é a transposta da matriz L (aquela que calculamos láaaaa na fatoração LU).
E a matriz é a diagonal principal obtida em U na fatoração LU, com a diferença que a matriz triangular superior e inferior são nulas. Molezinha né?
Mas que raios isso tem a ver com ?
Nesse caso:
Seeeee e somente se:
Na prática, achamos a matriz L e U e extraímos delas o que precisamos, como a L transposta e a diagonal de U. Até aí tudo bem né, mas existe um método bem mais suave pra calcular , com formulazinhas mágicas! Vamos aprender a calcular e é consequência :
Vamos fazer isso aos poucos e calcularemos termo por termo, assim teremos que ter uma coluna assim:
Primeiro a coluna 1:
Começaremos calculando o termo principal, que é aquele em que o linha e coluna são iguais e no caso da coluna 1 é o :
Agora, calculamos os elementos abaixo da diagonal principal:
Então:
Vale ressaltar que a matriz triangular superior será nula!
O próximo passo é calcular os termos da coluna 2, tendo como termo principal :
Agora, calculamos os elementos abaixo da diagonal principal:
Então:
Tem bastante coisa né? E outras colunas, como fica?
Generalizando a coluna:
Agora, para os termos abaixo da diagonal principal :
Parece bastante coisa, mas na prática é bem mais fácil. Já vamos calcular exercício e tu vai ver como isso é bem tranquilo.
Resolução de sistemas lineares
Nós encontramos a matriz G, certo ? e como eu soluciono um sistema?
Para resolver o sistema utilizando o método de Cholesky:
Então, dizer é a mesma coisa que dizer:
Aí, fazemos :
Resolve-se:
Igualzinho fazíamos lá na fatoração LU.
Bora fazer exercício?
Determinante positivo
Decomposição de Cholesky
Resolução de sistemas lineares
Exercícios Resolvidos
Exercício Resolvido #1
Adaptado de Cálculo Numérico, Resolução de Sistemas Lineares da UFMG
Prove que a A pode ser decomposta em : .
Passo 1
Simetria: O primeiro passo é encontrar a matriz transposta de A. Faremos isso invertendo linhas e colunas.
Tudo o que agora é coluna, será transformado em linha.
Coluna 1 virou linha 1, coluna 2 virou linha 2 e coluna 3 virou linha 3. Tranquilo né?
Mas, para ser simétrica:
Então, cada termo de A deve ser igua .
Opa, igualzinho né? Critério 1 satisfeito.
Passo 2
Agora vamos ao outro critério, ser positiva definida. A matriz é definida se cada uma de suas matrizes principais tiver um determinante positivo:
Agora,calculamos os determinantes de :
Como todos os determinantes são positivos, nossa matriz é definida positiva!
Resposta
Simétrica
Positiva
Exercício Resolvido #2
Adaptado de Cálculo Numérico, Resolução de Sistemas Lineares da UFMG
Prove que a A pode ser decomposta em : .
Passo 1
Simetria: Vamos achar a transposta de A.
Tudo o que agora é coluna, será transformado em linha.
Coluna 1 virou linha 1, coluna 2 virou linha 2 e coluna 3 virou linha 3. Tranquilo né?
Mas, para ser simétrica:
Então, cada termo de A deve ser igua .
Opa, igualzinho né? Critério 1 satisfeito.
Passo 2
Agora vamos ao outro critério, ser positiva definida. A matriz é definida se cada uma de suas matrizes principais tiver um determinante positivo:
Agora,calculamos os determinantes de :
Como todos os determinantes são positivos, nossa matriz é definida positiva!
Resposta
Simétrica
Positiva
Exercício Resolvido #3
Adaptado de Burden, RLB | .JDF | .AM Análise Numérica - Tradução da 10ª edição norte-americana.
Utilize o algorítimo para encontrar a fatoração da forma para a seguinte matriz:
Passo 1
Para resolver esse problema, usamos a nossa velha e conhecida Eliminação de Gauss para solucionar a fatoração LU.
Inicialmente, temos:
Para isso, pegamos nossa matriz e tiramos os seus coeficientes de multiplicação:
Vamos usar a primeira linha como base , entãos teremos o termo 2 em relação a 1 e termo 3 em relação a 1 .
E para o caso da linha 3:
Dale atualizar a matriz!!
Os termos em vermelho servirão como base para construir a matriz L. Para fazer essa atualização Usamos as seguintes fórmulas:
Agora, nós aplicamos essa fórmula em cada termo.
Primeiro para a linha :
Agora, para a linha :
Agora, substituímos os termos das linhas atualizadas na matriz nova:
Falta zerar o termo
Passo 2
Falta zerar o termo da linha , para isso, calcularemos o , substituindo a linha 3 e usando a linha 2 como base:
Atualizamos a linha :
Atualizando a matriz nova temos:
Agora é só separar em L e U
Passo 3
Por via de regra, os termos que estão na diagonal principal e na matriz triangular superior irão formar juntos a matriz U, e os termos/coeficientes usados para zerar a matriz triangular inferior vão servir para formar a matriz L.
Então, L:
U:
Agora, encontraremos os termos que importam: .
Passo 4
Vamos começar pelo que é mais fácil, certo? Já temos a matriz então é a própria transposta de
Agora é só trocar colunas por linhas:
E no caso na matriz ?
Hmmm..... a matriz é basicamente a matriz multiplicada por uma matriz identidade de mesmo tamanho:
Então, dizer que é fazer isso aqui:
Resposta
Exercício Resolvido #4
Adaptado de Cálculo Numérico, Resolução de Sistemas Lineares da UFMG
Utilize o algorítimo para encontrar a fatoração da forma para a seguinte matriz:
Passo 1
Agora já podemos resolver pelo método de Eliminação de Gauss, vamos zerar os termos da matriz triangular inferior.
Vamos usar a primeira linha como base , entãos teremos o termo 2 em relação a 1 e termo 3 em relação a 1 , e
E para o caso da linha 3:
Para a linha 4:
Agora é só a atualizar a matriz.
Repare que eu deixei os termos em vermelho né? Isso porque eles servirão como base para construir a matriz L. Para fazer essa atualização Usamos as seguintes fórmulas:
Agora, nós aplicamos essa fórmula em cada termo.
Primeiro para a linha :
Agora, para a linha :
Agora, para a linha :
Agora, substituímos os termos das linhas atualizadas na matriz nova:
Passo 2
Vamos manter os termos m, que facilitará a nossa vida para montar a matriz L
Falta zerar o termo da linha , para isso, calcularemos o .
Maneiríssimo... Agora é só começarmos a atualizar a matriz.
Agora, para a linha :
Agora, substituímos os termos das linhas atualizadas na matriz nova:
Passo 3
Falta zerar o termo da linha , para isso, calcularemos o .
Atualizando:
Os termos em vermelho servirão como base para construir a matriz L. Para fazer essa atualização Usamos as seguintes fórmulas:
Agora, nós aplicamos essa fórmula em cada termo.
Atualizando:
Passo 4
Agora achamos L e U e transformamos em :
Já conhecemos L, é a sua transposta:
A matriz D é basicamente a diagonal principal da matriz U, com os demais termos nulos:
Então :
Resposta
Exercício Resolvido #5
Adaptado de Cálculo Numérico, Resolução de Sistemas Lineares da UFMG
Encontre .
Passo 1
Vamos aprender a calcular e é consequência :
Vamos fazer isso aos poucos e calcularemos termo por termo, assim teremos que ter uma coluna assim:
Começamos com a coluna 1.
Considerando a matriz A:
Começaremos calculando o termo principal, que é aquele em que o linha e coluna são iguais e no caso da coluna 1 é o :
Agora, calculamos os elementos abaixo da diagonal principal:
Passo 2
Coluna 2.
Agora, calculamos os elementos abaixo da diagonal principal:
Coluna 3.
Substituindo na matriz:
Se :
Então: