Schemă Horner

De la Wikipedia, enciclopedia liberă
Salt la: Navigare, căutare

În analiza numerică schema Horner, numită după matematicianul englez William George Horner, este un algoritm pentru calculul eficient al valorii polinoamelor. Metoda Horner este un procedeu de aproximare a rădăcinilor unui polinom. Schema Horner poate fi folosită de asemenea pentru împărțirea polinoamelor liniare.

Istoric[modificare | modificare sursă]

Deși schema este numită după William George Horner, care a descris-o în 1819, metoda era cunoscută de Isaac Newton în 1669, și chiar mai demult de către matematicianul chinez Qín Jiǔshào în secolul al XIII-lea.

Descriere[modificare | modificare sursă]

Fiind dat polinomul

p(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n,

unde a_0, \ldots, a_n sunt numere reale, se cere calculul valorii polinomului pentru o valoare a lui x\,\! dată, de exemplu pentru x_0\,\!.

Pentru asta, se definește o secvență de constante după cum urmează:

b_n\,\! :=\,\! a_n\,\!
b_{n-1}\,\! :=\,\! a_{n-1} + b_n x_0\,\!
\vdots
b_0\,\! :=\,\! a_0 + b_1 x_0\,\!

Atunci b_0\,\! este valoarea lui p(x_0)\,\!.

Pentru a înțelege cum funcționează, polinomul poate fi pus în forma

p(x) = a_0 + x(a_1 + x(a_2 + \cdots x(a_{n-1} + a_n x)\dots))

apoi se substituie iterativ b_i în expresia

p(x_0)\,\! =\,\! a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(a_{n-1} + b_n x_0)\dots))
=\,\! a_0 + x_0(a_1 + x_0(a_2 + \cdots x_0(b_{n-1})\dots))
\vdots
=\,\! a_0 + x_0(b_1)\,\!
=\,\! b_0\,\!

Exemplu[modificare | modificare sursă]

Să se calculeze f_1(x)=2x^3-6x^2+2x-1\, pentru x=3\;. Prin extragerea repetată a factorului comun x\,, f_1\, poate fi adus la forma x(x(2x-6)+2)-1\,. Se folosește o formă sintetică de organizare a calculului.

     x_0 |   x^3    x^2     x^1   x^0 
 3 |   2    -6     2    -1
   |         6     0     6   
   |----------------------
       2     0     2     5

Valorile din rândul al treilea sunt sumele primelor două. Fiecare valoare din rândul al doilea este produsul lui x\, (în acest exemplu 3) cu valoarea imediat la stânga din rândul trei. Valorile din primul rând sunt coeficienții polinomului. Rezultatul este 5.

Această schemă se poate folosi și la împărțirea polinoamelor.

Eficiență[modificare | modificare sursă]

Dacă fiecare putere este calculată separat prin înmulțiri repetate, calculul valorii unui polinom de gradul n necesită n adunări și (n2 + n)/2 înmulțiri. (Asta poate fi redus la n adunări și 2n + 1 înmulțiri dacă puterile lui x sunt calculate iterativ.) În termeni de cifre (sau biți) algoritmul naiv trebuie să memoreze de cca. 2n ori numărul x (rezultatul având ordinul de mărime xn, deci și rezultatele intermediare trebuie memorate așa). Pron contrast, schema Horner necesită doar n adunări și n înmulțiri, și trebuie să memoreze doar de n ori un număr de cifre corespunzător lui x.

S-a arătat că schema Horner este optimă, în sensul că este nevoie de cel mai mic număr de operații. Că numărul de adunări este minim a fost arătat de Alexander Ostrowski în 1954; iar că numărul de înmulțiri este minim de Victor Pan, în 1966. Dacă însă x este o matrice, schema Horner nu mai este optimă, puteri ale lui x fiind deja calculate.[1]

Schema Horner este adesea folosită pentru conversia valorilor între diferite sisteme de numerație poziționale, unde x este baza sistemului, iar coeficienții ai sunt cifrele reprezentării numărului în baza x. Dacă x este o matrice, eficiența e chiar mai mare.

Note[modificare | modificare sursă]

  1. ^ Knuth, op. cit.

Bibliografie[modificare | modificare sursă]

  • en William George Horner. A new method of solving numerical equations of all orders, by continuous approximation. In Philosophical Transactions of the Royal Society of London, pp. 308-335, July 1819.
  • en Murray R. Spiegel Schaum's Outline of Theory and Problems of College Algebra, McGraw-Hill Book Company, 1956
  • Donald Knuth. Tratat de programare a calculatoarelor - Algoritmi seminumerici, Editura Tehnică, București, 1983
  • en Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Problema 2-3 (pg.39) și p.823 a secțiunii 30.1: Reprezentarea polinoamelor.

Legături externe[modificare | modificare sursă]