Hornerovo schéma

Hornerovo schéma je algoritmus pro efektivní výpočet mnohočlenu v daném bodě. Je užitečný například pro převod čísel do desítkové soustavy nebo zjištění derivace mnohočlenu.

Algoritmus

Mějme mnohočlen P(x), kde c₀ až c_n jsou reálné koeficienty odpovídajících členů polynomu. Chceme vypočítat hodnotu této funkce.

P(x) = c₀ + c₁ x + c₂ x² + c₃ x³ + ... + c_n-1 xⁿ⁻¹ + c_n xⁿ

Naivní algoritmus

Jeden z možných způsobů, jak takový mnohočlen spočítat pro danou hodnotu x, je vypočítat každý jeho člen zvlášť. To je poměrně náročné. Tento způsob totiž vyžaduje n násobení pro nejvyšší člen, n-1 pro druhý nejvyšší člen atd. až jedno násobení pro poslední člen polynomu. Budeme tedy potřebovat n + (n-1) + (n-2) ... 1 násobení. Členy této řady tvoří aritmetickou posloupnost, kde je diference 1 (každý následující člen posloupnosti se od předchozího liší o 1). To znamená, že budeme potřebovat (n² + n) / 2 násobení a n sčítání, protože vypočítané členy musíme nakonec sečíst, abychom dostali požadovaný výsledek.

Popsaný algoritmus jde vylepšit použitím efektivnějšího způsobu výpočtu mocniny (třeba postupným násobením x od nejnižšího členu). Existuje ale lepší a jednoduší způsob, jak stejný problém vyřešit.

Hornerovo schéma

Uvedený mnohočlen P(x) můžeme upravit postupným vytýkáním proměnné x, takže jeho hodnotu v bodě x potom lze vyhodnotit rekurzivním vztahem.

P(x) = c₀ + c₁ x + c₂ x² + c₃ x³ + ... + c_n-1 xⁿ⁻¹ + c_n xⁿ

P(x) = c₀ + x (c₁ + c₂ x + c₃ x² + ... + c_n-1 xⁿ⁻² + c_n xⁿ⁻¹)

P(x) = c₀ + x [c₁ + x (c₂ + c₃ x + ... + c_n-1 xⁿ⁻³ + c_n xⁿ⁻²)]

P(x) = c₀ + x {c₁ + x [c₂ + x (c₃ + ... + c_n-1 xⁿ⁻⁴ + c_n xⁿ⁻³)]}

Až dostaneme tvar:

P(x) = c₀ + x (c₁ + x (c₂ + ... x (c_n-1 + c_n x)...))

Hodnotu P(x) tak můžeme počítat od nejvyššího členu následujícím způsobem:

a_n = c_n

a_n-1 = c_n-1 + x a_n

...

a₀ = c₀ + x a₁

Členů je n + 1 a hodnota posledního výpočtu (a₀) se rovná hodnotě našeho mnohočlenu. Z této definice vyplývá, že budeme potřebovat právě jedno násobení a jedno sčítání pro každý člen a kromě členu a_n (ten se rovná c_n). Pro n členů budeme tedy potřebovat n násobení a n sčítání.

Příklad

Jelikož se daný způsob může zdát až moc abstraktní, podíváme se na konkrétní příklad a zkusíme aplikovat popsaný postup - Hornerovo schéma. Definujeme si mnohočlen P(x) jehož nejvyšší člen bude x⁵ a pokusíme se ho vypočítat v bodě x = 2

P(x) = 1 + 3x + 2x² + 9x⁴ + 4x⁵

V první řadě si všimněte, že mnohočlen neobsahuje člen s x³. To je naprosto v pořádku, jelikož u tohoto členu předpokládáme koeficient 0 (tedy c₃ = 0), čímž se člen sice vyruší, ale náš algoritmus bude i v tomto případě fungovat.

Postupným vytýkáním x dostaneme následující tvar:

P(x) = 1 + x (3 + x (2 + x (0 + x(9 + 4x))))

Pokud x = 2, můžeme postupně vypočítat hodnoty závorek:

a₅ = 4

a₄ = 9 + a₅ x = 9 + 4 * 2 = 17

a₃ = 0 + a₄ x = 0 + 17 * 2 = 34

a₂ = 2 + a₃ x = 2 + 34 * 2 = 70

a₁ = 3 + a₂ x = 3 + 70 * 2 = 143

a₀ = 1 + a₁ x = 1 + 143 * 2 = 287 = P(2)

Využití

Převod čísla do desítkové soustavy

Převod čísla z jiné číselné soustavy zpět do desítkové soustavy je jedno z možných použití Hornerova schématu. Každé číslo (C) v číselné soustavě o základu Z jde totiž napsat jako mnohočlen, kde koeficienty jsou jednotlivé cifry čísla C a za x dosadíme samotný základ (Z). Mějme tedy například číslo (2736)_8 , které chceme převést do desítkové soustavy.

C = 2 * 8³ + 7 * 8² + 3 * 8 + 6 = 1024 + 448 + 24 + 6 = 1502

My však známe lepší způsob, jak tuto hodnotu vypočítat. Podle Hornerova schématu:

1. Vezmeme první cifru čísla (2) a vynásobíme ji základem (8) = 16
2. K výsledku přičteme další cifru čísla (7) a vynásobíme základem (8) = 184
3. (184 + třetí cifra čísla (3)) * základ (8) = 1496
4. 1496 + čtvrtá cifra čísla (6) = 1502

Implementace převodu v konkrétním programovacím jazyce (viz sekce Implementace) je pak velice jednoduchá. Pokud již máme funkci pro výpočet hodnoty mnohočlenu (jakou je například popsané Hornerovo schéma), pak jen stačí funkci zavolat s konkrétními parametry:

x = základ číselné soustavy, ze které číslo převádíme a koeficienty jsou jednotlivé cifry tohoto čísla

Derivace mnohočlenu

Algoritmus pro nalezení derivace mnohočlenu může být užitečný například pro nalezení kořenů rovnice (tj. všech hodnot x, pro které platí P(x) = 0) metodou tečen. Navíc, pokud v tomto případě známe efektivní způsob nalezení derivace P, můžeme zrychlit celkový výpočet. Hornerovo schéma nám umožní společně s výpočtem hodnoty polynomu vypočítat i jeho derivaci.

Pokud vydělíme P(x) / (x - t) pro jakoukoli hodnotu t, dostaneme nějaký polynom (nižšího stupně) Q(x) a nějaký zbytek r. Vynásobením (x - t) tak můžeme mnohočlen vyjádřit jako: P(x) = Q(x) (x - t) + r (všimněte si, že pokud dosadíme x = t, pak P(t) = r). Zderivujeme P a upravíme výraz podle pravidla o derivaci součinu:

P'(x) = Q'(x) (x - t) + Q(x)

P'(t) = Q(t)

Abychom vypočítali P'(t), stačí nám zjistit hodnotu Q v bodě t.

Mějme například 5x² + 3x + 6. Chceme zjistit koeficienty po dělení x - 2 (abychom následně našli derivaci v bodě 2):

(5x² + 3x + 6) : (x - 2) = 5x + 13 + R

1. První koeficient Q je prvním koeficientem P (tedy 5)
2. Druhý koeficient Q dostaneme tak, že předchozí vynásobíme 2 a přičteme následující koeficient P v pořadí (3) = 5 * 2 + 3 = 13

Postup můžeme zobecnit. Koeficienty Q (a[0] až a[n-1]) vyjádříme pomocí c₁ až c_n (koeficientů P):

a[n-1] = c[n]

a[i] = c[i + 1] + a[i + 1] * x

a[0] až a[n-1] jsou tedy jednotlivé členy Hornerova schématu při výpočtu hodnoty P(x). Derivaci tak můžeme vypočítat opět Hornerovým schématem:

d[n-1] = a[n-1]

d[i] = a[i+1] + d[i+1] * x

Funkci horner (viz Implementace) tak můžeme rozšířit o výpočet derivace jednoduše tak, že namísto koeficientu budeme počítat s hodnotou předchozího členu Hornerova schématu pro výpočet samotné hodnoty funkce P(x).

Ukázka implementace v jazyce Python, která vrátí uspořádanou dvojici - (P(x), P'(x)):

def horner(x, koeficient):
  p = 0
  dp = 0
  for c in koeficient:
    dp = p + dp * x
    p = c + p * x
  return (p, dp)

Implementace

int horner(int x, int* koeficienty, int stupen)
{
  int r = 0, i = 0;
  for (i = 0; i < stupen; i++)
  {
    r = r * x + koeficienty[i];
  }
  return r;
}

def horner(x, koeficient):
  r = 0
  for c in koeficient:
    r = r * x + c
  return r

var horner = function(x, koeficient) {
  var r = 0;
  for (var i in koeficient) {
    r = r * x + koeficient[i];
  }
  return r;
};

Reference

• Horner's Rule for a Polynomials. Horner's Rule for a Polynomial and Its Derivative [online]. 2007 [cit. 2015-06-03]. Dostupné z: http://www.physics.utah.edu/…y/node4.html
• Horner's Rule for Polynomials [online]. 2007 [cit. 2015-06-03]. Dostupné z: http://www.physics.utah.edu/…y/node1.html
• Horner's method. Horner's Method [online]. 2004 [cit. 2015-06-03]. Dostupné z: http://mathfaculty.fullerton.edu/…rnermod.html
• Horner's Method [online]. 2015 [cit. 2015-06-03]. Dostupné z: http://www.cut-the-knot.org/…Method.shtml
• Horner's Method [online]. 2015 [cit. 2015-06-03]. Dostupné z: http://en.wikipedia.org/…r%27s_method
• Umění programování: Seminumerické algoritmy. Brno: Computer Press, 2010, s. 319-329. ISBN 978-80-251-289-5.