Wykład 2 aproksymacje liczb rzeczywistych



Pobieranie 85.21 Kb.
Data08.05.2016
Rozmiar85.21 Kb.

WYKŁAD 2

APROKSYMACJE LICZB RZECZYWISTYCH

  • Algorytm Euklidesa –metoda licząca 2300 lat!

Dane: m, n N, gdzie m > n.

Procedura:

Krok 1. m = k1 n + r1 gdzie 0 r1 < n

Uwaga: qm i qn qn i q r1, zatem

NWD(m, n) = NWD(n, r1 )

Krok 2. n = k2 r1 + r2 gdzie 0 r2 < r1

Uwaga: NWD(n,r1) = NWD(r1, r2 )

Krok 3. r1 = k3 r2 + r3 gdzie 0 r3 < r2

Uwaga: NWD( r1,r2) = NWD(r2, r3 )

..........

Krok j. rj-2 = kj rj-1 + rj gdzie 0 rj < rj-1

Uwaga: NWD( rj-2,rj-1) = NWD(rj-1, rj )

Dla pewnego j0, po j0 krokach musimy mieć rj0 = 0 tj.



rj0-2 = kj0 rj0-1 + 0

rj0-1 = NWD(rj0-2,rj0-1) = NWD(rj0-3,rj0-2) =...

= NWD(r1,r2) = (NWD(n,r1)) = NWD(m,n).

Zatem: algorytm Euklidesa polega na wykonaniu dzieleń do kroku, w którym reszta = 0. Ostatnia niezerowa reszta jest NWD(m,n).

rj0-1 =NWD(m,n) = a1 m + a2n dla pewnych liczb całkowitych a1, a2.

Przykład 1


NWD(13013, 390) = 13

13013(m) = 390(n) 33(k1 )+ 143(r1)

390 = 143 2 + 104

143 =104 1 + 39

104 = 39 2 + 26

39 = 26 1 + 13

26 = 13 2 + 0

Przykład 2


NWD(17986, 595)

17986 = 30 5 95 + 136

595 = 4 136 + 51

136 = 2 51 + 34

51 = 1 34 + 17

34 = 2 17 + 0

Program w Visual Basicu obliczający NWD:



Private Sub cmdNWD_Click()

Dim liczba3

Dim liczba4

liczba3 = vpp1

liczba4 = vpp2

Do While liczba3 <> liczba4

If liczba3 > liczba4 Then

liczba3 = liczba3 - liczba4



Else

liczba4 = liczba4 - liczba3



End If

Loop

etkNWD.Caption = liczba3



End Sub

Przykład

Weźmy liczba3 = 36, a liczba4 = 8.

Ponieważ liczby są różne wchodzimy w pętlę While.

liczba3 > liczba4, zatem

liczba3 = liczba3 - liczba4 = 36 – 8 = 28

liczba3 > liczba4, zatem

liczba3 =liczba3 - liczba4 = 28 – 8 = 20

liczba3 > liczba4, zatem

liczba3 = liczba3 - liczba4 = 20 – 8 = 12

liczba3 > liczba4, zatem

liczba3 = liczba3 - liczba4 = 12 – 8 = 4

Teraz

Liczba4 > liczba3, zatem

Liczba4 = liczba4 – liczba3 = 8 – 4 = 4

Ponieważ liczba3 = liczba4 wychodzimy z pętli i otrzymujemy NWD(36, 8) = 4.

  • Systemy pozycyjne

Ustalmy liczbę naturalną m > 0

Twierdzenie


Każdą liczbę naturalną można jednoznacznie przedstawić w postaci:

n = ak mk + ak-1mk-1 + ..... + a1m + a0 , gdzie 0 a0 < m.

Na mocy twierdzenia o podzielności.



,

gdzie 0 a0 < m.

Ponieważ a1 < n, więc na mocy założenia indukcyjnego

a1 = cl ml + ... + c1m + c0,

zatem


n = cl ml+1 +...+ c1m2 + c0m + a0.

Jednoznaczność wynika z porównania czynników.

Liczba m - podstawa systemu pozycyjnego.

Przy ustalonym m, liczbę n reprezentuje układ współczynników



akak-1 ... a1 a0

będący zapisem liczby n w systemie o podstawie m;



akak-1 ... a0 są cyframi w tym zapisie.
System o podstawie 2 - system binarny,

System o podstawie 8 - system ósemkowy,

System o podstawie 16 - system heksagonalny.

Zastosowanie:

Zapis kolorów, np. w HTML – system heksagonalny

Techniki Cyfrowe - przy programowaniu w Asemblerze – system binarny

Przykład 1


1610 = 1 101 + 6 100

16 = 1 32 +2 31 + 1 30

16= 121

16 = 1 24 + 0 23 +0 22 + 0 21+ 0 20

16= 10000

Przykład 2


124 = 1 26+ 1 25 +1 24 + 1 23 + 1 22 + 0 21+ 0 20

1242=1111100

124 =1 82 + 7  8 + 4 80

1248= 174


  • Kongruencje. Twierdzenie chińskie o resztach.

Określimy dla danej liczby naturalnej m > 1 działanie dodawania i mnożenia w Z tak, by wyniki tych działań należały do zbioru reszt z dzielenia przez m:

0, 1, ..., m - 1

np.: dla m=6,

zbiór reszt z dzielenia przez 6 = {0, 1, 2, 3, 4, 5}

Relacja kongruencji ‘mod’


a przystaje do b ‘modulo m’

Relacja „ ” jest relacją równoważności, tzn. jest:


  • zwrotna

  • symetryczna

  • przechodnia

Przykład







Definicja


Dla liczb całkowitych p, q przyjmiemy:

(p + q) (mod m) = reszta z dzielenia p + q przez m,

(p q) (mod m) = reszta z dzielenia p q przez m.

(p + q) (mod m) - suma p i q modulo m,

(p q) (mod m) - iloczyn p i q modulo m.

Przykład


(5+2)(mod3)=1

(6•5)(mod4)=2

Zbiór reszt 0,1,.., m -1 oznaczamy Zm.

Działania + (mod m) i (mod m) są określone w Zm.

Tabelki działań w Z2.




+ (mod 2)

0

1




 (mod 2)

0

1

0

0

1




0

0

0

1

1

0




1

0

1

Relacja między liczbami całkowitymi w Zm -

kongruencja (relacja przystawania) modulo m

Oznaczenie relacji m.



Definicja


p przystaje do q modulo m, pq(mod m)

wtedy i tylko wtedy, gdy



  • p - q jest podzielna przez m, lub

  • reszta z dzielenia p przez m jest równa reszcie z dzielenia q przez m.

Z =

A={}

klasy kongruencji

Przykład


m=7

zbiór reszt z dzielenia przez 7 = {0, 1, 2, 3, 4, 5, 6}

={reszta z dzielenia p przez 7 równa się 0}=

={0, 7, 14, 21, 28, 35, .......}

={reszta z dzielenia p przez 7 równa się 1}=

={1, 8, 15, 22, 29, 36, .......}

={reszta z dzielenia p przez 7 równa się 2}=

={2, 9, 16, 23, 30, 37, .......}

={reszta z dzielenia p przez 7 równa się 3}=

={3, 10, 17, 24, 31, 38, .......}

={reszta z dzielenia p przez 7 równa się 4}=

={4, 11, 18, 25, 32, 39, .......}

={reszta z dzielenia p przez 7 równa się 5}=

={12, 19, 26, 33, 40, .......}

={reszta z dzielenia p przez 7 równa się 6}=

={5, 13, 20, 27, 34, 41, .......}
Twierdzenie

Jeśli a b (mod m) oraz cd (mod m), wówczas:



  1. a + c  (b + d) (mod m)

  2. ac  (bd) (mod m)

  3. anbn (mod m)

Dowód:

  1. Wiemy z założenia, że m(a – b) oraz m(c – d). Pytamy, czy m((a + c) – (b + d))?
    (a + c) – (b + d) = a + c – b – d = (a – b) + (c – d) czyli m((a+ c) – (b+ d)).

  2. Wiemy z założenia, że m(a – b) oraz m(c – d). Pytamy, czy m((a c) – (b d))?
    (a c) – (b d) = (a c)(b c) + (b c)(b d) =
    c (a – b) + b (c – d)
    czyli m((a c) – (b d)).

  3. Konsekwencja punktu 2.

Twierdzenie Chińskie o resztach

Jeżeli liczby całkowite są parami względnie pierwsze, tzn. NWD()=1,



to dla każdego układu liczb całkowitych istnieje liczba całkowita q o tej własności, że



Przykład 1.

Znaleźć liczbę q, która podzielona przez liczbę pi da resztę qi dla następujących zbiorów liczb:

p1= 4, p2= 5, p3= 7

q1=0, q2= 4, q3=3

4/(q-0) q = 4a

5/(q-4) q = 5b + 4

7/(q-3) q = 7c+3

układ równań jest niejednoznaczny i jest spełniony np. dla

a=6, b=4, c=3

stąd

q=24
Przykład 2.

(Zadanie poniższe przytacza matematyk chiński Cin –Kin-Czang w dziele „Su-szou-kin-czang”, co znaczy „Dziewięć działów sztuki liczbowej”)

Do trzech beczek wsypano jednakowe ilości ryżu. Do składu dobrali się złodzieje i z każdej beczki ukradli znaczną część jej zawartości. Nie wiadomo ile było ryżu uprzednio. Wiadomo natomiast, że pozostało:

  • w I beczce 1 ho

  • w II beczce 1 szyng i 1 ho

  • w III beczce 1 ho

Gdy złodziei pochwycono, jeden z nich zeznał, że czerpał z pierwszej beczki czerpakiem, drugi z drugiej beczki – drewnianym chodakiem, trzeci zaś z trzeciej beczki – miseczką.

Przekonano się, że:

czerpak mieści 1 szyng i 1 ho

chodak mieści 1 szyng i 7 ho

miseczka mieści 1 szyng i 3 ho

Każda z beczek mieści najwyżej 3 szy.

10 ho = 1 szyng;
10 szyng = 1 tau;
10 tau = 1 szy.


Ile ryżu było w każdej z beczek?

Rozwiązanie:

Problem nasz możemy przeformułować w sposób następujący:

q  1 (mod 11) po 11 ho (czerpak) z I beczki

q  11 (mod 17) po 17 ho (chodak) z II beczki

q  1 (mod 13) po 13 ho (miseczka) z III beczki
Z naszego twierdzenia wiemy, że istnieje rozwiązanie tego problemu.
Metody rozwiązania mogą być różne. Najprostsza, choć nie zawsze najszybsza jest taka:

1, 12, 23, 34, 45, 56, 67, 78, 89, 100, 111, ..., 2278, 2289

11, 28, 45, 62, 79, 96, 113, 130, 147, 164, ..., 2272, 2289

1, 14, 27, 40, 53, 66, 79, 92, 105, 118, ..., 2276, 2289.
Algorytm szyfrowania:

RSA – Ronald Rivest, Adi Shamir, Leonard Adleman.

Metoda polega na wybraniu trzech liczb:


  • N, która jest iloczynem dwóch liczb pierwszych (w praktyce N musi mieć ponad 200 cyfr),

  • E oraz D, które dobieramy w odpowiedni sposób w zależności od tych właśnie liczb pierwszych. E i D nazywamy kluczami. Algorytm doboru E i D jest opisany w książce „Tajemne przekazy”.

Dla uproszczenia nasze N, E, D będą bardzo małe.

  • N i E podajemy do wiadomości publicznej.

  • Klucz D zachowujemy tylko dla naszej wiadomości.



Przykład

N = 85 = 5 17; E = 5; D = 13

Chcemy zaszyfrować wiadomość, dla uproszczenia literę x.

x = 24 (a = 1, b = 2,...)

245 (mod 85) = 24  24  24  24  24 (mod 85) =
= 7962624 (mod 85) = 79 (mod 85)


Rozszyfrowanie (przy użyciu klucza D):

7913 (mod 85) = 24 (mod 85)

Czyli otrzymaliśmy naszą wiadomość x.

Jak obliczyć to w łatwy sposób, mając do dyspozycji tylko zwykły kalkulator i pewną wiedzę z Teorii liczb:

79  79 = 6241  36 (mod 85)
79  79  79  79  36  36  21 (mod 85)
798  21  21  16 (mod 85)
7912  21  16  81 (mod 85)
7913  81  79  24 (mod 85)



A B






0 1

s – liczba rzeczywista wyznaczona przez pewien przekrój

(A, B) mający lukę

Zbiór A nie ma elementu największego

Zbiór B nie ma elementu najmniejszego

Stąd





s – można z dowolną dokładnością przybliżać z góry

i z dołu liczbami wymiernymi

np. przybliżenia

1.00, 1.4, 1.41, 1.414, 1.4142, 1.141421, itd.

2.00, 1.5, 1.42, 1.415, 1.4143, 1.141422, itd.

a zatem istnieją takie liczby wymierne pn i qn, że






  • Ograniczenia, kresy, zasada zupełności

Definicja


Liczba aR jest ograniczeniem górnym (dolnym) zbioru A liczb rzeczywistych, wtedy i tylko wtedy gdy dla każdego xA, a x (a x).

Ograniczenie górne (dolne) a jest kresem górnym (dolnym) zbioru A wtedy, gdy: a b, (a b) dla każdego ograniczenia górnego (dolnego) b zbioru A.

Kres górny A sup A,

Kres dolny A inf A.


Definicja


Zbiór A jest ograniczony od góry (z dołu), gdy istnieje ograniczenie górne (dolne) zbioru A.

Przykład


  • A={k: k=, n\{0}}

sup A=1, inf A=0

  • A=N

sup A=, inf A=0

Twierdzenie (Zasada zupełności)

Każdy zbiór A liczb rzeczywistych ograniczony z góry ma kres górny i każdy zbiór A liczb rzeczywistych ograniczony z dołu ma kres dolny.



  • Aproksymacje liczb rzeczywistych
Aproksymacja I
Systemy pozycyjne




Definicja


Przedstawieniem liczby s w systemie pozycyjnym o podstawie m nazwiemy zapis

a0 ,a1a2a3.....ak....

gdzie dla i=1,2,3,.....



Zapis ten oznacza, że

gdzie


,

Twierdzenie


Dla każdej liczby istnieje ciąg liczb całkowitych taki, że w systemie pozycyjnym o podstawie m.
Dowód

Krok1. Wybieramy takie, że

Krok2. Wybieramy takie, że

Załóżmy, że w kroku n wybraliśmy a tak, że





Krok n+1. Wybieramy atak, by

Ponieważ


, więc
Przykład

Przedstawić liczbę w systemie pozycyjnym o podstawie 2

=02+12+02+...

..........

,



Aproksymacja II

Ułamki łańcuchowe

, znajdujemy liczbę taką, że

tzn. , gdzie



,

Stąd




Ułamek łańcuchowy:




Przykład


Przedstawić liczbę w postaci ułamka łańcuchowego



  • Ciało liczbowe.

Definicja

Niech K będzie zbiorem liczbowym zawierającym przynajmniej dwa elementy.

Niech w K będą określone dwa działania zwane dodawaniem (+) i mnożeniem() oraz wyróżnione dwa elementy zwane zerem (0) i jedynką (1).

Powiemy, że K jest ciałem liczbowym, jeśli działania te i elementy 0 oraz 1 mają dla dowolnych elementów x, y, z należących do K następujące własności:



  1. x + y = y + x przemienność dodawania)

  2. x + (y + z) = (x + y) + z (łączność dodawania)

  3. x + 0 = x (0 jest elementem neutralnym dodawania)

  4. Dla każdego x K istnieje taki element t K, że
    x + t = 0 (istnienie elementu przeciwnego)

  5. xy = yx (przemienność mnożenia)

  6. x  (yz) = (xy)  z (łączność mnożenia)

  7. x  1 = x (1 jest elementem neutralnym mnożenia)

  8. Dla każdego różnego od 0 elementu x K istnieje taki element u K, że
    xu = 1 (istnienie elementu odwrotnego)

Przykład

Zbiór liczb wymiernych jest ciałem liczbowym.

Zbiór liczb rzeczywistych jest ciałem liczbowym.

Zbiór liczb zespolonych jest ciałem liczbowym.

Zbiór liczb całkowitych nie jest ciałem liczbowym.

(brak elementu odwrotnego).
Zbiór liczb niewymiernych nie jest ciałem liczbowym.

(np.: brak elementu zerowego)





©absta.pl 2016
wyślij wiadomość

    Strona główna