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