1. Vyhodnocení polynomu — Hornerovo schéma P(x) = anxn + an_ixn ľ + ■ ■ ■ + a0, P (z) = ? Přímý výpočet: z2 = zz z3 = z2z zn = zn- -xz => n — 1 násobení CL\Z a2z2 CLnZ => n násobení a0 + CL\Z + . . + a„zn => n sečítání a- 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 n-l Celkem n násobení a n sečítání = teoretické minimum Věta 1.1 (Hornerovo schéma). P{x) = Pi(x)(x - z) + P0, Pi{x) = bnx"-1 + 6„_ix™-2 + • bk = ak + zbk+í, k = n - í,n - 2,.. ., 1,0 Důkaz. Pi(x)x + P0 = bnxn + bn-xxn-x + ... —z Pi (x) = - zbnxn^1 - ... -bi, b0:=P0 = P(z),\áe > n násobení a n sečítání. b2x2 b^zx2 bix + b0 b2zx — biz P (x) = anxn + an-ixn x + ... + a2x2 Odtud porovnáním koeficientů obdržíme požadované vztahy pro bk. a,ix a0 D Algoritmus. P '■ 0,n «n-l O-n-2 XZ+ XZ + 1= / 1= / 1 = bn bn_i bn_2 G>l (2o XZ + 1= / 1 = b0 = P(z) Důsledek 1.2 (Rozšířené Hornerovo schéma). Po(x) := P{x) = Pn(z)(x -z)n + --- + P2(z)(x - z)2 + Pi(z)(x - z) + P0(z), kde Pk(x) = Pk+i{x)(x - z) + Pk(z), k = 0,1,...,n-í. Důkaz. Rozklad z věty 1.1 aplikujeme n-krát postupně na Po(x), Pi(x),..., Pn_i(x): Po (x) = (. . . {{Pn{z){x -Z)+ Pn-l{z)){x -Z)+ Pn-2{Z)){X - Z) + ■ ■ ■ + Pl{z)){x - z) + P0(z). v----------------------v----------------------' Prr-l(x) D P1(x) Důsledek 1.3 (Výpočet k-té derivace pomocí rozšířeného Hornerova schématu). ,(fc) P^'(z) = klPk(z) pro k = 0,1, Důkaz. tow*-*>']!=.={!U pro j ± k (z) pro j = k D i 2 Algoritmus. P0 : an Pí: P2: 1 = 6(1) 1 = J2) an-l