algoritmo horner

Messaggioda Nepler265 » 13/02/2020, 11:25

salve ho questo polinomio $ p(x) $= $3x^4 + 4x^3 - 2x^2 + 5x - 4 $

Si raccoglie x fra tutti i termini che ce l'hanno come fattore comune:
$p(x)$=$x(3x^3 + 4x^2 - 2x + 5) - 4$
Si ripete il procedimento:
$p(x)$=$x[x(3x^2 + 4x - 2) + 5] - 4$
Si ripete il procedimento:
$p(x)$=$x{x[x(3x + 4) - 2] + 5} - 4$
Fino a quando si arriva ad un binomio di primo grado.

Alla fine si deduce che si eseguono 4 moltiplicazioni e 4 addizioni, ma non riesco a "vederle" e "contarle".....
Qualcuno potrebbe aiutarmi ?
Nepler265
Starting Member
Starting Member
 
Messaggio: 24 di 25
Iscritto il: 18/09/2019, 11:05

Re: algoritmo horner

Messaggioda vict85 » 13/02/2020, 14:57

Tu stai trasformando \[3\cdot x \cdot x \cdot x \cdot x + 4 \cdot x \cdot x \cdot x + 2 \cdot x \cdot x + 5 \cdot x - 4\] in \[-4 + x \cdot \biggl( 5 + x \cdot \Bigl( 2 + x \cdot \bigl( 4 + x \cdot 3 \bigr) \Bigr) \biggr)\]

Ho esplicitato tutte le somme e i prodotti.

Il primo è equivalente al seguente:
\[\begin{align*}
m_1 &\leftarrow 3 \cdot x \\
m_2 &\leftarrow m_1 \cdot x \\
m_3 &\leftarrow m_2 \cdot x \\
m_4 &\leftarrow m_3 \cdot x \\
& \\
m_5 &\leftarrow 4 \cdot x \\
m_6 &\leftarrow m_5 \cdot x \\
m_7 &\leftarrow m_6 \cdot x \\
& \\
a_1 &\leftarrow m_4 + m_6 \\
& \\
m_8 &\leftarrow 2 \cdot x \\
m_9 &\leftarrow m_5 \cdot x \\
& \\
a_2 &\leftarrow a_1 + m_9 \\
& \\
m_{10} &\leftarrow 5 \cdot x \\
& \\
a_3 &\leftarrow a_2 + m_{10} \\
a_4 &\leftarrow a_3 - 4
\end{align*}\]
Invece, usindo l'algoritmo di Horner hai che:
\[\begin{align*}
m_1 &\leftarrow 3 \cdot x \\
a_1 &\leftarrow m_1 + 4 \\
& \\
m_2 &\leftarrow a_1 \cdot x \\
a_2 &\leftarrow m_2 + 2 \\
& \\
m_3 &\leftarrow a_2 \cdot x \\
a_3 &\leftarrow m_3 + 5 \\
& \\
m_4 &\leftarrow m_3 \cdot x \\
a_4 &\leftarrow m_4 - 4
\end{align*}\]

Nota che per i floating points, è spesso disponibile una operazione chiamata fused multiply–add (FMA). Quindi, per certi versi, si può dire che l'algorigmo di Horner usa 4 FMA.
vict85
Moderatore
Moderatore
 
Messaggio: 10062 di 10072
Iscritto il: 16/01/2008, 00:13
Località: Berlin

Re: algoritmo horner

Messaggioda Nepler265 » 13/02/2020, 15:21

ti ringrazio , sei stato chiarissimo ! :-) :-)
Nepler265
Starting Member
Starting Member
 
Messaggio: 25 di 25
Iscritto il: 18/09/2019, 11:05


Torna a Analisi Numerica e Ricerca Operativa

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite