Quais solucionadores lineares iterativos convergem para matrizes semidefinidas positivas?

Quero saber quais dos resolvedores lineares clássicos (por exemplo, Gauss-Seidel, Jacobi, SOR) têm a garantia de convergir para o problema onde é semi- definido positivo e, é claro, $Ax=b$ $A$ $b \in im(A)$

(O aviso é semi-definido e não definido) $A$

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

Você quer dizer matrizes semi-definidas positivas?

meawoppl

Qual é a utilidade de resolver sistemas lineares com essa matriz? Se não me engano, se sua matriz semidefinida positiva é não singular, então é simplesmente positiva.

faleichik

Sim eu tenho certeza. Eu tenho que atualizar minha memória quanto à prova real, mas de acordo com o que você estava dizendo - se o denominador no cálculo de

for zero, significa que

é zero, o que significa que todas as "direções de pesquisa" nas quais A não é singular foi esgotado, e o resíduo que você fica não está no intervalo de A (e, portanto, esta é a solução "ideal"). No caso em que, de facto,

, isto não acontecer como o residual irá chegar a zero imediatamente antes de, pela primeira 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

Defina

. Em seguida,

. GC irão convergir devido ao

para todos

. Em outras palavras, você nunca deixa

para o qual

é 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$

Death Breath

@faleichik: matrizes de densidade reduzida na mecânica quântica são semi-definidas positivas em muitos casos.

Deathbreath

Respostas:

O algoritmo de gradiente conjugado funciona para problemas semidefinidos e produz a solução de norma mínima.

Arnold Neumaier
fonte

obrigado. Qualquer idéia sobre os solucionadores "arcaicos", por exemplo, SOR Gauss-Seidel etc.

olamundo

Eles quase nunca são mais usados, e eu não sei como eles se comportam.

Arnold Neumaier

Para esclarecer: o CG certamente não funciona na forma de baunilha para matrizes semi-definidas; pode funcionar em teoria se B estiver na imagem de A; mas é improvável que isso termine bem na prática numérica. O MINRES muito semelhante, baseado em krylov, é uma escolha muito melhor aqui. Além disso, esses solucionadores "arcaicos" são amplamente usados em solucionadores do tipo multigrid, para citar um exemplo.

Eelco Hoogendoorn

$b$ $A$

O mesmo não se aplica a Jacobi; o que é uma pena, já que quem quer se preocupar com Gauss-Seidel em hardware de computador moderno? Se o seu problema puder ser dividido em blocos dominantes na diagonal, você estará com sorte; você pode aplicar as atualizações Jacobi a esses blocos de maneira incremental de Gauss-Seidel e obter o melhor de ambos para esse tipo de problemas semidefinidos.

Eelco Hoogendoorn
fonte