Σειρές Fourier
Έστω f μια περιοδική συνάρτηση περιόδου 2π, τέτοια ώστε :
Έστω επίσης ότι η σειρά Fourier της f συγκλίνει στην f (αυτό θα ισχύει εάν για παράδειγμα f είναι συνεχής). Εάν το N είναι μεγάλο,
μια καλή προσέγγιση της f θα δίνεται από:
Επομένως θέλουμε μια αριθμητική προσέγγιση των
Η αριθμητική τιμή του ολοκληρώματος ∫02πf(t)exp(−int)dt μπορεί να υπολογιστεί από τον τραπεζοειδή κανόνα (σημειώνουμε ότι ο αλγόριθμος Romberg δεν θα δούλευε εδώ, επειδή το ανάπτυγμα Euler Mac Laurin
έχει μηδενικούς συντελεστές, αφού η ολοκληρωτέα συνάρτηση είναι περιοδική, και επομένως όλες της οι παράγωγοι έχουν την ίδια τιμή στο 0 και στο 2π).
Εάν c_n είναι η αριθμητική τιμή της cn που παίρνουμε από
τον τραπεζοειδή κανόνα, τότε
Πράγματι, αφού xk=2kπ/N και f(xk)=yk:
Επομένως :
[c0,..c | | ,c | | ,..c−1]=
| | FN([y0,y1...y(N−1)]) |
<αφού
-
εάν n≥0, cn=yn
- εάν n<0 cn=yn+N
- ωN=exp(2iπ/N),
τότε ωNn=ωNn+N
Ιδιότητες
-
Οι συντελεστές του τριγωνομετρικού πολυωνύμου που παρεμβάλει την f
στα x=2kπ/N είναι
- Εάν η f είναι ένα τριγωνομετρικό πολυώνυμο P βαθμού m≤ N/2,
τότε
το τριγωνομετρικό πολυώνυμο που παρεμβάλει την f=P είναι το P, η αριθμητική
προσέγγιση των συντελεστών είναι στην πραγματικότητα ακριβής (cn=cn).
- Πιο γενικά, μπορούμε να υπολογίσουμε το cn−cn.
Υποθέτοντας ότι η f ισούται με την σειρά
Fourier της, δηλαδή ότι :
f(t)= | | cmexp(2iπ mt),
| | |cm|<∞ |
Τότε :
f(xk)=f( | | )=yk= | | cmωNkm,
c_n= | | | ykωN−kn |
Αντικαταστείστε το yk με την τιμή του στο c_n:
Εάν m≠ n (mod N ), ωNm−n είναι μια N-στη ρίζα της μονάδος διάφορη
του 1, και επομένως:
Άρα, εάν m−n είναι ένα πολλαπλάσιο του N (m=n+l· N) τότε
∑k=0N−1ωNk(m−n)=N, διαφορετικά
∑k=0N−1ωNk(m−n)=0.
Αντιστρέφοντας τα δυο αθροίσματα, έχουμε
c_n | = | |
| = | |
| = | ...cn−2· N+cn−N+cn+cn+N+cn+2·
N+..... |
|
Συμπέρασμα: εάν |n|<N/2, η διαφορά c_n−cn είναι ένα άθροισμα του cj μεγάλων δεικτών
(τουλάχιστον N/2 σε απόλυτη τιμή), και θα είναι μικρή (εξαρτάται από
την τάξη σύγκλισης των σειρών
Fourier).
Παράδειγμα, εισάγετε
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=c−k+ck ισούται με 1 εάν k=1, 2 και 0 σε κάθε άλλη περίπτωση.