www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Folgen und Reihen" - Rekursion,expliziteDarstellung
Rekursion,expliziteDarstellung < Folgen und Reihen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursion,expliziteDarstellung: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 17:02 Mo 06.04.2015
Autor: sissile

Aufgabe
Bezüglich eines Beweises zur Biejkivität von [0,1] zu ]0,1[ brauche ich eine explizite Darstellung von der Folge:
[mm] x_0=1 [/mm]
[mm] x_{n+1} [/mm] = [mm] \frac{x_n}{2} [/mm] + [mm] \frac{1}{4} [/mm]
und von der Folge mit selber Rekursionsvorschrift aber mit Anfangswert [mm] x_0=0 [/mm]
Im Skript steht [mm] x_n =\frac{1}{2} [/mm] + [mm] \frac{1}{2^{n+1}} [/mm] bzw. [mm] x_n=\frac{1}{2} [/mm] - [mm] \frac{1}{2^{n+1}}, [/mm] wie komme ich am schnellsten auf diese Darstellung?

Hallo,
Ich habe mir einige Folgenglieder angeschaut: [mm] x_0=1, x_1= [/mm] 1/4, [mm] x_2 [/mm] = 3/4, [mm] x_3=5/8 [/mm]  sowie versucht die Rekursionsvorschrift ineinander zu schachteln aber wie findet man da eine allgemeine Form ohne viel herumzubasteln?

Über einen Tipp wäre ich dankbar!
LG,
sissi

        
Bezug
Rekursion,expliziteDarstellung: Antwort
Status: (Antwort) fertig Status 
Datum: 19:05 Mo 06.04.2015
Autor: Marcel

Hallo Sissile,

vorweg: In dem rotmarkierten Teil wird sicher ein Fehler sein. Vielleicht
findet und korrigiert den ja jemand?

Für Dich: Scrolle einfach solange nach unten, bis nichts rotes mehr da
steht. Eigentlich sind es dann nur ein paar Zeilen, die für Dich interessant
sind!

> Bezüglich eines Beweises zur Biejkivität von [0,1] zu
> ]0,1[ brauche ich eine explizite Darstellung von der
> Folge:
>  [mm]x_0=1[/mm]
>  [mm]x_{n+1}[/mm] = [mm]\frac{x_n}{2}[/mm] + [mm]\frac{1}{4}[/mm]
>  und von der Folge mit selber Rekursionsvorschrift aber mit
> Anfangswert [mm]x_0=0[/mm]
>  Im Skript steht [mm]x_n =\frac{1}{2}[/mm] + [mm]\frac{1}{2^{n+1}}[/mm] bzw.
> [mm]x_n=\frac{1}{2}[/mm] - [mm]\frac{1}{2^{n+1}},[/mm] wie komme ich am
> schnellsten auf diese Darstellung?


Ich habe mich gerade mit der sogenannten z-Transformation beschäftigt,
damit wird das Ganze ziemlich schön:
Setze (mit [mm] $x_k=0$ [/mm] für alle $k [mm] \le [/mm] 0$)

    [mm] $Y(z):=\sum_{k=-\infty}^\infty x_k z^{-k}\,,$ [/mm]

dann geht

    [mm] $x_{n+1}=\frac{x_n}{2}+\frac{1}{4}$ [/mm]

über in

    [mm] $\frac{1}{z}Y(z)=\frac{1}{2}Y(z)+\frac{1}{4}\sum_{k=1}^\infty (1/z)^k$, [/mm]

also

    [mm] $\frac{1}{z}Y(z)=\frac{1}{2}Y(z)+\frac{1}{4}*\frac{1/z}{1-\frac{1}{z}}$ [/mm]

bzw.

    [mm] $\frac{1}{z}Y(z)=\frac{1}{2}Y(z)+\frac{1}{4}*\frac{1}{z-1}$ [/mm]

bzw.

    [mm] $(2-z)*Y(z)=\frac{1}{2}*\frac{z}{z-1}\,.$ [/mm]

Also

    [mm] $Y(z)=\frac{-1}{2}*\frac{z}{(z-1)*(z-2)}\,.$ [/mm]

Schreibe

    [mm] $\frac{z}{(z-1)*(z-2)}=\frac{A}{z-1}+\frac{B}{z-2}\,,$ [/mm]

dann folgt aus

    $A(z-2)+B(z-1) [mm] \stackrel{!}{\equiv} [/mm] z$,

dass [mm] $A+B=1\,$ [/mm] und [mm] $2A+B=0\,.$ [/mm] Also

    [mm] $A=-1\,$ [/mm] und [mm] $B=2\,,$ [/mm]

also

    [mm] $Y(z)=\frac{-1}{2}*\left(\frac{-1}{z-1}+\frac{2}{z-2}\right)$ [/mm]

    [mm] $=\frac{-1}{2z}*\left((-1)*\frac{z}{z-1}+2*\frac{z}{z-2}\right)$ [/mm]

    [mm] $=\frac{-1}{2z}*\left((-1)*\sum_{k=0}^\infty z^{-k}+2*\sum_{k=0}^\infty \left(\frac{2}{z}\right)^{k}\right)$ [/mm]

    [mm] $=\sum_{k=1}^\infty \left\{\frac{1}{2}\;-\;2^{k+1}\right\}z^{-k}$ [/mm]

Mhm.... irgendwo werde ich mich wohl verrechnet haben. Wie gesagt: Ich hoffe,
jemand korrigiert das vielleicht mal...


Daher mal eine andere Idee:
Es gilt für

    [mm] $x_{n+1}=\frac{x_n}{2}+\frac{1}{4}$: [/mm]

* [mm] $x_1=\frac{1}{4}+\frac{x_0}{2}$ [/mm]

* [mm] $x_2=\frac{1}{4}+\frac{x_1}{2}=\frac{1}{4}+\frac{1}{2}*\left(\frac{1}{4}+\frac{x_0}{2}\right)=\frac{1}{4}*(1+\tfrac{1}{2})+\frac{x_0}{4}$ [/mm]
    
* [mm] $x_3=\frac{1}{4}+\frac{1}{2}*x_2=\frac{1}{4}+\frac{1}{4}*(\tfrac{1}{2}+\tfrac{1}{4})+x_0/8=\frac{1}{4}\sum_{k=0}^{\red{3-1}} \left(\frac{1}{2}\right)^k+\frac{x_0}{2^3}$ [/mm]

Die letzte Darstellung sollte Dir helfen!

Gruß,
  Marcel

>  Hallo,
>  Ich habe mir einige Folgenglieder angeschaut: [mm]x_0=1, x_1=[/mm]
> 1/4, [mm]x_2[/mm] = 3/4, [mm]x_3=5/8[/mm]  

Rein zu Testzwecken habe ich mal gerechnet: Für [mm] $n=3\,$ [/mm] ist

    [mm] $x_n=x_3=\frac{1}{4}*\frac{2^{n}-1}{2^{n}}*2+\frac{x_0}{2^n}=\frac{1}{2}*\left(1-\frac{1}{2^{n}}\right)+\frac{x_0}{2^n}$ [/mm]

Bei Dir ist ja [mm] $x_0=1,$ [/mm] damit

    [mm] $x_n=x_3=\frac{1}{2}-\frac{1}{2^{n+1}}+\frac{1}{2^n}=\frac{1}{2}+\frac{1}{2^{n+1}}=\frac{1}{2}+\frac{1}{2^4}=\frac{9}{16}$ [/mm]

Deine ersten Folgenglieder stimmen übrigens nicht, denn es ist schon

    [mm] $x_0=1$ [/mm]

    [mm] $\Longrightarrow$ $x_1=\frac{1}{4}+\frac{x_0}{2}=\frac{1}{4}+\frac{1}{2}=\frac{3}{4}$, [/mm]

Du hattest aber [mm] $x_1=1/4$ [/mm] behauptet...

Gruß,
  Marcel

> sowie versucht die
> Rekursionsvorschrift ineinander zu schachteln aber wie
> findet man da eine allgemeine Form ohne viel
> herumzubasteln?
>  
> Über einen Tipp wäre ich dankbar!
>  LG,
>  sissi


Bezug
                
Bezug
Rekursion,expliziteDarstellung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:45 Mo 06.04.2015
Autor: sissile

Vielen lieben Dank, der Teil der für mich bestimmt war hat mich schnell zur Lösung geführt [mm] x_n [/mm] = [mm] \frac{1}{4}\sum_{k=0}^{n-1} (\frac{1}{2})^k [/mm] + [mm] \frac{x_0}{2^n} [/mm] die ich durch Induktion bewiesen habe und die mich anschließend mit der Formel der geoemtrischen Summe zu der Lösung im Skriptum brachte.

LG,
sissi

Bezug
                        
Bezug
Rekursion,expliziteDarstellung: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:51 Mo 06.04.2015
Autor: Marcel

Hallo Sissile,

> Vielen lieben Dank, der Teil der für mich bestimmt war hat
> mich schnell zur Lösung geführt [mm]x_n[/mm] =
> [mm]\frac{1}{4}\sum_{k=0}^{n-1} (\frac{1}{2})^k[/mm] +
> [mm]\frac{x_0}{2^n}[/mm] die ich durch Induktion bewiesen habe

genau: Konstruktiv motiviert habe ich sie ja quasi (im Prinzip *sieht* man
dabei ja, dass diese Formel rauskommt; um ganz sicher zu gehen und um
möglichst *sauber* zu arbeiten, hast Du es genau richtig gemacht: Beweis
per Induktion!).

> und die mich anschließend mit der Formel der geoemtrischen
> Summe zu der Lösung im Skriptum brachte.

[ok]

Dennoch hier der Hinweis: In Büchern zur Signaltheorie steht gerne (oder
gar immer?) drin, dass man viele Rekursionsformeln für Folgen etwa mit
der z-Transformation in eine explizite Darstellung bringen kann.

Ich bin da aber wohl ein typischer *Verrechner*; denn schon zum zweiten
Mal habe ich mich bei diesem Weg wohl verrechnet.

Aber wenn Du mal Zeit und Lust hast oder es später mal brauchst: Schlag'
es einfach mal nach, ich denke, jeder, der Analysis I-II (notfalls I bis IV) gehört
hat, sollte das Prinzip dabei schnell verstehen. Im Endeffekt wird man da
auch einen Identitätssatz anwenden, der aber bei *Praktikern* wohl keiner
oder selten einer Erwähnung *bedarf*; zu wissen, dass sie einfach einen
"Koeffizientenvergleich" 'machen dürfen', reicht dann wohl. ;-)

Gruß,
  Marcel

Bezug
                
Bezug
Rekursion,expliziteDarstellung: Ansatzfehler gefunden
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 23:33 Di 07.04.2015
Autor: Marcel

Hallo,

> Hallo Sissile,
>  
> vorweg: In dem rotmarkierten Teil wird sicher ein Fehler
> sein. Vielleicht
> findet und korrigiert den ja jemand?
>  
> Für Dich: Scrolle einfach solange nach unten, bis nichts
> rotes mehr da
> steht. Eigentlich sind es dann nur ein paar Zeilen, die
> für Dich interessant
>  sind!
>  
> > Bezüglich eines Beweises zur Biejkivität von [0,1] zu
> > ]0,1[ brauche ich eine explizite Darstellung von der
> > Folge:
>  >  [mm]x_0=1[/mm]
>  >  [mm]x_{n+1}[/mm] = [mm]\frac{x_n}{2}[/mm] + [mm]\frac{1}{4}[/mm]
>  >  und von der Folge mit selber Rekursionsvorschrift aber
> mit
> > Anfangswert [mm]x_0=0[/mm]
>  >  Im Skript steht [mm]x_n =\frac{1}{2}[/mm] + [mm]\frac{1}{2^{n+1}}[/mm]
> bzw.
> > [mm]x_n=\frac{1}{2}[/mm] - [mm]\frac{1}{2^{n+1}},[/mm] wie komme ich am
> > schnellsten auf diese Darstellung?

ich hatte einen Ansatzfehler:

Es ist

    [mm] $y[k+1]=[y_k]/2\,+\,x[k+1]$ [/mm] ($k [mm] \in \IN_0$) [/mm]

mit [mm] $y[0]=x[0]=x_0$ [/mm] und $x[k]=1/4$ für $k [mm] \in \IN$. [/mm]

Dann folgt mit [mm] $Y(z):=\sum_{k=-\infty}^\infty y[k]z^{-\,k}$ [/mm]

    $z*Y(z) [mm] \equiv \frac{1}{2}Y(z)+\sum_{k=-\infty}^\infty x[k+1]z^{-\,k}$ [/mm]

und damit

    $z*Y(z) [mm] \equiv \frac{1}{2}Y(z)\,+\,\sum_{k=-\infty}^\infty x[k]z^{-\,k\,+1}\,,$ [/mm]

also

    $z*Y(z) [mm] \equiv \frac{1}{2}Y(z)\,+\,z\,x_0+z*\sum_{k=1}^\infty x[k]*z^{-k}$ [/mm]

Vermutlich wird da immer noch irgendwo ein Fehler sein - oder beim
Weiterrechnen habe ich mich wieder verrechnet, aber wenigstens kam
ich so auf eine Formel, die wenigstens einigermaßen sinnvoll war (nicht
mit [mm] $2^n$'s, [/mm] sondern [mm] $2^{\red{-}\,n}$'s). [/mm]

Vielleicht kann ja jemand mal versuchen, mit der z-Transformation das
vorzurechnen; denn ich verzettel mich da anscheinend permanent. ^^

Interessant wäre es aber schon. :-)

P.S. Eventuell ist auch einfach oben im Ansatz irgendwo ein kleiner Fehler,
den ich schon immer und immer wieder übersehe. Daher bitte am Besten
nicht einfach nur Abschreiben. ;-)

Gruß,
  Marcel

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Folgen und Reihen"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]