403 2

403

9.3. Szybka analiza Fouriera

Stąd zaś	cynika, że
		2nijfi
	w" =	"^p—
(9,3.6)		p-i
		n v=0

2w i

pokażemy teraz dla przykładu, jak można wykorzystać rozkład (9.3.6) na czynniki, gdy /?=*»& Przyjmijmy, zgodnie z rozkładem (9.3.4), że

a_/r=c⁽⁰⁾(A:₁,k₂,A:₃).

Mamy zatem

Cj= X    III c^l0)(k_t,k₂,kjH£*^Jw{^ł*V*\

ę=o    fc,=oij^oŁ,=o

Można więc obliczać kolejno (zob. (9.3.5)) wielkości

mc_%, k_2j oc₃)= X    »k₃)w^    (j₂ zależy tylko od cc₃),

fc., = 0

r-j- 1

c^ł2>(ki, Cf₂. a₃)= Z ^C<I)(*I * *2 • *₃)    Ol zależy tylko od a₂ . «₃)•

Ła-0

^,t_I

^=c⁽3,(oc,, a₂, ct₃) = Z ^c<2>(*i» X2. *3) łv^Jk|    0 zależy od a_t, a₃, a₃).

i,=0

Wielkości c^<0 oblicza się dla każdej z rir₂r₃=/f kombinacji wartości argumentów. Dlatego łączna liczba operacji pełnej analizy Fouriera wynosi (co najwyżej) Nr_s 1- Nr₂ -- Nr_t. Uogólnienie na dowolne p jest oczywiste.

U waga. Opisane wyżej algorytmy dla liczb całkowitych można wykorzystywać, w szczególnym przypadku rj=£dla każdego i, do wyrażania liczb całkowitych lub ułamkowych w układz;c pozycyjnym z nową podstawą B.

Pytanie przeglądowe

Opisać ogólnie szybką analizę Fouriera i jej zalety numeryczne (wybrać przypadek szczególny, w którymi liczba składników jest równa 2^k).

Zadania

Udowodnić dwa algorytmy obliczania x,_y k_t z §9.3.2.

^    • Poniższy podprogram w Fortranie służący do szybkiego przekształcenia Fouriera

k^ypadku, gdy N=2^Kif podali Cooley, Lewis i Welch w IEEE Transaaions £-12, Nr 1 rzec 1965). Zastosować ten podprogram do funkcji z przykładu 9.2.1. Przyjąć np. Q 64.