Métodos Directos para Sistemas Lineales

Los métodos directos resuelven un sistema lineal Ax = b en un número finito de pasos aritméticos, típicamente factorizando la matriz y luego resolviendo sistemas triangulares por sustitución.

Definition

Un método directo es un algoritmo que calcula la solución exacta de un sistema lineal —hasta el error de redondeo— en un número finito predeterminado de operaciones, a diferencia de un método iterativo que produce una secuencia de aproximaciones.

Scope

Este tema cubre la eliminación gaussiana, su expresión como una factorización LU, el papel del pivoteo en el control del crecimiento del error, la sustitución hacia adelante y hacia atrás para sistemas triangulares, y los recuentos de operaciones que hacen que los solucionadores directos sean prácticos para matrices densas y en banda.

Core questions

• ¿Cómo reduce la eliminación gaussiana un sistema a forma triangular, y por qué esto es equivalente a una factorización LU?
• ¿Por qué es necesario el pivoteo y cómo controlan el pivoteo parcial y completo el crecimiento del error de redondeo?
• ¿Cuál es el costo computacional de una resolución directa y cómo lo reduce el aprovechamiento de la estructura (simetría, bandeo, escasez)?
• ¿Bajo qué condiciones es la eliminación gaussiana con pivoteo parcial numéricamente estable en la práctica?

Key theories

Factorización LU con pivoteo parcial

La eliminación gaussiana con intercambios de filas factoriza una matriz como PA = LU con L triangular inferior unitaria y U triangular superior; el pivoteo parcial acota los multiplicadores y hace que el método sea fiable para casi todas las matrices encontradas en la práctica.

Factor de crecimiento y estabilidad numérica

El error inverso de la eliminación gaussiana se rige por el factor de crecimiento de las entradas durante la eliminación; aunque es posible un crecimiento exponencial en casos artificiales, el pivoteo parcial mantiene el crecimiento lo suficientemente pequeño como para que el método sea numéricamente estable para prácticamente todos los problemas reales.

Mechanisms

La eliminación gaussiana procede columna por columna: en cada paso se selecciona un pivote (el pivoteo parcial elige el candidato de mayor magnitud en la columna actual), se restan múltiplos de la fila pivote de las filas inferiores para introducir ceros, y los multiplicadores se almacenan para formar L. La U resultante, que es triangular superior, se resuelve mediante sustitución hacia atrás y el lado derecho se procesa mediante sustitución hacia adelante. Para una matriz densa de n por n, la factorización cuesta aproximadamente dos tercios de n al cubo de operaciones, mientras que cada resolución triangular cuesta del orden de n al cuadrado.

Clinical relevance

Los solucionadores directos son la herramienta predeterminada siempre que un sistema denso o en banda de tamaño moderado debe resolverse con total precisión —en el ensamblaje de elementos finitos, la simulación de circuitos, el control y como la resolución interna dentro de esquemas numéricos más grandes— y una única factorización puede reutilizarse para resolver muchos lados derechos de forma económica.

History

Los métodos de eliminación se remontan a Gauss y anteriores, pero su comportamiento en aritmética de precisión finita fue aclarado por el análisis de error inverso de Wilkinson en la década de 1960, que mostró que el pivoteo parcial controla el crecimiento del error y explicó la fiabilidad empírica del método que se había observado durante mucho tiempo en las primeras computadoras.

Key figures

• Carl Friedrich Gauss
• James H. Wilkinson
• Nicholas J. Higham

Seminal works

• trefethen1997
• golub2013
• higham2002

Frequently asked questions

¿Cuándo se debe preferir un método directo sobre uno iterativo?

Los métodos directos se prefieren cuando la matriz es densa o de tamaño moderado, cuando muchos lados derechos comparten una matriz (por lo que se reutiliza una única factorización), o cuando se requiere una solución garantizada finita y de precisión completa. Los sistemas dispersos muy grandes suelen favorecer los métodos iterativos.

¿El pivoteo siempre garantiza un error pequeño?

El pivoteo parcial garantiza la estabilidad numérica en la práctica para casi todas las matrices, pero no supera el mal condicionamiento: si la matriz misma es casi singular, incluso una resolución numéricamente estable puede devolver una solución con un gran error directo.