Hornera algoritmo

Hornera algoritmo estas matematika metodo uzata en cifereca analitiko, precize en polinoma kalkulo, aŭ por efike komputi la valoron de polinoma funkcio en iu punkto, aŭ por kalkuli kvocienton de polinomo per monomo .

 Komputado de valoro de polinoma funkcio en iu punkto 

Estu  polinomo super komuta ringo  kaj estu  iu elemento de .

Pri komputo  eblas opinii, ke necesas unue komputi ĉiujn potencojn de , multipliki poste tiujn per siaj koeficientoj , kaj fine sumi la tial ricevitajn kvantojn. Se oni ankaŭ komputas  multiplikante  per si mem  fojoj, do por la komputado de  necesas  multiplikojn. Tiu kvanto kreskas kvadrate de la grado  de la polinomo. Rapida potencado ebligas pliefikigi la komputadon de  kaj do por  la kvanto de necesaj multiplikoj tiam kreskas kiel . Sed tiu ankoraŭ ne estas tiel rapida kiel la Hornera metodo.

Por komputi  per la Hornera metodo, unue oni rearanĝu P(a) per jena maniero:

Tiam sufiĉas komputi sekvante la ordon de la parentezoj. Tiu metodo necesas sole  multiplikojn. La komputtempo estas tiumaniere proksimume proporcia al grado de la polinomo (adicio estas multe pli rapida ol multipliko).

 Komputado de kvociento de polinomo per monomo  

Oni serĉu la kvocienton  de la polinomo  en sia eŭklida divido per . Oni havas la jenon:

Estu  . Se identigi la samgradajn koeficientojn el la du membroj, tiam montriĝas ke:

 je ĉiuj k kiel 0 < k < n

La valoro de P(a) estas λ0 + aq0.

La tie komputataj n valoroj el la vico q precize estas la n sinsekvaj kvantoj komputitaj al la antaŭa ĉapitro dum la komputado de P(a). Tial sufiĉas memori tiujn sinsekvajn valorojn por povi skribi la kvocientan polinomon. La lasta valoro estas la resto.

 Tabela ilustraĵo 

Tabela prezentado de la Hornera metodo montras ĝian simplecon: ĉiu koeficiento de Q estas kalkulata multiplikante la koeficienton de la malsupra linio per a kaj adiciante al tiu produto la koeficienton de la supra linia.

 Koeficientoj de P λnλn - 1λn - 2...λ1λ0Koeficientoj de Qqn - 1 =λnqn - 2 =aqn - 1 + λn - 1 qn - 3 =aqn - 2 + λ<sub>n - 2</sub>  ...  q0 =aq1 + λ1r =aq0 + λ0

Cifereca ekzemplo: divido de  per 
 Koeficientoj de P   4 − 73− 5Koeficientoj de Q48 − 7 = 12 + 3 = 5r = 10 − 5 = 5
El ĉi tio rezultiĝas: .

Kategorio:Algoritmoj
Kategorio:Polinomoj
Kategorio:Cifereca analitiko