Sistemas Lineares

computacao-cientifica, machine-learning, otimizacao basico algebra-linear

Sistemas Lineares

Resolver $Ax = b$ é o problema computacional mais executado do mundo. Ele aparece dentro de simulação física, ajuste de modelos, otimização, gráficos e praticamente todo método numérico.

Formulação

$$\begin{cases} a_{11}x_1 + \cdots + a_{1n}x_n = b_1 \ \vdots \ a_{m1}x_1 + \cdots + a_{mn}x_n = b_m \end{cases} \iff Ax = b$$

Três leituras do mesmo objeto, e cada uma ilumina uma coisa:

  • Por linhas: cada equação é um hiperplano; a solução é a interseção.
  • Por colunas: $b$ é combinação linear das colunas de $A$; existe solução se e somente se $b$ está no espaço coluna.
  • Por transformação: procura-se o vetor que $A$ leva em $b$.

A leitura por colunas é a mais útil, porque responde de imediato à pergunta da existência.

Existência e unicidade

Seja $r$ o posto de $A$ e $[A|b]$ a matriz aumentada:

CondiçãoResultado
$\operatorname{posto}(A) < \operatorname{posto}([A\vert b])$Sem solução (inconsistente)
$\operatorname{posto}(A) = \operatorname{posto}([A\vert b]) = n$Solução única
$\operatorname{posto}(A) = \operatorname{posto}([A\vert b]) < n$Infinitas soluções

Quando há infinitas soluções, o conjunto é $x_p + \mathcal{N}(A)$: uma solução particular mais o espaço nulo. O número de variáveis livres é $n - r$.

Eliminação gaussiana

O método padrão transforma o sistema em triangular por operações que preservam o conjunto de soluções: trocar linhas, multiplicar linha por escalar não nulo, somar múltiplo de uma linha a outra.

def eliminacao(A, b):
    n = len(A)
    for k in range(n):
        # pivoteamento parcial: escolhe o maior pivô em módulo
        p = max(range(k, n), key=lambda i: abs(A[i][k]))
        A[k], A[p] = A[p], A[k]
        b[k], b[p] = b[p], b[k]
        if abs(A[k][k]) < 1e-12:
            raise ValueError('matriz singular ou quase singular')
        for i in range(k + 1, n):
            f = A[i][k] / A[k][k]
            for j in range(k, n):
                A[i][j] -= f * A[k][j]
            b[i] -= f * b[k]
    # substituição regressiva
    x = [0.0] * n
    for i in reversed(range(n)):
        x[i] = (b[i] - sum(A[i][j] * x[j] for j in range(i + 1, n))) / A[i][i]
    return x

Custo: $\frac{2}{3}n^3$ operações, dominado pela eliminação.

Pivoteamento: por que é obrigatório

Sem pivoteamento, o algoritmo falha ao encontrar pivô nulo — e, pior, produz resultado ruim com pivô pequeno. Considere:

$$\begin{pmatrix} 10^{-20} & 1 \ 1 & 1 \end{pmatrix}\begin{pmatrix}x_1\x_2\end{pmatrix} = \begin{pmatrix}1\2\end{pmatrix}$$

Sem trocar linhas, o multiplicador é $10^{20}$, e ao subtrair, o valor $1$ da segunda linha é engolido pelo arredondamento. O resultado sai completamente errado, sem nenhum aviso.

Com pivoteamento parcial — trocar para que o maior elemento em módulo da coluna vire pivô — os multiplicadores ficam com módulo $\le 1$ e a amplificação de erro é controlada. É por isso que toda implementação séria pivoteia, e por isso que escrever eliminação "do jeito do livro" sem pivoteamento é um defeito latente.

Sistemas sobredeterminados e mínimos quadrados

Com mais equações que incógnitas ($m > n$), em geral não há solução exata. Busca-se então o $x$ que minimiza o resíduo:

$$\min_x |Ax - b|_2$$

A condição de otimalidade dá as equações normais:

$$A^TA,x = A^Tb$$

Elas resolvem o problema, mas têm um defeito numérico sério: o número de condição de $A^TA$ é o quadrado do de $A$, o que pode destruir a precisão. A prática recomendada é usar a fatoração QR ou a SVD, que resolvem o mesmo problema sem elevar o condicionamento ao quadrado.

Mínimos quadrados é exatamente a regressão linear: ajustar um modelo a dados com ruído.

import numpy as np
x, residuos, posto, sv = np.linalg.lstsq(A, b, rcond=None)

Condicionamento

O número de condição mede a sensibilidade da solução a perturbações:

$$\kappa(A) = |A| \cdot |A^{-1}|$$

Interpretação prática: com $\kappa(A) \approx 10^k$, perdem-se cerca de $k$ dígitos de precisão. Em precisão dupla (cerca de 16 dígitos), $\kappa = 10^{14}$ deixa apenas dois dígitos confiáveis.

Uma matriz mal condicionada é quase singular: pequenas mudanças em $b$ produzem grandes mudanças em $x$. Verifique sempre com numpy.linalg.cond antes de confiar num resultado.

Exemplo trabalhado

$$\begin{cases} 2x + y = 5 \ 4x + 3y = 11 \end{cases}$$

Eliminando: $L_2 \leftarrow L_2 - 2L_1$ dá $y = 1$. Substituindo na primeira: $2x + 1 = 5$, logo $x = 2$.

Verificando na segunda: $4(2) + 3(1) = 11$. Correto.

Aplicações em computação

Regressão. Todo ajuste de mínimos quadrados é um sistema linear.

Simulação. Métodos implícitos para equações diferenciais exigem resolver um sistema esparso a cada passo de tempo.

Gráficos. Coordenadas baricêntricas, deformação de malhas e iluminação global recaem em sistemas lineares.

Otimização. O passo de Newton resolve um sistema com a hessiana a cada iteração.

Redes. Análise de circuitos e fluxo em redes por leis de conservação produzem sistemas lineares.

Erros comuns

  • Não pivotear. Perda catastrófica de precisão.
  • Usar equações normais em problema mal condicionado, em vez de QR ou SVD.
  • Comparar com zero exato ao testar singularidade; use tolerância relativa.
  • Ignorar a estrutura. Sistemas esparsos, simétricos ou de banda têm métodos muito mais rápidos.
  • Calcular a inversa. Sempre mais lento e menos estável que fatorar.

Leituras recomendadas

  • Trefethen e Bau, Numerical Linear Algebra — as 40 lições são a melhor introdução moderna ao assunto; condicionamento e estabilidade tratados com clareza rara.
  • Golub e Van Loan — a referência completa sobre algoritmos matriciais.
  • Documentação do SciPy scipy.linalg — rotinas especializadas para matrizes de banda, simétricas e esparsas.
  • Higham, Accuracy and Stability of Numerical Algorithms — para quem quer entender profundamente o que dá errado e por quê.

Lloyd N. Trefethen and David Bau III (1997). Numerical Linear Algebra. SIAM. DOI: 10.1137/1.9780898719574. Gene H. Golub and Charles F. Van Loan (2013). Matrix Computations. Johns Hopkins University Press. DOI: 10.56021/9781421407944. Nicholas J. Higham (2002). Accuracy and Stability of Numerical Algorithms. SIAM. DOI: 10.1137/1.9780898718027.

Referências

  1. Lloyd N. Trefethen; David Bau III (1997). Numerical Linear Algebra. SIAM.
  2. Gene H. Golub; Charles F. Van Loan (2013). Matrix Computations. Johns Hopkins University Press.
  3. Nicholas J. Higham (2002). Accuracy and Stability of Numerical Algorithms. SIAM.