Semestr zimowy 2007/08

Konsultacje
  1. Matematyka obliczeniowa
  2. Metody numeryczne - ćwiczenia

Matematyka obliczeniowa

Uwaga! Egzamin termin dodatkowy (dla osób z usprawiedliwieną nieobecnością na II terminie) - pisemny - czwartek 17 kwietnia 2008 (czwartek) - 1215-1345 - sala4420 (wielka sala wykładowa na III piętrze) nie wolno mieć żadnych notatek



Zakres: cały wykład. Po egzaminie pisemnym zostanie zaproponowana ocena - którą osoby które przekroczą pewien minimalny próg będą mogły poprawić/pogorszyć na egzaminie ustnym

Egzamin MO II zakończony!
Wyniki egzaminów I i II: USOS

Program wykładu
(dość orientacyjny, kolejność punktów może ulec zmianie, będę podawał daty w miejscach gdzie skończyłem wykład z danej daty wraz z aktualizacją treści)
  1. Wstęp - czym jest matematyka obliczeniowa
  2. Arytmetyka zmiennopozycyjnej - fl - podstawowe wiadomości (4/10/2007) w tym definicje uwarunkowania względnego zadania i numerycznej poprawności algorytmu
  3. Metody rozwiązywania równań nieliniowych (skalarnych) - metoda iteracji prostych (Banachowskich), metoda bisekcji, metoda Newtona. Zbieżność m Newtona kwadratowa (lokalna) (11/10/2007) i globalna dla funkcji wypukłej, rosnącej. Rząd zbieżności metody (zbieżność z wykładnikiem p)). Metoda siecznych i jej zbieżność lokalna (bez dowodu). (18/10/2007)
  4. Aproksymacja: definicja elementu najlepszej aproksymacji (ENA) w dowlnej p. unormowanej, tw o istnieniu z przykładem że może nie być jednoznaczności. Interpolacja (jako zag. aproksymacji) wielomianowa Lagrange'a : istnienie i jednoznaczność rozwiązania, postać w bazie Lagrange'a i bazie Newtona w tym metoda Newtona (25/10/2007) i algorytm różnic dzielonych znajdowania wiel. interp. Lagrange'a, błąd interpolacji przy maksymalnej regularności funkcji oraz w przypadku ograniczonej regularności - korzystając z tw Jacksona z teorii aproksymacji, przyklad Rungego czyli ciag wielomianów interpolacyjnych na wezlach równoodległych NIE musi byc zbieżny jednostajnie do funkcji którą interpoluje (8/11/2007)
  5. Kwadratury - przybliżone obliczanie całek i wielomiany ortogonalne- rząd kwadratury, kwadratury interpolacyjne w tym trapezów i Simpsona, kwadratury złożone m.in. złożona kwadratura trapezów i Simpsona - wzory na błąd w przypadku gdy funkcja maksymalnej regularności oraz zbieżność w przypadku gdy funkcja tylko ciągła, (15/11/2007), wielomiany ortogonane w przestrzeniach typu L2g(a,b) - definicja i fakt ze ich pierwiastki są rzeczywiste i jednokrotne w (a,b), kwadratury o maksymalnym rzędzie oparte o zera takich wielomianów ortogonalnych czyli kwadratury Gaussa, ich zbiezność i oszacowanie błędu, przykłady wielomianów ortogonalnych : wielomiany Legendre'a, Hermite'a, Czebyszewa. Rożniczkowanie numeryczne (22/11/2007)
  6. FFT i interpolacja trygonometryczna (zespolona) - algorytm szybkiej transformaty Fouriera (FFT - fast Fourier transform) w wersji rekurencyjnej i zastosowanie do interpolacji zespolonej na siatce równomiernej na sferze jednostkowej zespolonej (29/11/2007)
  7. Interpolacja splajnowa - splany liniowe interpolacyjne i kubiczne w tym baza splajnow kubicznych, oszacowania błędu w normie L2 (6/12/2007)
  8. Kolokwium na wykładzie (13/12/2007)
  9. Aproksymacja w przestrzeniach z iloczynem skalarnym elem. najlep. aproksym. ENA to rzut ortogonalny wyznaczony jednoznacznie, układ z macierzą Gramma, baza ortogonalna - ortogonalizacja Gramma-Schmidta, wielomiany ortogonalne w przestrzeniach typu L2 (20/12/2007) dokończenie- reguła trójczłonowa, regularne liniowe zadanie najmniejszych kwadratów (RLZNK), układ równań normalnych jako szczególny przypadek aproksymacji w przestrzeni unitarnej: rozkłady QR (ortogonalizacja Gramma-Schmidta w Rn i (3/01/2008) metoda Housholdera) i ich zastosowanie do rozwiązywania RLZNK
  10. Aproksymacja jednostajna (krótka informacja) - zadanie, twierdzenie Czebyszewa o alternansie, jednoznaczność, (10/01/2008)związek z intepolacją Lagrange'a w węzłach Czebyszewa (tj odpowiednio przeskalowanch zerach odp. wielomianów Czebyszewa) - to na ćwiczenia
  11. Numeryczna algebra liniowa bezpośrednie metody rozwiązywania układów równań liniowych m.in. zastosowanie rozkładów QR (uzyskanych poprzez ortogonalizację G-S i za pomocą m. Housholdera) czyli zadanie rozwiązania układu równań liniowych jako szczególny przypadek RLZNK, eliminacja Gaussa czyli rozkład LU z częściowym i pełnym wyborem elem. głównego, (17/01/2008) jak obliczyć wyznacznik, uwarunkowanie zadania, informacja o własnościach numerycznych (fl) rozkładu LU
  12. Zagadnienie własne czyli numeryczne znajdowanie wektorów i wartości własnych. Metoda potęgow, odwrotna potęgowa, (24/01/2008)

Warunki zaliczenia:

ćwiczenia

Zalicza 25pkt. Max 30 punktów można uzyskać z kolokwium (w terminie wykładu) i 30pkt z ćwiczeń (zadania domowe, zadania komputerowe, kartkówki itp - szczegóły ustali prowadzący ćwiczenia).

Egzamin

Egzamin pisemny w I terminie będzie obejmował zakres materiału bez ostatniego wykładu. Z egzaminu pisemnego w I terminie można będzie otrzymac max 40 pktów. Propozycja oceny będzie zależałą od łącznej sumy punktów z egzaminu pisemnego, ćwiczeń i kolokwium. Podsumowując kolokwium 30, ćwiczenia 30, egzamin 40 - razem 100p.
W II terminie egzamin pisemny będzie obejmował cały wykład i również elementy zaliczenia ćwiczeń czyli więcej zadań.

Literatura:

Podręczniki: Pozycje [Mos2002] i [Pla2002] to skrypty dostępne dla studentów naszego wydziału. A pozycja [FMW2005] to książka skierowana raczej do studentów politechniki ale większość algorytmów jest w niej opisana. [KC2006] jest godnym polecenia podręcznikiem niestety drogim!

Inne użyteczne linki

Literatura dodatkowa dla osób zainteresowanych metodami numerycznymi, obejmująca materiał częściowo lub często całkowicie poza zakresem wykładu
Ciekawe eseje wyjaśniające mam nadzieję czym jest i czym na pewno nie jest Analiza Numeryczna (czy inaczej Matematyka Obliczeniowa)
Inne eseje tegoż autora o analizie numerycznej i nie tylko http://web.comlab.ox.ac.uk/oucl/work/nick.trefethen/

Ćwiczenia MO

Lista punktów z zadań komputerowych i kartkówek - aktualizowana w miarę na bieżąco. - plik pdf

  1. Gr 4 wtorek 830-10 - sala 5840
  2. Gr 1 czwartek 1600-1730 - sala 3250

Uwaga! Poniższe szczegóły warunków zaliczenia dotyczą WYłąCZNIE grup w których prowadzę zajęcia!

Zaliczenie ćwiczeń

Kolokwium na wykładzie (13 grudnia) i pkty za prace domowe/projekty komputerowe - przy czym projekty komputerowe należy wykonać w domu i zwrócić raport z wynikami i ewentualnym komentarzem w czasie ćwiczeń i na papierze (a nie e-mailem czy w innym terminie). Uwaga! w raportach proszę przede wszystkim zamieścić to o co proszę w treści zadania a nie zbędnych informacji! W przypadkach gdy np raport będzie liczył wiele stron wydruków np listingi programów czy wydruk wartości jakiegoś b długiego wektora mogę odejmować punkty nawet do 50%.
Reklamacje do wyników zadań komputerowych można składać w ciągu 2 tygodni od terminu oddania danego zadania (przy treści będę podawał terminy dla obu grup). A prace domowe będą sprawdzone poprzez 2-3 kartkówki (zapowiedziane) - czyli 2-3 wcześniej zadane zadania domowe czy omówione na ćwiczeniach (ewentualnie lekko zmienione) w ciągu np 30-40 minut. Nie przyjmuję raportów po terminie (chyba że ktoś ma lekarskie usprawiedliwienie). W sumie będzie można dostać (być może odp przeskalowane) 30 pktów z ćwiczeń (pewnie z 60-70% za zad komp) i 30pktów za kolokwium. Zaliczenie od 25 punktów. Dodatkowo dla osób mających kłopoty z zaliczeniem (i TYLKO TAKICH) planuje koło ratunkowe w postaci projektów komputerowych z którego można będzie dostać max 10 punktów , jakkolwiek w sumie z ćwiczeń będzie można dostać albo
Sum=ZK+KA+KO albo min(Sum+PR,25)
czyli projekt wpłynie tylko na zaliczenie ćwiczeń a nie propozycje oceny z egz w I terminie. Projekty będę zadawał indywidualnie w grudniu/styczniu
KA -pkt z kartkówek, ZK - pkty z zad komputerowych, KO - kolokwium, PR - projekt komputerowy

Lista punktów z zadań komputerowych i kartkówek - aktualizowana w miarę na bieżąco. - plik pdf

Treści zadań komputerowych

W treści zadania będzie podane explicite co ma zawierać raport - nie ma potrzeby dodawać kodu czy wydruków różnych pośrednich wyników nie wymaganych np w zad 1 wystarczy podać norme max odpowiedniego wektora a nie drukować elementy tego wektora (co wręcz jest niewskazane w tym przypadku).
  1. Arytmetyka FL Obliczyć wartość wielomianu (x+2)6 na siatce równoodległej ze 101 punktami na przedziale [-2+ 3e-4, -2-3e-4] dwoma algorytmami - pierwszym takim wprost z rozwinięcia w bazie potęgowej tzn licząc kolejno x6 +12x5+ ... +64 i drugim obliczając x=x+2 i potem x6. Dostaniemy dwa wektory x1 i x2 obliczonych wartości obu algorytmami i obliczyć wektor y=(x1-x2)/m2 dla m2=max_k |x2[k]| czyli norma max od x2. Policzyć normę maksimum y oraz (to opcjonalnie ale zachecam) rysując dwa wykresy wielomianu na tym odcinku (raz obliczonego pierwszym sposobem a raz drugim).
    W raporcie: norma max wektora y i oba wykresy na jednym rysunku (wykresy opcja). Jeśli widać jakąś różnice to wyjaśnic skąd się może ona brać.(23-25/10/07)
  2. Metody nieliniowe Zastosować metodę Newtona do obliczania 1/x bez dzielenia. Zastosować do obliczenia 1/a dla a=2.1 z x_0=0.5 i 1001 z x_0=1e-3 - zbadać eksperymentalnie czy mamy zbieżność kwadratową tzn liczyć e_{n+1}/(e_n*e_n) dla kolejnych n (e_n=|x_n-1/a|).
    W raporcie: błędy |e_n| i |e_{n+1}/(e_n*e_n)| dla kolejnych n - za warunek stopu |1-x_n*a| < 1e-10*|x0| lub |x_{n+1}-x_n| < 1e-10 lub ilość iteracji przekroczy 30. (obliczenia w arytmetyce podwójnej precyzji) (gr wtorkowa: 6/11/2007 i gr czwartkowa: 8/11/07)
  3. Interpolacja Lagrange'a Zastosować metodę Newtona obliczania wielomianu interpolacyjnego aby obliczyć współczynniki w bazie Newtona wielomianów interpolacyjnych L_N f_j dla węzłów równoodległych x_k =k*10/N dla k=0,..,N odp. stopnia N=5 i 20 interpolujących odpowiednio gładką funkcje f_1 (x)=1/(1+(x-5)2) i tylko ciągłą f_2 (x)=|x-5|)na odcinku [0,10].
    W raporcie: Współczynniki wielomianów interpolacyjnych ale tylko dla N=5 oraz dwie tabele: Podać w pierwszej tabeli (2x2): błędy w przybliżonej normie max na siatce y_k=k*0.01 k=0,..,1000 tzn max_k |f_j(y_k) -L_N f_j(y_k)| dla obu f_j i N=5,20
    W drugiej tabeli (2x2): różnice w węzłąch interpolacji tzn podać max_{k=0,..,N} |f_j(x_k) -L_N f_j(x_k)| dla obu f_j i N=5,20. W którym przypadku wyniki sugerują zbieżność L_N f_j do f_j? Opcjonalnie 2 rysunki: wykresy funkcji f_k i obu wielomianów L_5 f_k i L_20 f_k na 1 rysunku. (gr wtorkowa: 20/11/2007 i gr czwartkowa: 22/11/07)
  4. Interpolacja Lagrange'a - optymalne węzły interpolacji (zachęcam - treśc to właściwie zadanie poprzednie tylko w części z nowymi węzłami) Zastosować jakkąkolwiek metode obliczania wielomianu interpolacyjnego aby obliczyć współczynniki wielomianów interpolacyjnych L_N f_j dla węzłów równoodległych x_k =k*10/N i węzłów Czebyszewa x_k=5+5*cos(\Pi*(1+2k)/(2N+2)) dla k=0,..,N dla N=20, interpolujących odpowiednio gładką funkcje f(x)=1/(1+(x-5)2))na odcinku [0,10].
    W raporcie: Dwie liczby: Błędy w przybliżonej normie max na siatce y_k=k*0.01 k=0,..,1000 tzn max_k |f(y_k) -L_N f(y_k)| dla f i N=20 i obu typów węzłów W którym przypadku wyniki sugerują zbieżność L_N f do f? Opcjonalnie 2 rysunki: wykresy funkcji f i odpowiedniego wielomianów interpolacyjnego. (gr wtorkowa: 4/12/2007 i gr czwartkowa:6/12/07)
  5. Kwadratury Złożona kwadratura Simpsona - badanie rzędu (eksperymentalne)
    S(a,b,N,f)= -złożona kwadratura Simpsona na podziale odcinka [a,b] na N równoodległych poodcinków i wartościach funkcji f w środkach i końcach tych poodcinkach, I(f) -całka oda a do b z f, E(N,f)=|I(f)- S(a,b,N,f)|. Przetestować tę kwadraturę dla N=8,16,32,64,128 i funckji f1(x)=|x-1/3| na [0,1] oraz f2(x)=sin(x) na [0,\pi]. W raporcie: Dwie tabelki 3 kolumnowe dla obu funkcji: w pierwszej N - ilość punktów dla powyższych N; w drugiej błąd E(N,f)(znamy dokł wartość całki), w trzeciej stosunek błedu E(N/2,f)/E(N,f) - oczywiście dla N=8 to pole puste). (gr wtorkowa: 18/12/2007 i gr czwartkowa:20/12/07)
  6. Aproksymacja średniokwadratowa Znaleźć a i b takie że dla zadanych par p-tów (x_i,y_i) mamy \sum_i |x_i||a+b*x_i-y_i|^2=\min_{c,d} |x_i| |c+d*x_i-y_i|^2.
    Zastosować do x_i=i*h dla h=0.1 i i=1,..,10 i y_i=2+x+0.5*sin(x_i). W raporcie: Obliczone a i b oraz błędy: pierwiastek kwadratowy z (\sum_i |x_i||a+b*x_i-y_i|^2) oraz max_i |a+b*x_i-y_i|=|a+b*x_k -y_k| - podać też k tzn indeks w którym max jest osiągnięte.
    Opcjonalnie wykres punktów (x_i,y_i) i prosta y=a+b*x.
    (gr wtorkowa: 22/01/2008 i gr czwartkowa: 24/01/2008)
Projekt komputerowy: zaprogramować w arytmetyce podwójnej precyzji rozkład QR (a właściwie Q[R^T 0]^T) macierz prostokątnej A MxN (M>=N) kolumnami regularną z Q ortogonalną będącą iloczynem odp. przeksz. Housholdera MXM a R górnotrójkątna NxN z niezerowymi elementami na diagonali metodą Housholdera. Program ma wykryć czy macierz kolumnami regularna tzn jeśli norma kolejnej odpowiedniej podkolumny będzie mniejsza od ustalonego \eps=10-12 to program ma przerwać działanie z komunikatem "Uwaga!kolumny A liniowo zależne w fl". Testować na podmacierzach macierzy Vandermonde'a dla równoodległych węzłów na odcinku [0,1] tzn dla ustalonego m i n zdefiniować węzły xk=(k-1)*h, k=1,..,m+1; h=1/m i macierz (m+1)x(n+1) A(m,n) definiujemy tak aby element na pozycji (i,j) był równy Ai,j= xi(j-1) i=1,..,m+1; j=1,..,n+1. Znaleźć rozkład QR tej macierzy - i zastosować do rozwiązywania LZNK z A(m,n) i odp. wektorem prawej strony f: - dla m=30 i n=2,8,15,30 znaleźć rozkład QR. Zastosować do LZNK z macierzą A i prawą stroną f=Ax z x wektorem długości n+1 takim żę xk=(-1)k, k=1,..,n+1 (czyli f należy obliczyć!) Program powinien mieć opcję wprowadzania macierzy A i wektora f ręcznie z klawiatury, oraz wypisania na ekran macierzy R i wektorów Housholdera dla odp. przekształceń Housholdera i rozwiążania LZNK.
Drukować na ekranie: normę Frobeniusa: ||Q[R^T 0]^T - A(m,n)||F (czyli sprawdzić czy QR =A(m,n)) oraz ||f-Ay||/( ||A||F*||x||) oraz ||x-y||/||x|| dla y- rozwiązania obliczonego przy wykorzystaniu rozkładu QR macierzy A(m,n) || || - norma euklidesowa (druga), || ||F - norma Frobeniusa. Państwa program ma być w Pascalu lub C i kompilować się i działać w labie studenckim - należy mi go okazać przed I terminem egzaminu pisemnego (lepiej nie za późno) wykazując się znajomościa algorytmu i szczegółów programu tzn mogę poprosić o wprowadzenie jakiejś drobnej zmiany w programie w czasie zaliczania. przypominam że punkty z projektu (max 10p) mogą najwyżej podnieść ilość pktów z ćwiczeń do 25p.


Metody numeryczne

Uwaga! Egzamin pisemny - test! Wyniki kartkówki plik pdf (3 strona)

ćwiczenia - 1 grupa - piątek 1015-1145 sala 4070 do wykładu Metody Numeryczne - dr Piotra Krzyżanowskiego

Warunki zaliczenia

Kolokwium na wykładzie (30pktów) + 2 kartkówki z zadań domowych (30pkt) - zaliczenie od 25 punktów;
Dla osób mających kłopoty z zaliczeniem (i tylko takowych) - koło ratunkowe - projekt komputerowy za max 10 pktów i wtedy ilośc punktów z ćwiczeń to max(min(kol+kart+proj,25),kol+kart) czyli punkty z projektu mogą co najwyżej pomóc zaliczyć ćwiczen szczegóły strona do zajęć
Ostatnia aktualizacja: 10 kwietnia 2008