Previous Up Next

1.22.2  Διακριτός Μετασχηματισμός Fourier

Έστω N ένας ακέραιος. Ο Διακριτός Μετασχηματισμός Fourier (DFT) είναι ένας μετασχηματισμός FN που ορίζεται στο σύνολο των περιοδικών ακολουθιών περιόδου N. Εξαρτάται απ’ την επιλογή μιας αρχικής N-οστής ρίζας της μονάδας ωN. Εάν ο DFT ορίζεται σε ακολουθίες με μιγαδικούς συντελεστές, έχουμε:

ωN=e
i π
N
 

Εάν x είναι μια περιοδική ακολουθία περιόδου N, που ορίζεται από το διάνυσμα x=[x0,x1,...xN−1] τότε ο FN(x)=y είναι μια περιοδική ακολουθία περιόδου N, που ορίζεται από:

(FNN(x))k=yk=
N−1
j=0
xjωNk· jk=0..N−1 

όπου ωN είναι μια αρχική N-οστή ρίζα της μονάδας. Mε τον Γρήγορο Μετασχηματισμό Fourier (FFT) o διακριτός Μετασχηματισμός Fourier μπορεί να υπολογιστεί γρηγορότερα από τον υπολογισμό του καθενός yk ατομικά. Το Xcas υλοποιεί τον αλγόριθμο FFT για να υπολογίσει τον διακριτό μετασχηματισμό Fourier μόνο εάν το N είναι δύναμη του 2.

Ιδιότητες του διακριτού μετασχηματισμού Fourier

Ο Διακριτός Μετασχηματισμός Fourier FN είναι ένας αμφιμονοσήμαντος και επί μετασχηματισμός σε περιοδικές ακολουθίες τέτοιες ώστε :

 FNN−1=
1
N
 FNN−1 
 =
1
N
 
FN
     στο  ℂ

δηλαδή :

(FN−1(x))k=
1
N
N−1
j=0
xjωNk· j 

Στο Xcas ο Διακριτός Μετασχηματισμός Fourier και ο αντίστροφός του δηλώνονται με fft και ifft:

fft(x)= FN(x), ifft(x)= FN−1(x)

Ορισμοί
Έστω x και y δύο περιοδικές ακολουθίες με περίοδο N.

Ιδιότητες :

N*FN(x · y)=FN(x) * FN(y)
FN(x * y)=FN(x) · FN(y)

Εφαρμογές

  1. Τιμή ενός πολυωνύμου
    Ορίζουμε ένα πολυώνυμο P(x)=∑j=0N−1cjxj με το διάνυσμα των συντελεστών του c:=[c0,c1,..cN−1], όπου μηδενικά μπορούν να προστεθούν έτσι ώστε το N να είναι δύναμη του 2.
  2. Τριγωνομετρική παρεμβολή
    Έστω f μια περιοδική συνάρτηση περιόδου 2π, και έστω ότι f(2kπ/N)=fk for k=0..(N−1). Βρείτε ένα τριγωνομετρικό πολυώνυμο p που παρεμβάλει την f στα xk=2kπ/N, δηλαδή βρείτε pj, j=0..N−1 τέτοια ώστε
    p(x)= 
    N−1
    j=0
     pj exp(ijx),    p(xk)=fk
    Αντικαθιστώντας στο p(x) το xk με την τιμή του έχουμε:
    N−1
    j=0
     pj exp(i
    j2kπ
    N
    ) = fk
    Μ’ άλλα λόγια, (fk) είναι ο αντίστροφος μετασχηματισμός Fourier DFT του (pk), και επομένως
    (pk)= 
    1
    N
     FN(  (fk)  ) 
    Εάν η συνάστηση f είναι πραγματική, pk=pk, και επομένως ανάλογα αν το N είναι άρτιο ή περιττό:
    p(x)=
    p0+ 2 ℜ(
    N
    2
    −1
    k=0
    pkexp(ikx))+ℜ(p
     
    N
    2
     exp(i
    Nx
    2
    )) 
    p(x)=
    p0+ 2 ℜ(
    N−1
    2
    k=0
    pkexp(ikx))
  3. Σειρές Fourier
    Έστω f μια περιοδική συνάρτηση περιόδου 2π, τέτοια ώστε :
    f(xk)=yk,    xk=
    2kπ
    N
    k=0..N−1 
    Έστω επίσης ότι η σειρά Fourier της f συγκλίνει στην f (αυτό θα ισχύει εάν για παράδειγμα f είναι συνεχής). Εάν το N είναι μεγάλο, μια καλή προσέγγιση της f θα δίνεται από:
     
    N
    2
     ≤ n<
    N
    2
     cn exp(inx
    Επομένως θέλουμε μια αριθμητική προσέγγιση των
    cn=
    1
     


    0
    f(t)exp(−int)dt 
    Η αριθμητική τιμή του ολοκληρώματος ∫0f(t)exp(−int)dt μπορεί να υπολογιστεί από τον τραπεζοειδή κανόνα (σημειώνουμε ότι ο αλγόριθμος Romberg δεν θα δούλευε εδώ, επειδή το ανάπτυγμα Euler Mac Laurin έχει μηδενικούς συντελεστές, αφού η ολοκληρωτέα συνάρτηση είναι περιοδική, και επομένως όλες της οι παράγωγοι έχουν την ίδια τιμή στο 0 και στο 2π). Εάν c_n είναι η αριθμητική τιμή της cn που παίρνουμε από τον τραπεζοειδή κανόνα, τότε
    c_n=
    1
    N
    N−1
    k=0
    ykexp(−2i
    nkπ
    N
    ),     −
    N
    2
     ≤ n<
    N
    2
     
    Πράγματι, αφού xk=2kπ/N και f(xk)=yk:
    f(xk)exp(−inxk)=
    ykexp(−2i
    nkπ
    N
    ), 
    f(0)exp(0)=f(2π)exp(−2i
    nNπ
    N
    )
    =y0=yN 
    Επομένως :
    [c0,..c
     
    N
    2
    −1
    ,c
     
    N
    2
    ,..c−1]=
    1
    N
    FN([y0,y1...y(N−1)]) 
    <αφού

    Ιδιότητες

    Παράδειγμα, εισάγετε

    f(t):=cos(t)+cos(2*t)
    x:=f(2*k*pi/8)$(k=0..7)

    Έξοδος :

    x={2,(√2)/2,-1,-((√2)/2),0,-((√2)/2),-1,(√2)/2}
    fft(x)=[0.0,4.0,4.0,0.0,0.0,0.0,4.0,4.0]

    Μετά από διαίρεση με N=8, έχουμε :

    c0=0,c1=4.0/8,c2=4.0/2,c3=0.0,
    c−4=0,c−3=0,c−2=4.0/8,=c−1=4.0/8

    Επομένως, bk=0 και ak=ck+ck ισούται με 1 εάν k=1, 2 και 0 σε κάθε άλλη περίπτωση.

  4. Γινόμενο Συνέλιξης
    Εάν P(x)=∑j=0n−1ajxj και Q(x)=∑j=0m−1bjxj δίνονται από τα διανύσματα των συντελεστών τους a=[a0,a1,..an−1] and b=[b0,b1,..bm−1], υπολογίζουμε το γινόμενο αυτών των δύο πολυωνύμων χρησιμοποιώντας τον DFT. Το γινόμενο των δύο πολυωνύμων είναι το γινόμενο συνέλιξης της περιοδικής σειράς των συντελεστών τους εάν η περίοδος είναι μεγαλύτερη ή ίση από (n+m). Επομένως συμπληρώνουμε το a (αντίστοιχα το b) με m+p (αντίστοιχα n+p) μηδενικά, όπου p επιλέγεται τέτοιο ώστε το N=n+m+p να είναι δύναμη του 2. Εάν a=[a0,a1,..an−1,0..0] και b=[b0,b1,..bm−1,0..0], τότε:
    P(x)Q(x)=
    n+m−1
    j=0
    (a*b)jxj 
    Υπολογίζουμε τα FN(a), FN(b), και μετά ab=FN−1(FN(aFN(b)) χρησιμοποιώντας τις ιδιότητες
    NFN(x · y)=FN(x) * FN(y),    FN(x * y)=FN(x) · FN(y

Previous Up Next