Lo que se trata de gradiente conjugado que lo hace útil para atacar a sistemas lineales dispersos. ¿Por qué steepest descent ser significativamente peor? Por favor, tenga en cuenta que todavía estoy tratando totalmente envolver mi cabeza alrededor de la presencia de los dos métodos.
También por favor, hágamelo saber si hay algo que yo pueda aclarar.
Lo que se trata de gradiente conjugado que lo hace útil para atacar a sistemas lineales dispersos.
Para cualquier subespacios de Krylov método de como conjugar los gradientes, GMRES, MINRES, BiCG, etc., es necesario proporcionar esencialmente sólo la rutina que realiza la matriz-vector producto. Podría ser claro que la realización de la matriz-vector de productos con matrices dispersas es mucho más barato que con matrices densas. Además, estos métodos son útiles para los problemas en los que la matriz no existe "físicamente" en una forma que hace que la solución directa los métodos basados en la matriz de factorisations menos atractivo.
Sin embargo, con el fin de hacer que los métodos iterativos eficiente que uno necesita normalmente para proporcionar también una buena preconditioner que podría considerarse como una aproximación de la acción de la inversa de la matriz de un sistema de/operador. Generalmente, preconditioners se basan en información incompleta factorisations, dispersas inversa aproximaciones, multi-nivel de métodos, etc. Es muy depende del problema.
Sin embargo, el objetivo es evitar los problemas que pudieran surgir directa con los métodos de solución. Para problemas tales como los que surgen en 3D discretizations, los métodos directos pueden ser costosos debido al aumento de los requisitos de memoria debido a que el relleno (factorización de una matriz dispersa puede ser mucho menos dispersa (más densa) que el original de la matriz). Los modernos métodos de solución puede combinar tanto los directos e iterativos enfoques, aunque.
¿Por qué steepest descent ser significativamente peor?
El gradiente conjugado (CG) y steepest descent (SD) métodos tienen algo en común, que minimizan los $A$-norma del error en $Ax=b$ sobre un cierto subespacio. Tenga en cuenta que esto es equivalente a la minimización de la energía "funcional"$f(x)=\frac{1}{2}(Ax,x)-(b,x)$. En la SD, una de las actualizaciones de la aproximación a $x$ simplemente en la dirección de la "steepest descent" de $f(x)$, es decir, en la dirección de la residual. Esto significa que la SD realiza simplemente una unidimensional de minimización. La aplicación de la CG no difiere demasiado de la de la SD, pero su "magia" se basa en el hecho de que el 2 de dos términos en la fórmula recursiva (para el simétrica positiva definida $A$) lo suficiente como para construir una base ortogonal de los residuos formando el llamado subespacios de Krylov (el lapso de $\{r_0,Ar_0,A^2r_0,\ldots\}$). Como resultado, el nuevo vector residual se mantiene ortogonal para el subespacio generado por la anterior residuos y minimizando los $A$-norma del error sobre la totalidad del subespacio de Krylov la dimensión $k$ a $k$-ésima iteración. Debido a esto, el CG es (en teoría) garantiza la convergencia a la solución exacta $x$ en la mayoría de los $n$ iteraciones, donde $n$ es el tamaño del sistema.
Desde SD realiza sólo en una dimensión y la optimización de CG minimiza el error sobre la totalidad del subespacio de Krylov la dimensión cada vez más con cada iteración, SD puede ser el esperado mucho peor que el de CG. Un ejemplo conocido por $n=2$ ilustra cómo el malo SD puede realizar mediante el seguimiento de su ruta de acceso al mínimo de$f$, mientras que el CG converge al mínimo en (al menos) dos iteraciones!
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
