Vidi fonton por Hornera algoritmo

'''Hornera algoritmo''' estas [[matematiko|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 [[eŭklida divido|kvocienton]] de [[polinomo]] per [[monomo]] <math>X-a</math>.

== Komputado de valoro de polinoma funkcio en iu punkto ==

Estu <math>P = \lambda_nX^n + \lambda_{n-1}X^{n-1} + ... + \lambda_0</math> polinomo super [[komuta ringo]] <math>A</math> kaj estu <math>a</math> iu elemento de <math>A</math>.

Pri komputo <math>P(a) = \lambda_na^n + \lambda_{n-1}a^{n-1} + ... + \lambda_0</math> eblas opinii, ke necesas unue komputi ĉiujn potencojn de <math>a</math>, multipliki poste tiujn per siaj koeficientoj <math>\lambda_k</math>, kaj fine sumi la tial ricevitajn kvantojn. Se oni ankaŭ komputas <math>a^n</math> multiplikante <math>a</math> per si mem <math>n</math> fojoj, do por la komputado de <math>P(a)</math> necesas <math>n + (n-1) + ... + 2 + 1= n(n+1)/2</math> multiplikojn. Tiu kvanto kreskas kvadrate de la grado <math>n</math> de la polinomo. [[Rapida potencado]] ebligas pliefikigi la komputadon de <math>a^n</math> kaj do por <math>P(a)</math> la kvanto de necesaj multiplikoj tiam kreskas kiel <math>n \ln(n)</math>. Sed tiu ankoraŭ ne estas tiel rapida kiel la Hornera metodo.

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

<math>P(a) = ((...((\lambda_na + \lambda_{n-1})a + \lambda_{n-2})a + ... ) + \lambda_1)a + \lambda_0</math>

Tiam sufiĉas komputi sekvante la ordon de la parentezoj. Tiu metodo necesas sole <math>n</math> 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 <math>X-a</math> ==

Oni serĉu la kvocienton <math>Q</math> de la polinomo <math>P = \lambda_nX^n + \lambda_{n-1}X^{n-1} + ... + \lambda_0</math> en sia [[eŭklida divido]] per <math>X-a</math>. Oni havas la jenon:
<math>P = (X-a)Q + P(a)</math>

Estu <math>Q = q_{n-1}X^{n - 1} + q_{n-2}X^{n-2}+ ...+ q_1X + q_0</math> . Se identigi la samgradajn koeficientojn el la du membroj, tiam montriĝas ke:
::<math>q_{n-1} = \lambda_n</math>
::<math>q_{k-1} = \lambda_k + aq_k</math> je ĉiuj ''k'' kiel 0 < ''k'' < ''n''

La valoro de ''P''(''a'') estas λ<sub>0</sub> + ''aq''<sub>0</sub>.

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.

{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |&nbsp;Koeficientoj de P&nbsp;
|width = "110"|''λ''<sub>n</sub>
|width = "180"|'''''λ<sub>n - 1</sub>'''''
|width = "180"|''λ<sub>n - 2</sub>''
|width = "50"|...
|width = "110"|''λ<sub>1</sub>''
|width = "110"|''λ<sub>0</sub>''
|-style="text-align:center"
| bgcolor="#b3e2d1" |Koeficientoj de Q||'''''q<sub>n - 1</sub> ='''''<br />''λ<sub>n</sub>''||''q<sub>n - 2</sub> =''<br />'''''aq<sub>n - 1</sub> + λ<sub>n - 1</sub>''''' ||''q<sub>n - 3</sub> =''<br />''aq<sub>n - 2</sub> + λ<sub>n - 2''</sub> || ... || ''q<sub>0</sub> =''<br />''aq<sub>1</sub> + λ<sub>1</sub>''
|bgcolor="#b3e2d1" |''r =''<br />''aq<sub>0</sub> + λ<sub>0</sub>''
|}

Cifereca ekzemplo: divido de <math>4X^3 - 7X^2 + 3X - 5</math> per <math>X - 2</math>
{| border cellspacing="0"
|-style="text-align:center"
| bgcolor="#b3e2d1" |&nbsp;Koeficientoj de P  &nbsp;
|width = "60"|4
|width = "130"| − 7
|width = "130"|3
|width = "180"|− 5
|-style="text-align:center"
| bgcolor="#b3e2d1" |Koeficientoj de Q||4||8 − 7 = 1||2 + 3 = 5
|bgcolor="#b3e2d1" |''r'' = 10 − 5 = 5
|}
El ĉi tio rezultiĝas: <math>4X^3 - 7X^2 + 3X - 5 = (X - 2)(4X^2 + X + 5)  + 5 </math>.

[[Kategorio:Algoritmoj]]
[[Kategorio:Polinomoj]]
[[Kategorio:Cifereca analitiko]]