Czy rozwiązanie liniowego układu równań można aproksymować tylko dla kilku pierwszych zmiennych?

Mam liniowy układ równań wielkości mxm, gdzie m jest duży. Jednak zmienne, które mnie interesują, to tylko pierwsze n zmiennych (n jest małe w porównaniu do m). Czy istnieje sposób, aby zbliżyć rozwiązanie dla pierwszych m wartości bez konieczności rozwiązywania całego systemu? Jeśli tak, czy zbliżenie to byłoby szybsze niż rozwiązanie pełnego układu liniowego?

Jak zauważyli inni, jest to trudne w przypadku bezpośredniego solvera. To powiedziawszy, nie jest tak trudno zrobić z iteracyjnymi rozwiązaniami. W tym celu należy zauważyć, że większość iteracyjnych solverów w taki czy inny sposób minimalizuje błąd w odniesieniu do niektórych norm. Często norma ta jest albo indukowana przez samą matrycę, ale czasami jest to również norma wektora l2. Ale nie musi tak być: możesz wybrać normę, w której chcesz zminimalizować błąd (lub resztkowy), i możesz na przykład wybrać normę, w której ważisz komponenty, na których Ci zależy, za pomocą 1 i wszystkie inne z 1e-12, tj. na przykład coś takiego (1e-24) ∑ N i = 6 x 2 i i odpowiedni iloczyn skalarny. Następnie napisz wszystkie kroki iteracyjnego solvera w odniesieniu do tej normy i iloczynu skalarnego, a otrzymasz iteracyjny solver, który zwraca znacznie większą uwagę na elementy wektorowe, na których ci zależy, niż na inne.$|| x ||^2 = \sum_{i=1}^5 x_i^2 +$$\sum_{i=6}^N x_i^2$

Pytanie oczywiście brzmi, czy potrzebujesz mniej iteracji niż w przypadku produktu norm / skalar, który waży wszystkie składniki jednakowo. Ale tak powinno być: powiedzmy, że zależy ci tylko na pięciu pierwszych elementach wektorowych. Następnie powinieneś potrzebować maksymalnie pięciu iteracji, aby zmniejszyć błąd o współczynnik 1e12, ponieważ pięć iteracji jest potrzebne dla opisującego je systemu 5x5. To nie jest dowód, ale jestem całkiem pewien, że rzeczywiście powinieneś uciec o znacznie mniejszej liczbie iteracji, jeśli waga w normie (1e-12 powyżej) jest mniejsza niż tolerancja, z którą chcesz iteracyjnie rozwiązać układ liniowy .

Formowanie uzupełnienia Schur

Załóżmy, że permutowałeś i podzieliłeś swoją macierz na formę

tak, że zawiera stopnie swobody zainteresowania i jest znacznie mniejszy niż A 11 , wówczas można utworzyć dopełnienie Schur$A_{22}$$A_{11}$

albo poprzez częściową prawostronną LU faktoryzację, albo wyraźną formułę, a następnie można zrozumieć w następującym znaczeniu:$S_{22}$

gdzie oznacza „nieciekawą” część rozwiązania. Tak więc, pod warunkiem, że prawa strona, która jest tylko niezerowa w stopniach swobody uzupełnienia Schur S 22 , musimy rozwiązać tylko S 22 , aby uzyskać część rozwiązania odpowiadającą tym stopniom swobody.$\star$$S_{22}$$S_{22}$

Złożoność obliczeniowa w nieustrukturyzowanym gęstym przypadku

Ustawienie do wysokości A i n do wysokości A 22 , standardowe metody obliczeniowej S 22 jest Czynnikiem l 11 U 11 : = 11 (zignorujmy odchylany do tej pory) w przybliżeniu 2 / 3 ( N - n ) 3 prace, a następnie do formy$N$$A$$n$$A_{22}$$S_{22}$$L_{11} U_{11} := A_{11}$$2/3 (N-n)^3$

używając dwóch trójkątów wymagających pracy , a następnie wykonując aktualizację do A 22 w pracy 2 n 2 ( N - n ) .$n(N-n)^2$$A_{22}$$2n^2 (N-n)$

Zatem całkowity pracy jest w przybliżeniu . Gdy n jest bardzo mała, N - n ≈ N , więc koszty te mogą być widoczne w przybliżeniu 2 / 3 N 3 , który jest koszt pełnego faktoryzacji.$2/3 (N-n)^3 + 2n(N-n)^2 + 2n^2 (N-n)$$n$$N-n \approx N$$2/3 N^3$

Korzyścią jest to, że jeśli istnieje bardzo duża liczba prawostronnych stron do rozwiązania za pomocą tego samego układu równań, wówczas może potencjalnie zostać ponownie użyty wiele razy, przy czym każde rozwiązanie wymagałoby tylko 2 n 2 pracy (zamiast pracy 2 N 2 ), jeśli S 22 jest uwzględniony.$S_{22}$$2n^2$$2N^2$$S_{22}$

Złożoność obliczeniowa w (typowym) rzadkim przypadku

Jeśli twój rzadki system powstał z jakiegoś rodzaju przybliżenia skończonej różnicy lub przybliżenia elementu skończonego, wówczas solwery rzadkie bezpośrednie prawie na pewno będą w stanie wykorzystać część struktury; Systemy 2d można rozwiązać pracy i O ( N log N ) podczas przechowywania, natomiast systemy 3D może być rozwiązany O ( N 2 ) pracy i O ( N 4 / 3 ) pamięci. Systemy oparte na faktorach można następnie rozwiązać przy takim samym nakładzie pracy, jak wymagania dotyczące pamięci.$O(N^{3/2})$$O(N \log N)$$O(N^2)$$O(N^{4/3})$

Przywołanie złożoności obliczeniowej polega na tym, że jeśli i masz układ 2d, a ponieważ uzupełnienie Schur będzie prawdopodobnie gęste, złożoność rozwiązania przy uwzględnieniu faktoryzowanego uzupełnienia Schur będzie wynosićO(n2)=O(N), w którym brakuje tylko współczynnika logarytmicznego w porównaniu do rozwiązania pełnego system! 3D, wymagaO(N)pracy zamiastO(N 4 / 3 ).$n \approx \sqrt{N}$$O(n^2) = O(N)$$O(N)$$O(N^{4/3})$

Dlatego ważne jest, aby pamiętać, że w twoim przypadku, gdzie , znaczne oszczędności przyniesie tylko praca w kilku wymiarach i rozwiązanie wielu problemów po prawej stronie.$n=\sqrt{N}$

Metoda redukcji modelu

$\mathbf{P}$$\mathbf{P}$$\mathcal{R}(\mathbf{P})$$\mathbf{Ax} = \mathbf{b}$$k$$k$

$\mathbf{P}$

Macierze zasłonięte przez gwiazdy mają znaczenie dla innych rzeczy (takich jak błąd szacowania itp.), Ale na razie unikniemy zajmowania się obcymi szczegółami. Wynika, że

$\mathbf{P}$

Zasadniczo rozwiążesz system

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

$\widehat{\mathbf{x}}$$\mathbf{V}$$\mathbf{y}$$\mathbf{x}$

Dlaczego podejście uzupełniające Schur jest prawdopodobnie lepsze

$\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}$$\mathbf{P}$$\mathbf{A}$$\mathbf{P}$$k$$\mathbf{A}$$k$$\mathbf{A}$$\mathbf{A}$$_{2}$

$\mathbf{V}$$\mathbf{W}$$\mathbf{P}$ nadal jest „dobrą” matrycą projekcyjną dla wszystkich tych systemów, te dodatkowe koszty prawdopodobnie spowodują, że rozwiązanie zredukowanego systemu będzie droższe niż rozwiązanie oryginalnego systemu.

Wady są bardzo podobne do podejścia JackPoulsona, z tym wyjątkiem, że nie do końca wykorzystujesz wspomnianą strukturę.

Długa odpowiedź jest ... w pewnym sensie.

Możesz zmienić układ równań tak, aby był jak najdalszy $k$ kolumny to zmienne, dla których chcesz rozwiązać.

Krok 1: Wykonaj eliminację Gaussa, aby matryca była górna trójkątna. Krok 2: rozwiązuj przez podstawienie wsteczne tylko dla pierwszego (ostatniego)$k$ zmienne, którymi jesteś zainteresowany

Pozwoli ci to zaoszczędzić obliczeniową złożoność rozwiązywania ostatnich problemów $n-k$ zmienne poprzez podstawienie wsteczne, które może być tego warte, jeśli $n$jest tak duży, jak mówisz. Należy pamiętać, że w kroku 1 nadal trzeba będzie wykonać sporo pracy.

Pamiętaj również, że ograniczenie kolejności, w której zamierzasz wykonać podstawienie wsteczne, może ograniczyć formę matrycy (zabiera to możliwość wymiany kolumn), co może prowadzić do źle uwarunkowanego systemu, ale ja nie jestem pewny tego - tylko o czym należy pamiętać.