Método de Lagrange

Sejam n+1 pontos (x0, y0), (x1, y1), ..., (xn, yn). Podemos encontrar polinômios interpoladores de modo que o erro seja minimizado. Dado Pi(xi) = 0 e Pj(xj) != 0, temos:

Como o polinômio interpolador não tem grau superior a n, então podemos escrevê-lo como combinação linear. Só que tem um monte de coisas aqui no meu caderno pra ficar escrevendo e substituindo e eu to com preguiça. Vou direto ao trem:

Interpolação

Dados valores empíricos de uma determinada tabela xi; yi, podemos estimar por um polinômio interpolador valores de xi de modo que tenhamos a variável de resposta yi com certa precisão. O desafio maior para esse caso é exatamente saber qual polinômio utilizar de modo que o erro obtido seja o menor possível.

Interpolação linear
Seja P(x) um polinômio interpolador de modo que P(x) = a0 + a1*x. Deste modo, P(x0) = a0 + a1*x0 = y0 ; P(x1) = a0 + a1*x1 = y1. P(xi) é um polinômio interpolador de grau 1. Para n+1 pontos sempre tem-se (pode-se ter) um polinômio de grau n.
|1  x0|  |a0|    |y0|
|1  x1| .|a1| = |y1|

Interpolação quadrática
Análogo à interpolação linear, temos que a interpolação quadrática é um polinômio interpolador de grau 2, de modo que P(x0) = a0 + a1*x0 + a2*x0² = y0 ; P(x2) = a0 + a1*x1 + a2*x1² = y1 ; P(x2) = a0 + a1*x2 + a2*x2² = y2. A matriz para a forma quadrática é conhecida como matriz de Vandermonde e seu determinante é não nulo. Isso nos garante que o sistema linear terá uma única solução e o polinômio será único. A matriz:
|1  x0  x0²|    |a0|    |y0|
|1  x1  x1²| .  |a1| = |y1|    => o nome disso é preguiça
|1  x2  x2²|    |a2|    |y2|

Método de Gauss-Seidel

Seja A uma matriz diagonal estritamente dominante e um valor inicial x0 = bi / aii. A partir do método de Jacobi podemos variar determinados valores de xk de modo que a convergência para os valores de xi ocorram com menor custo. Para isso, é só fazer as contas no mesmo esquema de Jacobi, mas utilizando numa iteração valores obtidos na mesma. Por exemplo, eu descobri o x1. Aí na hora de descobrir o x2, ao invés de usar o x1 da iteração anterior, eu uso o que eu acabei de descobrir. O x3 usa o x2 mais novo e por aí vai. Assim chega mais rapidinho nos resultados!
Novamente, um dia eu posto um exemplo, agora to correndo aqui.

Método de Jacobi

Para o método estacionário, devemos decompor A de modo que (D+E+F) = A. Assim, o sistema Ax = b é (D+E+F)x = b. Realizando as operações possíveis, temos Dx = -(E+F)x + b.
Escrevendo x em processo de recorrência (iterativo) temos: x^k+1 = -D^-1 (E+F)x + D^-1b, onde -D^-1(E+F)x é uma matriz jacobiana.
A representação em sistema linear matricial, já evidenciando o valor de xi para cada equação linear, é a seguinte:

Sendo x0 = bi / aii.

Um dia eu escrevo o exemplo, porque na verdade a prova disso já passou e eu só to atualizando mais ou menos os resumos. Favor me lembrar.

Métodos iterativos estacionários

Um sistema linear pode ser resolvido por um processo iterativo a partir de um valor inicial x0 e uma sequência de vetores {x1, x2, x3 ... xn}.

Critério de parada
Como os métodos são iterativos, eles precisam parar alguma hora, né. Para o critério de parada é definido um valor ɛ tal que 

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!