Załóżmy, że podano następujący układ liniowy
Znalazłem to w jednym z bardzo cytowanych prac naukowych w tej dziedzinie jest dominujące po przekątnej metody takie jak Conjugate Gradient, Gauss-Seidl, Jacobi, nadal mogą być bezpiecznie stosowane do rozwiązywania . Uzasadnieniem jest to, że ze względu na niezmienność tłumaczenia można bezpiecznie naprawić jeden punkt (np. Usunąć pierwszy wiersz i kolumnę i pierwszy wpis z ), w ten sposób przekształcając do macierz diagonalnie dominująca. W każdym razie oryginalny system został rozwiązany w pełnej formie, z .
Czy to założenie jest prawidłowe, a jeśli tak, jakie są alternatywne uzasadnienie? Próbuję zrozumieć, jak nadal zachowuje się zbieżność metod.
Jeśli metoda Jacobi jest zbieżna , co można powiedzieć o promieniu spektralnym macierzy iteracji , gdzie to macierz diagonalna z wpisami na przekątnej? Jest, a zatem różni się od ogólnych gwarancji konwergencji dla ? Pytam o to, ponieważ wartości własne macierzy Laplacianaz tymi na przekątnej powinny być w zasięgu.
Z oryginalnej pracy:
......................................
Przy każdej iteracji obliczamy nowy układ (x (t +1), y (t + 1)), rozwiązując następujący układ liniowy:
.......................................
W powyższym pojęciu „iteracja” jest związana z podstawową procedurą minimalizacji i nie należy jej mylić z iteracją Jacobiego. Tak więc system jest rozwiązywany przez Jacobiego (iteracyjnie), a następnie rozwiązanie jest kupowane po prawej stronie (8), ale teraz w celu kolejnej iteracji podstawowej minimalizacji. Mam nadzieję, że to wyjaśnia sprawę.
Zauważ, że znalazłem Które iteracyjne solwery liniowe są zbieżne dla dodatnich macierzy półprzewodnikowych? , ale szukam bardziej szczegółowej odpowiedzi.
Odpowiedzi:
Iterację Jacobi można wykazać zbieżnością.
Pierwszą rzeczą, którą powinieneś się upewnić, jest tocT1n=0 , który jest warunkiem istnienia rozwiązania (zakładam L=LT , w przeciwnym razie potrzebujesz c∈(KerLT)⊥ ), ponieważ powiedziałeś V0:=KerL=span{1n} . Wykorzystamy konwencję, któraV0 jest również macierzą z kolumnami będącymi jej podstawą ortonormalną. W Twoim przypadku,V0:=1n/n−−√ .
Następnie, w przypadku błędów iteracji Jacobi w oryginalnym systemie, masz
z którego mamy macierz iteracji
Poniższy cytat jest stary i przechowywany wyłącznie w celach informacyjnych. Zobacz później nowy dowód.
Zauważ, żeV0 jest wektorem własnym odpowiadającym wartości własnej 1 z I−D−1L . Na podstawie obserwacji nazywamy Twierdzenie 2.1 z wartości własnych zaktualizowanych macierzy rangi 1 z niektórymi aplikacjami Jiu Dinga i Ai-Hui Zhou.
Twierdzenie 2.1 Niechu i v być dwojgiem n -wymiarowe wektory kolumnowe takie, że u jest wektorem własnym A związane z wartością własną λ1 . Następnie wartości własneA+uvT
są {λ1+uTv,λ2,…,λn} zliczanie krotności algebraicznej.
Następnie wiemy, że widmaS~ jest taki sam jak I−D−1L z wyjątkiem tego, że wartość własna 1 w tym drugim przesunięto o −1 w zero wartości własnej w pierwszym. Odρ(I−D−1L)⊂(−1,1] , mamy ρ(S~)⊂(−1,1) .
źródło
Metody Kryłowa nigdy nie używają jawnie wymiarów przestrzeni, w której się iterują, dlatego można je uruchamiać w systemach pojedynczych, o ile iteraty są przechowywane w podprzestrzeni o wartości innej niż zero. Zwykle odbywa się to poprzez rzutowanie pustego miejsca przy każdej iteracji. Są dwie rzeczy, które mogą pójść nie tak, pierwsza jest znacznie częstsza niż druga.
Aby rozwiązać pojedyncze systemy za pomocą PETSc, patrz
KSPSetNullSpace()
. Większość metod i warunków wstępnych może rozwiązać pojedyncze systemy. W praktyce mała zerowa przestrzeń dla PDE z warunkami brzegowymi Neumanna prawie nigdy nie stanowi problemu, o ile poinformujesz solver Krylova o pustej przestrzeni i wybierzesz rozsądny warunek wstępny.Z komentarzy wynika, że jesteś szczególnie zainteresowany Jacobi. (Dlaczego? Jacobi jest przydatny jako wygładzacz wielosieciowy, ale istnieją znacznie lepsze metody do wykorzystania jako solwery.) Jacobi zastosował doAx=b nie zbiega się, gdy wektor b ma komponent w pustym miejscu A , jednak część rozwiązania prostopadła do przestrzeni zerowej jest zbieżna, więc jeśli rzutujesz przestrzeń zerową z każdej iteracji, zbiega się. Alternatywnie, jeśli wybierzesz spójnyb i początkowe przypuszczenie, że iteraty (dokładnie arytmetyka) nie kumulują składników w przestrzeni zerowej.
źródło