Decomposição por LDLT

Seja A uma matriz simétrica. Podemos decompor A pelo produto de 3 outras matrizes a saber. L é uma matriz triangular inferior e unitária e D é uma matriz diagonal. A solução é: [Ly = b; Dt = y; L^Tx = t] para  .
Podemos ver que um termo usa o outro pra ser definido (l usa d e vice versa). Por isso tem uma ordem para fazer: d₁₁, l₂₁, l₃₁, d₂₂, l₃₂, d₃₃ (num exemplo de matriz de ordem 3). A ordem é essa porque fazendo o d₁₁ (esse é o primeiro em matriz de qualquer ordem) é possível descobrir todos os l da primeira coluna (ou seja, abaixo do índice 11, já que a matriz é triangular inferior e unitária). Após descobrir todos esses, com o d₂₂ dá pra descobrir todos os l abaixo de 22 e por aí vai.

Decomposição pelo método de Cholesky (LLT)

Seja A uma matriz simétrica e definida positiva (ou seja, para a determinante de A - λI todos os λ devem ser maiores que 0)(ou seja, mais fácil ainda: é simétrica e tem a diagonal principal toda positiva). Podemos decompor A por um produto de duas outras matrizes (L e a transposta de L), em que L é triangular inferior e LT é triangular superior. Para obter L, realizamos as seguintes operações:

Feito isso, temos as duas matrizes. IMPORTANTE: a conta é feita coluna por coluna, não adianta tentar começar pela diagonal que não vai dar. Agora um exemplo, de praxe:

Lindo (só que não)! Agora só falta resolver o sisteminha em vermelho aí em cima. Vão dar números horrorosos, então é bacana cortar com 4 casas decimais. Não pretendo resolver, preguiça.

Decomposição LU com pivotação parcial

A pivotação parcial é como se fosse uma 'extensão' do método LU. Existe pra lidar com o pivô nulo. Caso o pivô seja 0, tem que trocar as linhas E o termo independente do resultado do sistema linear que gerou a matriz A. O pivô deve ser o maior número EM MÓDULO da coluna (independentemente do primeiro elemento ser 0). Pra lidar com essa troca de forma facilitada, trabalha-se com uma matriz permutação P, do tipo identidade. A cada troca efetuada no dispositivo prático, troca-se também a ordem das linhas da matriz P e dos multiplicadores e o resultado de LU passa a ser PA, e não apenas A. Vamos ao desenho de exemplo:

Agora resta só montar as matrizes L e U e resolver o sistema:

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!