Semestr zimowy 2004/05

1. Matematyka Obliczeniowa  (ćwiczenia do wykładu  dr P.Krzyżanowskiego)
2. Metody numeryczne (ćwiczenia do wykładu   prof. K. Moszyński.)
   

lmarcin at mimuw.edu.pl, pok.1020 (na parterze koło biblioteki). Należy też sprawdzić: Plan.

Literatura:

• D.Kincaid, W.Cheney, Numerical Analysis, 2gie wyd., Brooks/Cole, 1996 (podstawa wykładu)
  
• N.Trefethen, The definition of numerical analysis, zgzipowany poscript.
• Å.Bjorck, G.Dahlquist, Metody numeryczne, PWN, 1987
• K.Moszyński, Metody numeryczne dla informatyków, skrypt, plik ps, 2002
• L.Plaskota,  Dwanaście wykładów z matematyki obliczeniowej, skrypt, plik pdf, 2002
• M.Dryja, J.M.Jankowscy, Metody numeryczne, WNT, 1982

1. Zaprogramować metodę Newtona skalarną. Testować dla problemu f(x)=x*x- a dla różnych a np. a=0.25,2,4,121 i przybliżeń początkowych x0.  W szczególności dla jednego a np a=4 wziąść x0 bliskie zeru, równe a i 10^5. W raporcie podać czy i w ilu iteracjach metoda zbiega (podając zarówno a jak i  x0) - przy ustalonym kryterium stopu np. |f(xn)/f(x0)|<1e-4=10^-4 albo |xn-x*|/|x0-x*|< 1e-4=10^-4 które oczywiście daje się zastosować o ile znamy x* czyli tylko do testowania metody a nie w praktyce. Oraz dla wybranych danych a i x0 przetestować czy zbieżność jest kwadratowa tzn drukować e(n)=|xn-sqrt(a)| i stosunek  e(n+1)/e(n)^p dla p=1,2,3.  Opracowanie testów jest istotną częścią zadania. Powodzenia. Termin 25.X.2004.
2. Zaprogramować fukcje obliczającą exp(x) dla dowolnego x z [-10,10] z zadaną dokładnością eps tzn dla danego eps obliczać S_N(x) =sum_{n=1}^N x^n/n! dla N=N(x) takiego aby mieć zapewnione: |exp(x) -S_N|<eps . (Musicie państwo m.in. sami oszacować ile elementów z szeregu potęgowego tzn jakie N   należy wziąść dla danego x aby błąd był odpowiednio mały). porównywać z wynikiem obliczonym poprzez funkcje standardowa Pascala C C++ czy pakietu typu scilab, matlab, octave. W raporcie podać tabelkę dla eps=10^{-10} z N(x) i z błędami względnymi dla różnych x z danego przedziału  tzn jeśli s - obliczony wynik, exp(x) to co daje biblioteka matematyczna np w Pascalu czy C, C++ to drukować |S_N(x)- exp(x)| i N  dla x_k=-10 + k*0.5, k=0,...,40.  Czyli wierszu tabelki: x_k, N(x_k), |S_N(x_k)-exp(x_k)|. Wyniki przeprowadzić w precyzji pojedyńczej (opcjonalnie  dla chętnych można porównać z wynikami w precyzji podwójnej)  Skomentować wyniki.  15/XI/2004
3. Zaprogramować metode obliczania kosztem O(n) rozkładu macierzy A=LU dla A=(a_{ij})i,j=1..n macierzy nxn takiej że: a_ij=0 |i-j|>1 a_ii=2, a_{i,i+1}=a_{i+1,i}=-1  i<n która jest symetryczna i dodatnio określona (i trójdiagonalna). Testować  rozwiązując układ równań z tą macierzą    i znanym wylosowanym  rozwiązaniem dla n=10,50,100,500,1000 tzn dla danego n wylosować x wektor w Rⁿ, unormować ten wektor  (tzn obliczyć x= x/||x||) obliczyć b=Ax i rozwiązać układ równań Ax=b - dostajemy x* - obliczone przybliżone rozwiązanie.  W raporcie podać 1 tabelke:w wierszu tabelki podac: n, ||x- x^*||, ||b - Ax*||, dla || x||²=x^Tx - normy euklidesowej (można użyc jakiejś innej normy np normy max lub pierwszej). Skomentować wyniki - tzn czy rząd wielkości błedu (2 kolumna) i błedu residualnego (3 kolumna) są  różne? jeśli tak to dlaczego? Uzasadnić 1-2 zdaniami.  29/XI/2004
4. Zaprogramować metodę obliczania stałej c t. że E(a,c)= suma_j=1ⁿ  | c*j- f(j)|^2 jest minimalna (f(j) stałe ustalone). Przetestować dla f(j)=1,  f(j)=j i f(j)=j^2 dla n=6.  Wyniki podać w formie tabelki drukując wartości tych stałych oraz bład E(a,c) dla odpowiednch f(j) oraz  rysując wykresy z pktami (j,f(j)) j=1,..,6 i (j,c*j).  (napisać 1-2 zdaniami jaką metodą Państwo tą stałą obliczali). 20/XII/2004
5. Napisać program który oblicza wielomian interpolujący zadaną funkcję f w 2 punktach: 0 i 1 z podwójną krotnością w 0 i pojedyńczą w 1, tzn tak że wielomian w który otrzymamy spełnia w (i)= f(i), i=0,1; i w'(0)=f' (0) . Jako raport: na jednym obrazie wykres cos(4*x) i w dla tej funkcji na odcinku [-1,2] (y w zakresie [-2,2]). Zaznaczyć który wykres jest wiel. interp. a który funkcji.  (napisać 1 zdaniem jaką metodą Państwo ten wielomian obliczali) 17/I/2005
6. Zadanie dodatkowe (10pkt) - nie liczy się do sumy pktów. Interpolacja Lagrange'a na dowolnym  [a,b] i węzłach dowolnych, przy czym testować w szczególności dla węzłów równodległych i węzłów Czebyszewa dla funkcji 1/(1+x*x) na odcinku [-5,5] i log(1+x) na [0, 8] (więć oczywiście musi być opcja generowania węzłów automatycznie tzn bez podawania ich z klawiatury). Jako raport wykresy  funkcji i wielomianów  interpolacyjnych na obu rodzajach węzłów tzn wykresy  f, L_n.czf  (wielomian interpolacyjny na węzłach Czebyszewa) i L_n,ro f (wiel. interpolacyjny na węzłach równoodległych) z węzłami i pktami przecięcia dla n=5,20. (Węzły Czebyszewa to zera n-tego wielomianu Czebyszewa T _n  odpowiednio przesunięte i przeskalowane - n-ty wielomian Czebyszewa na [-1,1] jest zdefiniowany jako T_n(x)=cos(n*arccos(x))  ma dokładnie n różnych zer : -1<x _i<1, które z tego wzoru od razu dają się policzyć).  Termin 17/I/2005

• pierwsze 17 listopada 2004 (śr) i 18 listopada  2004 (czw) - zakres : wszystko co było na ćwiczeniach przed kolokwium - normy wektorowe, macierzowe, interpolacja Lagrange'a/Hermite'a  - algorytmy szukania wiel. interp + błąd przy różnych założeniach co do regularności funkcji, interpolacja f. kawałkami wielomianowymi + oszacowanie błędu, interpolacja zespolona - dyskretna transformata Fouriera,
  
• drugie 12 stycznia 2004(śr)  - aproksymacja średniokwadratowa, LZNK , wielomiany Czebyszewa, optymalne ze względu na oszacowanie błędu węzły interpolacji, metody iteracyjne rozwiązywania równań liniowych (Richarson, Czebyszewa, gradientowe),  kwadratury (coś prostego o ile zdążymy coś powiedzieć na ćwiczeniach w styczniu). Można mieć ze sobą obustronnie zapisaną kartkę formatu A4.
  

1. Interpolacja Lagrange'a na dowolnym  [a,b] i węzłach dowolnych, przy czym testować w szczególności dla węzłów równodległych i węzłów Czebyszewa dla funkcji 1/(1+x*x) na odcinku [-5,5] i sin(x) na [0, 2Pi] (więć oczywiście musi być opcja generowania węzłów automatycznie tzn bez podawania ich z klawiatury). Rysować na ekranie funkcję i wielomian interpolacyjny z węzłami i pktami przecięcia . (Węzły Czebyszewa to zera n-tego wielomianu Czebyszewa T _n  odpowiednio przesunięte i przeskalowane - n-ty wielomian Czebyszewa na [-1,1] jest zdefiniowany, jako T_n(x)=cos(n*arccos(x))  ma dokładnie n różnych zer : -1<x _i<1, które z tego wzoru od razu dają się policzyć). Rysowanie na ekranie może być za pomocą jakiegoś narzędzia np gnuplota pod linuxem.  (Czyli zgrać wyniki do pliku i gnuplotem wyświetlić.)
2. Kwadratury trapezów i Simpsona (parabol) złożone na równoodległych pododcinkach: testować funkcje różnej gładkości na  [0,1] dla których całka jest znana np sin(x), wielomiany niskich stopni np 1,2 czy x ^p , p=k/2 k=1,2,3,4,5 itd, testować dla  h,h/2,h/4,h/8 dla h = 0.1 (h= 1/N gdzie N - ilość węzłów), porównywać błąd.Tzn obliczać całkę dla zadanego h i drukować błąd między przybliżoną wartością całki a dokładna całką którą dla funkcji całkowych możemy obliczyć tzn I(f) - całka, Q_h(f)=T_h(f) - złożona kwadratura trapezów lub Q_h(f)=S_h(f) - złożona kwadratura Simpsona  (inaczej kwadratura Parabol) na N równych odcinkach długości h.  Wypisywać na ekranie: e(h)=|I(f) - Q_h(f)| oraz e(2h)/e(h). Skomentować wynik.  (Wzory na obie kwadratury złożone oraz na błąd można znaleźć w większości książek o metodach numerycznych zob. §9.3, str 103 -( błąd Tw. 9.4 tamże), w skrypcie: L. Plaskota Dwanaście wykładów z matematyki obliczeniowe, plik pdf, 2002, lub inne książki por. literatura uzupełniająca.