Wydział FTIMS – Instytut Matematyki Politechniki Łódzkiej
Wst p do metod numerycznych – wykłady – matematyka
1
Posta Newtona wielomianu.
Niech
N
n
∈ ,
1
1
0
,
...
,
,
−
n
x
x
x
b d ustalonymi liczbami rzeczywistymi oraz k
∈P(n)∪{0}. Definiujemy
funkcje
R
R
p
k
→
:
nast puj co:
R
x
∈
∀
−
⋅
⋅
−
−
=
∈
∀
=
−
)
(
...
)
)(
(
)
(
)
(
1
)
(
1
1
0
0
k
k
x
x
x
x
x
x
x
p
n
P
k
x
p
.
Łatwo wykazujemy, e wielomiany
k
p zdefiniowane powy ej, tworz baz w przestrzeni liniowej
wielomianów stopnia co najwy ej n, czyli w przestrzeni R
n
[x]. Rozwa my dowolny wielomian stopnia n
zmiennej rzeczywistej x, zapisany w postaci naturalnej
=
⋅
=
∈
∀
n
k
k
k
x
a
x
w
R
x
0
)
(
. Oczywistym jest, e
].
[x
R
w
n
∈
Zatem istnieje dokładnie jeden ci g {b
k
}
k n
taki, e
=
⋅
=
∈
∀
n
k
k
k
x
p
b
x
w
R
x
0
).
(
)
(
Otrzymane
przedstawienie nazywane jest
postaci Newtona wielomianu w. Wielomian ten mo na zapisa w innej
postaci, wygodniejszej do oblicze numerycznych jego warto ci w punkcie x
∈R.
.
)
(
}
...
)
](
)
(
......[
{
)
(
0
0
1
2
1
1
b
x
x
b
x
x
b
x
x
b
x
w
n
n
n
n
+
−
⋅
+
+
−
+
−
=
−
−
−
Zdefiniujmy rekurencyjnie wielomiany:
(*)
.
0
...,
,
2
,
1
dla
)
(
1
−
−
=
+
−
⋅
=
=
+
n
n
i
b
x
x
w
w
b
w
i
i
i
i
n
n
Wówczas
.
)
(
0
w
x
w
=
Z zale no ci (*) wynika tzw.
Uogólniony algorytm Hornera obliczania warto ci
wielomianu zapisanego w postaci Newtona. Algorytm ten mo emy zapisa w postaci:
].
[
])
[
(
:
0
do
1
od
]
[
:
i
b
i
x
x
w
w
n
i
n
b
w
+
−
∗
=
−
=
=
Mo na pokaza , e algorytm ten jest numerycznie poprawny.
Wyznaczanie współczynników wielomianu w ró nych postaciach.
Znaj c współczynniki
k
b wielomianu w postaci Newtona, mo na wyznaczy współczynniki
k
a dla jego
postaci naturalnej. W tym celu ka dy z wielomianów
i
w postaci (*), zapiszemy w postaci naturalnej.
.
0
...,
,
1
,
dla
−
=
⋅
=
=
−
n
n
i
x
a
w
n
i
k
i
k
i
i
k
St d i z (*) otrzymujemy zale no ci:
n
n
n
b
a
=
+
=
+
=
+
=
⋅
−
+
⋅
⋅
−
+
⋅
=
+
⋅
⋅
−
⋅
=
+
+
−
−
+
+
+
−
+
−
−
+
−
+
n
i
i
i
i
n
i
k
i
i
k
i
k
i
n
i
n
n
i
i
i
k
i
k
i
k
i
k
i
i
k
i
k
i
k
x
a
b
x
x
a
a
x
a
b
x
x
a
x
a
w
1
1
).
(
)
(
1
1
1
1
1
1
1
1
1
1
1
Wstawiaj c te zale no ci do postaci wielomianów w
i
, a nast pnie porównuj c współczynniki przy tych
samych pot gach zmiennej x otrzymamy, e
,
n
n
n
b
a
=
,
1
1
i
i
i
i
i
i
x
a
b
a
⋅
−
=
+
+
.
1
...,
,
2
,
1
dla
1
1
1
−
+
+
=
⋅
−
=
+
+
+
n
i
i
k
x
a
a
a
i
i
k
i
k
i
k
Z tych zale no ci mo emy wywnioskowa , e szukane warto ci współczynników a
k
wielomianu w s
równe
0
k
a
dla k = 0, 1, …, n ( bo w(x)=w
0
(x) ).
Algorytm przej cia od postaci Newtona do postaci naturalnej ma posta :
a[n]=b[n],
dla i=n-1 do 0 wykonuj
Wydział FTIMS – Instytut Matematyki Politechniki Łódzkiej
Wst p do metod numerycznych – wykłady – matematyka
2
xi = x[i]
a[i] = b[i]
dla k=i do n-1 wykonuj
a[k] = a[k]−xi a[k+1].
Koszt tego algorytmu, to
2
)
1
(
+
n
n
mno e i tyle samo odejmowa . Mo na pokaza , e algorytm ten jest
numerycznie stabilny.
Uwagi o innych przedstawieniach wielomianów.
W obliczeniach numerycznych u ywa si równie przedstawienia wielomianów w postaci kombinacji
liniowej tzw.
wielomianów ortogonalnych. Przykładem takich wielomianów s wielomiany Czebyszewa
oznaczane symbolem T
n
. Wielomiany te s okre lone nast puj cymi zale no ciami:
(*)
R
x
∈
∀
.....
,
3
,
2
dla
)
(
)
(
2
)
(
)
(
1
)
(
2
1
1
0
=
−
⋅
=
=
=
−
−
k
x
T
x
T
x
x
T
x
x
T
x
T
k
k
k
Wielomiany te tworz baz w przestrzeni wszystkich wielomianów zmiennej rzeczywistej R[x]. Równie
dla dowolnego n
∈N, układ T
0
, T
1
, …, T
n
tworzy baz w przestrzeni R
n
[x]. Zatem dowolny wielomian
rzeczywisty stopnia n mo na zapisa jako kombinacj liniow wielomianów Czebyszewa. Oczywi cie
współczynniki tej kombinacji s wyznaczone w sposób jednoznaczny:
=
⋅
=
∈
∀
n
k
k
k
x
T
c
x
w
R
x
0
).
(
)
(
Zaproponowany przez Clenshawa algorytm obliczania warto ci wielomianu w, w punkcie x, polega na
wykorzystaniu zale no ci (*). Po rozpisaniu otrzymamy, e
,
~
~
)
(
2
0
1
c
c
x
c
x
w
−
+
⋅
=
gdzie
.
1
,
...
,
1
,
dla
~
~
2
~
2
1
−
=
−
+
=
+
+
n
n
k
c
c
c
x
c
k
k
k
k
oraz
.
0
~
~
1
2
=
=
+
+
n
n
c
c
Algorytm ten ma posta :
wykonaj
do
n
k
dla
x
dwax
c
c
1
2
0
2
1
=
∗
=
=
=
0
1
1
2
],
[
2
1
0
c
c
c
c
k
c
c
c
dwax
c
=
=
+
−
∗
=
.
2
]
0
[
1
c
c
c
x
w
−
+
∗
=
Mo na post puj c podobnie obliczy współczynniki postaci normalnej wielomianu w. (notatki str. 10e-f)
Obliczanie warto ci wielomianu zmiennej zespolonej.
Rozwa my wielomian stopnia n
∈N
0
zmiennej zespolonej
iy
x
z
+
=
, o współczynnikach zespolonych
k
k
ib
a
+
, k=0, 1, …, n. Wielomian ten ma posta
k
n
k
k
iy
x
ib
a
z
F
k
)
(
)
(
)
(
0
+
⋅
+
=
=
i jest w sposób
jednoznaczny okre lony przy pomocy dwóch ci gów współczynników
n
a
a
a
,
...
,
,
1
0
oraz
n
b
b
b
,
...
,
,
1
0
.
Wprowad my oznaczenia: u = Re F(z), v = Im F(z). Zapiszmy wielomian F(z) w postaci:
.
)
(
}
...
)
(
]
)
(
)
...[(
{
)
(
0
0
1
1
1
1
b
i
a
y
i
x
b
i
a
y
i
x
b
i
a
y
i
x
b
i
a
v
i
u
z
F
n
n
n
n
⋅
+
+
⋅
+
⋅
⋅
+
+
⋅
+
⋅
⋅
+
+
⋅
+
⋅
⋅
+
=
⋅
+
=
−
−
Wydział FTIMS – Instytut Matematyki Politechniki Łódzkiej
Wst p do metod numerycznych – wykłady – matematyka
3
Niech
.
0
,
...
,
2
,
1
dla
:
,
:
1
−
−
=
⋅
+
⋅
+
=
⋅
+
=
⋅
+
=
⋅
+
=
+
n
n
k
f
z
b
i
a
v
i
u
f
b
i
a
v
i
u
f
k
k
k
k
k
k
n
n
n
n
n
Wówczas
.
)
(
0
0
0
v
i
u
f
z
F
⋅
+
=
=
Zauwa my, e
,
,
n
n
n
n
b
v
a
u
=
=
oraz dla
0
,
1
...,
,
2
,
1
−
−
=
n
n
k
mamy, e
=
⋅
+
⋅
⋅
+
+
⋅
+
=
⋅
+
+
+
)
(
)
(
1
1
k
k
k
k
k
k
v
i
u
y
i
x
b
i
a
v
i
u
).
(
1
1
1
1
+
+
+
+
⋅
+
⋅
+
⋅
+
⋅
−
⋅
+
k
k
k
k
k
k
v
x
u
y
b
i
v
y
u
x
a
Rozpisuj c cz
rzeczywist oraz cz
urojon otrzymamy, e
,
,
)
(
,
,
1
1
1
1
+
+
+
+
⋅
+
⋅
+
=
⋅
−
⋅
+
=
∈
∀
=
=
k
k
k
k
k
k
k
k
n
n
n
n
u
y
v
x
b
v
v
y
u
x
a
u
n
P
k
b
v
a
u
.
)
(
,
,
0
0
0
0
v
u
iv
u
z
F
v
v
u
u
+
=
+
=
=
=
Schemat blokowy notatki str. 11.
Algorytm oblicze :
Dane: n – całkowite; a[k], b[k] – wektory; x, y – rzeczywiste;
i:=n
u:=a[n]
v:=b[n]
je li i>0 wykonuj
re:=x
⋅u−y⋅v
im:=x
⋅v+y⋅u
u:=re+a[i
−1]
v:=im+b[i
−1]
i:=i
−1
drukuj F(x+iy)=u+iv.