Regola di Horner

La regola di Horner o, più correttamente, l'algoritmo di Horner è un algoritmo inventato da William George Horner che permette di valutare un polinomio

${\displaystyle P_{N}(x)=a_{0}x^{N}+a_{1}x^{N-1}+...+a_{N-1}x+a_{N}}$

svolgendo ${\displaystyle N}$ addizioni e ${\displaystyle N}$ moltiplicazioni, anziché le ${\displaystyle N}$ addizioni e ${\displaystyle {\frac {N(N+1)}{2}}}$ moltiplicazioni richieste con il metodo di valutazione tradizionale. Esso è quindi particolarmente adatto qualora si ricerchino radici reali di equazioni polinomiali con metodi iterativi.

Il polinomio ${\displaystyle P_{N}(x)}$ può infatti essere scritto nella forma:

${\displaystyle P_{N}(x)=a_{N}+x(a_{N-1}+x(a_{N-2}+\ldots +x(a_{1}+a_{0}x)\ldots ))}$

Pertanto, il valore di tale polinomio si può calcolare sfruttando la definizione ricorsiva:

${\displaystyle p_{0}=a_{0}}$

${\displaystyle p_{k+1}=p_{k}x+a_{k+1}}$

in cui ${\displaystyle 0\leq k\leq N-1}$.

Il metodo di Horner permette di calcolare con meno operazioni anche la derivata prima e la derivata seconda di ${\displaystyle p_{N}(x)}$.

A tal fine, si introduca il concetto di polinomio ridotto ${\displaystyle q_{N-1}(x)}$:

${\displaystyle q_{N-1}(x)={\frac {p_{N}(x)-p_{N}(x_{i})}{x-x_{i}}}=x^{N-1}+b_{1}x^{N-2}+\ldots +b_{N-2}x+b_{N-1}}$

con ${\displaystyle b_{0}=1}$, ${\displaystyle b_{k}=b_{k-1}x_{i}+a_{k}}$, ${\displaystyle k=1,2,\ldots ,N-1}$ e ${\displaystyle x_{i}}$ generico punto.

Sviluppando in serie di Taylor ${\displaystyle p_{N}(x)}$ nell'intorno del generico punto ${\displaystyle x_{i}}$, si ricava, dopo alcuni passaggi algebrici:

${\displaystyle q_{N-1}(x_{i})=p'_{N}(x_{i})=d_{N-1}}$

nella quale ${\displaystyle d_{0}=1}$, ${\displaystyle d_{k}=d_{k-1}x_{i}+b_{k}}$ e ${\displaystyle k=1,2,\ldots ,N-1}$.

Analogamente per la derivata seconda, riscrivendo il polinomio ridotto a partire da ${\displaystyle q_{N-1}}$, si ottiene:

${\displaystyle p''_{N}(x_{i})=2e_{N-2}}$

con ${\displaystyle e_{0}=1}$, ${\displaystyle e_{k}=d_{k-1}x_{i}+d_{k}}$ e ${\displaystyle k=1,2,\ldots ,N-2}$.

Note le approssimazioni delle radici reali di ${\displaystyle p_{N}(x)}$, è possibile, attraverso l'applicazione ricorsiva della definizione di polinomio ridotto, determinare il valore delle radici di ${\displaystyle p_{N}(x)}$ con precisione arbitraria. Per fare ciò:

1. Trovare la radice ${\displaystyle x_{1}}$ di ${\displaystyle p_{N}(x)}$ con un metodo iterativo per il calcolo degli zeri di una funzione, quali bisezione, tangenti, secanti o regula falsi, utilizzando le formule ricorsive appena ricavate per valutare il polinomio e le sue derivate.
2. Riapplicare il metodo iterativo al polinomio ridotto ${\displaystyle q_{N-1}(x)}$ con ${\displaystyle x_{i}=x_{1}}$ per trovare la seconda radice ${\displaystyle x_{2}}$ di ${\displaystyle p_{N}(x)}$.
3. Riapplicare il metodo iterativo al polinomio ridotto ${\displaystyle q_{N-2}(x)}$ con ${\displaystyle x_{i}=x_{2}}$ per trovare ${\displaystyle x_{3}}$.
4. Procedere allo stesso modo finché non si sono trovate tutte le radici desiderate.

Si osservi che il metodo consente di ottenere un'approssimazione delle radici di ${\displaystyle p_{N}(x)}$ a causa degli errori di arrotondamento che si commettono nel calcolo. Per ridurre tali errori si suggerisce generalmente di determinare le radici considerando l'ordine crescente dei loro valori assoluti ed, eventualmente, di utilizzare le soluzioni ottenute come soluzioni di partenza per riapplicare il metodo iterativo (bisezione, tangenti, secanti o regula falsi) direttamente al polinomio ${\displaystyle p_{N}(x)}$.

• http://domino.research.ibm.com/tchjr/journalindex.nsf/0/eb51aa3e081ca90c85256bfa00683e2f?OpenDocument
• http://www.physics.utah.edu/~detar/lessons/c++/array/node1.html
• https://web.archive.org/web/20041211061232/http://rkb.home.cern.ch/rkb/AN16pp/node120.html
• Horner's Rule Archiviato il 24 dicembre 2004 in Internet Archive. su PlanetMath

• (EN) Horner’s method, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Eric W. Weisstein, Regola di Horner / Regola di Horner (altra versione), su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica