Fourierova transformace, aproximace, interpolace

Obtížnost: 3/5 Musíte trošku vědět

Někdy je potřeba, abychom vymysleli nějakou funkci, která se nám co nejblíže přibližuje třeba naměřeným hodnotám. K tomu používáme metod interpolace a aproximace. Poté se podíváme na lehce související téma s Fourierovo řadou a nakousneme fourierovu analýzu.

Interpolace

Interpolace je metoda, při níž vezmeme všechny naměřené body a vyrobíme takovou funkci, která všemi těmito body projde. K tomu využijeme tzv. Vandermondovy matice[1] více o tématu např. na cuni: http://www.kolej.mff.cuni.cz/~lmotm275/skripta/mzahrad/node41.html , což je zjednodušeně matice, která obsahuje všechny členy geometrické posloupnosti. Např. tedy:

$$ \begin{bmatrix}
a_0^0 & a_0^1 & a_0^2 \\
a_1^0 & a_1^1 & a_1^2 \\
a_2^0 & a_2^1 & a_2^2 \\
\end{bmatrix}$$

Pro to, abychom mohli provést interpolaci (tedy polynomiální), musíme si zvolit nějakou bázovou funkci, do které budeme interpolovat. Pokud chceme býti obecní, zvolíme si prostě obecnou funkci

$$ f(x) = a^0 x + a^1 x + a^2 x + … + a^{n-1} x $$

kde \(n \) vyjadřuje počet funkčních koeficientů. Pokud má platit interpolace, musí platit, jak je výše uvedeno, že výsledná funkce musí procházet všemi body. Aby funkce mohla toto splnit, musí být počet koeficientů minimálně takový, jaké je množství bodů. Pokud zvolíme více koeficientů, ty nepotřebné se akorát vynulují, proto je takové počínání zbytečné.

Samozřejmě může nastat situace, kdy máme naměřeno např. 10 bodů, které leží v přímce — potom samozřejmě všechny mocniny s “na druhou” počínaje budou též nulové.

Lehké varování: Pokud si to budete zkoušet doma, nezaokrouhlujte příliš, křivka vám pak body neprojde!

K čemu tedy využijeme Vandemondovy matice? Hledáme-li nejmenší vzdálenost nějakých vektorů, stačí vyřešit lineární soustavu rovnic (což vlastně soustava vektorů v matici je). Toho právě s výhodou využijeme. Ukážeme si prakticky na příkladu:

Jak spočítat interpolaci prakticky?

Ze všeho nejdříve je potřeba uvést “vstupní data”. Mějme tedy naměřeny třeba čtyři body (ať jich není moc, ale zase ať nejsou pouze dva):

X Y
0 0
1 2
2 2
3 4

Body tedy vypadají nějak takto:

 

Hledáme tedy takovou křivku, která přesně projde všemi body. Mezi nimi samozřejmě může libovolně oscilovat a dělat různé “psí kusy”, body ale musí projít.

Dále tedy obecně platí, že máme-li např. dva body, stačí nám na projití těmito body vždy alespoň přímka — tedy polynom 1. řádu. Pro tři body parabola, tedy polynom 2. řádu atd. Obecně tedy můžeme říci, že pro počet bodů \(N\) jsme schopni vytvořit interpolaci s polynomem \(N-1\) řádu.

Vytvoříme tedy soustavu rovnic s vektorem hodnot, bázovou funkci zvolíme jako polynom 3. řádu (máme 4 hodnoty):

$$
\begin{bmatrix}
1 & 0 & 0 & 0 \\
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
\end{bmatrix}
\begin{bmatrix}
x_0 \\
x_1 \\
x_2 \\
x_3
\end{bmatrix}
=
\begin{bmatrix}
0 \\
2 \\
2 \\
4
\end{bmatrix}
$$

K řešení soustavy jsem zavolal program Octave[2]Takový Matlab pro chudé 🙂 , do kterého jsem tedy zadal[3]Pokud by vás zajímalo, jak se počítají matice a rovnice, pak vězte, že pokud vytvořím inverzní matici z “levých stran” a vynásobím to (maticově klasicky) s vektorem z pravých stran, dostanu řešení. Ručně na papír bych to však řešil jednodušší metodou — gaussovou eliminací. Časem o této metodě možná taktéž něco napíšu, pro zatím však toto berte jako fakt.:

Výsledkem jsou čtyři hodnoty proměnných \(a_0, a_1, a_2, a_3\) právě v tomto pořadí. Jako kontrola nám slouží hodnota \(x_0\), kterou jsme očekávali nulovou — polynom pokud má konstantní člen nulový, pak prochází vždy nulou.

Funkce tedy je: \(y=a_0 + a_1 x + a_2 x^2 + a_3 x^3 = 0 + 4\frac{1}{3} x – 3 x^2 + \frac{2}{3} x^3\)

Vyrobíme-li tedy graf takové funkce (původní body jsou obmlženy červeně) vidíme, že graf opravdu prochází těmito čtyrmi body:

Jaké však hrozí riziko, pokud bychom měli bodů například 20? Museli bychom vytvořit takovou funkci, která by měla třeba až 20 koeficientů, tedy polynom 19. řádu. Představte si, co taková funkce dělá třeba na rozsahu hodnot \(<0, 10>\); v bodě \(0\) je sice třeba nulová, ale v bodě \(10\) při mocnině “na devatenáctou” může být až závratně vysoká (či nízká samozřejmě). Taková funkce je pak poněkud nestabilní a ne zcela dobře popisuje obecný trend v těchto bodech. Sice pořád platí, že taková funkce projde všemi body bezezbytku, ale mezi body je to naprostý chaos[4]Ano, narážím na teorii chaosu..

Někdy nám tedy stačí, abychom pouze určili obecný trend v naměřených datech — např. potřebujeme něco tzv. “proložit přímkou”. A k tomu slouží aproximace.

Aproximace

Aproximace je metoda, která je velmi podobná interpolaci, narozdíl od ní však neplatí ona podmínka, kdy počet koeficientů odpovídá počtu naměřených hodnot. Aproximace je tedy obecně metoda podobná interpolaci, kde \(n \leq n_x\), kde \(n\) odpovídá počtu koeficientů a \(n_x\) počtu hodnot.

Jak vidíte, aproximace snadno může přejít do interpolace — pokud nastanou ty správné podmínky. Interpolace se však nikdy nestane aproximací.

Typickým případem, kdy chceme udělat aproximaci, je nějaké proložení hodnot. Máme např. naměřené desítky hodnot, nicméně víme (či očekáváme), že hodnoty se budou pohybovat více-méně lineárně. Potom hledáme takovou přímku (či obecně křivku), pro kterou platí, že součet vzdáleností všech bodů (kladně i záporně) od dané křivky, bude právě nejmenší.

Pro tuto optimalizaci využijeme upravené metody, téměř jako během interpolace. Rozdíl však bude v počtu koeficientů. Pro takovou soustavu rovnic bychom však těžko hledali řešení, proto budeme muset provést úpravu pomocí metody nejmenších čtverců[5]o té se též někdy zmíním v nějakém článku, kterou lze zjednodušeně vyjádřit jako:

$$ A^T A = A^T y$$

kde \(A\) je matice vytvořena podobně, jako během interpolace, \(y\) je vektor hodnot a \(A^T\) je transponovaná matice \(A\).

Aproximace prakticky

Nyní opět prakticky. Budeme mít pár hodnot, které proložíme parabolou (ať je trochu legrace). Hodnoty jsou následující:

X Y
0 4.6
0.5 3.8
1 2.5
1.5 0.5
2 -0.2
2.5 0.2
3 2.8
3.5 4.1
4 3.9

V grafu tedy hodnoty vypadají nějak takto:

Budeme tedy hledat polynom 2. stupně (o 3 konstantách), sestavíme matici:

$$
\begin{bmatrix}
1 & 0 & 0 \\
1 & 0.5 & 0.5^2 \\
1 & 1 & 1 \\
1 & 1.5 & 1.5^2 \\
1 & 2 & 2^2 \\
1 & 2.5 & 2.5^2 \\
1 & 3 & 3^2 \\
1 & 3.5 & 3.5^2 \\
1 & 4 & 4^2 \\
\end{bmatrix}
$$

a vytvoříme rovnici:

$$
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0.5 & 1 & 1.5 & 2 & 2.5 & 3 & 3.5 & 4 \\
0 & 0.5^2 & 1^2 & 1.5^2 & 2 & 2.5^2 & 3 & 3.5^2 & 4^2 \\
\end{bmatrix}
\begin{bmatrix}
1 & 0 & 0 \\
1 & 0.5 & 0.5^2 \\
1 & 1 & 1 \\
1 & 1.5 & 1.5^2 \\
1 & 2 & 2^2 \\
1 & 2.5 & 2.5^2 \\
1 & 3 & 3^2 \\
1 & 3.5 & 3.5^2 \\
1 & 4 & 4^2 \\
\end{bmatrix}
\begin{bmatrix}
a_0 \\
a_1 \\
a_2
\end{bmatrix}
=
\begin{bmatrix}
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0.5 & 1 & 1.5 & 2 & 2.5 & 3 & 3.5 & 4 \\
0 & 0.5^2 & 1^2 & 1.5^2 & 2 & 2.5^2 & 3 & 3.5^2 & 4^2 \\
\end{bmatrix}
\begin{bmatrix}
4.6 \\
3.8 \\
2.5 \\
0.5 \\
-0.2 \\
0.2 \\
2.8 \\
4.1 \\
3.9
\end{bmatrix}
$$

Nyní opět zavolám na pomoc Octave, nejdříve si zadám matici a vektor hodnot (doufám, že tam někde neudělám překlep!):

Poté pro ilustraci udělám zvlášť levou a zvlášť pravou stranu:

Nyní provedu řešení této soustavy rovnic:

Funkce tedy bude: \(y = 1.0519 x^2 -4.2611 x + 5.0279 \)

Graf výsledné funkce tedy vypadá takto:

Fourierova transformace

Abychom mohli pochopit a správně provést tyto transformace, musíme znát několik termínů:

  • sudá funkce je taková funkce, pro kterou platí, že po dosazení dvou inverzních vstupních hodnot dostaneme stejné výsledky, tedy \(f(x) = f(-x)\). Např. tedy pro \(f(x)=x^2\) můžeme třeba pro \(x=2\) tvrdit \(f(2) = f(-2)\), tedy že \(4=4\).
  • lichá funkce je taková funkce, která splňuje \(-f(x) = f(-x)\), tedy např. pro funkci \(x^3\) můžeme tvrdit (opět pro vstup 2), že \(-f(2) = f(-2)\), tedy že \(-8=-8\).
  • integrování součinu provádíme nejčastěji (v případě FT) jako integrování per partes. Vysvětlení tohoto procesu je nad rámec článku, nicméně tuto metodu zde nejspíše též popíšu (na tomto serveru).

K čemu vlastně slouží taková fouriérova transformace? Všichni ji (resp. její výsledek) velmi dobře známe např. z obyčejného Winampu, který při přehrávání skladby zobrazuje, v jakém poměru se v dané hudbě aktuálně nachází basy, středy a výšky (tedy ekvalizér).

Další využití je např. během komprese a dekomprese obrazových dat (tato komprese je samozřejmě ztrátová).

Obecně lze říci, že že tuto transformaci použijeme tam, kde je daný signál (či vstup obecně) periodický a konečný (resp. změna takového vstupu není nekonečně velká).

Fourierova řada

Mějme nějakou funkci \(f(x)\), o které můžeme říci, že není nekonečná a pro zjednodušení[6]protože budeme počítat skoro výhradně se siny a cosiny, takže ať nám to “vychází hezky” všechny funkce budeme počítat na intervalu \(<-\pi, \pi>\).

Hledáme potom takovou funkci \(g(x)\), která nám původní funkci co nejlépe aproximuje a vypadá takto:

$$ g(x) = a_0 + a_1 \cos(x) + b_1 \sin(x) + a_2 \cos(2x) + b_2 \sin(2x) + \\
+ a_3 \cos(3x) + b_3 \sin(3x) + a_4 \cos(4x) + b_4 \sin(4x) \ldots $$

Obecně tedy hledáme součet

$$ g(x) = a_0 + \sum_{\mathrm{k}=1}^{\infty} a_\mathrm{k} \cos(\mathrm{k}x) + b_\mathrm{k} \sin(\mathrm{k}x) $$

Pro tyto koeficienty platí:

$$
\begin{array}{rcl}
a_0 & = & \frac{1}{2\pi} \int_{-\pi}^{\pi} f(x) \mathrm{d}x \\
a_\mathrm{k} & = & \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \cos{\mathrm{k}x} \mathrm{d}x \\
b_\mathrm{k} & = & \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin{\mathrm{k}x} \mathrm{d}x
\end{array}
$$

Fourierova řada prakticky

 Začněme “zlehka” tedy prvním příkladem; definujme si zadání funkce jako:

$$ \begin{array}{rrrr}
f(x) & = & 1 & \forall{x > 0} \\
f(x) & = & -1 & \forall{x \leq 0}
\end{array}
$$

Jak jsem uvedl výše, uvažujme též \(D(f(x)) \in <-\pi, \pi>\). Pro výpočet první konstanty tedy:

$$ a_0 = \frac{1}{2\pi} \int_{-\pi}^{\pi} f(k x) \mathrm{d}x = \frac{1}{2\pi} \int_{0}^{\pi} 1 \mathrm{d}x = \frac{1}{2\pi} [x]_0^\pi = \frac{1}{2\pi} (\pi – 0) = \frac{1}{2\pi} \pi = \frac{1}{2}$$

Nyní spočtěme rovnou “sinové” členy; kosínové můžeme taktéž, ale vidíme, že funkce je lichá, stejně jako funkce sinus, nebudeme se jí tedy bránit 🙂

$$ b_k = \frac{1}{\pi} \int_{-\pi}^{\pi} f(x) \sin(\mathrm{k}x) \mathrm{d}x =
\frac{1}{\pi} \int_{-0}^{\pi} sin(\mathrm{k}x) \mathrm{d}x =
\frac{1}{\pi \mathrm{k}} [-\cos{kx}]_{0}^{\pi} = \\
= \frac{-1}{\pi \mathrm{k}} [\cos{kx}]_{0}^{\pi} =
\frac{-1}{\pi \mathrm{k}} (\cos{k\pi} – 1) =
\frac{-1}{\pi \mathrm{k}} ( (-1)^{\mathrm{k}} – 1) =
\frac{1}{\pi \mathrm{k}} (1 – (-1)^{\mathrm{k}})
$$

Nyní vám nejspíše dlužím vysvětlení, co jsem to proboha prováděl v tomto výpočtu 🙂 Není to zase tak nic šíleného, jak se může na první pohled zdát, ale raději si to pěkně rozeberme postupně.

Vysvětlení výpočtu

Výpočet “vezmu” postupně, vysvětlím každý blok zvlášť. Jak blok chápu to, co se nachází mezi jednotlivými rovnítky (je to tedy i krok).

V prvním kroku jsem pouze napsal, co budu počítat obecně. Vidíme, že budeme integrovat od \(-\pi\) do \(\pi\) nějakou obecnou funkci násobenou sinem.

V druhém kroku jsem už dosadil konkrétní hodnoty. Využiji toho, že funkce je lichá symetrická  podle bodu počátku, tedy stačí, abych vyřešil pouze její polovinu a druhá bude funkční stejně (protože sinus je též lichá symetrická funkce). Proto tedy budu integrovat pouze od nuly do \(\pi\). V této části funkce nabývá hodnoty “1”, čili za \(f(x)\) dosadím jedničku a dovolím si ji před onen sinus nenapsat.

V třetím, tedy posledním kroku na první řárce jsem provedl integrování, ale zatím jsem neřešil meze integrálu, pouze jsem vyhledal primitivní funkci k té původní. Funkce \(\sin(kx)\) se podle \(x\) zintegruje jako \(\frac{-1}{\mathrm{k}} \cos(\mathrm{k}x)\), což jsem též provedl.

Ve čtvtém kroku, tj. první krok na druhé řádce, jsem pouze popřehazoval mínus, abych ho nemusel pak řešit v dalším výpočtu.

V pátem kroku jsem použil meze integrálu; využil jsem vlastnosti \([x]_a^b = (b-a)\), tyto hodnoty jsem tam tedy dosadil.

V šestém předposledním kroku jsem využil vlastnosti násobků \(\cos(k\pi)\), kde víme, že pokud za \(k\) dosadíme nulu, kosínus vyjde jedna, poku za \(k\) dosadíme jedničku, bude kosínus -1, pokud dvojku, bude opět jedna atd. Což odpovídá funkci \({(-1 )^k} \).

V posledním kroku jsem jen odstranil mínusové znaménko a tedy musel jsem přehodit i pořadí v rozdílu, abych provedl ekvivalentní úpravu.

Grafická reprezentace vypočtených koeficientů

Nicméně zpět k vypočítaným koeficientům. Provedl jsem (v excelu, soubor přiřadím jako přílohu) nasimulování těchto koeficientů a přidal jsem je jako funkci \(b_k \sin(\mathrm{k}x)\) a vynesl do grafu.

Ten vypadá takto:

Pro prvních 19 takto:

Vidíme, že čím vyšší harmonická, tím menší amplituda. Výslednou funkci dostaneme jako součet těchto (v tomto případě 19) křivek. Provedu tedy postupně součet a zobrazím všechny výsledky barevně opět do grafu.

Pro prvních 19 takto:

Pokud trošku vytížíme počítač a spočteme pro 100 koeficientů, vidíme, že už se graf moc nemění a poměrně věrně nám kopíruje “zadání”:

K čemu je to dobré?

Protože se přece jen nacházíme v článcích o fyzice, bylo by dobré tak nějak říci proč se tohle vůbec řeší a jaké to má důsledky.

Nejlépe si opět ukázat rovnou na praktickém příkladě. Představme si, že máme nějakou telefonní linku (nemusí to být nutně telefon, třeba Skype nebo obecně nějaký přenos po drátě či vzduchem) a chceme přenést nějaký signál, např. komorní a, tedy 440 Hz.

Naše linka je schopna přenést např. frekvence od 300 do 5000 Hz, tedy 440 Hz se bohatě vejde a můžeme prohlásit, že přenos sinusového signálu o frekvenci 440 Hz bude čistý a bez zkreslení[7]zde se samozřejmě dopouštím zjednodušení, ale berme to tak nyní. Nicméně budu chtít přenést tento obdélníkový signál (tedy signál, který vypadá jako obdélníky, tj. to, co jsme si zadefinovali výše).

Tento ukázaný fouriérův rozoj nám velmi prakticky ukázal, že obdélníkový signál se skládá z nekonečně mnoha dílčích signálů (harmonických frekvencí). Pokud tedy chceme přenést signál 440 Hz obdélníku, abychom měli signál tak čistý, jak je ukázáno v grafu s 5 sečtenými signály, budeme potřebovat \(5 \cdot 440 = 2200\ \mathrm{Hz}\) na přenos nejvyšší harmonické.

Chtěli-li bychom přenést onen signál o 19 složených funkcích, poté \(19 \cdot 440 = 8360\ \mathrm{Hz}\). Což už je frekvence, kterou naše linka o maximální frekvenci 5000 Hz není schopna přenést. Bez zkreslení je totiž schopna přenés maximálně 11. harmonickou frekvenci, tedy 4840 Hz.

Když toto víme, máme vůbec nějakou možnost zjistit, co se v daném signálu tedy nachází za harmonické (či jiné) frekvence, abychom věděli, co všechno ze signálu bude omezeno?

Ano máme, těmto metodám říkáme:

Fourierovy transformace

 Typů fouriérových transformací je několik — ve své podstatě převod na fourierovu řadu je též transformace, konkrétně tzv. rychlá fourierova transformace, nebo-li FFT. Mrkněme se však nyní na integrální fourierovu transformaci. Ta se využívá trošku k něčemu jinému, i když je základ podobný.

Jak jsem uvedl výše, někdy je potřeba zjistit, co všechno se v signálu nachází — ať už kvůli zpracování různých signálů (např. modem či frekvenční multiplexer), či třeba jen pro zábavu typu ekvalizéru ve winampu (nebo třeba různé vizualizace hraní typu světelná hudba a podobně).

Abychom mohli FT provést, musíme mít nějaký “rámec”, ve kterém je vše, co děláme, co nejvíce periodické. Je jasné, že třeba v hudbě se pořád něco mění, nicméně rozvrzorkujeme-li si hudební signál na vhodné rámce, dostaneme lokální periodicitu, čili můžeme pro každý tento rámec vyřešit.

Definice integrální fourierovy transformace

Podobně jako třeba Laplaceova transformace, i FT převádí daný “vstupní” signál na výstupní obrazovou formu. Tam, kde Laplace řeší přenosy nějaké soustavy, ve FT se řeší frekvenční přenosy. Integrální forma má tvar:

Mějme danou funkci \(f(\omega t)\) pro kterou platí, že je periodická, potom můžeme vytvořit obrazovou funkci

$$ F(\omega) = \int_{-\infty}^\infty f(\omega t) \mathrm{e}^{-i \omega t} \mathrm{d}t$$

Spočtením tohoto integrálu dostanem množství amplitudy v závislosti na frekvenci (v našem případě \(\omega\)).

Malá ukázka na příkladu

Využijeme stejné vstupní funkce, jako jsme měli výše. Provedeme integraci této funkce a povídáme se, co provádí po transformaci, budeme ji však zkoumat na celém rozsahu (nikoliv pouze od nuly):

$$
F(f) = \int_{-\pi}^\pi 1 \mathrm{e}^{-i \omega t} \mathrm{d}t = \frac{1}{-i \omega} [\mathrm{e}^{-i \omega t}]_{-\pi}^\pi =
\frac{1}{-i \omega} (\mathrm{e}^{-i \omega \pi} – \mathrm{e}^{i \omega \pi}) = \\
= \frac{1}{-i 2 \pi f} (\mathrm{e}^{-i \pi (2 \pi f) } – \mathrm{e}^{i \pi (2 \pi f)}) =
\frac{1}{\pi f} (\frac{\mathrm{e}^{i \pi (2 \pi f)} – \mathrm{e}^{-i \pi (2 \pi f)}}{2 i}) =
\frac{1}{\pi f} \sin(\pi f \pi) = 1 (\frac{\sin(\pi^2 f)}{\pi f})
$$

Můžeme využít vztahu \(\frac{\sin(\pi f)}{\pi f} = \mathrm{sinc}{f}\), akorát musíme zlomek rozšířit pomocí \(\frac{\pi}{\pi}\), tedy:

$$\frac{\pi}{\pi} (\frac{\sin(\pi^2 f)}{\pi f}) = \pi  (\frac{\sin(\pi^2 f)}{\pi^2 f}) = \pi\ \mathrm{sinc}(\pi f) $$

Vysvětlení postupu výpočtu

Opět vysvětlím provedený výpočet, a to postupně po jednotlivých krocích:

  1. Nejdříve v prvním kroku jsem určil meze výpočtu a za \(f(x)\) jsem dosadil “jedničku” (protože tuto hodnotu funkce má).
  2. V druhém kroku jsem zintegroval (zatím bez použití mezí).
  3. V posledním kroku na 1. řádce jsem zadal meze výpočtu.
  4. Na druhém řádku jsem využil vztahu \(\omega = 2 \pi f\) a toto jsem do vzorce dosadil.
  5. \(-2 i\) jsem přehodil do jmenovatele do závorky, změnil mu znaménko, takže rozdíl v čitateli jsem otočil (protože \(-(A-B) = (B-A)\)).
  6. Krok číslo 5. jsem dělal proto, abych mohl využít exponenciálního zápisu funkce \(\sin()\), čehož jsem teď využil a funkci na sinus přepsal.
  7. V posledním kroku jsem pouze sjednotil závorku.

Další krok už je vysvětlen výše, proto ho zde vysvětlovat nebudu. Stejně tak by ale poslední krok mohl být i posledním krokem ve výpočtu, převod na \(\mathrm{sinc()}\) není potřeba.

Grafické znázornění dat

Vytvoříme-li graf takové funkce, uvidíme:

Pokud si trošku přiblížíme oblast kolem “nuly”, uvidíme:

Jak vidíme, v oblasti od \(-\pi\) do \(\pi\) máme spojité rozložení amplitud a frekvencí — tedy to, co jsme očekávali, pro “hranatý” signál je prostě potřeba přenést nekonečné množství frekvencí.

Závěrem

S “Fourierem” obecně se dá dělat spousta zajímavých věcí, všechna využití ani neznám 🙂 FFT můžeme využít třeba pro ukládání obrazových dat[8]Obraz rozložíme na sektory a každý zpracováváme zvlášť jako vlnovou funkci. Poté jen ukládáme koeficienty z fourierovy transformace, čímž jsme schopni hodně ušetřit. Podle množství a přesnosti koeficientů určujeme kvalitu obrázku. Zkuste si schválně převést nějaký obrázek do JPG a nastavit mu nejnižší možnou kvalitu, uvidíte čtverečky — to jsou jednotlivé rámce, přes které se počítá., využíváme ji např. ve zpracování signálu[9]Např. při přenosu více informací po jedné lince, jsme takto na “jeden drát” natlačit třeba i stovky přenosů, každý má svůj kousek pásma. Stejně tak funguje třeba i přenos vzduchem — vzduch je vlastně jeden “velký drát”, takže pokud chceme přenášet např. více kanálů rádia, každý se nachází na své frekvenci — a to je právě ono fourierovo rozdělení, ke kterému jsme tady došli..

Existují i metody zpětné transformace, ale ty jsou opravdu mimo rozsah tohoto příspěvku, už takto je až přehnaně dlouhý. Myslím však, že pro základní představu o tom, co “to je”, jste si na základě tohoto textu udělat mohli. Pokud se však chcete o tématiku zajímat dále, doporučuji jakákoliv skripta vysokoškolské matematiky, kde všechny tyto a mnohé další věci máte vysvětleny, a to včetně důkazů.

Seznam příloh

[attachments include=”215,179,177,178″]

Poznámky pod čarou   [ + ]

1. více o tématu např. na cuni: http://www.kolej.mff.cuni.cz/~lmotm275/skripta/mzahrad/node41.html
2. Takový Matlab pro chudé 🙂
3. Pokud by vás zajímalo, jak se počítají matice a rovnice, pak vězte, že pokud vytvořím inverzní matici z “levých stran” a vynásobím to (maticově klasicky) s vektorem z pravých stran, dostanu řešení. Ručně na papír bych to však řešil jednodušší metodou — gaussovou eliminací. Časem o této metodě možná taktéž něco napíšu, pro zatím však toto berte jako fakt.
4. Ano, narážím na teorii chaosu.
5. o té se též někdy zmíním v nějakém článku
6. protože budeme počítat skoro výhradně se siny a cosiny, takže ať nám to “vychází hezky”
7. zde se samozřejmě dopouštím zjednodušení, ale berme to tak nyní
8. Obraz rozložíme na sektory a každý zpracováváme zvlášť jako vlnovou funkci. Poté jen ukládáme koeficienty z fourierovy transformace, čímž jsme schopni hodně ušetřit. Podle množství a přesnosti koeficientů určujeme kvalitu obrázku. Zkuste si schválně převést nějaký obrázek do JPG a nastavit mu nejnižší možnou kvalitu, uvidíte čtverečky — to jsou jednotlivé rámce, přes které se počítá.
9. Např. při přenosu více informací po jedné lince, jsme takto na “jeden drát” natlačit třeba i stovky přenosů, každý má svůj kousek pásma. Stejně tak funguje třeba i přenos vzduchem — vzduch je vlastně jeden “velký drát”, takže pokud chceme přenášet např. více kanálů rádia, každý se nachází na své frekvenci — a to je právě ono fourierovo rozdělení, ke kterému jsme tady došli.

1 komentář u „Fourierova transformace, aproximace, interpolace

Komentáře nejsou povoleny.