Schemă Horner

Î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

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

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

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ță

Dacă fiecare putere este calculată separat prin înmulțiri repetate, calculul valorii unui polinom de gradul n necesită n adunări și (n² + 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 xⁿ, 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 a_i sunt cifrele reprezentării numărului în baza x. Dacă x este o matrice, eficiența e chiar mai mare.

Note

^ Knuth, op. cit.

Bibliografie

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

Portal Matematică

[1] Knuth, op. cit.

[1]