krylov-method – ¿Cuáles son las principales diferencias entre GMRES y FOM?

Pregunta:

Estoy leyendo "Métodos iterativos para sistemas lineales dispersos" del profesor Saad (segunda edición) .

El algoritmo básico para FOM se da en la página 166 y el algoritmo básico para GMRES se da en la página 172.

Tanto FOM como GMRES parecen construir el mismo subespacio de Krylov y la misma matriz de Hessenberg superior.

Sin embargo, al final de los algoritmos, FOM resuelve un sistema lineal para obtener $ x_m $ (aparentemente descartando la última fila de la matriz de Hessenberg) mientras que GMRES resuelve un problema de mínimos cuadrados con toda la matriz de Hessenberg para obtener $ x_m $ . Entonces, la solución a ambos problemas es $ y_m = V_m x_m + x_0 $ y creo que $ V_m $ son iguales en ambos algoritmos.

Mis preguntas son:

  1. ¿Por qué esta diferencia (en mi opinión, aparentemente pequeña) crea dos algoritmos separados?

  2. ¿Por qué GMRES se usa ampliamente sobre FOM?

Claramente parece que me estoy perdiendo algo, pero no sé qué.

Respuesta:

Hay una gran diferencia entre GMRES y FOM. También es la razón por la que recomendaría GMRES sobre FOM.

En aritmética exacta, los residuos obtenidos por GMRES forman una secuencia decreciente. Está seguro de que los residuos de GMRES no aumentarán en ausencia de errores de redondeo. Una vez que el residuo calculado se desvía de este patrón simple, no se gana nada con más iteraciones.

En el caso de FOM, es posible una curva residual positiva arbitraria. Aún puede detectar cuándo más iteraciones no tienen sentido, pero debe medir el tamaño de los elementos subdiagonales $ h_ {j + 1, j} $ ya que $ V_k $ es un subespacio invariante para una matriz $ A + \ Delta A $ donde $ \ | \ Delta A \ | _2 = h_ {j + 1, j} $ . Encontrará una fórmula explícita para $ \ Delta A $ en el libro de Saad. En otras palabras, una vez que $ h_ {j + 1, j} $ cae por debajo de $ \ tau \ | A \ | _2 $ donde $ \ tau $ es el error relativo normal asociado con el cálculo de $ A $ , no tiene sentido hacer más pasos de Arnoldi. En esta etapa, es muy posible que hayamos resuelto exactamente el verdadero problema.

Decidir cuándo más iteraciones de FOM son inútiles requiere más conocimiento y comprensión que decidir cuándo más iteraciones de GMRES son inútiles.

Leave a Comment

Your email address will not be published. Required fields are marked *

Scroll to Top

web tasarım