IT rekvalifikace s garancí práce. Seniorní programátoři vydělávají až 160 000 Kč/měsíc a rekvalifikace je prvním krokem. Zjisti, jak na to!
Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.

Hornerovho schéma

Hornerovho schéma je algoritmus pre efektívne výpočet mnohočlena v danom bode. Je užitočný napríklad pre prevod čísel do desiatkovej sústavy alebo zistenie derivácie mnohočlena.

Algoritmus

Majme mnohočlen P (x), kde c 0 až c n sú reálne koeficienty zodpovedajúcich členov polynómu. Chceme vypočítať hodnotu tejto funkcie.

P (x) = c 0 + c 1 x + c 2 x 2 + c 3 x 3 + ... + c n -1 x n-1 + c n x n

Naivný algoritmus

Jeden z možných spôsobov, ako taký mnohočlen spočítať pre danú hodnotu x, je vypočítať každý jeho člen zvlášť. To je pomerne náročné. Tento spôsob totiž vyžaduje n násobenie pre najvyššie člen, n-1 pre druhý najvyšší člen atď. Až jedno násobenie pre posledný člen polynómu. Budeme teda potrebovať n + (n-1) + (n-2) ... 1 násobenie. Členmi tohto radu tvoria aritmetickú postupnosť, kde je diferencia 1 (každý nasledujúci člen postupnosti sa od predchádzajúceho líši o 1). To znamená, že budeme potrebovať (n 2 + n) / 2 násobenie a n sčítanie, pretože vypočítané členmi musíme nakoniec sčítať, aby sme dostali požadovaný výsledok.

Popísaný algoritmus ide vylepšiť použitím efektívnejšieho spôsobu výpočtu mocniny (napríklad postupným násobením x od najnižšieho členovi). Existuje ale lepšie a jednoduchšie spôsob, ako rovnaký problém vyriešiť.

Hornerovho schéma

Uvedený mnohočlen P (x) môžeme upraviť postupným vytýkáním premennej x, takže jeho hodnotu v bode x potom možno vyhodnotiť rekurzívne vzťahom.

P (x) = c 0 + c 1 x + c 2 x 2 + c 3 x 3 + ... + c n -1 x n-1 + c n x n .<>
P (x) = c 0 + x (c 1 + c 2 x + c 3 x 2 + ... + c n -1 x n-2 + c n x n-1) .<>
P (x) = c 0 + x [c 1 + x (c 2 + c 3 x + ... + c n -1 x n-3 + c n x n-2)] .<>
P (x) = c 0 + x {c 1 + x [c 2 + x (c 3 + ... + c n -1 x n-4 + c n x n-3)]}

Až dostaneme tvar:

P (x) = c 0 + x (c 1 + x (c 2 + ... x (c n -1 + c n x) ...))

Hodnotu P (x) tak môžeme počítať od najvyššieho členu nasledujúcim spôsobom:

a n = c n .<>
a n -1 = c n -1 + x a n .<>
... .<>
a 0 = c 0 + x a 1

Členov je n + 1 a hodnota posledného výpočtu (a 0) sa rovná hodnote nášho mnohočlena. Z tejto definície vyplýva, že budeme potrebovať práve jedno násobenie a jedno sčítanie pre každý člen a okrem členovi a n (ten sa rovná c n). Pre n členov budeme teda potrebovať n násobenie a n sčítanie.

Príklad

Keďže sa daný spôsob môže zdať až moc abstraktné, pozrieme sa na konkrétny príklad a skúsime aplikovať popísaný postup - Hornerovho schému. Definujeme si mnohočlen P (x) ktorého najvyšší člen bude x 5 a pokúsime sa ho vypočítať v bode x = 2

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

V prvom rade si všimnite, že mnohočlen neobsahuje člen s x 3. To je úplne v poriadku, pretože u tohto člene predpokladáme koeficient 0 (teda c 3 = 0), čím sa člen síce vyruší, ale náš algoritmus bude aj v tomto prípade fungovať.

Postupným vytýkáním x dostaneme nasledujúce tvar:

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

Ak x = 2, môžeme postupne vypočítať hodnoty zátvoriek:

a 5 = 4 .<>
a 4 = 9 + a 5 x = 9 + 4 * 2 = 17 .<>
a 3 = 0 + a 4 x = 0 + 17 * 2 = 34 .<>
a 2 = 2 + a 3 x = 2 + 34 * 2 = 70 .<>
a 1 = 3 + a 2 x = 3 + 70 * 2 = 143 .<>
a 0 = 1 + a 1 x = 1 + 143 * 2 = 287 = P (2)

Využitia

Prevod čísla do desiatkovej sústavy

Prevod čísla z inej číselnej sústavy späť do desiatkovej sústavy je jedno z možných použití Hornerovho schémy. Každé číslo (C) v číselnej sústave o základe Z ide totiž napísať ako mnohočlen, kde koeficienty sú jednotlivé cifry čísla C a za x dosadíme samotný základ (Z). Majme teda napríklad číslo (2736) _8, ktoré chceme previesť do desiatkovej sústavy.

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

My však poznáme lepší spôsob, ako túto hodnotu vypočítať. Podľa Hornerovho schémy:

  1. Vezmeme prvý cifru čísla (2) a vynásobíme ju základom (8) = 16
  2. K výsledku prirátame ďalšie cifru čísla (7) a vynásobíme základom (8) = 184
  3. (184 + tretia cifra čísla (3)) * základ (8) = 1496
  4. 1496 + štvrtá cifra čísla (6) = 1502

Implementácia prevodu v konkrétnom programovacom jazyku (pozri sekcia implementácia) je potom veľmi jednoduchá. Ak už máme funkciu pre výpočet hodnoty mnohočlena (akou je napríklad popísané Hornerovho schéma), potom len stačí funkciu zavolať s konkrétnymi parametrami:

x = základ číselnej sústavy, z ktorej číslo prevádzame a koeficienty sú jednotlivé cifry tohto čísla

Derivácie mnohočlena

Algoritmus pre nájdenie derivácie mnohočlena môže byť užitočný napríklad pre nájdenie koreňov rovnice (tj. Všetkých hodnôt x, pre ktoré platí P (x) = 0) metódou dotyčníc. Navyše, ak v tomto prípade poznáme efektívny spôsob nájdenia derivácie P, môžeme zrýchliť celkový výpočet. Hornerovho schéma nám umožní spoločne s výpočtom hodnoty polynómu vypočítať aj jeho derivácii.

Ak vydelíme P (x) / (x - t) pre akúkoľvek hodnotu t, dostaneme nejaký polynóm (nižšieho stupňa) Q (x) a nejaký zvyšok r. Vynásobením (x - t) tak môžeme mnohočlen vyjadriť ako: P (x) = Q (x) (x - t) + r (všimnite si, že ak dosadíme x = t, potom P (t) = r). Zderivujem P a upravíme výraz podľa pravidla o deriváciu súčinu:

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

P '(t) = Q (t)

Aby sme vypočítali P '(t), stačí nám zistiť hodnotu Q v bode t.

Majme napríklad 5x 2 + 3x + 6. Chceme zistiť koeficienty po delení x - 2 (aby sme následne našli derivácii v bode 2):

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

  1. Prvý koeficient Q je prvým koeficientom P (teda 5)
  2. Druhý koeficient Q dostaneme tak, že predchádzajúce vynásobíme 2 a pripočítame nasledujúce koeficient P v poradí (3) = 5 * 2 + 3 = 13

Postup môžeme zovšeobecniť. Koeficienty Q (a [0] až a [n-1]) vyjadríme pomocou c 1 až c n (koeficientov P):

a [n-1] = c [n] .<>
a [i] = c [i + 1] + a [i + 1] * x

a [0] až a [n-1] sú teda jednotlivé členmi Hornerovho schéme pri výpočte hodnoty P (x). Derivácii tak môžeme vypočítať opäť Hornerovým schémou:

d [n-1] = a [n-1] .<>
d [i] = a [i + 1] + d [i + 1] * x

Funkciu Horner (pozri Implementácia) tak môžeme rozšíriť o výpočet derivácie jednoducho tak, že namiesto koeficientu budeme počítať s hodnotou predchádzajúceho členovi Hornerovho schémy pre výpočet samotnej hodnoty funkcie P (x).

Ukážka implementácia v jazyku Python, ktorá vráti usporiadanú dvojicu - (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)

Implementácia

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

Referencie


 

Všetky články v sekcii
Matematické algoritmy
Článok pre vás napísal Drahomír Hanák
Avatar
Užívateľské hodnotenie:
Ešte nikto nehodnotil, buď prvý!
Autor v současné době studuje Informatiku. Zajímá se o programování, matematiku a grafiku.
Aktivity