Decomposição de Cholesky

Ver Todos os Exercícios

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 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?

Decomposição de Cholesky

Resolução de sistemas lineares

Exercícios Resolvidos

Exercício Resolvido #1

Prove que a A pode ser decomposta em : A = G . G T .

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

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

Prove que a A pode ser decomposta em : A = G . G T .

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

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

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

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

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

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