Sichere Anwendung iterativer Methoden auf diagonal dominante Matrizen

Angenommen , das folgende lineare System gegeben wobei die Laplace - gewichteten ist bekannt , positiv sein definit ein eindimensionaler Nullraum von spannte und die Übersetzungsvarianz von , dh , ändert den Funktionswert nicht (dessen Ableitung ). Die einzigen positiven Einträge von befinden sich in seiner Diagonale, was eine Summe der Absolutwerte der negativen Einträge außerhalb der Diagonale ist.

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

Ich fand in einem sehr wissenschaftlichen Arbeit zitiert in seinem Gebiet , das, obwohl ist diagonal dominant, Methoden wie konjugierten Gradienten, Gauß-Seidl, Jacobi, noch sicher zu lösen verwendet werden, um . Das Grundprinzip ist, dass man aufgrund der Translationsinvarianz sicher einen Punkt fixieren kann (z. B. die erste Zeile und Spalte von und den ersten Eintrag aus entfernen ), wodurch in eine diagonal dominante Matrix umgewandelt wird. Wie auch immer, das ursprüngliche System wird in der vollständigen Form von mit gelöst . $L$ $not~strictly$ $(1)$ $L$ $c$ $L$ $strictly$ $(1)$ $L\in\mathbb{R}^{n\times n}$

Ist diese Annahme richtig und wenn ja, welche alternativen Gründe gibt es? Ich versuche zu verstehen, wie die Konvergenz der Methoden noch gilt.

Wenn die Jacobi-Methode mit konvergent ist , was könnte man über den Spektralradius der Iterationsmatrix , wobei die Diagonalmatrix mit Einträgen von auf ihrer Diagonale ist? Ist , also anders als die allgemeinen Konvergenzgarantien für ? Ich frage dies seit den Eigenwerten der Die Laplace-Matrix mit Einsen auf der Diagonale sollte im Bereich . $(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]$

Aus der Originalarbeit:

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

Bei jeder Iteration berechnen wir ein neues Layout (x (t + 1), y (t + 1)), indem wir das folgende lineare System lösen: Ohne Verlust der Allgemeinheit können wir den Ort eines von die Sensoren (unter Verwendung des Translationsfreiheitsgrades der lokalisierten Spannung) und erhalten eine streng diagonal dominante Matrix. Daher können wir die Jacobi-Iteration sicher zum Lösen verwenden (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$

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

Oben bezieht sich der Begriff "Iteration" auf das zugrunde liegende Minimierungsverfahren und ist nicht mit der Jacobi-Iteration zu verwechseln. Das System wird also von Jacobi (iterativ) gelöst, und dann wird die Lösung auf der rechten Seite von (8) gekauft, aber jetzt für eine weitere Iteration der zugrunde liegenden Minimierung. Ich hoffe, das klärt die Sache.

Beachten Sie, dass ich festgestellt habe, welche iterativen linearen Löser für positive semidefinite Matrizen konvergieren. , suche aber eine ausführlichere Antwort.

linear-algebra optimization iterative-method matrix linear-solver usero
quelle

Könnten Sie einen Link oder ein Zitat zu der vielzitierten Arbeit posten?

Geoff Oxberry

Es kann abgerufen werden von: citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.164.1421 Da nicht erwartet wird, dass Sie das gesamte Werk lesen, werfen Sie einen Blick auf S. 7 (unten). Ich nehme an, die Wahl der iterativen Löser ist gerechtfertigt, aber ich bin der Meinung, dass eine bessere (oder zumindest andere) Begründung erforderlich ist.

Usero

Ich frage mich, ob diese Leute aus derselben Community stammen wie die kombinatorischen Vorkonditionierer.

Shuhalo

Antworten:

Die Jacobi-Iteration kann als konvergent erwiesen werden.

Das erste, was Sie sicherstellen sollten, ist, dass , was die Bedingung für das Vorhandensein einer Lösung ist (ich nehme an, , andernfalls benötigen Sie ), weil Sie gesagt haben . Wir werden die Konvention verwenden, dass auch die Matrix ist, deren Spalten eine orthonormale Basis bilden. In Ihrem Fall . $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}$

Dann haben Sie für die Fehler der Jacobi-Iteration auf dem ursprünglichen System wobei die orthogonale Projektion auf . Aus der obigen Iteration wissen wir, dass aus dem wir die Iterationsmatrix in , Nicht dass die gleichen Spektren (außer Nullen) mit der folgenden Matrix Wir wollen den Spektralradius von

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$ weniger als eins, um die Konvergenz zu beweisen.

Das folgende Zitat ist alt und dient nur als Referenz. Siehe danach für den neuen Beweis.

In Ihrem Fall ist Und Sie können überprüfen, ob streng diagonal dominant ist, indem Sie davon ausgehen, dass die Einträge von auf der Diagonale positiv und ansonsten negativ sind. Um zu zeigen, dass die Eigenwerte von real sind, stellen wir fest, dass die Matrix unter dem inneren Produkt $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.$

Wenn nicht in Ihrer spezifischen Form vorliegt, habe ich keine Antwort auf die Konvergenzfrage gefunden. Könnte jemand das klarstellen? $V_0$

Man beachte, dass der Eigenvektor ist, der dem Eigenwert von . Basierend auf der Beobachtung nennen wir Satz 2.1 aus Eigenwerten von Rang-1-aktualisierten Matrizen mit einigen Anwendungen von Jiu Ding und Ai-Hui Zhou. $V_0$ $1$ $I-D^{-1}L$

Satz 2.1 Sei und zwei dimensionale Spaltenvektoren, so dass ein Eigenvektor von , der dem Eigenwert . Dann werden die Eigenwerte von sind Zählen algebraische Multiplizität. $u$ $v$ $n$ $u$ $A$ $\lambda_1$ $A+uv^T$ $\{\lambda_1+u^Tv,\lambda_2,\ldots,\lambda_n\}$

Dann wissen wir, dass die Spektren von die gleichen sind wie außer dass der Eigenwert im letzteren um in den Eigenwert Null im ersteren verschoben wird . Da , haben wir . $\tilde{S}$ $I-D^{-1}L$ $1$ $-1$ $\rho(I-D^{-1}L)\subset (-1,1]$ $\rho(\tilde{S})\subset (-1,1)$

Hui Zhang
quelle

Danke für die Antwort. Ähnliches habe ich in Betracht gezogen: Mit dem gewichteten Laplace, der oben als strukturiert ist , konnte gezeigt werden, dass seine Eigenwerte innerhalb von , also mit dem Spektralradius innerhalb von (ein Eigenwert ist größer als und mindestens einer ist ). Daher ist der Spektralradius der Iterationsmatrix kleiner als , daher mit konvergierendem Jacobi. Vielleicht ist die obige Annahme zum Spektralradius von (ohne ) nicht sicher?

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

Ich denke, die Spektren von sollten in , das heißt bei geschlossen . Ich weiß nicht, wie man ausgeschlossen bekommen kann. Aus meiner Sicht kann der (Gershgorin-Kreissatz) [ en.wikipedia.org/wiki/Gershgorin_circle_theorem] nur die Schätzung einschließlich . Wenn es der Fall ist , die Schätzung des spektralen Radius ist ist mit der Gleichheit erreichbar mit den Vektoren in dem Kern von . Ich denke, die Konvergenz, die Sie wollen, ist die im orthogonalen Komplementraum wie in der obigen 'Antwort' angegeben.

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

Sie können sich Lemma 1.7 (v) von math.ucsd.edu/~fan/research/cb/ch1.pdf ansehen. Die Matrix kann daher in einem vollständigen Diagramm als gewichteter Laplace- Wert betrachtet werden mit ausgeschlossenen . Ich denke , es ist ein ausreichendes Argument für den Konvergenz Beweis? ........... Hat Ihr Ansatz erfordert andere Pre / Post-Verarbeitung der iteriert über Zentrierung . Ich frage, weil Sie eingeführt haben. Und in Bezug auf die Spektren von : , der Spektralradius ( ) von ist , die Addition von würde . Ist das nicht ein gutes Argument?

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

Hallo, danke, dass du auf ein gutes Buch hingewiesen hast. Aber ich habe festgestellt, dass ich keinen kurzen Blick darauf werfen kann. Über Ihr letztes Argument scheint es fast dasselbe zu sein wie die obige "Antwort". Seien Sie vorsichtig, Sie fügen nicht sondern . Dies ist also keine einfache Ergänzung zum von . Im Allgemeinen ist das der Summe zweier Matrizen keine einfache Summe der der einzelnen Matrizen.

\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

Gut, dass Sie darauf hingewiesen haben. Erfordert Ihr Ansatz eine andere Vor- / Nachbearbeitung der Iterationen über die Zentrierung hinaus? C. Ich frage, weil Sie eingeführt haben und ich dachte, Sie sprechen über das Projizieren des Nullraums. Wenn ja, ist die Projektion des Nullraums für die Konvergenz wirklich notwendig?

V_{0}

$V_0$

Usero

Krylov-Methoden verwenden niemals explizit die Dimensionalität des Raums, in dem sie iterieren. Daher können Sie sie auf singulären Systemen ausführen, solange Sie die Iterationen im Nicht-Null-Unterraum belassen. Dies erfolgt normalerweise durch Projizieren des Nullraums bei jeder Iteration. Es gibt zwei Dinge, die schief gehen können: Das erste ist viel häufiger als das zweite.

Der Vorkonditionierer ist instabil, wenn er auf den singulären Operator angewendet wird. Direkte Löser und unvollständige Faktorisierung können diese Eigenschaft haben. In der Praxis wählen wir nur verschiedene Vorkonditionierer aus, aber es gibt grundlegendere Möglichkeiten, Vorkonditionierer für singuläre Systeme zu entwerfen, z. B. Zhang (2010) .
Bei einigen Iterationen befindet sich im Nicht-Null-Unterraum, aber lebt vollständig im Nullraum. Dies ist nur mit unsymmetrischen Matrizen möglich. Unmodifiziertes GMRES bricht in diesem Szenario zusammen, aber siehe Reichel und Ye (2005) für störungsfreie Varianten. $x$ $A x$

Informationen zum Lösen einzelner Systeme mit PETSc finden Sie unter KSPSetNullSpace(). Die meisten Methoden und Vorkonditionierer können singuläre Systeme lösen. In der Praxis ist der kleine Nullraum für PDEs mit Neumann-Randbedingungen fast nie ein Problem, solange Sie den Krylov-Löser über den Nullraum informieren und einen angemessenen Vorkonditionierer auswählen.

Aus den Kommentaren geht hervor, dass Sie sich speziell für Jacobi interessieren. (Warum? Jacobi ist nützlich als Multigrid-Glätter, aber es gibt viel bessere Methoden als Löser.) Jacobi, angewendet auf , konvergiert nicht, wenn der Vektor eine Komponente im Nullraum von hat Ein Teil der Lösung, der orthogonal zum Nullraum ist, konvergiert. Wenn Sie also den Nullraum aus jeder Iteration projizieren, konvergiert er. Wenn Sie alternativ ein konsistentes und eine anfängliche Schätzung wählen , akkumulieren die Iterationen (in exakter Arithmetik) keine Komponenten im Nullraum. $A x = b$ $b$ $A$ $b$

Jed Brown
quelle

Sie können eine orthogonale Änderung der Basis durchführen, sodass die Diagonale eine Null enthält (suchen Sie eine orthogonale Matrix in der die erste Spalte der konstante Vektor ist). Unter dieser Transformation ist die Matrix immer noch symmetrisch positiv semidefinit, aber der erste diagonale Eintrag ist 0, so dass die direkte Anwendung von Jacobi fehlschlagen würde. Da dicht ist, würden Sie dies in der Praxis nicht tun, aber dies zeigt, dass die Basis wichtig ist. Wenn eine orthogonale Basis für den Nullraum ist, löst projiziertes GMRES nur .

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, anscheinend habe ich auf einen Kommentar geantwortet, der gelöscht wurde. Ich werde den Kommentar hier hinterlassen, falls es nützlich ist.

Jed Brown

Vielen Dank für die Antwort, es ist auf einem viel höheren spezialisierten Niveau als ich erwartet hatte. Daher benötige ich einige Anleitungen zu: 1) Wie wird der Nullraum bei jeder Iteration projiziert? 2) Nach meinem Verständnis haben Sie angegeben, dass die in erster Linie angegebene Jacobi-Anwendung auf das System möglicherweise nicht zur exakten Lösung konvergiert (dh die Iteranden erhalten keine besseren Lösungsschätzungen). Es wird daher empfohlen, verschiedene Vorkonditionierer zu wählen. Wenn ja, bedeutet dies praktisch eine dynamische Überprüfung des Verhaltens mit und eine Änderung, wenn ein Problem auftritt (im obigen Fall des linearen Systems)?

d i a g (A)

$diag(A)$

Usero

Meine 1) von oben sollte betrachtet werden als: Angesichts der Jacobi-Iteration mit dem hauptsächlich veröffentlichten System ist es erforderlich , den Nullraum zu projizieren, und wenn ja, wie könnte man ihn in das Update ? Nachbearbeitung der iterierten und Berücksichtigung der nachbearbeiteten Version für ?

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

In einer vernünftigen Basis sollte Jacobi stabil sein. Es kann auch 1 für die Diagonale verwendet werden, wenn das diagonale Matrixelement 0 ist. Die Projektion entfernt immer noch den Nullraum. Planen Sie eine Krylov-Methode wie CG oder GMRES? Wenn nicht, warum nicht? Wenn ja, benötigen Sie nur eine orthogonale Basis für den Nullraum. Sie haben nur den konstanten Modus in Ihrem Nullraum, daher ist ein orthogonaler Projektor in den Nullraum wobei der Spaltenvektor ist. Der orthogonale Projektor, der den Nullraum entfernt, ist somit . (Mein erster Kommentar hatte einen Fehler, wenn die Basis ist, ist der Projektor.)

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