Zahlenfolgen und Gleichungen

Hey,

kann man eigentlich für jede beliebige Zahlenfolge eine Gleichung aufstellen?

Nehmen wir an, ich denke mir folgende Zahlenfolge aus:

1, 1, 2, 3, 7, 11, 36, 4

Wie könnte man realisieren, dass diese Folge durch eine Gleichung repräsentiert werden kann? Mir ist es dabei nur wichtig, dass die ersten Zahlen korrekt sind. Alles was danach folgt ist irrelevant.

f(x) = 1^(x-1)

Das würde die ersten beiden korrekt liefern.
`f(0) = 1

f(1) = 1`

Aber wie schaffe ich auch den Rest? Geht das überhaupt?

Der Sinn? Einfach nur Interesse

Mr.Fister

Ja. Für n Zahlen nimmst du ein Polynom vom Grad n-1 und bestimmst die Koeffizienten a_j aus dem folgenden linearen Gleichungssystem

$\sum_{j=0}^{n-1} a\_j i^j = c\_i,\quad i=1,...n$

Das hat immer mindestens eine Lösung. Dann setzt du x=n+1 in das Polynom ein und du kriegst die nächste "logische" Zahl.
Wenn man von vornherein ein Polynom vom Grad n wählt, kann jede beliebige Zahl die nächste logische Zahl sein.

Ben04

Für Interessierte:

Bei unendlich langen Folgen von natürlichen Zahlen geht es nicht, weil es nur abzählbar unendlich viele Formeln aber überabzählbar viele Folgen gibt.

Wie es bei unendlichen Folgen von Restklassenringen aussieht weiß ich nicht.

Für endliche Folgen gibt es unendlich viele Formeln, da die Menge der Polynome n-ten Grads welche die Bedingung erfüllen eine Teilmenge davon ist und bereits unendlich ist. Es gibt aber nur genau ein Polynom mit Grad n-1 oder kleiner.

Könnte mir das jemand mal exemplarisch vormachen? Ich bin da leider nicht so gut drinne.

Würde das denn z.B. so aussehen (für n = 3)?

(a0*i^1) + (a1 * i^2) + (a2*i^3)

Und nehmen wir an, ich habe diese Folge: 4, 7, 11

Müsste ich das dann so ausrechnen?

4 = (a0*i^1) + (a1 * i^2) + (a2i^3)
7 = (a0*i^1) + (a1 * i^2) + (a2i^3)
11 = (a0*i^1) + (a1 * i^2) + (a2*i^3)

Und dieses nun "irgendwie" auflösen? Wie gesagt, ich bin da nicht so gut drinne, aber es interessiert mich doch seeehr

Hatten wir schon!
http://www.c-plusplus.net/forum/viewtopic-var-p-is-1297136.html#1297136

Christoph

MrNum schrieb:

Könnte mir das jemand mal exemplarisch vormachen? Ich bin da leider nicht so gut drinne.

Würde das denn z.B. so aussehen (für n = 3)?

(a0*i^1) + (a1 * i^2) + (a2*i^3)

Und nehmen wir an, ich habe diese Folge: 4, 7, 11

Müsste ich das dann so ausrechnen?

4 = (a0*i^1) + (a1 * i^2) + (a2i^3)
7 = (a0*i^1) + (a1 * i^2) + (a2i^3)
11 = (a0*i^1) + (a1 * i^2) + (a2*i^3)

Wenn man nicht an den genauen Parametern der Polynome interessiert ist, geht es auch einfacher, und zwar mit Differenzen.

Gegeben ist also die Folge 4, 7, 11. Die Differenzen zwischen den Folgengliedern sind 3, 4. Die Differenzen zwischen den Folgengliedern bei 3,4 sind 1. Man kann das auch systematischer aufschreiben:

Folge:    4   7   11   ?
1. Diff.:   3   4
2. Diff.:     1

Die dritte Reihe enthält eine konstante Folge aus lauter 1en. Die fortzusetzen, ist wirklich einfach:

Folge:    4   7   11   ?
1. Diff.:   3   4    ?
2. Diff.:     1    1

So, jetzt hat man in der zweiten Zeile eine 4 und ein Fragezeichen stehen. Die dritte Zeile sagt uns, dass ?-4 = 1 ist. Also kann man die Reihe fortsetzen.

Folge:    4   7   11   ?
1. Diff.:   3   4    5
2. Diff.:     1    1

Das Fragezeichen oben kann man genauso ausrechnen:

Folge:    4   7   11   16
1. Diff.:   3   4    5
2. Diff.:     1    1

Das funktioniert auch bei komplizierteren Reihen, man muss nur solange die Differenzen bilden, bis man bei einer konstanten Zahlenfolge angekommen ist. Nimm z.B. die Reihe 1,6,8,6,11, was ist die nächste Zahl?

Folge:    1    6    8     6     11   ?
1. Diff.:   5    2     -2    5
2. Diff.:     -3    -4    7
3. Diff.:        -1    11
4. Diff.:           12

Nach 4 mal Differenzenbilden kommt eine konstante Folge aus lauter 12en. Fortsetzen und zurückrechnen ergibt dann

Folge:    1    6    8     6     11    46
1. Diff.:   5    2     -2    5     35
2. Diff.:     -3    -4    7     30
3. Diff.:        -1    11    23
4. Diff.:           12    12

Die nächste Zahl in der ursprünglichen Folge ist also 46.

Hätte man das Interpolationspolynom kleinsten Grades ausgerechnet, würde man auch 46 als nächste Zahl rausbekommen. Der Vorteil bei dem Verfahren oben ist: Es kommt ohne Divisionen und Multiplikationen aus und ist per Hand oft schneller zu machen als die Koeffizienten des Interpolationspolynoms auszurechnen; die Koeffizienten können nämlich ziemlich hässlich werden und zum Beispiel Brüche mit sehr großem Zähler und Nenner ergeben.

edit: Rechenfehler behoben.

Mr.Fister

MrNum schrieb:

Könnte mir das jemand mal exemplarisch vormachen? Ich bin da leider nicht so gut drinne.

Würde das denn z.B. so aussehen (für n = 3)?

(a0*i^1) + (a1 * i^2) + (a2*i^3)

Und nehmen wir an, ich habe diese Folge: 4, 7, 11

Müsste ich das dann so ausrechnen?

4 = (a0*i^1) + (a1 * i^2) + (a2i^3)
7 = (a0*i^1) + (a1 * i^2) + (a2i^3)
11 = (a0*i^1) + (a1 * i^2) + (a2*i^3)

Und dieses nun "irgendwie" auflösen? Wie gesagt, ich bin da nicht so gut drinne, aber es interessiert mich doch seeehr

Naja du musst für i die Zeilennummer einsetzen... und du hast die falschen Potenzen (0,1,2 statt 1,2,3). Die zum Gleichungssystem gehörige Matrix ist dann

1 1 1
1 2 4
1 3 9

Vorrechnen werd ich es nicht, da gibt es Algorithmen nach denen du schauen kannst, aber es kommt laut gnuplot dieses Polynom raus:

f(x)=2+1.5*x+0.5*x^2
f(1)=4
f(2)=7
f(3)=11
f(4)=16

Christoph

Mr.Fister schrieb:

Vorrechnen werd ich es nicht, da gibt es Algorithmen nach denen du schauen kannst, aber es kommt laut gnuplot dieses Polynom raus:

f(x)=2+1.5*x+0.5*x^2
f(1)=4
f(2)=7
f(3)=11
f(4)=16

Die 16 hatte ich in meinem letzten Post auch ausgerechnet ohne Matrix und ohne ein lineares Gleichungssystem lösen zu müssen.

Mit linearem Gleichungssystem ist es natürlich allgemeiner, aber eben auch so kompliziert, dass man es ohne Computer-Unterstützung ungerne macht.

Christoph schrieb:

Die 16 hatte ich in meinem letzten Post auch ausgerechnet ohne Matrix und ohne ein lineares Gleichungssystem lösen zu müssen.

kann man da auch ne formel rauskriegen`?

Christoph

mathematikpraktikant schrieb:

Christoph schrieb:

Die 16 hatte ich in meinem letzten Post auch ausgerechnet ohne Matrix und ohne ein lineares Gleichungssystem lösen zu müssen.

kann man da auch ne formel rauskriegen`?

Nicht, dass ich wüsste. Man kann damit nur nach und nach die nächsten Folgenglieder berechnen.

Achso, man spart sich dabei übrigens nicht nur das lineare Gleichungssystem, sondern außerdem noch das Auswerten eines Polynoms.

Christoph

Christoph schrieb:

mathematikpraktikant schrieb:

Christoph schrieb:

Die 16 hatte ich in meinem letzten Post auch ausgerechnet ohne Matrix und ohne ein lineares Gleichungssystem lösen zu müssen.

kann man da auch ne formel rauskriegen`?

Nicht, dass ich wüsste. Man kann damit nur nach und nach die nächsten Folgenglieder berechnen.

Ich korrigiere mich: Man kann damit die Formel rausbekommen.

An dem Beispiel von oben:

Folge:    4   7   11   ?
1. Diff.:   3   4
2. Diff.:     1

Ganz links von oben nach unten stehen die Zahlan 4, 3, 1. Deswegen ist das Polynom für diese Folge:
f(n) = 4*binom(n,0) + 3*binom(n,1) + 1*binom(n,2) = 4 + 3n + n(n-1)/2 = 4 + 2.5*n + 0.5*n^2

Dabei ist binom(n,k) der Binomialkoeffizient "n über k". Das funktioniert allgemein. Für die andere, komplizierte Folge, die ich angegeben hatte, war die Tabelle:

Folge:    1    6    8     6     11   ?
1. Diff.:   5    2     -2    5
2. Diff.:     -3    -4    7
3. Diff.:        -1    11
4. Diff.:           12

Das Polynom für diese Folge ist also:
f(n) = 1*binom(n,0) + 5*binom(n,1) - 3*binom(n,2) - 1*binom(n,3) + 12*binom(n,4)

edit: Als Referenz für solche und ähnliche Zahlenspielereien würde ich dieses Buch nennen: "The book of numbers" von John H. Conway und Richard K. Guy. Ab Seite 81 geht es darum, wie man das Polynom aus so einer Differenzen-Tabelle ermitteln kann.