Î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.

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

Fiind dat polinomul

 

unde   sunt numere reale, se cere calculul valorii polinomului pentru o valoare a lui   dată, de exemplu pentru  .

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

     
     
 
     

Atunci   este valoarea lui  .

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

 

apoi se substituie iterativ   în expresia

     
   
 
   
   

Să se calculeze   pentru  . Prin extragerea repetată a factorului comun  ,   poate fi adus la forma  . Se folosește o formă sintetică de organizare a calculului.

  |                    
 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   (î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

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). Prin 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.

  1. ^ Knuth, op. cit.

Bibliografie

modificare
  • 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