Desenvolva um algoritmo em python que execute a Eliminação de Gauss para resolver um sistema de equações lineares
.
Considere:
Entrada : matriz aumenta
Saída : vetor solução
OBS : Considere a possibilidade de: SPD, SPI ou SI
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
usando Eliminação de Gauss. Entradas e saídas estão especificadas assim:
- Entrada: matriz aumentada (vou chamar de
), ou seja, uma matriz onde as primeiras colunas são os coeficientes e a última coluna é o vetor . - 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
de dimensão . - O número de incógnitas é
(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
, com entradas . Aqui indexa linhas e indexa colunas . As primeiras colunas ( ) correspondem à matriz dos coeficientes e a coluna corresponde ao vetor . - Objetivo: aplicar operações elementares sobre linhas para transformar
em uma forma triangular superior (forma escalonada por linhas), detectar a consistência e, se possível, obter o vetor solução . - 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
até tentando localizar um pivô não nulo na coluna nas linhas ainda não processadas. - Mantenho um índice de linha corrente
(a primeira linha não processada). Inicialmente . - Para uma coluna
, encontro a linha com maior valor absoluto de para . Esse é o pivoteamento parcial; ele evita divisões por valores muito pequenos e melhora estabilidade numérica. - Se o máximo absoluto
for menor que uma tolerância (por exemplo ), 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
com a linha (se ). Agora é o pivô. - Uso esse pivô para zerar todas as entradas abaixo dele na coluna
aplicando, para cada linha , a operação - Após zerar abaixo do pivô incremento
e prossigo para a próxima coluna . - 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
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
a ). - Se existir uma linha tal que todas as entradas dos coeficientes sejam aproximadamente zero, mas a entrada augmentada (coluna
) seja diferente de zero (maior que em módulo), então o sistema é inconsistente (SI). Isso porque a linha corresponde a com . - Caso contrário, calcule:
-
= número de linhas com pelo menos uma entrada não nula nas primeiras colunas (após eliminação). -
= número de linhas não nulas considerando também a última coluna.
-
- Pelo teorema de Rouché–Capelli:
- Se
então o sistema é SI. - Se
então o sistema é SPD (solução única). - Se
então o sistema é SPI (infinitas soluções), com variáveis livres.
- Se
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
linhas e colunas e que (ou seja rank ). - As equações ficarão com a forma (exemplo para a linha
): - Assim podemos calcular
recursivamente (back-substitution) de até usando: - 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
, então existem 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
. A solução geral seria 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
(por exemplo ou dependendo do problema). Em código usaremos um parâmetro 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
(para isso é ), que é o esperado para Eliminação de Gauss.
Passo 8
Resumo do método que o algoritmo implementará (recapitulando a lógica programática):
- Ler
e converter para floats. - Fazer forward elimination com pivoteamento parcial, mantendo registro das colunas que viraram pivôs.
- Após a eliminação, checar linhas do tipo
com para detectar SI. - Calcular
(número pivôs) e comparar com : - 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.
- 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:
aqui (duas incógnitas) e a última coluna é . - Aplicando eliminação, a segunda linha fica
. Se a última coluna também fosse não zero, teríamos com (inconsistente). Se for então rank 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.
“”"
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)