Projekt komputerowy na zaliczenie w terminie wstępnym,
Wstęp do Informatyki -semestr zimowy
Termin: ostatni lab tzn pierszy/drugi tydzień stycznia

Napisać program który implementuje procedurę rozkładu macierzy $A$ na $PA=LU$ wymiaru $n\times n$ metodą eliminacji Gaussa z częściowym wyborem elementu głównego ($L$ - macierz dolnotrójkątna, $U$- górnotrójkątna, $P$- macierz permutacji - czyli inaczej $PA$ macierz o spermutowanych wierszach macierzy $A$) i zastosować do rozwiązywnia układów równań liniowych $A{\bf x}={\bf b}$. Testowąc program jak opisano poniżej.

W programie wprowadzić następujące opcje na wczytywanie danych:

• podawanie elementów macierzy/wektora prawej strony(ps) z klawiatury
• wczytywanie macierzy/wektor ps z pliku tekstowego o określonym formacie, np. dla macierzy pierwsza linia - liczba naturalna $n$- wymiar macierzy kolejnych $n$ lini zawierających po $n$ liczb zmiennoprzecinkowych, w razie mniejszej/większej ilości tych liczb program ma zakładać że brakujące są zerami albo ignorować kolejne nadmiarowe liczby, analogicznie dla wektora prawej strony
• macierz/wektor ps generowane przez wzór np $a[i,j]=1/(1+i+j);\; i,j=1,\ldots,n$ - wzór może być podany w programie, nie jest koniecznie aby była możliwość wprowadzenia wzoru z klawiatury interaktywnie.

• elementy macierzy/wektora ps są losowane np. na diagonali n poza elementy o module mniejszym od jeden.

Po rozkładzie macierzy możliwe powinno być wykorzystywanie rozkładu dla rozwiązywanie układu równań liniowych dla różnych wektorów prawej strony ${\bf b}$ bez ponownego wykonywania rozkładu.

Powinna być też opcja włączania/wyłączania częściowego wyboru elementu głownego (c.w.e.g) (wtedy dla pewnych macierzy program może przestać działać mimo że działał z c.w.e.g.)

Po rozwiązaniu układu drukować błąd względny i residualny w normie 2, tzn.

1. $\Vert {\bf x} - \tilde{ \bf x} \Vert _2 / \Vert {\bf x}\Vert _2$
2. $\Vert A {\bf\tilde{x}} - {\bf b}\Vert _{1}/\Vert A\Vert _F\Vert{\bf x}\Vert _{2}$

gdzie ${\bf x}=(x[1],\ldots,x[n])^T$ rozwiązanie (znane) dokładne, ${\bf\tilde{x}}$ rozwiązanie przybliżone otrzymane po obliczeniach algorytmem,

$$\Vert{\bf y} \Vert _{2}=\sqrt{\sum_{i=1}^{n}\vert y[i]\vert... ...}\vert a[i,j]\vert^{2}} (\hbox{norma Frobeniusa macierzy} A).$$

Wypisywanie rowiązania uzyskanego algorytmem ${\bf\tilde{x}}$ na ekranie pozostawić jako opcję, tzn po rozwiązaniu układu drukować tylko błedy a użytkownik może np wciskając odpowiedni klawisz i/lub klikając gdzieś myszką rozwiązanie zobaczyć.

Rozwiązanie znane ${\bf x}$ można uzyskać losowaniem a następnie prawą stronę dostaniemy mnożąc przez macierz $A$ tzn ${\bf b} = A {\bf x}$.

Powyższy algorytm rozkładu będzie omówiony teoretycznie na algebrze liniowej wkrótce. Ponieważ jest to projekt na zalicznie w terminie wstępnym więc w jego skład wchodzi też dokładne zapoznanie się z powyższym algorytmem - wystarczy aspekt algorytmiczny tzn jak działa algorytm bez znajomości uzasadnienia czy i dlaczego działa, dla jakich macierzy itd. okaże się, że algorytm ten nie jest za skomplikowany - trzy pętle + ewentualna zamiana wierszy macierzy. Większa część pracy będzie związana z zaprogramowaniem opcji na wczytywanie macierzy, drukowanie błędów itp

Ten algorytm zwany też algorytmem eliminacji Gaussa z c.w.e.g. omówiony jest w każdej książce o metodach numerycznych czy do algebry liniowej (wtedy pominięty jest zazwyczaj aspekt wyboru elementu głównego i w ogóle praktyczna stron implementacji). Ewentualnie slużę informacją lub objaśnieniem jakby ktoś miał kłopoty ze zrozumieniem lub znalezieniem opisu algorytmu.

Ocena będzie zależała od uwzględnienia wszystkich zaleceń i ogólnej funkcjonalności/sensowności programu (oczywiscie bez przesady - wystarczy np wybieranie opcji może być podawaniem cyfr z klawiatury i wciśnięciem Enter). jeśli chodzi o sensowność to np. nie ma sensu trzymać całej macierzy permutacji $P$, która jest złożeniem (iloczynem) transpozycji (zamiany indeksów) wystarczy zapamiętać kolejne transpozycje w formie pary odpowiednich indeksów, jak ktoś napisze program w taki sposób że trzyma całą macierz $P$ $n\times n$ w pamięci i potem przez nią mnoży wektory stadardowo to oczywiście to nie wpłynie na podwyższenie ilości pktów za projekt,trzeba się posłużyć zdrowym rozsądkiem.

Ważne: Termin zaliczenia nieprzekraczalny!!!