Die Mathe-Redaktion - 18.12.2017 07:51 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 431 Gäste und 9 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Mathematik: Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung
Freigegeben von matroid am Di. 24. Januar 2017 00:01:06
Verfasst von trunx -   625 x gelesen [Gliederung] [Statistik] Druckbare Version Druckerfreundliche Version
Mathematik

\(\begingroup\)

Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung



Von rekursiv gegebenen Zahlenfolgen <math>c_{n+1} = f(c_0,\cdots,c_n;n)</math> ist oft eine allgemeine Darstellung <math>c_n =g(n)</math> gesucht. Diese ist für lineare Rekursionsgleichungen, also für <math>f(c_0,\cdots,c_n;n)</math> - linear, berechenbar, ich habe dies hier ausführlich besprochen.

Ist dagegen <math>f(c_0,\cdots,c_n;n)</math> 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 <math>\sqrt{a}</math>):
<math>\displaystyle c_{n+1} = \frac{1}{2} \Bigl(c_n +\frac{a}{c_n}\Bigr)</math> mit <math>a, c_i \neq 0 \in \mathds{Q}</math>.

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


Ausgangspunkt ist folgender Einfall, der im Prinzip bereits alles Weitere vorweg nimmt:
Wir setzen für <math>\displaystyle c_0=\sqrt{a} \, \frac{y+x}{y-x}</math> und erhalten für
<math>\displaystyle c_1=\sqrt{a} \, \frac{y^2+x^2}{y^2-x^2}</math> und weiter
<math>\displaystyle c_2=\sqrt{a} \, \frac{y^4+x^4}{y^4-x^4}</math> bzw.
<math>\displaystyle c_n=\sqrt{a} \, \frac{y^{2^n}+x^{2^n}}{y^{2^n}-x^{2^n}}</math>.

Wie gesagt, das ist praktisch schon die Lösung; wir setzen nun zunächst <math>y=1</math> (aber siehe weiter unten) und erhalten
<math>\displaystyle c_n=\sqrt{a} \, \frac{1+x^{2^n}}{1-x^{2^n}}</math>.
Jetzt müssen wir noch <math>x</math> ermitteln. Wir setzen <math>x=A+B\sqrt{a}</math> an, da <math>\sqrt{a}</math> im Gegensatz zu <math>a, c_n</math>, wegen der Eigenschaft von <math>a</math> kein Quadrat zu sein, nicht in <math>\mathds{Q}</math> liegt. Sprich wir gehen hier über die einfache Körpererweiterung <math>\mathds{Q}(\sqrt{a})</math>.

Damit erhalten wir zunächst für <math>\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}</math>.
Da <math>c_0 \in \mathds{Q}</math>, muss <math>aB^2+1-A^2=0</math> bzw. <math>A^2-aB^2=1</math> sein. Letzte Gleichung ist die sog. Pellsche Gleichung.

Es ist also <math>\displaystyle c_0=\frac{aB}{1-A}</math> mit der Nebenbedingung <math>A^2-aB^2=1</math>.
Oft wird gesagt, dass man für das Heron-Verfahren ein geeignetes <math>c_0</math> 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.

<math>A</math> und <math>B</math> werden nun konkret aus der Kettenbruchentwicklung für <math>\sqrt{a}</math> ermittelt. Diese besteht unter den angegebenen Bedingungen für <math>a</math> aus einer Vorperiode und der eigentlichen Periode. Bricht man diesen unendlichen Kettenbruch nach einigen Schritten ab, so entstehen rationale Näherungen für <math>\sqrt{a}</math>. Und unter diesen Brüchen wiederum gibt es eine Vielzahl, deren Zähler und Nenner die Pellsche Gleichung <math>A^2-aB^2=1</math> erfüllen. Der größte Bruch (oder der mit dem kleinsten Zähler bzw. Nenner), der die Pellsche Gleichung erfüllt, liefert als <math>\frac{\abs{A}}{\abs{B}}</math> die Beträge der gesuchten Zahlen. Daraus lassen sich 4 Paare bilden <math>(\pm A,\pm B)</math> unter denen letztlich <math>A=\abs{A}</math> und <math>B=-\abs{B}</math> die gesuchten Lösungen sind.

Beispiel <math>a=7</math>: Wie man sieht, ist <math>a</math> kein Quadrat, die Kettenbruchentwicklung von <math>\sqrt{7}=[2;{\overline {1,1,1,4}}]</math> und die ersten Näherungen lauten <math>2=\frac{2}{1}</math>, <math>3=\frac{3}{1}</math>, <math>\frac{5}{2}</math>, <math>\frac{8}{3}</math>, <math>\frac{37}{14}</math>, ...

Erstmalig erfüllt davon <math>\frac{8}{3}</math> die Pellsche Gleichung <math>(8^2-7\cdot3^2=1)</math>, die gesuchten Zahlen wären demnach <math>A=8</math> und <math>B=-3</math>. Damit ist das "geeignete" <math>c_0=3</math> und allgemein
<math>\displaystyle c_n=\sqrt{7} \, \frac{1+(8-3\sqrt{7})^{2^n}}{1-(8-3\sqrt{7})^{2^n}}</math>.

Alle diese <math>c_n</math> 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 <math>c_0=3</math>, aber kennen schon <math>\frac{8}{3}</math>. Es folgt <math>c_1=\frac{8}{3}</math>, aber dafür nutzen wir <math>127^2-7\cdot48^2=1</math>, sprich die bessere Näherung wäre hier <math>\sqrt{7}\approx\frac{127}{48}</math>, die erst im nächsten Schritt als <math>c_2</math> 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" <math>c_0</math> bereits die Lösung von <math>\sqrt{a}</math>, nämlich in Form des Kettenbruchs benutzt wird, also <math>c_0</math> frei wählbar bleiben soll. Für diesen Fall bilden die beiden Gleichungen
I <math>\displaystyle c_0=\frac{aB}{1-A}</math> und
II <math>A^2-aB^2=1</math>
ein Gleichungssystem für <math>A</math> und <math>B</math>.

Sie ergeben die quadratische Gleichung <math>(a-c_0^2)A^2+2c_0^2A-(a+c_0^2)=0</math> mit der Lösung <math>\displaystyle A=-\frac{a+c_0^2}{a-c_0^2}</math> und entsprechendem <math>\displaystyle B=\frac{2c_0^2}{a-c_0^2}</math> (die triviale Lösung <math>A=1</math> entfällt wegen Gleichung I).

Hierbei ist es für die Allgemeingültigkeit allerdings sinnvoll, dass <math>\mathds{K}=\mathds{R}</math> gesetzt wird. Wählt man aber insbesondere dann doch <math>c_0^2</math> so, dass <math>a-c_0^2 \in \mathds{Q}</math> (bzw. <math>c_0^2-a \in \mathds{Q}</math>) liegt, dann wäre nun <math>y=a-c_0^2</math> (bzw. <math>y=c_0^2-a</math>) und <math>x=-(a+c_0^2)+2c_0\sqrt{a}</math> (bzw. <math>x=a+c_0^2-2c_0\sqrt{a}</math>). Also alles in allem

<math>\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}}</math>

(bzw. <math>\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}}</math>).

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


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 <math>\displaystyle c_n=b \, \frac{A^{2^n}+B^{2^n}}{A^{2^n}-B^{2^n}}</math>.

Für <math>c_0</math> ergibt sich insbesondere <math>\displaystyle c_0=b \, \frac{A+B}{A-B}</math> bzw. das Verhältnis <math>\displaystyle \frac{A}{B}=\frac{c_0+b}{c_0-b}</math>.

Damit haben wir <math>\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}}</math>.

Wählt man bspw. <math>c_0=b+1</math> (für <math>c_0=b</math> ergibt sich einfach die konstante Folge <math>c_n=b</math>, was vielleicht uninteressant ist), dann ist <math>B=1</math> und <math>A=2b+1</math> bzw.

<math>\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)</math>.

Beispiel <math>a=4</math>, also <math>b=2</math>: Für <math>c_0=3</math> ergibt sich
<math>\displaystyle c_n=2\Bigl(1+\frac{2}{5^{2^n}-1}\Bigr)</math>.

Auch hier sieht man wieder das Konvergenzverhalten sehr deutlich.

3. Lösung für <math>a<0</math>


Dieser letzte Fall ist eigentlich schon im ersten Fall mit inbegriffen, es ergibt sich hier insbesondere als zu adjungierendes Element <math>\sqrt{-1}=i</math>. Im Zusammenhang mit der Potenzierung in der allgemeinen Darstellung der <math>c_n</math> läuft dies auf Winkelfunktionen hinaus.

Wir setzen daher zunächst
<math>\displaystyle c_{n+1}=\frac{1}{2}\Bigl(c_n -\frac{\abs{a}}{c_n}\Bigr)</math> und
<math>\displaystyle c_n=\sqrt{\abs{a}} \, \frac{\cos{2^nx}}{\sin{2^nx}}=\sqrt{\abs{a}} \,\cot{2^nx}</math>.

<math>x</math> wird nun ermittelt aus <math>c_0</math>, es ergibt sich <math>\displaystyle \sin{x}=\sqrt{\frac{\abs{a}}{\abs{a}+c_0^2}}</math> bzw. <math>\displaystyle x=\arcsin{\sqrt{\frac{\abs{a}}{\abs{a}+c_0^2}}}</math>.

Das Verhalten dieser Folge ist im Gegensatz zu ihren "positiven" Partnern nicht vorhersehbar.

Beispiel <math>a=-3</math> und <math>c_0=1</math>: Damit ist <math>x=\frac{\pi}{3}</math>, also
<math>c_n=\sqrt{3} \, \cot{2^n\frac{\pi}{3}}</math>.
Wie gesagt, das Verhalten ist allein aus dieser Folge nicht vorhersehbar, setzt man dagegen die ersten <math>n</math> ein, erhält man für <math>c=\{1,-1,1,-1,...\}</math>, also die alternierende Folge.

Soweit.

Viel Freude trunx (Jens Koch)
\(\endgroup\)
Link auf diesen Artikel Link auf diesen Artikel  Druckbare Version Druckerfreundliche Version  Einen Freund auf diesen Artikel aufmerksam machen Weitersagen Kommentare zeigen Kommentare  
pdfFür diesen Artikel gibt es keine pdf-Datei


Arbeitsgruppe Alexandria Dieser Artikel ist nicht im Verzeichnis der Arbeitsgruppe Alexandria eingetragen.
[Die Arbeitsgruppe Alexandria katalogisiert die Artikel auf dem Matheplaneten]

 
Verwandte Links
 
Besucherzähler 625


[Seitenanfang]

" Mathematik: Allgemeine Darstellung einer nichtlinearen Rekursionsgleichung" | 0 Kommentare
 
Für den Inhalt der Kommentare sind die Verfasser verantwortlich.

 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]