I. ARYTMETYKA W MASZYNIE KOMPUTEROWEJ

Zadanie 1.1. Przedstaw komputerową reprezentację liczb rzeczywistych.
Wartość liczby zmiennopozycyjnej określa się ze wzoru L=zmp^c, gdzie m-mantysa, p-
podstawa, c-cecha, z-znak. W systemie dwójkowym podstawa p zawsze jest równa 2 zatem
wzór redukuje się do postaci L=zm2^c. Można stwierdzić iż liczba zmiennoprzecinkowa
reprezentowana jest za pomocą dwóch grup bitów. Wyznacza się określony zakres na
mantysę oraz cechę, zatem liczba jest określona z pewną dokładnością i może występować w
określonym zakresie. Jeżeli mantysa jest stała a wykładnik się zmienia to wtedy przesuwa się
przecinek. W maszynie istnieje najmniejsza liczba, która jest reprezentowana dokładnie.
Nazywa się ona epsilon maszynowy.
Wzór na reprezentację liczb:

Zakres liczbowy: 2(

β

-1)

β

t-1

(U-L+1)+1

Zadanie 1.2. Opisz własności numeryczne operacji zmiennopozycyjnych.
Arytmetyka zmiennoprzecinkowa nie jest łączna, (x+y)+z != (y+z)+x. Kolejność
wykonywanych

operacji

ma

wpływ

na

wynik

końcowy.

Przy

operacjach

zmiennoprzecinkowych występują takie problemy jak: zaokrąglenie, przepełnienie,
nieprawidłowe operacje. Jeżeli liczby mają dwa różne wykładniki to podczas odejmowania
jedna z mantys musi zostać zdenormalizowana. Każda operacja zmiennopozycyjna opatrzona
jest błędem. Dodawanie i odejmowanie: (M1 +- M2*B^(e1-e2))*B^e1, mnożenie
(M1*M2)*B^(e1+e2), dzielenie: (M1/M2)*B^(e1-e2).
Główne cechy:

1)

operacje zmiennopozycyjne: x,y

∈

F, x+y?

∈

F – raczej rzadko

2)

maszynowe + i * nie są łączne i rozdzielne, są przemienne.

3)

maszynowe

ε

- najmniejsza liczba zmiennoprzecinkowa, dla której jeszcze

1+

ε

>1.

Zadanie 1.3. Podaj definicję i objaśnij na przykładzie pojęcia: zadanie, algorytm,
realizacja zmiennoprzecinkowa algorytmu.
Zadanie – jest to problem polegający na wyznaczeniu wektora wyników na podstawie
danych. Mówimy, że zdanie jest dobrze postawione jeżeli wektor jest jednoznacznie
określony dla przyjętego wektora danych. Np. obliczyć całkę z funkcji x^99.
Algorytm – określenie ciągu działań, które trzeba wykonać nad wektorem danych i wynikami
poprzednich działań. Liczba działań powinna być skończona. Lub też specyfikacja ciągu
elementarnych operacji, które zamieniają nasze dane wejściowe na oczekiwane wyniki.
Realizacja zmiennoprzecinkowa algorytmu – zastąpienie symboli matematycznych
odpowiednią arytmetyką komputerową. Komputer nie jest w stanie zinterpretować symbolu
całki zatem trzeba przedstawić go w formie np. dodawania z mnożeniem (metoda
prostokątów).

Zadanie 1.4. Podaj definicję i objaśnij na przykładzie: uwarunkowanie zadania,
poprawność numeryczna algorytmu, stabilność numeryczna algorytmu.
Uwarunkowanie zadania – czułość na zaburzenia danych. Charakteryzuje go również tzw.
wskaźnik uwarunkowania, który charakteryzuje wpływ zaburzeń danych za zaburzenie jego
rozwiązania.

}

e

t

i

i

i

cecha

e

mantysa

t

t

d

d

d

d

x

β

β

β

β

β

β

⋅

±

=

⋅













+

+

+

±

=

∑

1

/

2

2

1

...

4

4

4

3

4

4

4

2

1

Poprawność numeryczna algorytmu – Alg. num popr. ogranicza zaburzenie danych oraz
błędów reprezentacji. Jest to taki algorytm, który daje rozwiązania będące nieco zaburzonym
dokładnym rozwiązaniem o nieco zaburzonych danych. Jest to algorytm najwyższej jakości. .
Przykładem macierzy bardzo źle uwarunkowanej jest macierz Hilberta. H=[1/(i+j-1)]^n, ij=1.
Poprawność: lepsza arytmetyka, użycie zadania równoważnego, Wilkinson (x-1)(x-2)..(x-20)
Stabilność numeryczna algorytmu – 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. Algorytm powinien być stabilny dla każdej dostatecznie silnej
arytmetyki. Np. licząc e^-5.5 lepiej zamienić dane wejściowe na postać 1/e^5.5 , gdyż wtedy
błąd jest rzędu 0.007%.

Zadanie 1.5 Przeprowadź porównanie: interpolacja lagrange`a i hermeita.
Interpolacja jest procesem odwrotnym do tablicowania funkcji. Polega na wyznaczeniu
wielomianu, który przybliża funkcję na podstawie tzw. węzłów. Interpolacja Lagrange`a:

a)

dla pierwszego węzła f(x0) znajduje się wielomian który w tym punkcie przyjmuje
wartość f(x0) a w pozostałych 0

b)

Dla kolejnego węzła znajduje się wielomian, który w tym punkcie przyjmuje wartość
f(xk) a w pozostałych 0. Wynik tego wielomianu dodaje się do wielomianu
poprzedniego.

c)

Wielomian będący sumą wielomianów obliczonych dla poszczególnych węzłów jest
wielomianem interpolacyjnym

Wzór:

∑

=

−

n

j

j

n

j

n

x

x

x

x

yi

0

)

`(

)

(

)

(

ω

ω

Interpolacja Harmeit`a:
Interpolacja ta pozwala na znalezienie dla danej funkcji f (oraz danych wartości liczbowych
f

(j)

) wielomianu H

n

stopnia <= n, takiego, że H

n

(j)

(x

i

) = f

(j)

(x

i

) dla i = 0, 1, ..., k; j = 0, 1, ..., m

i

-

1. Czyli jest ona stosowana jeżeli oprócz węzłów interpolacji znane są także wartości
pochodnych oraz zachodzi potrzeba zarówno interpolacji funkcji jak i jej pochodnych. W
szczególnym przypadku jeśli nie ma danych pochodnych funkcji wzór interpolacyjny
Hermite’a jest równoważny wzorowi interpolacyjnemu Lagrang’e. Można zatem powiedzieć,
ż

e interpolacja Lagrange’a jest szczególnym przypadkiem interpolacji Hermite’a.

Zadanie 1.6 Objaśnij efekt Rungego – na czym polega i jakie są jego przyczyny
Błąd interpolacji – pogorszenie wyników interpolacji mimo zwiększania ilości węzłów.
Początkowo ze wzrostem liczby węzłów n przybliżenie poprawia się, jednak po dalszym
wzroście n zaczyna się pogarszać zwłaszcza na końcach przedziałów. Takie zachowanie się
wielomianu interpolującego (najczęściej mowa tu o wielomianie Lagrangea) jest zjawiskiem
typowym dla interpolacji za pomocą wielomianów wysokich stopni przy stałych
odległościach węzłów, jest to najczęściej przykład źle uwarunkowanego zadania. Efekt
Rungego może zostać zminimalizowany poprzez optymalny dobór węzłów interpolacji.
Jednym z rozwiązań jest posłużenie się wielomianami Czebyszewa.

Zadanie 1.7 Podaj definicję funkcji sklejanych, objaśnij ją, wyjaśnij kiedy i funkcje
sklejane dlaczego są użyteczne
Funkcja S(x) jest funkcją sklejaną stopnia m jeśli wraz z węzłami a= x0 <x1<x2…<xn=b
spełnia dwa warunki:

1)

w

każdym

przedziale

(xi,xi+1)

i=-1,0,1…n

gdzie

x

-1

=-nieskończoność,

x

n+1

=+nieskończoność S(x) jest wielomianem stopnia co najwyżej m

2)

jest klasy C

m-1

na całej osi rzeczywistej.

W najprostszym przypadku m=1 funkcja sklejana jest po prostu linią łamaną. W obliczeniach
maszynowych są one niezwykle użyteczne, gdyż wartości tych funkcji są łatwe do
wyznaczenia oraz są one zbieżne dla licznych klas funkcji. Są najbardziej użyteczne gdy: w
przypadku wielomianowych metod interpolacji może się zdarzyć że charakter interpolowanej
funkcji uniemożliwia dobre odwzorowanie za pomocą wielomianu interpolującego. Zamiast
stosować wielomianów dużego stopnia lepiej stosować spline’y, dzięki którym interpolacja
jest bezpieczniejsza, metoda ta jest szczególnie przydatna dla węzłów równoodległych,
funkcji sklejanej można używać do określania n-tych pochodnych oraz obliczania całek.
Stosowane są także do wygładzania powierzchni.

Zadanie 1.8 Porównaj interpolację wielomianową i funkcjami sklejanymi
Interpolacja wielomianowa = interpolacji Lagrangea (opisana w 1.5j).
Interpolacja funkcjami sklejanymi: Szczególnie popularnym rodzajem interpolacji jest
interpolacja funkcjami sklejanymi. Główną cechą wyróżniającą ten rodzaj interpolacji, jest
podział przedziału na którym znajdują się węzły, na mniejsze podprzedziały, a następnie
użycie na każdym z nich wielomianu interpolacyjnego odpowiednio niskiego stopnia.
Wyznaczenie sklejanej funkcji interpolującej nie sprawia problemu (także, gdy węzłów jest
bardzo dużo), tak jak późniejsze obliczanie jej wartości, co na pewno wpłynęło znacząco na
jej popularność. Gdy odstępy między węzłami wynoszą h, to moduł błędu metody jest rzędu
O(h

4

). Zalety sklejanych : - Są zbieżne dla wielu różnych klas funkcji

- Łatwo się je wyznacza, zalety lagrangea: przydatny w obliczeniach ręcznych

Zadanie 1.9 Omów warunki brzegowe stosowane przy wyznaczaniu sześciennych
funkcji sklejanych:
Niech f(x)

∈

C([a,b]). Funkcję s(x)

∈

S

3

(

∆

n

) nazywamy interpolacyjną funkcją sklejaną stopnia

trzeciego dla funkcji f(x), jeżeli s(x

i

) = f(x

i

) = y

i

, i = 0, 1, ..., n; n>=2. Jak wiadomo, funkcja

s(x) stopnia trzeciego zależy od (n+3) parametrów. Tak więc interpolacyjne funkcje sklejane
stopnia trzeciego mają dwa stopnie swobody, wobec czego nakłada się na nie dwa dodatkowe
warunki. Wybór tych warunków zależy zarówno od własności funkcji f(x), jak i od posiadanej
informacji o tej funkcji. Najczęściej rozpatruje się następujące warunki: s’(a+0)=

α

1

i s’(b-

0)=

β

1

lub s’’(a+0)=

α

2

i s’’(b-0)=

β

2

, gdzie

α

1

,

α

2

,

β

1

,

β

2

są ustalonymi liczbami

rzeczywistymi. Jeżeli funkcja f(x) ma pochodne w punktach a, b i są one znane, to można je
przyjąć jako liczby

α

1

,

α

2

,

β

1

,

β

2

. Na funkcję s(x) można nakładać inne warunki. Na przykład,

jeżeli f(x) jest funkcją okresową, o okresie (b-a), to najczęściej żąda się, aby funkcję sklejaną
s(x) można było przedłużyć na przedział (-

∞

; +

∞

) w taki sposób, że będzie ona funkcją

okresową o okresie (b-a), różniczkowalną w sposób ciągły. W takiej sytuacji na funkcję
sklejaną nakłada się warunki: s

(i)

=(a+0) = s

(i)

(b-0), i = 1, 2. Inne sposoby:

•

C

1

(x) – funkcja sześcienna przez pierwsze 4 punkty oraz C

n

(x) –

funkcja sześcienna przez ostatnie 4 punkty co umożliwia: s

’’’

(x

1

) = C

1

’’’

,

s

’’’

(x

n

) = C

n

’’’

,

•

natural cubic spline: s

’’

(x

1

) = s

’’

(x

2

) = 0 (free boundary)

•

complete spline: s’(x

1

) = y

1

’; s’(x

n

) = y

n

’ (clamped boundary)

•

s’’(x

1

) = y

1

’’; s’’(x

n

) = y

n

’’

•

s’’’(x) ciągła od x

2

do x

n-1

(not-a-knot condition)

KWWSQRWDWHNSOPHWRG\REOLF]HQLRZHLV\PXODFMDGULQ]PDU

LDQEXEDNS\WDQLDQDHJ]DPLQLRGSRZLHG]L"QRWDWND