Metody numeryczne 1 (MEN331) - Ćwiczenia 3

Kalendarium, Zasady, Ćw1, Ćw2, Ćw3, Ćw4, Ćw5, Ćw6, Ćw7, Ćw8, Ćw9, Ćw10, Ćw11, Ćw12, Ćw13

Prowadzący: Rafał Witkowski
Temat: Uwarunkowanie zadania, numeryczna poprawnośći stabilność algorytmów, złożoność obliczeniowa

Uwarunkowanie zadania

Mówimy, że zadanie jest źle uwarunkowane, jeśli niewielkie, względne zmiany danych wejściowych zadania powodują duże względne zmiany rozwiązania danego zadania.
Np. przykładowy źle uwarunkowany układ równań:

Przykład 1

Dla układu równań:
2x + 6y = 8
2x + 6,00001y = 8.00001
rozwiązaniem jest: x=y=1

Ale już dla układu równań:
2x + 6y = 8
2x + 5,99999y = 8,00002
rozwiązaniem jest:
x=10
y=-2

Uwarunkowanie zadania można sprawdzić zamieniając w wyrażeniu, które obliczamy wszystkie wartości na te wartości obrarczone pewnym błedem względnym (tzw. wartości zaburzone), czyli mnożąc każdą liczbę przez pewne (1+alfa). Wtedy możemy wyliczyć względną zmianę wyniku, której oszacowanie górne nazywane jest wskaźnikiem uwarunkowania zadania.

Przykład 2

Obliczmy wskaźnik uwarunkowania zadania obliczania iloczynu skalarnego:

Jako wskaźnik uwarunkowania można przyjać maksymalny mnożnik z jakim zaburzenie względne danych może przenieść się na zaburzenie względne wyniku.
W przypadku gdy wskaźnik uwarunkowania zadania jest równy 1, to zadanie jest idealnie uwarunkowane. Gdy jest bliskie 1 jest dobrze uwarunkowane. Im dalej od 1 tym zadania jest gorzej uwarunkowane.

Zadanie 1

Oblicz wskaźnik uwarunkowania zadania:
a) sumy n liczb
b) f(x) = a(b+c)

Wzór Taylora

Uwarunkowanie zadania można także liczyć z wzoru Taylora. Dowód poprawności tej metody został przedstawiony na wykładzie.
Dla funkcji y = f(x₁...x_n) wskaźnik uwarunkowania zadania można więc wyliczyć z wzoru:

Przykład 3

Obliczymy uwarunkowanie zadania obliczania sumy dwóch liczb:

Jeśli x₁ i x₂ mają te same znaki, to te współczynniki są ułamkami właściwymi, stąd błąd względny nie będzie przewyższał max(e_x1,e_x2). Jeśli x₁ i x₂mają różne znaki, to co najmniej jeden ze wspołczynników jest większy od 1 i błąd względny ulega wzmocnieniu. Wzmocnienie to jest największe, gdy x₁ = -x_{2 .}

Przykład 4

Obliczymy uwarunkowanie zadania obliczania iloczynu dwóch liczb:

Błędy względne w przypadku mnożenia słabo przenoszą się na wynik.

Zadanie 2

Oblicz uwarunkowanie zadania obliczania:
a) sumy n liczb
b) iloczynu skalarnego dwóch wektorów
c) obliczania pierwiastków równania kwadratowego
d) (a²-b²)

Zadanie 3

Wykonaj program liczący dwa razy tą samą funkcję tylko inaczej zapisaną.

program niesk;

{$APPTYPE CONSOLE}

var x,y: single;

begin
  x:=0.00000001;

  y := sqrt(x*x + 1) - 1;

  writeln('W pierwszym przypadku: y = ', y);

  x:=0.00000001;

  y := x*x / (sqrt(x*x + 1) + 1);

  writeln('W drugim przypadku   : y = ', y);

  readln;
end.

Który wynik jest obarczony mniejszym błędem? Dlaczego?

Numeryczna poprawność i stabilność algorytmów

Definicja

Mówimy, że algorytm

(należy do klasy zadań

) jeżeli

jest alg. obliczenia wyniku y=f(x) dla dowolnych danych

Numeryczna poprawność algorytmu

Algorytm

nazywamy numerycznie poprawnym w klasie zadań

jeżeli istnieją stałe C_x, C_y takie, że

i dostatecznie silnej arytmetyki instnieje

takie, że

Stałe C_x, C_ynazywamy wskaźnikami kumulacji algorytmu

w klasie zadań

Przykład 5

Zbadaj numeryczną poprawność algorytmu obliczania iloczynu sklalrnego wektorów a = (a₁, a_{2, ... )}b = (b₁, b_{2, ... )}. Zgodnie z algorytmem:
s₀:= 0,
s₁:= s_{0 +}a₁b₁, itd.

Ponieważ mamy dane zaburzone (nie da się ich dokładnie zapamiętać w komputerze) otrzymujemy:

, gdzie

Operacje są wykonywane w artytmetyce fl która jest również obarczona pewnym błędem.

jeśli przyjmiemy, że:

to otrzymujemy:

czyli:

, gdzie

Aby uznać, że algorytm jest numerycznie poprawny musimy sprawdzić czy spełnia odpowiednie założenia numerycznej poprawności algorytmu.

Zbadajmy jaki wpływ na błąd mają zaburzone dane wektora a na normę.

Jak widać - względne zmiany wektora a przenoszą się na normę tylko w małym stopniu.

Dodatkowo możemy założyć, że pozostała wartość błędu dla wyniku jest zaburzeniem dla danych wejściowych wektora b. Uzyskujemy:

Odpowiedzmy na pytanie czy algorym jest numerycznie poprawny:

Warunek pierwszy jest spełniony ponieważ używając arytmetyki fl każda wartość może być minimalnie zaburzona, a jak widać takie zaburzenia (dla wektora a) przenoszą się z takim samym błędem na normę. Otrzymujemy spełnienie pierwszego warunku
Warunek drugi jest również spełniony, gdyż, jak widać, można oszacować błąd otrzymany w wyniku wykonanych operacji fl jako stałą przemnożoną przez błąd

Błędy wytworzone w algorytmie można interpretować jako pewne zaburzenia tylko składowych wektora b, bądź podzielić pomiędzy wektory a i b

Numeryczna stabilność algorytmów

Wielkość

nazywamy optymalnym poziomem błędu rozwiązania f(x) w arytmetyce fl.
Algorytm

nazywamy numerycznie stabilnym w klasie zadań

jeżeli istnieje stałą C taka, że

i dla dostatecznie silnej arytmetyki

Nie wszystkie algorymy numerycznie stabilne są numerycznie poprawne.

Złożoność obliczeniowa

Dla zadania f wielkość

, gdzie z(f,x) oznacza minimalną liczbę działań potrzebnych do obliczenia f(x), nazywamy złożonością obliczeniową.

Mówimy, że zadanie y=f(x) ma na zbiorze D n istotnych danych, jeżeli instnieją dane

, dla których zmiana dowolnej ze składowych x powoduje zmianę wyniku.

Przykład 6

Ile wynosi minimalna liczba działań dla wyznacznika det(A) gdzie A jest macierzą n x n ?

Ponieważ, jak zostało omówione na wykładzie, minimalna liczba działań wymagana na obliczenie dowolnej funkcji zawierającej n danych istotnych wynosi połowę tej wartości to otrzymujemy, że wartość ta wynosi conajmniej:

Zadanie 4

Obliczyć ile wynosi numeryczna liczba działań dla obliczenia iloczynu macierzy A - o wymiarze p x q oraz B - q x r ?