Cálculo Numérico : março 2016

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

Resolver analítica ou numericamente os problemas abaixo.

1. 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 diretos: (i) de Cramer, (ii) eliminação de Gauss e (iii) decomposição A = LU.

Método de Cramer:

Consideramos o sistema

. Suponhamos, sem perda de generalidade, que a1≠0. Escalonando esse sistema (substituímos a 2ª equação pela soma dela com a 1ª multiplicando por –a2a1), temos

Lembremos que a matriz incompleta dos coeficientes do sistema é M=(a1 b1a2 b2). Assim, a1b2 - a2b1 é exatamente det M, que indicamos por D.

Se substituirmos, em M, a coluna dos coeficientes de y pela coluna dos coeficientes independes, obteremos (a1 c1a2 c2), cujo determinante é igual a a1c2 - a2c1, indicado por Dy.

Dessa forma na 2ª equação de (*) temos:

(a1b2 - a2b1)y=a1c2 - a2c1 ➔ D = Dy.

Se D ≠ 0, vem que y=-Dy D.

Substituindo y na 1ª equação (*), segue que:

(a1b2 - a2b1) . x=c1b2 - b1c2 (**)

Se substituirmos, em M, a coluna dos coeficientes de pela coluna dos coeficientes independentes, obteremos (c1 b1c2 b2), cujo determinante é c1b2 - b1c2, indicado por Dx.

Assim (**) temos:

D . x = Dy x=-DxD

Em resumo, o sistema

é possível e determinado se, e somente se,

M =|a1 b1a2 b2| ≠ 0. A solução do sistema é dada por:

x=-DxD e y=-Dy D

Os resultados acima são conhecidos como Regra de Cramer e podem ser generalizados para um sistema n x m (n equações e n incógnitas). A Regra de Cramer é um importante recurso da resolução de sistemas lineares possíveis e determinados, especialmente quando o escalonamento se torna muito trabalhoso (por causa dos coeficientes das equações do sistema), ou ainda quando o sistema é literal.

Fonte: IEZZI, G.; DOLCE, O.; DEGENSZAJN, D. M; PÉRIGO, R. Matemática volume único. São Paulo: Atual Editora, Cap. 22 p. 397 - 398.

Método de Eliminação de Gauss

O método da Eliminação de Gauss consiste em transformar o sistema linear original num sistema linear equivalente com a matriz dos coeficientes triangular superior, pois estes são de resolução imediata. Dizemos que dois sistemas lineares são equivalentes quando possuem a mesma solução.

Resolução de sistemas triangulares

Seja o sistema linear Ax = b, onde A: matriz n x n, triangular superior, com elementos da diagonal diferentes de zero. Escrevendo a equação desse sistema temos:

Da ultima equação temos

xn=bnann

xn-1 pode então ser obtido da penúltima equação:

xn-1 =bn-1-an-1, nxnan-1,n-1

E assim sucessivamente obtêm-se xn-2, ..., x2 e finalmente x1:

x1 =b1-a12x2 - a13x3 -… a1nxn a11

Descrição do método da Eliminação de Guass

TEOREMA 1

Seja Ax = b um sistema linear. Aplicando a este sistema uma sequencia de equações elementares escolhidas entre:

trocar duas equações;
multiplicar uma equação por uma constante não nula;
adicionar um múltiplo de uma equação a uma outra equação;

obtemos um novo um novo sistema Ax= b e os sistemas Ax = b e Ax= b são equivalentes.

Descrevemos a seguir como método de Eliminação de Gauss usa o teorema para triangularizar a matriz A. Vamos supor que det(A) ≠ 0.

A eliminação é efetuada por colunas que chamaremos etapa k do processo a fase em que se elimina a variável xk das equações k + 1, k + 2, ..., n.

Usaremos a notação aij (k) para denotar o coeficiente da linha i coluna j no final da k-ésima etapa, bem como bi (k) será o i-ésimo elemento do vetor constante na etapa k.

Considerando det(A) ≠ 0, é sempre possível reescreve o sistema linear de forma que o elemento da posição a11 seja diferente de zero, usando apenas a operação elementar (i):

Onde aij (0)=aij, bi (0) =bi e aij (0)≠ 0.

Exemplo:

Etapa 1

Etapa 2

Etapa 3

O algorítmico acima efetua, na fase da eliminação, 4n3+3n2-7n6, operações e para resolver o sistema triangular superior, o número de operações a estudar é n2.

Assim, o total de operações para se resolver um sistema linear pelo método da Eliminação de Gauss é 4n3+9n2-7n6.

Escalonamento sem pivoteamento

• Repetir da primeira até a penúltima coluna;

• Repetir para as linhas abaixo da diagonal principal;

• Aplicar operação elementar com o objetivo de zerar o elemento da linha corrente abaixo da diagonal principal;

• Alterar linha da matriz dos coeficientes;

• Alterar linha do vetor das constantes.

Escalonamento com pivoteamento

• Repetir da primeira até a penúltima coluna;

• Verificar a necessidade de se fazer o pivoteamento;

• Procurar uma linha adequada;

• No caso de encontrar, fazer a permuta das linhas;

• Verificar a necessidade de se fazer o escalonamento da coluna corrente;

• Repetir para as linhas abaixo da diagonal principal;

• Aplicar operação elementar com o objetivo de zerar o elemento da linha corrente abaixo da diagonal principal;

• Alterar linha da matriz dos coeficientes;

• Alterar linha do vetor das constantes.

Fonte: http://www1.univap.br/spilling/CN/apostila1.pdf

Fonte: RUGGIERO, M. A. G. e LOPES, V. L. .R. CÁLCULO NUMÉRICO: Aspectos teóricos e computacionais; 2ª edição. Cap. 3, P 119 – 125.

Método de decomposição A = LU

O método da fatoração A = LU é uma outra ferramenta da solução direta de sistemas lineares da forma Ax = b. É de certa utilidade para sistemas em que a sua matriz pode ser fatorada em outras duas, ou seja, A = LU, em que L é uma matriz triangular inferior, possui valores não nulos abaixo e na diagonal, e U é matriz triangular superior, os valores não nulos são acima e na diagonal.

Procedimento para se achar as matrizes triangulares de uma matriz original A:

Assumir que a eliminação de Gauss pode ser realizada no sistema linear Ax = b, sem que haja trocas de linha.
Multiplicar a matriz A original pela matriz de transformação de Gauss M(k), em que k = 1, 2, 3,..., n-1, e repetir esse processo até que se chegue a uma matriz triangular superior.

A matriz de transformação é formada por uma diagonal principal composta por 1, e para um dado k, por elementos negativos -mk+1, k até -mn, k, que possuem valores e são calculados através da equação mj, 1 = a(1)j1 / a(1)11, em que a(1)j1 é o elemento da j-ésima linha e a(1)11 é o primeiro elemento da matriz original.

Achar a inversa da matriz de transformação de Gauss, [M(k)]-1, em que k = 1, 2, 3,..., n. Esse procedimento fornece os valores das colunas da matriz triangulo inferior, L(k).
Multiplicar todas as matrizes L(k), para k = 1, 2, 3,..., n. Isso resultará na matriz triangular inferior L.

Resolução de um sistema linear:

Utilizar o processo de substituição regressiva para se encontrar o sistema na forma triangular.
Converter os sistemas para matriz A e matriz superior.
Através do passo 3 do procedimento de encontrar matrizes triangulares, encontrar a matriz triangular inferior.
Substituir A por LU, na equação Ax = b (1).
Substituir Ux por y, um vetor cujos valores são y(i), em que i = 1, 2, 3,..., n, na equação (1), chegando a Ly = b (2).
Resolver a equação Ux = y, usando os valores obtidos no passo anterior. A partir dessa equação, se chega aos valores das incógnitas do vetor x.

Apesar de ser um método trabalhoso, é útil para reduzir o número de operações necessárias para se resolver um sistema linear. Quando trabalhamos com um sistema linear do tipo Ax = b usando o método de eliminação de Gauss, são necessárias O(n3/3) operações, enquanto sistemas lineares que envolvam sistema triangulo superior, que utilizam substituição regressiva, necessitam de O(n²) operações.

Resumindo: