Hornerovo schéma

Algoritmy Matematické 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 c0cn 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:

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

  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[n-1]) vyjádříme pomocí c1cn (koeficientů P):

a[n-1] = c[n]

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

a[0]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


 

  Aktivity (1)

Článek pro vás napsal Drahomír Hanák
Avatar
Autor v současné době studuje Informatiku. Zajímá se o programování, matematiku a grafiku.

Jak se ti líbí článek?
Celkem (1 hlasů) :
55555


 


Miniatura
Všechny články v sekci
Matematické algoritmy
Miniatura
Následující článek
Eratosthenovo síto

 

 

Komentáře

Avatar
Kit
Redaktor
Avatar
Kit:

Trochu jsem ten kód pro PHP zjednodušil:

 // Deklarujeme proměnné - číslo opět jako String
$zakl = 2;
$cislo = "1010";
$vysl = 0;
// Projdeme cifry čísla
for($i = 0; $i < strlen($cislo); $i++) {
        // Hornerovo schéma
        $vysl = $vysl*$zakl + $cislo[$i];
}

// Vypíšeme ho
echo $vysl;
Odpovědět  +2 4.5.2012 10:15
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Milan
Neregistrovaný
Avatar
Milan:

prosím o zkontrolování př: 2361 v 5 soustavě do desítkové:
(x = 5) - 2*5 = 10
(10+3)*5 = 65
(65+6)*5 = 355
355+1 = 356 vy = 0;
vy = (0+356) = 356;
vy = (356+65)*5 = 18100;
vy = (18100+10)*5 = 90550;
vy = vy / 5;
vy = 18110; -- je to správně?

 
Odpovědět 29.5.2013 10:36
Avatar
Kit
Redaktor
Avatar
Odpovídá na Milan
Kit:

Máš to chaotické už v zadání, takže to správně určitě není.

Odpovědět 29.5.2013 11:17
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
Milan
Neregistrovaný
Avatar
Milan:

To zadání je příklad z tohohle článku uplně stejné, takže asi chaotické nebude
číslo 2361 z pětkové do desítkové soustavy.

 
Odpovědět 29.5.2013 13:58
Avatar
Kit
Redaktor
Avatar
Odpovídá na Milan
Kit:

Jenže 2361 není číslo zapsané v pětkové soustavě.

Odpovědět 29.5.2013 14:02
Vlastnosti objektů by neměly být veřejné. A to ani prostřednictvím getterů/setterů.
Avatar
David Čápka
Tým ITnetwork
Avatar
Odpovídá na Kit
David Čápka:

Je to špatně v článku, napíšu Drahošovi ať to opraví :)

Odpovědět 29.5.2013 14:16
Miluji svou práci a zdejší komunitu, baví mě se rozvíjet, děkuji každému členovi za to, že zde působí.
Avatar
Blaze
Člen
Avatar
Blaze:

2361 nieje cislo v 5tkovej sustave mozu sa pouzivat cifry len 0-4 ...

 
Odpovědět 22.4.2015 7:55
Avatar
Drahomír Hanák
Tým ITnetwork
Avatar
Odpovídá na Blaze
Drahomír Hanák:

Máš pravdu, díky za upozornění. Změnil jsem ten základ a nevšiml jsem si toho.

 
Odpovědět 22.4.2015 8:25
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 8 zpráv z 8.