Métodos iterativos para resolver Ax = método de B – Jacobi

talvez o método iterativo mais simples para resolver Ax = b é o método de Jacobi. Note – se que a simplicidade deste método é boa e má: boa, porque é relativamente fácil de entender e, portanto, é um bom primeiro gosto de métodos iterativos; má, porque não é tipicamente usada na prática (embora sua utilidade potencial tenha sido reconsiderada com o advento da computação paralela). Ainda assim, é um bom ponto de partida para aprender sobre métodos iterativos mais úteis, mas mais complicados.

Dada uma aproximação atual

x(k) = (x1(k), x2(k), x3(k), …, xn(k))

para x, a estratégia de Jacobi do Método é usar a primeira equação e os valores atuais de x2(k), x3(k), …, xn(k) para encontrar um novo valor de x1(k+1), e da mesma forma para encontrar um novo valor de xi(k) usando a i-ésima equação e os valores antigos das outras variáveis. Isto é, tendo em conta os actuais valores de x(k) = (x1(k), x2(k), …, xn(k)), encontrar novos valores através da resolução para

x(k+1) = (x1(k+1), x2(k+1), …, xn(k+1))

no

Este sistema também pode ser escrito como

Para ser claro, o subscrito i significa que xi(k) é o i ésimo elemento do vetor

x(k) = (x1(k), x2(k), …, xi(k), …, xn(k) ),

e expoente k corresponde a determinada iteração (não o kth poder da xi ).

Se a gente escrever D, L e U para a diagonal, o estrito triangular inferior e rigoroso superior triangular e partes de A, respectivamente,

em seguida, o Método de Jacobi pode ser escrito na matriz-vetor de notação de

Exemplo 1

Vamos aplicar o Método de Jacobi para o sistema

.

em cada etapa, dados os valores actuais x1 (k), x2 (k), x3 (k), resolvemos para x1( k+1), x2( k+1), e x3(k+1) em

.

Então, se a nossa estimativa inicial x(0) = (x1(0), x2(0), x3(0)) é o vetor de zero 0 = (0,0,0) — comum de uma estimativa inicial, a menos que nós temos algumas informações adicionais que nos leva a escolher alguns outros—, em seguida, encontramos x(1) = (x1(1), x2(1), x3(1) ) através da resolução de

Assim, x(1) = (x1(1), x2(1), x3(1)) = (3/4, 9/6, -6/7) ≈ (0.750, 1.500, -0.857). Iterate this process to find a sequence of increasingly better approximations x (0), x(1), x(2),…. Mostramos os resultados na tabela abaixo, com todos os valores arredondados a 3 casas decimais.

estamos interessados no erro e em cada iteração entre a solução verdadeira x e a aproximação x(k): E(k) = x − x(k) . Obviamente, nós geralmente não sabem a verdadeira solução x. No entanto, para melhor compreender o comportamento de um método iterativo, é esclarecedor para utilizar o método para resolver um sistema Ax = b, para que nós sabemos a verdadeira solução e analisar o quão rapidamente as aproximações estão convergindo para a verdadeira solução. Para este exemplo, a solução verdadeira é x = (1, 2, -1).

a norma de um vetor ||x| diz-nos quão grande é o vetor como um todo (em oposição à dimensão de cada elemento do vetor). O vetor de norma mais comumente usadas em álgebra linear é a norma l2:

Por exemplo, se x = (1, 2, -1), então

neste módulo, vamos sempre utilizar a norma l2 (incluindo a matriz normas subseqüentes tutoriais), de modo que || || sempre significa|| ||2.

para nossos propósitos, observamos que | / x / / será pequeno exatamente quando cada um dos elementos x1, x2,…, xn em x = (x1, x2,…, xn ) é pequeno. Na tabela seguinte, a norma do erro torna-se progressivamente menor à medida que o erro em cada um dos três elementos x1, x2, x3 se torna menor, ou em outras palavras, à medida que as aproximações se tornam progressivamente melhores.