Mathematik: Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung
Released by matroid on Di. 24. Januar 2017 00:01:06 [Statistics]
Written by trunx - 818 x read [Outline] Printable version Printer-friendly version -  Choose language   
Mathematik

\(\begingroup\)\(\usepackage{setspace}\)

Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung

Von rekursiv gegebenen Zahlenfolgen c_{n+1} = f(c_0,\cdots,c_n;n) ist oft eine allgemeine Darstellung c_n =g(n) gesucht. Diese ist für lineare Rekursionsgleichungen, also für f(c_0,\cdots,c_n;n) - linear, berechenbar, ich habe dies hier ausführlich besprochen. Ist dagegen f(c_0,\cdots,c_n;n) nichtlinear, so ist in aller Regel eine allgemeine Darstellung nicht möglich. Mehr noch, ich bin erstaunt, dass es tatsächlich nichtlineare Rekursionen gibt, die allgemein darstellbar sind. Darum soll es in diesem Artikel gehen. Konkret geht es um folgende Klasse von Rekursionen (dem altbekannten Heron-Verfahren zur Ermittlung von \sqrt{a}): \displaystyle c_{n+1} = \frac{1}{2} \Bigl(c_n +\frac{a}{c_n}\Bigr) mit a, c_i \neq 0 \in \mathds{Q}.

1. Allgemeine Lösung für Nichtquadratzahlen a>0

Ausgangspunkt ist folgender Einfall, der im Prinzip bereits alles Weitere vorweg nimmt: Wir setzen für \displaystyle c_0=\sqrt{a} \, \frac{y+x}{y-x} und erhalten für \displaystyle c_1=\sqrt{a} \, \frac{y^2+x^2}{y^2-x^2} und weiter \displaystyle c_2=\sqrt{a} \, \frac{y^4+x^4}{y^4-x^4} bzw. \displaystyle c_n=\sqrt{a} \, \frac{y^{2^n}+x^{2^n}}{y^{2^n}-x^{2^n}}. Wie gesagt, das ist praktisch schon die Lösung; wir setzen nun zunächst y=1 (aber siehe weiter unten) und erhalten \displaystyle c_n=\sqrt{a} \, \frac{1+x^{2^n}}{1-x^{2^n}}. Jetzt müssen wir noch x ermitteln. Wir setzen x=A+B\sqrt{a} an, da \sqrt{a} im Gegensatz zu a, c_n, wegen der Eigenschaft von a kein Quadrat zu sein, nicht in \mathds{Q} liegt. Sprich wir gehen hier über die einfache Körpererweiterung \mathds{Q}(\sqrt{a}). Damit erhalten wir zunächst für \displaystyle c_0=\sqrt{a}\,\frac{1+A+B\sqrt{a}}{1-A-B\sqrt{a}}=\frac{2aB+(aB^2+1-A^2)\sqrt{a}}{(1-A)^2-aB^2}. Da c_0 \in \mathds{Q}, muss aB^2+1-A^2=0 bzw. A^2-aB^2=1 sein. Letzte Gleichung ist die sog. Pellsche Gleichung. Es ist also \displaystyle c_0=\frac{aB}{1-A} mit der Nebenbedingung A^2-aB^2=1. Oft wird gesagt, dass man für das Heron-Verfahren ein geeignetes c_0 wählen soll und schon immer stellte sich (mir zumindest), ob und wie man dieses "Geeignet-Sein" genauer schon vor dem Ausprobieren ermitteln kann. Das ist jetzt möglich. A und B werden nun konkret aus der Kettenbruchentwicklung für \sqrt{a} ermittelt. Diese besteht unter den angegebenen Bedingungen für a aus einer Vorperiode und der eigentlichen Periode. Bricht man diesen unendlichen Kettenbruch nach einigen Schritten ab, so entstehen rationale Näherungen für \sqrt{a}. Und unter diesen Brüchen wiederum gibt es eine Vielzahl, deren Zähler und Nenner die Pellsche Gleichung A^2-aB^2=1 erfüllen. Der größte Bruch (oder der mit dem kleinsten Zähler bzw. Nenner), der die Pellsche Gleichung erfüllt, liefert als \frac{\abs{A}}{\abs{B}} die Beträge der gesuchten Zahlen. Daraus lassen sich 4 Paare bilden (\pm A,\pm B) unter denen letztlich A=\abs{A} und B=-\abs{B} die gesuchten Lösungen sind. Beispiel a=7: Wie man sieht, ist a kein Quadrat, die Kettenbruchentwicklung von \sqrt{7}=[2;{\overline {1,1,1,4}}] und die ersten Näherungen lauten 2=\frac{2}{1}, 3=\frac{3}{1}, \frac{5}{2}, \frac{8}{3}, \frac{37}{14}, ... Erstmalig erfüllt davon \frac{8}{3} die Pellsche Gleichung (8^2-7\cdot3^2=1), die gesuchten Zahlen wären demnach A=8 und B=-3. Damit ist das "geeignete" c_0=3 und allgemein \displaystyle c_n=\sqrt{7} \, \frac{1+(8-3\sqrt{7})^{2^n}}{1-(8-3\sqrt{7})^{2^n}}. Alle diese c_n sind rational, also enthalten keine Wurzel. Bemerkenswert ist, dass diese Brüche eine Teilfolge der Näherungsbrüche der zugehörigen Kettenbruchentwicklung bilden (weshalb mir die Lösbarkeit erst aufgefallen ist). Die jeweilige Bedingung aber für das Verschwinden der Wurzel, also die jeweilige Pellsche Gleichung, enthält stets eine genauere Näherung für die Wurzel. Im Beispiel starten wir mit c_0=3, aber kennen schon \frac{8}{3}. Es folgt c_1=\frac{8}{3}, aber dafür nutzen wir 127^2-7\cdot48^2=1, sprich die bessere Näherung wäre hier \sqrt{7}\approx\frac{127}{48}, die erst im nächsten Schritt als c_2 folgt usw. Im übrigen sieht man sehr schön das Konvergenzverhalten dieser Folge (und des Verfahrens). Man kann natürlich einwenden, dass für das "geeignete" c_0 bereits die Lösung von \sqrt{a}, nämlich in Form des Kettenbruchs benutzt wird, also c_0 frei wählbar bleiben soll. Für diesen Fall bilden die beiden Gleichungen I \displaystyle c_0=\frac{aB}{1-A} und II A^2-aB^2=1 ein Gleichungssystem für A und B. Sie ergeben die quadratische Gleichung (a-c_0^2)A^2+2c_0^2A-(a+c_0^2)=0 mit der Lösung \displaystyle A=-\frac{a+c_0^2}{a-c_0^2} und entsprechendem \displaystyle B=\frac{2c_0^2}{a-c_0^2} (die triviale Lösung A=1 entfällt wegen Gleichung I). Hierbei ist es für die Allgemeingültigkeit allerdings sinnvoll, dass \mathds{K}=\mathds{R} gesetzt wird. Wählt man aber insbesondere dann doch c_0^2 so, dass a-c_0^2 \in \mathds{Q} (bzw. c_0^2-a \in \mathds{Q}) liegt, dann wäre nun y=a-c_0^2 (bzw. y=c_0^2-a) und x=-(a+c_0^2)+2c_0\sqrt{a} (bzw. x=a+c_0^2-2c_0\sqrt{a}). Also alles in allem \displaystyle c_n=\sqrt{a} \, \frac{(a-c_0^2)^{2^n}+(-(a+c_0^2)+2c_0\sqrt{a})^{2^n}}{(a-c_0^2)^{2^n}-(-(a+c_0^2)+2c_0\sqrt{a})^{2^n}} (bzw. \displaystyle c_n=\sqrt{a} \, \frac{(c_0^2-a)^{2^n}+(a+c_0^2-2c_0\sqrt{a})^{2^n}}{(c_0^2-a)^{2^n}-(a+c_0^2-2c_0\sqrt{a})^{2^n}}).

2. Lösung für Quadratzahlen a=b^2>0

Hier gehen wir ganz ähnlich vor, allerdings brauchen wir nicht den Weg über eine Körpererweiterung zu gehen, was die Rechnung deutlich vereinfacht. Wir setzen zunächst als Lösung an \displaystyle c_n=b \, \frac{A^{2^n}+B^{2^n}}{A^{2^n}-B^{2^n}}. Für c_0 ergibt sich insbesondere \displaystyle c_0=b \, \frac{A+B}{A-B} bzw. das Verhältnis \displaystyle \frac{A}{B}=\frac{c_0+b}{c_0-b}. Damit haben wir \displaystyle c_n=b \, \frac{(c_0+b)^{2^n}+(c_0-b)^{2^n}}{(c_0+b)^{2^n}-(c_0-b)^{2^n}}. Wählt man bspw. c_0=b+1 (für c_0=b ergibt sich einfach die konstante Folge c_n=b, was vielleicht uninteressant ist), dann ist B=1 und A=2b+1 bzw. \displaystyle c_n=b \, \frac{(2b+1)^{2^n}+1}{(2b+1)^{2^n}-1}=b \, \Bigl(1+\frac{2}{(2b+1)^{2^n}-1}\Bigr). Beispiel a=4, also b=2: Für c_0=3 ergibt sich \displaystyle c_n=2\Bigl(1+\frac{2}{5^{2^n}-1}\Bigr). Auch hier sieht man wieder das Konvergenzverhalten sehr deutlich.

3. Lösung für a<0

Dieser letzte Fall ist eigentlich schon im ersten Fall mit inbegriffen, es ergibt sich hier insbesondere als zu adjungierendes Element \sqrt{-1}=i. Im Zusammenhang mit der Potenzierung in der allgemeinen Darstellung der c_n läuft dies auf Winkelfunktionen hinaus. Wir setzen daher zunächst \displaystyle c_{n+1}=\frac{1}{2}\Bigl(c_n -\frac{\abs{a}}{c_n}\Bigr) und \displaystyle c_n=\sqrt{\abs{a}} \, \frac{\cos{2^nx}}{\sin{2^nx}}=\sqrt{\abs{a}} \,\cot{2^nx}. x wird nun ermittelt aus c_0, es ergibt sich \displaystyle \sin{x}=\sqrt{\frac{\abs{a}}{\abs{a}+c_0^2}} bzw. \displaystyle x=\arcsin{\sqrt{\frac{\abs{a}}{\abs{a}+c_0^2}}}. Das Verhalten dieser Folge ist im Gegensatz zu ihren "positiven" Partnern nicht vorhersehbar. Beispiel a=-3 und c_0=1: Damit ist x=\frac{\pi}{3}, also c_n=\sqrt{3} \, \cot{2^n\frac{\pi}{3}}. Wie gesagt, das Verhalten ist allein aus dieser Folge nicht vorhersehbar, setzt man dagegen die ersten n ein, erhält man für c=\{1,-1,1,-1,...\}, also die alternierende Folge. Soweit. Viel Freude trunx (Jens Koch)
\(\endgroup\)
Get link to this article Get link to this article  Printable version Printer-friendly version -  Choose language     Kommentare zeigen Comments  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist im Verzeichnis der Arbeitsgruppe Alexandria eingetragen:
: Mathematik :: Rekursion :: Heron-Verfahren :
Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung [von trunx]  
Von rekursiv gegebenen Zahlenfolgen c_{n+1} = f(c_0,cdots,c_n;n) ist oft eine allgemeine Darstellung c_n =g(n) gesucht. Diese ist für lineare Rekursionsgleichungen, also für f(c_0,cdots,c_n;n) - linear, berechenbar, ich habe dies hi
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
 
Aufrufzähler 818
 
Aufrufstatistik des Artikels
Insgesamt 45 externe Seitenaufrufe zwischen 2020.05 und 2021.08 [Anzeigen]
DomainAnzahlProz
https://google.de2760%60 %
https://google.com1533.3%33.3 %
https://www.bing.com24.4%4.4 %
https://startpage.com12.2%2.2 %

Häufige Aufrufer in früheren Monaten
Insgesamt 41 häufige Aufrufer [Anzeigen]
DatumAufrufer-URL
2020-2021 (15x)https://google.de/
2020-2021 (14x)https://google.com/
2020-2021 (12x)https://google.de

[Top of page]

"Mathematik: Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung" | 0 Comments
The authors of the comments are responsible for the content.

 
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]