MN08LAB: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
m
m
 
Linia 101: Linia 101:
 
najwygodniejsze jest w CSR, bo dodatkowo narzuca zasadę lokalności w przestrzeni. Wyłuskanie wartości jest najmniej efektywne w
 
najwygodniejsze jest w CSR, bo dodatkowo narzuca zasadę lokalności w przestrzeni. Wyłuskanie wartości jest najmniej efektywne w
 
formacie AIJ. Szczegóły opisane są w rozdziale 3.5 książki  
 
formacie AIJ. Szczegóły opisane są w rozdziale 3.5 książki  
* <span style="font-variant:small-caps">Y. Saad</span>, <cite> [http://www-users.cs.umn.edu/&nbsp;saad/books.html  Iterative methods for sparse linear systems]</cite>, PWS, 1996.
+
* <span style="font-variant:small-caps">Y. Saad</span>, <cite> [http://www-users.cs.umn.edu/~saad/books.html  Iterative methods for sparse linear systems]</cite>, PWS, 1996.
  
Zobacz także implementacje w Fortranie, w pakiecie [http://www-users.cs.umn.edu/&nbsp;saad/software/SPARSKIT/sparskit.html  SPARSKIT], będącym czymś w rodzaju odpowiednika BLAS dla macierzy rozrzedzonych.
+
Zobacz także implementacje w Fortranie, w pakiecie [http://www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html  SPARSKIT], będącym czymś w rodzaju odpowiednika BLAS dla macierzy rozrzedzonych.
  
 
</div></div></div>
 
</div></div></div>
Linia 115: Linia 115:
  
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">   
 
<div class="mw-collapsible mw-made=collapsible mw-collapsed"><span class="mw-collapsible-toogle mw-collapsible-toogle-default style="font-variant:small-caps">Rozwiązanie </span><div class="mw-collapsible-content" style="display:none"><div style="margin-left:1em">   
Zobacz, jak to zrobiono w pakiecie [http://www-users.cs.umn.edu/&nbsp;saad/software/SPARSKIT/sparskit.html  SPARSKIT].
+
Zobacz, jak to zrobiono w pakiecie [http://www-users.cs.umn.edu/~saad/software/SPARSKIT/sparskit.html  SPARSKIT].
 
</div></div></div>
 
</div></div></div>
  

Aktualna wersja na dzień 21:26, 29 wrz 2006


Układy liniowe z macierzami rzadkimi

<<< Powrót do strony głównej przedmiotu Metody numeryczne

Oglądaj wskazówki i rozwiązania __SHOWALL__
Ukryj wskazówki i rozwiązania __HIDEALL__

Ćwiczenie: Metoda Richardsona

Jedną z najprostszych klasycznych metod iteracyjnych dla równania jest metoda Richardsona, zadana wzorem

gdzie jest pewnym parametrem. Gdy , mamy do czynienia ze zwykłą metodą iteracji prostej, która najczęściej nie będzie zbieżna, dlatego wybór parametru jest kluczowy dla skuteczności metody.

Dla symetrycznej, dodatnio określonej sprawdź, przy jakich założeniach o metoda będzie zbieżna do rozwiązania z dowolnego wektora startowego i oceń szybkość tej zbieżności.

Testuj na macierzy jednowymiarowego laplasjanu różnych wymiarów. Jak najefektywniej zaimplementować mnożenie przez ?

Wskazówka
Rozwiązanie

Ćwiczenie

Zaimplementuj operacje:

  • mnożenia macierzy przez wektor ,
  • wyłuskania wartości elementu ,
  • zmiany wartości pewnego zerowego wyrazu macierzy na niezerową,

jeśli macierz jest zadana w formacie

  • AIJ,
  • CSC,
  • CSR.

Przetestuj dla kilku macierzy z kolekcji MatrixMarket.

Rozwiązanie

Ćwiczenie: Konwersja formatu macierzy rzadkiej

Napisz procedurę aij2csr, konwertującą macierz w formacie AIJ do CSR i csr2aij, działającą w drugą stronę.

Rozwiązanie


Ćwiczenie

Jak tanio rozwiązywać układ równań z macierzą cykliczną trójdiagonalną, tzn.

Dla uproszczenia załóżmy, że macierz jest dodatnio określona i symetryczna.

Zaimplementuj opracowaną metodę, korzystając z BLASów i LAPACKa.

Wskazówka
Rozwiązanie

Ćwiczenie: CGNE

Ktoś mógłby sugerować, że skoro CG działa tylko dla macierzy symetrycznych, to dowolny układ z macierzą nieosobliwą można transformować do równoważnego mu układu równań normalnych

którego macierz jest już oczywiście macierzą symetryczną i dodatnio określoną.

Wskaż potencjalne wady tej metody i podaj sposób jej implementacji.

Wskazówka
Rozwiązanie