Decomposição LU, passo a passo

Fatorar uma matriz em partes triangular inferior e superior, por que isso é mais rápido que escalonar de novo e como Cholesky especializa o método.

A decomposição LU escreve uma matriz quadrada como o produto de uma matriz triangular inferior por uma triangular superior: A = L·U. Os fatores saem direto da eliminação de Gauss — U é a forma escalonada, e L guarda os multiplicadores que você usou para chegar até ela.

Para que serve

Porque a fatoração é reaproveitável. Resolver Ax = b do zero custa cerca de n³/3 operações. Com L e U em mãos, cada novo lado direito custa apenas n²: resolva Ly = b por substituição direta e depois Ux = y por substituição retroativa. Com dezenas de lados direitos, o ganho é enorme.

O determinante também sai de graça — é o produto da diagonal de U, multiplicado por −1 a cada troca de linha realizada.

Pivotamento

Nem toda matriz admite um A = L·U simples: um zero na posição do pivô quebra o método. A saída é uma matriz de permutação, resultando em P·A = L·U. Na prática o pivotamento é usado de qualquer forma, porque escolher o maior pivô disponível mantém os erros de arredondamento sob controle.

Cholesky: o caso simétrico

Se A for simétrica e definida positiva, ela fatora como A = L·Lᵀ — basta um fator triangular. Cholesky é cerca de duas vezes mais rápida que LU e numericamente bem estável, e é por isso que domina em otimização, mínimos quadrados e estatística (matrizes de covariância são simétricas definidas positivas por construção).

Se em algum momento o algoritmo pedir a raiz quadrada de um número negativo, a matriz não era definida positiva — Cholesky funciona também como teste dessa propriedade.