Diese Reihe....?

22.09.2008, 16:50

Zeno-2

Diese Reihe....?

Ich würde gerne mehr über die folgende Reihe wissen,
insbesondere ob sie vielleicht einen bestimmten Namen hat,
ob sie irgendwo häufig gebraucht wird, Konvergenz, usw.
Die Reihe ergibt sich als Konsequenz aus dem SPIHT Verfahren.

Also, sei

$\begin{eqnarray*} x \in \mathbb R \end{eqnarray*}$

$\begin{eqnarray*} T = 2^{\lfloor log_2(x) \rfloor} \end{eqnarray*}$

$\begin{eqnarray*} Q(x) = \frac{3}{2} T + a_0T/4 +a_1T/8 +a_2T/16... \end{eqnarray*}$

wobei

$\begin{eqnarray*} a_i \in \{1,-1\} \end{eqnarray*}$

sein soll.

Beispiel:

$\begin{eqnarray*} x = 18 \end{eqnarray*}$

$\begin{eqnarray*} T = 2^{\lfloor log_2(x) \rfloor} =2^4=16 \end{eqnarray*}$

$\begin{eqnarray*} Q(x) = \frac{3}{2}*(16) + a_0*(4) +a_1*(2) +a_2 *(1)... \end{eqnarray*}$

(Ich schreibe das Malzeichen * mal aus, hope you don't mind smile

) .

Wenn $\begin{eqnarray*} Q_n(x) \end{eqnarray*}$ den Abbruch nach dem n-ten Glied darstellt,
wäre man im Prinzip mit dem 3. Glied fertig:

$\begin{eqnarray*} Q_3(x) = \frac{3}{2}*(16) -1*(4) -1*(2) = 18 \end{eqnarray*}$

In der (SPIHT) Praxis kann es aber sein, daß zwangsläufig weiter 'approximiert'
wird, da die $\begin{eqnarray*} a_i \end{eqnarray*}$ nur -1 oder 1 sein können (Bit =True oder Bit=False ) :

$\begin{eqnarray*} Q_4(x) = \frac{3}{2}*(16) -1*(4) -1*(2) + 1*(1)= 19 \end{eqnarray*}$

$\begin{eqnarray*} Q_5(x) = \frac{3}{2}*(16) -1*(4) -1*(2) + 1*(1) -1 *(1/2)= 18.5 \end{eqnarray*}$
...
('Fehler' von $\begin{eqnarray*} Q_4(x) \end{eqnarray*}$ wird immer weiter reduziert).

Ok, würde mich freuen falls jemand was dazu weiß! Wink

22.09.2008, 17:08

Airblader

Auf diesen Beitrag antworten »

Zur Konvergenz wären meine Überlegungen:

Prinzipiell steht da

$\begin{eqnarray*} \frac{3}{2}T + T\sum_{k=2}^\infty a_k\frac{1}{2^k} \end{eqnarray*}$

mit eben $\begin{eqnarray*} a_k \in \{-1;1\} \end{eqnarray*}$ .
Für die Konvergenz interessiert uns nur die Summe selbst, denn der Summand vorne dran ist so oder so endlich und ändert so nur den Reihenwert.

Bei bei den trivialen Fällen $\begin{eqnarray*} a_k = 1 \end{eqnarray*}$ und $\begin{eqnarray*} a_k = -1 \end{eqnarray*}$ konvergiert die Reihe offensichtlich, weil sie eine geometrische Reihe ist.

Bleibt der Fall, dass die Vorzeichen von $\begin{eqnarray*} a_k \end{eqnarray*}$ sich irgendwie ändern.
In diesen Fällen haben wir allerdings mit den oberen trivialen Fällen ein "Sandwich" - der Reihe bleibt also gar nichts anderes übrig, als zu konvergieren.

Edit: Was dann einfach etwas ausführlicher ist als Arthurs Halbsatz dazu Augenzwinkern

air

22.09.2008, 17:12

Auf diesen Beitrag antworten »

@Zeno-2

Du willst also die Koeffizienten $\begin{eqnarray*} a_i \end{eqnarray*}$ der Reihe so ermitteln, dass $\begin{eqnarray*} Q(x)=x \end{eqnarray*}$ - verstehe ich dich da richtig? Die Konvergenz selbst ist ja wegen der Majorisierung durch eine geometrische Reihe kein Thema.

Prinzipiell handelt es sich hier nur um eine "verschobene" Binärdarstellung:

Erstmal muss $\begin{eqnarray*} x \end{eqnarray*}$ positiv sein statt nur beliebig reell - das hast du wohl vergessen anzugeben.

Als nächstes, so wie $\begin{eqnarray*} T \end{eqnarray*}$ definiert ist, handelt es sich um die größte Zweierpotenz kleiner oder gleich $\begin{eqnarray*} x \end{eqnarray*}$ . Also ist $\begin{eqnarray*} \frac{x}{T} \end{eqnarray*}$ eine reelle Zahl aus dem Intervall $\begin{eqnarray*} [1, 2) \end{eqnarray*}$ .

Substituiert man nun in Hinblick auf die Binärdarstellung $\begin{eqnarray*} a_i = 2b_i-1 \end{eqnarray*}$ mit $\begin{eqnarray*} b_i\in\{0,1\} \end{eqnarray*}$ , so folgt

$\begin{eqnarray*} \frac{Q(x)}{T} = \frac{3}{2} + \sum_{i=0}^{\infty} \frac{2b_i-1}{2^{i+2}} =1 + \sum_{i=0}^{\infty} \frac{b_i}{2^{i+1}} \end{eqnarray*}$ .

Mit der Binärdarstellung rechts kann man alle reellen Zahlen des Intervalls $\begin{eqnarray*} [1,2) \end{eqnarray*}$ darstellen, mit Ausnahme der abzählbar endlich vielen Binärbrüche sogar eindeutig.

EDIT:

@Airblader

Ja, so isser der Arthur mit seinen Halbsätzen. Wenigstens haben wir mit unseren beiden Beiträgen weitgehend verschiedene Aspekte des Problems beleuchtet, womit beide ihren Sinn haben. Augenzwinkern

22.09.2008, 17:29

Zeno-2

Auf diesen Beitrag antworten »

Cool!

In Praxi kann x auch kleiner Null sein, sorry für die Ungenauigkeit.
Dann steht also auch vor dem ersten Term ein $\begin{eqnarray*} a_i \end{eqnarray*}$

Aber ansonsten ist das also 'nur' eine andere Schreibweise.
Hätt' ich auch selbst drauf kommen können geschockt

.

Vielen Dank! Tanzen

22.09.2008, 18:19

Airblader

Auf diesen Beitrag antworten »

Zitat:

Original von Zeno-2
In Praxi(s) kann x auch kleiner Null sein,

Und was ist mit dem Logarithmus im Exponenten von T? Wird da einfach nur |x| genommen und eben das von dir erwähnte Vorzeichen angepasst?

air

22.09.2008, 19:23

Zeno-2

Auf diesen Beitrag antworten »

Zitat:

Original von Airblader

Zitat:

Original von Zeno-2
In Praxi(s) kann x auch kleiner Null sein,

Und was ist mit dem Logarithmus im Exponenten von T? Wird da einfach nur |x| genommen und eben das von dir erwähnte Vorzeichen angepasst?

air

Ja. Hm.

Etwas besser wäre wohl gewesen:

$\begin{eqnarray*} x \in \mathbb R \end{eqnarray*}$

$\begin{eqnarray*} T = 2^{\lfloor log_2(|x|) \rfloor} \end{eqnarray*}$

$\begin{eqnarray*} Q(x) = a_0\frac{3}{2} T + a_1T/4 +a_2T/8 +a_3T/16... \end{eqnarray*}$

wobei

$\begin{eqnarray*} a_0 = sign(x) \end{eqnarray*}$
$\begin{eqnarray*} a_i \in \{1;-1\}, i=1,2,... \end{eqnarray*}$

Der Teufel

steckt im Detail....

Nochmals Danke! Freude

Neue Frage »

Antworten »

Diese Reihe....?

Verwandte Themen