Cálculo Numérico

Sistemas linearesMétodos Iterativos: Introdução

Método Iterativo de Jacobi-Richardson

Métodos exatosMétodos como:� Método de eliminação de Gauss� Método de decomposição LU� Método de Cholesky

são ditos exatos: obtém a solução final após um número k de passos.

Em alguns casos/aspectos, métodos iterativos têm algumas vantagens.são melhores em matrizes esparsasapresentam auto-correção de erros (podem ser usados para melhorar a solução obtida por métodos exatos).

Idéia geral

Similar à idéia do método iterativo linear para resolução de equações.

Queremos resolver: Ax =bE reescrevemos o sistema como:

x = Bx + g

(B = I-A, g =b, por exemplo)

Idéia geral

De posse de x = Bx +g:Chutamos um valor inicial para x: x(0).� Obtemos:

x(1) = Bx(0) +g.x(2) = Bx(1) +g.x(3) = Bx(2) +g.

...x(k+1) = Bx(k) +g.

Da mesma forma como fazíamos:

xk+1 = ψ(xk)

Convergência

A seqüência converge ?Critério: A sequência será convergente se, para qualquer norma de matrizes, ||B|| < 1. Demonstração:

e(k) = x - x(k)

Mas x = Bx + g (5.1)x(k) = Bx(k-1) + g (5.2)

Logo: e(k) = B(x - x(k-1)) = B e(k-1)

Convergênciae(k) = B(x - x(k-1)) = B e(k-1)

Como fizemos antes para mostrar a convergência do método iterativo linear:

e(k) = B e(k-1)

e(k-1) = B e(k-2)

Logo: e(k) = B2e(k-2)

E, se aplicamos sucessivamente:e(k) = Bke(o)

Convergênciae(k) = Bke(o)

Usando normas consistentes (def. 1.14 do livro):

||AB|| ≤ ||A||.||B|| e logo,||e(k) || ≤ || Bk || . ||e(o) ||

Que tende a zero quando || B || < 1. Note a semelhança com o método iterativo

linear:B é chamada a matriz de iteração do processo

iterativo

Conclusão

Condição suficiente:O sistema é convergente se, para uma norma qualquer de matrizes, ||B||<1.Uma condição necessária e suficiente:

max |λi| <1, onde λi são os autovalores de B

Por hora, vamos nos preocupara com a condiçãosuficiente. Depois veremos como calcular os autovaloresde B.

Algumas normasnorma linha

norma coluna

norma Euclidiana

Exemplo:

Exemplo (convergência)

Um sistema Ax=b que seja reescrito na forma:x = Bx + g

Irá convergir quando o método iterativo for aplicado ?

Não podemos concluir... tentemos outra norma:

Convergência garantida!

Método iterativoVimos que dado um sistema Ax=b, se conseguirmos reescrevê-lo na forma:

x = Bx+g

Podemos usar um processo iterativo do tipo:

x(k+1) = Bx(k) +g.

Que convergirá se, para qualquer norma consistente, ||B|| <1.

Jacobi-RichardsonVamos ver uma maneira simples de obter uma matriz B, chamado de método de Jacobi-Richardson.Seja o sistema :

A matriz A (det(A)≠0) do sistema linear pode ser escrita como a soma de três matrizes:

A = L+D+R.

Jacobi-Richardson

A = L+D+R.

Vamos escolher L,D e R de modo que L só tenha elementos abaixo da diagonalD só tenha elementos na diagonalR só tenha elementos acima da diagonal

Jacobi-RichardsonExemplo (3x3)

A

L D R

Jacobi-RichardsonSupondo det(D)≠ 0 (aii ≠ 0, i=1,...n) e dividindo cada linha pelo elemento da diagonal, temos:

A*

L* I R*exemplificado no caso 3x3, mas válido para qualquer dimensãoobviamente, o vetor bi também é dividido pelo elemento aii.

Jacobi-Richardson

No caso geral:

ReescrevendoPodemos reescrever o sistema como:

(L*+I+R*)x = b*x = -(L*+R*)x + b*

E o processo iterativo fica:B g

Jacobi-Richardson

ConvergênciaVimos que o processo iterativo

converge se ||B|| < 1, para ao menos uma norma.

No caso de Jacobi-Richardson: B = -(L*+R*) e portanto o método converge se, por exemplo: ||L*+R*||1 < 1 (critério das linhas) ou||L*+R*||1 < 1 (critério das colunas):

NotasNote que se a matriz for estritamente diagonal dominante (isto é, em cada linha, o elemento da diagonal é estritamente maior que a soma de todos os outros elementos da linha), então o critério de convergência é automaticamente atendido para

B = -(L*+R*). Note que o critério independe de x(0)

No método de Jacobi-Richardson todos os valores de x da iteração (k+1) dependem dos valores de x da iteração (k), por isso o método é também chamado de Método dos deslocamentos simultâneos.

ExemploResolva o sistema linear:

Pelo método de Jacobi-Richardson com x(0) = (0.7,-1.6,0.6)t , até encontrar um erro

de 10-2.

Exemplo (solução)

Verificando convergência:

Vemos que a matriz é estritamente diagonal dominante:

Portanto o método irá convergir.

Exemplo (solução)Verificando convergência (outros critérios que poderiam ser usados):

Critério das linhas:

Critério das colunas:

Exemplo (solução)

Iteração 1:

Exemplo (solução)

Continuando: