¿Qué solucionadores lineales iterativos convergen para matrices semidefinidas positivas?

Quiero saber cuáles de los solucionadores lineales clásicos (por ejemplo, Gauss-Seidel, Jacobi, SOR) están garantizados para converger para el problema donde es positivo semi- definido y, por supuesto, $Ax=b$ $A$ $b \in im(A)$

(El aviso es semi definido y no definido) $A$

linear-algebra iterative-method convergence linear-solver olamundo
fuente

¿Te refieres a matrices semi-definidas positivas?

meawoppl

¿De qué sirve resolver un sistema lineal con tal matriz? Si no me equivoco, si su matriz semidefinida positiva no es singular, entonces es simplemente positiva definida.

faleichik

Sí, estoy seguro. Tengo que actualizar mi memoria en cuanto a la prueba real, pero según lo que estabas diciendo: si el denominador en el cálculo de

es cero, significa que

es cero, lo que significa que todas las "direcciones de búsqueda" en las que A no es singular se ha agotado, y el residuo que le queda no está en el lapso de A (y, por lo tanto, esta es la solución "óptima"). En el caso de que de hecho

, esto no sucederá ya que el residual llegará a cero justo antes de la primera vez

α

$\alpha$

A P_{k}

$A P_k$

b \in s p a n (A)

$b \in span(A)$

A P_{k} = 0

$AP_k=0$

olamundo

Conjunto

. Entonces

. CG convergerá debido a

para todos

. En otras palabras, nunca dejas

para el cual

es positivo-definido.

x_{0} = b

$x_0=b$

A^{n} b \in I m (A)

$A^nb\in Im(A)$

x_{n}^{*} A x_{n} > 0

$x_n^\ast Ax_n> 0$

0 \neq x_{n} \in I m (A)

$0\ne x_n\in Im(A)$

I m (A)

$Im(A)$

A

$A$

Deathbreath

@faleichik: las matrices de densidad reducida en mecánica cuántica son semi-definidas positivas en muchos casos.

Deathbreath

Respuestas:

El algoritmo de gradiente conjugado funciona para problemas semidefinidos y produce la solución de norma mínima.

Arnold Neumaier
fuente

Gracias. Cualquier idea acerca de los solucionadores "arcaicos", por ejemplo SOR Gauss-Seidel etc.

olamundo

Ya casi no se usan, y no sé cómo se comportan.

Arnold Neumaier

Para aclarar: CG ciertamente no funciona en forma de vainilla para matrices semi-definidas; puede funcionar en teoría si B está en la imagen de A; pero es poco probable que esto termine bien en la práctica numérica. El MINRES muy similar basado en krylov es una opción mucho mejor aquí. Además, estos solucionadores "arcaicos" se usan ampliamente en solucionadores de tipo multigrid, por nombrar un ejemplo.

Eelco Hoogendoorn

$b$ $A$

Lo mismo no es cierto para Jacobi; lo cual es una pena ya que ¿quién quiere molestarse con Gauss-Seidel en el hardware de la computadora moderna? Si su problema puede dividirse en bloques diagonalmente dominantes, tiene suerte; puede aplicar las actualizaciones de Jacobi a esos bloques de manera incremental de Gauss-Seidel y obtener lo mejor de ambos para este tipo de problemas semi-definidos.

Eelco Hoogendoorn
fuente