1. Uwarunkowanie zadania numerycznego

2. Stabilność algorytmu

3. Poprawność numeryczna

4. Złożoność obliczeniowa

UWARUNKOWANIE ZADANIA:

Cecha zadania nie zależy od metody rozwiązania

Dane zadania:

Zamiast dokładnych danych dysponujemy ich reprezentacjami:

gdzie:

Ta niewielka zmiana może spowodować duże zmiany względne rozwiązania. Jeżeli niewielkie względne zmiany danych powodują duże względne zmiany jego rozwiązania to zadanie nazywamy źle uwarunkowanym.

Wielkości charakteryzujące wpływ zaburzeń danych na zaburzenia rozwiązania nazywamy wskaźnikami uwarunkowania zadania.

przykład:

-210

Przy rozwiązaniu okazało się, że pierwiastki są zespolone .

przykład2:

Oszacujmy zmianę wyniku:

gdzie:

zaburzenie współczynnik

maksymalne uwarunkowania

zadania

Jeżeli
i
mają taki sam znak to wskaźnik = 1

Jeżeli znaki
i
, różne to wskaźnik uwarunkowania zadania > 1

Maksymalne zaburzenie względne danych może się przenieść na zaburzenie względne wyniku, co najwyżej z takim mnożnikiem.

STABILNOŚĆ NUMERYCZNA ALGORYTMU:

przykład:

chcemy liczyć dla

ze wzoru rekurencyjnego:

(funkcja miała być malejąca!!!)

Przykład algorytmu numerycznie niestabilnego.

Błąd zaokrąglenia wartości
, którego moduł może sięgać
jest mnożony przez 5 dla obliczenia
. Kolejne błędy przemnażane są przez 5.

przykład2:

Oszacować wartość początkową
.

maleje gdy n wzrasta (dla dużych n maleje wolno)

Założenia:

(O.K. wynik prawidłowy - patrz przykład 1)

Przykład algorytmu numerycznie stabilnego.

DEFINICJA:

D - zbiór danych

a - wektor danych;

W - wektor wyniku

Należy obliczyć W = W(a) - algorytm idealny

Algorytm określa odwzorowanie WN - wynik numeryczny (algorytm liczony na komputerze)

Wynik W' obliczony dla danych numerycznych:

- zbiór danych, dla których określony jest algorytm
.

Mówimy, że algorytm obliczeniowy jest numerycznie stabilny, jeśli dla dowolnie wybranych danych
istnieje taka dokładność obliczeń
, że dla
, mamy:

1)
oraz

2)

czyli algorytm jest numerycznie stabilny wtedy, gdy zwiększając dokładność obliczeń można wyznaczyć (z dowolną dokładnością) dowolne istniejące rozwiązanie zadania.

POPRAWNOŚĆ NUMERYCZNA:

Algorytmy numerycznie poprawne:

Za numerycznie najwyższej jakości uznajemy takie algorytmy, dla których obliczone rozwiązanie jest nieco zaburzonym rozwiązaniem (dokładnym) zadania o nieco zaburzonych danych. Algorytmy spełniające ten postulat nazywamy numerycznie poprawnymi.

D - zbiór danych

a - idealne dane

zaburzone dane:

Dla algorytmu numerycznie poprawnego:
- wynik maszynowy

W - wynik idealny

wynik

idealny

ZŁOŻONOŚĆ OBLICZENIOWA ALGORYTMU:

Złożoność obliczeniowa to funkcja określająca maksymalną ilość operacji, które należy wykonać, aby obliczyć wynik za pomocą danego algorytmu.

ALGORYTM HORNERA:

; z = 125

ilość dodawań: n

ilość mnożeń: (n-1) - z potęgowania

n-1+n = 2n-1 mnożeń

n - z mnożenia

Korzystając z algorytmu Hornera, mamy:

n - mnożeń oraz n - dodawań

- wzór ogólny

Algorytmy

stabilne

Algorytmy numerycznie poprawne

---