Projection de l'espace nul de partir de dans

Étant donné le système où , j'ai lu que, dans le cas où l'itération Jacobi est utilisée comme solveur, la méthode ne convergera pas si a un non-zéro composant dans l'espace nul de . Alors, comment pourrait-on déclarer formellement que, à condition que ait une composante non nulle couvrant l'espace nul de , la méthode Jacobi est non convergente? Je me demande comment cela pourrait être formalisé mathématiquement, car une partie de la solution orthogonale à l'espace nul converge.

A x = b,

$Ax=b,$

A \in R^{n \times n}

$A\in\mathbb{R}^{n\times n}$

b

$b$

A

$A$

b

$b$

A

$A$

Par conséquent, en projetant l'espace nul de hors de chaque itération, il converge (ou?). $A$

.........

Je suis particulièrement intéressé par le cas de où est une matrice laplacienne symétrique avec l'espace nul étendu par un vecteur , et a une composante nulle dans l'espace nul de , où est la matrice de centrage. Cela implique-t-il que chaque itération de Jacobi verra l'espace nul de projeté, c'est-à-dire que chaque itération sera centrée ? Je pose la question car il n'y aurait alors pas besoin de projeter l'espace nul de partir des itérations de Jacobi (ou, en d'autres termes, de centrer

L x = b,

$Lx=b,$

L

$L$

1_{n} = [1 \dots 1]^{T} \in R^{n}

$1_n=[1\dots 1]^T\in\mathbb{R}^n$

b

$b$

L

$L$

J b = b,

$Jb=b,$

J = I - \frac{1}{n} 1_{n} 1_{n}^{T}

$J=I-\frac{1}{n}1_n1_n^T$

L

$L$

L

$L$ les itérations).

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

Cette question peut également être pertinente pour vous: scicomp.stackexchange.com/questions/1505/…

shuhalo

Merci. J'ai en fait fait un extrait de mes commentaires là-bas, car la question mérite à elle seule l'attention. Cependant, ce qui précède n'a pas été abordé (pas du moins formalisé).

usero

Oh, honte à moi, je n'ai pas vérifié que c'était ta propre question.

shuhalo

@JedBrown Votre réponse sur scicomp.stackexchange.com/questions/1505/… a inspiré cette question. Je pense que cela mérite une considération indépendante. Je suppose que vous pourrez considérer les questions ci-dessus.

usero

Réponses:

La condition correcte pour solvability n'a rien à voir avec l'espace nul de (sauf est symétrique) mais avec l'espace nul de . Si alors implique que , donc doit être orthogonal à tout vecteur nul de (sinon il n'y a pas de solution et l'itération Jacobi n'a aucune raison de converger). $A$ $A$ $A^T$ $A^Tu=0$ $Ax=b$ $u^Tb=u^TAx=0$ $b$ $A^T$

Mais si tel est le cas, une solution existe et dans le cas carré, il y en a infiniment.

Dans le cas singulier, comme on ne sait jamais si cette condition est remplie (et elle serait de toute façon gâchée par l'arrondi), on résoudrait généralement le problème en tant que problème des moindres carrés. Pour trouver la solution de norme minimale, utilisez des gradients conjugués sur les équations normales; cela exige que vous la multiplication de code par et par . (Étant donné uniquement une routine de multiplication avec , on pourrait utiliser GMRES à la place, avec des propriétés de convergence moins prévisibles.) $A$ $A^T$ $A$

Arnold Neumaier
la source

Merci beaucoup. Notez que je m'intéresse spécifiquement à la méthode de Jacobi (raisons théoriques; sinon, j'accepte votre suggestion sur les alternatives.) Donc: "Je suis particulièrement intéressé par le cas où a une composante nulle dans l'espace nul de Est-ce que cela implique que chaque itération de Jacobi aura l'espace nul de projeté? Je demande cela car il n'y aurait alors pas besoin de projeter l'espace nul de partir de Jacobi itère (donc, quand b a le null- l'espace de projeté). "

b

$b$

A

$A$

A

$A$

A

$A$

A

$A$

usero

A

$A$

A^{T}

$A^T$

A

$A$

A

$A$

b

$b$

A

$A$

A = I - B

$A=I-B$

x_{0} = b

$x_0=b$

x_{n + 1} = b + B x_{n}

$x_{n+1}=b+Bx_n$

A u = 0

$Au=0$

u^{T} b = 0

$u^Tb=0$

u^{T} B = u^{T}

$u^TB=u^T$

u^{T} x_{n}

$u^Tx_n$ est constant par induction, donc nul. - Mais pourquoi vous souciez-vous de la méthode Jacobi? C'est très lent!

Arnold Neumaier

B

$B$

A

$A$

d i a g (A) \neq c \cdot I

$diag(A)\neq c\cdot I$

c \in R

$c\in \mathbb{R}$