41

Ortogonalizáció Wettl Ferenc

2016-03-22

Wettl Ferenc

Ortogonalizáció

2016-03-22

1 / 41

Tartalom

1 Ortonormált bázis 2 Ortogonális mátrix 3 Ortogonalizáció 4 QR-felbontás 5 Komplex skaláris szorzás 6 Diszkrét Fourier-transzformált Fourier-mátrixok Diszkrét Fourier-transzformáció Gyors Fourier-transzformáció

Wettl Ferenc

Ortogonalizáció

2016-03-22

2 / 41

Ortonormált bázis


Wettl Ferenc

Ortogonalizáció

2016-03-22

3 / 41

Ortonormált bázis

Ortogonális és ortonormált bázis D

OR (ortogonális rendszer, lehet köztük zérusvektor), ONR (ortonormált rendszer)

T

Ha a nullvektortól különböz®

a1 , a2 ,. . . , ak

vektorok páronként

ortogonálisak, akkor függetlenek is.

B

a + · · · + ck ak = 0

Tekintsük a c1 1

egyenletet.

Szorozzuk be az egyenl®ség mindkét oldalát

ai -vel

(i

= 1, 2, . . . , k ):

(c1 a1 + c2 a2 + · · · + ck ak ) · ai = 0 · ai ci ai

Mivel

ai · ai 6= 0,

Wettl Ferenc

i = 0,

ezért c

· ai = 0 .

és ez igaz minden i -re.

Ortogonalizáció

2016-03-22

4 / 41

Ortonormált bázis

Ortogonális és ortonormált bázis T

Legjobb közelítés ONB esetén Adva van a

{e1 , e2 , . . . , ek } egy

v

V

vektortérben egy

ortonormált rendszer által kifeszített

A

altér, valamint

vektor. Ekkor a

vˆ = (v · e1 )e1 + (v · e2 )e2 + · · · + (v · ek )ek vektor az

B

A

altér

v-hez

v

és az altér egy

2

(v − u) = Wettl Ferenc

k X v− (v · ei )ei

i =1 tetsz®leges u

v−

vˆ = projA v. legközelebb v-hez:

legközelebb fekv® pontja, azaz

Megmutatjuk, hogy az (1) szerinti pont van

(v − vˆ)2 =

(1)

k X i =1

= v2 −

k X (v · ei )2 . i =1

vektorának távolságnégyzete:

!2 ci ei

!2

= v2 − 2

Ortogonalizáció

k X i =1

ci (v

· ei ) +

k X i =1

2 ci .

2016-03-22

5 / 41

Ortonormált bázis

Ortogonális és ortonormált bázis A különbségük pozitív, tehát valóban

(v − u)2 − (v − vˆ)2

v2 − 2

=

=

=

k X i =1 k X i =1

2 ci

k X

ci (v

i =1 k X

−2

i =1

· ei ) +

ci (v

vˆ

k X

van

2 ci

i =1 k X

· ei ) +

i =1

v-hez

! −

legközelebb:

k X v2 − (v · ei )2 i =1

(v · ei )2

(ci − v · ei )2 ≥ 0.

Ebb®l a legjobb közelítés tétele szerint kapjuk, hogy

Wettl Ferenc

!

Ortogonalizáció

vˆ = projA v.

2016-03-22

6 / 41

Ortogonális mátrix


Wettl Ferenc

Ortogonalizáció

2016-03-22

7 / 41


Ortogonális mátrixok D

Egy valós négyzetes mátrix ortogonális, ha oszlopvektorai vagy sorvektorai ONR-t alkotnak. Ha nem kötjük ki, hogy négyzetes legyen, szemiortogonális mátrixról beszélünk.

P T B T

A forgatás, tükrözés mátrixa, és minden permutációmátrix ortogonális.

Q ∈ Rm×n . Ekkor Q = In (m ≤ n esetén QQT = In )

Legyen m

QT Q

≥n

és

szemiortogonális

⇐⇒

sorvektorszor oszlopvektor Legyen

Q ∈ Rn ×n .

Az alábbi állítások ekvivalensek:

Q oszlopvektorai ortonormált rendszert alkotnak. QT Q = In . Q−1 = QT . QQT = In . Q sorvektorai ortonormált rendszert alkotnak.

Á | det(Q)| = 1, O(n) Wettl Ferenc

és SO(n ) zárt a szorzásra és invertálásra nézve. Ortogonalizáció

2016-03-22

8 / 41


Ortogonális mátrixok geometriája T

Ortogonális mátrixhoz tartozó mátrixleképezés Legyen

Q ∈ Rn ×n .

Az

alábbi állítások ekvivalensek:

B

a) Q ortogonális. b) |Qx| = |x| minden x ∈ Rn vektorra. c) Qx · Qy = x · y minden x, y ∈ Rn vektorra. a) ⇒ b) : Ha Q ortogonális, akkor QT Q = I, így tetsz®leges x ∈ Rn 2 T T T T 2 vektorra |Qx| = Qx · Qx = (Qx) (Qx) = x Q Qx = x x = |x| . b)

⇒

c) : A skalárszorzás abszolút értékkel való kifejezéséb®l:

Qx · Qy = = c)

⇒

1 4 1 4

a) : A

1

|Qx + Qy|2 − |Qx − Qy|2 =

4

|x + y|2 − |x − y|2 = x · y

Q

mátrix i -edik oszlopa

qi = Qei (

qi · qj = Qei · Qej = ei · ej = Wettl Ferenc

|Q(x + y)|2 − |Q(x − y)|

Ortogonalizáció

0,

ha i

1,

ha i

6 j, = = j. 2016-03-22

9 / 41


A 2- és 3-dimenziós tér ortogonális transzformációi T

Minden O (2)-be es® ortogonális mátrix vagy egy vagy egy

α/2

cos α sin α

T

α

szög¶ forgatás,

szög¶ egyenesre való tükrözés mátrixa, azaz

− sin α cos α

vagy

cos α

sin α

sin α

− cos α

A harmadrend¶ 1 determinánsú ortogonális transzformációk a forgatások, a

−1

determinánsúak, azaz O (3)

− SO (3)

elemei egy

pontra való tükrözés és egy forgatás egymás utáni alkalmazásával megkaphatók.

Wettl Ferenc

Ortogonalizáció

2016-03-22

10 / 41


Givens-forgatás D

Givens-forgatás: forgatás egy síkban, minden más helyben marad:



1  .. . 

m

Egy tetsz.

x

... ..

.

0   G =  ...  0  .  ..

...

0

...

...

0 . . .

...

0 . . .

...

cos α . . .

...

− sin α

...

..

. . .

sin α . . .

...

0

...

.

cos α . . .

...

0

...

..

.



0 . . .

0  . . . 0  . . . 1

vektor olyan vektorba forgatható, melynek j -edik

koordinátája 0. Az i -edik és j -edik sorokat és oszlopokat kiemelve

cos α sin α

− sin α cos α

Wettl Ferenc

a

b

=

r

0

r

=

p

Ortogonalizáció

a2

+ b2 ,

cos α

a

= , r

sin α

2016-03-22

b

=− . r

11 / 41


Householder-tükrözés D

Householder-tükrözés: Egy adott

a 6= 0

vektorra mer®leges hipersíkra

való tükrözést Householder-tükrözésnek nevezzük. Mátrixa

H=I−

2

aT a

aaT

a és b két különböz®, de azonos hosszúságú vektor Rn -ben, ⊥ az (a − b) hipersíkra való H-tükrözés a-t és b-t fölcseréli. B Megmutatjuk, hogy Ha = b és Hb = a, ahol H = I − (a−b) 2 (a−b) (a − b)(a − b)T .

T

Ha

akkor

T

(a − b)T (a − b)

Ha = a − =a− Mivel

H−1

Wettl Ferenc

= aT a − aT b − bT a + bT b = 2(aT a − bT a) = 2(a − b)T a. 2

(a − b)T (a − b)

(a − b)(a − b)T a

1

(a − b)T a(a − b) = a − (a − b) = b. (a − b)T a = H, ezért Hb = H−1 b = a. Ortogonalizáció

2016-03-22

12 / 41

Ortogonalizáció


Wettl Ferenc

Ortogonalizáció

2016-03-22

13 / 41

Ortogonalizáció

GramSchmidt-ortogonalizáció T

A = {a1 , a2 , . . . , ak } egy független V = {v1 , v2 , . . . , vk } = 1, 2, . . . , k esetén

GramSchmidt-ortogonalizáció Ha

vektorrendszer, akkor létezik olyan ortogonális vektorrendszer, hogy minden i

a a2 , . . . , ai ) = span(v1 , v2 , . . . , vi ).

span( 1 , Az ortogonális

V

(2)

rendszerb®l a vektorok normálásával kapott

v1 v2 vk , ,..., |v1 | |v2 | |vk |

rendszer ortonormált.

Wettl Ferenc

Ortogonalizáció

2016-03-22

14 / 41

Ortogonalizáció

GramSchmidt-ortogonalizáció B v 1 = a1

span(a1 ) = span(v1 ). a a2 ) = span(v1 , v2 ) teljesüléséhez: v1 v1 a2 · v1 v2 = a2 − a2 · = a2 − v |v1 | |v1 | v1 · v1 1 a ·v a ·v E vektor nem 0-vektor, hisz v2 = 0 esetén a2 = v ·v v1 = v ·v a1 lenne, azaz a1 és a2 nem lenne független. span(a1 , a2 ) = span(v1 , v2 ) . . . vi v v kiszámoljuk az ai +1 vektornak a span( |v | , |v | , . . . , |vi | ) altérre mer®leges összetev®jét, ez lesz vi +1 a ·v a ·v a ·v vi +1 = ai +1 − i +1 1 v1 − i +1 2 v2 − · · · − i +1 i vi v1 · v1 v2 · v2 vi · vi vi +1 6= 0, különben A nem volna független. vi +1 kifejezhet® az a1 , a2 ,. . . , ai +1 vektorok lineáris kombinációjaként, és ai +1 kifejezhet® az v1 , v2 ,. . . , vi +1 vektorok lineáris kombinációjaként. A span( 1 ,

Wettl Ferenc

Ortogonalizáció

1

2

1

2

2

1

2

1

1

1

1

1

2016-03-22

15 / 41

Ortogonalizáció

GramSchmidt-ortogonalizáció P M

Keressünk ortonormált bázist az

(6, 2, 2, −2)

(1, 1, 1, 1), (3, −1, 3, −1),

vektorok által kifeszített altérben.

El®ször keressünk egy ortogonális bázist:

v1 = (1, 1, 1, 1) (3, −1, 3, −1) · (1, 1, 1, 1) (1, 1, 1, 1) = (2, −2, 2, −2) (1, 1, 1, 1) · (1, 1, 1, 1) (6, 2, 2, −2) · (1, 1, 1, 1) v3 = (6, 2, 2, −2) − (1, 1, 1, 1) (1, 1, 1, 1) · (1, 1, 1, 1) (6, 2, 2, −2) · (2, −2, 2, −2) − (2, −2, 2, −2) = (2, 2, −2, −2) (2, −2, 2, −2) · (2, −2, 2, −2)

v2 = (3, −1, 3, −1) −

Végül az ortonormált bázis:

1 2

Wettl Ferenc

1 1 1 1 1 1 1 1 , , , ,− , ,− , ,− ,− , , 1

1

1

2

2

2

2

2

2

Ortogonalizáció

2

2

2

2

2

2016-03-22

16 / 41

QR-felbontás


Wettl Ferenc

Ortogonalizáció

2016-03-22

17 / 41

QR-felbontás

A QR-felbontás D

Legyen

A

egy teljes oszloprangú mátrix. Az

A = QR

felbontást

QR-felbontásnak vagy redukált QR-felbontásnak nevezzük, ha

R T

Q

az

A-val

azonos méret¶ szemiortogonális mátrix, és

négyzetes fels® háromszögmátrix, f®átlójában pozitív elemekkel.

Teljes oszloprangú valós mátrix QR-felbontása létezik és egyértelm¶. A

Q

mátrixot ortonormált oszlopvektorok hozzávételével

kiegészíthetjük egy ortogonális mátrixszá, az zérussorok hozzávételével egy m

A,

akkor e mátrixok szorzata is

R

mátrixot pedig

fels® háromszögmátrixszá,

ugyanis

R

ˆ A= Q Q

× n-es

O

ˆ = QR = QR + QO

Ezt nevezzük teljes QR-felbontásnak.

Wettl Ferenc

Ortogonalizáció

2016-03-22

18 / 41

QR-felbontás

B

QR létezése a GramSchmidt-ortogonalizációs eljárásból:

A = [a1 a2 . . . ak ] ∈ Rn×k teljes oszloprangú (k ≤ n), a q-vektorokra: span(a1 , . . . , ai ) = span(q1 , . . . , qi ) minden i = 1, 2, . . . , k értékre, ezért léteznek olyan rij skalárok, hogy a1 = r11 q1 a2 = r12 q1 + r22 q2 . . .

ak = r1k q1 + r2k q2 + · · · + rkk qk . Ezt mátrixszorzat-alakba írva épp a kívánt felbontást kapjuk:

A = [a1 a2 . . . ak ] = [q1 q2

  r11 r12 . . . r1k  0 r22 . . . r2k  . . . qk ]  = QR. . .  ..  ... . .  . . . 0

0

...

rkk

ii = |vi |, tehát rii > 0. = Ik R = R, tehát R = QT A.

A GramSchmidt-eljárásból az is látható, hogy r

R

T kiszámítása: Q A

Wettl Ferenc

=

QT QR

Ortogonalizáció

2016-03-22

19 / 41

QR-felbontás

QR-felbontás primitív ortogonális transzformációkkal 

P M

4

QR-felbontását Givens-forgatásokkal:

a

= 4, b = 3, tehát r = "4 # 3 /5

Q1 = −3/5

0

/5 4/5

0

0

1

0

Következ® lépésben a

√

32

+ 42

Q1 A = Q1 A

5

A = 3

10

0

12

= 5, "

cos α

= #

5

10

0

5

0

0

12

13

8



6 13

4/5, sin α

= −3/5

10

.

mátrix harmadik sorának második elemét

elimináljuk:

"

Q2 =

1 0 0

0

5/13 −12/13

0 12/13 5/13

#

5

10

10

0

13

12

0

0

5

" .

R = Q2 Q1 A =

# .

és innen

"4

Q

/5 T 3/5 = (Q2 Q1 )−1 = QT Q = 1 2

0

Wettl Ferenc

Ortogonalizáció

36/65 −3/13 4/13 −48/65 , 12/13 5/13

#

2016-03-22

20 / 41

QR-felbontás

QR-felbontás primitív ortogonális transzformációkkal 

A

∗ ∗ = ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗

 ∗ ∗  → ∗ ∗

 ∗ ∗ ∗ ∗  0 ∗ ∗ ∗ →  = 0 ∗ ∗ ∗ 0 ∗ ∗ ∗

Q1 A

Q2 Q1 A 

Q1 = H1

1

0 Q2 =  0 0

Wettl Ferenc

 ∗ ∗ ∗ ∗  0 ∗ ∗ ∗ →  = 0 0 ∗ ∗ 0 0 ∗ ∗ 

0

0

H2

0

  

Ortogonalizáció

 ∗ ∗ ∗ ∗  0 ∗ ∗ ∗   = 0 0 ∗ ∗ 0 0 0 ∗  





Q3 Q2 Q1 A 

1

0 Q3 =  0



0

0 1

0 0

0 0

H3

0 0 



2016-03-22

21 / 41

QR-felbontás



P

A=

Q1 =



trafóhoz





100

2aaT I3 − T a a

4 −4

1 = 0 1 0− −4 001

(4, 3) 7→ (5, 0)

6

transzformációh

H2 = I2 − 

1

Q2 = 0 0

2 aaT aT a 0 4/5 3/5

= 

1



=

4

1 3



2

2





1 2 −2

2,Q1 A

 21 −2 2

3 −2

= 0

1

0

1

0

0

1

0 3/5  , −4/5

−

1 5

1

−3

−3

1

=

9

5



0

4 −5 3 −5

5

2 10

−5 .

11

2

Ortogonalizáció

3

−4  3

5

−7

0

1



 10 15 −10

1

3

−2

3

R = Q2 Q1 A = 0 

4

14

2016-03-22



3

a = (4, 3) − (5, 0) = (−1, 3)

Q = (Q2 Q1 )−1 = QT1 QT2 = Wettl Ferenc



4

4 −4

4 −4

0

−3 −2 5 −7 a = (1, 2, −2) − (3, 0, 0) = (−2, 2, −2)

QR-felbontását Householder-módszerrel:

M (1, 2, −2) 7→ (3, 0, 0)

1

22 / 41

QR-felbontás

Egyenletrendszer optimális megoldása QR-felbontással T

Legyen

A

egy teljes oszloprangú m

QR-felbontása, és Ekkor az

xˆ =

Ax = b

b

egy

Rm -beli

× n-es

valós mátrix,

A = QR

egy

vektor.

egyenletrendszer egyetlen optimális megoldása

R−1 QT b, ami megkapható az

Rxˆ = QT b

egyenletrendszerb®l

egyszer¶ visszahelyettesítéssel is.

B

Optimális megoldás a normálegyenletb®l:

AT Axˆ = AT b T

A = QR

behelyettesítése után

T

ˆ = (QR) b (QR) QRx

RT QT QRxˆ = RT QT b RT Rxˆ = RT QT b

QT Q = I balról szorzás az

(RT )−1

mátrixszal

Rxˆ = QT b.

Wettl Ferenc

Ortogonalizáció

2016-03-22

23 / 41

Komplex skaláris szorzás


Wettl Ferenc

Ortogonalizáció

2016-03-22

24 / 41


Komplex vektorok skaláris szorzata ?

komplex számok skaláris szorzata

?

(1, i) · (1, i) = 1 − 1 = 0 ?

(i, i) · (i, i) = −1 − 1 = −2 lehet®ségek:

z · w = z1 w1 + z2 w2 + · · · + zn wn , z · w = z1 w1 + z2 w2 + · · · + zn wn . D

vagy

A komplex mátrix adjungáltján (vagy Hermite-féle transzponáltján) elemenkénti konjugáltjának transzponáltját értjük. Az A adjungáltját T A∗ , vagy Hermite neve után AH jelöli, tehát AH = A . D z · w = z1 w1 + z2 w2 + · · · + zn wn = zH w. Az

Wettl Ferenc

Ortogonalizáció

2016-03-22

25 / 41


Adjungált és a skaláris szorzás tulajdonságai T

Legyenek

A

T

Legyen

D

A komplex skaláris szorzás segítségével a valós esethez hasonlóan

(AH )H

és

B

komplex mátrixok, c komplex szám. Ekkor

= A, (A + B)H = AH + BH , (c A)H = c AH (AB)H = BH AH .

u, v, w ∈ Cn ,

és legyen c ∈ C. Ekkor u·v =v·u u · (v + w) = u · v + u · w, (c u) · v = c (u · v) és u · (c v) = c (u · v), u · u > 0, ha u 6= 0, és u · u = 0, ha u = 0.

deniálható a komplex vektorok távolsága és szöge, és így a mer®legessége is.

Wettl Ferenc

Ortogonalizáció

2016-03-22

26 / 41


Önadjungált Hermite-féle mátrixok D A önadjungált, ha AH = A. P Melyik önadjungált? 

 −i 1−i

M

i

1

2 2

+ 3i

 +i 2 − 3i , 1

3

1

2

2

3

i

,

1

−i

1

+i 1

,

1 1

+i

1

+i

2

az els® kett®

Wettl Ferenc

Ortogonalizáció

2016-03-22

27 / 41


Unitér mátrixok D Á

Egy komplex négyzetes

U

mátrix unitér, ha

UH U = I.

Az alábbiak ekvivalensek:

UUH = I, U−1 = UH , U oszlopvektorai

ortonormált bázist alkotnak a komplex skalárszorzásra

nézve,

U

sorvektorai ortonormált bázist alkotnak a komplex skalárszorzásra

nézve,

|Ux| = |x| minden x ∈ Cn Ux · Uy = x · y.

Wettl Ferenc

vektorra,

Ortogonalizáció

2016-03-22

28 / 41

Diszkrét Fourier-transzformált


Wettl Ferenc

Ortogonalizáció

2016-03-22

29 / 41


M

Fourier-mátrixok

A Fourier-sorok komplex alakja, és részletösszegei (diszkrét Fourier-összeg):

∞ X

n=−∞

Á

A

cn e

nt i

g (t )

=

NX −1 n=0

cn e

n t = c +c e t +c e 2 t +· · ·+c (N −1) t 0 1 1 N −1 e i

i

(c0 , c1 , . . . , cN −1 ) 7→ (g (0), g ( 2Nπ ), . . . , 2(NN−1)π ))

és mátrixa

Wettl Ferenc

2π i

[e N

mn ]

(0

i

i

leképezés lineáris,

≤ m, n < N ).

Ortogonalizáció

2016-03-22

30 / 41


P

A

a

ε=e

2π i 3

Fourier-mátrixok

jelöléssel

y0

= c0 + c1 e i0 + c2 e 2i0 = c0 + c1 + c2

y1

= c0 + c1 e

y2

= c0 + c1 e

2π i 3 4π i 3

+ c2 e + c2 e

4π i 3

= c0 + c1 ε + c2 ε2

8π i 3

= c0 + c1 ε2 + c2 ε4

(c0 , c1 , c2 ) 7→ (y0 , y1 , y2 ) leképezés    y0 y1  y2

Wettl Ferenc

1

1

= 1

ε ε2

1

lineáris, mátrixszorzatos alakja:

Ortogonalizáció

 

c0 2   c1  ε 4 c2 ε 1

2016-03-22

31 / 41


Fourier-mátrixok

Általánosan:

y0 = c0 + c1 e 0 + c2 e 2 0 + · · · + cN −1 e (N −1) 0 = c0 + c1 + · · · + cN −1 i

y1 = c0 + c1 e

i

2π i

i

4π i

N + c2 e N + · · · + cN −1 e

2(N −1)πi

N

. . .

yN −1 = c0 + c1 e Az

ε = e2π /N i

2πi(N −1)

   

y0 y1 . . .

yN −1

Wettl Ferenc

1

1

1   1   = 1   .  ..

ε ε2 ε3



+ c2 e

4πi(N −1)

N

+ · · · + cN −1 e

2πi(N −1)2

N

jelöléssel mátrixszorzat-alakban

 

N

1

. . .

εN −1

1 ε2

1 ε3

ε4 ε6

ε6 ε9

. . .

. . .

ε2(N −1)

ε3(N −1)

Ortogonalizáció

··· ··· ··· ···

 1   N −1 ε  c0   ε2(N −1)    c1  3 (N −1)   .  ε  .  .  . .. .  . . cN −1 2 · · · ε(N −1) 2016-03-22

32 / 41


D

Fourier-mátrixok: az

Fourier-mátrixok

ε = e2π /N , ω = ε = e−2π /N  i

i

1

 1 N −1 ε ε 1   ΦN ,ε = VN (1, ε, ε2 , . . . , εN −1 ) =  . . . . . .. .  ..  . . N −1 (N −1)2 1 ε ... ε   1 1 ... 1 N −1 ω ... ω 1   ΦN ,ω = VN (1, ω, . . . , ω N −1 ) =  . . . . . .. .  ..  . . N −1 (N −1)2 1 ω ... ω

T

1

jelölésekkel:

... ...

A Fourier-mátrixok tulajdonságai:

Bármelyik Fourier-mátrix

k -adik és N − k -adik sora egymás konjugáltja,

esetén pedig az N/2-edik sorvektor (1, −1, 1, −1, . . . ). H ΦN ,ω = ΦN ,ε = ΦH N ,ε és ΦN ,ε = ΦN ,ω = ΦN ,ω ΦN ,ε ΦN ,ω = N IN , így ΦN ,ε és ΦN ,ω invertálható, páros

N

1 Φ− N ,ε = 1 továbbá √ Wettl Ferenc

N ΦN ,ε

és

1

1 ΦN ,ω , Φ− N ,ω =

N √1 ΦN ,ω N

1

Φ , N N ,ε

unitér.

Ortogonalizáció

2016-03-22

33 / 41


M

Diszkrét Fourier-transzformáció

A továbbiakban

f (t )

=

1

N

NX −1 n=0

cn e

nt i

függvényb®l indulunk ki, a megadott helyek a [0, 2π] intervallumot N

k N (k = 0, 1, . . . , N − 1) pontok. A FN : (c0 , c1 , . . . , cN −1 ) 7→ (y0 , y1 , . . . , yN −1 ) FN = ΦN ,ω , részre osztó 2 π/

amelyre a

továbbiakban az

D

Diszkrét Fourier-transzformáció (DFT) Az

FN

: CN → CN : x 7→ X = FN x

Wettl Ferenc

Ortogonalizáció

2016-03-22

34 / 41


P

Az

F1 , F2 , F 4

és

F8


mátrixok:



1

F1 = [1],

F2 =

1

1

1

−1

,

1

F4 =  

1 1



1

1   1  1 F8 =  1  1   1 1

Wettl Ferenc

1

1

−i

−i −1

1√−i 2 −√ 1−i

2

−1

−√ 1+i

2

i

1√+i 2

i

1

−√ 1−i

2

i

1√−i 2

1

−1

−i −1

i

i

1√+i 2

−√ 1+i

2

1

−1 1

−1 1

−1 1

−1

Ortogonalizáció

1

−√ 1+i

2

1

1

i

−1 −i

−1

1

i

−1 −i

1√−i 2

−√ 1−i

2

1



−i −1 i , −1 1 −1 i −1 −i 

−i

1√+i 2

1

i

1

1√+i 2

   i  −√ 1+i   2  −1   −√ 1−i  2   i  1√−i 2

2016-03-22

35 / 41


T


A DFT tulajdonságai

Konstans vektor képe impulzusvektor (melynek a nulladikat kivéve mindegyik koordinátája 0), és fordítva, konkrétan

FN (c , c , . . . , c ) = (Nc , 0, . . . , 0),

FN (c , 0, . . . , 0) = (c , c , . . . , c ).

c ∈ C tetsz®leges konstans. x valós vektor, akkor XN −k = X k . FN transzformáció invertálható, inverze

ahol Ha Az

x = FN−1 X =

Wettl Ferenc

1

N

ΦN ,ε X,

(IDFT) többféle felírásban:

N −1 N −1 2π 1 X 1 X xk = Xn εkn = Xn e N kn . N n=0 N n=0

Ortogonalizáció

i

2016-03-22

36 / 41


M M

DFT kiszámításához N

Gyors Fourier-transzformáció

2 m¶velet

két fele akkora méret¶ Fourier-transzformációból megkapható:

NX −1

NX −1 kn kn Xk = xn e N = xn ωN n =0 n =0 NX /2−1 NX /2−1 − π − π 2nk (2n+1)k N + x2n+1 e N = x2n e n =0 n=0 NX /2−1 NX /2−1 − π − π − π nk nk k N / N x2n e x2n+1 e N / = +e n=0 n =0 NX /2−1 NX /2−1 nk k nk k = x2n ωN /2 + ωN x2n+1 ωN /2 = Ek + ωN Ok . n=0 n =0 −2π i

2 i

2 i

2 i 2

2 i

2 i 2

Ek és Ok N /2 szerint periodikusak Innen k

< N /2

A m¶veletigény Wettl Ferenc

esetén

Ek +N /2 = Ek , Ok +N /2 = Ok k k Ok . Xk = Ek + ωN Ok , Xk +N /2 = Ek − ωN

3 2 N log N .

Ortogonalizáció

2016-03-22

37 / 41


function FFT(x) N ← dim(x) X legyen N -dimenziós if N = 1 then X0


vektor

← x0

else y ← x páros index¶ elemei z ← x páratlan index¶ elemei Y ← FFT(y) Z ← FFT(z) for k ← 0 to N /2 − 1 do E ← Yk − π k O ← e N Zk Xk ← E + O Xk +N /2 ← E − O 2 i

return X Wettl Ferenc

Ortogonalizáció

2016-03-22

38 / 41


M


FFT mátrixszorzat-alakja

F O FN = ∆N N /2 Π , O FN /2 N

ΠN

az a permutációs mátrix, mely el®re veszi a páros index¶

elemeket,

∆N

index¶eket egy

a fél transzformáltakat összeadó, és a páratlan

ω -hatvánnyal

beszorzó mátrix.

1 



1

0

0

0

0 Π4 =  0

0

1

0

1

0

0

0

0

0

1



1

0

1

0 ∆4 =  1

1

0

0

−1

0

1

0

Wettl Ferenc

Π8 =



0

00  0 0  0 0 0

0 0 0 0 1 0 0 0

0 1 0 0 0 0 0 0

0 0 0 0 0 1 0 0

0 0 1 0 0 0 0 0

0 0 0 0 0 0 1 0

0 0 0 1 0 0 0 0

0 0 0  0 0  0 0 1





−i  = I 2 D2 0  I2 −D2 i

Ortogonalizáció

I D4 ∆8 = 4 I4 −D4

2016-03-22

39 / 41



∆ mátrixokban szerepl® diagonális mátrixok az egységmátrixok, ω hatványait tartalmazó D mátrixok, ahol Dk = diag(1, ω, ω 2 , . . . , ω k −1 ). Pl. F4 O F8 = ∆8 Π O F4 8   F2 O O O O F2 O O  Π4 O ∆4 O    Π . = ∆8 O ∆4  O O F2 O  O Π4 8 A

és

az

O

Wettl Ferenc

O

Ortogonalizáció

O F2

2016-03-22

40 / 41


0000

0000

0000

0000

0001

0010

0100

1000

0010

0100

1000

0100

0011

0110

1100

1100

0100

1000

0010

0010

0101

1010

0110

1010

0110

1100

1010

0110

0111

1110

1110

1110

1000

0001

0001

0001

1001

0011

0101

1001

1010

0101

1001

0101

1011

0111

1101

1101

1100

1001

0011

0011

1101

1011

0111

1011

1110

1101

1011

0111

1111

1111

1111

1111

Wettl Ferenc


Ortogonalizáció

2016-03-22

41 / 41

41

Recommend Documents