Metoda Stone'a

W analizie numerycznej metoda Stone'a , znana również jako procedura silnie niejawna lub SIP , jest algorytmem rozwiązywania rzadkiego liniowego układu równań . Metoda wykorzystuje niepełną dekompozycję LU , która jest zbliżona do dokładnej dekompozycji LU , aby uzyskać iteracyjne rozwiązanie problemu. Nazwa metody pochodzi od nazwiska Harolda S. Stone'a , który zaproponował ją w 1968 roku.

Dekompozycja LU jest doskonałym narzędziem do rozwiązywania równań liniowych ogólnego przeznaczenia. Największą wadą jest to, że nie wykorzystuje macierzy współczynników jako macierzy rzadkiej. Dekompozycja LU rzadkiej macierzy zwykle nie jest rzadka, dlatego w przypadku dużego układu równań dekompozycja LU może wymagać zaporowej ilości pamięci i liczby operacji arytmetycznych .

W metodach iteracyjnych z uwarunkowaniami wstępnymi , jeśli macierz warunkująca M jest dobrym przybliżeniem macierzy współczynników A , to zbieżność jest szybsza. Prowadzi to do pomysłu wykorzystania przybliżonej faktoryzacji LU z A jako macierzy iteracji M .

W 1968 roku Stone zaproponował odmianę metody niezupełnej dekompozycji dolna-górna. Metoda ta jest przeznaczona do układów równań powstałych w wyniku dyskretyzacji równań różniczkowych cząstkowych i została po raz pierwszy zastosowana do pięciokątnego układu równań otrzymanych podczas rozwiązywania eliptycznego równania różniczkowego cząstkowego w przestrzeni dwuwymiarowej metodą różnic skończonych . Przybliżona dekompozycja LU wyglądała w tej samej pięciokątnej formie, co oryginalna macierz (trzy przekątne dla L i trzy przekątne dla U ) jako najlepsze dopasowanie z siedmiu możliwych równań dla pięciu niewiadomych dla każdego rzędu macierzy.

Algorytm

       
       
        metoda  kamień  jest  Dla układu liniowego  A  x = b  obliczyć niepełną  faktoryzację macierzy  A  A  x  = (  M  -  N  )x = (  LU  -  N  )x = b  M  x  (k+1)  =  N  x  (k)  + b , z ||  M  || >> ||   N  ||  M  x  (k+1)  =  LU  x  (k+1)  = c  (k) 
       
     LU  x  (k)  =  L  (  U  x  (k+1)  ) =  L  y  (k)  = c  (k)  zgadnij  k = 0, x  (k)  r  (k)  = b -  A  x  (k)  podczas gdy  (  ||r  (k)  ||  2  ≥ ε  )  oblicz  nową prawą stronę  c  (k)  =  N  x  (k)  + b  rozwiąż 
     L  y  (k)  = c  (k)  przez podstawienie w przód  y  (k)  =  L  −1  c  (k)  rozwiązanie  U  x  (k+1)  = y  (k)  przez podstawienie wsteczne  x  (k+1)  =  U  − 1  y  (k)  koniec podczas 

przypisy

• Kamień, HL (1968). „Iteracyjne rozwiązanie niejawnych przybliżeń wielowymiarowych równań różniczkowych cząstkowych”. SIAM Journal o analizie numerycznej . 5 (3): 530–538. Bibcode : 1968SJNA....5..530S . doi : 10.1137/0705044 . hdl : 10338.dmlcz/104038 . - artykuł oryginalny
•   Ferziger, JH i Peric, M. (2001). Metody obliczeniowe dla dynamiki płynów . Springer-Verlag w Berlinie. ISBN 3-540-42074-6 . {{ cite book }} : CS1 maint: wiele nazwisk: lista autorów ( link )
• Acosta, JM (2001). Algorytmy numeryczne dla trójwymiarowych obliczeniowych problemów dynamiki płynów . praca doktorska . Politechnika Katalońska.
• Ten artykuł zawiera tekst z artykułu Stone's_method na CFD-Wiki , który jest objęty licencją GFDL .