Obliczanie warto ci funkcji.

Zajmiemy si zagadnieniem obliczania warto ci funkcji elementarnych przy pomocy maszyny

cyfrowej. Jednym z elementów na które b dziemy zwraca uwag , jest ilo wykonywanych

operacji i dokładno oblicze .

Obliczanie warto ci wielomianu rzeczywistego.

Rozwa my wielomian n – tego stopnia ( n

∈N

0

) zmiennej rzeczywistej x zapisany w postaci:

=

⋅

=

∈

∀

n

k

k

k

x

a

x

w

R

x

0

)

(

.

Tak form zapisu wielomianu nazywamy jego postaci naturaln . Wielomian ten jest

reprezentowany w sposób jednoznaczny za pomoc sko czonego ci gu współczynników a

0

,

a

1

, …, a

n

. Obliczanie warto ci wielomianu w punkcie x

≠0, poprzez sumowanie warto ci

wyrazów a

0

, a

1

x, …, a

n

x

n

jest nieekonomiczne ze wzgl du na ilo koniecznych do

wykonania operacji arytmetycznych oraz ilo wykorzystywanej pami ci. Znacznie mniej

działa b dzie trzeba wykona , zapisuj c wielomian w postaci

.

}

...

]

)

{...[(

)

(

0

1

2

1

a

x

a

x

a

x

a

x

a

x

w

R

x

n

n

n

+

⋅

+

+

⋅

+

⋅

+

=

∈

∀

−

−

Wprowadzaj c oznaczenia

0

...,

,

2

,

1

dla

1

−

−

=

⋅

+

=

=

+

n

n

i

f

x

a

f

a

f

i

i

i

n

n

otrzymamy, e w(x)=f

n

. Zapisane zale no ci rekurencyjne, daj schemat liczenia warto ci

wielomianu z minimaln , konieczn do wykonania liczb działa arytmetycznych. Schemat

ten zwany jest

schematem Hornera.

0

1

1

1

2

0

1

1

.

..........

.......

...

......

f

f

f

f

f

x

f

x

f

x

a

a

a

a

n

n

n

n

n

−

−

⋅

⋅

⋅

+

,

.

)

(

0

f

x

w

=

Uwaga: Algorytm Hornera mo na przedstawi w postaci:

n

i

f

x

a

f

a

f

i

i

n

i

n

...,

,

2

,

1

dla

1

0

=

⋅

+

=

=

−

−

.

Wówczas

.

)

(

n

f

x

w

=

Algorytm oblicze do schematu Hornera:

Dane: n – całkowite; a[k] – wektor, macierz; x – rzeczywiste;

i=n

s=a[i]

je li i>0 wykonuj

s=s x

s=s+a[i-1]

i=i-1

drukuj w(x)=s;

Sprawdzimy, e algorytm Hornera jest numerycznie poprawny. Dla uproszczenia oblicze

załó my, e dane zadania s reprezentowane dokładnie. Realizuj c obliczenia w arytmetyce fl

otrzymamy warto ci

.

0

...,

,

2

,

1

dla

)

1

(

))

1

(

~

(

)

~

(

~

~

1

1

−

−

=

+

⋅

+

⋅

+

=

⋅

+

=

=

+

+

n

n

i

x

f

a

x

f

a

fl

f

a

f

i

i

i

i

i

i

i

n

n

δ

ε

,

przy czym

.

2

,

t

i

i

−

≤

δ

ε

St d wynika, e

=

+

⋅

⋅

=

=

n

k

k

k

k

e

x

a

f

0

),

1

(

....

~

0

gdzie

∏

−

=

=

+

⋅

+

⋅

+

=

+

1

0

.

0

),

1

(

)

1

(

)

1

(

1

k

n

i

i

k

k

i

e

δ

δ

ε

δ

Zatem

.

...,

,

1

,

0

dla

)

1

2

(

2

n

k

k

e

t

k

=

+

⋅

≤

−

Obliczona w arytmetyce fl warto wielomianu

0

~

w jest wi c dokładn warto ci wielomianu

o nieco zaburzonych współczynnikach

).

1

(

k

k

e

a

+

⋅

Zatem prawdziwe jest nast puj ce

Twierdzenie: Algorytm Hornera jest numerycznie poprawny ze współczynnikiem

kumulacji co najwy ej (2n+1).

Twierdzenie: Algorytm Hornera jest jedynym algorytmem, który minimalizuje liczb

dodawa i mno e przy obliczaniu warto ci wielomianu danego w postaci naturalnej.

Uwaga: Algorytm Hornera jest jednocze nie algorytmem dzielenia wielomianu w przez

dwumian (x−x

0

).

Niech

−

+

−

=

⋅

=

1

1

1

0

)

(

n

i

i

n

i

x

b

x

Q

b dzie wynikiem dzielenia wielomianu w(x) przez dwumian

(x−x

0

). Wówczas

.

)

(

)

(

)

(

0

0

1

1

0

0

b

x

x

x

b

x

a

x

w

n

i

i

n

i

i

n

i

i

+

−

⋅

⋅

=

⋅

=

−

+

=

=

Z porównania

współczynników przy tych samych pot gach zmiennej x otrzymamy, e

;

1

...,

,

1

,

0

dla

:

0

1

−

=

⋅

−

=

+

n

k

x

b

b

a

x

k

k

k

k

n

n

b

a

= .

St d wynika, e

n

n

b

a

= ,

.

1

...,

,

1

,

0

dla

0

1

−

=

⋅

+

=

+

n

k

x

b

a

b

k

k

k

Porównuj c otrzyman zale no z zale no ciami rekurencyjnymi schematu Hornera,
stwierdzamy, e

.

...,

,

1

,

0

dla

n

i

f

b

i

i

=

=

Zatem algorytm Hornera wyznacza nie tylko

warto wielomianu w punkcie

0

x (

0

0

)

(

f

x

w

=

), ale równie okre la warto ci

współczynników

n

b

b

b

,

...

,

,

2

1

wyniku dzielenia wielomianu w przez dwumian (x−x

0

).

Przykład. Obliczy warto wielomianu

3

3

2

)

(

2

3

4

+

−

+

−

=

x

x

x

x

x

w

dla x=1.

2

1

0

1

2

)

1

(

1

0

1

)

1

(

1

2

1

3

1

1

3

2

−

−

−

⋅

⋅

−

⋅

⋅

+

−

−

St d

.

2

)

1

(

=

w

Ponadto

.

2

)

1

)(

1

2

(

)

(

2

3

+

−

−

−

=

∈

∀

x

x

x

x

w

R

x

Zastosowanie algorytmu Hornera do obliczania unormowanych pochodnych

wielomianu.

Rozwa my wielomian n – tego stopnia ( n

∈N

0

) zmiennej rzeczywistej x zapisany w postaci

naturalnej:

=

⋅

=

∈

∀

n

k

k

k

x

a

x

w

R

x

0

)

(

.

Zauwa my, e posta ta jest jednocze nie rozwini ciem funkcji

)

(x

w

w szereg pot gowy

Maclaurina. Z jednoznaczno ci takiego rozwini cia wynika, e współczynniki

.

,

...

,

1

,

0

dla

!

)

0

(

)

(

n

j

j

w

a

j

j

=

=

Def. Funkcj okre lon wzorem

!

)

(

)

(

)

(

0

j

x

w

x

v

N

j

R

x

j

≡

∈

∀

∈

∀

, nazywamy

znormalizowan pochodn rz du j wielomianu w.

Uwaga: Pochodna znormalizowana rz du k>n wielomianu stopnia n, jest funkcj

to samo ciowo równ zeru.

Przyjmijmy oznaczenie P(n)={ 1, 2, … , n }. Niech x

0

jest ustalon liczb rzeczywist ,

j

∈P(n), za v(x) wynikiem dzielenia wielomianu w(x) przez ( x − x

0

)

j

. Wówczas istnieje

wielomian r(x) stopnia co najwy ej j −1 ( reszta z dzielenia ) taki, e

).

(

)

(

)

(

)

(

0

x

r

x

v

x

x

x

w

R

x

j

+

⋅

−

=

∈

∀

Zale no t ró niczkujemy j − razy wzgl dem zmiennej x. Otrzymamy, e

.

!

)

(

)

(

)

(

!

)

(

0

)

(

0

0

0

)

(

j

x

w

x

v

x

v

j

x

w

j

j

=

⋅

=

Z drugiej strony współczynniki wielomianu v oraz warto v( x

0

) mo emy obliczy dziel c

wielomian w i kolejno otrzymywane ilorazy

1

,

...

,

2

,

1

dla

)

(

)

(

0

−

=

−

j

k

x

x

x

w

k

, przez

)

(

0

x

x

−

algorytmem Hornera. W ten sposób proces ró niczkowania wielomianu sprowadza

si do ilu krotnego dzielenia tego wielomianu przez dwumian

)

(

0

x

x

−

.

Uwaga. Stosowanie algorytmu Hornera do obliczania warto ci m pocz tkowych (m n)

znormalizowanych pochodnych

n

j

j

x

w

j

,

...

,

1

,

0

dla

!

)

(

)

(

=

, wielomianu stopnia n, wymaga

wykonania (m+1) (n-m/2) dodawa i takiej samej ilo ci mno e , czyli

)

(

2

...

)

2

2

(

2

m

n

n

n

−

+

+

−

+

− działa ł cznie.

W zadaniach, w których nale y obliczy wszystkie pochodne, mo na zastosowa inny

algorytm nazywany algorytmem Shaw-Trauba. Algorytm ten zmniejsza ilo potrzebnych do

wykonania działa . W tym momencie wykładu nie b dziemy si zajmowa tym algorytmem.