Semestr zimowy 2006/07

Matematyka obliczeniowa

Wykład

1. Wstęp - czym jest matematyka obliczeniowa
2. Arytmetyka zmiennopozycyjnej - fl - podstawowe wiadomości (5-10-2006) w tym definicje uwarunkowania względnego zadania i numerycznej poprawności algorytmu
3. Interpolacja wielomianowa Lagrange'a : istnienie i jednoznaczność rozwiązania, postać w bazie Lagrange'a (12-10-2006) i bazie Newtona w tym metoda Newtona i algorytm różnic dzielonych znajdowania wiel. interp. Lagrange'a, błąd interpolacji przy maksymalnej regularności funkcji (19-10-2006) 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 (opcja) - 2 wykłady
4. Interpolacja Hermite'a - postawienie zadania, istnienie i jednoznaczność wielomainu interpolacyjnego Hermite'a, uogólnione różnice dzielone, postać wielomianu Hermite'a z wykorzystaniem różnic dzielonych, błąd interpolacji Hermite'a (bez dowodu) - 0.5-1 wykład (26-10-2006)
5. Kwadratury - przybliżone obliczanie całek i wielomiany ortogonalne- rząd kwadratury, kwadratury interpolacyjne, 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, (2-11-2006), wielomiany ortogonane w przestrzeniach typu L²_g(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 (9-11-2006) (16-11-2006 - kolokwium w czasie wykładu!)
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 - 0.5-1 wykład
7. Interpolacja splajnowa - splany liniowe interpolacyjne (23-11-2006) i kubiczne w tym baza splajnow kubicznych, oszacowania błędu w normie L²
8. Aproksymacja w przestrzeniach z iloczynem skalarnym - definicja elementu najlepszej aproksymacji (ENA) w dowlnej p. unormowanej, tw o istnieniu z przykładem że może nie być jednoznaczności, (30-11-2006), aproksymacja w p. z iloczynem skalarnym: ENA to rzut ortogonalny wyznaczony jednoznacznie, układ z macierzą Gramma, baza ortogonalna - ortogonalizacja Gramma-Schmidta, wielomiany ortogonalne w przestrzeniach typu L² dokończenie- reguła trójczłonowa, (7-12-2006) regularne liniowe zadanie najmniejszych kwadratów (RLZNK), układ równań normalnych jako szczególny przypadek aproksymacji w przestrzeni unitarnej: rozkłady QR (przekształcenie Housholdera i ortogonalizacja Gramma-Schmidta w Rⁿ) i ich zastosowanie do rozwiązywania RLZNK (14-12-2006)
9. Aproksymacja jednostajna (krótka informacja) - zadanie, twierdzenie Czebyszewa o alternansie, jednoznaczność, związek z intepolacją Lagrange'a w węzłach Czebyszewa (tj odpowiednio przeskalowanch zerach odp. wielomianów Czebyszewa)
10. 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 (21-12-2006)(4-01-2007 - kolokwium w czasie wykładu!) 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, (11-01-2007) jak obliczyć wyznacznik(to na ćwiczenia), uwarunkowanie zadania, informacja o własnościach numerycznych (fl) rozkładu LU
11. Metody rozwiązywania równań nieliniowych (skalarnych) - metoda iteracji prostych (Banachowskich), metoda bisekcji, (18-01-2007) metoda Newtona. Rząd zbieżności metody. Zbieżność m Newtona kwadratowa (lokalna) i globalana dla funkcji wypukłej rosnącej. Metoda siecznych i jej zbieżność lokalna. (25-01-2007)

Warunki zaliczenia ćwiczeń:

Literatura:

• [KC2006] D.Kincaid, W.Cheney, Analiza numeryczna, WNT, 2006
• [Mos2002] Krzysztof Moszyński, Metody numeryczne dla informatyków, skrypt, plik ps, 2002
• [Pla2002] Leszek Plaskota, Dwanaście wykładów z matematyki obliczeniowej, skrypt, plik pdf, 2002
• [DJ1982] Maksymilian Dryja, Janina i Michal Jankowscy, Metody numeryczne, WNT, 1982.
• [FMW2005] Z. Fortuna, B. Macukow, J. Wasowski, Metody numeryczne , WNT, 2005. Wydanie 7.

Inne użyteczne linki

• Lloyd N.Trefethen, Numerical analysis (The Princeton Companion to Mathematics, Princeton University press, ukaże się w 2007) plik pdf
• Lloyd N.Trefethen, The definition of numerical analysis, (SIAM News, Nov 1992) zgzipowany poscript.

Ćwiczenia

1. Gr 1 środa 830-10 - sala 1010
2. Gr 3 środa 1015-1145 - sala 3240

Zaliczenie ćwiczeń

Treści zadań komputerowych

1. Arytmetyka FL Obliczyć wartość wielomianu x⁴-4x³ +6x²-4x+1 na siatce równoodległej ze 101 punktami na przedziale [1+ 3e-4, 1-3e-4] dwoma algorytmami - pierwszym takim wprost i drugim obliczając (x-1)*(x-1)*(x-1)*(x-1). Porównać wyniki licząc maksimum z modułów różnicy na tej siatce oraz (to opcjonalnie ale zachecam) rysując dwa wykresy wielomianu na tym odcinku (raz obliczonego pierwszym sposobem a raz drugim). W raporcie max sumy modułów na siatce i oba wykresy na jednym rysunku (wykresy opcja). Jeśli widać jakąś różnice to wyjaśnic skąd się może ona brać. (25-10-2006)
2. Algorytm znajdowania wielomianu interpolacyjnego Lagrange'a Policzyć współczynniki wielomianu interpolacyjnego Lagrange'a w(x) w bazie Newtona na siatce równoodległej {-1,0,1,2} dla funkcji f(x)=sin(x) rozwiązując układ równań z macierzą dolnotrójkątna w bazie Newtona czy metoda Newtona (albo algorytmem różnic dzielonych - do wyboru). W raporcie współczynniki obliczonego wielomianu w bazie Newtona (kolejność p-któw ważna!), policzyć i wydrukowac max_k=-1,0,1,2|w(k)-sin(k)| czyli jak dokładnie spełnione są warunki interpolacyjne, podac arytmetyke (single/double) oraz wykresy sin(x) i w(x) na odcinku [-1.5, 2.5] (jak ktoś ma kłopoty z drukowaniem niech naszkicuje - w(x) to wielomian co najwyżej 3 stopnia). (15 listopada 2006)
3. Błąd interpolacji Lagrange'a Policzyć współczynniki wielomianu interpolacyjnego Lagrange'a w(x) na siatce równoodległej na odcinku [-5,5] dla N=10,20,40 tzn w(x(k))=f(x(k)) dla k=0,..,N gdzie x(k)=-5+k*h i h=10/N , dla funkcji f(x)=1/(1+x*x) jakkolwiek np. metoda Newtona czyli rozwiazując układ równań z macierzą dolnotrójkatną w bazie Newtona - następnie policzyć przybliżoną normę supremum na siatce z h=1/500 tzn max_k=0,..,500|w(y(k))-f(y(k))|, gdzie y(k)=-5+ k/50 i k=0,..,500.
   W raporcie: sprawdzenie czy warunki interpolacyjne są spełnione tzn policzyć max_k=0,..,N|w(x(k))-f(x(k))| i wydrukować wyniki, oraz przybliżone normy sup dla wszystkich trzech N oraz (opcja) wykresy funkcji i wszystkich trzech wielomianow interpolacyjnych. Czy przybliżone normy supremum różnicy w-f maleją lub są chociaż mniejsze od 1? Czy wyniki są zgodne z oszacowaniami z wykładu dla węzłów równoodległych? (29 listopada 2006)
4. Kwadratury złożone Zaimplementować złożoną kwadrature prostokątów tzn P_N f = \Suma_k=0,..,N-1 f(x_k+h/2)*h dla h=(b-a)/N i x_k=a+k*h, przybliżającą I(f) - całkę z f na [a,b]. Przetestować dla funkcji sin(x) na [0,Pi] dla N=10,20,40,80,160.
   W raporcie: W tabelce nr 1 (dla sin) w trzech kolumnach |I(sin)- P_N sin|*N^k dla k=0,1,2 dla kolejnych N. Czy wyniki potwierdzają oszacowania teoretyczne z ćwiczeń? (tzn dla f w C² błąd powinien być jak O(h²)) (13 grudnia 2006)
5. Aproksymacja średniokwadratowa
Dla węzłów x_k=k - k=1,2,..,10 znaleźć stałe a i b takie że \sum_k k*|f(x_k)-ax_k-b|^2 (Uwaga na wagę!!) osiąga minimum dla funkcji f(x)=2+3*x+ 1e-3*sin(x) (1e-3=0.001). W raporcie a i b oraz bład err2=pierwiastek(\sum_k k*|f(x_k)-ax_k-b|^2) oraz errm=max_k |f(x_k)-ax_k-b| i podać dla jakiego k errm=|f(x_k)-ax_k-b|. (10 stycznia 2007)
6. Liniowe zadania najmniejszych kwadratów. Dla macierzy A=((1 2 3 ... 99 100)^T; (1 1 ... 1)^T) - 100x2 tzn dwukolumnowej i f=(sin(1) sin(2) .. sin(100))^T - 100x1 - znaleźć rozkład A=QB dla Q=H1*H2 - iloczyn 2 p. Housholdera B=(R^T 0)^T (czyli macierz 100x2 - pierwsze 2 wiersze to R - macierz 2x2 górnotrójkątna a pozostałe równe zero) - zastosować do znalezienia rozwiązania.LZNK z A i f w arytmetyce podwójnej precyzji.
   W raporcie: podać macierz R, i 4 pierwszych pozycji 4 wektorów: dwu wektorów Housholdera dla H1 i H2 (unormowanych tzn o normie 2 rownej jeden), wektora Q^T*f, oraz wektora - x rozwiązania tego LZNK tzn np. x1=(y1,y2,y3,...,y100)^T a w raporcie (y1 y2 ..y4) oraz błędy: ||H1*H2*B - A||_F, i ||A x -f||₂. (Uwaga! Oczywiście nie należy tworzyć macierzy H1, H2, Q czy C=Q*B czyli obliczać iloczynów macierzy Q=H1*H2 czy Q*B ale obliczyć działanie H2 na kolumnach B (a może wystarczy drugiej kolumnie?) aby dostać C=H2*B a potem H1 na 2 kolumnach C aby dostać Q*B!). (24 stycznia 2007)