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 punktoRedakti

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 Redakti

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ĵoRedakti

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 λ0
Koeficientoj de Q qn - 1 =
λn
qn - 2 =
aqn - 1 + λn - 1
qn - 3 =
aqn - 2 + λn - 2
... q0 =
aq1 + λ1
r =
aq0 + λ0

Cifereca ekzemplo: divido de   per  

 Koeficientoj de P   4 − 7 3 − 5
Koeficientoj de Q 4 8 − 7 = 1 2 + 3 = 5 r = 10 − 5 = 5

El ĉi tio rezultiĝas:  .