Strona domowa ćwiczeń z Metody Numerycznych I A
w roku akademickim 2001/02.

Metody Numeryczne I A

Zasady zaliczania

• 50% (50 pkt.) - zadania na ćwiczeniach (programy)
• 35% (36 pkt.) - test z wiadomości z wykładu
• 15% (14 pkt.) - obecność na ćwiczeniach

Ćwiczenia rozpoczynają się w poniedziałki o 16:15 w OKWF A. Są dwie przerwy 10 minutowe o pełnych godzinach (czyli 17:00--17:10 oraz 18:00--18:10). Zajecia kończymy formalnie o 18:50 (można wyjść wcześniej, można także zostać do 19:00).

Wiadomości

• Po uwzględnieniu zadań przysłanych za pomocą e-mail i oddanych osobiście do dnia 21-02-2002 punktacja uległa zmianie. Poprawione wyniki zostały uwzględnione w tabeli wyników oraz liście oddanych zadań. Zmianie uległy także oceny niektórych osób. Wyniki (dla tych osób których ocena uległa zmianie) wysłałem do dr Wernera.
• Termin oddawania zadań domowych (czy to osobiście, czy to za pomocą e-mail) upływa z końcem sesji poprawkowej, czyli w piątek, 22-02-2002 r. Po upływie tego terminu nie przyjmuję zadań domowych!. Przypominam, że przysłane zadania będą oceniane na najwyżej 0.8 punkta "zadaniowego".
• Po uwzględnieniu zadań przysłanych za pomocą e-mail i oddanych osobiście do dnia 12-02-2002 punktacja i oceny uległy zmianie. Prof. Werner poprawki przyjął.
• W przyszłym semestrze będę prowadził zajęcia we czwartki, 9:00-12:00, w sali OKWF B.
• Programy można oddawać osobiście (pokój 125, budynek IFT (nowy), termin do uzgodnienia) czy to przynosząc je na dyskietce, czy to przesyłając je wcześniej za pomocą e-mail, czy to logując się zdanie (za pomocą ssh/telnet) na swoje konto i odpalając je tamże. Programy będą sprawdzane na Linuksie albo na własnym koncie.
• Po uwzględnieniu zadań przysłanych za pomocą e-mail do 21-01-2002 punktacja uległa zmianie, ale nie spowodowała zmian w ocenach. Informacja została przesłana do wykładowcy, prof. Wernera. Przepraszam za brak informacji zwrotnej.
• Ostateczne progi ocen oraz zaliczenia
  

  progi	45	60	65	71	75	94
  oceny	3	3+	4	4+	5	5+

  
  
  
• Skrócone wyniki dla grupy 4. (poniedziałkowej), tzn. dla wszystkich osób które pojawiły się na liście obecności na moich zajęciach. Za test można było dostać maksymalnie 36 punktów (za 18 poprawnych odpowiedzi), za obecności można było dostać maksymalnie 14 punktów (za 13 obecności), za programy można było dostać 50 (lub więcej) punktów (za 6 programów), czyli razem maksymalnie 100 punktów. Za oddanie przynajmniej jednego programu osobiście dawałem 50/6 pkt., za każdy oddany program (bez opóźnień i bez dodatkowych punktów) (50 - 20/6)/6 pkt, tzn. punktację z listy oddanych zadań należy przemnożyć przez 7.7778 pkt.
• Tutaj znaleźć można listę obecności i oddanych zadań na dzień 18.01.2001.
• Zadania których termin ważnosci jeszcze nie upłynął można oddawać do końca sesji tzn. do 03-02-2002 (za pomocą e-mail lub osobiście) bez utraty punktów. Po tym terminie zadania będą oceniane na maksimum 0.8 punkta.
• W poniedziałek, 14.02.2002 na wykładzie będzie test sprawdzający wiadomości z wykładu.
• Terminy zadań zostały przesunięte (z wyjątkiem zadań, których termin oddania bez obniżania punktacji minął, czyli zadań 1. i 2.).
• Minął termin oddawania zadania pierwszego i drugiego bez utraty punktów. Zadania pierwsze i drugie będą oceniane na maksimum 0.8 punkta. Pozostałe zadania można oddawać do końca sesji bez utraty punktów.

Przykładowe pytania na teście

1. Algorytm XYZ ma złożoność obliczeniową (czas wykonania) rzędu:
   a) N   b) N log N   c)N²
2. Największy błąd numeryczny dostajemy przy (zakładamy że obie liczby są liczbami zmiennoprzecinkowymi tego samego znaku):
   a) dodawaniu dużych liczb   b) odejmowaniu dużych liczb   c) mnożeniu dużej liczby przez małą

Zadania (programy) domowe

Programy będą oceniane w skali ciągłej [0,1]. Na koniec zajęć ilość punktów uzyskanych za oddane programy będzie dzielona przez ilość obowiązkowych zadań domowych i przeliczana do 50% (najprawdopodobniej 50 pkt.). Za szczególnie "ładne" rozwiązania można dostać dodatkowe punkty (na razie oznaczane przez +). Możliwe jest zatem uzyskanie za programy więcej niż 50% (50pkt). Każde zadanie domowe ma termin oddania (celem tego rozwiązania jest uniknięcie oddawania wszystkich zadań na ostatnich i przedostanich zajęciach). Po przekroczeniu tego terminu punktacja obniżana będzie do maksymalnie 0.8 pkt (punkt o szczególnie "ładnych" rozwiązaniach ma zastosowanie także tutaj). Uwaga: rozszerzenia zadań domowych nie mają terminów.

Programy można wysyłać pocztą (mój adres e-mail to jnareb@fuw.edu.pl), ale preferowane jest oddawanie programów osobiście. Uwaga: proszę zaznaczać które zadanie domowe rozwiązuje przysłany program. Przynajmniej połowa programów powinna (ale nie musi) być oddana osobiście (czy to na ćwiczeniach, czy też umówiwszy się ze mną na konkretny termin). Oceniane jest działanie programu oraz sposób jego zapisania (t.j. ocena bazuje także na źródłach programu). W większości przypadków styl programu nie ma wpływu na ocenę.

Wadą oddawania programów za pomocą poczty elektronicznej jest to, że mogę nie mieć czasu na sprawdzenie przysłanych programów. Zawsze gdy program zostanie sprawdzony i oceniony, wysyłam propozycję oceny i uwagi co do programu na adres zwrotny, tak więc proszę sprawdzać pocztę. Chwilę przysłania programu który wykonuje zlecone działanie uznaję za czas oddania. W razie potrzeby mogę wysyłać potwierdzenie odbioru.

W poradach znajduje się opis preferowanego sposobu (stylu) kodowania (zapisywania programu). Nie jest on obowiązkowy. Służy on głównie jako wskazówka, jak należy pisać programy.

Celem każdego zadania domowego powinno być napisanie zadanego algorytmu (metody) oraz jego przetestowanie.

Zagadnienia przedstawiane na ćwiczeniach

1. Dokładność numeryczna

1.1 Opis teoretyczny

• W pliku wstep.ps.gz (tex) przedstawione są konsekwencje przechowywania liczb rzeczywistych za pomocą reprezentacji zmiennoprzecinkowej na skończonej ilości bitów. Przedstawiony jest problem nadmiaru i niedomiaru w obliczeniach. Podany jest przykład poprawy własności numerycznych zagadnienia przez odpowiedni wybór algorytmu.

1.2 Zadania

1. Znaleźć najmniejszą taką liczbę a != 0, taką że fl(1+a) = 1 (gdzie fl(wyrażenie) oznacza wynik numerycznego obliczenia wyrażenia na liczbach zmiennoprzecinkowych). Znaleźć taką liczbę a, że fl(1/a*a) != 1. Uwaga: podane zadanie można rozwiązać nie korzystając z komputera przy założeniu określonej ilości bitów na mantysę; przy pisaniu programu w razie potrzeby należy zastosować zmienne pomocnicze.
2. Zaimplementować dwa algorytmy obliczania długości przeciwprostokątnej: bezpośrednie zastosowanie wzoru pitagorasa oraz wzór powstały przez wyłączenie większej co do modułu liczby przed pierwiastek (patrz wstep.ps.gz (tex)). Porównać ich dokładność oraz dokładnośc funkcji bibliotecznej hypot. Dla jakich wartości parametrów metoda klasyczna nie działa, a druga metoda daje poprawne wyniki (do tego nie potrzeba używać komputera).
3. Zaimplementować dwa: klasyczny i ulepszony (w którym z klasycznego wzoru oblicza się wiekszy co do moduły pierwiastek zaś drugi ze wzoru Verleta) rozwiązywania równania kwadratowego. Poszukać takich współczynników wielomianu, że metody te dają różne wyniki. Który algorytm jest dokładniejszy?
4. Kumulacja błędów w zagadnieniu obliczania sumy. Należy zaimplementować zwykłe sumowanie ciągu, sumowanie ciągu od najmniejszej wartości (ciąg może być zadany przez piszącego program, więc nie ma potrzeby wykonywać sortowanie), oraz algorytm Gilla-Mollera:

     u = p = 0;
     for (i = 0; i < N; i++) {
       v = A[i];
       s = u + v;
       p = u - s + v + p;
       u = s;
     }
     wynik = s + p
     

   Algorytm Gilla-Mollera zapobiega kumulacji błędów. Zobaczyć który algorytm daje najdokładniejszy wynik.

2. Wielomiany i aproksymacja wielomianowa.

2.1 Opis teoretyczny

• W pliku wielomiany.ps.gz (tex) znajdują się podstawowe informacje na temat wielomianów. M. in. opisany jest tam algorytm Hornera obliczania wartości wielomianu w punkcie.
• W pliku intwielom.ps.gz (tex) opisana zastała interpolacja wielomianowa (zagadnienie Lagrange'a) w punkcie. M. in. opisany został algorytm Neville'a interpolacji wielomianowej. Opisane są też tam metody bisekcji i polowania do znajdowania punktów o które chcemy oprzeć interpolację.
• W rozdziale trzecim "Numerical Receipies in C" 'Interpolation and Extrapolation', w podrozdziale "Introduction" oraz w "Polynominal Interpolation and Extrapolation" znaleźć możemy informacje na temat algorytmu Neville'a z obliczaniem poprawek (oraz jego przykładową implemencację w C).

2.2 Zadania

1. Napisać obliczanie wartości wielomianu danego przez swoje wspólczynniki (zapisane w tablicy) w zadanym punkcie x metodą Hornera:
   W(x) = a₀ + x (a₁ + ... + x (a_n-1 + x a_n)...)
2. Napisać procedury (funkcje) znajdujące elementy tablicy między którymi leży dane x metodami bisekcji oraz polowania. Dokładniej, znależć taki indeks i, że tab_i-1 < x <= tab_i .

2.3 Zadanie domowe

Napisać program dokonujący interpolacji wielomianowej zadanego stopnia metodą Neville'a. Wykres można przedstawić zapisując wyniki do pliku i korzystając z programu gnuplot, lub korzystając z którejś z bibliotek graficznych (g2, GRX, GTK, Qt, Xlib,...). W przypadku robienia wykresu należy, przy funkcji zadanej na N >= m + 1 punktach (gdzie m jest stopniem wielomianu interpolacyjnego), wyznaczać wartość wielomianu interpolacyjnego w punkcie na podstawie intepolacji opartej o najbliższe (w sensie odległości albo w sensie indeksów) m+1 punktów. W przypadku programu nie produkującego wykresów należy przynajmniej dać użytkownikowi możliwość punktu obliczenia intepolacji; program w wyniku powinien podawać wartość interpolacji w punkcie, wartość funkcji w punkcie i błąd interpolacji. Najlepiej, jeśli w programie było podanych kilka przykładowych punktów dla których można zobaczyć własności interpolacji (ekstrapolacji).

Przykładowe funkcje do testowania: |x|, 1/(1+x²), exp(-x²), exp(-1/x²), wielomian.
Czas oddania: do końca listopada bez obniżania punktacji.

3. Znajdowanie współczynników wielomianu interpolujacego.

3.1 Opis teoretyczny

• Tutaj możemy m.in. znaleźć opis algorytmu znajdowania współczynników wielomianu interpolacyjnego przy użyciu algorytmu Neville'a, oraz treść zadania domowego.
• W intlagr.ps możemy znaleźć metody znajdowania współczynników wielomianu interpolacyjnego oparte o wzór Lagrange'a i za pomocą ilorazów różnicowych.

3.2 Zadanie domowe

4. Interpolacja przy pomocy funkcji sklejanych (splines).

4.1 Opis teoretyczny

• W pliku spline.ps.gz (tex) znaleźć można opis algorytmu interpolacji funkcjiami sklejanymi trzeciego stopnia (splines). Podany algorytm pochodzi z "Numerical Receipies in C".
• Tutaj możemy znaleźć szczegółowy opis klasycznego (wyznaczanie współczynników każdego składeowego wielomianu) algorytmu interpolacji funkcjami sklejanymi. Uwaga: plik ten ma tę sama nazwę co powyższy.

4.2 Zadania

1. Napisać procedurę (funkcję) rozwiązującą układ równań o macierzy w postaci trójliniowej metodą przeganiania. Sprawdzić, czy daje ona dobre wyniki (przez przemnożenie wyniku przez macierz i sprawdzenie czy wynik jest równy wektorowi prawej strony).
2. Napisać procedurę (funkcję) dokonującej interpolacji funkcjami sklejanymi trzeciego stopnia (splines) przy zadanych wartościach funkcji i drugiej pochodnej funkcji w punktach, t.j. danych x_i, f_i = f(x_i), d2f_i = f''(x_i) .

4.3 Zadanie domowe

5. Całkowanie numeryczne przy pomocy kwadratur Gaussa.

5.1 Opis teoretyczny

5.2 Zadania

1. Całkowanie za pomoca kwadratury Gaussa-Legendre'a, z adaptacyjnym dzieleniem przedziału.
2. Całkowanie po przedziale nieskończonym za pomocą kwadratur Gaussa-Laguerre'a, Gaussa-Hermite'a oraz przez zamianę zmiennych (sprowadzenia do przedziału skończonego).

5.3 Zadanie domowe

Napisać program całkujący różne funkcje w zadanych przedziałach za pomocą kwadratur Gaussa-Legendre'a oraz Gaussa-Czebyszewa. Program powinien jako jedną z całek liczyć całkę na przedziale niewłaściwym (nieograniczonym przynajmniej z jednej strony) za pomocą odpowiedniej zamiany zmiennych. Całkowanie powinno się odbywac za pomocą kolejnego dzielenia przedziałów aż do osiągnięcia założonej dokładności lub przekroczenia ilości kroków.

Do oszacowania błędu całkowania można użyć wyników dla przedziału i przedziału podzielonego na części, lub dla kwadratury i kwadratury wyższego stopnia na tym samym przedziale. (Dla chętnych: zaimplementować kwadratury Gaussa-Kronroda, które licząc kwadraturę 2n+1. rzędu korzystają z węzłów kwadratury n. rzędu. Patrz pakiet QUADPACK, w szczególności procedury qk21 i podobne.). Przy dzieleniu przedziałów na części warto dzielić ten przedział, który daje największy błąd (szybkie znajdowanie minimum można zrobić za pomoca kolejki priorytetowej zaimplementowanej w postaci kopca), ale można po prostu dzielić te przedziały które dają większy błąd (jako wkład do całki) niż założona dokładność.

Dla chętnych: zastosować algorytm sumowania z poprawkami Gilla-Mollera.

Przykładowe funkcje do zcałkowania:

Czas oddania: do końca sesji bez obniżania punktacji.

6. Całkowanie numeryczne rozszerzoną metodą trapezów.

6.1 Opis teoretyczny

6.2 Zadania

1. Napisać procedurę (funkcję) całkującą zadaną funkcje po przedziale domkniętym rozszerzoną metodą trapezów. Rząd metody powinien być zwiększany do osiągnięcia żądanej dokładności (jako oszacowanie błędu można wziąść różnicę między wynikami z kolejnych rzędów) lub przekroczenia maksymalnej ilości podziałów. Funkcja powinna wykorzystywać wyniki z poprzedniego rzędu dla uniknięcia wielokrotnego obliczania wartosci funkcji w tym samym punkcie.

6.3 Zadanie domowe

Napisać program całkujący zadaną funkcję w zadanym przedziale za pomocą rozszerzonej metody trapezów. Program powinien zwiększać rząd metody (ilość podziałów) aż do osiągnięcia zakładanej dokładności lub przkeroczenia maksymalnej ilości iteracji.

To zadanie domowe można połączyć z poprzednim zadaniem, na całkowanie (adaptacyjne) za pomocą kwadratur Gaussa.
Czas oddania: do końca sesji bez obniżania punktacji.

7. Całkowanie wielowymiarowe metodą całki wielokrotnej. Ekstrapolacja Richardsona i metoda Romberga.

7.1 Opis teoretyczny

7.2 Zadania

1. Napisać funkcję obliczającą całkę wielokrotną (wielowymiarową) albo pisząc ogólną procedurę całkowania funkcji z parametrem i przekazując pozostałe zmienne jako parametry, albo napisać całkowanie dla zadanej liczby wymiarów, przekazując pozostałe zmienne w zmiennych globalnych (statycznych).
2. Napisać program całkujący metoda Romberga dla metody trapezów, bądż to korzystający bezpośrednio ze wzorów na ekstrapolację Richardsona, bądż to dokonujący ekstrapolacji wielomianowej do kroku równego 0 (jak w "Numerical Receipies"). Program/funkcja powinna wyliczać całkę z zadaną dokładnością (jeśłi się da) i wykorzystywać wyniki z poprzedniego rzędu.

7.3 Rozszerzenie zadania domowego z całkowania metodą trapezów

8. Rozwiązywanie równań nieliniowych.

8.1 Opis teoretyczny

• W pliku miejsca_zerowe.ps.gz (tex) przedstawiony jest wstęp do metod znajdowania miejsca zerowego (pierwiastka) równania nieliniowego jednowymiarowego, podane są różne algorytmy oraz zadanie domowe.
• W pliku miejzer.ps są opisane metody bisekcji, Newtona (stycznych), Steffensena, siecznych oraz metoda Riddersa. Zdefiniowany jest tam także wykładnik zbieżności metody. Większość informacji można znaleźć w pliku miejsca_zerowe.ps.gz (tex).
• W rozdziale 9. "Numerical Receipies in C" 'Root Finding...', w podrozdziale "Bracketing and Bisection" opisany jest sposób znalezienia przedziału wewnątrz którego znajduje się rozwiązanie (pierwiastek) oraz metoda bisekcji.

8.2 Zadania

1. Napisać procedurę (program) znajdującą zero zadanej funkcji w podanym przedziale z zadaną dokładnością metodą bisekcji, lub do przekroczenia zadanej liczby iteracji. Jako oszacowanie błędu można wziąć długość przedziału (dokładność znalezienia punktu) i/lub wartość bezwzględną funkcji w punkcie (np. pośrodku przedziału) (dokładność spełnienia warunku). Innym warunkiem na osiągnięcie zadanego błędu bezwzględnego (epsabs) i bezwzględnego (epsrel) jest zastosowanie do testowania czy osiągnięto zadane dokładności wzoru: |a - b| < epsabs + epsrel min(|a|, |b|), o ile przedział [a, b] nie zawiera 0. Innym oszacowaniem błędu znalezienia rozwiązania jest |f(x)|/|f'(x)| ~= |f((a+b)/2)| |a-b|/|f(a)-f(b)|.

8.3 Zadanie domowe

Napisać procedurę (program) znajdującą zero zadanej funkcji w podanym przedziale z zadaną dokładnością metodą bisekcji. Więcej informacji w pliku miejsca_zerowe.ps.gz (tex).
Czas oddania: do końca sesji bez obniżania punktacji.

9. Sortowanie.

9.1 Opis teoretyczny

• W pliku sortowanie.ps.gz (tex) opisane są metody sortowania przez wstawianie, selekcję oraz sortowanie stogowe. Podany jest też sposób wykorzystania bibliotecznej funkcji qsort do sortowania szybkiego (quicksort).

9.2 Zadania

1. Napisać procedurę i przykładowy program sortujące tablicę liczb zmiennoprzecinkowych (float) w porządku malejącym dowolnie wybraną metodą.