Desenvolva um algoritmo em python que execute a Eliminação de Gauss para resolver um sistema de equações lineares \mathrm{AX}=\mathrm{B}.
Considere:
Entrada : matriz aumenta
Saída : vetor solução
OBS : Considere a possibilidade de: SPD, SPI ou SI

Passo 1

O enunciado pede que eu desenvolva um algoritmo em Python que resolva um sistema linear dado por \mathrm{A}\mathrm{X}=\mathrm{B} usando Eliminação de Gauss. Entradas e saídas estão especificadas assim:
  • Entrada: matriz aumentada (vou chamar de \mathrm{M}), ou seja, uma matriz onde as primeiras n colunas são os coeficientes e a última coluna é o vetor \mathrm{B}.
  • Saída: vetor solução (quando existir solução única) ou indicação adequada quando houver infinitas soluções ou sistema impossível.
  • Devemos considerar as três possibilidades clássicas: sistema possível e determinado (SPD), sistema possível e indeterminado (SPI, infinitas soluções) e sistema impossível (SI).
Informações relevantes dadas ou implicadas:
  • A entrada é a matriz aumentada \mathrm{M} de dimensão m \times (n+1).
  • O número de incógnitas é n (colunas da parte dos coeficientes).
  • Precisamos usar Eliminação de Gauss (com cuidado numérico: pivoteamento parcial será adotado).
  • Devemos detectar e tratar os casos SPD, SPI e SI e retornar um vetor solução quando apropriado.

Passo 2

Como representar a matriz aumentada e o objetivo do algoritmo (explicação didática dos objetos):
  • A matriz aumentada será chamada de \mathrm{M}, com entradas \mathrm{M}_{ij}. Aqui i indexa linhas i=0,\dots,m-1 e j indexa colunas j=0,\dots,n. As primeiras n colunas ( j=0,\dots,n-1) correspondem à matriz dos coeficientes \mathrm{A} e a coluna j=n corresponde ao vetor \mathrm{B}.
  • Objetivo: aplicar operações elementares sobre linhas para transformar \mathrm{M} em uma forma triangular superior (forma escalonada por linhas), detectar a consistência e, se possível, obter o vetor solução \mathrm{X}=(x_0,\dots,x_{n-1})^\top.
  • Observação simples: cada operação elementar de linha não altera o conjunto de soluções do sistema. Essas operações são:
    • trocar duas linhas,
    • multiplicar uma linha por escalar não nulo,
    • somar a uma linha um múltiplo de outra linha.

Passo 3

Explicando a eliminação (passo a passo do processo matemático):
  • Vamos percorrer as colunas de j=0 até j=n-1 tentando localizar um pivô não nulo na coluna j nas linhas ainda não processadas.
  • Mantenho um índice de linha corrente r (a primeira linha não processada). Inicialmente r=0.
  • Para uma coluna j, encontro a linha p com maior valor absoluto de \mathrm{M}_{ij} para i=r,\dots,m-1. Esse é o pivoteamento parcial; ele evita divisões por valores muito pequenos e melhora estabilidade numérica.
  • Se o máximo absoluto \max_{i=r,\dots,m-1} |\mathrm{M}_{ij}| for menor que uma tolerância \varepsilon (por exemplo \varepsilon=10^{-12}), considero que não há pivô nesta coluna e passo para a próxima coluna (essa coluna será uma coluna de variável livre possivelmente).
  • Se houver pivô, troco a linha r com a linha p (se p\neq r). Agora \mathrm{M}_{rj} é o pivô.
  • Uso esse pivô para zerar todas as entradas abaixo dele na coluna j aplicando, para cada linha i>r, a operação \text{linha}_i \leftarrow \text{linha}_i - \frac{\mathrm{M}_{ij}}{\mathrm{M}_{rj}} \cdot \text{linha}_r.
  • Após zerar abaixo do pivô incremento r \leftarrow r+1 e prossigo para a próxima coluna j+1.
  • Ao final desse processo teremos a matriz em forma escalonada por linhas (forma triangular superior parcial). O número de pivôs encontrados é o posto (rank) da matriz dos coeficientes \mathrm{A} após a eliminação.

Passo 4

Como detectar SPD, SPI e SI (teorema de Rouché–Capelli explicado de forma simples):
  • Após a eliminação em forma escalonada, observamos as linhas que ficaram iguais a zero na parte dos coeficientes (colunas 0 a n-1).
  • Se existir uma linha tal que todas as entradas dos coeficientes sejam aproximadamente zero, mas a entrada augmentada (coluna n) seja diferente de zero (maior que \varepsilon em módulo), então o sistema é inconsistente (SI). Isso porque a linha corresponde a 0 = c com c\neq 0.
  • Caso contrário, calcule:
    • \operatorname{rank}(\mathrm{A}) = número de linhas com pelo menos uma entrada não nula nas primeiras n colunas (após eliminação).
    • \operatorname{rank}([\mathrm{A}\,|\,\mathrm{B}]) = número de linhas não nulas considerando também a última coluna.
  • Pelo teorema de Rouché–Capelli:
    • Se \operatorname{rank}(\mathrm{A}) \neq \operatorname{rank}([\mathrm{A}\,|\,\mathrm{B}]) então o sistema é SI.
    • Se \operatorname{rank}(\mathrm{A}) = \operatorname{rank}([\mathrm{A}\,|\,\mathrm{B}]) = n então o sistema é SPD (solução única).
    • Se \operatorname{rank}(\mathrm{A}) = \operatorname{rank}([\mathrm{A}\,|\,\mathrm{B}]) < n então o sistema é SPI (infinitas soluções), com n-\operatorname{rank}(\mathrm{A}) variáveis livres.

Passo 5

Back-substitution (como obter a solução quando ela é única) — fórmula e explicação:
  • Suponha que após a eliminação temos uma submatriz triangular superior nas primeiras r linhas e n colunas e que r=n (ou seja rank =n).
  • As equações ficarão com a forma (exemplo para a linha k): \mathrm{M}_{kk} x_k + \sum_{j=k+1}^{n-1} \mathrm{M}_{kj} x_j = \mathrm{M}_{k,n}.
  • Assim podemos calcular x_k recursivamente (back-substitution) de k=n-1 até k=0 usando: x_k = \frac{\mathrm{M}_{k,n} - \sum_{j=k+1}^{n-1} \mathrm{M}_{kj} x_j}{\mathrm{M}_{kk}}.
  • Em palavras: primeiro resolve-se a última variável (pois aí só aparece um coeficiente), depois substitui-se esse valor nas equações superiores e assim por diante.

Passo 6

Como obter uma solução particular no caso de infinitas soluções (SPI):
  • Se \operatorname{rank}(\mathrm{A})=r<n, então existem n-r variáveis livres.
  • Uma estratégia simples e prática (útil em prova e também computacionalmente) é:
    • Identificar as colunas que são pivôs (cada pivô corresponde a uma variável básica).
    • As colunas restantes são índices das variáveis livres.
    • Para obter uma solução particular escolho as variáveis livres iguais a zero (ou outro valor conveniente) e faço back-substitution apenas sobre as variáveis básicas, usando as mesmas fórmulas de back-substitution, porque as incógnitas não-pivôs aparecem do lado das somas.
  • Assim obtenho uma solução particular \mathrm{X}_p. A solução geral seria \mathrm{X} = \mathrm{X}_p + combinação linear das vetores fundamentais das soluções homogêneas, mas geralmente para o enunciado basta: detectar SPI e fornecer uma solução particular e indicar quais variáveis são livres.

Passo 7

Observações numéricas e escolha de tolerância:
  • Comparações com zero devem usar uma tolerância \varepsilon (por exemplo \varepsilon=10^{-12} ou \varepsilon=10^{-9} dependendo do problema). Em código usaremos um parâmetro tol padrão.
  • Pivoteamento parcial (escolher o maior elemento em módulo na coluna entre as linhas remanescentes) reduz problemas numéricos e evita divisões por números quase zero.
  • Complexidade do algoritmo: custo aproximado O(m n^2) (para m\approx n isso é O(n^3)), que é o esperado para Eliminação de Gauss.

Passo 8

Resumo do método que o algoritmo implementará (recapitulando a lógica programática):
  1. Ler \mathrm{M} e converter para floats.
  2. Fazer forward elimination com pivoteamento parcial, mantendo registro das colunas que viraram pivôs.
  3. Após a eliminação, checar linhas do tipo 0\cdots0 \mid c com c\neq 0 para detectar SI.
  4. Calcular \operatorname{rank}(\mathrm{A}) (número pivôs) e comparar com n:
    • Se rank = n -> SPD: usar back-substitution para retornar o vetor solução.
    • Se rank < n e não SI -> SPI: identificar variáveis livres, escolher valores (por exemplo zeros) para elas e obter uma solução particular por back-substitution; também retornar informação sobre as variáveis livres.
  5. O retorno do algoritmo será um tuplo com um código de status e a solução / informações úteis.

Passo 9

Exemplo conceitual rápido (para fixar):
  • Considere a matriz aumentada (exemplo pequeno) antes da eliminação: \mathrm{M} = \begin{pmatrix} 1 & 2 & 3 \\\\ 2 & 4 & 6 \end{pmatrix}aqui n=2 (duas incógnitas) e a última coluna é \mathrm{B}.
  • Aplicando eliminação, a segunda linha fica 0\;0\;0. Se a última coluna também fosse não zero, teríamos 0= c com c\neq0 (inconsistente). Se for 0 então rank =1<2 e há infinitas soluções (uma variável livre).
  • Para obter uma solução particular podemos fixar a variável livre igual a zero e resolver a outra.

Passo 10

Agora apresento o algoritmo em Python que implementa tudo o que expliquei: ele recebe a matriz aumentada (lista de listas ou matrix-like), faz eliminação com pivoteamento parcial, detecta SPD/SPI/SI e devolve resultado. O formato de retorno é documentado no código.

Resposta

def gaussian_elimination(A_aug, tol=1e-12):
“”"
Resolve um sistema linear dado pela matriz aumentada A_aug usando Eliminação de Gauss
com pivoteamento parcial.
Entrada:
  A_aug: lista de listas ou matriz-like com m linhas e n+1 colunas (augmented matrix).
         Cada elemento será convertido para float.
  tol: tolerância para considerar um número como zero (padrão 1e-12).

Saída:
  Tupla (status, solution, free_vars)
  - status: string, um dos 'SPD' (única solução), 'SPI' (infinitas soluções), 'SI' (impossível)
  - solution:
      * se status == 'SPD': lista de n floats (a solução única)
      * se status == 'SPI': lista de n floats (uma solução particular obtida atribuindo 0 às variáveis livres)
      * se status == 'SI' : None
  - free_vars:
      * se status == 'SPI': lista com índices (0-based) das variáveis livres
      * caso contrário: []

Observações:
  - O algoritmo não usa bibliotecas externas (puro Python).
  - Para SPI retornamos uma solução particular e os índices das variáveis livres.
"""
# Copia e converte para float
M = [list(map(float, row)) for row in A_aug]
m = len(M)
if m == 0:
    return ('SPD', [], [])  # sistema vazio
n_plus_1 = len(M[0])
n = n_plus_1 - 1  # número de incógnitas

# Verificação de consistência da forma das linhas
for i, row in enumerate(M):
    if len(row) != n_plus_1:
        raise ValueError("Todas as linhas devem ter o mesmo número de colunas (n+1). Linha {} tem {} colunas.".format(i, len(row)))

pivot_cols = []  # lista das colunas que viraram pivô
r = 0  # linha atual onde colocar o próximo pivô

# Forward elimination com pivoteamento parcial por coluna
for col in range(n):
    # Encontrar o melhor pivô (maior em módulo) abaixo/na linha r
    pivot_row = max(range(r, m), key=lambda i: abs(M[i][col])) if r < m else None
    if pivot_row is None or abs(M[pivot_row][col]) <= tol:
        # Coluna com pivô efetivamente zero -> variável possivelmente livre
        continue
    # Trocar linhas r e pivot_row se necessário
    if pivot_row != r:
        M[r], M[pivot_row] = M[pivot_row], M[r]
    # Normalmente não normalizamos a linha do pivô; apenas usamos para eliminar abaixo
    pivot_val = M[r][col]
    # Eliminar entradas abaixo do pivô na coluna col
    for i in range(r+1, m):
        if abs(M[i][col]) <= tol:
            continue
        factor = M[i][col] / pivot_val
        # row_i <- row_i - factor * row_r
        for j in range(col, n_plus_1):
            M[i][j] -= factor * M[r][j]
            # pequenas correções para evitar restos numéricos muito pequenos
            if abs(M[i][j]) < tol:
                M[i][j] = 0.0
    pivot_cols.append(col)
    r += 1
    if r == m:
        break

rankA = len(pivot_cols)

# Verificar inconsistencia: linha com coeficientes todos zero e termo independente não-zero
for i in range(rankA, m):
    all_zero_coef = True
    for j in range(n):
        if abs(M[i][j]) > tol:
            all_zero_coef = False
            break
    if all_zero_coef and abs(M[i][n]) > tol:
        return ('SI', None, [])

# Agora decidir SPD / SPI
if rankA == n:
    # Sistema possível e determinado: solução única. Fazer back-substitution.
    x = [0.0] * n
    # Percorrer pivot rows de trás para frente. Precisamos mapear cada pivot para sua linha.
    # Note que após a eliminação pivôs ocuparam as primeiras rankA linhas, mas nem sempre em
    # colunas consecutivas. Vamos recuperar as linhas onde os pivôs estão.
    # Observação: pivot_cols[i] corresponde ao pivô na linha i (para i < rankA).
    for i in range(rankA - 1, -1, -1):
        col = pivot_cols[i]
        # soma das entradas já conhecidas
        s = M[i][n]  # termo independente
        for j in range(col+1, n):
            s -= M[i][j] * x[j]
        # divisor é M[i][col]
        if abs(M[i][col]) <= tol:
            # Isto não deveria ocorrer se rankA == n e pivôs bem escolhidos, mas verificamos
            return ('SI', None, [])
        x[col] = s / M[i][col]
    return ('SPD', x, [])
else:
    # rankA < n e não inconsistente => infinitas soluções (SPI)
    # Identificar variáveis livres: colunas que não estão em pivot_cols
    pivot_set = set(pivot_cols)
    free_vars = [j for j in range(n) if j not in pivot_set]
    # Construir uma solução particular atribuindo 0 às variáveis livres
    x = [0.0] * n
    # Fazer back-substitution apenas para as variáveis básicas (pivôs)
    for i in range(rankA - 1, -1, -1):
        col = pivot_cols[i]
        s = M[i][n]
        for j in range(col+1, n):
            s -= M[i][j] * x[j]  # se j for livre e x[j]=0 então não contribui
        if abs(M[i][col]) <= tol:
            # Inesperado, mas por segurança
            return ('SI', None, [])
        x[col] = s / M[i][col]
    return ('SPI', x, free_vars)

Exercícios relacionados