Cos'è horner?

Metodo di Horner

Il metodo di Horner (conosciuto anche come regola di Horner o schema di Horner) è un algoritmo efficiente per valutare un polinomio in un punto specifico. È particolarmente utile in contesti di calcolo dove l'efficienza è importante. Oltre alla valutazione del polinomio, il metodo di Horner può essere utilizzato per la divisione sintetica di un polinomio per un fattore lineare e per convertire numeri tra diverse basi numeriche.

L'idea chiave dietro il metodo di Horner è di riscrivere il polinomio in una forma che minimizzi il numero di moltiplicazioni. Consideriamo un polinomio di grado n:

p(x) = a<sub>n</sub>x<sup>n</sup> + a<sub>n-1</sub>x<sup>n-1</sup> + ... + a<sub>1</sub>x + a<sub>0</sub>

Possiamo riscriverlo come:

p(x) = (...((a<sub>n</sub>x + a<sub>n-1</sub>)x + a<sub>n-2</sub>)x + ... + a<sub>1</sub>)x + a<sub>0</sub>

Questa forma richiede solo n moltiplicazioni e n addizioni per valutare il polinomio.

Algoritmo

Per valutare il polinomio p(x) in un punto x<sub>0</sub>, l'algoritmo di Horner procede come segue:

  1. Inizializza un valore risultato = a<sub>n</sub>
  2. Per i che va da n-1 a 0:
    • risultato = risultato * x<sub>0</sub> + a<sub>i</sub>
  3. Il valore finale di risultato è p(x<sub>0</sub>)

Vantaggi

  • Efficienza: Riduce il numero di moltiplicazioni necessarie rispetto al calcolo diretto del polinomio.
  • Stabilità numerica: In alcune situazioni, il metodo di Horner può essere più stabile numericamente rispetto ad altri metodi di valutazione.
  • Divisione sintetica: Il metodo può essere facilmente adattato per eseguire la divisione sintetica di un polinomio per (x - x<sub>0</sub>). Questo implica anche che usando il metodo di Horner, si può calcolare la derivata del polinomio, applicando il metodo al polinomio risultante dalla divisione.

Applicazioni

  • Valutazione di polinomi
  • Divisione sintetica
  • Conversione di base numerica
  • Calcolo di derivate di polinomi (usando divisione sintetica)
  • Ricerca di radici di polinomi (in combinazione con altri algoritmi)

Per approfondire: