P O L I T E C H N I K A W R O C Ł A W S K A WYDZIAŁ ELEKTRONIKI Automatyka i Robotyka (II rok, inż.)
Metody numeryczne - labolatorium (piątek, godz. 11^15)
Imię i Nazwisko:		Piotr Zazula 155558 Daniel Kielar	Data: 07.03.2008r
Ćwiczenie nr.: 2 Temat: Reprezentacje liczb, algorytm Hornera, badanie błędów numerycznych

Zadanie 1:

1. Wstęp:

Funkcję
można przedstawić w postaci nieskończonego szeregu:

Cechą funkcji
jest to, że jej pochodna jest równa jej samej. Eksponens jako funkcję analityczną na mocy twierdzenia Taylora można rozwinąć w szereg potęgowy:
.

Wykres funkcji
:

2. Przykładowy fragment kodu z wyjaśnieniem oraz wynikami:

function[suma] = exponent(x,N)

E=0.1

suma=1

blad=0

for i=1:N

suma=(suma+(x.^i)/factorial(i))

blad(i)=exp(x)-suma

if E>abs((x.^i)/factorial(i)) break

end

end

Program napisany został w Matlabie. Zasada jego działania opiera się na szeregu Taylora. Została stworzona pętla która sumuje kolejne elementy ciągu oraz zapisuje błąd dla danego i. Pętla zakończy się jeśli błąd będzie mniejszy niż:
gdzie
jest zadaną z góry dokładnością lub po n krotnym przejściu pętli.

	X=2	X=3	X=3,5	X=4
0,1	4.3891 2.3891 1.0557 0.3891 0.1224 0.0335	16.0855 11.5855 7.0855 3.7105 1.6855 0.6730 0.2391 0.0764 0.0221	28.6155 22.4905 15.3446 9.0920 4.7152 2.1620 0.8855 0.3270 0.1098 0.0338	49.5982 41.5982 30.9315 20.2648 11.7315 6.0426 2.7918 1.1664 0.4440 0.1550 0.0500 0.0149

3. Wnioski:

Jak widać wszystkie bledy dążą do 0 co jest oczywiście jak najbardziej zrozumiałe. Po każdym przejściu pętli programu błąd się zmniejsza ponieważ dodawane są kolejne, coraz dokładniejsze przybliżenia. Inną rzeczą która jest bardzo widoczna jest fakt, że wraz ze wzrostem x czyli potęgi funkcji
Błędy są coraz większe.

Zadanie 2 - Schemat Hornera

1. Wstęp:

Dowolny wielomian o postaci:

mona zapisać w postaci, która pozwala na realizację tzw. algorytmu Hornera:

Schemat Hornera - sposób obliczania wartości wielomianu dla danej wartości argumentu wykorzystujący minimalną liczbę mnożeń.

Jeśli dany jest wielomian
, to dla obliczenia jego wartości dla zadanego x bezpośrednio z podanego wzoru należy wykonać 1 + 2 + 3 + ... + (n-1) + n = n(n+1)/2 mnożeń oraz n dodawań. Tymczasem proste przekształcenie:
pokazuje, że wystarczy jedynie n mnożeń i n dodawań. Mnożenia są operacją czasochłonną i eliminacja zbędnych mnożeń jest jednym z podstawowych problemów optymalizacji algorytmów.

2. Przykładowy fragment kodu z wyjaśnieniem:

double Horner(double x)

{

int suma=0;

cout << ("Stopien wielomianu= ");

int n;

cin >> n;

for(int i=n; i>=0; i--)

{

int a;

cout << "Podaj wspolczynnik " << i<<":" << endl ;

cin >> a;

if (i!=0)

{

suma=x*(suma+a);

}

else suma=suma+a;

};

return suma;

}

3. Wnioski:

Program został napisany w języku C++. Program w pętli pobiera wartość aktualnego współczynnika a i dodaje go do sumy oraz mnoży razy x co odpowiada fragmentowi schematu Hornera. Przy ostatnim elemencie zostało tylko zsumowane a.

Jak widać ze wzoru Hornera jest on o wiele szybszy gdyż w porównaniu ze zwykłym wielomianem nie zawiera funkcji wykładniczych. Żeby wyznaczyć wartość wielomianu stopnia n za pomocą postaci
potrzebujemy n dodawań i wykonywania n funkcji wykładniczych (maksymalna wartość funkcji wynosi x^n). A aby wyznaczyć wartość wielomianu stopnia n za pomocą schematu Hornera potrzebujemy n dodawań i tylko n mnożeń. Stąd schemat Hornera jest o wiele lepszym sposobem na rozwiązanie wielomianu.

Zadanie 3.

1. Wstęp:

Celem tego zadania była zamiana liczby całkowitej/rzeczywistej na postać binarną. Liczba całkowita powstaje przez dzielenie liczby z resztą przez 2 a następnie zapisanie jej „od końca”. Zapisanie ułamka polegało na mnożeniu części ułamkowej razy 2 i sprawdzaniu wyniku. Gdy wynik był większy lub równy jedności ustawiany była wartość 1, a następnie od wyniku odjęta została jedynka i operacje były kontynuowane aż do zadanej precyzji. Na początku każdej liczby binarnej zawsze znajduje się 1.

2. Przykładowy fragment kodu z wyjaśnieniem:

void zamiana(int calkowita,double ulamek)

{

calkowita=fabs(calkowita);

for(int i=9;i>=0;i--)

{

TablicaRzeczywiste[i]=0;

TablicaUlamkowa[i]=0;

TablicaUlamkowa[i]=calkowita%2;

calkowita=calkowita/2;

};

if (calkowita<0)

{

bool koniec=false;

for(int i=0;i<10;i++)

{

if(TablicaUlamkowa[i]==1) koniec=true;

if(koniec) TablicaUlamkowa[i]=(!TablicaUlamkowa[i]);

}

for(int i=9;i>=0;i--)

{

if(TablicaUlamkowa[i]==0)

{

TablicaUlamkowa[i]=1;

break;

}

else TablicaUlamkowa[i]=0;

};

};

for(int i=0; i<10;i++)

{

ulamek=ulamek*2;

if(ulamek>=1)

{

ulamek=ulamek-1;

TablicaRzeczywiste[i]=1;

}

else

{

TablicaRzeczywiste[i]=0;

};

};

};

Zamiana liczby całkowitej dodatniej odbywa się w następujący sposób: wykonuje się dzielenie przez 2 i do tablicy zapisuje się reszte z tego dzielenia i powtarza się ten krok dopóki liczba dzielona nie spadnie do 0 lub 1. Zamiana liczby całkowitej ujemnej odbywa się poprzez zmianę wszystkich bitów liczby z 1 na 0 i z 0 na 1 a nastepnie do tej liczby dodaje wartość 1. Część ułamkową (mniejszą od 1 ale większą od 0) uzyskuje się poprzez mnożenie razy 2. Jeśli pomnożona liczba przekroczy 1 do tablicy wpisana zostaje 1 a następnie od pomnożonej liczby zostaje odjęta 1. W przeciwnym wypadku do tablicy wpisywane jest 0.

Dla typu float liczby mogą być z zakresu od 1,5*10^-45 do 3,4*10³⁸, dla typu double od 5,0*10^-324 do 1,7*10³⁰⁸ dla typu long double od 3,4*10^-4932 do 1,1*10⁴⁹³².

---