Kann die Lösung eines linearen Gleichungssystems nur für die ersten Variablen approximiert werden?

Ich habe ein lineares Gleichungssystem der Größe mxm, wobei m groß ist. Die Variablen, die mich interessieren, sind jedoch nur die ersten n Variablen (n ist klein im Vergleich zu m). Gibt es eine Möglichkeit, die Lösung für die ersten m-Werte zu approximieren, ohne das gesamte System lösen zu müssen? Wenn ja, wäre diese Approximation schneller als die Lösung des vollständigen linearen Systems?

Wie bereits erwähnt, ist dies mit einem direkten Löser nur schwer möglich. Das heißt, es ist nicht so schwer mit iterativen Lösern zu tun. Beachten Sie zu diesem Zweck, dass die meisten iterativen Löser auf die eine oder andere Weise den Fehler in Bezug auf eine Norm minimieren. Oft wird diese Norm entweder durch die Matrix selbst induziert, manchmal ist es aber auch nur die l2-Vektornorm. Dies muss jedoch nicht der Fall sein: Sie können auswählen, in welcher Norm Sie den Fehler (oder den Rest) minimieren möchten, und Sie können beispielsweise eine Norm auswählen, in der Sie die Komponenten, die Sie interessieren, mit 1 und 2 abwägen alle anderen mit 1e-12, also zum Beispiel so etwas wie (1e-24) Σ N i = 6 x 2 i und entsprechende Skalarprodukt. Schreiben Sie dann alle Schritte des iterativen Lösers in Bezug auf diese Norm und dieses Skalarprodukt, und Sie erhalten einen iterativen Löser, der den Vektorelementen, die Sie interessieren, erheblich mehr Aufmerksamkeit schenkt als den anderen.$|| x ||^2 = \sum_{i=1}^5 x_i^2 +$$\sum_{i=6}^N x_i^2$

Die Frage ist natürlich, ob Sie weniger Iterationen benötigen als mit dem Norm- / Skalarprodukt, bei dem alle Komponenten gleich schwer sind. Aber das sollte tatsächlich der Fall sein: Nehmen wir an, Sie interessieren sich nur für die fünf ersten Vektorelemente. Dann sollten Sie höchstens fünf Iterationen benötigen, um den Fehler um den Faktor 1e12 zu reduzieren, da für das 5x5-System, das sie beschreibt, fünf Iterationen erforderlich sind. Das ist kein Beweis, aber ich bin mir ziemlich sicher, dass Sie in der Tat mit einer viel geringeren Anzahl von Iterationen davonkommen sollten, wenn das Gewicht in der Norm (1e-12 oben) kleiner ist als die Toleranz, mit der Sie das lineare System iterativ lösen möchten .

Bildung der Schur-Ergänzung

Angenommen, Sie haben Ihre Matrix permutiert und in das Formular partitioniert

Damit Ihre Interessenfreiheitsgrade enthält und viel kleiner als A 11 ist , kann man das Schur-Komplement bilden$A_{22}$$A_{11}$

entweder durch eine teilweise rechts aussehende LU-Faktorisierung oder durch die explizite Formel, und dann kann im folgenden Sinne verstanden werden:$S_{22}$

Dabei steht für den "uninteressanten" Teil der Lösung. Wenn also eine rechte Seite vorgesehen ist, die in den Freiheitsgraden des Schur-Komplements S 22 nur ungleich Null ist , müssen wir nur gegen S 22 lösen , um den Teil der Lösung zu erhalten, der diesen Freiheitsgraden entspricht.$\star$$S_{22}$$S_{22}$

Rechenkomplexität in unstrukturierten dichten Fällen

Einstellen auf die Höhe der A und n die Höhe der A 22 , dann wird die Standard - Methode zur Berechnung von S 22 zu ersten Faktor ist L 11 U 11 : = A 11 (mal ignore jetzt Schwenk) etwa in 2 / 3 ( N - n ) 3 arbeiten, dann formen$N$$A$$n$$A_{22}$$S_{22}$$L_{11} U_{11} := A_{11}$$2/3 (N-n)^3$

Verwenden von zwei Dreieckslösungen, die jeweils Arbeit erfordern , und Ausführen der Aktualisierung auf A 22 in 2 n 2 ( N - n ) Arbeit.$n(N-n)^2$$A_{22}$$2n^2 (N-n)$

Somit ist die Gesamtarbeit etwa . Wenn n sehr klein ist , N - n ≈ N , so können die Kosten in etwa sein gesehen werden 2 / 3 N 3 , die die Kosten eines vollständigen Faktorisierung ist.$2/3 (N-n)^3 + 2n(N-n)^2 + 2n^2 (N-n)$$n$$N-n \approx N$$2/3 N^3$

Der Vorteil ist, dass, wenn eine sehr große Anzahl von rechten Seiten mit dem gleichen Gleichungssystem gelöst werden muss, möglicherweise eine große Anzahl von Malen wiederverwendet werden könnte, wobei jede Lösung nur 2 n 2 Arbeit erfordern würde (anstatt 2 N 2 zu arbeiten), wenn S 22 berücksichtigt wird.$S_{22}$$2n^2$$2N^2$$S_{22}$

Rechenaufwand im (typischen) spärlichen Fall

Wenn Ihr Sparse-System aus einer Art Finite-Differenzen- oder Finite-Elemente-Approximation hervorgegangen ist, können Sparse-Direct-Solver mit ziemlicher Sicherheit einen Teil der Struktur ausnutzen. 2D - Systeme können gelöst werden mit Arbeit und O ( N log N ) Speicherung, während 3D - Systeme mit lösenden kann O ( N 2 ) Arbeit und O ( N 4 / 3 ) Lagerung. Die faktorisierten Systeme können dann mit dem gleichen Arbeitsaufwand wie die Speicheranforderungen gelöst werden.$O(N^{3/2})$$O(N \log N)$$O(N^2)$$O(N^{4/3})$

Der Punkt, an dem die Komplexität der Berechnungen angesprochen wird, ist der, wenn und Sie haben ein 2d-System. Da das Schur-Komplement wahrscheinlich dicht ist, ist die Komplexität der Lösung angesichts des faktorisierten Schur-KomplementsO(n2)=O(N), wobei nur ein logarithmischer Faktor fehlt,während dasGanze gelöst wird System! In 3d, es erfordertO(N)Arbeits anstelle vonO(N 4 / 3 ).$n \approx \sqrt{N}$$O(n^2) = O(N)$$O(N)$$O(N^{4/3})$

Es ist daher wichtig zu berücksichtigen, dass in Ihrem Fall , es gibt nur signifikante Einsparungen, wenn Sie in mehreren Dimensionen arbeiten und viele rechte Seiten zu lösen haben.$n=\sqrt{N}$

Der Modellreduktionsansatz

Da Paul gefragt hat, werde ich darüber sprechen, was passiert, wenn Sie projektionsbasierte Modellreduktionsmethoden für dieses Problem verwenden. Angenommen, Sie könnten einen Projektor , bei dem der mit R ( P ) bezeichnete Bereich von P die Lösung für Ihr lineares System A x = b enthält und die Dimension k hat , wobei k die Anzahl der Unbekannten ist, für die Sie sich entscheiden in einem linearen System lösen wollen.$\mathbf{P}$$\mathbf{P}$$\mathcal{R}(\mathbf{P})$$\mathbf{Ax} = \mathbf{b}$$k$$k$

Eine Singulärwertzerlegung von ergibt die folgende partitionierte Matrix:$\mathbf{P}$

Die von Sternen verdeckten Matrizen sind für andere Dinge von Bedeutung (wie das Abschätzen von Fehlern usw.), aber im Moment vermeiden wir den Umgang mit überflüssigen Details. Es folgt dem

ist eine volle Rang Zersetzung von .$\mathbf{P}$

Im Wesentlichen lösen Sie das System

in einer klugen Weise, weil und W hat auch die Eigenschaft , dass W T V = I . Multipliziert man beide Seiten von P A x = P b durch W T und lassen y = V x eine Näherung für sein x Ausbeuten$\mathbf{V}$$\mathbf{W}$$\mathbf{W}^{T}\mathbf{V} = \mathbf{I}$$\mathbf{PAx} = \mathbf{Pb}$$\mathbf{W}^{T}$$\mathbf{y} = \mathbf{V}\widehat{\mathbf{x}}$$\mathbf{x}$

Lösen Sie für x , premultiply es durch V , und Sie haben y , Ihre Näherung für x .$\widehat{\mathbf{x}}$$\mathbf{V}$$\mathbf{y}$$\mathbf{x}$

Warum der Schur-Komplement-Ansatz wahrscheinlich besser ist

Für den Anfang muss man sich irgendwie für . Wenn die Lösung von A x = b in R ( P ) ist , dann ist y = x und y ist keine Näherung. Andernfalls ist y ≠ x und Sie führen einen Approximationsfehler ein. Dieser Ansatz nutzt die von Ihnen erwähnte Struktur, die Sie ausnutzen möchten, nicht wirklich aus. Wenn wir P so auswählen , dass sein Bereich die Standardeinheitsbasis in den Koordinaten von x ist, die Sie berechnen möchten, weisen die entsprechenden Koordinaten von y Fehler auf. Es ist nicht klar, wie Sie auswählen möchten$\mathbf{P}$$\mathbf{Ax} = \mathbf{b}$$\mathcal{R}(\mathbf{P})$$\mathbf{y} = \mathbf{x}$$\mathbf{y}$$\mathbf{y} \neq \mathbf{x}$$\mathbf{P}$$\mathbf{x}$$\mathbf{y}$ . Sie könntenzum Beispieleine SVD von A verwenden und P als Produkt der ersten k linken Singularvektoren von A und des Adjunkts der ersten k rechten Singularvektoren von A auswählen, vorausgesetzt, die Singularvektoren sind in absteigender Reihenfolge von angeordnet singulärer Wert. Diese Wahl des Projektors würde einer ordnungsgemäßen orthogonalen Zerlegung von A entsprechen und den L 2 -Fehler in der Näherungslösungminimieren.$\mathbf{P}$$\mathbf{A}$$\mathbf{P}$$k$$\mathbf{A}$$k$$\mathbf{A}$$\mathbf{A}$$_{2}$

Zusätzlich zur Einführung von Approximationsfehlern werden bei diesem Ansatz zusätzlich zu der linearen Lösung des kleineren Systems und der für die Berechnung von und W erforderlichen Arbeit drei zusätzliche Matrixmultiplikationen eingeführt . Solange Sie nicht häufig dasselbe lineare System lösen und nur die rechte Seite ändern und P immer noch eine "gute" Projektionsmatrix für all diese Systeme ist, wird die Lösung des reduzierten Systems aufgrund dieser zusätzlichen Kosten wahrscheinlich teurer als die Lösung Ihres Systems sein ursprüngliches System.$\mathbf{V}$$\mathbf{W}$$\mathbf{P}$

Die Nachteile sind denen von JackPoulson sehr ähnlich, außer dass Sie die von Ihnen erwähnte Struktur nicht wirklich nutzen.

Die lange Antwort lautet ... irgendwie.

Sie können Ihr Gleichungssystem so neu anordnen, dass die am weitesten rechts stehenden Spalten die Variablen sind, für die Sie eine Lösung finden möchten.$k$

Schritt 1: Führen Sie die Gaußsche Elimination so durch, dass die Matrix im oberen Dreieck liegt. Schritt 2: Lösen Sie durch Rückersetzung nur die ersten (letzten) Variablen auf, an denen Sie interessiert sind$k$

Dies erspart Ihnen den Rechenaufwand für die Lösung der letzten Variablen durch Back-Substitution. Dies könnte sich lohnen, wenn n so groß ist, wie Sie sagen. Denken Sie daran, dass für Schritt 1 noch einiges an Arbeit erledigt werden muss.$n-k$$n$

Denken Sie auch daran, dass die Einschränkung der Reihenfolge, in der Sie die Rücksubstitution durchführen, die Form der Matrix einschränken kann (dies nimmt die Fähigkeit zum Austausch von Spalten in Mitleidenschaft), was möglicherweise zu einem schlecht konditionierten System führen kann, ich jedoch nicht da ist man sich sicher - nur etwas, an das man denken muss.