Decomposição de Cholesky

Teoria Completa

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 m × n 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 n é simétrica se : A   =   A T .

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, a i j =   a j i         s e     ∀ i = 1,2 … n   e   j = 1,2 , … n

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 m × n : a 11 ⋯ a 1 n ⋮ ⋱ ⋮ a m 1 ⋯ a m n

Imagine uma matriz 3X3, mais ou menos assim:

a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33

A transposta é basicamente quando invertemos as colunas com as linhas, assim:

a 11 a 21 a 31 a 12 a 22 a 32 a 13 a 23 a 33

E no caso de A   =   A T :

a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 = a 11 a 21 a 31 a 12 a 22 a 32 a 13 a 23 a 33

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 A 1 ,   A 2   e   A 3 . E calcular os determinantes dessas submatrizes. Como nós usamos uma matriz 3X3 no exemplo passado, faremos assim:

Vamos separar as matrizes em A 1 = 1 × 1 , A 2 = 2 × 2 e A 3 = 3 × 3 .

A 1 = a 11

A 2 = a 11 a 12 a 21 a 22

A 3 = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33

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 G . G T . 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: A = G . G T .

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:

A   =   L U   =   L D L T

Hmmm... mas de onde surgiu o termo D   e   L T ?

O termo L T é fácil de achar, ele é a transposta da matriz L (aquela que calculamos láaaaa na fatoração LU).

E a matriz D é 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 A = G . G T ?

Nesse caso:

A = G . G T = L D L T

Seeeee e somente se:

G = L ( D ) 1 / 2

G T = L T ( D ) 1 / 2

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 G   e   G T , com formulazinhas mágicas! Vamos aprender a calcular G   e G T é consequência :

Vamos fazer isso aos poucos e calcularemos termo por termo, assim teremos que ter uma coluna assim:

G = g 11 0 0 g 21 g 22 0 g 31 g 32 g 33

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 a 11 :

a 11 = g 2 11

g 11 = a 11

Agora, calculamos os elementos abaixo da diagonal principal:

a 21 = g 21 . g 11

a 31 = g 31 . g 11

a n 1 = g n 1 . g 11

Então:

g 21 = a 21 g 11

g 31 = a 31 g 11

g n 1 = a n 1 g 11

Vale ressaltar que a matriz triangular superior será nula!

O próximo passo é calcular os termos da coluna 2, tendo como termo principal a 22 :

a 22 = g 2 22 + g 2 21

g 22 = a 22 - g 2 21

Agora, calculamos os elementos abaixo da diagonal principal:

a 32 = g 31 . g 21 + g 32 . g 22

a 42 = g 41 . g 21 + g 42 . g 22

a n 2 = g n 1 . g 21 + g n 2 . g 22

Então:

g 32 = a 32 - g 31 . g 21 g 22

g 42 = a 42 - g 41 . g 21 g 22

g n 2 = a n 2 - g n 1 . g 21 g 22

Tem bastante coisa né? E outras colunas, como fica?

Generalizando a coluna   j :

a j j = ∑ k = 1 j g 2 j k

a j j = ∑ k = 1 j - 1 g 2 j k + g 2 j j

g j j = a j j - ∑ k = 1 j - 1 g 2 j k

Agora, para os termos abaixo da diagonal principal i   > j :

g i j = a i j - ∑ k = 1 j - 1 g i k . g j k g j j

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 A x =   b utilizando o método de Cholesky:

Então, dizer A x =   b é a mesma coisa que dizer:

b = G . G T x

Aí, fazemos :

b = G y

Resolve-se:

G T x = y

Igualzinho fazíamos lá na fatoração LU.

Bora fazer exercício?

Expandir

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 : A = G . G T .

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

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Simetria: O primeiro passo é encontrar a matriz transposta de A. Faremos isso invertendo linhas e colunas.

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

Tudo o que agora é coluna, será transformado em linha.

  A T = 1 1 0 1 2 - 1 0 - 1 3

Coluna 1 virou linha 1, coluna 2 virou linha 2 e coluna 3 virou linha 3. Tranquilo né?

Mas, para ser simétrica:

A   =   A T

Então, cada termo a i j de A deve ser igua   A T .

1 1 0 1 2 - 1 0 - 1 3 = 1 1 0 1 2 - 1 0 - 1 3

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:

A 1 = a 11 = ( 1 )

A 2 = a 11 a 12 a 21 a 22 = 1 1 1 2

A 3 = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 = 1 1 0 1 2 - 1 0 - 1 3

Agora,calculamos os determinantes de A 1 ,   A 2   e   A 3 :

I     det ⁡ A 1 = det ⁡ 1 = 1 > 0

I I       d e t ⁡ ( A 2 ) = d e t 1 1 1 2 = 1.2 - 1.1 = 1 > 0

d e t ⁡ ( A 3 ) = d e t 1 1 0 1 2 - 1 0 - 1 3 = 1.2 . 3 + 1 . - 1.0 + 1 . - 1.0 - 0.2 . 0 + 1 + 3

I I I   d e t ⁡ ( A 3 ) = 2 > 0

Como todos os determinantes são positivos, nossa matriz é definida positiva!

Resposta

Simétrica

A   =   A T

1 1 0 1 2 - 1 0 - 1 3 = 1 1 0 1 2 - 1 0 - 1 3

Positiva

det ⁡ A 1 = 1 > 0

det ⁡ A 2 = 1 > 0

det ⁡ A 3 = 2 > 0

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 : A = G . G T .

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

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Simetria: Vamos achar a transposta de A.

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

Tudo o que agora é coluna, será transformado em linha.

  A T = 2 - 1 0 - 1 2 - 1 0 - 1 2

Coluna 1 virou linha 1, coluna 2 virou linha 2 e coluna 3 virou linha 3. Tranquilo né?

Mas, para ser simétrica:

A   =   A T

Então, cada termo a i j de A deve ser igua   A T .

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

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:

A 1 = a 11 = ( 2 )

A 2 = a 11 a 12 a 21 a 22 = 2 - 1 - 1 2

A 3 = a 11 a 12 a 13 a 21 a 22 a 23 a 31 a 32 a 33 = 2 - 1 0 - 1 2 - 1 0 - 1 2

Agora,calculamos os determinantes de A 1 ,   A 2   e   A 3 :

I     det ⁡ A 1 = det ⁡ 2 = 2 > 0

I I       d e t ⁡ ( A 2 ) = d e t 2 - 1 - 1 2 = 2 . 2 - - 1 . - 1 = 3 > 0

d e t ⁡ ( A 3 ) = d e t 2 - 1 0 - 1 2 - 1 0 - 1 2 = 8 + 0 + 0 - 0 + 2 + 2 = 8 - 4 = 4 > 0

I I I   d e t ⁡ ( A 3 ) = 4 > 0

Como todos os determinantes são positivos, nossa matriz é definida positiva!

Resposta

Simétrica

A   =   A T

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

Positiva

det ⁡ A 1 = 2 > 0

det ⁡ A 2 = 3 > 0

det ⁡ A 3 = 4 > 0

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 L D L T para encontrar a fatoração da forma A = L D L T para a seguinte matriz:

A = 2 1 2 1 2 3 4 1 2

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Para resolver esse problema, usamos a nossa velha e conhecida Eliminação de Gauss para solucionar a fatoração LU.

Inicialmente, temos:

A = 2 1 2 1 2 3 4 1 2

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 ( m 21 ) e termo 3 em relação a 1 ( m 31 ) .

m 21 = a 21 a 11 = 1 2 = 0,5

E para o caso da linha 3:

m 31 = a 31 a 11 = 4 2 = 2

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:

E 2 n o v a = E 2 - m 21 E 1

E 3 n o v a = E 3 - m 31 E 1

Agora, nós aplicamos essa fórmula em cada termo.

Primeiro para a linha E 2 :

E 2 n o v a = E 2 - m 21 E 1

( a 21 ) = 1 - 0,5.2 = 0

( a 22 ) = 2 - 0,5.1 = 1 , 5

( a 23 ) = 3 - 0,5.2 = 2

Agora, para a linha E 3 :

E 3 n o v a = E 3 - m 31 E 1

( a 31 ) = 4 - ( 2.2 ) = 0

( a 32 ) = 1 - 1.2 = - 1

( a 33 ) = 2 - 2.2 = - 2

Agora, substituímos os termos das linhas atualizadas na matriz nova:

A = 2 1 2 0 1,5 2 0 - 1 - 2

Falta zerar o termo m 3 2 .

Passo 2

Falta zerar o termo x 2 da linha E 3 , para isso, calcularemos o m 32 , substituindo a linha 3 e usando a linha 2 como base:

A = 2 1 2 0 1,5 2 0 - 1 - 2

m 32 = a 32 a 22 = - 1 1,5 = - 0 , 67

Atualizamos a linha E 3 :

E 3 n o v a = E 3 - m 32 E 2

( a 32 ) = - 1 - - 0,67.1,5 = 0

( a 33 ) = - 2 - - 0,67.2 = - 0,67

Atualizando a matriz nova temos:

2 1 2 0 1,5 2 0 0 - 0,67

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.

2 1 2 0,5 1,5 2 2 - 0,67 - 0,67

Então, L:

L = 1 0 0 0,5 1 0 2 - 0,67 1

U:

U = 2 1 2 0 1,5 2 0 0 - 0,67

Agora, encontraremos os termos que importam: L D L T .

Passo 4

Vamos começar pelo que é mais fácil, certo? Já temos a matriz L ,   então L T   é a própria transposta de L .

L = 1 0 0 0,5 1 0 2 - 0,67 1

Agora é só trocar colunas por linhas:

L T   = 1 0,5 2 0 1 - 0,67 0 0 1

E no caso na matriz D ?

Hmmm..... a matriz D é basicamente a matriz U multiplicada por uma matriz identidade de mesmo tamanho:

U . I = 2 1 2 0 1,5 2 0 0 - 0,67 . 1 0 0 0 1 0 0 0 1 = 2 0 0 0 1,5 0 0 0 - 0,67 = D

Então, dizer que A = L D L T é fazer isso aqui:

A = 1 0 0 0,5 1 0 2 - 0,67 1 . 1 0,5 2 0 1 - 0,67 0 0 1 . 2 0 0 0 1,5 0 0 0 - 0,67

Resposta

A = L D L T

A = 1 0 0 0,5 1 0 2 - 0,67 1 . 1 0,5 2 0 1 - 0,67 0 0 1 . 2 0 0 0 1,5 0 0 0 - 0,67

Exercício Resolvido #4

Adaptado de Cálculo Numérico, Resolução de Sistemas Lineares da UFMG

Utilize o algorítimo L D L T para encontrar a fatoração da forma A = L D L T para a seguinte matriz:

A = 16 - 4 12 - 4 - 4 2 - 1 1 12 - 1 14 - 2 - 4 1 - 2 83

MOSTRAR SOLUÇÃO COMPLETA

Passo 1

Agora já podemos resolver pelo método de Eliminação de Gauss, vamos zerar os termos x 1 da matriz triangular inferior.

Vamos usar a primeira linha como base , entãos teremos o termo 2 em relação a 1 ( m 21 ) e termo 3 em relação a 1 ( m 31 ) , e ( m 41 )

m 21 = a 21 a 11 = - 4 16 = - 0,25

E para o caso da linha 3:

m 31 = a 31 a 11 = 12 16 = 0 , 75

Para a linha 4: m 41 = a 41 a 11 = - 4 16 = - 0 , 2 5

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:

E 2 n o v a = E 2 - m 21 E 1

E 3 n o v a = E 3 - m 31 E 1

E 4 n o v a = E 4 - m 41 E 1

Agora, nós aplicamos essa fórmula em cada termo.

Primeiro para a linha E 2 :

E 2 n o v a = E 2 - m 21 E 1

( a 21 ) = - 4 - 16 . - 0,25 = 0

( a 22 ) = 2 - - 4 . - 0,25 = 1

( a 23 ) = - 1 - 12 . - 0,25 = 2

( a 24 ) = 1 - - 4 . - 0,25 = 0

Agora, para a linha E 3 :

E 3 n o v a = E 3 - m 31 E 1

( a 31 ) = 12 - 16.0,75 = 0

( a 32 ) = - 1 - - 4.0,75 = 2

( a 33 ) = 14 - 12.0,75 = 5

( a 34 ) = - 2 - - 4.0,75 = 1

Agora, para a linha E 4 :

E 4 n o v a = E 4 - m 41 E 1

( a 41 ) = - 4 - 16 . - 0,25 = 0

( a 42 ) = 1 - - 4 . - 0,25 = 0

( a 43 ) = - 2 - 12 . - 0,25 = 1

( a 44 ) = 83 - - 4 . - 0,25 = 82

Agora, substituímos os termos das linhas atualizadas na matriz nova:

16 - 4 12 - 4 - 0,25 1 2 0 0 , 75 2 5 1 - 0,25 0 1 82

Passo 2

Vamos manter os termos m, que facilitará a nossa vida para montar a matriz L

Falta zerar o termo x 2 da linha E 3 , para isso, calcularemos o m 32 .

m 32 = a 32 a 22 = 2 1 = 2

m 43 = a 4 2 a 22 = 0 1 = 0

Maneiríssimo... Agora é só começarmos a atualizar a matriz.

E 3 n o v a = E 3 - m 31 E 1

( a 32 ) = 2 - 2.1 = 0

( a 33 ) = 5 - 2.2 = 1