Hornerova šema

Polinom se obično zapisuje u obliku

$f(x)=\sum_{k=0}^{n} a_k x^k$

ili, član po član,

$f(x)=a_0+a_1x+a_2x^2+\dots+a_nx^n,$

gde su realni brojevi $a_0, a_1, \dots, a_n$ koeficijenti polinoma, a $x$ je promenljiva.

Ako je ${a_n\ne 0},$ kažemo da je polinom $n$-tog stepena, to jest ${\deg f(x)=n},$ gde je $n$ najveći izložilac promenljive.

Kako radi Hornerova šema

Hornerova šema (zove se i Hornerov metod ili Hornerovo pravilo) jeste algoritam koji pojednostavljuje izračunavanje vrednosti polinoma $f(x)$ za datu vrednost ${x=x_0}.$ Polinom se zapisuje kao niz izraza prvog stepena umetnutih jedan u drugi. Za svaki od njih potrebno je najviše jedno množenje i jedno sabiranje, a rezultat svakog koraka koristi se u sledećem. Istim postupkom polinom se deli sa ${x-x_0},$ pa se u literaturi na engleskom jeziku ovaj postupak naziva i sintetičko deljenje.

Da bismo to objasnili, zapišimo vrednost polinoma za $x_0$ u razvijenom obliku:

$f(x_0)=a_0+a_1x_0+a_2x_0^2+\dots+a_nx_0^n$

Ako $x_0$ uzastopno izvlačimo ispred zagrade, dobijamo zapis

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+\dots+{x_0(a_{n-1}+a_nx_0)\dots)))}$

Algoritam računa izraze u zagradama jedan po jedan, počevši od unutrašnje zagrade i krećući se ka spoljašnjim.

Postupak se sastoji od sledećih koraka:

1. Neka je ${k=n}.$
2. Neka je ${b_k=a_k}.$
3. Neka je ${b_{k-1}=a_{k-1}+x_0b_k}.$
4. Smanjimo $k$ za $1.$
5. Ako je ${k\ge 1},$ vraćamo se na korak 3; u suprotnom je postupak završen.

Poslednji dobijeni broj je vrednost polinoma: ${b_0=f(x_0)}.$

Uzmimo, na primer, polinom petog stepena:

$f(x)=a_0+a_1x+a_2x^2+a_3x^3+a_4x^4+a_5x^5$

Njegova vrednost za ${x=x_0}$ računa se tako što se polinom zapiše u obliku

$f(x_0)=a_0+x_0(a_1+x_0(a_2+x_0(a_3+{x_0(a_4+a_5x_0))))}$

Koraci algoritma mogu se zapisati u tabeli:

$k$	$b_k$
$5$	${b_5=a_5}$
$4$	${b_4=a_4+x_0b_5}$
$3$	${b_3=a_3+x_0b_4}$
$2$	${b_2=a_2+x_0b_3}$
$1$	${b_1=a_1+x_0b_2}$
$0$	${b_0=a_0+x_0b_1}$

Primer. Izračunajte vrednost polinoma ${f(x)=x^4+3x^3+5x^2+7x+9}$ za ${x=2}.$

Rešenje. Polinom je četvrtog stepena, pa je ${n=4}.$ Ovde je ${x_0=2},$ a koeficijenti su ${a_4=1},$ ${a_3=3},$ ${a_2=5},$ ${a_1=7}$ i ${a_0=9}.$

$k$	Korak	Rezultat
$4$	${b_4=1}$	$1$
$3$	${b_3=3+2\cdot 1}$	$5$
$2$	${b_2=5+2\cdot 5}$	$15$
$1$	${b_1=7+2\cdot 15}$	$37$
$0$	${b_0=9+2\cdot 37}$	$83$

Dakle, ${f(2)=83}.$

Hornerova šema u obliku tabele

U praksi se zapisuju samo brojevi, u tabeli sa tri reda. I ta tabela se naziva Hornerova šema. U prvom redu su koeficijenti polinoma, levo stoji broj $x_0,$ a treći red se popunjava sleva nadesno:

$\begin{array}{c|cccc|c} & a_n & a_{n-1} & \cdots & a_1 & a_0 \\ x_0 & & x_0b_n & \cdots & x_0b_2 & x_0b_1 \\ \hline & b_n & b_{n-1} & \cdots & b_1 & b_0\end{array}$

1. U prvi red upišite koeficijente po opadajućim stepenima promenljive $x.$ Ako neki stepen nedostaje, na njegovo mesto upišite $0.$
2. Prepišite prvi koeficijent u treći red: ${b_n=a_n}.$
3. Pomnožite upravo upisani broj sa $x_0$ i proizvod upišite u drugi red sledeće kolone.
4. Saberite dva broja u toj koloni i zbir upišite ispod njih, u treći red.
5. Ponavljajte korake 3 i 4 dok ne popunite poslednju kolonu.

Za polinom ${x^4+3x^3+5x^2+7x+9}$ i ${x_0=2}$ iz prethodnog primera šema izgleda ovako:

$\begin{array}{r|rrrr|r} & 1 & 3 & 5 & 7 & 9 \\ 2 & & 2 & 10 & 30 & 74 \\ \hline & 1 & 5 & 15 & 37 & 83\end{array}$

Poslednji broj u trećem redu je vrednost polinoma: ${f(2)=83}.$

Deljenje binomom prvog stepena

Treći red šeme daje više od same vrednosti $f(x_0).$

Za proveru izmnožimo desnu stranu. Koeficijent uz $x^n$ je ${b_n=a_n},$ a koeficijent uz svaki niži stepen $x^k$ je ${b_k-x_0b_{k+1}},$ što je jednako $a_k,$ jer je ${b_k=a_k+x_0b_{k+1}}.$

Ako u jednakosti stavimo ${x=x_0},$ ponovo dobijamo ${f(x_0)=b_0}.$ To je Bezuova teorema (Bezuov stav): ostatak pri deljenju polinoma $f(x)$ sa ${x-x_0}$ jednak je $f(x_0).$

U prethodnom primeru treći red čine brojevi $1;$ $5;$ $15;$ $37$ i $83,$ pa je količnik ${x^3+5x^2+15x+37},$ a ostatak je $83$:

${x^4+3x^3+5x^2+7x+9}={(x-2)(x^3+5x^2+15x+37)}+83$

Primer. Podelite ${f(x)=2x^4-3x^2+5x-7}$ sa ${x+2}.$

Rešenje. Pošto je ${x+2=x-(-2)},$ imamo ${x_0=-2}.$ Polinom nema član sa $x^3,$ pa je koeficijent uz $x^3$ jednak $0,$ a prvi red je $2;$ $0;$ $-3;$ $5;$ $-7.$

$\begin{array}{r|rrrr|r} & 2 & 0 & -3 & 5 & -7 \\ -2 & & -4 & 8 & -10 & 10 \\ \hline & 2 & -4 & 5 & -5 & 3\end{array}$

Količnik je ${2x^3-4x^2+5x-5},$ a ostatak je $3$:

${2x^4-3x^2+5x-7}={(x+2)(2x^3-4x^2+5x-5)}+3$

Provera pomoću Bezuove teoreme: ${f(-2)}={2\cdot 16-3\cdot 4+5\cdot(-2)-7}={32-12-10-7}={3}.$

Nule polinoma i rastavljanje na činioce

Ako je ostatak $b_0$ jednak $0,$ onda je ${f(x_0)=0}.$ Broj $x_0$ je nula (koren) polinoma, a polinom je deljiv sa ${x-x_0}$:

$f(x)=(x-x_0)\,q(x)$

Zato je Hornerova šema zgodna za rastavljanje na činioce. Ako polinom sa celobrojnim koeficijentima ima celobrojnu nulu, ta nula je delilac slobodnog člana $a_0.$ Delioce broja $a_0$ proveravamo jedan po jedan, a Hornerova šema svaki put pokazuje da li je taj broj nula polinoma i odmah daje količnik. Ako poslednji broj u trećem redu nije $0,$ taj broj nije nula polinoma, pa proveravamo sledeći delilac.

Primer. Rastavite na činioce polinom ${x^3-6x^2+11x-6}.$

Rešenje. Delioci slobodnog člana su $\pm 1;$ $\pm 2;$ $\pm 3$ i $\pm 6.$ Počinjemo sa ${x_0=1}$:

$\begin{array}{r|rrr|r} & 1 & -6 & 11 & -6 \\ 1 & & 1 & -5 & 6 \\ \hline & 1 & -5 & 6 & 0\end{array}$

Ostatak je $0,$ pa je $1$ nula polinoma i ${x^3-6x^2+11x-6}={(x-1)(x^2-5x+6)}.$ Nastavljamo sa količnikom ${x^2-5x+6}$ i ${x_0=2}$:

$\begin{array}{r|rr|r} & 1 & -5 & 6 \\ 2 & & 2 & -6 \\ \hline & 1 & -3 & 0\end{array}$

Ostatak je ponovo $0,$ pa je ${x^2-5x+6}={(x-2)(x-3)}.$ Dakle,

${x^3-6x^2+11x-6}={(x-1)(x-2)(x-3)}$

Racionalne nule traže se na isti način: ako je neskrativ razlomak $\frac{p}{q}$ nula polinoma sa celobrojnim koeficijentima, onda $p$ deli $a_0,$ a $q$ deli vodeći koeficijent $a_n.$

Delilac oblika mx + n

Pomoću Hornerove šeme možemo deliti i bilo kojim polinomom prvog stepena ${mx+n}.$ Njegova nula je ${x_0=-\frac{n}{m}},$ a ${mx+n=m(x-x_0)},$ pa je

$f(x)={(x-x_0)\,q(x)+b_0}={(mx+n)\cdot\frac{q(x)}{m}+b_0}$

Popunimo šemu za $x_0,$ a zatim koeficijente količnika podelimo sa $m.$ Ostatak se ne menja.

Primer. Podelite ${3x^3-5x^2+2x+3}$ sa ${2x-1}.$

Rešenje. Nula delioca je ${x_0=\frac12}.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 3 & -5 & 2 & 3 \\ \dfrac12 & & \dfrac32 & -\dfrac74 & \dfrac18 \\ \hline & 3 & -\dfrac72 & \dfrac14 & \dfrac{25}{8}\end{array}$

Deljenje sa ${x-\frac12}$ daje količnik ${3x^2-\frac72x+\frac14}$ i ostatak $\frac{25}{8}.$ Koeficijente količnika delimo sa $2$:

${3x^3-5x^2+2x+3}={(2x-1)\left(\frac32x^2-\frac74x+\frac18\right)}+\frac{25}{8}$

Kada je delilac drugog ili višeg stepena, koristi se pismeno deljenje polinoma.

Zašto koristimo Hornerovu šemu?

Kada računamo vrednost polinoma za neku vrednost promenljive, obično tu vrednost zamenimo u polinom i izvršimo računanje. Za to možemo upotrebiti ili napisati računarski program, što postaje neophodno kada radimo sa složenim polinomima visokog stepena.

Način na koji računar rešava zadatak zavisi uglavnom od toga kako mu ga vi, kao programer, opišete. Program može računati vrednost polinoma direktnom zamenom ili Hornerovom šemom. Jedina razlika između ova dva pristupa je brzina kojom računar dolazi do rezultata.

Prednost Hornerove šeme je u tome što smanjuje broj množenja. Pri direktnoj zameni, ako se svaki stepen računa iznova, za član $a_kx^k$ potrebno je $k$ množenja, pa je za polinom stepena $n$ potrebno ukupno ${1+2+\dots+n}={\frac{n(n+1)}{2}}$ množenja. Hornerovoj šemi treba samo $n$ množenja i $n$ sabiranja. Za polinom desetog stepena to je $10$ množenja umesto $55.$ U oba postupka ima $n$ sabiranja, pa je sva ušteda u množenjima, i za polinome visokog stepena program koji koristi Hornerovu šemu radi primetno brže.

Vežbe

Rešite zadatke Hornerovom šemom, a zatim otvorite rešenja. Svaki korak možete proveriti i pomoću kalkulatora pri vrhu stranice.

1. Izračunajte $f(3)$ za polinom ${f(x)=2x^3-5x^2+x-7}.$

$\begin{array}{r|rrr|r} & 2 & -5 & 1 & -7 \\ 3 & & 6 & 3 & 12 \\ \hline & 2 & 1 & 4 & 5\end{array}$

${f(3)=5}.$

2. Podelite ${x^4-2x^3+4x-5}$ sa ${x-1}.$

Nema člana sa $x^2,$ pa je prvi red $1;$ $-2;$ $0;$ $4;$ $-5.$

$\begin{array}{r|rrrr|r} & 1 & -2 & 0 & 4 & -5 \\ 1 & & 1 & -1 & -1 & 3 \\ \hline & 1 & -1 & -1 & 3 & -2\end{array}$

Količnik je ${x^3-x^2-x+3},$ a ostatak je $-2.$

3. Odredite ostatak pri deljenju polinoma ${f(x)=x^5-3x^2+2}$ sa ${x+1}.$

Ovde je ${x_0=-1},$ a prvi red je $1;$ $0;$ $0;$ $-3;$ $0;$ $2.$

$\begin{array}{r|rrrrr|r} & 1 & 0 & 0 & -3 & 0 & 2 \\ -1 & & -1 & 1 & -1 & 4 & -4 \\ \hline & 1 & -1 & 1 & -4 & 4 & -2\end{array}$

Ostatak je $-2.$ Provera: ${f(-1)}={-1-3+2}={-2}.$

4. Pokažite da je $-2$ nula polinoma ${3x^3+7x^2-4}$ i rastavite polinom na činioce.

Nema člana sa $x,$ pa je prvi red $3;$ $7;$ $0;$ $-4.$

$\begin{array}{r|rrr|r} & 3 & 7 & 0 & -4 \\ -2 & & -6 & -2 & 4 \\ \hline & 3 & 1 & -2 & 0\end{array}$

Ostatak je $0,$ pa je $-2$ nula polinoma i ${3x^3+7x^2-4}={(x+2)(3x^2+x-2)}.$ Nule polinoma ${3x^2+x-2}$ su $-1$ i $\frac23,$ pa je ${3x^3+7x^2-4}={(x+2)(x+1)(3x-2)}.$

5. Podelite ${4x^3-3x+5}$ sa ${2x+1}.$

Ovde je ${x_0=-\frac12},$ a prvi red je $4;$ $0;$ $-3;$ $5.$

$\def\arraystretch{2.3}\begin{array}{r|rrr|r} & 4 & 0 & -3 & 5 \\ -\dfrac12 & & -2 & 1 & 1 \\ \hline & 4 & -2 & -2 & 6\end{array}$

Deljenje sa ${x+\frac12}$ daje količnik ${4x^2-2x-2}$ i ostatak $6.$ Kada koeficijente količnika podelimo sa $2,$ dobijamo ${4x^3-3x+5}={(2x+1)(2x^2-x-1)}+6.$