Hornerova šema

Tipično, polinom se predstavlja oblikom:

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

ili

f(x) = a0 + a1x + a2x2 + ... + akxk

gde su ak realni brojevi koji predstavljaju koeficijente polinoma, a xk su promenljive polinoma.

Za prethodni polinom kažemo da je n-tog stepena, na primer deg(f(x)) = n, gde je n najveći stepen promenljive.

Hornerova šema za deljenje polinoma je metod za izračunavanje vrednosti polinoma f(x) za vrednost promenljive x = x0 razlaganjem polinoma na monome (polinome prvog stepena). Svaki monom uključuje najviše jedno množenje i jedno sabiranje. Rezultat dobijen iz jednog monoma se dodaje na rezultat dobijen iz sledećeg monoma, i tako redom akumulativnom metodom. Ovaj postupak se u Americi naziva još i sintetičko deljenje.

Kako bismo objasnili prethodno zapišimo polinom u drugačijoj formi;

f(x0) = a0 + a1x0 + a2x02 + ... + anx0n

Možemo ga zapisati ovako:

f(x0) = a0 + x0(a1 + x0(a2 + x0(a3 + ... + (an-1 + anx0)....)

Algoritam koji sledi iz ovog pravila zasniva se na izračunavanju monoma gore formiraninh počevši od onog u najdubljoj zagradi i krećući se izračunavanjem monoma u spoljnjim zagradama.

Metoda se primenjuje praćenjem sledećih koraka:

1. Neka je k = n
2. bk = ak
3. bk - 1 = ak - 1 + bkx0
4. k = k - 1
5. Ako je k ≥ 0 vratiti se na korak 3.
U suprotnom je kraj.

Ovaj metod se može i grafički predstaviti za polinom petog stepena datog sa:

f(x) = a0 + a1x + a2x2 + a3x3 + a4x4 + a5x5

koji može biti izračunat za x = x0 transformacijom polinoma u oblik:

f(x0) = a0 + x0(a1 + x0(a2 + x0(a3 + x0(a4 + a5x0))))

Drugi način predstavljanja rezultata korišćenjem ove metode je pomoću tablice date ispod:

K 5 4 3 2 1 0
b5 = a5 b4 = a4 + x0b5 b3 = a3 + x0b4 b2 = a2 + x0b3 b1 = a1 + x0b2 b0 = a0 + x0b1

Primer: Izračunaj vrednost polinoma f(x) = x4 + 3x3 + 5x2 + 7x + 9 za x = 2

Rešenje:

Pošto je polinom četvrtog stepena onda je n = 4

K 4 3 2 1 0
Korak b4 = 1 b3 = 3 + 2 * 1 b2 = 5 + 2 * 5 b1 = 7 + 2 * 15 b0 = 9 + 2 * 37
Rezultat 1 5 15 37 83

Pa je, f(2) = 83.

Zašto koristimo ovu metodu?

Uobičajeno, kada izračunavamo polinom za određenu vrednost promenljive, navikli smo zameniti vrednost ove promenljive u polinom i izračunati. Takođe možemo razviti i primeniti matematičku aplikaciju za izračunavanje kako bismo to uradili, što je neophodno kada radimo sa složenim polinomima velikog stepena.

Način na koji računar procesuira problem uglavnom zavisi od toga kako vi kao programer opišete proces računaru. Možete napraviti da vaša aplikacija rešava polinome direktnom zamenom ili koristeći sintetičko deljenje prema Hornerovom pravilu. Jedina razlika između ova dva pristupa je brzina kojom će računar rešiti problem u bilo kom od ova dva slučaja.

Prednost Hornerovog pravila je u tome što smanjuje broj operacija množenja. Znajući da je vreme potrebno računaru za izračunavanje samo jedne operacije množenja 5 do 20 puta duže od vremena potrebnog za sabiranje, jasno je da će aplikacija za izračunavanje polinoma pomoću Hornerovog pravila značajno smanjiti vreme potrebno računaru da izračuna polinom.

Kalkulator za deljenje polinoma


Kontakt imejl:

Copyright © 2005 - 2024