¿Hay alguna otra razón, excepto "el gran tamaño de la matriz", que me haga preferir el uso de solucionadores iterativos a los directos, para (sistemas algebraicos lineales)? Gracias
Respuestas
¿Demasiados anuncios?
El problema de la "gran matriz es sin duda una de las razones.
Otra es que solucionadores iterativos pueden ejecutarse hasta que el resultado sea "suficientemente bueno", por lo que está comprobando los resultados cada k-ésima iteración.
Otra razón es que la matriz explícita puede no estar disponible, por lo que puede obtener Ax para cualquier x especificada pero no la propia A.
Andy
Puntos
21
Panorama general:
- En teoría, la eliminación gaussiana con pivotaje parcial tiene algunos problemas graves de estabilidad. Es técnicamente estable hacia atrás en una dimensión fija $n$ pero el factor multiplicador constante es algo así como $2^n$ . Así, en dimensiones superiores a $50$ errores de tamaño epsilon de la máquina en teoría podría escalar hasta errores de orden 1 (a grandes rasgos, "ningún dígito correcto" en la solución). Hay un ejemplo explícito de esto en Trefethen y Bau (es algo así como la identidad con la última columna llena de 1s). Sorprendentemente, este fenómeno es bastante raro en las aplicaciones; todavía no he visto una buena explicación de por qué.
- Quizá no sepas que el problema de "la matriz es demasiado grande" tiene dos aspectos diferentes. Uno es "no puedo ensamblar la matriz en su forma completa". Piénsalo: supongamos que tienes 8 GB de RAM, sabemos que un número de doble precisión es de 8 bytes, por lo que puedes almacenar unos mil millones de números de doble precisión a la vez en la RAM. Por tanto, las matrices más grandes que puedes almacenar en forma completa con acceso rápido son de unos 50000 por 50000. Si necesitas más, entonces $A$ sólo está disponible para usted como "una caja negra que computa $Ax$ dado $x$ ", por lo que los métodos iterativos son todo lo que puedes hacer.
- El otro aspecto del problema de "la matriz es demasiado grande" es que puede que no tengas $O(n^3)$ tiempo para quemar. Tomando como ejemplo esas matrices de 50000 por 50000, ejecutar la eliminación gaussiana sobre ellas lleva aproximadamente $10^{14}$ operaciones. El número de operaciones en coma flotante que podemos hacer en un segundo varía en función de la máquina y de lo bien que se paralelice el problema, pero si suponemos que son 10.000 millones, la eliminación gaussiana en una matriz de 50000 por 50000 tardaría unas 2 horas. Más rápido que eso sería bueno.
- Incluso cuando se puede montar $A$ a veces se te presenta naturalmente como una caja negra que computa $Ax$ dado $x$ y montarlo como una matriz puede costarle tiempo adicional. Esto me pasó a mí: Tenía una función lineal que actuaba sobre coeficientes de Fourier que estaba definida en el espacio real, así que para calcular la matriz de la misma tenía que hacer $2n$ $n$ -FFT dimensionales. En mi caso $n$ era sólo $60$ así que esto no fue tan malo, pero habría sido mucho peor con grandes $n$ .
- Los problemas de mínimos cuadrados suelen estar muy mal condicionados cuando se abordan con la eliminación de Gauss sobre las ecuaciones normales. Pueden estar tan mal condicionados que las únicas buenas opciones entre los métodos "directos" se basan en la descomposición QR (reducir algebraicamente $(A^T A)^{-1} A^T b$ a $R^{-1} Q^T b$ ) y SVD (se reduce algebraicamente a $V \Sigma^{-1} U^T b$ ). E incluso esa opción de SVD no es realmente directa, porque no existe un método directo para el propio SVD.
El pequeño cuadro se reduce a "qué propiedades de $A$ podemos explotar para solucionar problemas como los anteriores". Por ejemplo, si $A$ es bastante escasa, $Ax$ puede ser bastante rápido de calcular, por lo que incluso $n$ las multiplicaciones matriciales podrían resultar mucho más rápidas que $n^3$ tiempo (aunque el peor caso para $n$ multiplicaciones de matrices es $n^3$ tiempo).
