Fourier-Matrix < Numerik < Hochschule < Mathe < Vorhilfe
|
Hallo!
Ich habe gelesen, dass die Fourier-Matrix [mm] T_n = (w^0,...,w^{n-1}) \in \IC^{nxn} [/mm] mit [mm] w^k = (w_n^{0k},...,w_n^{(n-1)k})^T [/mm] mit [mm] w_n=e^{i2 \pi / n} [/mm] nur n verschiedene Einträge hat, die in zyklischer Art angeordnet sind, weshalb die Multiplikation einen geringeren Aufwand hat als [mm] O(n^2).
[/mm]
Ich bin direkt mal über die "n verschiedenen Einträge" gestolpert. Ich bin darauf gekommen, dass [mm] T_n [/mm] symmetrisch ist, wodurch es statt [mm] n^2 [/mm] verschiedenen Einträgen nur n! verschiedene Einträge sind. Hier muss wohl die zyklische Anordnung noch eine Verringerung hervorrufen, aber das sagt mir nichts. Kann mir jemand weiter helfen?
Liebe Grüße, Lily
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 13:50 So 10.07.2016 | | Autor: | fred97 |
ich denke, dass es deine Einsicht beträchtlich erhöht,wenn du dir die Fälle n=2 und n=3 vornimmst. das sollte dann auch den allgemeinen Fall klären
fred
|
|
|
| |
|
Hallo!
Das habe ich schon gemacht. Dabei kommt raus:
[mm] T_2= \pmat{ w_2^0 & w_2^0 \\ w_2^0 & w_2^1 } [/mm] Hier sieht man: [mm] T_2 [/mm] ist symmetrisch und es kommen n=2 verschiedene Einträge vor
[mm] T_3= \pmat{ w_3^0 & w_3^0 &w_3^0 \\ w_3^0 & w_3^1 & w_3^2 \\ w_3^0 & w_3^2 & w_3^4 } [/mm] Hier ist das nicht mehr so eindeutig: [mm] T_3 [/mm] ist zwar symmetrisch, aber es gibt 4 verschiedene Einträge. Außer (könnte das sein?), wenn man [mm] w_3^k = w_3^{k mod 3} [/mm] setzt... dann wäre [mm] w_3^4=w_3^1 [/mm] und es würde wieder stimmen. Ist das mit der "zyklischen Art" gemeint?
Dann wäre es ja klar: es kann nur [mm] w_n^k [/mm] mit k [mm] \in [/mm] {0,...,n-1} geben und damit sind es genau n Einträge... ?
Liebe Grüße,
Lily
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 15:31 So 10.07.2016 | | Autor: | fred97 |
> Hallo!
>
> Das habe ich schon gemacht. Dabei kommt raus:
>
> [mm]T_2= \pmat{ w_2^0 & w_2^0 \\ w_2^0 & w_2^1 }[/mm] Hier sieht
> man: [mm]T_2[/mm] ist symmetrisch und es kommen n=2 verschiedene
> Einträge vor
>
> [mm]T_3= \pmat{ w_3^0 & w_3^0 &w_3^0 \\ w_3^0 & w_3^1 & w_3^2 \\ w_3^0 & w_3^2 & w_3^4 }[/mm]
> Hier ist das nicht mehr so eindeutig: [mm]T_3[/mm] ist zwar
> symmetrisch, aber es gibt 4 verschiedene Einträge. Außer
> (könnte das sein?), wenn man [mm]w_3^k = w_3^{k mod 3}[/mm]
> setzt... dann wäre [mm]w_3^4=w_3^1[/mm]
so ist es.
> und es würde wieder
> stimmen. Ist das mit der "zyklischen Art" gemeint?
ja
> Dann wäre es ja klar: es kann nur [mm]w_n^k[/mm] mit k [mm]\in[/mm]
> {0,...,n-1} geben und damit sind es genau n Einträge... ?
ja
fred
>
> Liebe Grüße,
> Lily
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 15:38 So 10.07.2016 | | Autor: | Mathe-Lily |
Aha! Danke 
|
|
|
|
