Metody Numeryczne - Kolokwium 1

Część I - Analiza błędów - Zadania i algorytmy numeryczne, problem źle uwarunkowany, źródła błędów, błędy operacji arytmetycznych, arytmetyka komputerowa, arytmetyka przedziałowa

W standardzie IEEE 754 liczba zmiennoprzecinkowa posiada cechę złożoną z tylu bitów

11

W standardzie IEEE 754 liczba zmiennoprzecinkowa posiada mantysę złożoną z tylu bitów

52

W standardzie IEEE 754 liczba zmiennoprzecinkowa jest ujemna kiedy:

Pierwszy bit jest 1

Pierwszym bitem jest bit znaku S (sign). Jeśli liczba jest ujemna, oznacza to, iż S przyjmie wartość 1. Jeśli jest dodatnia S jest równe zero.

Błąd względny aproksymacji pi (3,141592...), do 3,14 wynosi około:

$$\frac{|3,14−3,141592|}{3,141592}=0,051\%$$

Błąd względny aproksymacji pi (3,141592...), do 3 wynosi około:

$$\frac{|3−3,141592|}{3,141592}=4,507\%$$

Błąd względny aproksymacji e (2,718281...), do 3 wynosi około:

$$\frac{|3−2,718281|}{2,718281}=10,36\%$$

Błąd względny aproksymacji g (9,81...), do 10 wynosi około:

$$\frac{|10-9,81|}{9,81}=1,937\%$$

Błąd względny aproksymacji c (299 792 458) do 300 000 000 wynosi około:

$$\frac{|300000000−299792458|}{299792458}=0,069\%$$

Błąd względny aproksymacji fi (1,618033) do 1,6 wynosi około:

$$\frac{|1,6-1,618033|}{1,618033}=1,115\%$$

Przy zapisie liczby 0,1 mantysa m i cecha c wynoszą odpowiednio

$m = 1,6$, $c = -4$
$1,6\cdot 2^{−4}$

Przy zapisie liczby 0,15 mantysa m i cecha c wynoszą odpowiednio

$m = 1,2$, $c = -3$
$1,2\cdot 2^{−3}$

Przy zapisie liczby 8,5 mantysa m i cecha c wynoszą odpowiednio

$m = 1,0625$, $c = 3$
$1,0625\cdot 2^3$

Przy zapisie liczby 4,5 mantysa m i cecha c wynoszą odpowiednio

$m = 1,125$, $c = 2$
$1,125\cdot 2^2$

Wartość liczby zmiennoprzecinkowej z mantysą równą 1,6 oraz cechą równą -4 wynosi

$1,6\cdot 2^{−4}=0,1$

Wartość liczby zmiennoprzecinkowej z mantysą równą 1,2 oraz cechą równą -3 wynosi

$1,2\cdot 2^{−3}=0,15$

Wartość liczby zmiennoprzecinkowej z mantysą równą 1,0625 oraz cechą równą 4 wynosi

$1,0625\cdot 2^4=17$

Wartość liczby zmiennoprzecinkowej z mantysą równą 1,125 oraz cechą równą 3 wynosi

$1,125\cdot 2^3=9$

Jeżeli przy drobnej zmianie wejścia algorytmu wynik zmienia się drastycznie to problem

jest źle uwarunkowany

Który błąd jest lepszą miarą dokładności np. pomiaru?

Błąd względny

Do głównych źródeł błędu nie należą

błędy wprowadzania danych

Najczęstszym błędem na wprowadzanych danych wejściowych jest

błąd pomiaru

Błędy algorytmu iteracyjnego wynikają z ograniczenia zasobu jakim jest

czas (nie można iterować w nieskończoność)

Do błędu zaokrągleń zaliczymy

błąd reprezentacji

Podstawową operacją matematyczną podlegającą największemu błędowi dokładności jest

odejmowanie (było powiedziane na wykładzie, nikt się tego nie spodziewał)

Mając wprowadzony błąd, podczas operacji mnożenia zmiana tego błędu jest zależna

od żadnej z nich

Mając wprowadzony błąd, podczas operacji odejmowania zmiana tego błędu jest zależna

zarówno od odjemnej jak i odjemnika

Błąd operacji odejmowania pochodzi od

utraty cyfr znaczących

Znalezienie miejsc zerowych wielomianu Wilkinsona jest zadaniem

źle uwarunkowanym (z ćwiczeń)

Część II - Iteracyjne metody rozwiązywania równania nieliniowego - Metody iteacyjne, w tym błędy, stabilność, zbieżność, Podstawowe metody rozwiązywania równania nieliniowego, Modyfiacje i udoskonalenia, Uzupełnienia: Kryterium stopu i zera wielokrotne

Proces iteracyjny

może być nieskończony

Algorytm iteracyjny

musi być skończony

Skumulowany błąd liniowy $\Epsilon_n$ to

$Cn\epsilon$

Rząd zbieżności 1 występuje w metodzie

bisekcji (połowienia przedziału)

Rząd zbieżności 2 występuje w metodzie

stycznych (Newtona, Newtona-Raphsona)

Rząd zbieżności $\approx 1,618$ występuje w metodzie

siecznych

Podstawienie punktu środkowego za jedną z granic zakresu to operacja typowa dla algorytmu

bisekcji (połowienia przedziału)

Znajdowanie miejsc zerowych równania liniowego wygenerowanego z punktów na granicach zakresu to operacja typowa dla algorytmu

falsi (fałszywej reguły)

Norma kolumnowa to norma

1

Norma wierszowa to norma

$\infin$

Dany wzór $||x||_1=\sum_{i=1}^n|x_i|$ opisuje normę

1

Dany wzór $||x||_2=\sqrt{\sum_{i=1}^nx_i^2}$ opisuje normę

2

Dany wzór $||x||_\infin=\max_{i=1\dots n}|x_i|$ opisuje normę

$\infin$

Dany wzór $||A||_1=\max_{j=1\dots n}\sum_{i=1}^n|a_{ij}|$ opisuje normę

1

Dany wzór $||A||_2=\sqrt{\max\{\sigma(A^TA)\}}$ opisuje normę

2

Dany wzór $||A||_\infin=\max_{i=1\dots m}\sum_{j=1}^n|a_{ij}|$ opisuje normę

$\infin$

Norma macierzy to największa wartość

wektora przekształconego / wektor nieprzekształcony

Metody iteracyjne mają w stosunku do metod "dokładnych" złożoność obliczeniową

mniejszą

Część III - Numeryczna algebra liniowa - Podstawowe pojęcia, Nieosobliwe układy równań, w tym uwarunkowanie układu równań, algorytmy bezpośrednie i iteracyjne, Zagadnienia własne czyli numeryczne metody wyznaczania wartości i wektorów własnych macierzy

Macierz źle uwarunkowana to macierz

o wysokim współczynniku uwarunkowania

Wskaźnik uwarunkowania mówi

ile razy zaburzenie wyniku przełoży się na zaburzenie danych wyjściowych

Która z poniższych metod nie jest metodą rozwiązywania układów równań liniowych?

Metoda Newtona (Newtona-Raphsona, stycznych)

Ogólny algorytm problemu liniowego to

1. spr. wskaźnika uwarunkowania
2. rozwiązanie
3. iteracyjne poprawienie rozwiązania

Algorytmy bezpośrednie

łatwo szacują czas obliczeń

Podział macierzy A = L + D + U

jest łatwy

Macierz L to macierz

poddiagonalna (trójkątna dolna - Lower)

Macierz D to macierz

diagonalna

Macierz U to macierz

naddiagonalna (trójkątna górna - Upper)

Jeżeli metoda Jacobiego jest zbieżna to metoda Gaussa-Siedla

jest zbieżna szybciej

Jeżeli metoda Jacobiego jest rozbiezna to metoda Gaussa-Seidla

jest rozbieżna szybciej

Do własności macierzy jednostkowej M nie należy

$||M||_F=1$ (norma Frobeniusa)

Gdy sumy modułów elementów we wszystkich wierszach są sobie równe mamy doczynienia z macierzą

wyrażoną wierszami

Zadania od prowadzących

Standard IEEE 754 dotyczy

reprezentacji liczb zmiennoprzecinkowych

Wektor $x=[-1, \frac{1\sqrt{2}}{2}, \frac{1}{4}]^T$ jest wektorem jednostkowym, gdy przyjmiemy normę

$||\quad||_\infin$ (nieskończoną, wierszową)

Metoda wyznaczania wartości własnych z rozkładem QR macierzy. Należy zaznaczyć zdanie prawdziwe.

Pojedyncza iteracja wymaga rozkładu macierzy $A$ na macierze $Q$ i $R$, a następnie obliczenia iloczynu $A=R\cdot Q$

Koszt obliczeniowy jednego (dowolnego, ale nie pierwszego) kroku metody iteracyjnej jest mierzony liczbą koniecznych (w jednym kroku) obliczeń wartości funkcji i jej pochodnych. Które zdanie jest prawdziwe?

Koszt metody siecznych: raz obliczana $f(x)$

Dla $\omega=1$ metoda Younga (metoda SOR) sprowadza się do

metody Gaussa-Siedla

Które zdanie najlepiej określa zalety i wady metody Newtona?

Zaleta: szybka zbieżność.
Wady: konieczność obliczania pochodnej, brak gwarancji zbieżności

Załóżmy, że mantysa jest zapisywana w polu o długości $p$ bitów. Wtedy maksymalny względny błąd zaokrąglenia liczby z przedziału $[4, 8)$ wynosi

$2^{-p-1}$

Oblicz błąd bezwzględny aproksymacji $x=-9,6$ za pomocą $x'=-9,5$

$\Delta=|x-x'|=0,1$