Resolución numérica de sistemas
Mapa conceptual
Directo frente a iterativo
Dos filosofías. Los métodos directos (eliminación, factorización) transforman el sistema y dan la solución exacta en un número finito de pasos, salvo redondeo. Los iterativos parten de una conjetura y la refinan, acercándose a la solución de forma asintótica.
Eliminación gaussiana
El caballo de batalla: triangularizar el sistema eliminando incógnitas fila a fila y luego sustituir hacia atrás. Su coste es cúbico en el número de incógnitas, lo que lo hace prohibitivo para sistemas de millones de variables densas.
El pivote
Dividir por un pivote cercano a cero amplifica el redondeo de forma catastrófica. La eliminación con pivote parcial reordena las filas para usar el mayor valor disponible como divisor: barato y esencial para la estabilidad de un método por lo demás vulnerable.
Factorización LU
La eliminación gaussiana es en el fondo una factorización del sistema en un factor triangular inferior por uno superior. Su ventaja: una vez calculada la factorización, resolver para múltiples términos independientes es barato, solo sustitución hacia adelante y atrás.
Cholesky para matrices definidas
Si la matriz es simétrica y definida positiva (como las de mínimos cuadrados o covarianzas), la factorización de Cholesky es unas dos veces más rápida y estable que LU, explotando la estructura. Reconocer esa estructura ahorra trabajo.
Coste y estructuras
Una matriz dispersa (mayoría de ceros, como las de diferencias finitas) no debe almacenarse ni tratarse como densa: guardar solo los términos no nulos y reordenar para minimizar el relleno cambia radicalmente el coste. Ignorar la estructura es tirar eficiencia.
Por qué iterativos
Para sistemas enormes y dispersos, el coste cúbico de los directos se vuelve inasumible por memoria y tiempo. Los métodos iterativos solo necesitan multiplicar la matriz por un vector, operación barata en matrices dispersas, y convergen a una solución aproximada sin factorizar nunca.
Jacobi y Gauss-Seidel
Los iterativos más simples despejan cada incógnita a partir de las demás, usando estimaciones previas. Gauss-Seidel mejora a Jacobi usando los valores recién actualizados en la misma pasada. Convergen solo bajo condiciones como dominancia diagonal.
El gradiente conjugado
Para sistemas simétricos definidos positivos, el método del gradiente conjugado minimiza una cuadrática asociada recorriendo direcciones conjugadas. Convergencia mucho más rápida que los simples, y en aritmética exacta resolvería en un número finito de pasos igual a la dimensión.
GMRES y no simétricos
Cuando la matriz no es simétrica, GMRES busca la mejor aproximación en un subespacio de Krylov creciente. Es el caballo de batalla de los sistemas generales dispersos, aunque requiere reiniciar para controlar memoria y convergencia.
El precondicionador
La clave del éxito iterativo es el precondicionado: transformar el sistema con una matriz parecida a la inversa de la original pero barata de aplicar, de modo que el nuevo sistema converja rápido. Un buen precondicionador vale más que un método elegante.
Condicionamiento otra vez
El número de condición de la matriz gobierna tanto la precisión alcanzable como la velocidad de convergencia iterativa. Una matriz mal condicionada hace que los métodos directos acumulen error y que los iterativos avancen a paso de tortuga. El condicionamiento lo es todo.
Criterio de parada iterativo
Se itera hasta que el residuo (la diferencia entre el lado izquierdo evaluado y el derecho) cae por debajo de una tolerancia relativa. Un residuo pequeño no siempre significa solución exacta: de nuevo el condicionamiento puede esconder un error grande bajo un residuo engañosamente bajo.
Sistemas no lineales
Para ecuaciones acopladas no lineales, el Newton multidimensional linealiza cada paso resolviendo un sistema con la matriz jacobiana. Convergencia cuadrática cerca de la solución, pero cada iteración cuesta resolver un sistema lineal, a veces enorme.
El precio de la jacobiana
En problemas de muchas incógnitas, la jacobiana es densa y costosa. Se usan versiones casi-Newton (Broyden, BFGS) que actualizan una aproximación de la inversa sin recalcularla, o jacobianas dispersas que solo requieren derivadas relevantes.
Errores frecuentes
- Aplicar un método directo a una matriz dispersa gigante ignorando el relleno y la memoria.
- Iterar sin precondicionar y concluir que el método no converge cuando el problema es el condicionamiento.
- Aceptar una solución por residuo pequeño sin verificar el condicionamiento de la matriz.
La razón principal para preferir un método iterativo sobre uno directo es:
La factorización de Cholesky aplica a cualquier matriz cuadrada simétrica.
Mínimos cuadrados como sistema
Ajustar un modelo lineal equivale a resolver el sistema normal, cuya matriz es una Gram simétrica definida positiva. Su condicionamiento es el cuadrado del de la matriz de diseño: por eso en la práctica se prefiere una factorización QR, numéricamente más sana que formar el sistema normal.
QR y valores singulares
La factorización QR y la descomposición en valores singulares (SVD) resuelven mínimos cuadrados de forma estable y revelan el rango y el condicionamiento reales del problema. Son más caras, pero robustas justo donde el sistema normal se vuelve frágil.
Paralelismo y escalado
La multiplicación matriz-vector, núcleo de los métodos iterativos, paraleliza bien, lo que hace favorecerlos en computación de alto rendimiento. El equilibrio entre coste por iteración, número de iteraciones y comunicación define el método elegido a escala.
Sistemas: vocabulario
Ordena el razonamiento para elegir solucionador:
Estructura
Tamano
Directo
Iterativo
Netlib Linear Algebra
Referencia de algoritmos y librerías clásicas de álgebra lineal numérica.
Tienes un sistema de dos millones de incógnitas con matriz dispersa y simétrica definida positiva, mal condicionada. ¿Directo o iterativo, y qué palanca priorizarías para que converja?
Math.NET Numerics
Biblioteca de métodos numéricos.