Regola di Horner

La regola di Horner, o, più correttamente, l'algoritmo di Horner permette di valutare un polinomio

$P_N(x) = x^N + a_1 x^{N-1} + ... + a_{N-1}x + a_N$

svolgendo N addizioni e N moltiplicazioni, anziché le N addizioni e $\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.

Calcolo del valore di un polinomio e delle sue derivate prima e seconda

Il polinomio $P_N (x)$ può infatti essere scritto nella forma:

$P_N(x) = a_N + x ( a_{N-1} + x ( a_{N-2} + ... + x (a_1 + x) ...))$

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

$p_0 = 1$

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

in cui $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 $p_N(x)$.

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

$q_{N-1}(x) = \frac{p_N(x)-p_{N} (x_i)}{x-x_i} = x^{N-1} + b_1 x^{N-2} + ... + b_{N-2}x + b_{N-1}$

con $b_0 = 1$, $b_k = b_{k-1} x_i + a_k$, $k = 1, 2, ..., N-1$ e $x_i$ generico punto.

Sviluppando in serie di Taylor $p_N (x)$ nell'intorno del generico punto $x_i$, si ricava, dopo alcuni passaggi algebrici:

$q_{N-1}(x_i) = p'_N(x_i) = d_{N-1}$

nella quale $d_0 = 1$, $d_k = d_{k-1}x_i + b_k$ e $k = 1, 2, ..., N-1$.

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

$p''_N(x_i) = 2 e_{N-2}$

con $e_0 = 1$, $e_k = d_{k-1} x_i + d_k$ e $k = 1, 2, ..., N-2$.

Applicazione al calcolo delle radici reali di un polinomio

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

1. Trovare la radice $x_1$ di $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 $q_{N-1}(x)$ con $x_i = x_1$ per trovare la seconda radice $x_2$ di $p_N(x)$.
3. Riapplicare il metodo iterativo al polinomio ridotto $q_{N-2}(x)$ con $x_i = x_2$ per trovare $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 $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 $p_N(x)$.

Bibliografia

• http://domino.research.ibm.com/tchjr/journalindex.nsf/0/eb51aa3e081ca90c85256bfa00683e2f?OpenDocument
• http://www.physics.utah.edu/~detar/lessons/c++/array/node1.html
• http://rkb.home.cern.ch/rkb/AN16pp/node120.html
• Horner's Rule su PlanetMath

Risorse

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