Ugrás a tartalomhoz

Numerikus módszerek 1.

Stoyan Gisbert (1942–), Takó Galina (195?–) (2005)

Typotex

4.7. Trigonometrikus interpoláció, gyors Fourier-transzformáció

4.7. Trigonometrikus interpoláció, gyors Fourier-transzformáció

Legyen -periodikus függvény, amelynek értékeit ismerjük az

pontokban. Akkor egyértelműen meghatározható

(4.88)

vagyis

(4.89)

úgy, hogy

(4.90)

Ugyanis a jelöléssel felírt

(4.91)

egyenletrendszernek Vandermonde-féle determinánsa van, amely nem nulla. (Ehhez (4.12) szerint az is elég lett volna, hogy az halmaz különböző, -ből való pontból áll).

Az ekvidisztáns alappontok azért előnyösek, mert az

(4.92)

skaláris szorzatban (amellyel – nem függvények, hanem vektorok esetén – az 1.2. pontban már találkoztunk) igaz

(4.93)

Itt figyelembe vettük, hogy esetén

hiszen egységgyök: . Tehát az rendszer ortogonális a (4.92) skalárszorzatban. Felhasználva ezt, valamint a együtthatók (4.91) meghatározását, kapjuk

Vagyis

(4.94)

A (4.88)– (4.94) összefüggésekből általános tanulságot vonunk le a 33. feladatban.

Itt foglalkozunk a -k gyakorlati kiszámításával. Az összes előállítása a (4.94) képletből nyilván aritmetikai műveletbe kerül (feltéve, hogy az összes szükséges számot már előre kiszámítottuk), éppen úgy, mint meghatározása az pontban – ha adott :

(4.95)

A gyors Fourier-transzformáció egy olyan algoritmus (angolul a rövidítése FFT), amely mind a kettő, egészen hasonló feladatot,

Fourier-analízis: (4.94), tehát ,

Fourier-szintézis: (4.95), tehát ,

már művelettel oldja meg, hogyha (ahol a az osztói). Így az , a legegyszerűbb, lent ismertetésre kerülő esetben csupán művelet szükséges a helyett.

Legyen tehát , kiszámítandó

(4.96)

Itt akár Fourier-analízisről (ekkor ), akár a szintézisről (ekkor ) lehet szó, mivel csak azt a tulajdonságot használjuk majd, hogy . Egyébként a (4.96) alakban felírható több más számelméleti transzformáció, pl. a Walsh-, Fermat-, Mersenne-transzformáció. Lényeges egy egységgyök , amelynek segítségével felépíthető egy ortogonális bázis ; nemcsak komplex számokról lehet szó, hanem maradékosztályokról, gyűrűk elemeiről.

Írjuk (4.96)-ban a indexet

formában. Így

Most (4.96) helyett írhatjuk -re

Lényeges, hogy a , mennyiségeket ( -tagú Fourier összegeket) csak a fele indexre kell kiszámítanunk, -re, mert

és így

Ezzel már nyertünk valamit, még akkor is, hogyha most a , Fourier-összegeket a hagyományos módon számítjuk ki.

Ugyanis ebben az esetben művelet szükséges és előállítására (egy művelet legyen egy összeadás és egy szorzás mint 1.3.5-ben), amiután további 2 művelettel kapjuk a

mennyiségeket; ezeknek kiszámításához így 2n művelet helyett csak n+2 szükséges. Természetesen ehelyett rekurzív módon tovább bontjuk a , összeget -tagú összegekre, és így tovább.

Legyen most a műveletigény, amivel előállíthatjuk az összes -tagú összegeket. Ekkor

mivel láttuk, hogy 2 független -tagú Fourier-összegek halmazára volt szükségünk, és ezekből egy-egy művelettel kapjuk a -tagú összegeket. Figyelembe véve, hogy

levonhatjuk a következtetést:

Amennyiben csak a szorzásokat számítjuk, megmutatható (ld.  34. feladat), hogy .

Nem feltétlenül szükséges, hogy .

Amikor például , akkor (4.96)-ban a index következő felbontását használjuk:

ahol

Most

és így (v.ö. (4.96)-tal)

ahol

az -höz tartozó egységgyök. Most az és számokat lehet tovább felbontani.

A gyakorlati számításnál előnyös legalább az , , számokra a gyors Fourier-transzformációt végrehajtó programmal rendelkezni.

Említjük továbbá (ld. a 35. feladatot), hogy a (4.94) és (4.95) komplex Fourier-transzformációt a (valós) cosinus

(4.97)

és sinus transzformációra vezethetjük vissza,

(4.98)

ezeket pedig a „páratlan” cosinus transzformációra,

(4.99)

Ekkor a komplex transzformáció műveletigénye esetén szorzás és összeadás lesz.

A Fourier-analízist arra lehet használni, hogy periodikus jelenségeket alapvető összetevőikre bontsuk. Ekkor a gyors Fourier-transzformáció bevetésével lényeges időnyereményhez jutunk. Emiatt ennek az algoritmusnak alapvető szerepe van mechanikai és elektromágneses rezgések elemzésénél és transzformációjánál (pl. a villamosságtanban, hírközlésben, szeizmogramok és EKG-protokollok automatikus kiértékelésénél stb.).

Lássuk a gyors Fourier-transzformációnak egy első alkalmazását. Legyenek

-, ill.  -edfokú polinomok. Keressük a polinomot, amely -edfokú. Az egyszerű (iskolai) algoritmus ehhez műveletet követel.

Ahelyett így lehet eljárni. Kiszámítjuk és értékeit a

pontokban, tehát az egységkörön. Ehhez nyilván két Fourier-szintézis szükséges:

Ebből máris megkapjuk összes értékét,

Most csak még egy Fourier-analízis kell, amelynek segítségével kiszámítjuk együtthatóit. Összesen így művelet elegendő, és itt nem nagy a szorzó (ez a szorzó 3 egy Fourier-analízis és esetén).

Eddig tárgyaltuk a trigonometrikus interpolációt a (4.88), (4.94) alakban. A végtelen Fourier-sor,

alakja mutatja, hogy megfelelőbb lesz (4.88)-ról átmenni az

(4.100)

véges vagy csonkított Fourier-sorhoz (itt az r egész része). Ezt tehetjük, definiálva

mert ekkor a (4.88) és a (4.100) függvények,

miatt, az pontokban felveszik ugyanazokat az értékeket. A pontok között viszont lényegesen eltérhetnek egymástól. A (4.100) forma viszont közvetlenül át is írható a szokott

alakba, ahol

és

a

összefüggések alapján.

Második alkalmazásként használjuk a véges Fourier-sort és a gyors Fourier-algoritmust függvényértékek approximációjára; ez az alkalmazás közel áll a 2.6.3. pontban tárgyalt csonkított szinguláris felbontáshoz.

A periodikus függvény értékei legyenek adottak,

Ehhez kiszámítjuk először a

együtthatókat , majd segítségével megyünk át az

csonkított Fourier-sorhoz. Ezután az

reláció definiál olyan függvényt, amely „simított” abban az értelemben, hogy a legmagasabb frekvenciájú hullámok ( , ) hiányoznak belőle. A diszkrét paraméterrel befolyásolhatjuk a simítás fokát, kiszűrve a magasabb frekvenciákat.

Folytonosan változtatható paramétert alkalmazzuk a következő simítási eljárásnál.

Legyen az a -periodikus függvény, amelynek értékei minimalizálják az

függvényt, ahol , és a szokásos (4.17), (4.18) elsőrendű osztott differenciák lépéstávolsággal.

Az F függvény értelme a következő: kicsi -ra lényegesek a interpolációs feltételek; nagy esetén viszont előnyben részesítjük azt, hogy -nek ne legyenek túl nagy első deriváltjai (ld.  (4.24)). A

feltételekből (amelyek szükségképpen a minimum helyén teljesülnek) kapjuk a 2-re való osztás után

(4.101)

ahol

(4.102)

figyelembe véve, hogy periodikus.

Ennek a lineáris rendszernek a mátrixa szimmetrikus, soronként domináns főátlóval rendelkező M-mátrix. Így a megoldás egyértelműen meg van határozva (és kiszámítható a rövidített Gauss-eliminációnak egy változatával, ld. a 4.10.1. pontot).

Ezután a és függvényeket állíthatjuk elő eme pont elején leírt trigonometrikus interpoláció segítségével. A (4.101) Fourier-együtthatók birtokában ( Fourier-együtthatói legyenek , míg Fourier-együtthatóit -vel jelöljük) átmegyünk esetén , ill.  segítségével a (4.92) alakra.

Alkalmazzuk a g függvény (4.100) csonkított Fourier-sorát arra, hogy az és g(x) közötti viszonyt megvilágítsuk.

-ből kapjuk

és így

azaz

Itt

így a nagyobb és értékekre a lényegesen kisebb lesz a -nél, ugyanis ekkor

Kis és -re viszont alig különbözik -től, mert ilyenkor

Ezt az eljárást úgy lehet használni, hogy különböző -értékre kirajzoltatjuk (ill. kivetíttetjük) a függvényt. Ehhez először Fourier-analízissel előállítjuk a együtthatókat, abból , és végül Fourier-szintézissel kapjuk a simított függvényt.

Ez a példa azt is mutatja, hogyan lehet a Fourier-transzformáció segítségével bizonyos differenciálegyenleteket megoldani, hiszen a fenti (4.101), (4.102) egyenletrendszer nyilván approximálja a

feladatot (ilyenekkel a 11. fejezetben foglalkozunk), mivel

(4.24) szerint.

A Fourier-transzformáció lényegében helyettesíti az integrálást a Fourier- együtthatók osztásával és a differenciálást az együtthatók szorzásával, pl. az

osztott differenciához tartoznak a

együtthatók. Így lineáris differenciálegyenletből a Fourier-együtthatókat összekötő lineáris algebrai egyenletrendszer lesz. Ha nemlineáris tagok vannak a differenciálegyenletben, akkor előnyös olyan művelet, mint azt a polinomok szorzásának példáján bemutattuk: a Fourier-együtthatók (közelítő) értékek birtokában átmegyünk a Fourier-szintézissel a megfelelő függvényekhez, azoknak nemlineáris kifejezéseit kiszámítjuk, majd Fourier-analízissel visszamegyünk a Fourier-együtthatókhoz.