1. Jakie zadanie obliczeniowe nazywamy źle uwarunkowanym?
Zdarza się, że małe zmiany (zaburzenia) danych powodują duże zmiany wyniku zadania
obliczeniowego. Uwarunkowanie zadania zależy od konkretnych liczb w zadaniu.
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 postawanie tak zwanego „błędu numerycznego”?
Powstaje on z powodu niedokładnego odczytania pomiarów, zaokrąglenia i ucinania. Przy
setkach różnych obliczeń błędy te kumulują się i mogą mieć decydujący wpływ na ostateczną
odpowiedź.
4. Jaki algorytm nazywany stabilnym względem błędu numerycznego?
Jest to algorytm, który nie powoduje zwiększenia błędu w stosunku do błędu danych na
wejściu algorytmu.
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.
Jest to warunek przerwania iteracji, gdy różnica między kolejnymi wynikami jest dostatecznie
mała.
Np. |𝑥
𝑘+1
− 𝑥
𝑘
| < 𝜀
7. Opisz zastosowania schematu Hornera.
Obliczenie wartości wielomianu
Dzielenie wielomianu przez dwumian
Rozkład względem potęg dwumianu
8. Do czego służy algorytm Herona – opisz go.
Służy do obliczania przybliżonej wartości pierwiastka kwadratowego z liczby rzeczywistej.
Schemat obliczeń:
Wybór wartości startowej x
0
𝑥
𝑘+1
=
1
2
(𝑥
𝑘
+
𝑆
𝑥
𝑘
)
Warunek stopu |𝑥
𝑘+1
− 𝑥
𝑘
| < 𝜀
9. Podaj omawiane na wykładzie metody interpolacji. Krótko opisz, na czym każda z nich
polega.
Interpolacja wielomianowa - przybliżanie funkcji za pomocą wielomianów.
Interpolacja sklejana – duża liczba węzłów, dlatego też aby uprościć obliczenia dzieli
się je na wielomiany niskiego stopnia.
Interpolacja trygonometryczna - służy przede wszystkim przybliżaniu funkcji
okresowych.
10. Podaj znane Ci metody wyznaczania wielomianu interpolacyjnego stopnia n
przechodzącego przez n+1 zadanych węzłów.
Metoda Lagrange’a - 𝐿
𝑛
(𝑥) = ∑
𝑝
𝑖
(𝑥)𝑦
𝑖
𝑛
𝑖=0
, przypadek dla węzłów równoodległych.
Łatwy algorytm, jednak niewygodna postać wielomianu.
Metoda Newtona - 𝑃
𝑛
(𝑥) = ∑
𝑏
𝑚
𝑞
𝑚
(𝑥)
𝑛
𝑚=0
, Do wyliczeń współczynników b
m
korzystamy z ilorazów różnicowych funkcji.
Trudniejszy algorytm, łatwe liczenie wartości, łatwe powiększenie stopnia
wielomianu po dodaniu kolejnego węzła.
Metoda Aitkena
11. Wyjaśnij, na czym polega aproksymacja średniokwadratowa.
Polega na tym, że szukamy funkcji P(x), która przybliża funkcję f(x) na całym przedziale [a,b]
oraz korzystając z przybliżenia średniokwadratowego minimalizujemy błąd.
12. Wyjaśnij, do czego służy i na czym polega metoda najmniejszych kwadratów.
Metoda przybliżania rozwiązań układu, w którym jest więcej równań niż zmiennych.
Najczęściej stosowana przy regresji liniowej. Polega na minimalizacji 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?
W przypadku interpolacji funkcja interpolująca musi przechodzić przez wszystkie węzły, a
funkcja aproksymacyjna nie, jedynie je przybliża. Nie zawsze jest to potrzebne, ponieważ
mogą występować takie problemy jak: overfit i oscylacje wielomianu dla dużego n
(interpolacja wielomianowa), interpolacja nie uwzględnia błędów pomiaru.
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: funkcje trygonometryczne, wielomiany Legendre’a, wielomiany
Czebyszewa, wielomiany Laguerre’a, wielomiany Hermite’a.
15. Podaj poznane na wykładzie metody rozwiązywania układów równań. Na jakie dwie grupy
dzieli się je?
Metody dokładne:
Układy trójkątne
Eliminacja Gaussa
Eliminacja Gaussa-Jordana
Rozkłady na iloczyny trójkątne
Metody iteracyjne:
Metoda Jacobiego
Metoda Gaussa-Seidla
Metoda Richardsona
16. Opisz zagadnienie wyboru elementu podstawowego w metodzie eliminacji Gaussa.
Element podstawowy w macierzy to element, który służy do eliminacji wartości w danej
kolumnie.
Element ten musi być niezerowy. Rozwiązaniem problemu jest zamiana wierszy i wybór
innego elementu podstawowego. Jako nowy element wybieramy element o największej
wartości co do modułu w kolumnie.
17. Opisz różnice między następującymi metodami rozwiązywania równań nieliniowych:
bisekcji, stycznych, siecznych.
Najmniej efektywna jest metoda bisekcji. Porównanie efektywności metod siecznych i
stycznych zależy od kosztu obliczania pochodnej K
1
. Granicą jest 𝑟 =
1
𝑙𝑜𝑔
2
(
1+√5
2
)
− 1 ≈ 0.44.
Dla K
1
<r bardziej efektywna jest metoda stycznych, w przeciwnym wypadku metoda
siecznych.
18. Do czego stosuje się metodę Laguerre'a?
Do poszukiwania miejsc zerowych wielomianów.
19. Wyprowadź wzór skalarnej metody siecznych.
Bierzemy z metody stycznych Newtona 𝑥
𝑘+1
= 𝑥
𝑘
−
𝑓(𝑥
𝑘
)
𝑓′(𝑥
𝑘
)
Przybliżamy pochodną ilorazem różnicowym: 𝑓′(𝑥
𝑘
) =
lim
𝑥
𝑘
→𝑥
𝑘−1
𝑓(𝑥
𝑘
)−𝑓(𝑥
𝑘−1
)
𝑥
𝑘
−𝑥
𝑘−1
Ostateczny wzór: 𝑥
𝑘+1
= 𝑥
𝑘
−
𝑥
𝑘
−𝑥
𝑘−1
𝑓(𝑥
𝑘
)−𝑓(𝑥
𝑘−1
)
𝑓(𝑥
𝑘
)
20. Wyprowadź wzór skalarnej metody stycznych.
Równanie stycznej funkcji f(x) w punkcie (x
k
,f(x
k
)): 𝑦 = 𝑓
′
(𝑥
𝑘
)(𝑥 − 𝑥
𝑘
) + 𝑓(𝑥
𝑘
)
przyrównujemy do 0 (y=0) i wyznaczamy x.
Ostateczny wzór: 𝑥
𝑘+1
= 𝑥
𝑘
−
𝑓(𝑥
𝑘
)
𝑓′(𝑥
𝑘
)
21. Opisz trzy spośród znanych Ci metod rozwiązywania równań nieliniowych. Jakie są
praktyczne różnice w ich zastosowaniu?
Metoda bisekcji - metoda polegająca na dzieleniu przedziału argumentów na połowę
i wybieraniu tej połowy, w której funkcja zmienia znak.
Metoda 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 – 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 Jacobiego
Metoda Gaussa-Seidla
Iteracja prosta Banacha
Metoda iteracyjna Richardsona
23. Jakie poznałeś zastosowania rozkładu LU?
Metoda Doolittle’a, Metoda Cholesky’ego-Banachiewicza.
24. Podaj różnice rozkładu LU oraz rozkładu Cholesky'ego-Banachiewicza LLT.
Rozkład LU: A=LU, 𝐿 = [
1
0
0
𝑙
21
1
0
𝑙
31
𝑙
32
1
] , 𝑈 = [
𝑢
11
𝑢
12
𝑢
13
0
𝑢
22
𝑢
23
0
0
𝑢
33
]
Rozkład Cholesky’ego-Banachiewicza: A=LL’, 𝐿 = [
𝑙
11
0
0
𝑙
21
𝑙
22
0
𝑙
31
𝑙
32
𝑙
33
] , 𝐿′ = [
𝑙
11
𝑙
21
𝑙
31
0
𝑙
22
𝑙
32
0
0
𝑙
33
]
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.
1) Kwadratury interpolacyjne – metoda prostokątów, złożona metoda prostokątów,
metoda trapezów, złożona metoda trapezów.
2) Kwadratury Newtona-Cotesa – kwadratury oparte na wielomianach Legendre’a.
3) Kwadratury Gaussa – kwadratury wykorzystujące wielomiany ortogonalne.
4) Kwadratury Monte-Carlo – kwadratury wykorzystujące pojęcie średniej całkowej
funkcji.
26. Na czym polegają kwadratury Newtona-Cotesa?
Polegają na przybliżeniu funkcji podcałkowej za pomocą wielomianu Lagrange’a określonego
stopnia:
∫ 𝑓(𝑥)𝑑𝑥 ≈ ∫ 𝐿𝑛(𝑥)
𝑏
𝑎
𝑑𝑥
𝑏
𝑎
Wybieramy węzły równoodległe x
i
= a + ih.
Podstawiamy x
i
we wzorze na wielomian Lagrange’a: 𝐿
𝑛
= ∑
𝑦
𝑖
𝑛
𝑖=0
∏
𝑥−𝑥
𝑗
𝑥
𝑖
−𝑥
𝑗
𝑛
𝑗=0,𝑗≠𝑖
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 współrzędnych węzłów(Xi).
∫ 𝑓(𝑥)𝑑𝑥 ≈
𝑏
𝑎
𝑄(𝑓) = ∑ 𝑓(𝑥
𝑖
)𝐴
𝑖
x
i
– miejsca zerowe wielomianów ortogonalnych
A
i
– współczynniki zależne od typu wielomianu i jego stopnia
28. Opisz dwie metody całkowania Monte-Carlo.
1) Metoda chybił-trafił – losujemy punkt, czyli dwie wartości i sprawdzamy jak wiele
punktów trafiło w pole pod wykresem funkcji.
2) Kwadratury Monte-Carlo – kwadratury wykorzystujące pojęcie średniej całkowej
funkcji.
29. Co wiesz na temat pojęć: wartość własna, wektor własny oraz równanie charakterystyczne
macierzy?
𝐴𝑣⃗
𝑖
= 𝜆𝑣⃗
𝑖
, gdzie 𝑣⃗
𝑖
– wektor własny macierzy A, λ – wartość własna macierzy A.
𝑃
𝐴
(𝜆) = 𝜆
𝑛
+ 𝑥
1
𝜆
𝑛−1
+ ⋯ + 𝑥
𝑛
= 0 , gdzie λ – wartość własna macierzy A.
Macierze podobne mają takie same wartości własne.
30. W jakich celach stosujemy poznaną na wykładzie metodę Kryłowa?
Stosujemy ją do wyznaczania wielomianu charakterystycznego lub do wyznaczania macierzy
odwrotnej A
-1
.
31. W jaki sposób znaleźć największą, co do modułu, wartość własną macierzy rzeczywistej
korzystając z metody potęgowej?
1) Bierzemy dowolny wektor niezerowy 𝑥
0
⃗⃗⃗⃗⃗
2) Mnożymy przez macierz A: 𝑥
1
⃗⃗⃗⃗⃗ = 𝐴𝑥
0
⃗⃗⃗⃗⃗
3) Powtarzamy wielokrotnie krok 2)
4) Największa co do modułu wartość własna: 𝜆 ≈
𝑥
𝑖
𝑘
⃗⃗⃗⃗⃗⃗
𝑥
𝑖
𝑘−1
⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗
⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗⃗
, 𝑥
𝑖
⃗⃗⃗⃗ – ita składowa wektora.
32. W jaki sposób znaleźć najmniejszą, co do modułu, wartość własną macierzy rzeczywistej
korzystając z metody potęgowej?
33. Jak definiujemy macierze podobne i w jaki sposób wykorzystujemy pojęcie podobieństwa
macierzy do szukania wartości własnych macierzy?
Mówimy, że macierze A i B są podobne wtedy, gdy istnieje przekształcenie takie, że:
B = P
-1
AP, gdzie P to macierz nieosobliwa. Dla macierzy diagonalnej wartości własne są równe
elementom na diagonali. Macierze podobne mają te same wartości własne.
34. Na czym polega metoda Jacobiego szukania wartości własnych macierzy?
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 kolumny macierzy Q możemy otrzymać dokonując
ortogonalizacji macierzy A metodą Grama-Schmidta, wtedy kolumny macierzy R są
zbudowane z współczynników rozwinięcia zortogonalizowanej macierzy A.