Hornerschema

Neue Frage »

Halfdan Auf diesen Beitrag antworten »
Hornerschema
Ich stehe zzt bei folgender Aufgabe an:

Sei ein Polynom mit

1. Wir wollen konkrete Funktionswerte berechnen, also z.B. . Wir nehmen an, dass durch mehrfaches Multiplizieren von mit sich selbst berechnet wird. Berechnen Sie die Anzahl der Multiplikation, die Sie benötigen, um für ein konkretes auszurechnen.

2. Es gibt einen besseren Algorithmus, um zu berechnen. Dieser braucht im wesentlichen Multiplikation. (Sie können dies voraussetzen, ohne den Algorithmus hier selbst zu entwickeln.)

Berechnen Sie wiederum die Anzahl der Multiplikation. (Tipp: Verwenden sie ggf. die Abschätzung log(n!) \approx log(n).

3. Noch besser eignet sich die Darstellung von p(x) im Horner-Schema:



Wie groß ist die Anzahl der Multiplikationen, wenn Sie die Darstellung im HornerSchema verwenden?


Ganz offen gesagt habe ich nicht die geringste Ahnung was ich tun soll. Wir behandeln zzt das Thema Funktionen, bzw. ging es in der letzten Vorlesung um Folgen und Reihen. Das Hornerschema taucht aber zB. nirgends auf und ich weis nicht recht was ich damit anfangen soll, bzw. welche Informationen mir fehlen...
Steffen Bühler Auf diesen Beitrag antworten »
RE: Hornerschema
Beim ersten Teil musst Du nur die Anzahl der Multiplikationen zählen. Wie groß ist die zum Beispiel bei ?

Beim zweiten Teil geht es wahrscheinlich eher um die Optimierung der -Berechnung als die von , oder? Auf wieviel Multiplikationen reduziert sich dann unser Beispiel? Und auf wieviel verallgemeinert?

Wenn ihr das Hornerschema wirklich nicht vorher besprochen habt, was eigentlich seltsam wäre, lies es Dir in Ruhe auf Wiki durch. Wieviel Multiplikationen brauchst Du nun fürs Beispiel? Wieviel allgemein?

Viele Grüße
Steffen
Halfdan Auf diesen Beitrag antworten »

Ist das eine Multiplikation für oder 2: eine für (bzw. sind das alleine 2..also insgesamt 3) und nochmals eine für

Sind das dann bei 1. 2n-1 Multiplikationen?

2. Blicke ich noch gar nicht durch. Ich weis ehrlich gesagt auch nicht woher ich genau die nötigen Informationen hernehmen soll. Fühle mich hier gerade sehr ins kalte Wasser geschmissen, was ja okay ist - aber ich weis nicht mal recht wonach ich suchen soll.

3. Nein haben wir wirklich nicht besprochen. Habe beide Foliensätze durchsucht (Repetion Funktionen 8-10 Klasse und den Foliensatz Abbildungen zu dem das Übungsblatt gehört..) da wird Horner nicht 1x erwähnt.

Allgemein wären dann wie bei 1. 2n-1 und mit Horner nur noch n. Oder müsste ich die ... im Funktionsterm noch deuten können und n durch eine Zahl ersetzen?!
Steffen Bühler Auf diesen Beitrag antworten »

EDIT: Bin jetzt beim Zählen selber durcheinandergekommen. smile

Zitat:
Original von Halfdan
Ist das eine Multiplikation für oder 2: eine für (bzw. sind das alleine 2..also insgesamt 3) und nochmals eine für


Also drei Multiplikationen. Stimmt. Eine fürs Quadrieren, eine für den Koeffizienten, eine für das lineare Glied danach.

Zitat:
Original von Halfdan
Sind das dann bei 1. 2n-1 Multiplikationen?


Könnte sein (hab's nicht selber untersucht). Hier ist z.B. n=2 und Du hast korrekt drei Multiplikationen herausgefunden. Setz mal n=3 und n=4 und schau, was herauskommt. Dann schau, ob es immer noch passt.

Zitat:
Original von Halfdan
2. Blicke ich noch gar nicht durch.


Angenommen, es gibt einen "Trick", nicht mit 2 Multiplikationen, sondern mit log(3) Multiplikationen auszuführen. Und nur mit log(4) Multiplikationen. Dan sparst Du doch eine Menge. Versuche auch hier die Regel zu finden.

Zitat:
Original von Halfdan
mit Horner nur noch n.


Gut erkannt!
Halfdan Auf diesen Beitrag antworten »

Danke dir, ja irgendwie stimmt es nicht. Außer ich mache einen Überlegungsfehler.
Komme bei einem Polynom 3ten Grades auf 6 Multiplikationen, 2n-1 dürften aber nur 5 sein.
Bei 4ten Grades müssten es dann ja 7 sein, komme hier aber auf 10.

Zitat:
Angenommen, es gibt einen "Trick", x3 nicht mit 2 Multiplikationen, sondern mit log(3) Multiplikationen auszuführen. Und x4 nur mit log(4) Multiplikationen. Dann sparst Du doch eine Menge. Versuche auch hier die Regel zu finden.

Kann sein, hatte offengesagt noch nie mit Logarithmus zu tun. Habe nur ein Fachabi und da behandelt man dies leider nicht. Muss ich mich wohl mal zusätzlich einlesen.
Steffen Bühler Auf diesen Beitrag antworten »

Zitat:
Original von Halfdan
Danke dir, ja irgendwie stimmt es nicht. Außer ich mache einen Überlegungsfehler.

Sieht so aus, das ist das tägliche Brot von Mathematikern. Willkommen im Club. Augenzwinkern

Ich hab mir das jetzt mal angeschaut. Also bei n=1 eine Multiplikation, bei n=2 drei, denn es kommen 2 dazu. Bei n=3 sind es 6, denn kommen drei dazu. Und so weiter.

Also sieht die Regel wohl anders aus. Hast Du eine Idee?

Zitat:
Original von Halfdan
Kann sein, hatte offengesagt noch nie mit Logarithmus zu tun. Habe nur ein Fachabi

Da sollte man den Logarithmus kennen, aber egal. Du hast ja einen Taschenrechner.

Die Regel oben ändert sich dann entsprechend. Es kommen z.B. bei n=3 eben nicht drei dazu, sondern eine für den Koeffizienten und nur log(3) statt 2 für die Potenzierung. Nun überlege.
 
 
Halfdan Auf diesen Beitrag antworten »

Also das Muster welches ich erkenne, ist dass es immer die Quersumme der Exponenten ist.

Für die Exponenten immer n-1 und dann noch jeweils eine für die Anzahl der enthaltenen Koeffizienten.

Zitat:
Da sollte man den Logarithmus kennen, aber egal. Du hast ja einen Taschenrechner.

Stelle mich hier vielleicht doof an, aber wie tippe ich das denn richtig ein? ich habe ja beim Taschenrechner wobei ich für n jeweils einen Wert eingeben soll - was tippe ich denn zb für für das n ein? Wenn ich da wieder 3 wähle -ergibt das 1.

Dann wäre das wohl Anzahl Koeffizienten * log(3)
Steffen Bühler Auf diesen Beitrag antworten »

Zitat:
Original von Halfdan
Also das Muster welches ich erkenne, ist dass es immer die Quersumme der Exponenten ist.


Die Summe der Exponenten meinst Du wahrscheinlich. Ja, das würde passen. Erst 1, dann 1+2, dann 1+2+3 und so weiter. Kennst Du diese Regelmäßigkeit? Zur Not bemühe Google, zum Beispiel "liggetse".

Zitat:
Original von Halfdan
was tippe ich denn zb für für das n ein?

Hier hatte ich gehofft, dass so etwas bei Euch definiert wurde. Laut Wiki kann log für den natürlichen Logarithmus (ln) stehen, dann wäre die Basis e. Oder für den Zehnerlogarithmus (lg) mit Basis 10. Da müsstest Du noch mal nachfragen, wenn es so unsauber formuliert ist.
Dann wäre es zuerst 1, dann 1+(1+log(2)), dann 1+(1+log(2))+(1+log(3)), dann...
Halfdan Auf diesen Beitrag antworten »

Ach, der kleine Gauß müsste das dann sein. smile Danke

Zitat:
Dann wäre es zuerst 1, dann 1+(1+log(2)), dann 1+(1+log(2))+(1+log(3)), dann...


..(1+log(4) etc. ergibt das dann sowas wie die fakultät? Versuche gerade den Tipp in der Aufgabe zu verstehen. Du hast jetzt wenn ich das richtig Verstanden habe die Produktregel auf das Polynom angewendet oder?
Steffen Bühler Auf diesen Beitrag antworten »

Den Tipp verstehe ich auch nicht. Bei sehe ich auf Anhieb keine Möglichkeit, mit einer Fakultät zu vereinfachen. Ich hätte die Summe so stehengelassen. Vielleicht hat ein Kollege noch eine Idee.

Ohnehin ist noch nicht geklärt, ob das hier wirklich so in der Aufgabe stand:
Zitat:
Es gibt einen besseren Algorithmus, um zu berechnen. Dieser braucht im wesentlichen Multiplikation.


Das Quadrat passt hier meines Erachtens nicht, daher hatte ich stillschweigend vorausgesetzt. Du hast das bisher nicht kommentiert. Was steht denn nun wirklich da?
Halfdan Auf diesen Beitrag antworten »

Sorry das hatte ich übersehen! Du hast recht, da steht !
Steffen Bühler Auf diesen Beitrag antworten »

Zitat:
Original von Steffen Bühler
Bei sehe ich auf Anhieb keine Möglichkeit, mit einer Fakultät zu vereinfachen.

Hm, anscheinend sind meine Logarithmuskenntnisse etwas eingerostet. Natürlich gilt: Der Logarithmus eines Produktes entspricht der Summe der Logarithmen der Faktoren.

Damit kommen wir weiter. Siehst Du, wie?
Halfdan Auf diesen Beitrag antworten »

Habe die Regeln jetzt nur kurz überflogen muss sonst am Freitag mich wirklich mal in Logarithmus einarbeiten weil ich davon keine Ahnung habe.

Aber heißt das denn das ich zb. aus das hier bilde:
Steffen Bühler Auf diesen Beitrag antworten »

Nein, das heißt es nicht. Es geht darum, die Zahl der Multiplikationen für ein Polynom vom Grad n herauszufinden, wenn dieser Logarithmustrick angewendet wird.

Bei benötigt man damit also für zum einen log(n) Multiplikationen für die Potenz und eine weitere für den Koeffizienten. Also schon mal 1+log(n). Bei dann nach demselben Schema 1+log(n-1) Multiplikationen.

Somit für das gesamte Polynom Multiplikationen. Das ist die Summenformel, die ich oben hingeschrieben habe.

Und nun kann man die ganzen Einsen zusammenfassen. Dann bleibt eine Summe von Logarithmen übrig. Und für die gilt das Obengesagte.
HAL 9000 Auf diesen Beitrag antworten »

ist ja selbst auch nur eine Schätzung (gemeint sein dürfte übrigens , oder?).

Laut Stirlingformel ist nun , d.h., wenn wir mal nur den dominierenden Faktor nehmen können wir damit sagen , eine derartige Grobeinordnung reicht ja womöglich schon für diese Teilaufgabe.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »