SPEKTRÁLNÍ ANALÝZA 2
MARTIN KOLÁŘ
Obsah
1 Aplikace spojité Fourierovy analýzy 3
1.1 Ortogonální polynomy . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1.1 Legendreovy polynomy . . . . . . . . . . . . . . . . . . . . . . 5
1.1.2 Aplikace Legendreových polynomů v numerice . . . . . . . . . 7
1.2 Aplikace Fourierových řad na problém rekurence náhodné procházky . 9
1.2.1 Náhodná procházka . . . . . . . . . . . . . . . . . . . . . . . . 10
2 Diskrétní fourierova transformace 14
2.1 Cyklická konvoluce . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.2 Diskrétní fourierova transformace . . . . . . . . . . . . . . . . . . . . 16
2.3 Další vlastnosti diskrétní Fourierovy transformace . . . . . . . . . . . 18
2.3.1 Posunutí . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
2.3.2 Modulace (frekvenční posun) . . . . . . . . . . . . . . . . . . . 19
2.4 Transformace sumy a diference . . . . . . . . . . . . . . . . . . . . . . 19
2.5 Maticová reprezentace diskrétní Fourierovy
transformace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.6 Symetrická diskrétní Fourierova transformace . . . . . . . . . . . . . 20
2.6.1 Reálná diskrétní Fourierova transformace . . . . . . . . . . . . 21
2.6.2 Inverzní reálná diskrétní Fourierova transformace . . . . . . . 21
2.6.3 Diskrétní sinová a cosinová Fourierova transformace . . . . . . 22
2.6.4 Aplikace diskrétní Fourierovy transformace . . . . . . . . . . . 23
3 Z-transformace 25
3.1 Inverzní Z-transformace . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 Vlastnosti Z-transformace . . . . . . . . . . . . . . . . . . . . . . . . 26
3.3 Řešení diferenčních rovnic pomocí
Z-transformace . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Laplaceova transformace 29
4.1 Existence Laplaceovy transformace . . . . . . . . . . . . . . . . . . . 30
4.2 Laplaceova transformace derivace . . . . . . . . . . . . . . . . . . . . 30
4.3 Věty o posunu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
1
5 Hartleyho transformace 34
5.1 Sudá a lichá část Hartleyho transformace . . . . . . . . . . . . . . . . 34
5.2 Diskrétní Hartleyho transformace . . . . . . . . . . . . . . . . . . . . 35
6 Radonova transformace 36
6.1 Inverzní radonova transformace . . . . . . . . . . . . . . . . . . . . . 37
7 Jednotící pohled na Fourierovy řady, Fourierovu transformaci a
diskrétní Fourierovu transformaci s využitím zobecněných funkcí 38
7.1 Zobecněné funkce (distribuce) . . . . . . . . . . . . . . . . . . . . . . 38
7.2 Operace na distribucích . . . . . . . . . . . . . . . . . . . . . . . . . 39
7.3 Zobecněná Fourierova transformace . . . . . . . . . . . . . . . . . . . 40
7.4 Zobecněná Fourierova transformace zobecněných periodických funkcí 41
8 Rychlá Fourierova transformace 43
2
Kapitola 1
Aplikace spojité Fourierovy
analýzy
1.1 Ortogonální polynomy
Skalární součin na C([−π, π]):
(f, g) =
π
−π
f(x)¯g(x)dx
→ L2-teorie
Zobecnění: skalární součin s váhovou funkcí
r(x) . . . váhová funkce, hladká funkce na intervalu [a, b]
r(x) ∈ C([a, b]) ∩ L1
([a, b])
Na C([a, b]) definujeme skalární součin (f, g) předpisem
(f, g) =
b
a
r(x)f(x)¯g(x)dx
Lemma 1.1.1. (f, g) je skalární součin na C([a, b]), tj. platí:
(i) (f, g) = (g, f)
(ii) (λf + µg, h) = λ(f, h) + µ(g, h)
(iii) (f, f) ∈ R, (f, f) ≥ 0
(iv) (f, f) = 0 ⇔ f ≡ 0
Důkaz:
(i) (f, g) =
b
a
r(x)f(x)¯g(x)dx =
b
a
r(x)¯g(x)f(x)dx = (g, f), r = ¯r
(ii) zřejmé
(iii) (f, f) =
b
a
r(x)
≥0
|f(x)|2
≥0
dx ≥ 0
(iv) 0 = (f, f) =
b
a
r(x)
>0
|f(x)|2
dx ⇒ f(x) = 0
3
Pro každý skalární součin platí Cauchy - Schwartzova nerovnost:
|(f, g)| ≤ f g
neboli
(f, g)2
≤ (f, f)(g, g),
tedy
(
b
a
r(x)f(x)¯g(x)dx)2
≤
b
a
r(x)(f(x))2
dx
b
a
r(x)(g(x))2
dx
Skalární součina dává normu:
f = (f, f)1/2
a platí:
λf = |λ| f ,
f = 0 ⇔ f = 0,
f + g = f + g
Lemma 1.1.2. Nechť uj je polynom stupně přesně j. Jsou-li polynomy u0, u1, . . . , um
ortonormální a p je polynom stupně ≤ m, potom
p =
m
j=0
(f, uj)uj
.
Důkaz: p je lineární kombinací polynomů u0, u1, . . . , um, tedy ∃λ0, λ1, . . . , λm tak,
že p = m
j=0 λjuj:
indukcí: nechť tvrzení platí pro m−1 a pm je polynom stupně ≤ m, pm = m
k=0 akxk
,
um(x) = m
k=0 ajxk
, kde bm = 0, a tedy pm = 1
bm
amum + pm−1, kde pm−1 je polynom
stupně ≤ m − 1,
pm−1 = pm − 1
bm
amum
(P, uj) = ( m
k=0 λkuk, uj) = λj, tedy p = m
j=0(f, uj)uj.
Věta 1.1.3. Nechť uj je polynom stupně přesně j. Tvoří-li polynomy u0, u1, u2, . . .
ortonormální systém, pak
f −
n
j=0
(f, uj)uj → 0
pro n → ∞ pro všechny funkce f ∈ C([a, b]).
Důkaz: Z Weierstrassovy věty víme, že pro ∀ > 0 existuje polynom stupně, řekněme,
m tak, že |P(x) − f(x)| < pro ∀x ∈ [a, b].
Tedy P(x) − f(x) = (
b
a
r(x)((P(x)−f(x)))2
dx)1/2
≤ K, kde K = (
b
a
r(x)dx)1/2
.
4
Pro g ∈ C([a, b]) označme Rng = n
j=0(g, uj)uj.
Pak pro n ≥ m máme podle předchozího lemmatu RnP = P, a tedy
f − n
j=0(f, uj)uj = f − Rnf ≤ f − P
≤ K
+ P − RnP
=0
+ RnP − Rnf =
= f − P + Rn(P − f)
≤ P−f
≤ 2 P − f ≤ 2 K,
tedy n
j=0(f, uj)uj → f pro n → ∞ v normě L2
.
Příklad 1.1.4.
(i) pro r(x) ≡ 1 a [a, b] = [−1, 1] máme Legendreovy polynomy
(ii) Čebyševovy polynomy Tn : cos(nθ) = Tn(cos θ)
Lemma 1.1.5. Polynomy 1√
2
T0, T1, T2, . . . tvoří ortonormální systém na intervalu
[−1, 1] vzhledem k váhové funkci r(x) = 2
π
1√
1−x2 .
Důkaz: (Tn, Tm) =
1
−1
2
π
1√
1−x2 TnTmdx =
/ substituce cos θ = x ⇒ dx = −sinθdθ = −
√
1 − cos2 θdθ =
√
1 − x2dθ /
=
π1
0
2
π
cos(nθ) cos(mθ)dθ =
1 pro m = n,
0 pro m = n,
tedy Tj tvoří ortogonální systém.
Příklad 1.1.6. další ortonormální polynomy:
polynomy [a, b] r(x)
Legendreovy [−1, 1] 1
Čebyševovy I. druhu [−1, 1] 1√
1−x2
Čebyševovy II. druhu [−1, 1]
√
1 − x2
Hermiteovy (−∞, ∞) e−x2
Lagnerrovy [0, ∞) xα
e−x
, α < −1
Jacobiho (−1, 1) (1 − x)α
(1 + x)α
Gegenbauerovy [−1, 1] (1 − x2
)α−1
2
1.1.1 Legendreovy polynomy
[a, b] = [−1, 1], r(x) = 1
Pn(x) =
1
2nn!
dn
dxn
(x2
− 1)n
Lemma 1.1.7.
(i) Pn je reálný polynom stupně přesně n.
(ii) Pro 0 ≤ r ≤ n je
dr
dxr
(x2
− 1)n
= (x2
− 1)n−r
Qn,r(x),
5
kde Qn,r(x) je polynom.
(iii) Pro 0 ≤ r ≤ n je dr
dxr (x2
− 1)n
= 0 v bodech x = ±1.
(iv) Pro 0 ≤ r ≤ n a m ≥ 0 platí
1
−1
dn
dxn
(x2
− 1)n dm
dxm
(x2
− 1)m
dx =
1
−1
dn−r
dxn−r
(x2
− 1)n dm+r
dxm+r
(x2
− 1)m
dx.
(v)
1
−1
(x2
− 1)n
dx = (−1)n2n+1n!
n
r=0(2r+1)
.
(vi)
1
−1
Pn(x)Pm(x)dx = 0 pro n = m.
(vii)
1
−1
Pn(x)2
dx = 2
2n+1
.
Důkaz:
(i) zřejmé
(ii) indukcí: r → r + 1:
dr+1
dxr+1 (x2
− 1)n
= d
dx
((x2
− 1)n−r
Qn,r(x)) = (n − r)(x2
− 1)n−(r+1)
2xQn,r(x)+
+((x2
− 1)n−r
Qn,r(x)) = (x2
− 1)n−(r+1)
(2xQn,r(x)(n − r) + (x2
− 1)Qn,r(x)) =
= (x2
− 1)n−(r+1)
Qn,r+1(x)
(iii) dosazením do (ii)
(iv) per partes:
L = dn
dxn (x2
− 1)n dm−1
dxm−1 (x2
− 1)m
|1
−1 −
1
−1
dn+1
dxn+1 (x2
− 1)n dm−1
dxm−1 (x2
− 1)m
= . . .
(opakujeme r×)
(v) In =
1
−1
(x2
− 1)n
dx =
/ u = 1, v = (x2
− 1)n
⇒ u = x v = 2xn(x2
− 1)n−1
/
= x(x2
− 1)|1
−1
=0
−
1
−1
2x2
(x2
− 1)n−1
dx = −2
1
−1
((x2
− 1) + 1)n(x2
− 1)n−1
dx =
= −2n
1
−1
(x2
− 1)n
dx − 2n
1
−1
(x2
− 1)n−1
dx = −2nIn − 2nIn−1 ⇒ In = −2nIn−1
1+2n
indukcí: I0 =
1
−1
1dx = 2
n − 1 → n: In = −2n
1+2n
(−1)n−12n(n−1)!
n−1
r=0 (2r+1)
= (−1)n2n+1n!
n
r=0(2r+1)
(vi) v (iv) položme r = m + 1 a búno předpokládejme n > m:
1
−1
dn
dxn (x2
− 1)n dm
dxm (x2
− 1)m
dx = (−1)r 1
−1
dn−r
dxn−r (x2
− 1)n dm+r
dxm+r
(x2
− 1)m
=0
dx = 0
(vii) v (iv) položme r = m = n:
1
−1
( 1
2nn!
)2 d2n
dx2n
(x2
− 1)n
=(2n)!
(x2
− 1)n
dx = ( 1
2nn!
)2 (2n)!(−1)n2n+1n!
n
r=0(2r−1)
= 2
2n+1
Lemma 1.1.8. Nechť u1, u2, . . . , un jsou ortonormální polynomy vzhledem k váhové
funkci r(x) na intervalu [a, b] a nechť uj je polynom stupně přesně j. Pak uj má
přesně j jednoduchých kořenů ležících v [a, b].
Důkaz: Sporem: Nechť tvrzení věty neplatí. Pak un mění znaménko méně než n×,
řekněme, že v bodech x1, x2, . . . , xk ∈ (a, b).
6
Nechť Q(x) = k
j=1(x − xj).
Pak Qun je na [a, b] − {x1, x2, . . . , xk} > 0 nebo < 0.
Tedy (Q, un) =
b
a
r(x)Q(x)un(x)dx = 0.
Ale Q(x) má stupeň < n, a tedy
(Q, un) = ( k
j=1(Q, uj)uj, un) = k
j=1(Q, uj) (uj, un)
=0
= 0
→ spor.
1.1.2 Aplikace Legendreových polynomů v numerice
Gaussova kvadratura
Chceme počítat
b
a
f(x)dx pomocí lineární substituce
u =
2
b − a
(x −
b + a
2
).
Stačí použít
1
−1
f(x)dx.
Výpočet z definice Riemannova integrálu: přes Riemannovy součty
Tn(f) =
n−1
r=−n
1
n
f(
2r + 1
2n
).
Tato metoda zaručeně konverguje, ale velmi pomalu.
Příklad 1.1.9. f(x) = x2
Tn(f) = n−1
r=−n
1
n
(2r+1
2n
)2
= 21
4
n−3 n−1
r=−n((2r2+1
)2
= 2
3
+ 1
6
1
n2
s použitím n−1
r=0 r = n(n−1)
2
a n−1
r=0 r2
= n(n−1)(2n−1
6
.
Chceme co nejrychlejší konvergenci → kvadraturní formule, přesné pro polynomy.
Lemma 1.1.10. Nechť −1 ≤ x1 < x2 < . . . < xn ≤ 1. Pak existují jednoznačně
určená čísla A1, A2, . . . , An tak, že
1
−1
P(x)dx =
n
j=1
AjP(xj)
pro polynomy stupně ≤ n − 1.
Důkaz:
• existence: Označme Qj(x) = k=j(x−xk)
k=j(xj−xk)
.
Platí Qj(xk) = 0 pro k = j a Qj(xj) = 1.
Nechť P(x) je polynom stupně ≤ n−1. Pak R(x) = P(x)− n
j=1 P(xj)Qj(x).
R(x) je polynom stupně ≤ n − 1 a platí R(xj) = 0 ⇒ R(x) má n kořenů ⇒
7
R(x) ≡ 0 a platí P(x) = n
j=1 P(xj)Qj(x)
⇒
1
−1
P(x)dx =
1
−1
P(xj)Qj(x)dx = n
j=1 P(xj)
1
−1
Qj(x)dx
=:Aj
=
= n
j=1 AjP(xj).
• jednoznačnost: Nechť
1
−1
P(x)dx = n
j=1 BjP(xj) pro polynom stupně
≤ n − 1.
Pro P(x) = Qj(x) dostaneme
1
−1
Qj(x)dx = n
k=1 BkQj(xk) = Bj, tedy
Aj = Bj.
Věta 1.1.11. (Gaussova) Nechť x1, x2, . . . , xn jsou kořeny n−tého Legendreova polynomu.
Pak existují čísla A1, A2, . . . , An tak, že
1
−1
P(x)dx =
n
j=1
AjP(xj)
pro libovolný polynom stupně ≤ 2n − 1.
Důkaz: Nechť A1, A2, . . . , An jsou konstanty z předchozího lemmatu, příslušné
Legendreovým polynomům Pn(x).
Je-li P(x) polynom stupně ≤ 2n − 1, vydělme jej Pn:
P(x) = Pn(x)Q(x) + R(x), kde stQ(x) ≤ n − 1 a stR(x) ≤ n − 1.
1
−1
P(x)dx =
1
−1
Pn(x)Q(x)dx
=0
+
1
−1
R(x)dx = n
j=1 AjR(xj),
ale P(xj) = Pn(xj)
=0
Q(xj) + R(xj) = R(xj)
⇒
1
−1
P(x)dx = n
j=1 AjP(xj.
Lemma 1.1.12. Nechť −1 ≤ x1 < x2 < . . . < xn ≤ 1 a A1, A2, . . . , An jsou takové,
že
1
−1
P(x)dx = n
j=1 AjP(xj) pro všechny polynomy stupně ≤ 2n − 1. Pak body
x1, x2, . . . , xn jsou kořeny Legendreova polynomu Pn(x).
Důkaz: Nechť T(x) = n
j=1(x − xj). Pak TPr(x) pro r < n má stupeň ≤ 2n − 1.
Pak
1
−1
TPr(x)dx = n
j=1 AjT(xj)Pr(xj) = 0
⇒ T(x) je polynom stupně n, který je kolmý na P0, P1, . . . , Pn−1
⇒ T(x) je násobek Pn(x) a má tedy stejné kořeny jako Pn(x)
⇒ x1, x2, . . . , xn jsou kořeny polynomu Pn(x).
Poznámka. Newton - Coatesovy formule: xj = −1 + 2(j−1)
n
• n = 2 →
1
−1
f(x)dx ≈ f(−1) + f(1) → lichoběžníkové pravidlo
8
• n = 3 →
1
−1
f(x)dx ≈ 1
3
(f(−1) + 4f(0) + f(1)) → Simpsonovo pravidlo
• Pro velké n jsou Aj velká čísla střídající znaménko,
např. n = 21: A1 ≈ 106
, A2 ≈ 10−6
1
−1
1
1+16x2 dx T21(x) = −1, 93
Pro Gaussovu formuli se toto nestane.
Lemma 1.1.13. Nechť −1 ≤ x1 < x2 < . . . < xn ≤ 1 a A1, A2, . . . , An jsou jako
v Gaussově větě. Pak
(i) A1, A2, . . . , An > 0
(ii) n
j=1 Aj = 2
Důkaz:
(i) Qj(x) = k=j(x − xj)2
, stQj(x) = 2n − 2, tedy podle Gaussovy věty
1
−1
Qj(x)dx = n
k=1 AkQj(xk) = AjQj(xj)
Qj(xk) > 0,
1
−1
Qj(x)dx > 0 ⇒ Aj > 0
(ii) Pro P(x) ≡ 0 máme 2 =
1
−1
1dx = n
j=1 AjP(xj) = n
j=1 Aj
Označení:
(i) P2n−1 . . . prostor polynomů stupně ≤ 2n − 1
(ii) Gn(f) = n
j=1 Ajf(xj), kde Aj a xj jsou jako v Gaussově větě
(iii) f sup = supx∈[−1,1]|f(x)|
Věta 1.1.14. (Stieltjes) Platí:
Gn(f) −
1
−1
f(x)dx ≤ 4inf f(t) − P(t) sup , P(t) ∈ P2n−1
Důkaz: Nechť P(x) ∈ P2n−1, pak Gn(P) =
1
−1
P(x)dx, tedy
Gn(f) −
1
−1
f(x)dx = Gn(f) − Gn(P) − (
1
−1
f(x)dx −
1
−1
P(x)dx) ≤
≤ |Gn(f) − Gn(P)| +
1
−1
(f(x) − P(x))dx ≤ n
j=1 Aj(f(xj) − P(xj))dx +
+2 f(x) − P(x) sup ≤ 2 f(x) − P(x) sup + 2 f(x) − P(x) sup =
= 4 f(x) − P(x) sup
1.2 Aplikace Fourierových řad na problém rekurence
náhodné procházky
Opakování: Fourierovy řady v R1
f(x) . . . 2π-periodická funkce,
9
ck = 1
2π
2π
0
f(x)e−ikx
dx,
pak f(x) = ∞
−∞ ckeikx
Analogicky v Rm
:
x = (x1, . . . , xm),
f(x) . . . 2π-periodická funkce ve všech proměnných, tj.
f(x1, . . . , xi + 2π, . . . , xm) = f(x1, . . . , xi, . . . , xm) pro ∀i,
k = (k1, . . . , km) ∈ Zm
multiindex,
k · x = m
j=1 kj · xj pro k ∈ Zm
a x ∈ Rm
,
ck = 1
(2π)m [0,2π]m f(x)e−ikx
dx,
pak f(x) = k∈Zm ckeikx
1.2.1 Náhodná procházka
• V R1
:
Nechť X1, X2, . . . , Xm je posloupnost nezávislých stejně rozdělených náhodných
veličin.
P(Xi = 1) = P(Xi = −1) = 1
2
Náhodný proces
Sn = X1 + X2 + . . . + Xm, S0 = 0
se nazývá Symetrická jednoduchá náhodná procházka.
Platí:
E(Xj) = 1
2
· 1 + 1
2
· (−1) = 0
E(X2
j ) = E(1) = 1
E(Sn) = E(Xj) = 0
E(S2
n) = E(X2
j ) = n
j=1 1 = n
• V Rm
:
např. m = 2: Uvažujme Z2
= celočíselné body v R2
Rekurence: Vrátí se částice zpět do počátku? S jakou pravděpodobností?
Věta 1.2.1. (Pólya) Uvažujme částici konající náhodnou procházku na množině
Zm
, kde m ∈ N, splňující následující podmínky:
(i) Jestliže v čase t = n je částice v bodě k = (k1, . . . , km) ∈ Zm
, pak pravděpodobnost
p(k, k ), že v čase t = n + 1 bude v bodě k = (k1, . . . , km) ∈ Zm
, je
p(k, k ) =
1
2m
, je-li m
j=1 kj − kj = 1 (sousední body),
0 pro ostatní k .
(ii) Jednotlivé kroky jsou nezávislé náhodné veličiny.
(iii) V čase t = 0 je částice v bodě 0 = (0, . . . , 0) ∈ Zm
.
10
Pak:
(I) P(částice se vrátí do počátku v nějakém čase t > 0) = 1 pro m = 1, 2,
(II) P(částice se vrátí do počátku v nějakém čase t > 0) < 1 pro m > 3.
Důsledek 1.2.2.
(i) Pro m ≤ 2 částice navštíví s pravděpodobností 1 nekonečněkrát každý bod v Zm
.
(ii) Pro m > 2 se vzdálenost částice od počátku s pravděpodobností 1 blíží ∞ pro
t → ∞.
Lemma 1.2.3. Nechť qn je pravděpodobnost, že se částice vrátí do počátku alespoň
n× a nechť un je pravděpodobnost, že se vrátí přesně n×. Označme q = q1. Pak pro
∀n ≥ 0 platí
qn = qn
, un = qn
(1 − q).
Důkaz: qn+1 = P(vrátí se alespoň (n + 1)×) =
= P(vrátí se alespoň (n + 1) × /n×) · qn = q · qn
q0 = 1 ⇒ qn = qn
un = P(vrátí se alespoň n×)−P(vrátí se alespoň (n+1)×) = qn
−qn+1
= qn
(1−q)
Lemma 1.2.4.
(i) Je-li q = 1, pak s pravděpodobností 1 se částice vrátí do počátku nekonečněkrát.
(ii) Je-li q < 1, pak s pravděpodobností 1 se částice vrátí do počátku konečněkrát.
Důkaz: P(nekonečněkrát) = 1 − P(konečněkrát) =
= 1 − ∞
i=1 ui = 1 − ∞
i=1 qi
(1 − q) =
1 − (1 − q) · 1
1−q
= 1 − 1 = 0 pro q < 1,
1 − ∞
i=1 qi
· 0 = 1 − 0 = 1 pro q = 1.
Lemma 1.2.5. Nechť pk je pravděpodobnost, že se částice vrátí do počátku v čase k.
Pak:
(i) Jestliže ∞
i=1 pk konverguje, pak q = P(vrátí se do počátku v čase t > 0) < 1.
(ii) Jestliže ∞
i=1 pk diverguje, pak q = P(vrátí se do počátku v čase t > 0) = 1.
Důkaz:
(i) Je - li q < 1, pak podle předchozího lemmatu je počet návratů do počátku Z
s pravděpodobností 1 konečný, tj. P(Z = ∞) = 0.
E(Z) = ∞
k=0 kuk = ∞
k=0 kqk
(1 − q) =
/ ∞
k=0 qk
= 1
1−q
, ∞
k=1 kqk−1
= 1
(1−q)2 ⇒ ∞
k=0 kqk
= q
(1−q)2 /
= (1 − q) q
(1−q)2 = q
(1−q)
< ∞
Pro ∀j definujeme náhodnou veličinu
Zj =
0, pokud částice není v počátku v čase j,
1, pokud částice je v počátku v čase j.
Z = ∞
j=0 Zj
E(Z) = ∞
j=0 E(Zj) = ∞
j=0 pj < ∞
11
(ii) Nechť q = 1. Pro libovolné pevné k ∈ N definujme náhodnou veličinu
Zk =
k, pokud se částice vrátila nejméně k×,
r, pokud se částice vrátila r×, kde r ≤ k.
Z předchozího lemmatu víme, že Zk = k s pravděpodobností rovnou 1.
Zk ≤ ∞
j=0 Zj.
k = E(Zk) ≤ E( ∞
j=0 Zj) = ∞
j=0 pj, ale k je libovolné, tedy ∞
j=0 pj diverguje.
Lemma 1.2.6. Pro x ∈ A platí:
|xj|2
≥ 1 − cos xj ≥
|xj|2
4
.
Důkaz: cos xj − (1 −
x2
j
2
) ) = ∞
n=2
(−x2
j )n
2n!
) ≤ x2
j
∞
n=2
x2n−2
j
2n!
) ≤
≤ x2
j
∞
n=1
1
102n = x2
j
1
99
≤ x2
j
1
4
⇒ −
−x2
j
4
≤ 1 − cos xj −
x2
j
2
≤
x2
j
4
⇒
x2
j
4
≤ 1 − cos xj ≤ 3
4
x2
j ≤ x2
j
Důkaz: Pólyovy věty: Označme k(j) polohu částice v čase t = j. Chceme zjistit,
zda ∞
k=0 pk konverguje nebo diverguje. Chceme spočítat pj = P(k(j) = 0).
Uvažujme funkci fj(x) : Rn
→ C, fj(x) = r∈Zm P(k(j) = r)e−ir·x
= E(e−ik(j)·x
).
fj(x) je dána jako součet Fourierovy řady (analogie charakteristické funkce).
Máme cr = ˆf(r) = P(k(j) = r) pro r ∈ Zm
.
fj(x) = E(eik(j)·x
) = E(ei j
q=1 s(q)·x
), kde s(q) je q-tý krok, tj. s(q) = k(q)−k(q −1),
s(q) jsou nezávislé, stejně rozdělené, tedy i eis(q)
jsou nezávislé, a tedy
E(ei j
q=1 s(q)·x
) = E( j
q=1 eis(q)·x
) = j
q=1 E(eis(q)·x
) = j
q=1 E(eis(1)·x
) =
= (E(eis(1)·x
))j
= (f1(x))j
.
Máme obecně P(k(j) = r) = ˆfj(r) = 1
(2π)m [0,2π]m fj(x)e−ir·x
dx,
speciálně pro r = 0: P(k(j) = 0) = 1
(2π)m [0,2π]m fj(x)dx = 1
(2π)m [0,2π]m f1(x)j
dx.
Dále máme ∞
j=0 pj = ∞
j=0 [0,2π]m
1
(2π)m f1(x)j
dx = 1
(2π)m [0,2π]m
dx
1−f1(x)
.
Spočítáme f1(x):
s(1) může být (±1, 0, . . . , 0), (0, ±1, . . . , 0), . . ., (0, . . . , 0, ±1), pravděpodobnost
každé možnosti je 1
2m
, tedy f1(x) = 1
2m
(eix1
+e−ix1
+. . .+eixm
+e−ixm
) = 1
m
m
j=1 cos xj,
kde cos xj = 1 −
x2
j
2
+
x4
j
4
− . . .
Je-li |xj| ≥ 1
10
, pak cos xj ≤ 1 −
x2
j
2
, a tedy je-li A = x ∈ [0, 2π]m
, x 1 < 1
10
,
kde x 1 = m
j=1 |xj|.
Pak pro x /∈ A platí f1(x) ≤ 1 − 1
200
, a tedy x/∈A
dx
1−f1(x)
≤ 1
1
200
(2π)m
= 200(2π)m
.
Tedy konvergence závisí jen na konvergenci x∈A
dx
1−f1(x)
.
Označme x 2
= m
j=1 x2
j .
Sečtením přes j dostaneme x 2
4
≤ m − m
j=1 cos xj ≤ x 2
12
⇒ x 2
4m
≤ 1 −
1
m
m
j=1
cos xj
=f1(x)
≤ x 2
m
.
Tedy konvergence integrálu x∈A
dx
1−f1(x)
je ekvivalentní konvergenci integrálu
x∈A
1
x 2 .
V polárních souřadnicích: r = x
τ
0
1
r2 rm−1
dr =
τ
0
rm−3
dr konverguje ⇔ m − 3 > −1 ⇔ m > 2.
Tedy pro m > 2 je P < 1 a pro m = 1, 2 je P = 1.
13
Kapitola 2
Diskrétní fourierova transformace
Motivace
1. Fourierovy řady
rozvoj 2π-periodické funkce do báze eikx
, kde k ∈ Z
2π-periodická funkce ↔ funkce na T = {z ∈ C, z = 1}
g(x) ↔ g(eikx
)
T je grupa
- multiplikativní: eix
· eiy
= ei(x+y)
- aditivní: sčítáme úhly
eikx
je charakter grupy T, tj. eikx
: T → C, eikx
→ eikx
2. Fourierova transformace
rozvoj funkcí f : R → C do báze eiξx
, kde ξ ∈ R
R je grupa s operací +
eiξx
je charakter grupy R
3. Diskrétní fourierova transformace
Uvažujme konečnou grupu G řádu N. G má dvě realizace:
(i) multiplikativní: grupa N-tých odmocnin z 1
ω = ei 2π
N . . . primitivní N
√
1
G = 1, ω, ω2
, . . . , ωN−1
(ii) aditivní: grupa zbytkových tříd při dělení N
G = {0, 1, 2, . . . , N − 1}
Uvažujme prostor funkcí na G:
L2
(G) = {f : G → C} .
14
L2
(G) je konečnědimenzionální vektorový prostor se skalárním součinem
f, g =
1
N x inG
f(x)¯g(x), f, g ∈ L2
(G).
Skalární součin indukuje normu
f = f, g 1/2
a metriku
ρ(f, g) = f − g .
Platí Cauchy - Schvartzova nerovnost
| f, g | ≤ f g
a Trojúhelníková nerovnost
f + g ≤ f + g .
Je-li f, g = 0, řekneme, že funkce f, g jsou ortogonální.
Lemma 2.0.7. Jsou-li v1, . . . , vm ortogonální funkce a v = m
j=1 ajvj, pak
aj =
v, vj
vj, vj
.
Důkaz: v, vj = m
k=1 akvk, vj = m
k=1 ak vk, vj = aj vj, vj
Definice 2.0.8. Standartní bází L2
(G) je δ-funkce: pro i = 0, 1, . . . , N − 1 položme
δi(j) = 1 pro j = i a δi(j) = 0 pro j = i.
Lemma 2.0.9. δ-funkce tvoří ortogonální bázi L2
(G).
Důkaz: δi, δj = 1
N k δi(k)¯δj(k) =
0 pro j = i,
1
N
pro j = i.
Každou funkci f ∈ L2
(G) lze tedy psát ve tvaru
f(x) =
N−1
j=0
f(j)δj(x),
kde f(j) =
f,δj
δj,δj
= N f, δj .
Prostor L2
(G) je izomorfní prostoru Cn
se standartním skalárním součinem, zobrazení
T : L2
(G) → Cn
je dáno vztahem
T(f) =
1
√
N
(f(0), f(1), . . . , f(N − 1)).
15
2.1 Cyklická konvoluce
Pro f, g ∈ L2
(G) definujeme
f ∗ g(x) =
1
N y∈G
f(y)g(x − y)
pro ∀x ∈ G.
Lemma 2.1.1.
δi ∗ δj(x) =
1
N
δi+j(x)
Důkaz: δi ∗ δj(x) = 1
N y∈G δi(y)δj(x − y) =
1
N
pro x = i + j,
0 jinak.
Příklad 2.1.2. N = 7, f(x) = δ0(x) + δ1(x) + δ2(x), g(x) = 1
2
f(x), f ∗ g(x) =?
f ∗ g(0) = 1
7 y∈{0,...,6} f(y)g(0 − y) = 1
7
· 1
2
= 1
14
f ∗ g(1) = 1
7 y∈{0,...,6} f(y)g(1 − y) = 1
7
· 1 = 1
7
f ∗ g(2) = 1
7 y∈{0,...,6} f(y)g(2 − y) = 1
7
· 3
2
= 3
14
f ∗ g(3) = 1
7 y∈{0,...,6} f(y)g(3 − y) = 1
7
· 1 = 1
7
f ∗ g(4) = 1
7 y∈{0,...,6} f(y)g(−3 − y) = 1
7
· 1
2
= 1
14
f ∗ g(5) = 1
7 y∈{0,...,6} f(y)g(−2 − y) = 1
7
· 0 = 0
f ∗ g(6) = 1
7 y∈{0,...,6} f(y)g(−1 − y) = 1
7
· 0 = 0
Definice 2.1.3. Pro m = 0, 1, . . . , N − 1 definujme funkci
em(j) = e
2πijm
N = (e
2πij
N )m
= (ωj
)m
= ωjm
.
Tedy em(j) je m-tá odmocnina, diskrétní analogie exponenciály.
em jsou charaktery grupy G, tvoří grupu vzhledem k násobení:
em(j)en(j) = em+n(j).
2.2 Diskrétní fourierova transformace
Definice 2.2.1. Nechť f ∈ L2
(G). Definujme diskrétní fourierovu transformaci
předpisem
ˆf(j) = (f, ej) =
1
N
N−1
m=0
f(m)ω−mj
16
pro j = 0, 1, . . . , N − 1.
Lemma 2.2.2. Funkce em, m = 0, 1, . . . , N − 1, tvoří ortonormální bázi prostoru
L2
(G).
Důkaz:
(i) em, em = 1
N
N−1
j=0 em(j)ˆem(j) = 1
N
N−1
j=0 (ωj
)m
(ωj
)m
= 1
N
· N = 1
(ii) em, en = 1
N
N−1
j=0 em(j)ˆen(j) = 1
N
N−1
j=0 (ωj
)m
(ωj
)n
= 1
N
N−1
j=0 (ωm−n
)j
=
= 1
N
· 1−(ωm−n)N
1−ωm−n = 1
N
1−1
1−ωm−n = 0
Věta 2.2.3. (o inverzní transformaci) Je-li f ∈ L2
(G), pak
f =
N−1
m=0
ˆf(j)ej.
Důkaz: ej tvoří ortonormální bázi, tedy f = N−1
j=0 ajej
⇒ aj = (f, ej) ⇒ (f, ej) = ( N−1
k=0 akek, ej) = aj
Důsledek 2.2.4. Diskrétní fourierová transformace je lineární zobrazení, které je
injektivní a surjektivní.
Lemma 2.2.5. (Parsevalova rovnost)
f, f =
N−1
j=0
| f, ej |2
Důkaz: N−1
k=0 akek, N−1
l=0 alel = N−1
k=0
N−1
l=0 ak¯al ek, el = N−1
k=0 ak¯ak · 1 =
= N−1
k=0 |ak|2
= N−1
j=0 | f, ej |2
Příklad 2.2.6. Diskrétní fourierová transformace konkrétních funkcí
(i) konstanta f(j) ≡ 1 pro ∀j ∈ G
ˆf(m) = (f, em) = 1
N
N−1
j=0 f(j)ˆωjm
= 1
N
N−1
j=0 1 · ω−jm
= 1−(ω−m)N
1−ω−m = 0 pro m = 0
ˆf(0) = 1
N
N−1
j=0 1 = 1
N
· N = 1
⇒ ˆ(1) = δ0
(ii) f(j) = ek(j) = e
2πijk
N
ˆf(m) = (f, em) = (ek(j), em) =
1 pro m = k,
0 jinak.
⇒ ˆ(ek) = δk
(iii) f(j) = δk(j)
17
ˆf(m) = (f, em) = 1
N
N−1
j=0 δk(j)e
−2πijm
N = 1
N
e
−2πijk
N = 1
N
¯ek(m) = 1
N
ek(−m)
⇒ ˆ(δk) = 1
N
¯ek
(iv) fj = 1
2
(δ1 + δ−1)(j)
ˆf(m) = 1
2
ˆδ1(m) + 1
2
ˆδ−1(m) = 1
2N
¯e1(m) + 1
2N
¯e−1(m) = 1
2N
(e
−2πim
N + e
2πim
N ) =
= 1
2N
(2 cos(2πm
N
)) = 1
N
cos(2πm
N
)
Věta 2.2.7. Diskrétní fourierová transformace převádí konvoluci na násobení, tedy
ˆ(f ∗ g)(j) = ˆf(j)ˆg(j)
.
Důkaz: (f ∗ g)(y) = 1
N
N−1
k=0 f(x)g(y − x)
ˆ(f ∗ g)(y) = (f ∗ g)(y), ej(y) = 1
N
N−1
y=0 (f ∗ g)(y)ej(y) =
= 1
N2
N−1
y=0
N−1
k=0 f(x)g(y − x)ωjy
= 1
N2
N−1
k=0
N−1
y=0 f(x)g(y − x)ωjx
ωj(y−x)
=
= 1
N
N−1
k=0 f(x)ωjx
· N−1
y=0 g(y − x)ωj(y−x)
= ˆf(j)ˆg(j)
Poznámka. Konvoluce pro funkce na R nemá jednotku, ale na L2
(G) jednotku
má.
Lemma 2.2.8. Je-li D(r) = 0 pro r = 0 a D(0) = N (tj. D = Nδ0), pak f ∗D(x) =
f(x) pro ∀f ∈ L2
(G), tj. funkce D je jednotkou na L2
(G) vzhledem ke konvoluci.
Důkaz: přímým výpočtem:
f ∗ D(x) = f(x) = 1
N y∈G f(y) D(x − y)
=



N pro y = x,
0 jinak.
= 1
N
· Nf(x) = f(x)
Lemma 2.2.9. Nechť N ≥ 2. Pak e0, e1 = 0, ale e0 ∗e1 = 0, tj. v L2
(G) jsou dělitelé
nuly (není to těleso).
Důkaz: Nechť f = e0 ∗ e1. Pak ˆf(j) = ˆe0(j)
δ0
ˆe1(j)
δ1
=



1 · 0 pro j = 0,
0 · 1 pro j = 1,
0 · 0 jinak.
⇒ ˆf(j) ≡ 0 ⇒ f(x) ≡ 0
2.3 Další vlastnosti diskrétní Fourierovy transfor-
mace
2.3.1 Posunutí
Nechť
fk(j) = f(j − k).
18
Posunutí lze napsat pomocí konvoluce s δ-funkcí:
δk ∗ f(j) = 1
N
N−1
i=0 δk(i)f(j − i) = 1
N
f(j − k)
⇒ f(j − k) = (Nδk) ∗ f(j) ⇒
ˆfk(j) = ˆfj · N ·
1
N
· ek(−j) = ˆf(j)ω−jk
Tedy koeficienty se otočí a absolutní hodnota se zachová.
Speciálně posun o půl periody: k = N
2
pro N sudé
ω−k
= ω−N
2 = −1 ⇒ ˆfk(j) = (−1)j ˆf(j)
2.3.2 Modulace (frekvenční posun)
Nechť f ∈ L2
(G). Označme
gk(j) = f(j)e
2πijk
N .
k . . . nosná frekvence
f . . . signál
gk . . . modulovaný signál
ˆgk(m) =
1
N
N
j=1
f(j)ω−mj
ωkj
=
1
N
N
j=1
f(j)ω−(m−k)j
= ˆf(m − k)
2.4 Transformace sumy a diference
Definice 2.4.1. Nechť f ∈ L2
(G). Řekneme, že g je suma f ⇔
g(j) = f(j) + f(j + 1).
Definice 2.4.2. Podle transformace posunutí dostaneme diskrétní Fourierovu transformaci
sumy
ˆg(m) = (1 + ωm
) ˆf(m).
Poznámka. Pro m malé je 1 + ωm
velké.
Definice 2.4.3. Nechť f ∈ L2
(G). Řekneme, že g je diference f ⇔
g(j) = f(j) − f(j + 1).
19
Definice 2.4.4. Diskrétní Fourierovu transformaci diference definujeme
ˆg(m) = (1 − ωm
) ˆf(m).
2.5 Maticová reprezentace diskrétní Fourierovy
transformace
Ve standartní bázi tvořené δ-funkcemi je matice diskrétní Fourierovy transformace
obrazy δ0, δ1, . . . do sloupců:
δj →
1
N
ej(−m) =
1
N
e
2πi
N
(−jm)
(Ajm)N
jm=1, Ajm = 1
N
ω−(j−1)(m−1)
Příklad 2.5.1.
• N = 2 ⇒ A =
1
2
1
2
1
2
−1
2
• N = 4 ⇒ A =




1
4
1
4
1
4
1
4
1
4
− i
4
−1
4
i
4
1
4
−1
4
1
4
−1
4
1
4
i
4
−1
4
− i
4




2.6 Symetrická diskrétní Fourierova transformace
Analýza digitálního signálu
signál . . . posloupnost reálných čísel f0, f1, . . . , fN−1
pre-procesing of data
post-procesing of data
(i) reálná diskrétní Fourierova transformace
(ii) sinová diskrétní Fourierova transformace (liché funkce)
(iii) cosinová diskrétní Fourierova transformace (sudé funkce)
20
2.6.1 Reálná diskrétní Fourierova transformace
Uvažujme reálnou funkci f : G → R. Pak
ˆf(N − k) =
1
N
N−1
j=0
f(j)ω(N−k)j =
1
N
N−1
j=0
f(j) · ωkj = ˆf(k).
Explicitní tvar diskrétní Fourierova transformace:
ˆf(k) = 1
N
N−1
j=0 f(j)e−2πijk
N = 1
N
N−1
j=0 f(j) cos 2πjk
N
+ i sin 2πjk
N
Ze symetrie víme, že stačí spočítat ˆf(k) pro 0 ≤ k ≤ N
2
, neboť ˆf(N − k) = ˆf(k).
Definice 2.6.1. Reálná uspořádaná N-tice ˆf(0), Re ˆf(1), Im ˆf(1), . . . , ˆf(N
2
) se nazývá
Reálná diskrétní Fourierova transformace funkce f.
Máme
ˆf(0) = ˆf(N) = ˆf(0) ⇒ ˆf(0) je reálná
ˆf(N
2
) = ˆf(N − N
2
) = ˆf(N
2
) ⇒ ˆf(N
2
) je reálná
Máme
Re ˆf(k) = 1
N
N−1
j=0 f(j) cos 2πjk
N
Im ˆf(k) = 1
N
N−1
j=0 f(j)i sin 2πjk
N
2.6.2 Inverzní reálná diskrétní Fourierova transformace
Lemma 2.6.2. Pro f(x) ∈ L2
(G) s reálnými hodnotami platí
f(j) =
1
2
a0 +
N
2
−1
m=1
am cos
2πjm
N
+ bm sin
2πjm
N
+
1
2
aN
2
cos(jπ),
kde a0 = 2 ˆf(0), am = 2Re ˆf(m), bm = −2Im ˆf(m), aN
2
= 2 ˆf(N
2
).
Důkaz: f(j) = N−1
m=0
ˆf(m)e
2πijm
N =
= ˆf(0) +
N
2
−1
m=1
ˆf(m)e
2πijm
N + ˆf(−m)e−2πijm
N + ˆf(N
2
) cos(jπ) =
= ˆf(0) +
N
2
−1
m=1 2Re( ˆf(m)e
2πijm
N ) + ˆf(N
2
) cos(jπ) =
= ˆf(0) +
N
2
−1
m=1 2Re( ˆf(m) cos 2πjm
N
+ i sin 2πjm
N
) + ˆf(N
2
) cos(jπ) =
= ˆf(0) +
N
2
−1
m=1 2Re( ˆf(m) cos 2πjm
N
) − 2Im( ˆf(m) sin 2πjm
N
) + ˆf(N
2
) cos(jπ)
21
2.6.3 Diskrétní sinová a cosinová Fourierova transformace
Nechť f : G → R je sudá funkce, tedy f(j) = f(N − j) neboli f(−j) = f(j). Nechť
N je sudé. Pak
ˆf(m) = 1
N
N−1
j=0 f(j)e−2πijm
N = 1
N
f(0) + 1
N
N
2
−1
j=1 f(j) e−2πijm
N + e
2πijm
N
2 cos 2πijm
N
+
+ 1
N
f(N
2
) cos(mπ)
(−1)m
= 1
N
f(0) + 2
N
N
2
−1
j=1 f(j) cos 2πijm
N
+ 1
N
f(N
2
) cos(Mπ)
Definice 2.6.3. Nechť f ∈ L2
(G). Funkce
ˆfc(m) =
1
N
f(0) +
2
N
N
2
−1
j=1
f(j) cos
2πijm
N
+
1
N
f(
N
2
) cos(mπ)
se nazývá diskrétní cosinová transformace funkce f.
Lemma 2.6.4. Pro sudou funkci f platí:
f(j) = ˆfc(0) + 2
N
2
−1
m=1
ˆfc(m) cos
2πijm
N
+ ˆfc(
N
2
) cos(jπ).
Důkaz: přímým výpočtem.
Analogicky, nechť f : G → R je lichá funkce, tedy f(j) = −f(N − j) neboli
f(−j) = −f(j).
Lemma 2.6.5. Je-li f(x) lichá funkce, pak ˆf(m) je taky lichá funkce.
Důkaz: ˆf(N − m) = 1
N
N−1
j=0 f(j)e−
2πij(N−m)
N =
= 1
N
N
2
−1
j=1 f(j) e−
2πij(N−m)
N − e
2πij(N−m)
N =
= − 1
N
N
2
−1
j=1 f(j) e−2πijm
N − e
2πijm
N = − ˆf(m)
Je-li f(x) lichá a reálná funkce, pak
ˆf(m) = 1
N
f(0) + 1
N
N
2
−1
j=1 f(j) e−2πijm
N + e−
2πi(N−j)m
N
−2i sin 2πjm
N
+ 1
N
f(N
2
) cos(mπ) =
= −i 2
N
N
2
−1
j=1 f(j) sin 2πjm
N
.
22
Definice 2.6.6. Nechť f ∈ L2
(G). Funkce
ˆfs(m) =
2
N
N
2
−1
j=1
f(j) sin
2πjm
N
se nazývá diskrétní sinová transformace funkce f.
Lemma 2.6.7. Pro lichou funkci f platí:
f(j) = 2
N
2
−1
m=1
ˆfs(m) sin
2πjm
N
.
Důkaz: přímým výpočtem.
2.6.4 Aplikace diskrétní Fourierovy transformace
• řešení diferenčních rovnic (okrajových úloh) → analogie řešení diferenciálních
rovnic pomocí Fourierovy transformace
Okrajová úloha pro diferenční rovnici 2. řádu:
Uvažujme posloupnost u0, . . . , uM , zadáváme u0 = A, uM = B. Použitím
diskrétní Fourierovy transformace přejde diferenční rovnice na algebraickou
rovnici. Po jejím vyřešení se najde zpětná transformace řešení.
• v geometrii
Uvažujme f ∈ L2
(G). Hodnoty f(0), . . . , f(N −1) chápeme jako vrcholy mnohoúhelníka
Π v C, tj. Π = {f(0), . . . , f(N − 1)}.
Nechť Df(j) je střed j-té strany (f(j − 1), f(j)), tedy
Df(j) =
1
2
(f(j − 1) + f(j)) =
N
2
(δ0 + δ1) ∗ f(j).
Definujme odvozený N-úhelník Π = {Df(0), . . . , Df(N − 1)} a dále
Π = (Π ) , . . . , Π(r)
= (Π(r−1)
) .
Věta 2.6.8. Uvažujme N-úhelník Π v C, tj. Π = {f(0), . . . , f(N − 1)} v komplexní
rovině. Nechť Df(j) je střed j-té strany a Π = {Df(0), . . . , Df(N − 1)}
je odvozený N-úhelník a nechť Π(r)
= (Π(r−1)
) . Pak pro r → ∞ Π(r)
konverguje
k těžišti Π, tedy k bodu P = 1
N
(f(0) + . . . + f(N − 1)).
23
Důkaz: búno Nechť těžiště P je v počátku, tedy 1
N
N−1
j=0 f(j) = 0.
Víme, že Df(j) = N
2
(δ0 + δ1) ∗ f(j) = d ∗ f(j), kde d = N
2
(δ0 + δ1),
tedy D2
f = d ∗ (d ∗ f(j)) atd. Nás zajímá limr→∞ d ∗ . . . ∗ d
r×
∗f(j).
Víme, že ˆ(d ∗ f)(j) = ˆd(j) · ˆf(j) = N
2
(ˆδ0 + ˆδ1) · ˆf(j) = 1
2
(1 + e−2πij
N ) · ˆf(j)
⇒ ˆ(d ∗ . . . ∗ d) = ( ˆd)r
, ˆd(j) = 1
2
(1 + e−2πij
N )
⇒ limr→∞( ˆd(j))r
=
0 pro j = 0,
1 pro j = 0
⇒ limr→∞( ˆd(j))r ˆf(j) = 0, neboť 1
N
(f(0) + . . . + f(N − 1)) = 0
⇒ limr→∞ d ∗ . . . ∗ d
r×
∗f(j) = 0, tedy těžiště Π.
24
Kapitola 3
Z-transformace
Fourierovy řady: funkce → posloupnost
Fourierova transformace: funkce → funkce
Z-transformace: posloupnost → funkce
Definice 3.0.9. Nechť un ∈ C, n = 0, 1, 2, . . . je posloupnost. Z-transformaci posloupnosti
un definujme
Z {un} = U(z) =
∞
n=0
unz−n
,
kde z je komplexní proměnná, pro kterou řada konverguje.
Příklad 3.0.10.
• konstantní posloupnost un = 1 pro n = 0, 1, 2, . . .
U(z) = ∞
n=0 z−n
= 1
1− 1
z
= z
z−1
konverguje ⇔ 1
z
< 1 ⇔ |z| > 1
• geometrická posloupnost un = an
, a ∈ C
U(z) = ∞
n=0 an
z−n
= ∞
n=0(a
z
)n
= 1
1−a
z
= z
z−a
konverguje ⇔ a
z
< 1 ⇔ |z| > |a|
• sinová a cosinová posloupnost
un = cos nθ = einθ+e−inθ
2
z předchozího pro a = ein
nebo a = e−in
dostaneme
Z(cos nθ) = Z(einθ+e−inθ
2
) = 1
2
Z(einθ
) + 1
2
Z(e−inθ
) = 1
2
( z
z−ein + z
z−e−in ) =
= 1
2
2z2−2z cos θ
z2−2z cos θ+1
= z−cos θ
z−2 cos θ+ 1
z
un = sin nθ
analogicky:
Z(sin nθ) = sin θ
z−2 cos θ+ 1
z
25
3.1 Inverzní Z-transformace
Definice 3.1.1. Inverzní Z-transformaci definujme
un = Z {U(z)}n .
Příklad 3.1.2.
• základní parciální zlomek: U(z) = 1
z−a
1
z−a
= 1
z
·
1
1 − a
z
tvar 1
1−x
= 1
z
∞
n=0(a
z
)n
= ∞
n=0
an
zn+1 = ∞
n=1
an−1
zn
⇒ un =
0 pro n = 0,
an−1
pro n > 0.
• inverze pomocí parciálních zlomků: U(z) = z+6
z2−4
= z+6
(z−2)(z+2)
= 2
z−2
− 1
z+2
Z−1
( z+6
z2−4
) = Z−1
( 2
z−2
) − Z−1
( 1
z+2
)
un =
0 pro n = 0,
2 · 2n−1
− 1 · (−2)n−1
= 2n
+ (−2)n
pro n > 0.
• dlouhé dělení: U(z) = z2+2z
z2−2z+1
(z2
+ 2z) : (z2
− 2z + 1) = 1 + 4
z
+ 7
z2 + 10
z3 + . . .
⇒ un = 3n + 1
3.2 Vlastnosti Z-transformace
1. linearita
Z {aun + bvn} = aZ {un} + bZ {vn}
2. transformace posunu
Nechť {un} označuje posloupnost {u1, u2, . . .}. Pak
Z {un+1} = −zu0 + zU(z),
kde U(z) je Z-transformace původní posloupnosti {un}.
Je totiž: Z {un+1} = ∞
n=0 un+1z−n
= z ∞
n=0 un+1z−n−1
= z ∞
n=1 unz−n
=
= z(−u0 + ∞
n=0 unz−n
) = −zu0 + zU(z)
Pro posunutí o 2 doleva dostaneme
Z {un+2} = −zu1 + zZ {un+1} = −zu1 + z(−zu0 + zU(z)) =
= −zu1 − z2
u0 + z2
U(z).
26
3. derivace obrazu
Existuje-li Z {un} = U(z), pak existuje také Z {nun} a platí vztah
Z {nun} = −z
d
dz
U(z).
Je totiž: −z d
dz
U(z) = −z d
dz
∞
n=0 unz−n
= −z ∞
n=0
d
dz
(unz−n
) =
= −z ∞
n=0(−nunz−n−1
) = ∞
n=0 nunz−n
= Z {nun}
Příklad 3.2.1. Vypočtěte Z-transformaci posloupnosti un = n.
Z {n · 1} = −z d
dz
U(z) = −z d
dz
( z
z−1
) = z
(z−1)2
Z {n2
} = Z {n · n} = −z d
dz
( z
(z−1)2 ) = z(z+1)
(z−1)3
Z {n3
} = z(z2+4z+1)
(z−1)4
Poznámka. Víme (a)n Z
→ z
z−a
. Označme {an−1
} posloupnost {0, 1, a, a2
, . . .}.
∞
n=1 an−1
z−n
= z−1 ∞
n=0 an
z−n
= z−1
· Z {an
} = 1
z−a
. Tedy
Z an−1
=
1
z − a
.
3.3 Řešení diferenčních rovnic pomocí
Z-transformace
Příklad 3.3.1. Řešte diferenční rovnici un+2 = 2un+1 + 3un s počátečními podmínkami
u0 = 1, u1 = 0.
1. Řešení je posloupnost {un}. Její Z-transformaci označme U(z). Přetransformujeme
rovnici pomocí pravidla o transformaci posunu:
Z {un+2} = 2Z {un+1} + 3Z {un} = 2(−zu0 + z(U(z))) + 3U(z) = −z2
u0−
−zu1 + z2
U(z)
2. Vypočteme U(z):
U(z) = −2z+z2
z2−2z−3
= 1 +
3
4
z−3
−
3
4
z+1
3. Najdeme Z−1
{un}:
un =
1 pro n = 0,
3
4
· 3n−1
− 3
4
· (−1)n−1
pro n > 0
27
Příklad 3.3.2. Řešte diferenční rovnici un+2 + 2un = 0 s počátečními podmínkami
u0 = 1, u1 = 1
Z {un+2} + 2Z {un} = −z2
u0 − zu1 + z2
U(z) + 2U(z) = 0
U(z) = z2u0+zu1
z2+2
= z2+z
z2+2
= 1 + z−2
2+z2 = 1 +
1
2
+
√
2i
z−
√
2i
+
1
2
−
√
2i
z+
√
2i
un =
1 pro n = 0,
(1
2
+
√
2i) · (
√
2i)n−1
+ (1
2
+
√
2i) · (−
√
2i)n−1
pro n > 0
28
Kapitola 4
Laplaceova transformace
- spojitá analogie Z-transformace: Místo posloupnosti s kladnými indexy uvažujeme
funkce pro kladné hodnoty t.
Definice 4.0.3. Pro funkci f(t) : 0, ∞ → C definujme Laplaceovu transformaci
F(s) =
∞
0
f(t)e−st
dt
pro ty hodnoty s, pro které integrál konverguje.
Poznámka. Fourier: ˆf(ξ) =
∞
−∞
f(t)e−iξt
dt, e−iξt
= 1
e−st
→ 0 rychle pro t → ∞
Laplaceova transformace existuje pro daleko více funkcí něž Fourierova transformace.
Označení:
F(s) = L(f)
inverzní transformace: f(t) = L−1
(f)
Příklad 4.0.4.
• Pro f(t) = 1, t > 0, máme
F(s) =
∞
0
e−st
dt = −1
s
e−st ∞
0
= 1
s
pro s > 0
• Pro f(t) = eat
, t > 0, a ∈ R máme
F(s) =
∞
0
eat
e−st
dt =
∞
0
e(a−s)t
dt = 1
a−s
e(a−s)t ∞
0
= 1
s−a
pro s > a
• Pro f(t) = tn
, t > 0, máme F(s) = n!
sn+1 pro s > 0
indukcí: pro n = 0 máme f(t) = 1 a L(tn
) = 1
s
L(tn+1
) =
∞
0
tn+1
e−st
dt =
/u = tn+1
, v = e−st
, u = (n + 1)tn
, v = −1
s
e−st
/
= −tn+1
· 1
s
e−st ∞
0
+
∞
0
(n + 1)tn 1
s
e−st
dt = n+1
s
· L(tn
) = n+1
s
· n!
sn+1 = (n+1)!
sn+2
29
Lemma 4.0.5. Platí:
L(ta
) =
Γ(a + 1)
sa+1
,
kde Γ je Gamma funkce Γ =
∞
0
xn−1
e−x
dx.
Důkaz: L(ta
) =
∞
0
ta
e−st
dt =
/st = x ⇒ t = x
s
⇒ sdt = dx ⇒ dt = 1
s
dx/
=
∞
0
xa
sa
1
s
e−x
dx = 1
sa+1
∞
0
xa
e−x
dx = 1
sa+1 Γ(a + 1).
Poznámka. L(eat
) = 1
s−a
platí i pro a ∈ C, tedy
L(eiωt
) = 1
s−iω
= s+iω
s2+ω2 = s
s2+ω2 + i ω
s2+ω2 ,
tedy L(cos ωt) = s
s2+ω2 a L(sin ωt) = ω
s2+ω2 .
4.1 Existence Laplaceovy transformace
Věta 4.1.1. Nechť f(t) je po částech spojitá na 0, ∞) a platí odhad
|f(t)| ≤ M · eγt
pro nějaké konstanty M a γ. Pak Laplaceova transformace existuje pro všechna
s > γ.
Důkaz: Pro s > γ máme
|L(f)| =
∞
0
e−st
f(t)dt ≤
∞
0
|e−st
| |f(t)| dt ≤ M
∞
0
e−st
eγt
dt = M
∞
0
e(γ−s)t
dt <
< +∞,
protože
∞
0
e(γ−s)t
dt konverguje ⇔ γ − s < 0.
4.2 Laplaceova transformace derivace
Lemma 4.2.1. Nechť f(t) je spojitá pro t ≥ 0 a splňuje odhad |f(t)| ≤ M ·eγt
. Pak
L(f ) = s · L(f) − f(0).
Důkaz: L(f ) =
∞
0
e−st
f (t)dt =
/u = f , v = e−st
⇒ u = f, v = −se−st
/
= [fe−st
]
∞
0 −
∞
0
(−se−st
f(t))dt = 0 − f(0) + sL(f) = sL(f) − f(0)
Analogicky dostaneme
L(f ) = sL(f ) − f (0) = s2
L(f) − sf(0) − f (0)
30
a obecně
L(f(n)
) = sn
L(f) − sn−1
f(0) − sn−2
f (0) − . . . − f(n−1)
(0).
Příklad 4.2.2. Řešte diferenciální rovnici y − y = t, y(0) = 1, y (0) = 1.
1. Laplaceova transformace:
L(y) = Y
s2
Y − sy(0) − y (0) − Y = 1
s2
s2
Y − s − 1 − Y = 1
s2
2. Vypočteme Y :
Y (s2
− 1) = 1
s2 + s + 1 ⇒ Y = 1
s−1
+ 1
s2−1
− 1
s2
3. Zpětnou transformací dostaneme
y(t) = et
+ sin ht − t
4.3 Věty o posunu
Věta 4.3.1. (posun v proměnné s) Nechť F(s) = L(f), pak
L−1
(F(s − a)) = F(t)eat
neboli
F(s − a) = L(feat
).
Důkaz: L(feat
) =
∞
0
f(t)e−st
eat
dt =
∞
0
f(t)e−(s−a)t
dt = F(s − a)
Označení:
u(t) =
0 pro t < 0,
1 pro t ≥ 0
. . . Heavisideova fukce (1 krok v bodě 0)
u(t − a) . . . 1 krok v bodě a
Věta 4.3.2. (posun v proměnné t) Platí
L(F(t − a)u(t − a)) = F(s)e−as
neboli
L−1
(F(s)e−as
) = f(t − a)u(t − a).
31
Důkaz: L(F(t − a)u(t − a)) =
∞
0
f(t − a)e−st
u(t − a)dt =
∞
0
f(t − a)e−st
dt =
/x = t − a ⇒ dx = dt/
=
∞
0
f(x)e−s(x+a)
dx = e−sa ∞
0
f(x)e−sx
dx = e−sa
L(F(x))
Laplaceova transformace je vhodná pro nespojité vstupy, např. δ-funkce:
δa(x) =
0 pro x = a,
∞ pro x = a
. . . Diracova δ-funkce v bodě a ∈ R+
∞
−∞
f(x)δa(x)dx = f(a)
δ0 → 1
L(δa) =
∞
0
δa(t)e−st
dt = e−as
Příklad 4.3.3. Řešte harmonický oscilátor y + y + y = δ0, y(0) = y (0) = 0:
systém je nejprve v klidu, v čase t = 0 mu dáme ránu kladivem...
Y = L(y)
s2
y − s · 0 − 0 + sY − 0 + Y = 1
⇒ Y = 1
s2+s+1
= 1
(s+1
2
)2+3
4
= 2√
3
·
√
3
2
(s+1
2
)2+3
4
sin ωt = ω
t2+ω2
y = L−1
(y) = 2√
3
· sin
√
3
2
te−1
2
t
Věta 4.3.4. (Lerchova věta o jednoznačnosti) Nechť existují čísla a > γ (z odhadu
|f(t)| ≤ M · eγt
) a b tak, že
L(f)(a + ub) = 0
pro ∀n ∈ N. Pak
L(f) ≡ 0 a f ≡ 0.
Důkaz: pomocí Hausdorfovy věty o momentech:
f : 0, 1 → R, Mk =
1
0
f(x)dx . . . k-tý obecný moment
Mk = 0 pro ∀k = 0, 1, . . . ⇒ f(x) = 0
Označme α(t) = e−at
f(t).
Máme α(0) = 0 a limt→∞ α(t) = 0, neboť a > γ a α je spojitá
0 = Lf(a + ub) =
∞
0
f(t)e−at
e−ubt
dt =
∞
0
α(t)e−ubt
dt =
/u = e−bt
, du = −b · e−bt
dt, du
u
= −bdt,
t = −1
b
lg u, t = 0 ⇒ u = 1, t = ∞ ⇒ u = 0/
= −
1
0
β(u)un du
u
(−1
b
) = 1
b
1
0
β(u)un−1
du = Mn−1,
kde β(u) = α(−1
b
lg u) pro 0 < u < 1, β(0) = 0, β(1) = 1, β spojitá
⇒ podle Hausdorfovy věty Mn−1 = 0 pro ∀n ⇒ β(u) ≡ 0 ⇒ α ≡ 0 ⇒ f ≡ 0
V definici Laplaceovy transformace můžeme místo s ∈ R uvažovat z ∈ C:
F(z) =
∞
0
f(t)e−zt
dt
32
• pro reálnou hodnotu z → Laplaceova transformace
• pro ryze imaginární hodnotu z → Fourierova transformace f(t) dodefinovaná
f(t) ≡ 0 pro t < 0
z = iξ ⇒ F(iξ) =
∞
0
f(t)e−iξt
dt =
∞
−∞
f(t)e−iξt
dt = ˆf(ξ).
Platí-li odhad |f(t)| ≤ M · eγt
, pak F(z) je pro Re(z) > γ holomorfní.
Věta 4.3.5. (o lineární Laplaceově transformaci) Nechť f(t) je spojitá funkce na
R, f(t) = 0 pro t < 0, která splňuje odhad |f(t)| ≤ M · eγt
. Pak pro libovolné b > γ
a t ∈ 0, ∞) je
f(t) =
1
2π
∞
−∞
Lf(b + iξ)e(b+iξ)t
dξ.
Důkaz: Použijeme větu o inverzní Fourierově transformaci na funkci e−bt
f(t).
Máme f(t) = ebt
(f(t)e−bt
)ebt
· 1
2π
∞
−∞
ˆfe−bt(ξ)eiξt
dξ = 1
2π
∞
−∞
Lf(b + iξ)tdξ,
neboť Lf(b + iξ) =
ˆˆfe−bt(ξ) =
∞
−∞
f(t)e−bt
eiξt
dt =
∞
−∞
f(t)e−t(b+iξ)
dt.
33
Kapitola 5
Hartleyho transformace
Definice 5.0.6. Nechť h(x) ∈ L1
(R), tj.
∞
−∞
|h(x)| dx < ∞. Hartleyho transformace
funkce h(x) je definovaná vztahem
H(ξ) =
∞
−∞
h(x)cas (ξx) dx,
kde cas (x) = cos x + sin x.
Hartleyho transformace je čistě reálná transformace.
Definice 5.0.7. Inverzní Hartleyho transformace funkce H(x) je definovaná vzta-
hem
h(x) =
1
2π
∞
−∞
H(ξ)cas (ξx) dξ,
tedy H−1
= 1
2π
H.
5.1 Sudá a lichá část Hartleyho transformace
Sudá a lichá část Hartleyho transformace jsou dány vztahy
E(ξ) =
H(ξ) + H(−ξ)
2
=
∞
−∞
h(x) cos (ξx) dx
a
O(ξ) =
H(ξ) − H(−ξ)
2
=
∞
−∞
h(x) sin (ξx) dx,
tedy od Hartleyho transformace k Fourierově transformaci přejdeme vztahem
ˆf(ξ) = E(ξ) − iO(ξ).
Naopak, přechod od Fourierovy transformace k Hartleyho transformaci je dán vzta-
hem
H(ξ) = Re ˆf(ξ) − Im ˆf(ξ).
34
5.2 Diskrétní Hartleyho transformace
Definice 5.2.1. Diskrétní Hartleyho transformace posloupnosti hn, n = 0, . . . , N−1,
je posloupnost
Hk =
1
N
N−1
n=0
hncas
2πkn
N
.
Definice 5.2.2. Inverzní diskrétní Hartleyho transformace posloupnosti Hk, k =
0, . . . , N − 1, je posloupnost
hn =
N−1
k=0
hkcas
2πkn
N
.
Přechody mezi diskrétní Hartleyho transformací a diskrétní Fourierovou transformací
jsou analogické jako u spojité verze.
Poznámka. Platí ortonormální vztahy:
N−1
n=0
cas
2πkn
N
cas
2πjn
N
=
0 pro j = k,
N pro j = k.
35
Kapitola 6
Radonova transformace
- tomografie: rekonstrukce obrazu z projekcí
Motivace
Paprsek procházející homogenním tělesem
I0 . . . intenzita na počátku
I . . . intenzita na konci
Rychlost útlumu je přímo úměrná intenzitě:
I = −u · I ⇒ I = I0 · e−ux
, kde u je koeficient útlumu.
Pro těleso složené ze dvou částí je I = I0 · e− 2
i=1 uixi
.
Je-li těleso nehomogenní, u(x) je koeficient útlumu v bodě x, pak dostaneme
I = I0 · e− L u(x)dx
, kde L jsou přímky.
Obvykle u(x) odpovídá hustotě v bodě x.
Označení: x = (x1, x2) . . . souřadnice v R2
Nechť u(x1, x2) je hustota materiálu v bodě (x1, x2),
I = I0 · e− L u(x1,x2)ds
⇒ − lg
I
I0
=
L
u(x1, x2)ds.
Definice 6.0.3. Nechť u(x1, x2) je omezená, integrovatelná (ne nutně spojitá) funkce
definovaná v omezené oblasti D ⊆ R2
. Radonova transformace funkce u(x1, x2)
je funkce Ru proměnných (r, ω) ∈ R × S1(0), kde S1(0) = {x ∈ R2
/x2
1 + x2
2 = 1},
definovaná vztahem
Ru(r, ω) =
x×ω=r
u(x1, x2)ds,
kde x×ω je standartní skalární součin v R2
a ds je jednorozměrná Euklidovská míra
na přímce x × ω = r.
Příklad 6.0.4. Vypočtěte radonovu transformaci charakteristické funkce kruhu
o poloměru R:
u(x1, x2) =
1 pro x2
1 + x2
2 ≤ R2
,
0 pro x2
1 + x2
2 > R2
.
36
r > R ⇒ Ru(r, ω) = 0
r ≤ R ⇒ l
2
=
√
R2 − r2 = Ru(r, ω)
⇒ Ru(r, ω) =
2
√
R2 − r2 pro r ≤ R,
0 pro r > R.
6.1 Inverzní radonova transformace
Označme ˆRu(ρ, ω) jednodimenzionální Fourierovu transformaci funkce Ru(r, ω)
v proměnné r.
Věta 6.1.1. Nechť ω ∈ S1(0) a ρ ∈ R. Pak
ˆRu(ρ, ω) = ˆu(ξ1, ξ2) =
R2
u(x1, x2) · e−i(ξ1x1+ξ2x2)
dx1dx2,
kde (ξ1, ξ2) je vektor ρ · ω.
Důkaz: ˆu(ρ, ω) = R2 u(ξ1, ξ2) · e−i(ξ1x1+ξ2x2)
dx1dx2 =
=
∞
−∞ x·ω=r
u(ξ1, ξ2) · e−iρr
ds dr =
∞
−∞
e−iρr
x·ω=r
u(x)ds
Ru
dr = ˆRu(ρ, ω)
Tedy Fourierova transformace radonovy transformace v proměnné r je dvourozměrná
Fourierova transformace funkce u zúžené na přímku určenou vektorem v.
Označíme-li Ru(r, ω) = g(r, ω), F1 jednorozměrnou Fourierovu transformaci
v proměnné r a F2 dvourozměrnou Fourierovu transformaci v proměnné r, pak
u = F−1
2 (F1(g)) .
37
Kapitola 7
Jednotící pohled na Fourierovy
řady, Fourierovu transformaci a
diskrétní Fourierovu transformaci
s využitím zobecněných funkcí
7.1 Zobecněné funkce (distribuce)
s . . . prostor testovacích funkcí
s = C∞
0 (R) . . . prostor funkcí nekonečně hladkých s kompaktním nosičem
supp(f) = {x ∈ R/f(x) = 0} . . . nosič funkce f
Příklad 7.1.1.
• f(x) =
e− 1
x2
pro x > 0,
0 pro x ≤ 0
/∈ C∞
0 (R)
• g(x) =
f(1 − x2
) pro x ∈ (−1, 1) ,
0 jinak
∈ C∞
0 (R)
Definice 7.1.2. Spojitý lineární funkcionál
g : s → R
se nazývá distribuce. Je-li g distribuce, pak její hodnotu na testovací funkci ϕ ozna-
čujeme
g(ϕ) = g, ϕ .
38
Je-li f spojitá funkce na R, pak f přiřadíme jednoznačně definovanou distribuci,
kterou budeme označovat stejným písmenem, předpisem
g, ϕ =
∞
−∞
f(x)ϕ(x)dx.
Jsou-li f a g dvě různé spojité funkce, pak jim příslušející distribuce jsou také
různé:
Nechť x0 je takové, že f(x0) = g(x0). Předpokládejme, že f(x0) > g(x0). Ze spojitosti
plyne, že ∃ > 0 tak, že f(y) > g(y)∀y ∈ (x0 + , x0 − ).
Nechť ϕ ∈ C∞
0 (R) je taková, že supp(ϕ) ∈ (x0 + , x0 − )
⇒ f, ϕ =
∞
−∞
f(x)ϕ(x)dx =
x0+
x0−
f(x)ϕ(x)dx >
x0+
x0−
g(x)ϕ(x)dx =
=
∞
−∞
g(x)ϕ(x)dx = g, ϕ
⇒ f = g jako distribuce.
Příklad 7.1.3. Diracova δ-funkce v bodě a je distribuce δa taková, že δa, ϕ =
ϕ(a). Speciálně pro δ = δ0 je δ0, ϕ = ϕ(0).
Distribuce tvoří lineární prostor. Platí:
u1 + u2, ϕ = u1, ϕ + u2, ϕ .
Poznámka. Fyzikální motivace (kvantová teorie)
veličiny se neměří ”bodově”, ale jako výsledky experimentu
f . . . veličina (distribuce)
ϕ . . . testovací funkce (popisuje parametry pokusu)
f, ϕ . . . výsledek experimentu
7.2 Operace na distribucích
Nechť T je operátor, T : C∞
0 (R) → C∞
0 (R), ke kterému existuje adjungovaný operátor
T∗
, tj. takový, že Tf, g = f, T∗
g . Pak operátor T rozšíříme na prostor
distribucí předpisem
Tf, ϕ = f, T∗
ϕ .
Příklad 7.2.1. derivace T : C∞
0 (R) → C∞
0 (R), T = d
dx
pro f, g ∈ C∞
0 (R) :
Tf, g =
∞
−∞
f (x)g(x)dx = f(x)g(x)/∞
−∞ −
∞
−∞
f(x)g (x)dx = f, −Tg
⇒ T∗
= −T = − d
dx
Tedy pro distribuci u ∈ C∞
0 (R) definujeme derivaci vztahem
u , ϕ = − u, ϕ .
39
Příklad 7.2.2. Vypočtěte 1. a 2. derivaci funkce f(x) = |x| ve smyslu distribucí.
f (x) =



−1 pro x ∈ (−∞, 0) ,
1 pro x = 0,
1 pro x ∈ (0, ∞)
= sgn(x)
f , ϕ = − f, ϕ = −
∞
−∞
f(x)ϕ (x)dx = −
∞
−∞
sgn(x)ϕ (x)dx = −
0
−∞
ϕ (x)dx−
−
∞
0
ϕ (x)dx = ϕ(x)/∞
−∞ + (−ϕ(x))/∞
−∞ = 2ϕ(0)
⇒ f (x) = 2δ0
f (x) = 2δ0:
δ0, ϕ = − δ0, ϕ = −ϕ (0)
⇒ f (x) = −ϕ0
Příklad 7.2.3. Fourierova transformace T
ˆf(x) =
∞
−∞
f(ξ)e−iξx
dξ a f(x) = 1
2π
∞
−∞
ˆf(ξ)eiξx
dξ
Základní identita pro Fourierovu transformaci:
f(x), ˆg(x) =
∞
−∞
f(x)ˆg(x)dx =
∞
−∞
ˆf(x)g(x)dx = ˆf(x), g(x)
⇒ T∗
= T
Tedy pro distribuci u definujeme její Fourierovu transformaci předpisem
ˆu, ϕ = u, ˆϕ .
Příklad 7.2.4. Vypočtěte ˆf pro f(x) ≡ 1.
ˆ1, ϕ = 1, ˆϕ =
∞
−∞
1 ˆϕ(x)dx =
∞
−∞
ˆϕ(x)e−i0x
dx = ˆˆϕ(0) = 2πϕ(0)
⇒ ˆ1 = 2πδ0
Příklad 7.2.5. Vypočtěte ˆf pro f(x) = x.
ˆx, ϕ = x, ˆϕ =
∞
−∞
x ˆϕ(x)dx =
/f(x) = 1
2π
∞
−∞
ˆf(ξ)eiξx
dξ
⇒ f (x) = 1
2π
∞
−∞
iξ ˆf(ξ)eiξx
dξ
⇒ f (0) = 1
2π
∞
−∞
iξ ˆf(ξ)dξ/
= −2πi · ϕ (0) = −2πi · δ0
⇒ ˆx = 2πiδ0
7.3 Zobecněná Fourierova transformace
C∞
0 (R) . . . prostor testovacích funkcí
C∞
0 (R) ⊆ s . . . Schvartzův prostor (prostor rychle klesajících funkcí)
f ∈ s ⇔ f ∈ C∞
0 (R) a pro ∀k, l ∈ N : limx→±∞ xk
f(l)
(x) = 0
např. P(x) · e−a(x−x0)2
∈ s, a > 0, x0 ∈ R
40
Definice 7.3.1. Temperovaná distribuce je spojitý lineární funkcionál na s.
C∞
0 (R) ⊆ s ⇒ (C∞
0 (R)) ⊆ (s) , tj. temperovaná distribuce je distribuce.
Uvažujme operaci posunutí o a doprava: fa(x) = f(x − a)
Taf = fa
f, g ∈ C∞
0 (R) : Taf, g = f, T∗
a g
∞
−∞
f(x − a)g(x)dx = /x = x − a ⇒ x = x + a/ =
∞
−∞
f(x )g(x + a)dx
⇒ T∗
a = T−a
Definice 7.3.2. Posunutí distribuce: Je-li u distribuce, definujme u(x−a) předpisem
u(x − a), ϕ(x) = u(x), ϕ(x + a) .
Definice 7.3.3. Distribuce u je periodická s periodou p, jestliže u(x − p) = u(x) ve
smyslu distribucí, tj.
u(x − p), ϕ(x) = u(x), ϕ(x)
pro ϕ ∈ C∞
0 (R).
Poznámka. Funkce periodická na R nemůže patřit do L1
, nemá definovanou Fourierovu
transformaci.
Platí: ˆδ0 = 1
ˆδ0, ϕ = δ0, ˆϕ = ˆϕ(0) =
∞
−∞
ϕ(x) · 1dx = 1, ϕ
Podobně: ˆδa = e−iax
ˆδa, ϕ = δa, ˆϕ = ˆϕ(a) =
∞
−∞
ϕ(x) · e−iax
dx = e−iax
, ϕ
Příklad 7.3.4. Vypočtěte zobecněnou Fourierovu transformaci funkcí eit
, sin t
a cos t.
ˆeit
, ϕ = eit
, ˆϕ =
∞
−∞
eit
ˆϕ(t)dt = 2πϕ(1) = 2πδ1, ϕ ⇒ ˆeit
= 2πδ1
ˆe−it
, ϕ = 2πδ−1, ϕ ⇒ ˆe−it
= 2πδ−1
ˆsin t = eit−e−it
2i
= π · δ1−δ−1
i
= πi(δ−1 − δ1)
ˆcos t = eit+e−it
2
= π · δ1+δ−1
1
= π(δ−1 + δ1)
7.4 Zobecněná Fourierova transformace zobecněných
periodických funkcí
Budeme uvažovat součty δ-funkcí. Pro nekonečné součty budeme potřebovat pojem
limity.
41
Definice 7.4.1. Nechť u1, u2, . . . je posloupnost distribucí.
Řekneme, že limn→∞un = u, jestliže
limn→∞ un, ϕ = u, ϕ ∀ϕ ∈ C∞
0 (R).
Analogicky, ∞
n=−∞ un = u, jestliže posloupnost částečných součtů sn = n
k=n uk
konverguje k u, tj. limn→∞sn = u, ve smyslu předchozí definice.
Příklad 7.4.2. ∞
n=−∞ δn, ϕ = limn→∞
n
k=−n δk, ϕ = limn→∞
n
k=−n ϕk =
= ∞
n=−∞ ϕn
Řada konverguje, neboť ϕ ∈ C∞
0 (R).
Definice 7.4.3. Svazkem δ-funkcí rozumíme součet ∞
k=−∞ akδk·∆x, kde ak ∈ R.
∆x se nazývá (prostorový) krok svazku.
Fourierova transformace svazku δ-funkcí je
( ∞
k=−∞ akδk·∆x) = ∞
k=−∞ ak
ˆδk·∆x = ∞
k=−∞ ake−ik∆xξ
,
což je periodická funkce (pokud řada konverguje) s periodou 2π
∆x
.
Je-li f(x) ”rozumná” funkce, pak má konvergentní Fourierovu řadu a platí
f(x) = ∞
k=−∞ cke−ikx
. Tedy zobecněná Fourierova transformace funkce f(x) je
rovna f(x) = ( ∞
k=−∞ cke−ikx) = ∞
k=−∞ cke−ikx = 2π ∞
k=−∞ ckδk, tedy f(x) je
svazkem δ-funkcí.
Věta 7.4.4. Nechť p > 0 je perioda. Označme ∆ω = 1
p
a nechť f a F jsou dvě
distribuce takové, že F je zobecněná Fourierova transformace funkce f. Je-li splněna
jedna z následujících dvou podmínek:
(i) f je periodická distribuce s periodou p,
(ii) F je svazek δ-funkcí s krokem ∆ω = 1
p
,
pak platí i druhá podmínka a navíc existují jednoznačně určená čísla
{. . . , f−1, f0, f1, f2, . . .} taková, že
f(t) =
∞
k=−∞
fkei2πk∆ωt
a
F(ω) = 2π
∞
k=−∞
fkδk∆ω(ω).
42
Kapitola 8
Rychlá Fourierova transformace
Místo f ∈ L2
(G) budeme uvažovat konečnou posloupnost čísel
x0, x1, . . . , xN−1
a místo ˆf(m) = 1
N
N−1
j=0 f(xj)e−i 2π
N
jm
budeme uvažovat
Xm =
1
N
N−1
j=0
xjω−jm
N ,
kde ωN = ei 2π
N je N-tá primitivní odmocnina z 1.
Nechť N je sudé, N = 2M. Rozdělme {x0, x1, . . . , xN−1} na sudou a lichou část:
{x0, x2, . . . , xN−2} a {x1, x3, . . . , xN−1} a označme yn = x2n a zn = x2n+1.
Máme Xm =
N
2
−1
j=0 yjω−2jm
N +zjω−(2j+1)m
=
N
2
−1
j=0 yj(ω2
N )−jm
+ω−m
N zj(ω2
N )−jm
, ale
ω2
N = ωN
2
.
Nechť {Ym}
N
2
−1
m=0 je diskrétní Fourierova transformace posloupnosti {ym}
N
2
−1
m=0 , analogicky
pro Zm. Pak platí Rekombinační vztah
Xm = Ym + ω−m
N Zm,
Xm+N
2
= Ym − ω−m
N Zm
pro m = 0, 1, . . . , N
2
− 1.
Porovnání počtů operací:
• transformace z definice: N × N násobení
• transformace pomocí Rekombinačního vzorce: 2(N
2
× N
2
) + 2N = N2
2
+ 2N
43
Pro N >> 1 je N2
>> N, tedy ušetříme cca polovinu operací.
Je-li N = 2p
, můžeme v dělení pokračovat, Ym a Zm počítat pomocí dělení atd.
Po p krocích dostaneme diskrétní Fourierovu transformaci délky 1, kdy X0 = x0 a
počítání končí.
Počet operací pro N = 2p
:
p = log2 N → celkem 2N log2 N operací oproti N × N operací z definice
např. pro N = 103
:
z definice: 106
operací
ze vzorce: log2 1000 ≈ 10
⇒ cca 50× méně operací
44