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!

Vetores

Vetores são como as variáveis normais, só que um vetor pode guardar mais de um valor ao mesmo tempo. Imagina um vetor como uma caixinha com várias divisões, e cada divisão equivaleria a uma variável normal. Tanto que tudo parece com o normal, a declaração, a atribuição de valores e tal.

int i, vetor[5];

Pronto, declarei um vetor de 5 posições. Em C a gente TEM que colocar quantas posições esse vetor vai ter na declaração dele.

OBSERVAÇÃO IMPORTANTE: num vetor de x posições, os índices vão de 0 a x-1. Portanto, no meu vetorzinho de 5 posições eu tenho 0, 1, 2, 3 e 4 como índices. E quando a gente declara, todas essas posições são iniciadas com valores aleatórios. Por isso, antes de usar seu vetor (ou qualquer variável) sempre inicialize, senão vai dar lixo.

Pra atribuir um valor a uma posição do vetor é só colocar qual posição eu quero e atribuir. TARAAAN! Tipo vetor[0] = 18; Taí, a primeira posição do meu vetor tem o valor 18 guardado.

A gente também pode atribuir valores direto na declaração, assim:

int vetor[5] = {18, 14, 9, 5, 44};

Dessa forma nosso vetor já não vem mais com lixo, já vem com esses valores. Se eu declarar um vetor de 5 posições e declarar só 3 delas desse jeito, por exemplo, as outras automaticamente são declaradas com 0.

Uma matriz é um vetor cujas posições contêm outros vetores. A declaração é igual à do vetor: int matriz[5][3]; em que cada uma das 5 posições tem um vetor de 3 posições. Tipo isso. Dá até pra desenhar, fica assim:

[ ][ ][ ][ ][ ]

[ ][ ][ ][ ][ ]

[ ][ ][ ][ ][ ]

A gente pode fazer vetores de múltiplas dimensões (sério, quantas a gente quiser), mas fica meio difícil de ver então é melhor com no máximo 3 mesmo.

Pra inicializar uma matriz seria bem