Método del residuo mínimo

El método de residuos mínimos o MINRES es un método de subespacio de Krylov para la solución iterativa de sistemas de ecuaciones lineales simétricas . Fue propuesto por los matemáticos Christopher Conway Paige y Michael Alan Saunders en 1975. ^[1]

A diferencia del popular método CG , el método MINRES no asume que la matriz sea definida positiva , solo es obligatoria la simetría de la matriz.

GMRES frente a MINRES

El método GMRES es esencialmente una generalización de MINRES para matrices arbitrarias. Ambos minimizan la norma 2 del residuo y realizan los mismos cálculos en aritmética exacta cuando la matriz es simétrica. MINRES es un método de recurrencia corta con un requisito de memoria constante, mientras que GMRES requiere almacenar todo el espacio de Krylov, por lo que su requisito de memoria es aproximadamente proporcional al número de iteraciones. Por otro lado, GMRES tiende a sufrir menos pérdida de ortogonalidad. ^[1]^[2]

Propiedades del método MINRES

El método MINRES calcula iterativamente una solución aproximada de un sistema lineal de ecuaciones de la forma donde es una matriz simétrica y un vector . $Ax=b,$ $A\in \mathbb {R} ^{n\times n}$ $b\in \mathbb {R} ^{n}$

Para ello, se minimiza la norma del residuo en un subespacio de Krylov de dimensión a . Aquí hay un valor inicial (a menudo cero) y . $r(x):=b-Ax$ ${\estilo de visualización k}$ $V_{k}=x_{0}+\operatorname {span} \{r_{0},Ar_{0}\ldots ,A^{k-1}r_{0}\}$ $x_{0}\in \mathbb {R} ^{n}$ $r_{0}:=r(x_{0})$

Más precisamente, definimos las soluciones aproximadas a través de donde es la norma euclidiana estándar en . $Estilo de visualización x_{k}}$ $x_{k}:=\mathrm {argmin} _{x\in V_{k}}\|r(x)\|,$ ${\estilo de visualización \|\cdot \|}$ $\mathbb {R} ^{n}$

Debido a la simetría de , a diferencia del método GMRES , es posible realizar este proceso de minimización de forma recursiva, almacenando únicamente los dos pasos anteriores (recurrencia corta). Esto ahorra memoria. ${\estilo de visualización A}$

Algoritmo MINRES

Nota: El método MINRES es más complicado que el método del residuo conjugado, que es algebraicamente equivalente. Por lo tanto, a continuación se elaboró el método del residuo conjugado (CR) como sustituto. Se diferencia del MINRES en que en el MINRES, las columnas de una base del espacio de Krylov (indicadas a continuación por ) se pueden ortogonalizar, mientras que en el CR sus imágenes (indicadas a continuación con ) se pueden ortogonalizar mediante la recursión de Lanczos. Existen variantes más eficientes y preacondicionadas con menos AXPY. Compárese con el artículo. $estilo de visualización p_{k}}$ $estilo de visualización s_ {k}}$

Primero eliges arbitrario y calculas $x_{0}\in \mathbb {R} ^{n}$ ${\begin{aligned}r_{0}&=b-Ax_{0}\\p_{0}&=r_{0}\\s_{0}&=Ap_{0}\end{aligned}}$

Luego iteramos en los siguientes pasos: $k=1,2,\puntos$

Calcular a través de $x_{k},r_{k}$
$\alpha _{k-1}={\frac {\langle r_{k-1},s_{k-1}\rangle }{\langle s_{k-1},s_{k-1} \rangle }}$ $x_{k}=x_{k-1}+\alpha _{k-1}p_{k-1}$ $r_{k}=r_{k-1}-\alpha _{k-1}s_{k-1}$ Si es menor que una tolerancia especificada, el algoritmo se interrumpe con la solución aproximada . De lo contrario, se calcula una nueva dirección de descenso mediante $\|r_{k}\|$ $Estilo de visualización x_{k}}$ $estilo de visualización p_{k}}$ $p_{k}\leftarrow s_{k-1}$
$s_{k}\leftarrow As_{k-1}$
para (el paso no se realiza en el primer paso de iteración) calcular: $l=1,2$ $l=2$ $\beta _{k,l}={\frac {\langle s_{k},s_{kl}\rangle }{\langle s_{kl},s_{kl}\rangle }}$ $p_{k}\leftarrow p_{k}-\beta _{k,l}p_{kl}$ $s_{k}\leftarrow s_{k}-\beta _{k,l}s_{kl}$

Tasa de convergencia del método MINRES

En el caso de matrices definidas positivas, la tasa de convergencia del método MINRES se puede estimar de manera similar a la del método CG. ^[3] Sin embargo, a diferencia del método CG, la estimación no se aplica a los errores de las iteraciones, sino a los residuos. Se aplica lo siguiente:

$\|r_{k}\|\leq 2\left({\frac {{\sqrt {\kappa (A)}}-1}{{\sqrt {\kappa (A)}}+1}}\right)^{k}\|r_{0}\|,$

donde es el número de condición de la matriz . Como es normal, tenemos donde y son los valores propios máximo y mínimo de , respectivamente. $\kappa (A)$ ${\estilo de visualización A}$ ${\estilo de visualización A}$ $\kappa (A)={\frac {\left|\lambda _{\text{máx}}(A)\right|}{\left|\lambda _{\text{mín}}(A)\right|}},$ $\lambda _{\text{máx}}(A)$ $\lambda _{\text{mín}}(A)$ ${\estilo de visualización A}$

Implementación en GNU Octave / MATLAB

función [x, r] = minres ( A, b, x0, maxit, tol ) 
  x = x0 ;  
  r = b - A * x0 ;      
  p0 = r ;  
  s0 = A * p0 ;    
  p1 = p0 ;  
  s1 = s0 ;  
  para iter = 1 : maxit   
    p2 = p1 ; p1 = p0 ;     
    s2 = s1 ; s1 = s0 ;     
    alfa = r '* s1 / ( s1 '* s1 );    
    x = x + alfa * p1 ;      
    r = r - alfa * s1 ;      
    si ( r '* r < tol ^ 2 )   
      romper
    fin
    p0 = s1 ;  
    s0 = A * s1 ;    
    beta1 = s0 '* s1 / ( s1 '* s1 );    
    p0 = p0 - beta1 * p1 ;      
    s0 = s0 - beta1 * s1 ;      
    si iter > 1   
      beta2 = s0 '* s2 / ( s2 '* s2 );    
      p0 = p0 - beta2 * p2 ;      
      s0 = s0 - beta2 * s2 ;      
    fin
  fin
fin

Referencias

^ ab Christopher C. Paige, Michael A. Saunders (1975). "Solución de sistemas indefinidos dispersos de ecuaciones lineales". Revista SIAM sobre análisis numérico . 12 (4): 617–629. doi :10.1137/0712047.
^ Nifa, M. Naoufal. "Solucionadores eficientes para optimización restringida en problemas de identificación de parámetros" (PDF) (Tesis doctoral). pp. 51–52.
^ Sven Gross, Arnold Reusken. Métodos numéricos para flujos incompresibles de dos fases . Sección 5.2: Springer. ISBN 978-3-642-19685-0.{{cite book}}: Mantenimiento de CS1: ubicación ( enlace )