Para resolver um sistema de equações lineares com n variáveis, apresentamos o método de eliminação de Gauss-Jordan. Este enfoque baseia-se em operações elementares de matriz para converter a matriz aumentada em uma forma diagonal, facilitando a extração das soluções.
Considere o sistema genérico:
O método de Gauss-Jordan utiliza transformações elementares de linha, que incluem: trocar duas linhas, multiplicar uma linha por um escalar não nulo, ou somar um múltiplo de uma linha a outra. Essas operações preservam a equivalência do sistema.
Construa a matriz aumentada \( A \) de dimensão \( n \times (n+1) \) combinando a matriz de coeficientes e o vetor de constantes:
A complexidade temporal é \( \mathcal{O}(n^3) \).
Para identificar casos sem solução ou com infinitas soluções, analise as linhas após a eliminação. Se uma linha consistir apenas de zeros na parte dos coeficientes, mas com termo constante não nulo, o sistema é inconsistente. Se ambos forem zero, há graus de liberdade.
A seguir, apresentamos implementações em C++ com estruturas e nomes de variáveis alterados para manter a correção algorítmica.
Exemplo de código para eliminação de Gauss-Jordan básica:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const double LIMIAR = 1e-7;
int main() {
int tamanho;
cin >> tamanho;
vector<vector>> matriz(tamanho + 2, vector<double>(tamanho + 3));
for (int linha = 1; linha <= tamanho; ++linha) {
for (int coluna = 1; coluna <= tamanho + 1; ++coluna) {
cin >> matriz[linha][coluna];
}
}
for (int coluna = 1; coluna <= tamanho; ++coluna) {
int indice_max = coluna;
for (int k = coluna + 1; k <= tamanho; ++k) {
if (fabs(matriz[k][coluna]) > fabs(matriz[indice_max][coluna])) {
indice_max = k;
}
}
swap(matriz[coluna], matriz[indice_max]);
if (fabs(matriz[coluna][coluna]) < LIMIAR) {
cout << "Sem Solução" << endl;
return 0;
}
double fator_pivo = matriz[coluna][coluna];
for (int k = tamanho + 1; k >= 1; --k) {
matriz[coluna][k] /= fator_pivo;
}
for (int linha = 1; linha <= tamanho; ++linha) {
if (linha == coluna) continue;
double multiplicador = matriz[linha][coluna];
for (int k = 1; k <= tamanho + 1; ++k) {
matriz[linha][k] -= multiplicador * matriz[coluna][k];
}
}
}
for (int i = 1; i <= tamanho; ++i) {
printf("%.2lf\n", matriz[i][tamanho + 1]);
}
return 0;
}
</double></vector></cmath></vector></iostream>
Para determinar se o sistema tem solução única, nenhuma ou infinitas, utilize uma variável de controle para linhas processadas. Se após a eliminação o número de linhas processadas for menor que n, verifique os termos constantes nas linhas remanescentes.
Código adaptado para lidar com diferentes tipos de soluções:
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const double TOLERANCIA = 1e-7;
int main() {
int n;
cin >> n;
vector<vector>> sistema(n + 2, vector<double>(n + 3));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n + 1; ++j) {
cin >> sistema[i][j];
}
}
int linha_atual = 1;
for (int col = 1; col <= n; ++col) {
int pivo = linha_atual;
for (int k = linha_atual + 1; k <= n; ++k) {
if (fabs(sistema[k][col]) > fabs(sistema[pivo][col])) {
pivo = k;
}
}
swap(sistema[linha_atual], sistema[pivo]);
if (fabs(sistema[linha_atual][col]) < TOLERANCIA) continue;
double divisor = sistema[linha_atual][col];
for (int k = n + 1; k >= 1; --k) {
sistema[linha_atual][k] /= divisor;
}
for (int i = 1; i <= n; ++i) {
if (i == linha_atual) continue;
double coef = sistema[i][col];
for (int k = 1; k <= n + 1; ++k) {
sistema[i][k] -= coef * sistema[linha_atual][k];
}
}
++linha_atual;
}
--linha_atual;
bool sem_solucao = false, infinitas_solucoes = false;
for (int i = 1; i <= n; ++i) {
bool todos_zeros = true;
for (int j = 1; j <= n; ++j) {
if (fabs(sistema[i][j]) > TOLERANCIA) {
todos_zeros = false;
break;
}
}
if (todos_zeros && fabs(sistema[i][n + 1]) > TOLERANCIA) sem_solucao = true;
if (todos_zeros && fabs(sistema[i][n + 1]) < TOLERANCIA) infinitas_solucoes = true;
}
if (sem_solucao) {
cout << "-1" << endl;
} else if (infinitas_solucoes) {
cout << "0" << endl;
} else {
for (int i = 1; i <= n; ++i) {
cout << "x" << i << "=";
printf("%.2lf\n", sistema[i][n + 1]);
}
}
return 0;
}
</double></vector></cmath></vector></iostream>
O método também se aplica a sistemas de equações XOR, onde as operações são substituídas por XOR. A estrutura é semelhante, mas a eliminação resulta em uma matriz triangular superier.
Para resolver equações XOR, percorra as colunas, selecione pivôs e realize operações XOR para eliminação. A resolução é feita de baixo para cima.
Código para equações XOR:
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<vector>> equacoes(n + 2, vector<int>(n + 3, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
cin >> equacoes[i][j];
}
}
int passo = 1;
for (int col = 1; col <= n; ++col) {
int sel = passo;
for (int k = passo + 1; k <= n; ++k) {
if (equacoes[k][col] > equacoes[sel][col]) {
sel = k;
}
}
swap(equacoes[passo], equacoes[sel]);
for (int i = passo + 1; i <= n; ++i) {
if (equacoes[i][col] == 0) continue;
for (int k = col; k <= n + 1; ++k) {
equacoes[i][k] ^= equacoes[passo][k];
}
}
++passo;
}
int livres = 0;
for (int i = n; i >= 1; --i) {
for (int j = i + 1; j <= n; ++j) {
equacoes[i][n + 1] ^= (equacoes[i][j] & equacoes[j][n + 1]);
}
if ((equacoes[i][i] == 0 && equacoes[i][n + 1] != 0) || (equacoes[i][i] != 0 && equacoes[i][n + 1] == 0)) {
cout << "Não" << endl;
return 0;
}
if (equacoes[i][i] == 0 && equacoes[i][n + 1] == 0) {
equacoes[i][n + 1] = (1 << livres++);
}
}
cout << "Sim" << endl;
for (int i = 1; i <= n; ++i) {
cout << equacoes[i][n + 1] << " ";
}
cout << endl;
return 0;
}
</int></vector></vector></iostream>
Em problemas como "Painter's Problem", modele a situação como um sistema XOR onde cada operação de pintura afeta múltiplos blocos. Defina variáveis indicando se um bloco é pintado e formule equações baseadas no estado inicial.
Para resolver, construa a matriz de coeficientes representando as relações de vizinhança e aplique a eliminação de Gauss-Jordan para XOR.
Exemplo de implementação para o problema do pintor:
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void resolver() {
int n;
cin >> n;
int total = n * n;
vector<vector>> modelo(total + 2, vector<int>(total + 3, 0));
for (int i = 1; i <= total; ++i) {
char estado;
cin >> estado;
modelo[i][total + 1] = (estado == 'w') ? 1 : 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= n; ++j) {
int idx = n * (i - 1) + j;
modelo[idx][idx] = 1;
for (int d = 0; d < 4; ++d) {
int ni = i + dx[d], nj = j + dy[d];
if (ni >= 1 && ni <= n && nj >= 1 && nj <= n) {
int nidx = n * (ni - 1) + nj;
modelo[idx][nidx] = 1;
}
}
}
}
int etapa = 1;
for (int col = 1; col <= total; ++col) {
int max_pivo = etapa;
for (int k = etapa + 1; k <= total; ++k) {
if (modelo[k][col] > modelo[max_pivo][col]) {
max_pivo = k;
}
}
if (modelo[max_pivo][col] == 0) continue;
swap(modelo[etapa], modelo[max_pivo]);
for (int i = 1; i <= total; ++i) {
if (i == etapa || modelo[i][col] == 0) continue;
for (int k = 1; k <= total + 1; ++k) {
modelo[i][k] ^= modelo[etapa][k];
}
}
++etapa;
}
for (int i = etapa; i <= total; ++i) {
if (modelo[i][total + 1]) {
cout << "inf" << endl;
return;
}
}
int resposta = 0;
vector<int> solucao(total + 2);
for (int i = 1; i <= total; ++i) {
solucao[i] = modelo[i][total + 1];
for (int j = i + 1; j <= total; ++j) {
solucao[i] ^= (modelo[i][j] & solucao[j]);
}
resposta += solucao[i];
}
cout << resposta << endl;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int t;
cin >> t;
while (t--) resolver();
return 0;
}
</int></int></vector></cstring></vector></iostream>
Problemas de interruptores são análogos, onde cada interruptor afeta outros, formando um sisstema XOR. A quantidade de soluções é \(2^k\) para \(k\) variáveis livres após a eliminação.