Matroids Matheplanet Forum Index
Moderiert von Curufin epsilonkugel
Analysis » Folgen und Reihen » Rekursive Folge finden/herleiten
Autor
Universität/Hochschule Rekursive Folge finden/herleiten
LudwigM
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.11.2020
Mitteilungen: 14
  Themenstart: 2020-12-21

Hallo, \ Ich möchte herausfinden, wie man aus den folgenden ersten Gliedern die rekursive Folge a_k(x) mit k, n\in \IN und x>0 herausfinden kann: a_0 = 1 a_1 = - (nx-1) a_2 = (n+1)*x*(nx-2)+1 a_3 = -((n+2)*x*((n+1)*x*(nx-3)+3)-1) a_4 = ((n+3)*x*((n+2)*x*((n+1)*x*(nx-4)+6)-4)+1) ... Ein Muster ist hier schon zu sehen, allerdings kann ich es nicht in eine rekursive Folge übersetzen. Daher brauche ich hier Hilfe.


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5738
Wohnort: Berlin
  Beitrag No.1, eingetragen 2020-12-21

Was ist denn der Kontext, und kannst vielleicht noch die nächsten Folgenglieder nennen?


   Profil
Caban
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.09.2018
Mitteilungen: 1735
Wohnort: Brennpunkt einer Parabel
  Beitrag No.2, eingetragen 2020-12-21

Hallo Ich hätte folgenden Ansatz, stelle die zweite Gleichung nach x um uns setze das Ergebnis in die dritte Gleichung ein. Gruß Caban [Die Antwort wurde vor Beitrag No.1 begonnen.]


   Profil
ILoveMath3
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.11.2019
Mitteilungen: 89
  Beitrag No.3, eingetragen 2020-12-21

\ a_1 = -n*x+1 -> x = (1-a_1)/n Einsetzen in a_2: a_2 = (n+1)*((1-a_1)/n)*(n*(1-a_1)/n -2)+1 = (n+1)/n * (1-a_1)* (-1-a_1) +1 = -(n+1)/n * (1-(a_1)^2) +1 Somit krieg ich zumindest eine Beziehung zwischen a_2 und a_1; Sollte ich dasselbe für die 3. bzw. 4. Gleichung machen? Denn hieraus kann ich immer noch nicht sehen, wie die Folge aussehen soll. Für den Kontext: Wir haben die Funktion f(x) = (e^(-1/x)/x^n) gegeben. Man solle zeigen, dass es eine Polynomfunktion a_k(x) gibt, sodass die k-te Ableitung f^(k)(x) = f(x) * a_k(x)/x^2k sich so darstellen lässt. Durch Ableiten und Umformen auf diese Darstellung komme ich immer auf diese a_k's. Ich hab mithilfe eines Ableitungsrechners es mehrfach ableiten lassen, wobei dieser sogar diese in obere Darstellung vereinfacht, sodass ich die a_k's direkt ablesen kann. Das nächste Element wäre dementsprechend: a_5 = ((n+4)*x*((n+3)*x*((n+2)*x*((n+1)*x*(nx-5)+10)-10)+5)-1) Möglicherweise mach ich mir das Leben schwer, falls es einen anderen, leichteren Weg gibt..


   Profil
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1696
Wohnort: Bochum
  Beitrag No.4, eingetragen 2020-12-21

Hallo, könnte es sein, dass in der Aufgabe gar niemand verlangt, die $a_k$ explizit anzugeben/auszurechnen? Man kann das natürlich trotzdem wollen, aber möglicherweise ist das wirklich mühsam. Viele Grüße, haerter


   Profil
Caban
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 06.09.2018
Mitteilungen: 1735
Wohnort: Brennpunkt einer Parabel
  Beitrag No.5, eingetragen 2020-12-21

hallo Ich würde die Polynome einzeln aufschreiben und für jeden Parameter Vorschriften finden. Gruß Caban [Die Antwort wurde nach Beitrag No.3 begonnen.]


   Profil
LudwigM
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.11.2020
Mitteilungen: 14
  Beitrag No.6, vom Themenstarter, eingetragen 2020-12-21

\quoteon(2020-12-21 22:19 - Caban in Beitrag No. 5) hallo Ich würde die Polynome einzeln aufschreiben und für jeden Parameter Vorschriften finden. Gruß Caban [Die Antwort wurde nach Beitrag No.3 begonnen.] \quoteoff Was meinst du mit "Polynome" einzeln aufschreiben? Und ja, wir müssen die Folge explizit angeben. Sobald man die durch Ausprobieren heraus gefunden hat, sollte die k-te Ableitunng durch einen Induktionsbeweis letztendlich beweisbar sein (glaub ich).


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5738
Wohnort: Berlin
  Beitrag No.7, eingetragen 2020-12-21

\quoteon(2020-12-21 22:29 - LudwigM in Beitrag No. 6) Und ja, wir müssen die Folge explizit angeben. \quoteoff Das geht zumindest aus der (oben genannten) Aufgabenstellung nicht hervor. Die Aufgabe ist durch eine simple Induktion und Ableitungsregeln zu lösen.


   Profil
LudwigM
Junior Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 22.11.2020
Mitteilungen: 14
  Beitrag No.8, vom Themenstarter, eingetragen 2020-12-21

\quoteon(2020-12-21 22:31 - Triceratops in Beitrag No. 7) \quoteon(2020-12-21 22:29 - LudwigM in Beitrag No. 6) Und ja, wir müssen die Folge explizit angeben. \quoteoff Das geht zumindest aus der (oben genannten) Aufgabenstellung nicht hervor. Die Aufgabe ist durch eine simple Induktion und Ableitungsregeln zu lösen. \quoteoff Laut einem Tutor genügt es eine Rekursionsvorschrift (für die Folge) anzugeben - wenn ich's also richtig verstanden habe, muss also die Folge explizit angegeben werden Edit: \ Wenn man die Induktion durchführt, dann erhält man tatsächlich mühelos eine Rekursionsvorschrift für a_k(x), falls die Aussage tatsächlich stimmen sollte: a_(k+1) (x) = (1-nx-2kx)*a_k(x)+x^2*(a_k)'(x) Allerdings weiß ich nicht, ob das ein wirklicher Beweis ist, dass a_k(x) eine Polynomfunktion ist bzw. das fehlt eigentlich komplett. Wie baue ich das ein?


   Profil
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1696
Wohnort: Bochum
  Beitrag No.9, eingetragen 2020-12-22

Hallo, Meditier doch ein wenig über Dein "Edit". Da steht schon sehr viel, das Dir nur vielleicht noch nicht wirklich klar ist. Viele Grüße, haerter


   Profil
Triceratops
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 28.04.2016
Mitteilungen: 5738
Wohnort: Berlin
  Beitrag No.10, eingetragen 2020-12-22

Dass die so definierte Funktion $a_k$ ein Polynom ist, kannst du (wie gesagt) durch eine Induktion erkennen.


   Profil
Folgende Antworten hat der Fragesteller vermutlich noch nicht gesehen.
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.11, eingetragen 2020-12-23

Da a[5] im Beitrag 3 falsch ist und a[k]'(x) nur ein unfertiges Zwischenprodukt ..., habe ich das mal nachgerechnet: https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Reku_Polynom.PNG (mittlere Spalte ist die Ableitung des Vorgängers, also um 1 verschoben: a[k-1]'(x) ) Nur dank der FullSimplify Darstellung konnte ich erkennen, dass die Ableitung zum Teil bereits in a[k-1] enthalten ist: a[k]'(x) =k*(1 - k - n)*a[k - 1](x) Zusammen: a[1 + k](x) = a[k](x)*(1 - n*x - 2*k*x) + x^2*k*(1 - k - n)*a[k - 1](x) https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Reku_PolynomOhneAbleitung.PNG (eigenartig: nur bei k=3 hat FullSimplify 1- und dann innerhalb der Klammer wieder zurück-negiert, was aber den identischen Term ergibt) Dies lässt sich auch mit Hilfe von Mathematica nicht weiter explizit zusammenfassen. Ohne die Ableitung ginge es einfach mit der Pochhammer-Funktion. Vielleicht findet ja noch jemand was...


   Profil
haerter
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.11.2008
Mitteilungen: 1696
Wohnort: Bochum
  Beitrag No.12, eingetragen 2020-12-23

Hallo, ich möchte nochmal die Frage in den Raum werfen, ob es wirklich sinnvoll ist, die $a_k$ explizit zu bestimmen. Es geht doch eher darum, die angegebene Rekursionsvorschrift für die $a_k$ herzuleiten und sich klarzumachen, dass das alles Polynome sind. Ich würde da gerne dem Fragesteller (und auch dem Korrekteur/der Korrekteurin) möglicherweise unnötige Mühen ersparen... Viele Grüße, haerter


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.13, eingetragen 2020-12-23

Hallo haerter, natürlich will der eigentliche Aufgabensteller (meist Professor, der nur seine Standard-Aufgaben "an den Mann bringen will") keine explizite Funktion (wenn das nicht mal mathematica schafft). ABER ich mache Mathe als Hobby und interessiere mich für universelle Lösungen. Viele ungelöste Rekursionen lassen sich z.B. mit speziellen Funktionen wie Pochhammer, hypergeometrische Funktionen usw. darstellen. Zwar sind das genau genommen auch unendliche Summen, aber das sind trigonometrische Funktionen auch. Interessant sind jedoch die Laufzeiten, die bei rekursiven Algorithmen exponentiell schlechter werden. Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.14, eingetragen 2020-12-23

Wenn man z.B. den komplizierten Vorfaktor x^2*k*(1 - k - n) entfernt, gibt es eine explizite Lösung: \sourceon mathematica a[1 + k] == a[k]*(1 - n*x - 2*k*x) + a[k - 1] (*mit den Startbedingungen*) Out: {{a[k]->(BesselI[k-(1-n x)/(2 x),1/x] BesselK[-((1-n x)/(2 x)),-(1/x)]-n x BesselI[k-(1-n x)/(2 x),1/x] BesselK[-((1-n x)/(2 x)),-(1/x)]-BesselI[k-(1-n x)/(2 x),1/x] BesselK[1-(1-n x)/(2 x),-(1/x)]-BesselI[-((1-n x)/(2 x)),1/x] BesselK[k-(1-n x)/(2 x),-(1/x)]+n x BesselI[-((1-n x)/(2 x)),1/x] BesselK[k-(1-n x)/(2 x),-(1/x)]+BesselI[1-(1-n x)/(2 x),1/x] BesselK[k-(1-n x)/(2 x),-(1/x)])/(BesselI[1-(1-n x)/(2 x),1/x] BesselK[-((1-n x)/(2 x)),-(1/x)]-BesselI[-((1-n x)/(2 x)),1/x] BesselK[1-(1-n x)/(2 x),-(1/x)])}} ohne Startbedingung noch allgemeiner: a[k]->BesselI[k-(1-n x)/(2 x),1/x] *c1+BesselK[k-(1-n x)/(2 x),-(1/x)] *c2 \sourceoff


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.15, eingetragen 2020-12-24

\quoteon(2020-12-23 17:53 - hyperG in Beitrag No. 13) ... die bei rekursiven Algorithmen exponentiell schlechter werden. ... \quoteoff Das hat mich zwischen den Weihnachtstagen doch genauer interessiert. Zunächst muss beim praktischen Anwenden klar sein, dass es nicht einfach ein a[k] , sondern eine Funktion mit 3 Übergabeparametern ist: a[k,x,n] { denn x und n kommen nur bei "globalen Variablen" oder bei "Kopfrechnern" aus dem NICHTS daher} Nun habe ich 4 Algorithmen verglichen. Zunächst den langsamsten a1[k,x,n] mit Ableitung pro k: k < 13 liegt alles noch unter 1 s, aber schon bei k=16 schießen die Berechnungszeiten über 340 s hoch! Da ich nicht Jahre warten kann, hier eine gute Näherungsformel für die Wartezeit in s: 0.025662282950292 + 9.18140836168791*10^-8 E^(1.07298658724611 k^1.0900000000001) a2[k,x,n] nutzt die rekursive Formel aber ohne die langsame FullSimplify-Darstellung. Jedoch werden x & n erst nach Berechnung der Polynomfunktion bekannt gegeben. a3 gibt x & n schon vor der Rekursion bekannt. (mathematica kann intern schon x und n zu festen Zahlenwerten optimieren) a4 nutzt die interne DifferenceRoot-Function von mathematica (vermutlich analog a3) Hier nun der Beweis, dass man mit dem Ableitungs-Algorithmus selbst mit schnellen Computern nicht mal Funktionsparameter im mittleren 2stelligen Bereich praktisch berechnen kann: \sourceon mathematica n = 19; x = 31; k = 36; Ergebnisse: a1: mit Ableitung a'(x) berechnet 0.025662282950292 + 9.18140836168791*10^-8 E^(1.07298658724611 k^1.0900000000001) in 1.32871121904209*10^16 s = 421 Mio. Jahre a2: erst a[k-1](x) dann einsetzen 16572628380848160369936740318859738516379590729306807877130214299802721840104962288627719609887188994283075957 in 50.5853242 s a3: x,n bekannt, a[k-1]Rekursion: 16572628380848160369936740318859738516379590729306807877130214299802721840104962288627719609887188994283075957 in 0.*10^-8 s a4: DifferenceRoot-Function 16572628380848160369936740318859738516379590729306807877130214299802721840104962288627719609887188994283075957 in 0.*10^-8 s \sourceoff Interessant: das Ergebnis besteht nur aus 3 Primfaktoren: 7*103*22985614952632677350813786850013506957530639014295156556352585714012096865610211218623744257818570033679717 Der nächste Schritt wäre die Untersuchung von a3 und a4 bei k>100 und ob es nicht noch ein a5 gibt ... (aber nicht zu Heilig Abend! )


   Profil
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3249
  Beitrag No.16, eingetragen 2020-12-25

Hallo. \quoteon(2020-12-24 23:18 - hyperG in Beitrag Nr.15 schreibt ... Hier nun der Beweis, dass man mit dem Ableitungs-Algorithmus selbst mit schnellen Computern nicht mal Funktionsparameter im mittleren 2stelligen Bereich praktisch berechnen kann: ... \quoteoff \sourceon mathematica (* In *) ClearAll @ "Global`*" a[0, n_, x_] := 1 mem : a[k_, n_, x_] := mem = (1 - n* x - 2*k*x + 2 x)*a[k - 1, n, x] + x^2* D[a[k - 1, n, x] , x] // Expand // Collect[#, x] & a[1, n, x] a[4, n, x] rule = {n -> 19, x -> 31}; a[36, n, x] /. rule // AbsoluteTiming (* Out *) 1 - n x 1 + (-12 - 4 n) x + (36 + 30 n + 6 n^2) x^2 + (-24 - 44 n - 24 n^2 - 4 n^3) x^3 + (6 n + 11 n^2 + 6 n^3 + n^4) x^4 {0.126805, 1657262838084816036993674031885973851637959072930680787713021429980272\ 1840104962288627719609887188994283075957} \sourceoff Gruss endy


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.17, eingetragen 2020-12-25

Hallo endy, danke für den Hinweis mit // Expand // Collect (also Ableitung ohne Umweg von Zwischenformeln)! Damit kommt man schon bis k=300 in 60 s Ich habe nun die anderen Algorithmen weiter untersucht. Da bei k=10000 immer noch kaum messbare Unterschiede auftraten, aber die Ergebnisse in die Mio. Stellen gingen (also zu viel Zeit in überlange Zahlen floss und die Algorithmus-Unterschiede in den Hintergrund traten), habe ich n und x auf 2 und 3 verkleinert und k vergrößert. Erst ab k um 26000 gab es messbare Unterschiede! \sourceon mathematica n = 2; x = 3; k = 26001; Ergebnis 115911 stellige Zahl!!! a1 8.579158404473605*10^30228 Mio. Jahre (vorher RAM Überlauf!) a2 Jahre & RAM-Grenze, weil Zwischenformel zu lang wird a3 in 0.469 s Rekursion aus Beitrag 11 ohne FullSimplify a4 in 0.230 s DifferenceRoot-Function (schnellste Rekursion) a5 in 2.605 s Fold-Iteration/Rekursion a6 in 0.0747 s hyg1F1 & Pochhammer Explizit!!! a7 in 0.0649 s hyg1F1 Regular Explizit -> Sieger!!!! \sourceoff Unglaublich, was explizite Formeln hermachen. Theoretisch kann man damit auch reelle (oder sogar komplexe) Werte an die 3 Übergabeparameter (Argumente k, x, n) übergeben (dann natürlich meist langsamer oder hyg1F1 konvergiert nicht immer). Ich wette, dass der Professor, der die Aufgabe gestellt hat, nicht mal diese explizite Formel mit hypergeometrischen Funktionen kennt! Ich bereite das mal vor, wenn ich mehr Zeit habe. Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.18, eingetragen 2020-12-26

Tests der expliziten hypergeometrischen Funktion mit reellen Argumenten: \sourceon nameDerSprache a[k,x,n] /. {k->9.123456789,x->3.123456789,n->1.5123456789} Out: 6.64025429710725*10^9 funktioniert! \sourceoff Plot3D pro Bild funktioniert nur, wenn 1 von 3 Parametern konst.: a) normaler 3DPlot f(x,y) -> mit z konst. Funktionsergebnis ist 3. Dimension b) umgestellte f(x,y,z)= konst. {Kartesische Form (meist Kugeln)} Ich habe mal Variante a mit k=7...9 in Schrittweite 1/7 eingegeben, was 15 Bilder ergibt. Man könnte auch Film erstellen, wobei Parameter k zur Zeitkomponente t wird https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/rotate.gif https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Plot3D_hyg1F1Regular_k_x_n_veroeffentl.PNG


   Profil
endy
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 10.01.2011
Mitteilungen: 3249
  Beitrag No.19, eingetragen 2020-12-26

Hallo. \quoteon(2020-12-25 23:11 - hyperG in Beitrag No. 17) Hallo endy, danke für den Hinweis mit // Expand // Collect (also Ableitung ohne Umweg von Zwischenformeln)! .... \quoteoff FullSimplify bzw Collect und Expand sind nicht das Problem. Siehe \sourceon mathematica ClearAll @ "Global`*" b[0, n_, x_] := 1 b[k_, n_, x_] := (1 - n* x - 2*k*x + 2 x)*b[k - 1, n, x] + x^2* D[b[k - 1, n, x] , x] // Expand // Collect[#, x] & Information @ b b[1, n, x] b[4, n, x] Information @ b a[0, n_, x_] := 1 mem : a[k_, n_, x_] := mem = (1 - n* x - 2*k*x + 2 x)*a[k - 1, n, x] + x^2* D[a[k - 1, n, x] , x] // Expand // Collect[#, x] & Information @ a a[1, n, x] a[4, n, x] Information @ a \sourceoff Siehe Functions That Remember Values They Have Found Statt f[x_]:= f[x] = rhs kann man auch mem: f[x_]:= mem = rhs schreiben. mem für "Memorisation" dann weiss man was die Funktion tut. Gruss endy


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.20, eingetragen 2020-12-27

Unter Explizite-Algorithmen-einer-Rekursionsfunktion habe ich mal die expliziten Funktionen zusammengetragen. - natürlich geht das über die Fragestellung hinaus - natürlich wird das nicht von Studenten verlangt - natürlich werden wieder einige Leser hypergeometrische Funktionen nicht als "explizit" bezeichnen Aber die Erfolge bei Geschwindigkeit & Erweiterung der Argumente auf reelle Zahlen sprechen für sich. Da die Algorithmen doch sehr unterschiedlich sind und alle die selben Ergebnisse liefern, ist es auch eine gute Probe (Validierung). Grüße Gerd


   Profil
hyperG
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 03.02.2017
Mitteilungen: 1489
  Beitrag No.21, eingetragen 2021-01-07

https://matheplanet.com/matheplanet/nuke/html/uploads/b/47407_Hypergeometric1F1Regularized_-k_Pi.PNG Weitere Diagramme & mp4 Filme zu dieser expliziten Funktion mit 3 reellen Argumenten hier https://matheplanet.com/matheplanet/nuke/html/images/forum/subject/wink.gif


   Profil

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]