Algoritmo di horner

[eleonora-89]

qualcuno ha del materiale o saprebbe consigliarmi qualche sito con la spiegazione ed esempi dell'algoritmo di horner?
vi ringrazio anticipatamente

[Megan00b]

Forse ti riferisci a questo:
$p(x)=a_n+a_1x+...+a_0x^n$
Algoritmo:
${(s_0=a_0,),(s_i=s_{i-1}x+a_i,(i=1,...,n)):}$
In tal caso cosa vuoi sapere?

[eleonora-89]

volevo sapere se era possibile trovare del materiale con applicazioni dell'algoritmo visto che il mio libro riporta un banale esempio di un polinomio di quinto grado con coefficienti tutti unitari mentre sull'esame i polinomi sono più complicati...potresti aiutarmi?
comunque si l'algoritmo è quello...

[Megan00b]

Non ho capito concretamente cosa ti serva...però...
Prova a guardare qua:
http://it.wikipedia.org/wiki/Regola_di_Horner
e/o qua:
http://en.wikipedia.org/wiki/Horner_scheme

Poi ci sarebbe l'applicazione ai metodi iterativi di approssimazione funzionale. Un esempio semplice ce l'hai nell'interpolazione polinomiale o trigonometrica. Se vuoi calcolare un polinomio interpolante sulla base standard (nel caso di non malcondizionamento) o una DFT un metodo "semplice" è quello di applicare la regola di Horner [-Ruffini].
Un altro argomento considerato dall'analisi numerica è quello della stabilità del metodo di Horner rispetto all'algoritmo naturale per la valutazione del polinomio.

In sostanza l'algoritmo in sè nonha niente di speciale. Sono le use applicazioni ad essere interessanti.
Se il tuo interesse è orientato verso un'applicazione specifica del metodo dovresti cercare in qualche testo che si occupa di tale applicazione e che certamente ti mostra come e quando applicare il metodo di Horner.

[eleonora-89]

ah ok non pensavo avesse tutte queste applicazioni a me serve l'algoritmo per l'approssimazione del valore di un polinomio in un punto da usare in matlab ora il mio problema consiste nel trovare un coefficiente che va dichiarato nella function che vado a creare ed è il coefficiente dell'ultimo termine in x (quello di grado massimo) ottenuto dalle ripetute messe in evidenza parziali tutto qui grazie comunque

[Megan00b]

"lellina89":...a me serve l'algoritmo per l'approssimazione del valore di un polinomio in un punto ...

Che vuoi dire con "approssimare un polinomio"? Un polinomio basta calcolarlo in un punto sostituendo il punto al posto dell'incognita.
Se spieghi meglio forse posso aiutarti.

[eleonora-89]

allora...spero di non farti esaurire quindi mi scuso il problema è il calcolo del valore di un polinomio in un punto tanto per cominciare io ho il mio polinomio Pn(x)=a(0)x^n+a(1)x^(n-1)+....+a(n-1)x+a(n) lo devo portare nella forma Pn(x)=a(n)+x(a(n-1)+x(a(an-2)+....+x(a(1)+xa(0))...)) ti faccio un esempio : il polinomio che approssima la funzione arctan(x/2) è P(x)=x/2-x^3/(2^3*3)+x^5/(2^5*5)-x^7/(2^7*7)+...+(-1^N)*x^(2N+1)/[2^(N+1)*(N+1)] in questo polinomio devo ridurre il numero di moltiplicazioni quindi faccio delle ripetute messe in evidenza parziali e trovo questo polinomio P(x)=x/2(1-x^2/2^2(1/3-x^2/2^2(1/7-....x^2/2^2(1/(2N-3)-(x^2/2^2)*1/(2N+1))....))) la mia prima difficoltà è portare i polinomi in questa forma per trovare quel coefficiente che ti dicevo (in questo caso è 1/(2N+1)) la seconda è impostare il ciclo for nella function che vado a creare spero di essere stata chiara questa volta purtroppo non è un concetto molto chiaro per me e mi è anche difficile spiegarlo...sorry

[Megan00b]

Ma se il tuo obiettivo è scrivere una function che valuti il polinomio in un punto con Horner non hai bisogno di esplicitare la scrittura del polinomio in quella forma "raccolta".
Penso che basti qualcosa del genere (mi scuso per la poca eleganza del codice):

function [ p ] = horner( a , x )
%HORNER horner(a): a vettore dei coefficienti del polinomio 
%dal più alto in grado al più basso; x valore su cui valutare il polinomio.
deg=size(a);
deg=deg(2);
tmp=a(1)
for k=2:1:deg
    tmp=tmp*x+a(k);
end;
p=tmp;

Mi sembra che worki.

[eleonora-89]

purtroppo è proprio quello il problema il mio prof e vuole che sia fatto tutto come dice lui figurati che contraddice anche alcune cose del libro...e la parte più importante di tutto l'esercizio è quel cavolo di raccoglimento!!!

[Megan00b]

Guarda non ti so proprio dire. Fatto sta che il matlab tratta i polinomi come vettori (dei coefficienti). Quindi per il matlab non fa alcuna differenza se il polinomio glielo scrivi in forma standard o raccolto.

[eleonora-89]

si lo so che funziona così ma fare quel raccoglimento garantisce un risultato affetto da un errore minore ,dato che si lavora il algebra finita, perchè è minore il numero delle operazioni diciamo che è questo lo scopo del raccoglimento comunque ti ringrazio ti farò sapere come è andata... grazie ancora ciao