Horner-Schema < Numerik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:25 So 27.04.2014 | | Autor: | Lustique |
| Aufgabe | a) Sei ein Polynom $p(t) = [mm] \sum_{i=0}^m a_{i+1}t^i$ [/mm] und ein [mm] $\bar [/mm] t [mm] \in \mathbb{R}$ [/mm] gegeben. Das Horner-Schema berechnet aus den [mm] $a_j$ [/mm] neue Koeffizienten [mm] $b_j$, [/mm] mit deren Hilfe der Wert [mm] $p(\bar [/mm] t)$ und die Koeffizienten eines abdividierten Polynoms vom Grad kleiner gleich $m-1$ bestimmt werden können. Mehrfache Anwendung dieser Idee führt auf den folgenden Algorithmus:
----------------------------------------------------------------
for $j = m+1, [mm] \dotsc [/mm] , 1$ do
[mm] $b_{1,j} [/mm] = [mm] a_j$
[/mm]
end
for $i = 1, [mm] \dotsc, [/mm] m$ do
[mm] $b_{i+1,m+1} [/mm] = [mm] b_{i,m+1}
[/mm]
for $j = m, [mm] \dotsc, [/mm] i$ do
[mm] $b_{i+1,j} [/mm] = [mm] \bar t\cdot b_{i+1,j+1} [/mm] + [mm] b_{i,j}$
[/mm]
end
end
[mm] $b_{m+2,m+1} [/mm] = [mm] b_{m+1,m+1}$
[/mm]
----------------------------------------------------------------
[Die Teile in blau wurden von mir hinzugefügt, da auf dem Originalzettel die for-Schleifen durch eine Art "Klammern" eingegrenzt sind, und ich nicht weiß, wie man die hier hätte benutzen können.]
Man zeige, dass für $i=1, [mm] \ldots, [/mm] m+1$ gilt
[mm] $b_{i+1,i} [/mm] = [mm] \frac{p^{(i-1)}(\bar t)}{(i-1)!}.$
[/mm]
b) [Implementierung in Matlab, etc. ...] |
Hallo zusammen,
ich habe mich jetzt schon einige Zeit an dieser Aufgabe versucht, aber komme einfach kein Stück weiter. Die Aufgabe ist vom zweiten Zettel einer Numerik I-Vorlesung und bis jetzt mussten wir eigentlich noch keine Algorithmen untersuchen. Entsprechend aufgeschmissen bin ich dann auch hier:
1. Ich verstehe nicht mal genau, was dieser Algorithmus eigentlich tun soll. Wegen Wikipedia weiß ich, dass man mit dem Horner-Algorithmus bspw. so etwas wie Polynomdivision und das Ausrechnen von Funktionswerten erledigen kann. Was hier geschehen soll, erschließt sich mir aber nicht. "Abdividiertes Polynom" klingt irgendwie nach Polynomdivision (ich habe den Begriff aber noch nie gehört), aber da nirgendwo von einer Nullstelle die Rede ist (es sei denn, [mm] $\bar [/mm] t$ soll so eine sein), könnte es ja auch genauso gut nur um das Berechnen eines Funktionswerts handeln.
2. Ich habe noch nie einen Algorithmus untersucht, oder versucht, daraus etwas mathematisches herzuleiten (nur mal einen Haskell-Algorithmus, aber die sind ja auch sehr viel schöner zu untersuchen, weil funktional, und da ging es nur um Effizienz). Demzufolge weiß ich nicht mal, wie ich diesen Algorithmus richtig zu lesen habe, damit ich zu einem Ergebnis komme. Da es hier ja verschachtelte for-Schleifen gibt und ziemlich viele Indizes involviert sind, verliere ich einfach komplett die Übersicht.
Das einzige was ich bis jetzt bei dieser Aufgabe geschafft habe, ist [mm] $\frac{p^{(i-1)}(\bar t)}{(i-1)!}$ [/mm] umzuformen:
Per Induktion bin ich auf folgende Darstellung für [mm] $p^{(m)}(x)=\frac{\mathrm{d}^m}{\mathrm{d}\,x^m} \left(\sum_{k=0}^n a_k \cdot x^k\right)$ [/mm] gekommen für $m=1, [mm] \dotsc, [/mm] n$:
[mm] $p^{(m)}(x) [/mm] = [mm] \sum_{k=0}^n k\cdot [/mm] (k-1) [mm] \dotsb [/mm] (k-(m-1)) [mm] \cdot a_k\cdot x^{k-m} [/mm] = [mm] \sum_{k=0}^n \frac{k!}{(k-m)!} \cdot a_k\cdot x^{k-m} [/mm] = [mm] \sum_{k=0}^n \binom{k}{m}\cdot [/mm] m! [mm] \cdot a_k\cdot x^{k-m}$ [/mm]
und damit auf:
[mm] $\frac{p^{(i-1)} (\bar t)}{(i-1)!} [/mm] = [mm] \sum_{k=0}^n \binom{k}{i-1}\cdot \cdot a_k\cdot {\bar t}^{k-(i-1)} [/mm]
Ansonsten bin ich aber ratlos bei dieser Aufgabe, wenn ich ehrlich bin. Demzufolge wäre ich auch dankbar für alle Tipps, die mich hier weiterbringen könnten.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 14:06 So 27.04.2014 | | Autor: | abakus |
Hallo,
ich kenne das Hornerschema als ein Verfahren, dass die Anzahl der erforderlichen Operationen beim ausrechnen eines Polynoms reduziert.
Beispiel: Für [mm] $f(x)=4x^3+5x^2-7x+8$ [/mm] soll den Funktionswert an einer beliebigen Stelle x berechnet werden.
Man rechnet normalerweise 4*x*x*x+5*x*x-7*x+8. Das sind 6 Multiplikationen und 3 Additionen.
Schreibt man f(x) hingegen in der Form x*(4*x*x+5*x-7)+8, hat man nur 4 Multiplikationen und 3 Additionen.
Nun kann man in der Klammer wiederum teilweise x ausklammern und erhält
f(x)=x*(x*(4*x+5)-7)+8.
Das sind nur noch 3 Multiplikationen und 3 Additionen.
Es wird also durch teilweises Ausklammern von x der Grad des verbleibenden Polynoms schrittweise reduziert.
Gruß Abakus
|
|
|
| |
|
> Hallo,
> ich kenne das Hornerschema als ein Verfahren, dass die
> Anzahl der erforderlichen Operationen beim ausrechnen eines
> Polynoms reduziert.
> Beispiel: Für [mm]f(x)=4x^3+5x^2-7x+8[/mm] soll den Funktionswert
> an einer beliebigen Stelle x berechnet werden.
> Man rechnet normalerweise 4*x*x*x+5*x*x-7*x+8. Das sind 6
> Multiplikationen und 3 Additionen.
> Schreibt man f(x) hingegen in der Form x*(4*x*x+5*x-7)+8,
> hat man nur 4 Multiplikationen und 3 Additionen.
> Nun kann man in der Klammer wiederum teilweise x
> ausklammern und erhält
> f(x)=x*(x*(4*x+5)-7)+8.
> Das sind nur noch 3 Multiplikationen und 3 Additionen.
> Es wird also durch teilweises Ausklammern von x der Grad
> des verbleibenden Polynoms schrittweise reduziert.
> Gruß Abakus
Danke Abakus. Ich habe mir den Algorithmus mal für ein kleines Beispiel angeguckt [mm] ($p(t)=1+2t-3t^2$) [/mm] und dabei gesehen, dass für irgendwelche Indizes i und j (in diesem Fall $i=2, j=1$) das Ursprungspolynom in der "ausgeklammerten" Form in [mm] $b_{i,j}$ [/mm] steht (für $t = [mm] \bar [/mm] t: [mm] \qquad b_{2,1}=\bar{t}\cdot (\bar{t}\cdot [/mm] (-3) + 2) + 1$) und bspw. wie ebenfalls behauptet [mm] $b_{3,2} [/mm] = [mm] 2\cdot \bar{t} \cdot [/mm] (-3) + 2 = [mm] \frac{p^{(2-1)}(\bar{t})}{(2-1)!}$. [/mm] Aber ich habe trotzdem keine Ahnung, wie ich hier mit einem allgemeinen Polynom die gewünschte Identität zeigen soll. Das Ganze an einem Beispiel durchzugehen ist ja gut und schön, aber mir hat sich dadurch nicht erschlossen, wie die allgemeine Lösung anzugehen ist. Ich habe schon allein mit diesem "Mini-Polynom" fast eine ganze DIN A4-Seite vollgeschrieben, als ich den Algorithmus wie angegeben (kleinschrittig) benutzt habe, und musste da schon sehr mit den Indizes aufpassen...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:03 Mo 28.04.2014 | | Autor: | DieAcht |
Hallo Lustique,
Den Algorithmus hast du dann wohl verstanden.
Zu zeigen: [mm] b_{i+1,i}=\frac{p^{(i-1)}(\bar t)}{(i-1)!} [/mm] für alle [mm] i\in\{1,\ldots,m+1\}.
[/mm]
Hattet ihr schon etwas zur Schleifeninvariante?
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:14 Mo 28.04.2014 | | Autor: | Lustique |
> Hallo Lustique,
>
>
> Den Algorithmus hast du dann wohl verstanden.
>
> Zu zeigen: [mm]b_{i+1,i}=\frac{p^{(i-1)}(\bar t)}{(i-1)!}[/mm] für
> alle [mm]i\in\{1,\ldots,m+1\}.[/mm]
>
> Hattet ihr schon etwas zur Schleifeninvariante?
>
>
> Gruß
> DieAcht
Hallo DieAcht,
wir hatten nichts dergleichen, und ich habe dazu auch in beiden Skripten, auf denen die Vorlesung (angeblich) basiert keinerlei Hinweise darauf gefunden. Selbst die Wörter "Schleife" und "invariant" oder Abwandlungen davon tauchen nur allerhöchstens zweimal oder sogar gar nicht auf. Ist das nicht eigentlich auch ein Begriff aus der Informatik? Ich habe davon nur mal was im Zusammenhang mit Registermaschinen in einer Informatik-Vorlesung gehört und werde das dann wohl so auch kaum benutzen können/dürfen, denke ich mal.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:33 Mo 28.04.2014 | | Autor: | DieAcht |
Die "Richtigkeit" des Horner-Schemas findest du zum Beispiel
![[]](/images/popup.gif) hier, aber das ist nicht deine Aufgabe. Ich würde ohne Vor-
wissen probieren die Behauptung zu beweisen mit vollständiger
Induktion. Betrachte dazu
[mm] p_n(x):=a_nx^n+a_{n-1}x^{n-1}+\ldots+a_1x+a_0.
[/mm]
Ich habe aber nicht probiert ob das klappt.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:20 Mi 30.04.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 14:19 So 27.04.2014 | | Autor: | Tinitus |
for j = m+1, [mm] \dotsc [/mm] , 1 do
[mm] b_{1,j} [/mm] = [mm] a_j
[/mm]
end
for i = 1, [mm] \dotsc, [/mm] m do
[mm] b_{i+1,m+1} [/mm] = [mm] b_{i,m+1}
[/mm]
for j = m, [mm] \dotsc, [/mm] i do
[mm] b_{i+1,j} [/mm] = [mm] \bar t\cdot b_{i+1,j+1} [/mm] + [mm] b_{i,j}
[/mm]
end
end
[mm] b_{m+2,m+1} [/mm] = [mm] b_{m+1,m+1} [/mm]
am Beispiel:
11 + 7x - [mm] 5x^2 -4x^3 [/mm] + [mm] 2x^4 \;=\; [/mm] 11 + x [mm] \cdot\left(7 + x \cdot(-5 + x \cdot(-4 + x \cdot 2))\right) [/mm]
a1 = 11
a2 = 7
a3 = 5
a4 = 4
a5 = 2
ist wohl klar =) also muss dein m im Algo 4 sein:
Als erstes werden den [mm] b_{1,j} [/mm] die Werte deiner Koeefizienten des Polynoms zugeordnet:
[mm] b_{1,5} [/mm] = a5
[mm] b_{1,4} [/mm] = a4
[mm] b_{1,3} [/mm] = a3
[mm] b_{1,2} [/mm] = a2
[mm] b_{1,1} [/mm] = a1
Ende der ersten for-Schleife..
Kann man jetzt nicht einfach den Algorithmus weitermachen ?
Ich würde es halt so machen, den Algo mit einem Beispiel durchgehen..
Das Ergebnis ist dir ja bekannt.
Nur eine Idee von mir.
Grüße
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:35 Mo 28.04.2014 | | Autor: | Lustique |
> for j = m+1, [mm]\dotsc[/mm] , 1 do
> [mm]b_{1,j}[/mm] = [mm]a_j[/mm]
> end
> for i = 1, [mm]\dotsc,[/mm] m do
> [mm]b_{i+1,m+1}[/mm] = [mm]b_{i,m+1}[/mm]
>
> for j = m, [mm]\dotsc,[/mm] i do
> [mm]b_{i+1,j}[/mm] = [mm]\bar t\cdot b_{i+1,j+1}[/mm] + [mm]b_{i,j}[/mm]
> end
> end
> [mm]b_{m+2,m+1}[/mm] = [mm]b_{m+1,m+1}[/mm]
>
> am Beispiel:
> 11 + 7x - [mm]5x^2 -4x^3[/mm] + [mm]2x^4 \;=\;[/mm] 11 + x [mm]\cdot\left(7 + x \cdot(-5 + x \cdot(-4 + x \cdot 2))\right)[/mm]
>
> a1 = 11
> a2 = 7
> a3 = 5
> a4 = 4
> a5 = 2
>
> ist wohl klar =) also muss dein m im Algo 4 sein:
>
> Als erstes werden den [mm]b_{1,j}[/mm] die Werte deiner
> Koeefizienten des Polynoms zugeordnet:
> [mm]b_{1,5}[/mm] = a5
> [mm]b_{1,4}[/mm] = a4
> [mm]b_{1,3}[/mm] = a3
> [mm]b_{1,2}[/mm] = a2
> [mm]b_{1,1}[/mm] = a1
>
> Ende der ersten for-Schleife..
> Kann man jetzt nicht einfach den Algorithmus weitermachen
> ?
> Ich würde es halt so machen, den Algo mit einem Beispiel
> durchgehen..
> Das Ergebnis ist dir ja bekannt.
>
> Nur eine Idee von mir.
>
> Grüße
>
>
>
>
Hallo Tinitus, danke für den Tipp, aber das hat mich leider nicht wirklich weitergebracht (siehe Antwort/Frage an Abakus).
|
|
|
|
