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.