Método de Gauss-Jacobi

O Método de Gauss-Jacobi é um algoritmo iterativo utilizado para resolver sistemas lineares de equações do tipo $A x = b$ , onde $A$ é uma matriz quadrada, $x$ e $b$ são vetores. Este método é particularmente útil quando a matriz $A$ possui certas propriedades que facilitam sua aplicação.

Formulando o Problema

Considere um sistema linear de equações representado por:

\begin{aligned} a_{11} x_{1} + a_{12} x_{2} + \dots + a_{1 n} x_{n} & = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + \dots + a_{2 n} x_{n} & = b_{2} \\ ⋮ \\ a_{n 1} x_{1} + a_{n 2} x_{2} + \dots + a_{n n} x_{n} & = b_{n} \end{aligned}

Podemos expressar este sistema em forma matricial como $A x = b$ , onde:

$A$ é uma matriz $n \times n$ ,
$x$ é um vetor coluna de incógnitas,
$b$ é um vetor coluna dos termos independentes.

Aplicação Do Método

O método de Gauss-Jacobi consiste em decompor a matriz $A$ em suas partes diagonal, triangular inferior e triangular superior. Especificamente, podemos escrever:

A = D + L + U,

onde $D$ é a matriz diagonal formada pelos elementos da diagonal principal de $A$ , $L$ é a matriz triangular inferior (com zeros na diagonal) e $U$ é a matriz triangular superior (também com zeros na diagonal).

Assim, o sistema original pode ser reescrito como:

D x = - L x - U x + b .

Isolando $x$ , obtemos:

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

onde $x^{(k)}$ representa a aproximação do vetor solução no $k$ -ésimo passo.

Exemplo

Considere o sistema linear:

\begin{aligned} 2 x_{1} + x_{2} & = 8 \\ x_{1} + 3 x_{2} & = 10 \end{aligned}

Em forma matricial, temos $A = (\begin{matrix} 2 & 1 \\ 1 & 3 \end{matrix})$ , $b = (\begin{matrix} 8 \\ 10 \end{matrix})$ .

Aplicando o método de Gauss-Jacobi:

x_{1}^{(k + 1)} = \frac{1}{2} (8 - x_{2}^{(k)}) x_{2}^{(k + 1)} = \frac{1}{3} (10 - x_{1}^{(k)})

Criterio de Parada Do Método de Gauss-jacobi

O método de Gauss-Jacobi é uma técnica iterativa utilizada para resolver sistemas lineares. O critério de parada desse método é fundamental para determinar quando a solução atinge um nível aceitável de precisão. Este critério pode ser estabelecido considerando as seguintes condições:

Erro Absoluto:

ϵ = max_{i} | x_{i}^{(k + 1)} - x_{i}^{(k)} | < ε

Aqui, $x_{i}^{(k + 1)}$ e $x_{i}^{(k)}$ representam os valores das variáveis no $(k + 1)$ -ésimo e $k$ -ésimo iterações, respectivamente. $ε$ é um valor pequeno definido pelo usuário que serve como a tolerância de erro.

Erro Relativo:

ϵ = \frac{max_{i} | x_{i}^{(k + 1)} - x_{i}^{(k)} |}{max_{i} | x_{i}^{(k + 1)} |} < ε

Este critério é útil quando as soluções são de ordens de grandeza diferentes.

Número Máximo de Iterações:
O método pode ser interrompido após um número máximo de iterações, $K_{max}$ , seja atingido.

k \geq K_{max}

Convergência Garantida:
Para garantir a convergência do método de Gauss-Jacobi, é necessário que o sistema linear seja diagonalmente dominante ou que as matrizes associadas sejam simétricas e definidas positivas, conforme o Teorema Condição Suficiente de Converência do Método de Gauss-Jacobi

Exemplos

Considere um sistema linear $A x = b$ com matriz $A$ diagonalmente dominante. Suponha que a tolerância de erro $ε = 10^{- 6}$ , o número máximo de iterações seja $K_{max} = 50$ , e os valores iniciais sejam $x^{(0)} = [0, 0, \dots, 0]^{T}$ .

Erro Absoluto:

| x_{i}^{(k + 1)} - x_{i}^{(k)} | < 10^{- 6}

Erro Relativo:

\frac{| x_{i}^{(k + 1)} - x_{i}^{(k)} |}{| x_{i}^{(k + 1)} |} < 10^{- 6}

Observações Importantes

O critério de parada baseado no erro relativo é mais robusto, pois considera a escala dos valores das variáveis.
A escolha do critério de parada deve levar em conta o problema específico e as características do sistema linear.

Código em Python

import numpy as np

def gauss_jacobi(A, b, x0=None, tol=1e-6, max_iter=100):
    """
    Solve the linear system Ax = b using the Gauss-Jacobi iterative method.

    Parameters:
    A : numpy.ndarray
        Coefficient matrix (n x n)
    b : numpy.ndarray
        Right-hand side vector (n,)
    x0 : numpy.ndarray, optional
        Initial guess for the solution (n,). If None, uses zeros.
    tol : float, optional
        Tolerance for the stopping criterion (default: 1e-6)
    max_iter : int, optional
        Maximum number of iterations (default: 100)

    Returns:
    result : dict
        Dictionary with keys:
            'solution'   : Solution vector (numpy.ndarray)
            'iterations' : Number of iterations performed (int)
            'converged'  : Boolean indicating if the method converged (bool)
            'residual'   : Final residual norm (float)
    """
    n = A.shape[0]
    if x0 is None:
        x0 = np.zeros(n)
    x = x0.copy()
    x_new = np.zeros_like(x)

    for iteration in range(1, max_iter + 1):
        for i in range(n):
            s = sum(A[i, j] * x[j] for j in range(n) if j != i)
            x_new[i] = (b[i] - s) / A[i, i]
        if np.linalg.norm(x_new - x, ord=np.inf) < tol:
            residual = np.linalg.norm(np.dot(A, x_new) - b, ord=np.inf)
            return {
                'solution': x_new,
                'iterations': iteration,
                'converged': True,
                'residual': residual
            }
        x[:] = x_new
    residual = np.linalg.norm(np.dot(A, x_new) - b, ord=np.inf)
    return {
        'solution': x_new,
        'iterations': max_iter,
        'converged': False,
        'residual': residual
    }

# Example usage
if __name__ == "__main__":
    A = np.array([[10., -1., 2., 0.],
                  [-1., 11., -1., 3.],
                  [2., -1., 10., -1.],
                  [0.0, 3., -1., 8.]])
    b = np.array([6., 25., -11., 15.])
    x0 = np.zeros(4)
    result = gauss_jacobi(A, b, x0, tol=1e-8, max_iter=100)
    print("Solution:", result['solution'])
    print("Iterations:", result['iterations'])
    print("Converged:", result['converged'])
    print("Final residual norm:", result['residual'])
    print("Verification: A·x =", np.dot(A, result['solution']))
    print("b =", b)