Método de Jacobi

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa

O método de Jacobi trata-se de um algoritmo para determinar a solução de um sistema de equações lineares com os maiores valores absolutos em cada linha e coluna dominados pelo elemento da sua diagonal. Trata-se de uma versão simplificada do algoritmo de valores próprios de Jacobi. O método tem o nome do matemático Alemão Carl Gustav Jakob Jacobi.

O método iterativo de Jacobi é um método clássico que data do final do século XVIII. Técnicas iterativas são raramente utilizadas para solucionar sistemas lineares de pequenas dimensões, já que o tempo requerido para obter um mínimo de precisão ultrapassa o requerido pelas técnicas diretas como a eliminação gaussiana. Contudo, para sistemas grandes, com grande porcentagem de entradas de zero, essa técnicas são eficientes em termo de cálculo como de armazenamento. Sistemas desse tipo frequentemente surgem na análise de circuitos e na solução numérica de problemas de valor de limite e equações diferenciais parciais.[1]

Descrição[editar | editar código-fonte]

Dado uma matriz quadrada de n equações lineares:

A\mathbf x = \mathbf b

em que:

A=\begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & a_{nn} \end{bmatrix}, \qquad  \mathbf{x} = \begin{bmatrix} x_{1} \\ x_2 \\ \vdots \\ x_n \end{bmatrix} , \qquad  \mathbf{b} = \begin{bmatrix} b_{1} \\ b_2 \\ \vdots \\ b_n \end{bmatrix}.

Então A pode ser decomposto num componente diagonal D e o resto R:

A=D+R \qquad \text{Onde} \qquad D = \begin{bmatrix} a_{11} & 0 & \cdots & 0 \\ 0 & a_{22} & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\0 & 0 & \cdots & a_{nn} \end{bmatrix}, \qquad R = \begin{bmatrix} 0 & a_{12} & \cdots & a_{1n} \\ a_{21} & 0 & \cdots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\a_{n1} & a_{n2} & \cdots & 0 \end{bmatrix}

O sistema de equações lineares pode ser reescrito como:

D \mathbf{x} = \mathbf{b} - R \mathbf{x}

O método de Jacobi é um método iterativo que resolve o membro esquerdo da expressão em ordem a x ao usar o método resultante da iteração anterior no membro direito. Analiticamente, isto pode ser escrito como:

 \mathbf{x}^{(k+1)} = D^{-1} (\mathbf{b} - R \mathbf{x}^{(k)}).

A expressão pode será então:

 x^{(k+1)}_i  = \frac{1}{a_{ii}} \left(b_i -\sum_{j\ne i}a_{ij}x^{(k)}_j\right),\quad i=1,2,\ldots,n.

Nota-se que a computação de x_i^{k+1} é feita com base em todos os valores obtidos em iterações anteriores. Ao contrário do método de Gauss-Seidel, não se pode reescrever x_i^{(k)} com x_i^{(k+1)}, pois esse valor é necessário durante a continuação da computação. Esta é a diferença mais significativa entre o método de Jacobi e o método de Gauss-Seidel e é o motivo que o torna um algoritmo paralelo.

Algoritmo[editar | editar código-fonte]

Definir a primeira tentativa x^{0} para a solução

Enquanto o resultado não convergir faça
para i\, desde 1\, até n\, faça
 \sigma \gets 0
para j\, desde 1\, até n\, faça
se j\, é diferente de i\, então
 \sigma  \gets \sigma  + a_{ij} x_j^{(k)}
  x_i^{(k+1)}  \gets {{\left( {b_i  - \sigma } \right)} \over {a_{ii} }}
  k \gets k+1

Convergência[editar | editar código-fonte]

O método converge sempre se a matriz A é estrita ou irredutivelmente uma matriz estritamente diagonal dominante.

Se A é diagonal dominante ou irredutivelmente diagonal dominante, então o raio espectral da matriz de iteração

\rho(D^{-1}R) < 1.

O método de Jacobi por vezes converge quando estas condições são satisfeitas.

Recentemente, uma técnica de duplo ciclo foi introduzida para forçar a convergência para a solução correcta do algoritmo de Jacobi mesmo quando as condições suficientes para convergência não são verificadas. A técnica de duplo ciclo funciona para matrizes positivas definidas ou dependentes de colunas.[2]

Exemplos[editar | editar código-fonte]

1.Um sistema linear Ax=b é dado por

 A =
      \begin{bmatrix}
           2 & 3 \\
           5 & 7 \\
           \end{bmatrix},
 b =
      \begin{bmatrix}
           11 \\
           13 \\
           \end{bmatrix}
e  x^{(0)} =
        \begin{bmatrix}
           1.1 \\
           2.3 \\
        \end{bmatrix} .

Pretende-se usar a equação  x^{(k)}=Tx^{(k-1)} + C . Agora é necessário encontrar  D^{-1} a matriz inversa dos valores da diagonal A através duma decomposição A = LDU

 D^{-1} =
      \begin{bmatrix}
           1/2 & 0 \\
           0 & 1/7 \\
           \end{bmatrix},
 L =
      \begin{bmatrix}
           0 & 0 \\
           -5 & 0 \\
           \end{bmatrix}
e  U =
        \begin{bmatrix}
           0 & -3 \\
           0 & 0 \\
        \end{bmatrix} .

Para se encontrar T recorre-se à equação  T=D^{-1}(L+U) .

 T =
      \begin{bmatrix}
           1/2 & 0 \\
           0 & 1/7 \\
           \end{bmatrix}
\left\{
      \begin{bmatrix}
           0 & 0 \\
           -5 & 0 \\
           \end{bmatrix}
 +
        \begin{bmatrix}
           0 & -3 \\
           0 & 0 \\
        \end{bmatrix}\right\}
 =
        \begin{bmatrix}
           0 & -1.5 \\
           -0.714 & 0 \\
        \end{bmatrix}  .

Agora, encontrada T, torna-se necessário obter C recorrendo à expressão  C=D^{-1}b .

 C =
      \begin{bmatrix}
           1/2 & 0 \\
           0 & 1/7 \\
           \end{bmatrix}
      \begin{bmatrix}
           11 \\
           13 \\
           \end{bmatrix}
 =
        \begin{bmatrix}
           5.5 \\
           1.857 \\
        \end{bmatrix} .

Assim, agora teremos  x^{(1)}= Tx^{(0)}+C .

 x^{(1)} =
      \begin{bmatrix}
           0 & -1.5 \\
           -0.714 & 0 \\
           \end{bmatrix}
      \begin{bmatrix}
           1.1 \\
           2.3 \\
           \end{bmatrix}
 +
        \begin{bmatrix}
           5.5 \\
           1.857 \\
        \end{bmatrix}
 =
        \begin{bmatrix}
           2.05 \\
           1.07 \\
        \end{bmatrix}  .

E agora estamos em posição de encontrar  x^{(2)} .

 x^{(2)} =
      \begin{bmatrix}
           0 & -1.5 \\
           -0.714 & 0 \\
           \end{bmatrix}

      \begin{bmatrix}
           2.05 \\
           1.07 \\
           \end{bmatrix}
 +
        \begin{bmatrix}
           5.5 \\
           1.857 \\
        \end{bmatrix}
 =
        \begin{bmatrix}
           3.893 \\
           0.3927 \\
        \end{bmatrix}  .

Agora que se está na posse de X matrizes é possível avaliar a convergência para aproximar as soluções.


2.Efetuando os cálculos com três casas decimais, determine a solução do sistema de equações lineares AX=B por meio do método de Jacobi, onde :

 A =
      \begin{bmatrix}
           8 & 1 & -1 \\
           1 & -7 & 2 \\
           2 & 1 & 9 \\
           \end{bmatrix}


B=\begin{bmatrix}
           8 \\
           -4 \\
           12 \\
           \end{bmatrix}

Nesse caso tem-se:

 x_{1}^{(k+1)} = 1 -0.125x_{2}^{(k)}+ 0,125x_{3}^{(k)}


x_{2}^{(k+1)}=0.571 +0.143x_{1}^{(k)}+ 0.286x_{3}^{(k)}


x_{3}^{(k+1)}=1.333 -0.222x_{1}^{(k)} -0.111x_{2}^{(k)},

E os resultados de aplicação do método de Jacobi são mostrados na tabela:

k 0 1 2 3 4 5 6 7
x_{1}^{k} 0 1,000 1,095 1,065 1,063 1,062 1,062 1,062
x_{2}^{k} 0 0,571 1,095 1,190 1,209 1,210 1,210 1,210
x_{3}^{k} 0 1,333 1,618 1,698 1,702 1,703 1,703 1,703

Notemos que a partir da 5 interação o método se estabiliza, com uma erro de aproximadamente 0,04%.

Critério de convergência (critério das linhas)[editar | editar código-fonte]

Seja o sistema linear Ax=b e seja: α_{k} = \sum^{n}_{j=1,j\ne k}\frac{|a_{kj}|}{|a_{kk}|}.

Se α= máx α_{k}<1, sendo 1≤k≤n, então o método de Jacobi gera uma sequencia {x(k)} convergente para a solução do sistema dado, independente da escolha da aproximação inicial, x(0).

Exemplo: Analisando a matriz A do sistema linear:

 A =
      \begin{bmatrix}
           10 & 2 & 1 \\
           1 & 5 & 1 \\
           2 & 3 & 10 \\
           \end{bmatrix},

temos:

α_{1} = \frac{2+1}{10} = \frac{3}{10} = 0.3 < 1;

α_{2} =\frac{1+1}{5} =0.4 < 1;

α_{3} = \frac{2+3}{10} = 0.5 < 1

e então máx α_{k} = 0.5 < 1, sendo 1≤k≤3 donde, pelo critério das linhas, temos garantia de convergência para o método de Jacobi. Sempre que o critério de linhas não for satisfeito, devemos tentar uma permutação de linhas e/ou colunas de forma a obtermos uma disposição para a qual a matriz dos coeficientes satisfaça o critérios das linhas.[3]

Referências

  1. Cálculo numérico: características matemáticas. Sperandio,Décio. Mendes,João Teixeira.Moken e Silva,Luiz Henry. São Paulo,Pearson,2003.
  2. Fixing the convergence of the Gaussian belief propagation algorithm. J. K. Johnson, D. Bickson and D. Dolev. In the International symposium on information theory (ISIT), July 2009. http://arxiv.org/abs/0901.4192
  3. Cálculo numérico: aspectos teóricos e computacionais. Ruggiero, Márcia A. Gomes e Lopes,Vera lúcia da Rocha. 2ª Ed. São Paulo, Editora: Pearson, 1996

Ver também[editar | editar código-fonte]

Ligações externas[editar | editar código-fonte]