Cálculo Numérico : 03/30/16

3. Descreva, fazendo um passo-a-passo explicativo (pode conter um pseudocódigo, fluxograma, etc), como resolver sistemas de equações lineares usando os métodos iterativos: (i) Jacobi e (ii) Gauss-Seidel.

Método de Jacobi

O método de Jacobi é um algoritmo para resolver sistemas de equações lineares, tem o nome do matemático Alemão Carl Gustav Jakob Jacobi. Como o exemplificado abaixo:

Dada uma matriz quadrada de ${\textstyle 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)})$ ou, equivalentemente:

$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.$

Fluxograma

Exemplo:

Método de Gauss-Seidel

O método de Gauss-Seidel é um método iterativo para resolução de sistemas de equações lineares, seu nome é uma homenagem aos matemáticos alemães Carl Friedrich Gauss e Philipp Ludwig von Seidel. É semelhante ao método de Jacobi (e como tal, obedece ao mesmo critério de convergência). É condição suficiente de convergência que a matriz seja estritamente diagonal dominante, i. e., fica garantida a convergência da sucessão de valores gerados para a solução exata do sistema linear.

Procuramos a solução do conjunto de equações lineares, expressadas em termos de matriz como:

A iteração Gauss-Seidel é

$x^{(k+1)} = \left( {D - L} \right)^{ - 1} \left( {U x^{(k)} + b} \right),$

onde

; as matrizes

, e

representam respectivamente os coeficientes da matriz

: a diagonal, triangular estritamente inferior, e triangular estritamente superior; e

é o contador da iteração. Esta expressão matricial é utilizada principalmente para analisar o método. Quando implementada, Gauss-Seidel, uma aproximação explícita de entrada por entrada é utilizada:

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

Diferenciando-se do método de Gauss-Jacob:

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

Sendo que o método de Gauss-Seidel apresenta convergência mais rápida que este último.

Note que o cálculo de $x^{(k+1)}_i$ utiliza apenas os elementos de $x^{(k+1)}\,$ que já havia sido calculada e apenas aqueles elementos de $x^{(k)}\,$ já haviam avançado para a iteração

. Isto significa que nenhum armazenamento adicional é necessário, e que computacionalmente pode ser substituído ( $x^{(k)}\,$ por $x^{(k+1)}\,$ ). A iteração geralmente continua até que a solução esteja dentro da tolerância especificada.

Calculando o Erro

O cálculo do erro consiste em se pegar a maior diferença entre as raízes da iteração k-1 e k, e dividi-las por o valor de x máximo da iteração atual;

$erro^{(k)} = \frac{\max\left|x_{i}^{(k)}-x_{i}^{(k-1)}\right|}{\displaystyle\max_{1\le i \le n}\left|x_{i}^{(k)}\right|}$

Diferença entre os dois métodos

Nota-se que a computação de $x_i^{k+1}$ , no método de Jacobi é 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.

Diagrama mostrando esquematicamente a dependência de cada um dos termos nas três primeiras iterações de uma matriz A:3x3 dos métodos de Gauss-Jacobi e Gauss-Seidel.

Referências

RUGGIERO, M. A. G. e LOPES, V. L. .R. CÁLCULO NUMÉRICO: Aspectos teóricos e computacionais; 2ª edição. Cap. 3, p. 155 - 176.

http://www1.univap.br/spilling/CN/CN_revisao1.pdf

4. Analisar a convergência usando o critério das linhas e o critério de Sassenfeld do seguinte sistema linear e resolvê-lo usando os dois métodos iterativos explicados no exercício anterior. Usar x0 = (-2,4; 5; 0; 3) e tolerância ε<10-2

5x1 + 2x2 + x3 = 7,

-x1 + 4x2 + 2x3 = 3,

2x1 - 3x2 + 10x3 = -1.

Convergência: Critério das Linhas

Este método pode também ser aplicado para análise de convergência no método de Seidel.

Resolução pelo método de Jacobi (Excel)

A partir da 10.ª interação todos os valores de erros são menores que o valor da tolerância, portanto os valores são : X1=0,9994

X2=0,9971

X3=-0,0008

Resolução pelo método de Gauss-Seidel (Scilab)

A função resulta em 6 interações e seus valores finais são: 1.000068869335937 ; 1.000212232470703 e 0.000049895874023.

Podemos observar que há uma diferença no número total de interações necessárias entre os métodos de Jacobi e Gauss-Seidel, de 10 para 6 interações; nesse sistema em específico, o segundo método mostra-se mais eficiente uma vez que haja uma diminuição de 40% nas interações em relação ao primeiro.

5. [OPCIONAL] Resolva o seguinte sistema linear usando o metodo de Jacobi.

Usar x0 = (0,7 ;-1,6 ;0,6) e tolerância < 10-2.

10x1 + 2x2 + x3 = 7 ;

x1 + 5x2 + x3 = -8 ;

2x1 + 3x2 + 10x3 = 6 :

Solução exata e x1 = 1; x2 = -2 e x3 = 1

Cálculo Numérico

quarta-feira, 30 de março de 2016

Lista 3B - Exercícios, resoluções e discussões.