Hornerovo schéma

Vydávání, hosting a aktualizace umožňují jeho sponzoři.
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 c0 až cn jsou reálné koeficienty odpovídajících členů polynomu. Chceme vypočítat hodnotu této funkce.
P(x) = c0 + c1 x + c2 x2 + c3 x3 + ... + cn-1 xn−1 + cn xn
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 (n2 + 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) = c0 + c1 x + c2 x2 + c3 x3 + ... + cn-1 xn−1 + cn xn
P(x) = c0 + x (c1 + c2 x + c3 x2 + ... + cn-1 xn−2 + cn xn−1)
P(x) = c0 + x [c1 + x (c2 + c3 x + ... + cn-1 xn−3 + cn xn−2)]
P(x) = c0 + x {c1 + x [c2 + x (c3 + ... + cn-1 xn−4 + cn xn−3)]}
Až dostaneme tvar:
P(x) = c0 + x (c1 + x (c2 + ... x (cn-1 + cn x)...))
Hodnotu P(x) tak můžeme počítat od nejvyššího členu následujícím způsobem:
an = cn
an-1 = cn-1 + x an
...
a0 = c0 + x a1
Členů je n + 1 a hodnota posledního výpočtu (a0) 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 an (ten se rovná cn). 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 x5 a pokusíme se ho vypočítat v bodě x = 2
P(x) = 1 + 3x + 2x2 + 9x4 + 4x5
V první řadě si všimněte, že mnohočlen neobsahuje člen s x3. To je naprosto v pořádku, jelikož u tohoto členu předpokládáme koeficient 0 (tedy c3 = 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:
a5 = 4
a4 = 9 + a5 x = 9 + 4 * 2 = 17
a3 = 0 + a4 x = 0 + 17 * 2 = 34
a2 = 2 + a3 x = 2 + 34 * 2 = 70
a1 = 3 + a2 x = 3 + 70 * 2 = 143
a0 = 1 + a1 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 * 83 + 7 * 82 + 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:
- Vezmeme první cifru čísla (2) a vynásobíme ji základem (8) = 16
- K výsledku přičteme další cifru čísla (7) a vynásobíme základem (8) = 184
- (184 + třetí cifra čísla (3)) * základ (8) = 1496
- 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 5x2 + 3x + 6. Chceme zjistit koeficienty po dělení x - 2 (abychom následně našli derivaci v bodě 2):
(5x2 + 3x + 6) : (x - 2) = 5x + 13 + R
- První koeficient Q je prvním koeficientem P (tedy 5)
- 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í c1 až cn (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.
Komentáře


Zobrazeno 8 zpráv z 8.