30
Polynome und schnelle Fourier-Transformation Mohsen Taheri FU Berlin – SoSe2012

Polynome und schnelle Fourier-Transformation

  • Upload
    elijah

  • View
    60

  • Download
    0

Embed Size (px)

DESCRIPTION

Polynome und schnelle Fourier-Transformation. Mohsen Taheri FU Berlin – SoSe2012. Polynome. Ein Polynom ist eine Funktion Koeffizienten: Ein Polynom hat Grad k wenn der höchste Koeffizient mit einem Wert ungleich 0 Länge = jede ganze Zahl großer als Grad eines Polynoms . - PowerPoint PPT Presentation

Citation preview

Page 1: Polynome und schnelle Fourier-Transformation

Polynome und schnelle Fourier-Transformation

Mohsen TaheriFU Berlin – SoSe2012

Page 2: Polynome und schnelle Fourier-Transformation

Polynome und FFT2

Polynome Ein Polynom ist eine Funktion

Koeffizienten: Ein Polynom hat Grad k wenn der höchste

Koeffizient mit einem Wert ungleich 0 Länge = jede ganze Zahl großer als Grad eines

Polynoms

1

0)( n

jj

jxaxA

jaka

1GradLänge

Page 3: Polynome und schnelle Fourier-Transformation

Polynome und FFT3

Addition von Polynomen Seien und

Polynome der Länge n Addition von A(x) und B(x) ist

hat auch Länge n und Beispiel

Laufzeit:

1

0)( n

jj

j xaxA

1

0)( n

jj

jxbxB

1

0)( n

jj

j xcxC

jjj bac

39228

)2325(51238234

2334

xxxx

xxxxxx

)(n

Page 4: Polynome und schnelle Fourier-Transformation

Polynome und FFT4

Multiplikation von Polynomen Seien und

Polynome der Länge n Multiplikation von A(x) und B(x) ist Wobei Länge(C) = Länge(A) + Länge(B)

Beispiel

Laufzeit:

1

0)( n

jj

j xaxA

1

0)( n

jj

jxbxB

22

0)( n

jj

jxcxC

45867520441412

182014123640282445503530

)542)(91076(

23456

345623423

323

xxxxxx

xxxxxxxxxxx

xxxxx

j

k kjkj bac0

)( 2n

Page 5: Polynome und schnelle Fourier-Transformation

Polynome und FFT5

Darstellung von Polynomen Koeffizienten-Darstellung Point-Value-Darstellung

Page 6: Polynome und schnelle Fourier-Transformation

Polynome und FFT6

Koeffizienten-Darstellung Das Polynom als ein Vektor

der Koeffizienten Addition:

Laufzeit

Multiplikation (wie vorhin): wobei

Laufzeit

1

0)( n

jj

j xaxA),...,( 11,0 naaaa

),...,,( 110 naaaa ),...,,( 110 nbbbb

),...,,( 111100 nn babababac

),...,,( 1210 ncccc j

k kjkj bac0

)(n

)( 2n

Page 7: Polynome und schnelle Fourier-Transformation

Polynome und FFT7

Point-Value-Darstellung Polynom Länge n in Point-Value-

Darstellung: eine Menge von Punkten alle sind disjunkt für alle :

Auswertung durch Horne-Schema (in )

1

0)( n

jj

j xaxA

)},(),...,,(),,{( 111100 nn yxyxyx

kx)( kk xAy 1,...,1,0 nk

)(n

))...))((...(()( 1020201000 nn axaxaxaxaxA

Page 8: Polynome und schnelle Fourier-Transformation

Polynome und FFT8

Addition in Point-Value-Darstellung A : B :

Addition:

Laufzeit:

)},(),...,,(),,{( 111100 nn yxyxyx)},(),...,,(),,{( 111100 nn yxyxyx

)},(),...,,(),,{( 111111000 nnn yyxyyxyyxBAC

)(n

Page 9: Polynome und schnelle Fourier-Transformation

Polynome und FFT9

Multiplikation in Point-Value-Darstellung Problem: Länge(A.B)=Länge(A)+Länge(B) Lösung: Extended Point-Value

2n Punkte statt n Punkte A: B:

Multiplikation: C:

Laufzeit :

)},(),...,,(),,{( 12121100 nn yxyxyx)},(),...,,(),,{( 12121100 nn yxyxyx

)},(),...,,(),,{( 121212111000 nnn yyxyyxyyx

)(n

Page 10: Polynome und schnelle Fourier-Transformation

Polynome und FFT10

Evaluation Evaluation: Transform von Koeffizienten-

Vektor zur Point-Value-Darstellung Evaluating: Die Auswertung eines Polynoms

unter einen bestimmten Wert von x Mit Hilfe von Horne-Schema in

Evaluation insgesamt in

)(n

)( 2n

Page 11: Polynome und schnelle Fourier-Transformation

Polynome und FFT11

Interpolation Interpolation: Transform von Point-Value-

Darstellung zur Koeffizienten-Darstellung Lagranges Formel

1

0))(/)(()( n

kkj

jkkj

jk xxxxyxA

Page 12: Polynome und schnelle Fourier-Transformation

Polynome und FFT12

Theorem 1: Eindeutigkeit von Interpolation der Polynomen Für alle Menge von n Punkten mit disjunkt gibt es ein eindeutiges Polynom A(x) der

Länge n, so dass für alle

)},(),...,,(),,{( 111100 nn yxyxyx

kx

)( kk xAy 1,...,1,0 nk

Page 13: Polynome und schnelle Fourier-Transformation

Polynome und FFT13

DFT effiziente Methode für Evaluation und

Interpolation Diskrete Fourier Transform

Das Polynom in n komplexe n-te Einheitswurzeln auswerten

Eingabe: Koeffizienten-Vektor Ausgabe: Vektor

Auswertung der Polynom in n Komplexe n-te Einheitswurzeln

),...,,( 110 naaaa)(aDFTy n

),...,,( 110 nyyyy

1

0)( n

jj

j xaxA

Page 14: Polynome und schnelle Fourier-Transformation

Polynome und FFT14

Komplexe Einheitswurzeln komplexe Einheitswurzel: eine komplexe Zahl

wobei

Es gibt genau n komplexe n-te Einheitswurzeln: für k=0,1, … , n-1:

Die Zahl : primitive n-te Einheitswurzel alle anderen Zahlen sind die Potenzen dieser Zahl

n komplexe n-te Einheitswurzeln sind dann:

1n

nikk e /2

nin e /2

1210 ,...,,, nnnnn

Page 15: Polynome und schnelle Fourier-Transformation

Polynome und FFT15

Komplexe Einheitswurzeln - Eigenschaften Additive Gruppe

Die n Zahlen haben die gleiche Struktur wie die additive Gruppe

Beweis:

1210 ,...,,, nnnnn

nn mod),(

nkjn

kjn

kn

jnn

nn

mod0 1

Page 16: Polynome und schnelle Fourier-Transformation

Polynome und FFT16

Komplexe Einheitswurzeln - Eigenschaften Cancellation Lemma Für jede ganze Zahl gilt:

Beweis: .

Korollar: Für alle ganze Zahlen n>0 gilt:

0 und 0 ,0 dknkn

dkdn

kn

knikdkdnidkdn ee )()( /2/2

122/ n

n

Page 17: Polynome und schnelle Fourier-Transformation

Polynome und FFT17

Komplexe Einheitswurzeln - Eigenschaften Halving Lemma: wenn n>0 gerade Zahl die Quadrate der n komplexen n -te

Einheitswurzeln sind die n/2 komplexe (n/2)-te Einheitswurzeln: },...,,{})(,...,)(,){( 12/

2/1

2/0

2/212120 n

nnnnnnn

Page 18: Polynome und schnelle Fourier-Transformation

Polynome und FFT18

Komplexe Einheitswurzeln - Eigenschaften Halving Lemma: Beweis: Da n gerade ist, nehmen wir an n=2m Zu zeigen: Nach Cancellation Lemma:

da , ist dann , also

},...,,{})(,...,)(,){( 1102122

212

202

mmmm

mmmm

},...,,,,...,,{},...,,{ 1211101210 mm

mm

mm

mmmm

mmmm

},...,,{

},...,,,,...,,{},...,,,,...,,{110

110110121110

mmmm

mmmm

mmmm

mm

mm

mm

mmmm

1mm j

mjm

m

},...,,{})(,...,)(,){( 12102122

212

202

mmmm

mmmm

Page 19: Polynome und schnelle Fourier-Transformation

Polynome und FFT19

Komplexe Einheitswurzeln - Eigenschaften Summation Lemma: Für jede ganze Zahl n≥1 und für k≠0 und

nicht dividierbar durch n, gilt: 0)(1

0

n

jjk

n

Page 20: Polynome und schnelle Fourier-Transformation

Polynome und FFT20

FFT Evaluation eines Polynoms in

unter Verwendung der Eigenschaften der Einheitswurzeln

Diese Methode heißt Fast Fourier Transform(FFT).

Annahme n ist ein 2er Potenz ( ) Divide-and-Conquer

)lg( nn

kn 2

Page 21: Polynome und schnelle Fourier-Transformation

Polynome und FFT21

FFT das Polynom A(x) in gerade und ungerade

indizierte Koeffizienten teilen zwei neue Polynome der

Länge n/2

Das Polynom wird so berechnet:

)(),( ]1[]0[ xAxA

12/1

2531

]1[

12/2

2420

]0[

...)(

...)(

n

n

nn

xaxaxaaxA

xaxaxaaxA

)()()( 2]1[2]0[ xxAxAxA

Page 22: Polynome und schnelle Fourier-Transformation

Polynome und FFT22

FFT das Problem von Auswerten des Polynoms in n

Punkten ( ) reduziert zu:

1. zwei Polynome der Länge n/2 in Punkten ( ) auswerten

2. das Resultat mit Hilfe der Abgleichung

zusammen addieren

212120 )(,...,)(,)( nnnn

110 ,...,, nnnn

)(),( ]1[]0[ xAxA

)()()( 2]1[2]0[ xxAxAxA

Page 23: Polynome und schnelle Fourier-Transformation

Polynome und FFT23

FFT Nach Halving Lemma:

die Anzahl der Elemente der Liste nicht n, sondern n/2.

Die zwei Subprobleme haben genau die gleiche Struktur wie das ursprüngliche Problem und sind halb so groß.

212120 )(,...,)(,)( nnnn

Page 24: Polynome und schnelle Fourier-Transformation

Polynome und FFT24

Rekursiv FFTRECURSIVE-FFT(a)1. n = a.length()2. if n==1 3. return a4. 5. 6. 7. 8. 9. 10. for k=0 to n/2-111. 12. 13. 14. return y

1

nin e /2

),...,,( 220]0[

naaaa

),...,,( 131]1[

naaaa)( ]0[]0[ aFFTRECURSIVEy )( ]1[]1[ aFFTRECURSIVEy

]1[]0[kkk yyy

]1[]0[)2/( kknk yyy

n

),...,,( 110 naaaa)(aDFTy n

Eingabe:Ausgabe:

Page 25: Polynome und schnelle Fourier-Transformation

Polynome und FFT25

Rekursiv FFT Zeilen11-12 kombinieren das Ergebnis der

rekursiven Berechnung Zeile 11 für

Zeile 12 für

zusammengefügt wird Vektor y berechnet

2/nDFT

12/10 ,..., nyyy)()()( 2]1[2]0[]1[]0[ k

nkn

kn

knk

knkk AAAyyy

112/2/ ,..., nnn yyy

)()()(

)()()2/(2]1[)2/(2]0[

2]1[)2/(2]0[

]1[2/]0[]1[]0[)2/(

nkn

nkn

nkn

nkn

kn

nkn

kn

knk

nkkknknk

AAA

AA

yyyyy

Page 26: Polynome und schnelle Fourier-Transformation

Polynome und FFT26

Rekursiv FFT - Laufzeit jeder rekursiver Aufruf kostet

n = Länge des Eingabevektors Laufzeit:

)(n

)lg()()2/(2)( nnnnTnT

Page 27: Polynome und schnelle Fourier-Transformation

Polynome und FFT27

Interpolation in Einheitswurzeln umgekehrtes Verfahren

Polynom vom Point-Value zurück zu Koeffizienten Berechnung von DTF als eine

Matrizenmultiplikation

Vandermonde-Matrix wir brauchen die Inverse-Matrix

)(1 yDFTa

1

3

2

1

0

)1)(1()1(3)(21

)1(3963

)1(2642

132

1

3

2

1

0

1

111

11111

)(

nnn

nn

nn

nnn

nnnnn

nnnnn

nnnnn

n a

aaaa

y

yyyy

aDFT

nV1

nV

yVaaVy nn .. 1

Page 28: Polynome und schnelle Fourier-Transformation

Polynome und FFT28

Inverse von Vandermonde-Matrix Theorem: Für j,k=0,1,…,n-1 sind die

(j,k)Einträge von die Zahlen Beweis:

z.z.: , wobei die n×n Identitätsmatrix betrachte die (j,j')Einträge von

Falls j=j‘ : Falls j≠j‘ :

-(n-1) ≤ j-j' ≤ n-1 j-j' ist nicht durch n dividierbar Summation Lemma :

1nV

nkjn /

nnn IVV 1nI

nn VV 1

1

0)'(1

0'

'1 )/())(/(][ n

kjjk

nn

kkjn

kjnjjnn nnVV

1)/(1

0)'(

n

kjjk

n n

0)/(1

0)'(

n

kjjk

n n

Page 29: Polynome und schnelle Fourier-Transformation

Polynome und FFT29

Interpolation in Einheitswurzeln I : (j,k)Einträge der sind: II :

Vergleiche mit Polynom in Einheitswurzeln leichte Modifikation in Algorithmus berechnet die

Interpolation tausche a und y ersetze durch dividiere jedes Element durch n

Also die Interpolation auch in berechenbar

yVa n .1nV kj

njkn /][ 1 1nV

1

0

1 n

kkjnkj y

naIII

1

0

n

kknkk ay

n 1n

)lg( nn

Page 30: Polynome und schnelle Fourier-Transformation

Polynome und FFT30

Zusammenfassung

221,0 ,..., nccc

)(),(

)(),(

)(),(

122

122

12

12

02

02

nn

nn

nn

nn

BA

BA

BA

Koeffizienten-Darstellung

Point-Value-Darstellung

)(

)(

)(

122

12

02

nn

n

n

C

C

C

Standard-Multiplikation

Laufzeit

EvaluationLaufzeit

InterpolationLaufzeit

punktweise Multiplikation

Laufzeit

)lg( nn)lg( nn

)( 2n

)(n

110

11,0

,...,,

,...,

n

n

bbb

aaa