Rozwiązanie systemu z aktualizacją po przekątnej małego stopnia

Załóżmy, że mam oryginalny duży, rzadki układ liniowy: . Teraz nie mam ponieważ A jest zbyt duże, aby uwzględnić czynnik lub jakikolwiek rozkład , ale zakładam, że mam rozwiązanie z rozwiązaniem iteracyjnym.$A\textbf{x}_0=\textbf{b}_0$$A^{-1}$$A$$\textbf{x}_0$

Teraz chcę zastosować małą aktualizację rangi do przekątnej A (zmień kilka wpisów po przekątnej): gdzie jest macierzą diagonalną z głównie 0 na przekątnej i kilka niezerowych wartości. Gdybym miał , byłbym w stanie skorzystać z formuły Woodbury i zastosować aktualizację odwrotności. Jednak nie mam tego dostępnego. Czy jest coś, co mogę zrobić oprócz rozwiązania całego systemu od nowa? Czy jest jakiś sposób, że mógłbym wymyślić warunek wstępny który jest łatwy \ łatwiejszy do odwrócenia, taki jak , tak że wszystko, co musiałbym zrobić, jeśli mam to zastosować$(A+D)\textbf{x}_1=\textbf{b}_0$$D$$A^{-1}$$M$$MA_1 \approx A_0$$\textbf{x}_0$$M^{-1}$ a metoda iteracyjna byłaby zbieżna w kilku / kilku iteracjach?

1. Zapisz w kolumnach dwóch macierzy $B$ i $C$ wszystkie wektory $b_j$ do której zastosowałeś macierz w poprzednich iteracjach i wynikach $c_j=Ab_j$.

2. Dla każdego nowego systemu $(A+D)x'=b'$ (lub $Ax=b'$, co jest przypadkiem szczególnym $D=0$), w przybliżeniu rozwiązuje nadmiernie określony układ liniowy $(C+DB)y\approx b'$, np. wybierając podzbiór wierszy (ewentualnie wszystkie) i stosując metodę gęstego najmniejszego kwadratu. Zauważ, że tylko wybrana część$C+DB$musi zostać złożony; więc jest to szybka operacja!

3. Położyć $x_0=By$. Jest to dobre wstępne przybliżenie, od którego można rozpocząć iterację rozwiązywania$(A+D)x'=b'$. W przypadku konieczności przetworzenia dalszych systemów, użyj produktów wektora macierzy w tej nowej iteracji, aby rozszerzyć macierze$B$ i $C$ w powstałym podsystemie.

Jeśli macierze $B$ i $C$ nie pasują do głównej pamięci, przechowuj $B$na dysku i wcześniej wybierz podzbiór wierszy. Pozwala to zachować w centrum odpowiednią część$B$ i $C$ potrzebne do utworzenia systemu najmniejszych kwadratów i następnego $x_0$ można obliczyć za pomocą jednego przejścia $B$ przy niewielkim wykorzystaniu pamięci podstawowej.

Wiersze powinny być wybrane w taki sposób, aby w przybliżeniu odpowiadały zgrubnej dyskretyzacji pełnego problemu. Wystarczy pięć razy więcej wierszy niż całkowita liczba oczekiwanych mnożników wektorów macierzy.

Edycja: Dlaczego to działa? Z założenia macierze$B$ i $C$ są powiązane przez $C=AB$. Jeśli podprzestrzeń obejmuje wszystkie kolumny$B$ zawiera dokładny wektor rozwiązania $x'$ (rzadka, ale prosta sytuacja) $x'$ ma formę $x'=By$ dla niektórych $y$. Podstawiając to do definicji równania$x'$ daje równanie $(C+DB)y= b'$. Tak więc w tym przypadku powyższy proces stanowi punkt wyjścia$x_0=By=x'$, które jest dokładnym rozwiązaniem.

Zasadniczo nie można się spodziewać $x'$ leżeć w przestrzeni kolumny $B$, ale generowany punkt początkowy będzie punktem w tej najbliższej przestrzeni cloumn $x'$, w metodzie określonej przez wybrane wiersze. Dlatego prawdopodobnie będzie to rozsądne przybliżenie. W miarę przetwarzania większej liczby systemów przestrzeń kolumn rośnie, a przybliżenie prawdopodobnie ulegnie znacznej poprawie, dzięki czemu można mieć nadzieję, że zbierze się coraz mniej iteracji.

Edycja2: Informacje o wygenerowanej podprzestrzeni: Jeśli każdy układ rozwiązuje się metodą Kryłowa, wektory użyte do uzyskania punktu początkowego dla drugiego układu obejmują podprzestrzeń Kryłowa pierwszej prawej strony. W ten sposób można uzyskać dobre przybliżenie, ilekroć ta podprzestrzeń Kryłowa zawiera wektor zbliżony do rozwiązania drugiego układu. Zasadniczo wektory użyte do uzyskania punktu wyjścia dla$(k+1)$System obejmuje obszar zawierający podprzestrzeń Kryłowa pierwszego $k$ prawe boki.