Metoda macierzy rzadkich

Z Wikipedii, wolnej encyklopedii
Przejdź do nawigacji Przejdź do wyszukiwania

Metoda macierzy rzadkich rozwiązuje trzy następujące problemy informatyczne:

Metoda LU (ang. lower – dolny, upper górny) – metoda rozwiązywania układu równań liniowych. Nazwa pochodzi od użytych w tej metodzie macierzy trójkątnych, tj. dolnotrójkątnej (dolnej) i górnotrójkątnej (górnej). Metoda pozwala także na szybkie wyliczenie wyznacznika macierzy układu. Macierz wstęgowa lub pasmowa – kwadratowa macierz rzadka, której wszystkie elementy są zerowe poza diagonalą i wstęgą wokół niej. Mając daną macierz n × n {displaystyle n imes n} jej elementy a i , j {displaystyle a_{i,j}} są niezerowe, gdy i − k 1 ⩽ j ⩽ i + k 2 {displaystyle i-k_{1}leqslant jleqslant i+k_{2}} ; gdzie k 1 , 2 ⩾ 0 {displaystyle k_{1,2}geqslant 0} określają tzw. szerokość wstęgi.
  • Oszczędny zapis tzw. macierzy rzadkiej, tzn. macierzy z dużą liczbą wyrazów zerowych, nie wymagający blokowania dużej pamięci na zapisywanie zer. Macierze takie występują często przy rozwiązywaniu praktycznych zagadnień, sprowadzających się do układu równań liniowych.
  • Przeciwdziałanie zagęszczaniu macierzy w trakcie procesu rozwiązywania układu tych równań.
  • Modyfikacja algorytmu rozwiązywania w celu automatycznego wyeliminowania zbędnych operacji z udziałem zer.
  • Metody przechowywania macierzy rzadkiej w pamięci[ | edytuj kod]

    Przyjmuje się następujące założenia:

  • Wszystkie wyrazy z głównej przekątnej macierzy Y są różne od zera: dla i=1,2...n
  • gdzie n jest liczbą niezależnych węzłów układu.
  • Macierz Y ma strukturę symetryczną, co oznacza, że wyrazy na pozycjach symetrycznych względem głównej przekątnej są albo jednocześnie zerami, albo jednocześnie mają wartości ≠0 (ale niekoniecznie równe).
  • Zatem:

    Metoda pamiętania wierszami[ | edytuj kod]

    Metoda ta polega na przeglądaniu macierzy Y wierszami i zapisywaniu kolejno napotykanych niezerowych wyrazów do wektora Y. Dodatkowo tworzy się dwa wektory indeksowe typu integer. Pierwszy z nich A ma tyle pozycji co wektor Y i zawiera numery kolumn, tj. drugich indeksów odpowiednich wyrazów zapisanych w Y. Drugi wektor indeksowy F ma liczbę pozycji = liczbie wierszy macierzy Y i zawiera numery pozycji w wektorze A (lub w Y) rozpoczynające odpowiedni wiersz w macierzy Y. Innymi słowami określa on zakres pozycji w Y (lub w A) dotyczących wyrazów tego samego wiersza macierzy Y, a więc cechujących się tym samym pierwszym indeksem.

    Metoda dostosowana do | edytuj kod]

    Niezerowe wyrazy macierzy X zapisuje się tu w trzech oddzielnych wektorach typu „real”:

  • Y0 – zawiera kolejne wyrazy głównej przekątnej macierzy Y;
  • YU – zawiera niezerowe wyrazy z górnej, trójkątnej części macierzy Y przeglądanej wierszami;
  • YL – zawiera niezerowe wyrazy z dolnej, trójkątnej części macierzy Y przeglądanej kolumnami.
  • Wykorzystując założoną symetrię strukturalną macierzy Y można użyć tylko dwóch wektorów indeksowych A i F, dotyczących zarówno wektora YU, jak i YL. A – zawiera numery kolumn (drugie indeksy) wyrazów w wektorze YU i jednocześnie numery wierszy (pierwsze indeksy) wyrazów w wektorze YL, F – zawiera numery pozycji w YU (YL) rozpoczynających kolejny wiersz (kolumnę) w Y

    Podstrony: 1 [2] [3]




    Reklama