¿Existe una distinción significativa entre los métodos "directos" e "iterativos" para resolver ecuaciones?

Question

Motivaré esta pregunta con un ejemplo.

El Teorema de Abel-Ruffini afirma que hay ninguna "fórmula" general para las raíces de los polinomios de grado superior a 4. (En concreto, afirma que no existe ninguna solución que pueda expresarse en términos de radicales). Esta falta de una fórmula directa significa que, para calcular las raíces de, por ejemplo, un quíntico genérico, tenemos que recurrir a iterativo algoritmos de búsqueda de raíces .

La distinción también se da en otros problemas, como en el álgebra lineal. Las técnicas "directas" utilizan una "fórmula", mientras que las "indirectas" iteran hasta la convergencia. Lo mismo ocurre con las soluciones de las ecuaciones diferenciales lineales ordinarias -que tienen "fórmulas" directas en términos de exponenciales complejos- y otros sistemas, que no las tienen.

Pero por mucho que me guste fingir que lo entiendo, simplemente no comprendo la distinción entre métodos directos e iterativos. Tal y como yo lo veo, casi cada El método numérico es iterativo, incluso el cálculo de las raíces cuadradas requiere un método iterativo, como el método de Newton, para converger a la respuesta con el error limitado por una tolerancia deseada. No veo por qué es tan importante que no haya una "fórmula" para los quintos, incluso si la hubiera, el ordenador tendría que utilizar un método iterativo como el método de Newton hasta que converja. Y ni siquiera estoy seguro de cómo hacer una definición significativa de la palabra "fórmula" para distinguir entre las dos en primer lugar.
Entonces, ¿dónde está exactamente la distinción y por qué es tan importante? ?

Answer 1

No estoy de acuerdo en que las técnicas directas utilicen siempre una "fórmula". Por ejemplo, al resolver sistemas lineales de ecuaciones "directamente", no se suele utilizar una solución de forma cerrada, sino algo como la descomposición LU o Cholesky.

Los solucionadores iterativos, por otro lado, serían cosas como la iteración de Gauss-Seidel, SOR (sobrerrelajación sucesiva), métodos de subespacio de Krylov como los gradientes conjugados, o métodos multinivel.

¿Cuál es la gran diferencia? En el caso de los sistemas lineales, yo diría que las siguientes son dos de las principales diferencias:

Con un método directo, hay que hacer un cierto trabajo y luego se obtiene la solución. Por ejemplo, si estás haciendo la factorización LU, no puedes parar a mitad de camino y decir "vale, ya está bien". (Aunque existe algo llamado LU incompleta, ¡pero en realidad se utiliza en los métodos iterativos!) Para obtener una solución, hay que ejecutar el algoritmo hasta el final. Normalmente, la solución que obtengas se acercará a la exacta.

Con los métodos iterativos, siempre actualizas tu antigua suposición y te acercas (con suerte) un poco más a la solución verdadera. Esto significa que puedes decidir cuánto trabajo quieres invertir en función de lo precisa que sea tu solución. Por ejemplo, se sabe que el CG converge a la solución exacta en $n$ para una matriz de tamaño $n$ y, por ello, históricamente se consideró en primer lugar un método directo. Sin embargo, después de un tiempo la gente se dio cuenta de que funciona muy bien si se detiene la iteración mucho antes - a menudo se obtiene una muy buena aproximación después de mucho menos de $n$ pasos. De hecho, podemos analizar la rapidez con la que converge el CG. El resultado final es que el CG se utiliza hoy en día como método iterativo para grandes sistemas lineales.

La segunda gran diferencia es que, para un método directo, generalmente se necesita tener toda la matriz almacenada en memoria. No es el caso de los métodos iterativos: aquí sólo se necesita una forma de calcular la aplicación de la matriz a un vector, es decir, el producto matriz-vector. Por lo tanto, si tienes una matriz muy grande, pero puedes calcular con relativa rapidez su aplicación a un vector (por ejemplo, porque la matriz es muy dispersa o tiene algún otro tipo de estructura), puedes utilizar esto a tu favor.