40

Mer®legesség Wettl Ferenc

2015-03-13

Wettl Ferenc

Mer®legesség

2015-03-13

1 / 40

Tartalom

1

Pszeudoinverz

2

Ortonormált bázis ortogonális mátrix

3

Komplex és véges test feletti terek

4

Diszkrét Fourier-transzformált Fourier-mátrixok Diszkrét Fourier-transzformáció Gyors Fourier-transzformáció

Wettl Ferenc

Mer®legesség

2015-03-13

2 / 40

Pszeudoinverz

A pszeudoinverz fogalma Á A sortér és az oszloptér közt létezik természetes kölcsönösen egyértelm¶ megveleltetés (

Rn

A

egyetlen sortérbe es® megoldása).

A+ R m

S(A)

D

Ax = b

O(A)

0 0 A ∈ Rm×n pszeudoinverzén vagy MoorePenrose-féle + azt az A -szal jelölt mátrixot értjük, amellyel a sortér minden

x

A+ (Ax) = x, továbbá minden z vektorra A+ z = 0.

vektorára

az oszloptérre mer®leges

Wettl Ferenc

pszeudoinverzén

Mer®legesség

2015-03-13

3 / 40

Pszeudoinverz

Néhány pszeudoinverz Á Á Á Á

A+ = A−1 , ha A invertálható, O+ m ×n = On ×m , [a]+ = [1/a], ha a 6= 0, és [0]+ = [0], (A+ )+ = A,

Á ha a

ii 6= 0



(i

a11

0

0

a22

     

. . . 0

= 1, 2, . . . , r ), ... ...

. . .

..

0

...

Wettl Ferenc

.

O

+

0 0 . . .

arr

akkor

   O   

O

    =  

m ×n

Mer®legesség

1

a11 0 . . . 0

1

... ...

0

. . .

..

. . .

0

...

0

a22

.

O

0

1

arr

    O   

O

2015-03-13

n×m

4 / 40

Pszeudoinverz

A pszeudoinverz kiszámítása T Ha a valós

A

teljes oszloprangú, akkor

+ ha teljes sorrangú, akkor A Legyen

A = BC,

ahol

B

=

A+ = (AT A)−1 AT ,

AT (AAT )−1 .

egy teljes oszloprangú,

C

egy teljes sorrangú

mátrix (ld. bázisfelbontás). Ekkor

B

A+ = C+ B+ = CT (CCT )−1 (BT B)−1 BT = CT (BT ACT )−1 BT . n T Ha A teljes oszloprangú, akkor R = S(A), és A A invertálható: (AT A)−1 AT Ax = x.

z ∈ N (AT ), vagyis AT z = 0, akkor = = = 0. m Ha A teljes sorrangú, akkor O(A) = R : ∀y-ra Ax = y konzisztens. ˆ az egyetlen sortérbe es® megoldást, így minden más x Jelölje x ˆ. A+ -ra fenn kell álljon A+ y = x ˆ: megoldásra projS(A) x = x Meg kell még mutatnunk, hogy ha

A+ z

0: (AT A)−1 AT z

(AT A)−1 0

T T −1 T T −1 (Ax) = A+ y. A x = A (AA ) Ax = A (AA )

projS( ) Wettl Ferenc

Mer®legesség

2015-03-13

5 / 40

Pszeudoinverz

A pszeudoinverz tulajdonságai T MoorePenrose-tétel: A valós

A

mátrixnak

X

pontosan akkor

pszeudoinverze, ha az alábbi négy feltétel mindegyike fennáll:

a)

AXA = A,

K Tetsz®leges

b)

XAX = X,

A ∈ Rm×n

Rm

A+ A

az

Rn

és

d)

(XA)T = XA.

AA+ = projO(A) .

teret mer®legesen vetíti

teret mer®leges vetíti

Wettl Ferenc

(AX)T = AX,

mátrix esetén

A+ A = projS(A) Tehát

c)

A

A

sorterére, míg

AA+

az

oszlopterére.

Mer®legesség

2015-03-13

6 / 40

Pszeudoinverz

A pszeudoinverz és a min. absz. érték¶ opt. megoldás A egy valós mátrix. Az Ax = b egyenletrendszernek xˆ = A+ b a minimális abszolút érték¶ optimális megoldása.

T Legyen

az

P Határozzuk meg a minimális abszolút érték¶ optimális megoldását!

y

+

z

=3

x

+ y + 2z = 2

x

+y

=2

M Az egyenletrendszer nem oldható meg:

"

0

1

1

3

1

1

2

2

1

1

0

2

#

" ⇒

1

0

1

0

0

1

1

0

0

0

0

1

#

Ezt felhasználva a minimális abszolút érték¶ optimális megoldás

xˆ = A b = +

Wettl Ferenc

1 9

"

−4

1

5

3

5

1

−4

2

1

2

1

2

Mer®legesség

0

#" #

" # =

1

.

1 2015-03-13

7 / 40


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.

a + · · · + ck ak = 0

B 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.

Mer®legesség

2015-03-13

8 / 40


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

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

B 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

Mer®legesség

k X i =1

ci (v

· ei ) +

k X i =1

2 ci .

2015-03-13

9 / 40


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

!

Mer®legesség

vˆ = projA v.

2015-03-13

10 / 40


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 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 )

T Legyen m

QT Q

≥n

és

szemiortogonális

⇐⇒

B sorvektorszor oszlopvektor T 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, Wettl Ferenc

O(n ) és SO(n ) zárt a szorzásra és invertálásra nézve. Mer®legesség

2015-03-13

11 / 40


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:

Q ortogonális. |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: 1 1 Qx · Qy = |Qx + Qy|2 − |Qx − Qy|2 = |Q(x + y)|2 − |Q(x − y)| a)

b)

B

4

= c)

⇒

1 4

a) : A

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

Mer®legesség

0,

ha i

1,

ha i

6 j, = = j. 2015-03-13

12 / 40


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

α

szög¶ forgatás,

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

cos α sin α

− sin α cos α

vagy

cos α

sin α

sin α

− cos α

T 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

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

Wettl Ferenc

Mer®legesség

2015-03-13

13 / 40


Givens-forgatás D Givens-forgatás: forgatás, mely egy koordinátasík vektorain kívül minden más vektort helyben hagy. Az i -edik és j -edik koordinátákra:



1  .. . 

... ..

.

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

...

0

...

...

0 . . .

...

0 . . .

...

cos α . . .

...

− sin α

...

..

. . .

sin α . . .

...

0

...

.

M E forgatással elérhet® például, hogy egy

cos α . . .

...

0

...

x

..

.



0 . . .

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

vektort egy olyan vektorba

forgassunk, melynek j -edik koordinátája 0. Csak az i -edik és j -edik sorokat és oszlopokat kiemelve

cos α

− sin α cos α

sin α Wettl Ferenc

a

b

=

r

0

r

=

Mer®legesség

p

a2

+ b2 ,

cos α

a

= , r

sin α

2015-03-13

b

=− . r

14 / 40


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, akkor ⊥ az (a − b) hipersíkra való H-tükrözés a-t és b-t fölcseréli. Megmutatjuk, hogy Ha = b és Hb = a, ahol H = I − (a−b)T2 (a−b) (a − b)(a − b)T . (a − b)T (a − b) = aT a − aT b − bT a + bT b = 2(aT a − bT a) = 2(a − b)T a.

T Ha

B

Ha = a − =a− Mivel

H−1

Wettl Ferenc

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. Mer®legesség

2015-03-13

15 / 40


GramSchmidt-ortogonalizáció A = {a1 , a2 , . . . , ak } egy független V = {v1 , v2 , . . . , vk } = 1, 2, . . . , k esetén

T 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

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

rendszer ortonormált.

Wettl Ferenc

Mer®legesség

2015-03-13

16 / 40


GramSchmidt-ortogonalizáció B

v1 = 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 = 2 1 v1 = 2 1 a1 v 1 ·v 1 v 1 ·v 1 lenne, azaz a1 és a2 nem lenne független. span(a1 , a2 ) = span(v1 , v2 ) . . . v v v kiszámoljuk az ai +1 vektornak a span( 1 , 2 , . . . , i ) altérre | v 1 | |v 2 | |v i | 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

Mer®legesség

2015-03-13

17 / 40


GramSchmidt-ortogonalizáció P 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.

M 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

Mer®legesség

2

2

2

2

2

2015-03-13

18 / 40


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

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.

T 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

Mer®legesség

2015-03-13

19 / 40


A 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:



r11

r12

0 . . .

r22 . . .

0

0

A = [a1 a2 . . . ak ] = [q1 q2 . . . qk ]   

... ... ..

.

...

r1 k



r2 k  .  .  .

= QR.

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

Mer®legesség

2015-03-13

20 / 40


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

4

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

M 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

Mer®legesség

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

#

2015-03-13

21 / 40


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

A

∗ ∗ = ∗ ∗

∗ ∗ ∗ ∗

∗ ∗ ∗ ∗

 ∗ ∗  → ∗ ∗

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

Q1 A

Q2 Q1 A 

Q1 = H1

1 0

0 Q2 =  0

0

Wettl Ferenc

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

0

0

H2

Mer®legesség

  

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





Q3 Q2 Q1 A 

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

0 Q3 =  0 

2015-03-13

22 / 40




A=

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

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



2

2





1 2 −2

3 −2

2 , Q1 A

 21 3 −2 2

1

0

0

1

0 3/5  , −4/5

−

1 5

1

−3

4 −5

0

3 −5

1

−3

1

=

9

5



0 5

2 10

−5 .

11

2

Mer®legesség

3

−4  3

5

−7

0

1



 10 15 −10

1

3

−2

3

R = Q2 Q1 A = 0 

4

3

= 0

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)

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

M

1

14

2015-03-13

23 / 40


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

Mer®legesség

2015-03-13

24 / 40


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 D lehet®ségek:

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

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 . z · w = z1 w1 + z2 w2 + · · · + zn wn = zH w.

D Az

D

Wettl Ferenc

Mer®legesség

2015-03-13

25 / 40


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

A

(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.

T Legyen

D A komplex skaláris szorzás segítségével a valós esethez hasonlóan deniálható a komplex vektorok távolsága és szöge, és így a mer®legessége is.

Wettl Ferenc

Mer®legesség

2015-03-13

26 / 40


Önadjungált Hermite-féle mátrixok D

A

önadjungált, ha

AH = A.

P Melyik önadjungált?



i

1

 −i 1−i

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

Mer®legesség

2015-03-13

27 / 40


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,

Mer®legesség

2015-03-13

28 / 40

Diszkrét Fourier-transzformált

Fourier-mátrixok

M 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 ).

Mer®legesség

2015-03-13

29 / 40


P A

a

ε=e

Fourier-mátrixok

2π i 3 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

Mer®legesség

lineáris, mátrixszorzatos alakja:

 

c0 2   c1  ε 4 c2 ε 1

2015-03-13

30 / 40


Fourier-mátrixok

Általánosan:

y0

= c0 + c1 e i0 + c2 e 2i0 + · · · + cN −1 e (N −1)i0 = c0 + c1 + · · · + cN −1

y1

= c0 + c1 e N + c2 e N + · · · + cN −1 e

2π i

4π i

2(N −1)πi

N

. . . y N −1

Az

= c0 + c1 e

ε = 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)

Mer®legesség

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

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

31 / 40


D Fourier-mátrixok: az

Fourier-mátrixok

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

i

1

1

jelölésekkel:

 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 A Fourier-mátrixok tulajdonságai:

Bármelyik Fourier-mátrix k -adik és N

− k -adik

sora egymás konjugáltja,

páros N 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ó, 1 Φ− N ,ε = 1 továbbá √ Wettl Ferenc

N ΦN ,ε

1 és √

1 N

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

N ΦN ,ω

1 N

ΦN ,ε ,

unitér.

Mer®legesség

2015-03-13

32 / 40


Diszkrét Fourier-transzformáció

M 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

Mer®legesség

2015-03-13

33 / 40


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

−1

i

1√−i 2

1

−1

−i −1

i

i

1

1√+i 2

−√ 1+i

2

1

−1 1

−1 1

−1

Mer®legesség

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

2015-03-13

34 / 40



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 F N (c , c , . . . , c ) ahol c Ha Az

∈C

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

= (Nc , 0, . . . , 0),

tetsz®leges konstans.

x valós vektor, akkor XN −k = X k . FN transzformáció invertálható, inverze x = FN−1 X =

Wettl Ferenc

= (c , c , . . . , c ).

1 N

ΦN ,ε X,

xk

=

Mer®legesség

1 N

NX −1 n=0

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

kn =

Xn ε

1 N

NX −1 n=0

2π i

Xn e N

2015-03-13

kn .

35 / 40


M DFT kiszámításához N

Gyors Fourier-transzformáció

2 m¶velet

M 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 −2π −2π 2nk (2n+1)k N + x2n+1 e N = x2n e n =0 n=0 NX /2−1 NX /2−1 −2π −2π −2π nk nk k N / 2 N x2n e x2n+1 e N /2 = +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

i

i

i

i

i

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 .

Mer®legesség

2015-03-13

36 / 40


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 −2π k O ← e N Zk Xk ← E + O Xk +N /2 ← E − O i

return X Wettl Ferenc

Mer®legesség

2015-03-13

37 / 40



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

Mer®legesség

I D4 ∆8 = 4 I4 −D4

2015-03-13

38 / 40



∆ 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

Mer®legesség

O F2

2015-03-13

39 / 40


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


Mer®legesség

2015-03-13

40 / 40

40

Recommend Documents