1. Jakie zadanie obliczeniowe nazywamy źle uwarunkowanym?
Kiedy mały błąd reprezentacji danych wejściowych powoduje duży błąd wyniku.
2. Opisz, co oznacza wskaźnik uwarunkowania?
Wskaźnik 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 okresowych
10. Podaj znane Ci metody wyznaczania wielomianu interpolacyjnego stopnia n przechodzącego przez n+1 zadanych węzłów.
Metody: Lagrange’a, Newtona, Aitkena
11. Wyjaśnij, na czym polega aproksymacja średniokwadratowa.
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 ∫ab(f(x)−P(x))2dx miała możliwie małą wartość.
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.
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. Wyprowadź wzór skalarnej metody siecznych.
$\frac{f(x_{0})}{x_{2} - x_{0}} = \frac{f\left( x_{1} \right)}{x_{2} - x_{1}}$ ->$x_{2} = \frac{f\left( x_{0} \right)x_{1} - f(x_{1})x_{0}}{f\left( x_{0} \right) - f(x_{1})}$->$x_{2} = \frac{f\left( x_{0} \right)x_{1} - f\left( x_{1} \right)x_{1} + f\left( x_{1} \right)x_{1} - f(x_{1})x_{0}}{f\left( x_{0} \right) - f(x_{1})}$->$x_{2} = x_{1} - \frac{x_{0} - x_{1}}{f\left( x_{0} \right) - f(x_{1})}*f(x_{1})$
20. Wyprowadź wzór skalarnej metody stycznych.
y = f′(xk)x + b->f(xk) = f′(xk)xk + b->b = f(xk) − f′(xk)xk->y = f′(xk)x + f(xk) − f′(xk)xk->0 = f′(xk)xk + 1 + f(xk) − f′(xk)xk->$\mathbf{x}_{\mathbf{k}\mathbf{+}\mathbf{1}}\mathbf{=}\mathbf{x}_{\mathbf{k}}\mathbf{-}\frac{\mathbf{f}\mathbf{(}\mathbf{x}_{\mathbf{k}}\mathbf{)}}{\mathbf{f}^{\mathbf{'}}\mathbf{(}\mathbf{x}_{\mathbf{k}}\mathbf{)}}$
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−x2), 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 $\frac{1}{\sqrt{1 - x^{2}}}$), jako argument funkcji przyjmujemy pierwiastki wielomianu Czebyszewa
26. Na czym polegają kwadratury Newtona-Cotesa?
Polegają na przybliżeniu funkcji podcałkowej za pomocą wielomianu określonego stopnia, gdzie ∫abf(x)dx ≈ ∫abLn(x)dx, Ln(x)-wielomian interpolacyjny 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).
Kwadratury Gaussa konstruuje się za pomocą wzoru : $\int_{a}^{b}{f(x)dx} \approx \sum_{i = 0}^{n}{A_{i} \cdot f(x_{i})}$ gdzie $A_{i} = \int_{a}^{b}{p(x) \cdot \prod_{j = 0;j \neq i}^{n}\frac{x\ - \ x_{j}}{x_{i}\ - \ x_{j}}}dx,$ p(x) jest zależne od rodzaju użytej metody 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.
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 charakterystycznego macierzy.
Obliczenie macierzy odwrotnej do podanej. (dzięki twierdzeniu Hamiltona).
31. W jaki sposób znaleźć 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 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ą.
32. W jaki sposób znaleźć najmniejszą, co do modułu, wartość własną macierzy rzeczywistej korzystając z metody potęgowej?
Na początku należy wybrać nie zerowy wektor np. v0= [1,0,0,…,n] (n to rozmiar danej w zadaniu macierzy)oraz odwrócić daną w poleceniu macierz. Następnie mnożymy odwróconą macierz przez wektor v0. 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.