1. Vyhodnocení polynomu — Hornerovo schéma
P(x) = anxn + an-\xn~x H-----Y a0,    P (z) = ?
Přímý výpočet:
a\z a2z a0 + a\z
zn = zn~1z => n — 1 násobení anzn =>   n násobení
+   ...    +   anzn =>   n sečítání
Celkem 2n — 1 násobení a n sečítání
Princip Hornerova schématu:
(...(( anz + an-i)z + an-2)z H-----h a{)z + a0
Celkem n násobení a n sečítání = teoretické minimum
Věta 1.1 (Hornerovo schéma).
P(x) = P1(x)(x-z)+P0, P\{x) = bnxn~l + bn_ixn~2 H-----h&i, b0 := P0 = P (z), kde
bn   — an
bk   =   a-k + zbk+i, k = n — 1, n — 2,.
Důkaz.
n násobení a n sečítání.
Pi(a;)a; + Po -zPi(a;)
bnxn   + bn_ixT' — zbnXn~
+
+   b2x2     +   bxx     + b0
b-izx
bozx
b\z
P(x) ~=   anxn   +   an-ixn 1   +   ~    +   a~2~x2     +   a\x    + ~clq
Odtud porovnáním koeficientů obdržíme požadované vztahy pro bk.
Algoritmus.
P '■     OLn a-n-1 dri-2     • • • «1
1=      /       1= /       1=        •••      1 =
bn &TI-1 bn_2      ••• &1
«0
/       1 =
b0 = P (z)
Důsledek 1.2 (Rozšířené Hornerovo schéma).
P0(x) := P(x) = Pn(z)(x -z)n + --- + P2(z)(x - z)2 + P!(z)(x - z) + P0(z), kde Pk(x) = Pk+1(x)(x - z) + Pk(z), k = 0,1,...,n - 1.
Důkaz. Rozklad z věty 1.1 aplikujeme n-krát postupně na Pq{x), P\{x), ..., Pn-i(x): Po(x) =
(... ((P„(z)(x -z) + Pn-i{z)){x -z) + Pn-2(z))(x -z) + --- + Pi{z)){x -z) + P0(z).
Pi(x)
Důsledek 1.3 (Výpočet fc-té derivace pomocí rozšířeného Hornerova schématu). P^\z) = k\Pk{z) prok = 0,l,...,n.
Důkaz.
\P(z)(x - zY]{k) = { ° pro j^k
l^(Z){x    z) ix=z     <  klpk{z) . = k .
i
Algoritmus.
Po :	a„			«71-2	ŕl2	ai	a0
Pl :	1 = b{1)	X2 + /	X2 + 1= / °Tl-l	1 = °n-2	XZ + •••      1= /"	XZ + 1= /	1 = °o
	1 =	/"	X2 + 1= /	1 =	XZ + •••      1= /	1 =	
P2 :	6(2)		°n-l	°n-2	°2	b^ =	Pi(z)
	1 =	/"	1 =				
Pn :	b(n)		°n-l —	Pn-i(z)			
	1 =						
	Pn(z)