Rozwinięcia nieskończone dziesiętne i nie tylko

Pierwszy wpis będzie dotyczył rozwinięć liczb z przedziału [0, 1] w systemach pozycyjnych o dowolnej podstawie. Zacznijmy od tego o co chodzi z tym rozwinięciem.

Jeśli mamy pewną liczbę x postaci

0, c_1 c_2 c_3 c_4 c_5 c_6 \dots

gdzie c_i są pewnymi cyframi, to ciąg \{c_n\}_{n=1}^\infty będzie rozwinięciem x. W systemie dziesiątkowym mniej więcej jest jasne co taki zapis oznacza oraz, że cyfry to liczby 0, 1, 2, 3, 4, 5, 6, 7, 8 i 9 oraz, że faktycznie to jest liczba! Trzy kropeczki, które się pojawiły świadczą o tym, że to rozwinięcie jest nieskończone, bo takie w ogólnej sytuacji będzie potrzebne, aby móc przedstawić dowolną liczbę z przedziału [0,1], np. część ułamkową liczby \pi. Wykażemy, że każda liczba ma rozwinięcie nieskończone, przy czym np. mając skończone rozwinięcie liczby \frac{1}{2}=0,5  w naszym ciągu c_n od drugiego miejsca będą występowały same zera, to jest 0,5= 0,50000... Za chwilę przejdziemy do zapisu w systemie o dowolnej podstawie L \in \mathbb{N}_2, ale najpierw spróbujmy zapisać inaczej naszą liczbę. Zauważmy, że:

x=0, c_1 + 0,0 c_2 + 0,00 c_3 + \dots=c_1 \cdot 0,1 + c_2 \cdot 0,01 + c_3 \cdot 0,001 + \dots

a więc inaczej:

\displaystyle x=c_1 10^{-1} + c_2 10^{-2} + c_3 10^{-3} + \dots=\sum_{n=1}^\infty \frac{c_n}{10^n}

Zatem jest to pewien szereg. W ogólnej sytuacji, gdy mamy system o podstawie L, to znaczy cyfry: 0, 1, 2, \dots L-1, to rozwinięciem liczby x będziemy nazywali taki ciąg cyfr z tego systemu \{c_n\}_{n=1}^\infty, że

\displaystyle x=c_1 L^{-1} + c_2 L^{-2} + c_3 L^{-3} + \dots=\sum_{n=1}^\infty \frac{c_n}{L^n}.

Chciałbym zwrócić tu uwagę na dwie analogie. Pierwsza to oczywiście przedstawienie ułamka dziesiętnego. Rolę 10 pełni L, druga to zapis w systemie o dowolnej podstawie liczb całkowitych. Każdą liczbę całkowitą (no powiedzmy, że naturalną, żeby nie martwić się znakiem) możemy zapisać, tym razem jako skończoną sumę:

c_n L^n + c_{n-1} L^{n-1} + \dots c_1 L + c_0

gdzie c_k to oczywiście cyfry, a L podstawa. W przypadku liczb z [0, 1] mamy to samo, ale potęgi przy L są ujemne. Stąd zapis przedstawiony powyżej jest w pewien sposób naturalny.  Mamy więc pewien szereg. Pierwsze pytanie jakie powinniśmy sobie zadać to czy jest zbieżny. Jest to dosyć oczywiste, ale zauważmy, że szeregi postaci

\displaystyle \sum_{n=1}^\infty \frac{c_n}{L^n}

są po pierwsze nieujemne, a po drugie co najwyżej równe \displaystyle \sum_{n=1}^\infty \frac{L-1}{L^n}, gdy wszystkie c_n=L-1 lub co najmniej równe 0, gdy wszystkie cyfry to zera.  Zbieżność szeregu \displaystyle \sum_{n=1}^\infty \frac{L-1}{L^n} gwarantuje nam żądaną zbieżność, ponadto ze wzoru na sumę szeregu geometrycznego

\displaystyle \sum_{n=1}^\infty q^n=\frac{q}{1-q}, gdy |q|<1

podstawiając q=\frac{1}{L} otrzymujemy

\displaystyle \sum_{n=1}^\infty \frac{L-1}{L^n}=(L-1)\frac{\frac{1}{L}}{1-\frac{1}{L}}=1.

Zatem nasze szeregi są zbieżne a dodatkowo przyjmują wartości z przedziału [0, 1].

Wykazaliśmy przy okazji, że

1=0,L-1 \thinspace L-1 \thinspace L-1 \dots

a oczywiste jest też, że

0=0,000\dots

Nietrudno również zauważyć, że są to jedyne rozwinięcia tych liczb, gdyż każda niezerowa cyfra po przecinku sprawi, że liczba ta będzie większa od zera, a każda cyfra mniejsza od L-1 po przecinku sprawia, że zabraknie nam trochę do jedynki.

Skonstruujemy teraz indukcyjnie algorytm wyznaczania rozwinięć dla dowolnej liczby z przedziału [0, 1].

Weźmy zatem dowolny x \in [0, 1]. Pierwszą cyfrę po przecinku c_1 wyznaczamy jako największą dla której

\frac{c_1}{L} \leq x.

Oczywiście znajdziemy taką, bo w najgorszym wypadku x<\frac{1}{L} i weźmiemy wtedy c_1=0. Chodzi o to, aby liczba 0,c_1 jak najlepiej przybliżała od dołu x. Zwięźlej:

c_1:= max \{ c \in \{0,1, \dots L-1\}: \frac{c}{L} \leq x \}

Załóżmy, że wybraliśmy już n cyfr c_1, c_2, \dots c_n następną wybieramy

\displaystyle c_{n+1}:=max \{ c \in \{0,1, \dots L-1\} : \sum_{k=1}^n \frac{c_k}{L^k}+\frac{c}{L^{n+1}} \leq x \}.

Czyli jeśli mamy liczbę 0, c_1 c_2 \dots c_n, która dla n cyfr po przecinku najlepiej przybliża od dołu x, to następną cyfrę dobieramy znowu tak, aby 0, c_1 c_2 \dots c_n c_{n+1} jak najlepiej przybliżało x od dołu. Zawsze będziemy mogli wybrać w ten sposób kolejną cyfrę, bo dysponujemy zerem.

Pokażemy teraz, że istotnie

\displaystyle x=\sum_{n=1}^{\infty}\frac{c_n}{L^n}

Zauważmy, że wystarczy wykazać następujące oszacowanie błędu w przybliżeniu do n cyfr

\displaystyle 0 \leq x- \sum_{k=1}^n \frac{c_k}{L^k} \leq \frac{1}{L^n}

i przejść z n do granicy w nieskończoności.

Nieujemność wynika ze sposobu określenia ciągu cyfr. Drugą nierówność dowiedziemy przez indukcję.

Dla n=1 jest jasne, że

x-\frac{c_1}{L} \leq \frac{1}{L}

bo gdyby

x-\frac{c_1}{L} >\frac{1}{L}

to \frac{c_1+1}{L}<x

Stąd jeśli  c_1 było równe L-1, to otrzymujemy, że 1<x a nasz x jest z przedziału [0,1], a jeśli c_1<L-1, to mamy sprzeczność z maksymalnością c_1.

Załóżmy teraz, że

\displaystyle x- \sum_{k=1}^n \frac{c_k}{L^k} \leq \frac{1}{L^n}

i będziemy chcieli wywieść stąd nierówność dla n+1.

Przypuśćmy, że ona nie zachodzi, to znaczy że

\displaystyle x- \sum_{k=1}^{n+1} \frac{c_k}{L^k} > \frac{1}{L^{n+1}}

Wtedy

\displaystyle \sum_{k=1}^n \frac{c_k}{L^k} +\frac{c_{n+1}+1}{L^{n+1}}<x

i znowu jeśli c_{n+1}<L-1, to mamy sprzeczność z maksymalnością c_{n+1}, natomiast gdy c_{n+1}=L-1, to mamy sprzeczność z założeniem indukcyjnym, ponieważ nierówność przyjmuje postać

\displaystyle \sum_{k=1}^n \frac{c_k}{L^k} +\frac{L}{L^{n+1}}<x

a więc równoważnie

\displaystyle \frac{1}{L^{n}}<x-\sum_{k=1}^n \frac{c_k}{L^k}

Stąd żądana nierówność na mocy indukcji zachodzi dla dowolnego n naturalnego. Otrzymaliśmy więc, że do każdej liczby z przedziału [0,1] możemy dobrać w ten sposób ciąg cyfr, który będzie jej rozwinięciem L-kowym (w systemie o podstawie L). Zauważmy też, że ten algorytm wybiera skończone rozwinięcia jeśli nieskończone nie są koniecznie. To znaczy weźmy na przykład ponownie liczbę \frac{1}{2}. Wiemy, że \frac{1}{2}=0,5  jednak łatwo sprawdzić, że, że również \frac{1}{2}=0,4999\dots,  co naprowadza nas na problem jednoznaczności rozwinięcia L-kowego. Widać, że czasami rozwinięć może być więcej, choć nie zawsze, bo 0 i 1 da się przedstawić w jedyny sposób. Problem ten a także jego konsekwencje m.in. w teorii mnogości omówione zostaną w następnym wpisie.

Reklamy

2 uwagi do wpisu “Rozwinięcia nieskończone dziesiętne i nie tylko

  1. Pingback: Algorytm Hornera (prostszy dowód) | roznematematyka

  2. Pingback: Dodawanie pisemne. Ułamki okresowe. | roznematematyka

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Wyloguj / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Wyloguj / Zmień )

Zdjęcie na Facebooku

Komentujesz korzystając z konta Facebook. Wyloguj / Zmień )

Zdjęcie na Google+

Komentujesz korzystając z konta Google+. Wyloguj / Zmień )

Connecting to %s