MN05LAB

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania


Rozwiązywanie układów równań liniowych

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

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

Uwaga

Niektóre fragmenty zadań wymagają wykorzystania procedur LAPACKa; te części odłóż do momentu, gdy opanujesz następny wykład, dotyczący m.in. bibliotek algebry liniowej.

Ćwiczenie: Metoda Cholesky'ego

Ważnym przykładem macierzy szczególnej postaci są macierze symetryczne i dodatnio określone. Są to macierze spełniające warunki:

Dla takich macierzy można nieco zmniejszyć koszt kombinatoryczny i zużycie pamięci, przeprowadzając trochę inny rozkład na macierze trójkątne: tak, aby otrzymać rozkład

zamiast , przy czym jest tu jak zwykle macierzą trójkątną dolną z jedynkami na przekątnej, a jest macierzą diagonalną z dodatnimi elementami na diagonali. Opracuj taki algorytm. W jego implementacji możesz porównywać się z procedurą LAPACKa DPOSV. Inny wariant tego samego rozkładu to tak zwany rozkład Cholesky'ego--Banachiewicza, w którym, przy tych samych założeniach na , szukamy rozkładu wykorzystującego tylko jedną macierz trójkątną dolną:

(oczywiście tym razem nie żądamy, aby miała na diagonali jedynki). Jaka jest relacja między rozkładem a ?

Rozwiązanie

Ćwiczenie: Mnożyć przez odwrotność to nie zawsze to samo...

W Octave układ równań rozwiązujemy korzystając z "operatora rozwiązywania równania"

x = A \ b;

Ale w Octave jest także funkcja inv, wyznaczająca macierz odwrotną, więc niektóre (nie najlepsze, oględnie mówiąc) podręczniki zalecają

x = inv(A)*b;

Przedyskutuj, które podejście jest lepsze i dlaczego. Przeprowadź eksperymenty numeryczne weryfikujące twoją tezę.

Rozwiązanie

Ćwiczenie: Wybór elementu głównego jest naprawdę ważny!

Rozwiąż prosty układ równań

czterema sposobami:

  • na kartce papieru (dokładnie!)
  • w komputerze, w arytmetyce podwójnej precyzji, korzystając z rozkładu LU bez wyboru elementu głównego
  • jak poprzednio, ale z wyborem elementu głównego w kolumnie
  • w LAPACKu lub Octave.

Porównaj uzyskane rozwiązania i wyciągnij wnioski.

Rozwiązanie

Ćwiczenie

Zapisz w Octave algorytm rozkładu LU macierzy (bez wyboru elementu głównego) działający in situ.

Wskazówka

Wykorzystaj go do napisania funkcji, która rozwiąże układ równań .

Przetestuj tę funkcję na kilku macierzach i porównaj czas jego działania z czasem wykonania operacji x = A\b.

Spróbuj zastosować swój algorytm do kilku specjalnych macierzy:

  • Hilberta dużego wymiaru
  • diagonalnej z jednym elementem bardzo małym (a nawet równym zero)
Rozwiązanie

Ćwiczenie: Układy równań z wieloma prawymi stronami

Podaj sposób taniego wyznaczenia rozwiązania sekwencji układów równań z tą samą macierzą i różnymi prawymi stronami:

Układy równań z tą samą macierzą, ale ze zmieniającą się prawą stroną równania powstają często na przykład przy rozwiązywaniu równań różniczkowych cząstkowych, gdzie prawa strona układu odpowiada zmieniającym się warunkom brzegowym.

Wskazówka
Rozwiązanie

Ćwiczenie: Obliczanie wyznacznika macierzy

Bardzo rzadko w praktyce numerycznej zdarza się potrzeba obliczenia wartości wyznacznika macierzy . Zaproponuj metodę obliczania oraz wskaż, jakiego rodzaju problemy numeryczne możesz napotkać.

Rozwiązanie