Geometrische Reihe < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:19 Fr 19.11.2004 | | Autor: | Es_press |
Hallo,
mir fehlt der letzte Kniff, um eine Reihe mit einem k-Abschnitt in eine Rechenvorschrift mit etwa k/2 Multiplikationen, die keine Division
enthält umzuschreiben.
Reihe :
g(x) = [mm] 1+x+x^2+x^3+....+x^k [/mm] k aus den natürlichen Zahlen
Ansatz 1:
Die Summenformel bildet die geometrische Reihe:
[mm] \summe_{k=0}^{n} x^k [/mm] = (1-x^(n+1))/(1-x)
Leider hat man aber eine Division ...
Ansatz 2:
Man kann z.B: [mm] x^2 [/mm] als :
[mm] \summe_{n=1}^{x} [/mm] 2n-1
bzw. : [mm] \summe_{n=1}^{x} [/mm] n+n-1
Für [mm] 3^2 [/mm] würde sich z.B: 1+3+5 = 9 ergeben
Man könnte sich ähnliche Formeln überlegen für [mm] x^3,x^4 [/mm] usw.
Allerdings soll die Rechenvorschrift einfach sein, was hierbei nicht mehr der
Fall wäre.
Kann man hier vereinfachen oder gibt es noch ganz andere Möglichkeiten ?
Gruß,
Es_press
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
Hallo Es_press,
ich kenne keine Methode, die mit k/2 Multiplikationen auskommt. Allerdings funktioniert deine Methode mit der Summe nur für x aus den natürlichen Zahlen. [mm](1,5)^2[/mm] kannst du damit nicht berechnen.
Ein effizienter Algorithmus zum Berechnen von Funktionswerten von Polynomen ist das sogenannte Horner-Schema.
Statt die Potenzen von z.B. [mm]f(x)=2x^3-3x^2+4x-6[/mm] klammert man um und erhält:
[mm]f(x)=((2\cdot x-3)\cdot x+4)\cdot x-6[/mm]
Offensichtlich kommt man bei einem Polynom k-ten Grades mit genau k Multiplikationen und k Additionen aus.
Du hast das Polynom [mm]1x^k+\dots\+1x^2+1x+1[/mm] und daraus wird
[mm](\dots(1\cdot x+1)+1)\cdot x+1)\cdot x+1)\cdot x+1[/mm]
Probier es doch mal aus fur x=1 und x=2 mit verschiedenen Werten für k. Im ersten Fall müsste [mm]k+1[/mm], im zweiten [mm]2^{k+1}-1[/mm] rauskommen.
Hugo
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 00:22 Di 23.11.2004 | | Autor: | Es_press |
... besonderer Dank an Hugo.
Gruß,
Espress
|
|
|
|
