1

Wielomian

y

1.1

P

ostac

p

otego

w

a

(naturalna)

wielomian

u

Wielomian

moze

b

yc

zapisan

y

w

bazie:

f1;

x;

x

2

;

:

:

:

;

x

n

g.

w

(x)

=

n

X

k =0

a

k

x

k

(1)

Algorytm:

s

=

a

0

;

xp

=

1;

f

or

i

=

1

to

n

beg

in

(2)

xp

=

xp



x;

s

=

s

+

a

i



xp

end

Liczba

dzialan



2n()

+

n(+).

1.2

Algorytm

Hornera

Ab

y

p

oliczyc

w

artosc

wielomian

u

mozna

zastoso

w

ac

szybszy

algorytm.

Korzystam

y

z

p

ostaci:

w

(x)

=

(:::(a

n

x

+

a

n

1

)x

+

:::

+

a

1

)x

+

a

0

(3)

Algorytm:

w

n

=

a

n

w

i

(x)

=

w

i+1

(x)x

+

a

i

dl

a

i

=

n

1;

n

2;

:

:

:

;

0

(4)

w

(x)

=

w

0

(x)

Liczba

dzialan



n()

+

n(+).

Twierdzenie:

Algorytm

Hornera

jest

jedyn

ym

algorytmem,

ktory

minimalizuje

liczb

e

do

da

w

an

i

mnozen

przy

obliczaniu

w

artosci

wielomian

u

danego

w

p

ostaci

p

otego

w

ej.

1.3

Dzielenie

wielomian

u

w

(x)

przez

(x

 )

Algorytm

Hornera

moze

b

yc

wyk

orzystan

y

w

celu

p

o

dzielenia

wielomian

u

w

(x)

przez

(x

).

Jezeli:

n

X

k =0

a

k

x

k

=

(

n

1

X

k =0

b

k +1

x

k

)(x

)

+

b

0

;

(5)

gdzie

(

P

n

1

k =0

b

k +1

x

k

)

-

wynik

dzielenia,

b

0

-

reszta

z

dzielenia.

T

o:

a

n

=

b

n

a

k

=

b

k

b

k +1



dl

a

k

=

n

1;

n

2;

:

:

:

;

0

(6)

P

oro

wn

ujac

z

algorytmem

Hornera

(a

i

=

w

i

(x)

w

i+1

(x))

b

i

=

w

i

().

1

1.4

P

ostac

Newtona

wielomian

u

Wielomian

moze

b

yc

ro

wniez

zapisan

y

w

bazie:

f1;

x

x

0

;

(x

x

0

)(x

x

1

);

:

:

:

;

(x

x

0

)

(x

x

n

)g,

gdzie

x

0

;

x

1

;

:

:

:

;

x

n

sa

dan

ymi

liczbami.

w

(x)

=

b

0

+

n

X

i=1

b

i

(x

x

0

)

(x

x

i

)

(7)

Algorytm:

s

=

b

0

;

xp

=

1;

f

or

i

=

1

to

n

beg

in

(8)

xp

=

xp



(x

x

i

1

);

s

=

s

+

b

i



xp

end

Liczba

dzialan



2n()

+

2n(+).

1.5

Uogolnion

y

algorytm

Hornera

P

ono

wnie

mozna

zastoso

w

ac

szybsza

meto

de.

Korzystam

y

z

p

ostaci:

w

(x)

=

(:::(b

n

(x

x

n

1

)

+

b

n

1

)(x

x

n

2

)

+

:::

+

b

1

)(x

x

0

)

+

b

0

(9)

Algorytm:

w

n

=

b

n

w

i

(x)

=

w

i+1

(x

x

i

)x

+

b

i

dl

a

i

=

n

1;

n

2;

:

:

:

;

0

(10)

w

(x)

=

w

0

(x)

Liczba

dzialan



n()

+

2n(+).

1.6

Przejscie

o

d

p

ostaci

Newtona

do

p

ostaci

p

otego

w

ej

Zna

jac

wsp

olczynniki

wielomian

u

w

p

ostaci

Newtona

mozna

wyznaczyc

wsp

olczynniki

jego

p

ostaci

nat-

uralnej.

W

t

ym

celu

k

azdy

z

wielomiano

w

p

omo

cniczyc

h

zdenio

w

an

yc

h

wzorami

11

zapiszm

y

w

p

ostaci

naturalnej:

w

i

(x)

=

n

X

k =i

a

(i)

k

x

k

i

;

i

=

n;

n

1;

:

:

:

0

(11)

Ze

wzoru

11

otrzym

ujem

y

zaleznosci:

a

(n)

n

=

b

n

(12)

oraz

w

i

(x)

=

n

X

k =i+1

a

(i+1)

k

x

k

(i+1)

(x

x

i

)

+

b

i

=

n

X

k =i+1

a

(i+1)

k

x

k

i

n

X

k =i+1

a

(i+1)

k

x

k

(i+1)

x

i

+

b

i

=

a

(i+1)

n

x

n

i

+

n

1

X

k =i+1

(a

(i+1)

k

a

(i+1)

k +1

x

i

)x

k

i

+

(b

i

a

(i+1)

i+1

x

i

):

(13)

Stad

wsp

olczynniki

p

ostaci

p

otego

w

ej

k

olejn

yc

h

wielomiano

w

w

i

(i

=

n;

n

1;

:

:

:

;

0)

mozna

wyznaczyc

rekurencyjnie:

a

(i)

n

=

a

(i+1)

n

=

:

:

:

=

a

(n)

n

=

b

n

a

(i)

i

=

b

i

a

(i+1)

i+1

x

i

(14)

a

(i)

k

=

a

(i+1)

k

a

(i+1)

k +1

x

i

;

dl

a

k

=

i

+

1;

i

+

2;

:

:

:

;

n

1

2

P

amieta

jac,

ze

w

(x)

=

w

0

(x)

wiem

y

,

ze

szuk

ane

wsp

olczynniki

a

k

sa

ro

wne

a

(0)

k

(k

=

0;

1;

:

:

:

;

n).

Da

je

to

nastepujacy

algorytm

na

przejscie

o

d

p

ostaci

Newtona

do

p

ostaci

p

otego

w

ej:

a[n]

=

b[n];

f

or

i

=

n

1

dow

nto

0

do

beg

in

xi

=

x[i];

(15)

a[i]

=

b[i];

f

or

k

=

i

to

n

1

do

a[k

]

=

a[k

]

xi



a[k

+

1];

end

1.7

T

ablice

Deklaracja:

in

t

a[10];

deniuje

za

wsze

tablice

a[0..9].

Nie

istnieje

w

C

meto

da

zapisania

wprost

w

ektora

o

do

w

olnie

zaczyna-

jacym

sie

wsk

azniku

(np.

a[5..14]).

W

wielu

przypadk

ac

h

przyda

ja

sie

jednak

tablice

a[1..10].

Mozna

je

lat

w

o

zapisac

przy

p

omo

cy

wsk

aznik

o

w:

in

t

a[10],*ap;

ap=a-1;

Wsk

aznik

ap

wsk

azuje

na

p

ozycje

przed

a

dzieki

czem

u

st

w

orzylism

y

tablice

ap[1..10].

Mozna

nastepnie

wyk

on

yw

ac

na

niej

dzialania.

3