Quels solveurs linéaires itératifs convergent pour des matrices semi-définies positives?

Je veux savoir lesquels des solveurs linéaires classiques (par exemple Gauss-Seidel, Jacobi, SOR) sont garantis pour converger pour le problème où est positif semi défini et bien sûr $Ax=b$ $A$ $b \in im(A)$

(L'avis est semi-défini et non défini) $A$

linear-algebra iterative-method convergence linear-solver olamundo
la source

Voulez-vous dire des matrices semi-définies positives?

meawoppl

Quelle est l'utilité de résoudre un système linéaire avec une telle matrice? Si je ne me trompe pas, si votre matrice semi-définie positive n'est pas singulière, elle est simplement définie positive.

faleichik

Oui je suis sûr. Je dois rafraîchir ma mémoire quant à la preuve réelle, mais d'après ce que vous disiez - si le dénominateur dans le calcul de

est zéro, cela signifie que

est nul, ce qui signifie que toutes les "directions de recherche" dans lesquelles A n'est pas singulier ont été épuisés, et le résidu qui vous reste n'est pas dans la plage de A (et c'est donc la solution "optimale"). Dans le cas où en fait

, cela ne se produira pas car le résidu atteindra zéro juste avant la première fois

α

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

Réglez

. Alors

. CG convergera en raison de

pour tous les

. En d'autres termes, vous ne quittez jamais

pour lequel

est positif-défini.

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: les matrices à densité réduite en mécanique quantique sont semi-définies positives dans de très nombreux cas.

Deathbreath

Réponses:

L'algorithme de gradient conjugué fonctionne pour les problèmes semi-définis et produit la solution de norme minimale.

Arnold Neumaier
la source

Merci. Toute idée sur les solveurs "archaïques", par exemple SOR Gauss-Seidel etc.

olamundo

Ils ne sont presque plus utilisés et je ne sais pas comment ils se comportent.

Arnold Neumaier

Pour clarifier: CG ne fonctionne certainement pas sous forme de vanille pour les matrices semi-définies; cela peut fonctionner en théorie si B est à l'image de A; mais il est peu probable que cela se termine bien dans la pratique numérique. Le MINRES très similaire à base de krylov est un bien meilleur choix ici. De plus, ces solveurs "archaïques" sont largement utilisés dans les solveurs de type multigrille, pour ne citer qu'un exemple.

Eelco Hoogendoorn

$b$ $A$

Il en va tout autrement de Jacobi; ce qui est dommage car qui veut s'embêter avec Gauss-Seidel sur du matériel informatique moderne? Si votre problème peut être divisé en blocs à dominante diagonale, vous avez de la chance; vous pouvez appliquer des mises à jour Jacobi à ces blocs de manière incrémentielle Gauss-Seidel, et tirer le meilleur parti des deux pour ce type de problèmes semi-définis.

Eelco Hoogendoorn
la source