1. Jakie zadanie obliczeniowe nazywamy zle uwarunkowanym? Kiedy mały błąd reprezentacji danych wejściowych powoduje duży błąd wyniku. 2. Opisz, co oznacza wskaznik uwarunkowania? Wskaznik uwarunkowania oznacza jak błąd reprezentacji danych wejściowych wpływa na błąd wyniku. Im większy współczynnik uwarunkowania tym gorzej uwarunkowane zadanie. 3. Co powoduje powstawanie tak zwanego błędu numerycznego ? Zaokrąglanie, ucinanie końcówek, niedokładny odczyt pomiarów. 4. Jaki algorytm nazywamy stabilnym względem błędu numerycznego? Błąd popełniony w jednym z kroków nie zwiększa się w kolejnych krokach lub pozostaje tego samego rzędu. 5. Wyjaśnij, na czym polega metoda kolejnych przybliżeń (iteracji). Metoda kolejnych przybliżeń polega na stworzeniu ciągu zbieżnego do rozwiązania poprzez wyliczanie kolejnych wyrazów tego ciągu zwanych przybliżeniami lub iteracjami właśnie. 6. Co to jest warunek stopu w metodach iteracyjnych podaj przykłady. Warunek stopu to różnica pomiędzy wynikami kolejnych iteracji. Kiedy jest odpowiednio mała, przestajemy liczyć dalej. 7. Opisz zastosowania schematu Hornera. Mnożenie i dzielenie wielomianów używając jak najmniej mnożeń. 8. Do czego służy algorytm Herona opisz go. Do obliczania wartości pierwiastka kwadratowego. Jest to algorytm iteracyjny, który z każdą kolejną iteracją podaje coraz dokładniejszą wartość liczonego pierwiastka. Metoda Herona służy do przybliżenia pierwiastka kwadratowego danej liczby. Polega ona na wyznaczaniu połowy odległości między wartością z poprzedniej iteracji, a ilorazem danej liczby i wartości z poprzedniej iteracji. 9. Podaj omawiane na wykładzie metody interpolacji. Krótko opisz, na czym każda z nich polega. a) interpolacja wielomianowa przybliżanie funkcji za pomocą wielomianu b) interpolacja sklejona dzielimy przedział na mniejsze przedziały i w każdym z nich interpolujemy funkcję wielomianem niskiego stopnia, a potem sklejamy to wszystko razem c) interpolacja trygonometryczna przybliżanie funkcji za pomocą wielomianu trygonometrycznego (szereg Fouriera). Dobre dla funkcji kwadratowych 10. Podaj znane Ci metody wyznaczania wielomianu interpolacyjnego stopnia n przechodzącego przezn+1 zadanych węzłów. Metody: Lagrange a, Newtona, Aitkena 11. Wyjaśnij, na czym polega aproksymacja średniokwadratowa. 1 Przybliżenie średniokwadratowe zadanej funkcji f(x) funkcją P(x) to takie dla którego odległość średniokwadratowa f(x) i P(x) jest najmniejsza. Szukamy takie P(x) aby całka a f x P x dx miała możliwie małą wartość. +"b 12. Wyjaśnij, do czego służy i na czym polega metoda najmniejszych kwadratów. Metoda najmniejszych kwadratów służy do liczenia regresji liniowej. Metoda polega na liczeniu układu równań nadokreślonego. Nazwa pochodzi od tego, że końcowe rozwiązanie tą metodą minimalizuje sumę kwadratów błędów przy rozwiązywaniu każdego z równań. 13. Wyjaśnij, czym różni się interpolacja od aproksymacji średniokwadratowej? Interpolacja polega na wyznaczeniu funkcji na tyle dobrze przybliżającej funkcje (wyjściową), której wzoru nie znamy, natomiast znamy punkty przez które ona przechodzi. Aproksymację stosujemy zazwyczaj wtedy, kiedy znamy funkcję wyjściową natomiast wyliczanie wartości funkcji dla szukanych argumentów jest zbyt czasochłonne. 14. Co to są układy wielomianów ortogonalnych? Podaj ich przykład. Wielomiany wzajemnie do siebie ortogonalne w sensie pewnego iloczynu skalarnego. Korzysta się z nich między innymi przy rozwijaniu funkcji w szereg Fouriera i interpolacji wielomianowej przykłady: Czybyszewa, Laguerre a, Legendre a, Hermite a, trygonometryczne 15. Podaj poznane na wykładzie metody rozwiązywania układów równań. Na jakie dwie grupy dzieli się je? Metody dokładne: - Metoda Gaussa-Jordana - Metoda Cholesky ego -Banachiewicza Metody iteracyjne: - Metoda Jakobiego - Metoda Richardsona 16. Opisz zagadnienie wyboru elementu podstawowego w metodzie eliminacji Gaussa. W pierwszym kroku z pierwszej kolumny wybieramy wartość największą i cały wiersz w której ta wartość max się znajduje zamieniamy z pierwszym wierszem. Następnie, już z pominięciem pierwszego wiersza, wybieramy z następnej kolumny wartość max i zamieniamy cały wiersz z wierszem drugim. Ilość takich operacji jest zależna od rozmiaru naszej macierzy. Oczywiście pomiędzy wybieraniem kolejnych elementów podstawowych zerujemy wartości w kolumnie pod wybraną wartością max. Celem tej metody jest pozostawienie na diagonali niezerowych elementów. 17. Opisz różnice między następującymi metodami rozwiązywania równań nieliniowych: a. bisekcji Metoda bisekcji (połowienia, krojenia na pół) polega na dzieleniu zadanego przedziału argumentów na dwie równe połówki. Dokonujemy tego znajdując punkt środkowy przedziału jako średnią arytmetyczną jego krańców. b.stycznych 2 W metodzie stycznych nie określamy przedziału poszukiwań, lecz punkt na osi x dostatecznie blisko pierwiastka funkcji. Następnie znajdujemy prostą styczną do wykresu funkcji w tym punkcie. Prosta ta przecina oś x i wyznacza nam kolejny punkt c.siecznych W algorytmie siecznych, skrajne wartości funkcji ciągłej przychodzącej przez oś OX na zadanym odcinku łączymy prostą. Punkt przecięcia tej prostej z osią OX oznaczamy jako kandydata na pierwiastek. 18. Do czego stosuje się metodę Laguerre'a? Metoda Laguerre a pozwala obliczać miejsca zerowe wielomianów oraz funkcji analitycznych, lokalnie rozwijalnych w szereg potęgowy do wyrazów rzędu n. 19. Wyprowadz wzór skalarnej metody siecznych. -> -> -> 20. Wyprowadz wzór skalarnej metody stycznych. -> -> -> - > -> 3 21. Opisz trzy spośród znanych Ci metod rozwiązywania równań nieliniowych. Jakie są praktyczne różnice w ich zastosowaniu? - Metoda bisekcji (połowienia) Metoda bisekcji (połowienia, krojenia na pół) polega na dzieleniu zadanego przedziału argumentów na dwie równe połówki. Dokonujemy tego znajdując punkt środkowy przedziału jako średnią arytmetyczną jego krańców. - Metoda Newtona W metodzie stycznych nie określamy przedziału poszukiwań, lecz punkt na osi x dostatecznie blisko pierwiastka funkcji. Następnie znajdujemy prostą styczną do wykresu funkcji w tym punkcie. Prosta ta przecina oś x i wyznacza nam kolejny punkt - Metoda Siecznych W algorytmie siecznych, skrajne wartości funkcji ciągłej przychodzącej przez oś OX na zadanym odcinku łączymy prostą. Punkt przecięcia tej prostej z osią OX oznaczamy jako kandydata na pierwiastek. 22. Wymień trzy iteracyjne metody rozwiązywania układów równań (liniowych lub nieliniowych). - Metoda Gaussa-Seidla - Metoda Jakobiego - Metoda Richardsona 23. Jakie poznałeś zastosowania rozkładu LU? -wyznaczanie macierzy odwrotnej do macierzy A -wyznaczenie macierzy L(lower) i U(upper) za pomoca eliminacji Gaussa -wyznaczanie wyznacznika macierzy A -rozwiązywanie układu równań liniowych A*x=b 24. Podaj różnice rozkładu LU oraz rozkładu Cholesky'ego-Banachiewicza LLT. Rozkład LU możemy stosować do dowolnej macierzy kwadratowej, a rozkład Cholesky'ego-Banachiewicza tylko do macierzy symetrycznych i dodatnio określonych 25. Wymień i omów poznane na wykładzie kwadratury. - Gaussa-Hermite'a (waga e^-x^2), jako argument funkcji przyjmujemy pierwiastki wielomianu Hermite a - Gaussa-Laguerre'a(waga e^-x), jako argument funkcji przyjmujemy pierwiastki wielomianu Laguerre'a - Gaussa-Legendre'a(waga 1), jako argument funkcji przyjmujemy pierwiastki wielomianu Legendre'a - Gaussa-Czebyszewa(waga 1/sqrt(1-x^2)), jako argument funkcji przyjmujemy pierwiastki wielomianu Czebyszewa 26. Na czym polegają kwadratury Newtona-Cotesa? 4 Polegają na przybliżeniu funkcji podcałkowej za pomocą wielomianu b b określonego stopnia, gdzie f x dx Ln x dx,Ln(x)-wielomian interpolacyjny +"a +"a Lagrange a funkcji f oparty na równoległych węzłach xk = a + k*h, gdzie h b a n 27. Omów, w jaki sposób konstruuje się kwadratury Gaussa. Polega na optymalizacji położenia n węzłów interpolacyjnych oraz doborze odpowiednich wartości współczynników wagowych (Ai) i wspołrzednych węzłów(Xi). b Kwadratury Gaussa konstruuje się za pomocą wzoru : f x dx "n Ai f xi +"a i b x xj gdzie Ai = p x "n dxp(x) jest zależne od rodzaju użytej metody +"a j j i xi xj Gaussa.Sumuje się współczynniki dla kolejnych węzłów z wartościami funkcji dla tych węzłów. 28. Opisz dwie metody całkowania Monte-Carlo. Metoda Monte Carlo polega na wylosowaniu n punktów znajdujących się w obrębie prostokąta wyznaczonego przez krańcowe odcięte i sieczne przedziału i na tej podstawie obliczenia stosunku pola powierzchni pod krzywą czyli wartości całki do pola wyznaczonego prostokąta. wersja 2: Metoda Monte Carlo I- polega na wylosowaniu n punktów znajdujących się w obrębie prostokąta, który zawiera całkowaną funkcję, i na tej podstawie obliczeniu stosunku liczby wylosowanych punktów które znalazły się pod całkowaną funkcją do liczby wszystkich strzałów , po czym przemnożeniu tego stosunku przez pole wybranego prostokąta. Otrzymana w ten sposób liczba jest przybliżeniem całki zadanej funkcji. Metoda Monte Carlo II polega na wylosowaniu n punktów znajdujących się w obrębie przedziału całkowania i na tej podstawie obliczeniu średniej wartości funkcji w tym przedziale. Następnie wyliczoną wartość należy przemnożyć przez długość przedziału i tak otrzymana liczba jest przybliżeniem całki zadanej funkcji. 29. Co wiesz na temat pojęć: wartość własna, wektor własny oraz równanie charakterystyczne macierzy? Wektor x jest wektorem własnym macierzy A jeśli istnieje taka liczba , że Ax = x. to wartość własna macierzy A. Macierze podobne mają takie same wartości własne. Wektor, który po przeskalowaniu wskazuje ten sam kierunek jest wektorem własnym. Jest to taki szczególny wektor odwzorowania A, który jest odporny na odwzorowanie. 30. W jakich celach stosujemy poznaną na wykładzie metodę Kryłowa? Wyznaczanie wielomianu charaktetystycznego macierzy. Obliczenie macierzy odwrotnej do podanej. (dzięki twierdzeniu Hamiltona). 31. W jaki sposób znalezć największą, co do modułu, wartość własną macierzy rzeczywistej korzystając z metody potęgowej? Załóżmy, że mamy wyznaczoną bazę tej macierzy (złożoną z wektorów własnych). Mnożąc 5 każdy wektor wiele razy przez tę macierz zauważymy i porównując wektor wynikowy z tym wektorem zauważymy, że jeden z wektorów będzie coraz bardziej zbiegał do wektora wyjściowego. Ten wektor zatem jest największą wartością własną. To jest wersja z głowy (Michał Wnenk) : Na początku należy wybrać nie zerowy wektor np. v = [1, , ,& ,n] (n to rozmiar danej w zadaniu macierzy). Następnie mnożymy daną macierz prze wektor v . Przed otrzymany wektor wyciągamy taką liczbę aby jedna z wartości wektora była równa 1,a pozostałe wartości były mniejsze równe 1. Tak otrzymany wektor oraz liczba to odpowiednio wektor własny oraz wartość własna danej macierzy. Aby wyliczyć kolejne wartości i wektory własne należy daną macierz przemnożyć przez poprzednio wyliczony wektor własny. Największa wartość własna danej macierzy to wartość własna wyliczona jako ostatnia (w ostatniej iteracji). 32. W jaki sposób znalezć najmniejszą, co do modułu, wartość własną macierzy rzeczywistej korzystając z metody potęgowej? To jest wersja z głowy (Michał Wnenk) : Na początku należy wybrać nie zerowy wektor np. v = [1, , ,& ,n] (n to rozmiar danej w zadaniu macierzy)oraz odwrócić daną w poleceniu macierz. Następnie mnożymy odwróconą macierz przez wektor v . Przed otrzymany wektor wyciągamy taką liczbę aby jedna z wartości wektora była równa 1,a pozostałe wartości były mniejsze równe 1. Tak otrzymany wektor oraz liczba to odpowiednio wektor własny oraz wartość własna odwróconej macierzy. Aby wyliczyć kolejne wartości i wektory własne należy odwróconą macierz przemnożyć przez poprzednio wyliczony wektor własny. Najmniejsza wartość własna danej macierzy to największa co do modułu wartość własna wyliczona jako ostatnia (w ostatniej iteracji). 33. Jak definiujemy macierze podobne i w jaki sposób wykorzystujemy pojęcie podobieństwa macierzy do szukania wartości własnych macierzy? Macierze A i B są podobne, wtedy kiedy spełnione jest równanie B=P-1AP, gdzie P to macierz nieosobliwa. Macierze podobne mają te same wartości własne. 34. Na czym polega metoda Jacobiego szukania wartości własnych macierzy? Metoda Jacobiego polega na wykonaniu na wyjściowej macierzy ciągu transformacji ortogonalnych, w wyniku których macierz ta zostanie doprowadzona do postaci diagonalnej, w której na głównej przekątnej znajdą się wartości własne macierzy wyjściowej. 35. Na czym polega metoda QR szukania wartości własnych macierzy? Według algorytmu QR każdą macierz A możemy rozłożyć na iloczyn macierzy ortogonalnej Q i macierzy trójkątnej R, którą zapisujemy według schematu A=QR. Gdy macierz A jest nieosobliwa, to poszczególne kolumnach macierzy Q możemy otrzymać dokonując ortogonalizacji macierzy A metodą Grama-Schmidta, wtedy kolumny macierzy R są zbudowane z współczynników rozwiniecie z ortogonalizowanej macierzy A. 6 7