1
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 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.
2
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
∫ f x P x
a
b
dx 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.
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
3
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. Wyprowadź wzór skalarnej metody siecznych.
->
->
->
20. Wyprowadź wzór skalarnej metody stycznych.
->
->
->
-
>
->
4
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 LL
T
.
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?
5
Polegają na przybliżeniu funkcji podcałkowej za pomocą wielomianu
określonego stopnia, gdzie ∫
b
a
f x dx ∫
b
a
Ln x dx,Ln(x)-wielomian interpolacyjny
Lagrange’a funkcji f oparty na równoległych węzłach x
k
= 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 : ∫
b
a
f x dx ∑
n
i
A
i
f x
i
gdzie Ai = ∫
b
a
p x ∏
n
j j i
x x
j
x
i
x
j
dxp(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.
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 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
6
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 znaleźć 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
-1
AP, 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.
7