En matemàtiques i informàtica, el mètode de Horner (o esquema de Horner) és un algorisme per a l'avaluació de polinomis. Rep el nom de William George Horner, tot i que és molt més antic, atribuït per Horner a Joseph-Louis Lagrange, i va ser descobert centenars d'anys abans per matemàtics xinesos i perses.600 years earlier, by the Chinese mathematician Qin Jiushao and 700 years earlier, by the Persian mathematician Sharaf al-Dīn al-Ṭūsī Després de la introducció dels ordinadors, aquest algorisme es va convertir en fonamental per calcular de manera eficient amb polinomis.
L'algorisme es basa en la regla de Horner, en què un polinomi s'escriu en forma imbricada : Això permet l'avaluació d'un polinomi de grau amb només
multiplicacions i sumes. Això és òptim, ja que hi ha polinomis de grau que no es poden avaluar amb menys operacions aritmètiques. https://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=rm&paperid=5823&option_lang=eng
El mètode de Horner i també fa referència a un mètode per aproximar les arrels dels polinomis, descrit per Horner el 1819. És una variant del mètode de Newton-Raphson que es va fer més eficient per al càlcul manual mitjançant l'aplicació de la regla de Horner. Es va utilitzar àmpliament fins que els ordinadors es van generalitzar al voltant del 1970.
Avaluació polinòmica i divisió llarga Donat el polinomi on són coeficients constants, el problema és avaluar el polinomi a un valor específic de
Per això, es defineix recursivament una nova seqüència de constants de la següent manera:
Aleshores és el valor de .
Per veure per què funciona això, el polinomi es pot escriure de la forma De la mateixa manera, es pot demostrar que:
Suggerint un procediment convenient per determinar el resultat de la divisió polinòmica
amb (que és igual a ) sent el residu de la divisió. Si és una arrel de , aleshores (és a dir, la resta és ) i un factor de .
Exemples Avaluar per .
x 0 │ x x x x
3 │ 2 −6 2 −1
│ 6 0 6
└─────────────────────────
2 0 2 5
Les entrades de la tercera fila són la suma de les de les dues primeres. Cada entrada de la segona fila és el producte del valor ( en aquest exemple) amb l'entrada de la tercera fila immediatament a l'esquerra. Les entrades de la primera fila són els coeficients del polinomi que s'ha d'avaluar. Aleshores, la resta de en divisió per és .
Però pel teorema del residu polinòmic, sabem que el residu és Així, .
En aquest exemple, si podem veure que , les entrades de la tercera fila. Per tant, la divisió sintètica (que en realitat va ser inventada i publicada per Ruffini 10 anys abans de la publicació de Horner) és més fàcil d'utilitzar; es pot demostrar que és equivalent al mètode de Horner.
Com a conseqüència del teorema del residu del polinomi, les entrades de la tercera fila són els coeficients del polinomi de segon grau, el quocient de en divisió per El residu és Això fa que el mètode de Horner sigui útil per a la divisió llarga de polinomis.
Eficiència Avaluació mitjançant la forma monomial d'un grau el polinomi requereix com a màxim addicions i multiplicacions, si les potències es calculen mitjançant multiplicacions repetides i cada monomi s'avalua individualment. El cost es pot reduir a addicions i multiplicacions avaluant les potències de per iteració.
Si les dades numèriques es representen en termes de dígits (o bits), l'algorisme ingenu també implica emmagatzemar aproximadament vegades el nombre de bits de : el polinomi avaluat té una magnitud aproximada , i també cal emmagatzemar en si mateix. En canvi, el mètode de Horner només requereix addicions i multiplicacions, i els seus requisits d'emmagatzematge només són vegades el nombre de bits de Alternativament, el mètode de Horner es pot calcular amb multiplicacions-sumes fusionades. El mètode de Horner també es pot ampliar per avaluar el primer derivades del polinomi amb sumes i multiplicacions. https://dl.acm.org/doi/10.1145/364063.364089
El mètode de Horner és òptim, en el sentit que qualsevol algorisme per avaluar un polinomi arbitrari ha d'utilitzar com a mínim el mateix nombre d'operacions. Alexander Ostrowski va demostrar el 1954 que el nombre d'addicions necessàries és mínim. https://www.sciencedirect.com/book/monograph/9781483232720/studies-in-mathematics-and-mechanics Victor Pan va demostrar el 1966 que el nombre de multiplicacions és mínim. Tanmateix, quan és una matriu, el mètode de Horner no és òptim.
Això assumeix que el polinomi s'avalua en forma monomial i no es permet el precondicionament de la representació, cosa que té sentit si el polinomi només s'avalua una vegada. Tanmateix, si es permet el precondicionament i el polinomi s'ha d'avaluar moltes vegades, aleshores són possibles algorismes més ràpids. Impliquen una transformació de la representació del polinomi. En general, un grau- El polinomi es pot avaluar només utilitzant multiplicacions de ⌊n/2]+2 i addicions.
Avaluació paral·lela Un desavantatge de la regla de Horner és que totes les operacions són seqüencialment dependents, de manera que no és possible aprofitar el paral·lelisme a nivell d'instrucció en els ordinadors moderns. En la majoria d'aplicacions on l'eficiència de l'avaluació polinòmica importa, molts polinomis d'ordre inferior s'avaluen simultàniament (per a cada píxel o polígon en gràfics per ordinador, o per a cada quadrat de la quadrícula en una simulació numèrica), de manera que no cal trobar paral·lelisme dins d'una sola avaluació polinòmica.
Aplicació a la multiplicació i divisió en coma flotant El mètode de Horner és un mètode ràpid i eficient en el codi per a la multiplicació i divisió de nombres binaris en un microcontrolador sense multiplicador de maquinari. Un dels nombres binaris que s'han de multiplicar es representa com un polinomi trivial, on (utilitzant la notació anterior) , i Aleshores, x (o x a una certa potència) es factoritza repetidament. En aquest sistema de numeració binari (base 2), , de manera que les potències de 2 es factoritzen repetidament.
Exemple Per exemple, per trobar el producte de dos nombres (0,15625) i m :
Trobar arrels polinòmiques Utilitzant l'algorisme de divisió llarga en combinació amb el mètode de Newton, és possible aproximar les arrels reals d'un polinomi. L'algorisme funciona de la següent manera. Donat un polinomi de grau amb zeros fer alguna conjectura inicial de tal manera que Ara itera els dos passos següents:
Utilitzant el mètode de Newton, trobeu el zero més gran de utilitzant l'endevinació . Utilitzant el mètode de Horner, dividiu obtenir Torna al pas 1 però utilitza el polinomi i la conjectura inicial .
Aquests dos passos es repeteixen fins que es troben tots els zeros reals per al polinomi. Si els zeros aproximats no són prou precisos, els valors obtinguts es poden utilitzar com a estimacions inicials per al mètode de Newton, però utilitzant el polinomi complet en lloc dels polinomis reduïts.
Exemple miniatura|400x400px|Trobar arrels polinòmiques mitjançant el mètode de Horner Considereu el polinomi que es pot ampliar a A partir de l'anterior sabem que l'arrel més gran d'aquest polinomi és 7, de manera que podem fer una conjectura inicial de 8. Utilitzant el mètode de Newton, el primer zero de 7 es troba tal com es mostra en negre a la figura de la dreta. A continuació
es divideix per obtenir que està dibuixat en vermell a la figura de la dreta. El mètode de Newton s'utilitza per trobar el zero més gran d'aquest polinomi amb una estimació inicial de 7. El zero més gran d'aquest polinomi, que correspon al segon zero més gran del polinomi original, es troba a 3 i està encerclat en vermell. El polinomi de grau 5 ara es divideix per obtenir que es mostra en groc. El zero d'aquest polinomi es troba de nou a 2 utilitzant el mètode de Newton i està encerclat en groc. Ara s'utilitza el mètode de Horner per obtenir que es mostra en verd i que té un zero a − 3. Aquest polinomi es redueix encara més a que es mostra en blau i dóna un zero de − 5. L'arrel final del polinomi original es pot trobar utilitzant el zero final com a estimació inicial per al mètode de Newton o reduint i resolent l'equació lineal. Com es pot veure, es van trobar les arrels esperades de − 8, − 5, − 3, 2, 3 i 7.
Diferència dividida d'un polinomi El mètode de Horner es pot modificar per calcular la diferència dividida Donat el polinomi (com abans) procediu de la següent manera https://web.archive.org/web/20170814190521/https://people.eecs.berkeley.edu/~fateman/papers/nform.pdf En finalitzar, tenim
Aquest càlcul de la diferència dividida està subjecte a menys error d'arrodoniment que l'avaluació i per separat, sobretot quan .
Derivada d'un polinomi Substituint en aquest mètode dóna , la derivada de Avaluar un polinomi i la seva derivada en un punt és útil per trobar arrels mitjançant el mètode de Newton.
Història Tot i que a Horner se li atribueix el mèrit de fer que el mètode fos accessible i pràctic, era conegut molt abans que Horner. En ordre cronològic invers, el mètode de Horner ja era conegut per:
Paolo Ruffini el 1809 (vegeu la regla de Ruffini) https://projecteuclid.org/page-not-found?aspxerrorpath=%2fDPubS%2fRepository%2f1.0%2fDisseminate Isaac Newton el 1669Analysis Per Quantitatum Series, Fluctiones ac Differentias : Cum Enumeratione Linearum Tertii Ordinis, Londini. Ex Officina Pearsoniana. Anno MDCCXI, p. 10, 4th paragraph.Newton's collected papers, the edition 1779, in a footnote, vol. I, p. 270-271 el matemàtic xinès Zhu Shijie al segle XIV el matemàtic xinès Qin Jiushao al seu Tractat matemàtic en nou seccions al segle XIII el matemàtic persa Sharaf al-Dīn al-Ṭūsī al segle XII (el primer a utilitzar aquest mètode en un cas general d'equació cúbica) https://www.jstor.org/stable/604533?origin=crossref el matemàtic xinès Jia Xian al segle XI (dinastia Song) Els Nou Capítols sobre l'Art Matemàtic, una obra xinesa de la dinastia Han (202 aC – 220 dC) editat per Liu Hui (segle III).
Referències
Categoria:Polinomis Categoria:Anàlisi numèrica