Regola di Horner

Da Wikipedia, l'enciclopedia libera.

La regola di Horner o, più correttamente, l'algoritmo di Horner è un algoritmo inventato da William George Horner che 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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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[modifica | modifica sorgente]

Risorse[modifica | modifica sorgente]

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