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 $X-a$.

Komputado de la valoron de polinoma funkcio en iu punkto

Estu $P=\lambda _{n}X^{n}+\lambda _{n-1}X^{n-1}+...+\lambda _{0}$ polinomo super komuta ringo $A$ kaj estu $a$ iu elemento de $A$.

Por komputi $P(a)=\lambda _{n}a^{n}+\lambda _{n-1}a^{n-1}+...+\lambda _{0}$ eblas pensi, ke necesas unue komputi ciujn potencojn de $a$, multipliki poste tiujn per siaj koeficientoj $\lambda _{k}$, kaj fine sumi la tial akiratajn kvantojn. Se oni ankaŭ komputas $a^{n}$ multiplikante $a$ per si mem $n$ fojoj, tiam la komputado de $P(a)$ necesas $n+(n-1)+...+2+1=n(n+1)/2$ multiplikadojn. Tiu kvanto kreskas kvadrate de la grado $n$ de la polinomo. Rapida potencado ebligas pliefikigi la komputadon de $a^{n}$ kaj do de $P(a)$ : la kvanto de necesaj multiplikadoj tiam kreskas kiel $n\ln(n)$. Sed tiu ankoraŭ ne estas tiel rapida ol la Hornera metodo.

Por komputi $P(a)$ kun la Hornera metodo, unue skribu :

$P(a)=((...((\lambda _{n}a+\lambda _{n-1})a+\lambda _{n-2})a+...)+\lambda _{1})a+\lambda _{0}$

Tiam sufiĉas komputi sekvante la ordon de la parentezoj. Tiu metodo necesas sole $n$ multiplikadojn. La komputtempo estas tiumaniere proksimume proporcia al grado de la polinomo (adicii estas multe pli rapida ol multipliki).

Komputado de la kvocienton de polinomo per monomo $X-a$

Ni serĉu la kvocienton $Q$ de la polinomo $P=\lambda _{n}X^{n}+\lambda _{n-1}X^{n-1}+...+\lambda _{0}$ en sia eŭklida divido per $X-a$. Ni havas : $P=(X-a)Q+P(a)$

Se oni nun skribas $Q=q_{n-1}X^{n-1}+q_{n-2}X^{n-2}+...+q_{1}X+q_{0}$ kaj identigas la samgradajn koeficientojn el la du membroj, tiam aperas ke :

$q_{n-1}=\lambda _{n}$

$q_{k-1}=\lambda _{k}+aq_{k}$ je ĉiuj k kiel 0 < k < n

La valoro de P(a) estas ne alia ol λ₀ + aq₀.

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

Tabela ilustraĵo

Tabela prezentado de la Hornera metodo aperigas lia simplecon : ĉiu koeficiento de Q akiriĝas multiplikante la koeficienton de la liva fako per a kaj adiciante al tiu produto la koeficienton de la supera fako.

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 $4X^{3}-7X^{2}+3X-5$ per $X-2$

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

Tio havigas : $4X^{3}-7X^{2}+3X-5=(X-2)(4X^{2}+X+5)+5$.