matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAnalysis des R1Rekursionsgleichung lösen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Analysis des R1" - Rekursionsgleichung lösen
Rekursionsgleichung lösen < eindimensional < reell < Analysis < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Rekursionsgleichung lösen: .. und beweisen
Status: (Frage) reagiert/warte auf Reaktion Status 
Datum: 18:55 Di 17.10.2017
Autor: pc_doctor

Aufgabe
Lösen Sie die folgenden Rekursionsgleichungen. Beweisen Sie jeweils die Richtigkeit ihrer Lösung (z.B. durch vollstände Induktion)

a)

T(1) = 0

T(n) = [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n    für n > 1

Sie dürfen annehmen, dass n eine Zweierpotenz ist.



Hallo,

ich habe Probleme bei dieser Aufgabe.

Also normale Rekursionsgleichungen mittels charak. Polynom ist eigentlich kein Problem, aber die Gaußklammern stören mich etwas.

Ich habe mal testweise Werte eingesetzt, um ein System zu erkennn, doch vergebens:

T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2
T(3) = 5
T(4) = 8

T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24

T(9)  = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59

Ich erkenne, dass für n  = 2,3 und 4 die Differenz immer 3 beträgt

von n = 5 bis 8 ist die Differenz 4

und ab n = 8 bis ?? ist die Differenz 5

Ich werde aber daraus nicht schlau. Oder gibt es einen anderen Ansatz?

Ich würde mich über einen Tipp freuen.

Vielen Dank im Voraus.


        
Bezug
Rekursionsgleichung lösen: Tipp
Status: (Antwort) fertig Status 
Datum: 20:48 Di 17.10.2017
Autor: HJKweseleit

Du solltest den Zahlenwert von [mm] \lfloor log_2(n)\rfloor [/mm] betrachten.

Damit kannst du einerseits die sich ändernden Stufenabstande in den Griff bekommen und andererseits eine Korrektur zu den richtigen Werten finden (dazu brauchst du dann aber [mm] 2^{\lfloor log_2(n)\rfloor}). [/mm]

Bezug
                
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:58 Di 17.10.2017
Autor: pc_doctor

Danke für den Tipp, mit dem komme ich weiter!

Bezug
                
Bezug
Rekursionsgleichung lösen: Neuer Anlauf
Status: (Frage) beantwortet Status 
Datum: 19:35 So 22.10.2017
Autor: pc_doctor

Hallo,

ich habe mal bisschen anders gerechnet, um die Rekursionsgleichung zu lösen. Ich komme auf log(n), allerdings fehlt da etwas, aber ich weiß nicht was.

Also wir hatten:

T(1) = 0 , das ist der Anker


T(n) = $ [mm] T(\lfloor\bruch{n}{2}\rfloor) [/mm] $ + $ [mm] T(\lceil\bruch{n}{2}\rceil) [/mm] $ +n   für n > 1

Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also so aussieht n = [mm] 2^{a} [/mm] , a [mm] \in \IN [/mm]

Damit ändert sich T(n) zu:

T(n) = [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{2} [/mm] + n , für n > 1, n Zweierpotenz.

So, dann versuche ich die Rekursionsgleichung aufzulösen, indem ich immer rekursiv einsetze. Ich setze jetzt also [mm] \bruch{n}{2} [/mm] ein für den Anfang.


[mm] T(\bruch{n}{2}) [/mm] = [mm] T(\bruch{n}{4}) [/mm] + [mm] T(\bruch{n}{4}) [/mm] + n + [mm] \bruch{n}{2} [/mm]

Jetzt setzen wir [mm] \bruch{n}{4} [/mm] ein

[mm] T(\bruch{n}{4}) [/mm] = [mm] T(\bruch{n}{8}) [/mm] + [mm] T(\bruch{n}{8}) [/mm] + n + [mm] \bruch{n}{2} [/mm] + [mm] \bruch{n}{4} [/mm]

=
..

= [mm] T(\bruch{n}{2^k}) [/mm] +  [mm] T(\bruch{n}{2^k}) [/mm]  + [mm] \summe_{i=0}^{k} \bruch{n}{2^k} [/mm]

So, so sieht wohl die Rekursion für k Schritte aus.

Wir setzen [mm] \bruch{n}{2^k} [/mm] = 1
Formen nach k um:

k = [mm] log_2(n) [/mm]  mit k [mm] \le log_2(n) [/mm]

Naja, daraus folgt:

[mm] T(\bruch{n}{2^k}) [/mm] = T(1) = 0

Jetzt müssen wir ja k in die Summe einsetzen, k ist ja k = [mm] log_2(n) [/mm]

Aus der Summe wird nun also [mm] \summe_{i=0}^{log_2(n)} \bruch{n}{2^{log_2(n)}} [/mm] und das ist gleich


[mm] \summe_{i=0}^{log_2(n)} [/mm] 1 = [mm] log_2(n) [/mm] + 1 ( laut Wolframalpha ? )


Also erhalten wir

T(n) = T(1)+ T(1) + [mm] log_2(n) [/mm] +1
T(n) = 0+0+ [mm] log_2(n) [/mm] +1 = [mm] log_2(n) [/mm] +1

Das funktioniert aber irgednwie nicht, wenn ich Testeinsetzungen mache. Wo ist mein Fehler ?

Bezug
                        
Bezug
Rekursionsgleichung lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 20:29 So 22.10.2017
Autor: HJKweseleit


> Hallo,
>  
> ich habe mal bisschen anders gerechnet, um die
> Rekursionsgleichung zu lösen. Ich komme auf log(n),
> allerdings fehlt da etwas, aber ich weiß nicht was.
>  
> Also wir hatten:
>  
> T(1) = 0 , das ist der Anker
>  
>
> T(n) = [mm]T(\lfloor\bruch{n}{2}\rfloor)[/mm] +
> [mm]T(\lceil\bruch{n}{2}\rceil)[/mm] +n   für n > 1
>  
> Da wir annehmen dürfen, dass n eine Zweierpotenz ist, also
> so aussieht n = [mm]2^{a}[/mm] , a [mm]\in \IN[/mm]
>  



Sorry, aber ich hatte bei meinem Tipp vergessen, dich auf Folgendes aufmerksam zu machen:

n=Zweierpotenz ist völlig unsinnig, wenn n die natürlichen Zahlen durchlaufen soll.

Wenn T nur für Zweierpotenzen definiert werden soll, müsste es heißen:

T(1)=0

[mm] T(2^n)=[/mm] [mm]T(\lfloor\bruch{2^n}{2}\rfloor)[/mm] + [mm]T(\lceil\bruch{2^n}{2}\rceil)[/mm] [mm] +2^n [/mm]
= [mm]T(2^{n-1})[/mm] + [mm]T(2^{n-1})[/mm] [mm] +2^n [/mm] = [mm]2*T(2^{n-1})[/mm]  [mm] +2^n. [/mm]


Man würde also immer nur 2-er-Potenzen addieren.
T(3), T(5),... wären gar nicht definiert, und das Ergebnis wäre auch trivial. Es wäre [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung damit sinnlos.


Nehmen wir an, es wäre doch so gemeint, wie es sich anhört. Wenn n eine Zweierpotenz wäre, wäre [mm] \bruch{n}{2} [/mm] ganzzahlig und damit [mm]\lfloor\bruch{n}{2}\rfloor[/mm] = [mm]\lceil\bruch{n}{2}\rceil[/mm], die Unterscheidung gäbe, wie in meinem obigen Gesagten, wieder keinen Sinn.

Was müsste man nun für n=7 rechnen? [mm]\lfloor\bruch{n}{2}\rfloor[/mm]=3, [mm]\lceil\bruch{n}{2}\rceil[/mm]=4, und dann 7 addieren? 7 ist aber keine 2-er-Potenz, n sollte aber eine sein!

Man merkt, dass die Bemerkung so unsinnig ist. Sie hätte heißen müssen:
Hinweis: Betrachten sie die 2-er-Potenzen, zwischen denen n liegt.
Dann wäre man auch sehr schnell auf die Funktion [mm] log_2 [/mm] gestoßen...

Bezug
                                
Bezug
Rekursionsgleichung lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:34 So 22.10.2017
Autor: pc_doctor

Danke für die Antwort.

Sofern ich weiß, soll davon ausgegangen werden, dass n eine Zweierpotenz ist. Nehmen wir an, als geschlossene Formel kommt [mm] log_2(n) [/mm] raus, dann wäre dieser Logarithmus für nicht-Zweierpotenzen nicht definiert, habe ich das richtig verstanden?

Bezug
                                        
Bezug
Rekursionsgleichung lösen: Korrigiert
Status: (Antwort) fertig Status 
Datum: 15:15 Mo 23.10.2017
Autor: HJKweseleit

Natürlich ist [mm] log_2(n) [/mm] für alle n definiert.

Ich schreibe mal auf, was ich für die von dir gebildete Reihe herausgefunden habe.

T(1) = 0 ( Rekursionsanker )
-------
T(2) = 2

T(3) = 5
T(4) = 8

T(5) = 12
T(6) = 16
T(7) = 20
T(8) = 24

T(9)  = 29
T(10) = 34
T(11) = 39
T(12) = 44
T(13) = 49
T(14) = 54
T(15) = 59
T(16) = 64

T(17) = 70

Die einzelnen Abschnitte bilden jeweils für sich eine arithmetische Folge und sind damit beschreibbar durch jeweils eine lineare Funktion der Form y=a*x+b, wobei a und b jeweils angepasst werden müssen. An den Nahtstellen kommt es zu überlappungen, die 8 kann man auch schon zur nächsten Reihe zählen, ebenso 24 und 64.

Man erhält so die Funktionen

y = 2x - 2      für x = 1   bis 2             mit [mm]\lfloor log_2(x) \rfloor[/mm]= 0
y = 3x - 4      für x von 2 bis 4 3           mit [mm]\lfloor log_2(x) \rfloor[/mm]= 1
y = 4x - 8      für x von 4 bis 8 7           mit [mm]\lfloor log_2(x) \rfloor[/mm]= 2
y = 5x - 16     für x von 8 bis 16 15         mit [mm]\lfloor log_2(x) \rfloor[/mm]= 3
y = 6x - 32     für x von 16 bis 32 31        mit [mm]\lfloor log_2(x) \rfloor[/mm]= 4
usw.

Allgemein erkennt man: Der Faktor a ist [mm]\lfloor log_2(x) \rfloor[/mm]  + 2, der Summand b ist [mm]-2^{\lfloor log_2(x) \rfloor+1}[/mm],

Somit [mm]T(n)=(\lfloor log_2(n) \rfloor \red{+} 2)*x - 2^{\lfloor log_2(x) \rfloor+1 [/mm]

Viel Spass beim Beweis durch vollständige Induktion ...


Bezug
                                                
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 19:59 Mo 23.10.2017
Autor: pc_doctor

Hallo nochmal,

vielen Dank für die Antwort.

Oh man, das kann ja mal was werden mit der Induktion. Ich versuche es :)

Bezug
                                                        
Bezug
Rekursionsgleichung lösen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 21:39 Mo 23.10.2017
Autor: HJKweseleit

Sorry, habe noch einen Schreibfehler gehabt und ihn nun mit rot korrigiert.

Bezug
                
Bezug
Rekursionsgleichung lösen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 11:04 Do 26.10.2017
Autor: vancouver

Hallo,
darf ich fragen wie du auf $ [mm] \lfloor log_2(n)\rfloor [/mm] $ gekommen bist?
LG

Bezug
                        
Bezug
Rekursionsgleichung lösen: Antwort
Status: (Antwort) fertig Status 
Datum: 21:29 Do 26.10.2017
Autor: HJKweseleit

Der Wechsel bei den Abständen der Folgeglieder geschieht immer an einer Zweierpotenz, also bei n = 2, 4, 8, 16,...
Somit brauche ich die Information, zu welchem Abschnitt z.B. die 10 gehört. [mm] 2^3\le 10<2^4. [/mm] somit muss mir die 10 irgendwie den Exponenten 3 liefern, und alle Zahlen zwischen 8 und 15 ebenfalls.

Der [mm] log_2(n) [/mm] fragt: [mm] 2^{wieviel}=n, [/mm] und so kommt für die Zahlen von 8 bis 15 der Wert 3,... heraus, den ich dann abrunde.

Den [mm] log_2 [/mm] von x bekommst du, indem du einen beliebigen log (z.B. ln oder lg=log_10) nimmst und den Wert durch log(2) dividierst, wobei log(2) mit dem selben log genommen werden muss. Also:

[mm] log_2(x)=\bruch{ln(x)}{ln(2)}=\bruch{lg(x)}{lg(2)}=\bruch{log_5(x)}{log_5(2)}=... [/mm]

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Analysis des R1"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


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