Application sûre de méthodes itératives sur des matrices diagonalement dominantes

Supposons que le système linéaire suivant soit donné où est le Laplacien pondéré connu pour être défini positif avec un espace nul unidimensionnel par , et la variance de translation de , c'est-à-dire que ne change pas la valeur de la fonction (dont la dérivée est ). Les seules entrées positives de trouvent sur sa diagonale, qui est une somme des valeurs absolues des entrées négatives hors diagonale.

\begin{matrix} (1) & L x = c, \end{matrix}

$Lx=c,\tag1$

L

$L$

s e m i -

$semi-$

1_{n} = (1, \dots, 1) \in R^{n}

$1_n=(1,\dots,1)\in\mathbb{R}^n$

x \in R^{n}

$x\in\mathbb{R}^{n}$

x + a 1_{n}

$x+a1_n$

(1)

$(1)$

L

$L$

J'ai trouvé dans un travail universitaire très cité dans son domaine que, bien que soit dominant en diagonale, des méthodes telles que le gradient conjugué, Gauss-Seidl, Jacobi, pouvaient toujours être utilisées en toute sécurité pour résoudre . La raison est que, en raison de l'invariance de la traduction, il est sûr de fixer un point (par exemple, supprimer la première ligne et la colonne de et la première entrée de ), convertissant ainsi en une matrice diagonale dominante. Quoi qu'il en soit, le système d'origine est résolu sous la forme complète de , avec . $L$ $not~strictly$ $(1)$ $L$ $c$ $L$ $strictly$ $(1)$ $L\in\mathbb{R}^{n\times n}$

Cette hypothèse est-elle correcte et, dans l'affirmative, quelle est la justification alternative? J'essaie de comprendre comment la convergence des méthodes tient toujours.

Si la méthode de Jacobi est convergente avec , que pourrait-on dire sur le rayon spectral de la matrice d'itération , où est la matrice diagonale avec les entrées de sur sa diagonale? Est-ce que , donc différent des garanties de convergence générales pour ? Je le demande car les valeurs propres de la La matrice laplacienne avec celles sur la diagonale doit être dans la plage . $(1)$ $\rho$ $D^{-1}(D-L)$ $D$ $L$ $\rho(D^{-1}(D-L)\leq1$ $\rho(D^{-1}(D-L))<1$ $D^{-1}L$ $[0, 2]$

De l'œuvre originale:

......................................

À chaque itération, nous calculons une nouvelle disposition (x (t +1), y (t + 1)) en résolvant le système linéaire suivant: Sans perte de généralité, nous pouvons fixer l'emplacement de l'un des les capteurs (en utilisant le degré de liberté de translation de la contrainte localisée) et obtenir une matrice strictement diagonale dominante. Par conséquent, nous pouvons utiliser en toute sécurité l'itération de Jacobi pour résoudre (8)

\begin{matrix} (8) & L \cdot x (t + 1) = L (x (t), y (t)) \cdot x (t) L \cdot y (t + 1) = L (x (t), y (t)) \cdot y (t) \end{matrix}

$L · x(t + 1) = L(x(t),y(t)) · x(t) \\ L · y(t + 1) = L(x(t),y(t)) · y(t) \tag 8$

.......................................

Dans ce qui précède, la notion d '"itération" est liée à la procédure de minimisation sous-jacente et ne doit pas être confondue avec l'itération de Jacobi. Ainsi, le système est résolu par Jacobi (de manière itérative), puis la solution est achetée à droite de (8), mais maintenant pour une autre itération de la minimisation sous-jacente. J'espère que cela clarifie la question.

Notez que j'ai trouvé Quels solveurs linéaires itératifs convergent pour des matrices semi-définies positives? , mais je cherche une réponse plus élaborée.

linear-algebra optimization iterative-method matrix linear-solver usero
la source

Pourriez-vous publier un lien ou une citation vers l'œuvre très citée?

Geoff Oxberry

Il peut être récupéré à partir de: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.1421 Puisque vous ne devez pas lire l'intégralité de l'ouvrage, jetez un œil à la p.7 (en bas). Je suppose que le choix des solveurs itératifs est justifié, mais je pense qu'une meilleure justification (ou, au moins, différente) est nécessaire.

usero

Je me demande si ces gars-là sont de la même communauté que les préconditionneurs combinatoires.

shuhalo

Réponses:

L'itération de Jacobi peut être prouvée convergente.

La première chose que vous devez vous assurer est que , qui est la condition d'existence de la solution (je suppose que , sinon vous avez besoin de ) parce que vous avez dit . Nous utiliserons la convention selon laquelle est également la matrice dont les colonnes en sont la base orthonormée. Dans votre cas, . $c^T \mathbf{1}_n = 0$ $L=L^T$ $c\in (\mathrm{Ker} L^T)^\perp$ $V_0:=\mathrm{Ker} L = \mathrm{span}\{\mathbf{1}_n\}$ $V_0$ $V_0:=\mathbf{1}_n/\sqrt{n}$

Ensuite, pour les erreurs de l'itération Jacobi sur le système d'origine, vous avez où est la projection orthogonale sur . De l'itération ci-dessus, nous savons que partir de laquelle nous avons la matrice d'itération dans , Non pas que ait les mêmes spectres (sauf les zéros) avec la matrice suivante Nous voulons le rayon spectral de

e_{1} = (I - D^{- 1} L) e_{0} = (I - D^{- 1} L) (P e_{0} + V_{0} a) = (I - D^{- 1} L) P e_{0} + V_{0} a,

$e_1 = (I-D^{-1}L)e_0 = (I-D^{-1}L) (P e_0 + V_0a)=(I-D^{-1}L) P e_0 + V_0a,$

P := I - V_{0} V_{0}^{'}

$P:=I-V_0V_0'$

V_{1} := V_{0}^{⊥}

$V_1:=V_0^\perp$

P e_{1} = P (I - D^{- 1} L) P e_{0},

$P e_1 = P (I-D^{-1}L) P e_0,$

S

$S$

V_{1}

$V_1$

S := P (I - D^{- 1} L) P .

$S: = P (I-D^{-1}L) P.$

S

$S$

\tilde{S} := (I - D^{- 1} L) P P = (I - D^{- 1} L) P = (I - D^{- 1} L) (I - V_{0} V_{0}^{'}) = I - D^{- 1} L - V_{0} V_{0}^{'} .

$\tilde{S}:= (I-D^{-1}L) P P=(I-D^{-1}L) P=(I-D^{-1}L)(I-V_0V_0')\\ =I-D^{-1}L-V_0V_0'.$

S

$S$ moins d'un pour prouver la convergence.

La citation suivante est ancienne et conservée uniquement pour référence. Voir après pour la nouvelle preuve.

Dans votre cas, Et vous pouvez vérifier que est strictement à dominante diagonale en utilisant l'hypothèse que les entrées de sont positives sur la diagonale et négatives sinon. Pour montrer que les valeurs propres de sont réelles, nous notons que la matrice est auto-adjointe sous le produit intérieur $V_0V_0'=\frac{1}{n}\mathbf{1}_{n\times n}.$ $D^{-1}L+V_0V_0'$ $L$ $D^{-1}L+V_0V_0'$ $<x,y>:=y^TDx.$

Si n'est pas sous votre forme spécifique, je n'ai pas trouvé de réponse à la question de convergence. Quelqu'un pourrait-il clarifier cela? $V_0$

Notez que est le vecteur eigen correspondant à la valeur propre de . Sur la base de l'observation, nous appelons le théorème 2.1 à partir des valeurs propres des matrices mises à jour de rang 1 avec quelques applications de Jiu Ding et Ai-Hui Zhou. $V_0$ $1$ $I-D^{-1}L$

Théorème 2.1 Soit et deux vecteurs de colonnes à dimensions telles que est un vecteur propre de associé à la valeur propre . Ensuite, les valeurs propres de sont comptant la multiplicité algébrique. $u$ $v$ $n$ $u$ $A$ $\lambda_1$ $A+uv^T$ $\{\lambda_1+u^Tv,\lambda_2,\ldots,\lambda_n\}$

Ensuite, nous savons que les spectres de sont les mêmes que sauf que la valeur propre dans ce dernier est décalée de dans la valeur propre zéro dans le premier. Depuis , nous avons . $\tilde{S}$ $I-D^{-1}L$ $1$ $-1$ $\rho(I-D^{-1}L)\subset (-1,1]$ $\rho(\tilde{S})\subset (-1,1)$

Hui Zhang
la source

Merci de répondre. Quelque chose de similaire était ce que j'ai considéré: à savoir, avec le Laplacien pondéré structuré comme le ci-dessus, il pourrait être montré que ses valeurs propres sont dans , donc avec le rayon spectral dans (une valeur propre est supérieure à et au moins une vaut ). Par conséquent, le rayon spectral de la matrice d'itération est inférieur à , donc avec Jacobi convergent. Peut-être que l'hypothèse ci-dessus sur le rayon spectral de (à l'exclusion de ) n'est pas sûre?

D^{- 1} L

$D^{-1}L$

[0, 2)

$[0, 2)$

(0, 2)

$(0, 2)$

0

$0$

0

$0$

I - D^{- 1} L

$I-D^{-1}L$

1

$1$

I - D^{- 1} L

$I-D^{-1}L$

0

$0$

usero

Je pense que les spectres de devraient être dans , c'est-à-dire fermés à . Je ne sais pas comment vous pouvez obtenir exclus. De mon point de vue, le (théorème du cercle de Gershgorin) [ en.wikipedia.org/wiki/Gershgorin_circle_theorem] ne peut donner qu'une estimation incluant . Si tel est le cas, l'estimation du rayon spectral de est avec l'atteinte de l' égalité avec les vecteurs dans le noyau de . Je pense que la convergence que vous voulez est que dans l'espace de complément orthogonal comme indiqué dans la «réponse» ci-dessus.

D^{- 1} L

$D^{-1}L$

[0, 2]

$[0,2]$

2

$2$

2

$2$

2

$2$

I - D^{- 1} L

$I-D^{-1}L$

\leq 1

$\leq 1$

L

$L$

V_{1}

$V_1$

Hui Zhang

Vous pouvez jeter un œil au lemme 1.7 (v) de math.ucsd.edu/~fan/research/cb/ch1.pdf La matrice pourrait être considérée comme un laplacien pondéré sur un graphe complet, d'où avec exclus . Je suppose que c'est un argument suffisant pour la preuve de convergence? ........... Votre approche nécessite-t-elle un autre pré / post-traitement des itérations au-delà du centrage . Je demande parce que vous avez introduit Et concernant les spectres de : étant donné que le rayon spectral ( ) de est , l'addition de , donnerait . N'est-ce pas un argument suffisant?

D^{- 1} L

$D^{−1}L$

2

$2$

c

$c$

V_{0}

$V_0$

I - D^{- 1} L - V_{0} V_{0}^{'}

$I-D^{-1}L-V_0V_0'$

s r

$sr$

I - D^{- 1} L

$I-D^{-1}L$

(0, 1]

$(0, 1]$

- \frac{1}{n}

$-\frac{1}{n}$

s r < 1

$sr<1$

usero

Salut, merci d'avoir pointé un bon livre. Mais j'ai trouvé que je ne pouvais pas y jeter un coup d'œil. À propos de votre dernier argument, il apparaît presque comme la "réponse" ci-dessus. Attention, vous n'ajoutez pas mais , donc ce n'est pas un simple ajout au de l' . Généralement, les de la somme de deux matrices ne sont pas la simple somme des des matrices individuelles.

\frac{1}{n}

$\frac{1}{n}$

\frac{1}{n} 1_{n \times n}

$\frac{1}{n}\mathbf{1}_{n\times n}$

s r

$sr$

I - D^{- 1} L

$I-D^{-1}L$

s r

$sr$

s r

$sr$

Hui Zhang

Heureusement que vous l'avez signalé. Votre approche nécessite-t-elle un autre pré / post-traitement des itérations au-delà du centrage c. Je pose la question parce que vous avez présenté , et je pensais que vous parliez de projeter l'espace nul. Si oui, la projection de l'espace nul est-elle vraiment nécessaire à la convergence?

V_{0}

$V_0$

usero

Les méthodes Krylov n'utilisent jamais explicitement la dimensionnalité de l'espace dans lequel elles itèrent, vous pouvez donc les exécuter sur des systèmes singuliers tant que vous gardez les itérations dans le sous-espace non nul. Cela se fait normalement en projetant l'espace nul à chaque itération. Il y a deux choses qui peuvent mal tourner, la première est beaucoup plus courante que la seconde.

Le préconditionneur est instable lorsqu'il est appliqué à l'opérateur singulier. Les solveurs directs et la factorisation incomplète peuvent avoir cette propriété. En pratique, nous choisissons simplement différents préconditionneurs, mais il existe des façons plus fondées sur des principes de concevoir des préconditionneurs pour des systèmes singuliers, par exemple Zhang (2010) .
À une certaine itération, est dans le sous-espace non nul, mais vit entièrement dans l'espace nul. Cela n'est possible qu'avec des matrices non symétriques. GMRES non modifié tombe en panne dans ce scénario, mais voir Reichel et Ye (2005) pour les variantes sans panne. $x$ $A x$

Pour résoudre des systèmes singuliers à l'aide de PETSc, voir KSPSetNullSpace(). La plupart des méthodes et préconditionneurs peuvent résoudre des systèmes singuliers. En pratique, le petit espace nul pour les PDE avec les conditions aux limites de Neumann n'est presque jamais un problème tant que vous informez le solveur Krylov de l'espace nul et choisissez un préconditionneur raisonnable.

D'après les commentaires, il semble que vous soyez spécifiquement intéressé par Jacobi. (Pourquoi? Jacobi est utile comme un lisseur multigrille, mais il existe de bien meilleures méthodes à utiliser comme solveurs.) Jacobi appliqué à ne converge pas lorsque le vecteur a une composante dans l'espace nul de , cependant, le une partie de la solution orthogonale à l'espace nul converge, donc si vous projetez l'espace nul hors de chaque itération, il converge. Alternativement, si vous choisissez un cohérent et une estimation initiale, les itérations (en arithmétique exacte) n'accumulent pas de composants dans l'espace nul. $A x = b$ $b$ $A$ $b$

Jed Brown
la source

Vous pouvez effectuer un changement de base orthogonal pour qu'il y ait un zéro sur la diagonale (trouver n'importe quelle matrice orthogonale dans laquelle la première colonne est le vecteur constant). Sous cette transformation , la matrice est toujours symétrique positive semi-définie, mais la première entrée diagonale est 0, donc l'application directe de Jacobi échouerait. Puisque est dense, vous ne le feriez pas en pratique, mais cela montre que la base est importante. Si est une base orthogonale pour l'espace nul, le GMRES projeté résout simplement .

Q

$Q$

A_{1} = Q^{T} A Q

$A_1 = Q^T A Q$

A_{1}

$A_1$

A_{1}

$A_1$

Z

$Z$

(I - Z) P^{- 1} A x = (I - Z) P^{- 1} b

$(I-Z)P^{-1} A x = (I-Z)P^{-1} b$

Jed Brown

Hmm, il semble que j'ai répondu à un commentaire qui a été supprimé. Je laisse le commentaire ici au cas où cela serait utile.

Jed Brown

Merci pour la réponse, c'est à un niveau spécialisé beaucoup plus élevé que prévu. Par conséquent, j'aurai besoin de quelques guides sur: 1) comment projeter l'espace nul à chaque itération? 2) D'après ce que je comprends, vous avez déclaré que l'application Jacobi au système tel qu'énoncé principalement pourrait ne pas converger vers la solution exacte (c'est-à-dire que les itérands n'obtiennent pas de meilleures estimations de solution). Il est donc suggéré de choisir différents préconditionneurs? Dans l'affirmative, cela implique-t-il pratiquement une vérification dynamique du comportement avec et un changement si un problème survient (avec le cas ci-dessus du système linéaire)?

d i a g (A)

$diag(A)$

usero

Mon 1) ci-dessus doit être considéré comme: étant donné l'itération Jacobi avec le système principalement posté, est-il nécessaire de projeter l'espace nul et, si oui, comment pourrait-on l'intégrer dans la mise à jour ? Post-traiter l'itération et considérer la version post-traitée pour ?

X_{k + 1} = D^{- 1} (b - (A - D) X_{k})

$X_{k+1}=D^{-1}(b-(A-D)X_k)$

X_{k + 1}

$X_{k+1}$

X_{k}

$X_{k}$

usero

Dans une base raisonnable, Jacobi devrait être stable. Il peut également utiliser 1 sur la diagonale si l'élément matriciel diagonal est 0, la projection supprime toujours l'espace nul. Envisagez-vous d'utiliser une méthode Krylov comme CG ou GMRES? Sinon, pourquoi pas? Si vous l'êtes, vous avez juste besoin d'une base orthogonale pour l'espace nul. Vous n'avez que le mode constant dans votre espace nul, donc un projecteur orthogonal dans l'espace nul est où est le vecteur de colonne. Le projecteur orthogonal qui supprime l'espace nul est donc . (Mon premier commentaire avait une erreur, si est la base, est le projecteur.)

N = Z Z^{T}

$N=ZZ^T$

Z

$Z$

I - N

$I-N$

Z

$Z$

N = I - Z Z^{T}

$N=I-ZZ^T$

Jed Brown