Algorytm Goertzela
Wyznaczyć wartość wielomianu trygonometrycznego danego wzorem
t
7
(x) = 1 + cos x −
1
2
sin x −
1
2
cos 2x +
3
2
sin 2x + sin 3x − 3 cos 4x
w punkcie λ =
π
3
Pierwszym krokiem jest rozdzielenie danego wielomiany na dwa wielomiany trygo-
nometryczne, z których jeden zawiera same cosinusy i wyraz wolny, a drugi zawiera
tylko sinusy. Mamy zatem
p
1
(x) = 1 + cos x −
1
2
cos 2x − 3 cos 4x
p
2
(x) =
1
2
sin x +
3
2
sin 2x + sin 3x
Każdemu z wielomianów p
1
i p
2
odpowiadają odpowiednio wielomiany zespolone w
1
i w
2
, których współczynniki są tworzone w myśl reguły
a cos bx → az
b
a sin bx → az
b
Mamy więc
w
1
(z) = 1 + z −
1
2
z
2
− 3z
4
w
2
(z) =
1
2
z +
3
2
z
2
+ z
3
Teraz należy obliczyć wartości wielomianów w
1
i w
2
w punkcie z
0
= cos λ + i sin λ, a
więc w naszym przykładzie z
0
= cos
π
3
+ i sin
π
3
.
Do wyznaczenia wartości wielomianów w
1
i w
2
w punkcie z
0
pozsłużymy się algoryt-
mem Goertzela.
W ogólnym przypadku mając dany wielomian w(z) zmiennej zespolonej
w(z) = d
0
+ d
1
z + . . . + d
n
z
n
aby obliczyć jego wartość w punkcie z
0
= cos ξ + i sin ξ konstruujemy ciąg
e
n+1
= e
n+2
= 0
e
k
= d
k
+ 2c · e
k+1
− e
k+2
,
k = n, n − 1, . . . , 1
e
0
= d
0
− e
2
gdzie c = cos ξ. Wówczas wartość wielomianu w(z) w punkcie z
0
wynosi
w(ξ) = e
1
· z
0
+ e
0
przy czym
Re w(z
0
) = e
1
· c + e
0
Im w(z
0
) = e
1
sin ξ
Do wyznaczenia wartości wielomianu t
7
(x) w punkcie
π
3
musimy wyznaczyć Re w
1
(z
0
)
oraz Im w
2
(z
0
) ponieważ ostateczną wartość otrzymamy z zależności
t
7
π
3
= Re w
1
(z
0
) + Im w
2
(z
0
)
Wyznaczymy najpierw Re w
1
(z
0
), dla z
0
= cos
π
3
+ i sin
π
3
. Mamy c = cos
π
3
=
1
2
.
Ponadto n = 4 oraz
d
0
= 1
d
1
= 1
d
2
= −
1
2
d
3
= 0
d
4
= −3
Ponadto e
5
= e
6
= 0 oraz
e
4
= d
4
+ 2c · e
5
− e
6
= −3
e
3
= d
3
+ 2c · e
4
− e
5
− 3
e
2
= d
2
+ 2c · e
3
− e
4
= −
1
2
e
1
= d
1
+ 2c · e
2
− e
3
=
7
2
e
0
= d
0
− e
2
=
3
2
A więc otrzymujemy, że
Re w
1
(z
0
) = e
1
· c + e
0
=
7
2
·
1
2
+
3
2
=
13
4
Teraz należy wyznaczyć Im w
2
(z
0
), dla z
0
= cos
π
3
+ i sin
π
3
. W dalszym ciągu c =
1
2
.
Ponadto n = 3 oraz
d
0
= 0
d
1
= −
1
2
d
2
=
3
2
d
3
= 1
Mamy więc e
4
= e
5
= 0 oraz
e
3
= d
3
+ 2c · e
4
− e
5
= 1
e
2
= d
2
+ 2c · e
3
− e
4
=
5
2
e
1
= d
1
+ 2c · e
2
− e
3
= 1
e
0
= d
0
− e
2
= −
5
2
Ostatecznie dostajemy, że
Im w
2
(z
0
) = e
1
· sin
π
3
=
√
3
2
Zatem szukana wartość wielomianu t
7
(x) w punkcie λ =
π
3
wynosi
t
7
π
3
= Re w
1
(z
0
) + Im w
2
(z
0
) =
13
4
+
√
3
2