11 - wielomiany

1

Wielomiany

1.1

Postac potegowa (naturalna) wielomianu

Wielomian moze byc zapisany w bazie: f1; x; x2 ; : : : ; xn g.

X w(x) = a x n

k

(1)

k

k=0

Algorytm:

s = a0 ; xp = 1; for i = 1 to n begin xp = xp  x; s = s + ai  xp end

(2)

Liczba dzialan  2n() + n(+). 1.2

Algorytm Hornera

Aby policzyc wartosc wielomianu mozna zastosowac szybszy algorytm. Korzystamy z postaci:

w(x) = (:::(an x + an 1 )x + ::: + a1 )x + a0

(3)

Algorytm:

wn = an wi (x) = wi+1 (x)x + ai dla i = n 1; n 2; : : : ; 0 w(x) = w0 (x)

(4)

Liczba dzialan  n() + n(+). Twierdzenie: Algorytm Hornera jest jedynym algorytmem, ktory minimalizuje liczbe dodawan i mnozen przy obliczaniu wartosci wielomianu danego w postaci potegowej. 1.3

Dzielenie wielomianu

w(x) przez (x )

Algorytm Hornera moze byc wykorzystany w celu podzielenia wielomianu w(x) przez (x

Xa x n

k

k=0

Xb

n k

=(

1

k+1

xk )(x ) + b0 ;

). Jezeli: (5)

k=0

P

gdzie ( nk=01 bk+1 xk ) - wynik dzielenia, b0 - reszta z dzielenia. To:

an = bn ak = bk bk+1  dla k = n 1; n 2; : : : ; 0 Porownujac z algorytmem Hornera (ai = wi (x)

wi+1 (x)) bi = wi ().

1

(6)

1.4

Postac Newtona wielomianu

Wielomian moze byc rowniez zapisany w bazie: f1; x gdzie x0 ; x1 ; : : : ; xn sa danymi liczbami.

w(x) = b0

X b (x + n

x0 ; (x

x0 )(x

x1 ); : : : ; (x

x0 )


(x

xn )g,

x0 )


(x xi )

i

(7)

i=1

Algorytm:

s = b0 ; xp = 1; for i = 1 to n begin xp = xp  (x xi 1 ); s = s + bi  xp end

(8)

Liczba dzialan  2n() + 2n(+). 1.5

Uogolniony algorytm Hornera

Ponownie mozna zastosowac szybsza metode. Korzystamy z postaci:

w(x) = (:::(bn (x xn 1 ) + bn 1 )(x xn 2 ) + ::: + b1)(x x0 ) + b0

(9)

Algorytm:

wn = bn wi (x) = wi+1 (x xi )x + bi dla i = n 1; n 2; : : : ; 0 w(x) = w0 (x)

(10)

Liczba dzialan  n() + 2n(+). 1.6

Przejscie od postaci Newtona do postaci potegowej

Znajac wspolczynniki wielomianu w postaci Newtona mozna wyznaczyc wspolczynniki jego postaci naturalnej. W tym celu kazdy z wielomianow pomocniczych zde niowanych wzorami 11 zapiszmy w postaci naturalnej:

wi (x) =

Xa n

x

(i) k k

i

; i = n; n 1; : : : 0

(11)

k=i

Ze wzoru 11 otrzymujemy zaleznosci: oraz

wi (x) =

Xa n

x

(i+1) k k

k=i+1

a(ni+1) xn i +

(i+1)

(x

X (a

n

1

a(nn) = bn xi ) + bi =

Xa n

k

x

(i+1) k k

k=i+1

(i+1)

(12)

Xa n

i

(i+1) k

xk

(i+1)

xi + bi =

k=i+1

+1) i+1) a(ki+1 xi )xk i + (bi a(i+1 xi ):

(13)

k=i+1

Stad wspolczynniki postaci potegowej kolejnych wielomianow wi (i = n; n 1; : : : ; 0) mozna wyznaczyc rekurencyjnie:

a(ni) = a(ni+1) = : : : = a(nn) = bn i+1) a(ii) = bi a(i+1 xi +1) a(ki) = a(ki+1) a(ki+1 xi ; dla k = i + 1; i + 2; : : : ; n 1 2

(14)

Pamietajac, ze w(x) = w0 (x) wiemy, ze szukane wspolczynniki ak sa rowne a(0) (k = 0; 1; : : : ; n). k Daje to nastepujacy algorytm na przejscie od postaci Newtona do postaci potegowej:

a[n] = b[n]; for i = n 1 downto 0 do begin xi = x[i]; a[i] = b[i]; for k = i to n 1 do a[k] = a[k] xi  a[k + 1]; end 1.7

(15)

Tablice

Deklaracja: int a[10]; de niuje zawsze tablice a[0..9]. Nie istnieje w C metoda zapisania wprost wektora o dowolnie zaczynajacym sie wskazniku (np. a[5..14]). W wielu przypadkach przydaja sie jednak tablice a[1..10]. Mozna je latwo zapisac przy pomocy wskaznikow: int a[10],*ap; ap=a-1; Wskaznik ap wskazuje na pozycje przed a dzieki czemu stworzylismy tablice ap[1..10]. Mozna nastepnie wykonywac na niej dzialania.

3