Lösen eines Systems mit einem kleinen Rangdiagonal-Update

Angenommen, ich habe das ursprüngliche große, spärliche lineare System: . Nun, ich habe nicht A - 1 als ein zu groß , um Faktor oder jede Art von Zersetzung ist A , aber davon ausgehen , dass ich habe die Lösung x 0 mit einem gefunden iterativen lösen.$A\textbf{x}_0=\textbf{b}_0$$A^{-1}$$A$$\textbf{x}_0$

Jetzt möchte ich eine kleine Rangaktualisierung auf die Diagonale von A anwenden (einige der diagonalen Einträge ändern): wobei D eine Diagonalmatrix ist, auf deren Diagonale meistens Nullen und einige wenige liegen Werte ungleich Null. Wenn ich A - 1 hätte, könnte ich die Woodbury-Formel nutzen, um ein Update auf die Inverse anzuwenden. Ich habe dies jedoch nicht zur Verfügung. Kann ich irgendetwas tun, ohne das gesamte System erneut aufzulösen? Gibt es vielleicht eine Möglichkeit, einen Vorkonditionierer M zu finden, der leicht zu invertieren ist, so dass M A 1$(A+D)\textbf{x}_1=\textbf{b}_0$$D$$A^{-1}$$M$ , so dass alles, was ich tun müsste, wenn ich x 0 habe , M - 1 anwendenwürde und eine iterative Methode in ein paar / wenigen Iterationen konvergieren würde?$MA_1 \approx A_0$$\textbf{x}_0$$M^{-1}$

1. Speichern Sie in den Spalten zweier Matrizen und C alle Vektoren b j, auf die Sie die Matrix in den vorherigen Iterationen angewendet haben, und die Ergebnisse c j = A b j .$B$$C$$b_j$$c_j=Ab_j$

2. Lösen Sie für jedes neue System (oder A x = b ' , was der Sonderfall D = 0 ist ) ungefähr das überbestimmte lineare System ( C + D B ) y ≈ b ' , z durch Auswahl einer Teilmenge der Zeilen (möglicherweise aller) und Verwendung einer Methode mit dichten kleinsten Quadraten. Beachten Sie, dass nur der ausgewählte Teil von C + D B zusammengebaut werden muss. Das ist also eine schnelle Operation!$(A+D)x'=b'$$Ax=b'$$D=0$$(C+DB)y\approx b'$$C+DB$

3. Setze . Dies ist eine gute anfängliche Näherung, mit der die Iteration zum Lösen von ( A + D ) x ' = b ' gestartet werden kann . Falls weitere Systeme verarbeitet werden müssen, verwenden Sie die Matrixvektorprodukte in dieser neuen Iteration, um die Matrizen B und C auf dem resultierenden Subsystem zu erweitern.$x_0=By$$(A+D)x'=b'$$B$$C$

Wenn die Matrizen und C nicht in den Hauptspeicher passen, speichern Sie B auf der Festplatte und wählen Sie die Teilmenge der Zeilen im Voraus aus. Auf diese Weise können Sie den relevanten Teil von B und C im Kern behalten, der zur Bildung des Systems der kleinsten Quadrate erforderlich ist, und das nächste x 0 kann durch einen Durchgang durch B berechnet werden, ohne dass der Kernspeicher verwendet wird.$B$$C$$B$$B$$C$$x_0$$B$

Die Zeilen sollten so ausgewählt werden, dass sie ungefähr einer groben Diskretisierung des gesamten Problems entsprechen. Es sollte ausreichen, fünfmal mehr Zeilen als die Gesamtzahl der erwarteten Matrixvektormultiplikationen zu verwenden.

Edit: Warum funktioniert das? Konstruktionsbedingt sind die Matrizen und C durch C = A B verbunden . Wenn der Unterraum durch die Spalten der aufgespannten B die exakte Lösung Vektor enthält x ' (eine seltene , aber einfache Situation) , dann x ' hat die Form x ' = B y für einige y . Einsetzen dieser in die Gleichung, die x ' definiert , ergibt die Gleichung ( C + D B ) y = b $B$$C$$C=AB$$B$$x'$$x'$$x'=By$$y$$x'$$(C+DB)y= b'$. In diesem Fall ergibt der obige Prozess als Ausgangspunkt , was die genaue Lösung ist.$x_0=By=x'$

Im Allgemeinen kann man nicht erwarten , dass im Spaltenraum von B liegt , aber der erzeugte Startpunkt ist der Punkt in diesem Spaltenraum, der x ' am nächsten liegt , in einer Metrik, die durch die ausgewählten Zeilen bestimmt wird. Daher ist es wahrscheinlich eine sinnvolle Annäherung. Wenn mehr Systeme verarbeitet werden, wächst der Spaltenraum und die Annäherung wird sich wahrscheinlich stark verbessern, so dass man hoffen kann, in immer weniger Iterationen zu konvergieren.$x'$$B$$x'$

Edit2: Über den erzeugten Unterraum: Wenn man jedes System mit einer Krylov-Methode löst, überspannen die Vektoren, die verwendet werden, um den Startpunkt für das zweite System zu erhalten, den Krylov-Unterraum der ersten rechten Seite. Somit erhält man eine gute Annäherung, wenn dieser Krylov-Unterraum einen Vektor enthält, der nahe an der Lösung Ihres zweiten Systems liegt. Im Allgemeinen überspannen die Vektoren, die verwendet werden, um den Startpunkt für das -ste System zu erhalten, einen Raum, der den Krylov-Unterraum der ersten k rechten Seiten enthält.$(k+1)$$k$