[Numerik I] - Übung 7 *

23.01.2009, 21:59	tigerbine	Auf diesen Beitrag antworten »
[Numerik I] - Übung 7 * Diskrete Fourriertransformation und inverse Fourriertransformation Multiplikation komplexer Zahlen trigonometrische Polynome Schnelle Matrixmultiplikation nach Strassen
23.01.2009, 22:52	tigerbine	Auf diesen Beitrag antworten »
7.1 Diskrete Fouriertransformation Zunächst einmal sollten die Begriffe geklärt werden. Ein Interpolationspolynom vom Grad (n-1) ist durch die Angabe von n Funktionswerten an n Stützstellen eindeutig bestimmt. $\begin{eqnarray} V \end{eqnarray}$ ist die Vandermonde-Matrix $\begin{eqnarray} \alpha \end{eqnarray}$ sind die Knoten, an denen interpoliert wird. $\begin{eqnarray} \beta \end{eqnarray}$ sind die Koeffizienten des Polynoms und $\begin{eqnarray} f \end{eqnarray}$ sind die Funktionswerte des Polynoms in den Knoten. FFI - Bestimmung das interpolierende Polynom zu den Wertepaaren $\begin{eqnarray} \beta = \frac{1}{n} V(\alpha^{-1}) f \end{eqnarray}$ Gehen wir nun einmal beide Wege. Unter der diskreten FouriertransformationI würde man das Matrix-Vektor-Produkt verstehen. $\begin{eqnarray} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 1&1&1&1 \\ w_4^{-0} & w_4^{-1} &w_4^{-2} & w_4^{-3} \\ w_4^{-0} & w_4^{-2} &w_4^{-4} & w_4^{-6} \\ w_4^{-0} & w_4^{-3} &w_4^{-6} & w_4^{-9} \end{pmatrix}\begin{pmatrix} f_0\\f_1\\f_2\\f_3\end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 1&+1&+1&+1 \\ 1 & -i & -1 & +i \\ 1 & -1 & +1 & -1 \\ 1 &+ i &-1 & -i \end{pmatrix}\begin{pmatrix} f_0\\f_1\\f_2\\f_3\end{pmatrix} \end{eqnarray}$ Damit ergibt sich für die konkrete Angabe hier $\begin{eqnarray} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix} = \frac{1}{4} \begin{pmatrix} 1&+1&+1&+1 \\ 1 & -i & -1 & +i \\ 1 & -1 & +1 & -1 \\ 1 &+ i &-1 & -i \end{pmatrix}\begin{pmatrix} +0\\+1\\+2\\-1 \end{pmatrix} = \frac{1}{2} \begin{pmatrix} 1\\-1-i\\1\\-1+i\end{pmatrix} \end{eqnarray}$ Nun das ganze mit dem IFFT-Algorithmus: $\begin{eqnarray} \begin{array} {\|c\|\|c\|c\|c\|\|c\|} \hline \text{j} & f_j & f_j^{(1)} & f_j^{(2)} & \text{k} \\ \hline \hline 0 & 0& 2& 2 & 0 \\ \hline 1 &1 & 0 & 2& 2 \\ \hline 2 & 2& -2 & -2-2i & 1\\ \hline 3 & -1& 2\omega_4^{-1} & -2+2i & 3 \\ \hline \end{array} \end{eqnarray}$ Nach der bit-Umkehr und Division durch 4 erhalten wir also die gesuchte Lösung: $\begin{eqnarray} \frac{1}{2} \begin{pmatrix} 1\\-1-i\\1\\-1+i\end{pmatrix} \end{eqnarray}$ FFT - Auswertung des Interpolationspolynom in den Knoten $\begin{eqnarray} V(\alpha) \beta = f \end{eqnarray}$ Wieder wollen wir beide Wege gehen. Unter der diskreten Fouriertransformation würde man das Matrix-Vektor-Produkt verstehen. $\begin{eqnarray} \begin{pmatrix} f_0\\f_1\\f_2\\f_3\end{pmatrix}= \begin{pmatrix} 1&1&1&1 \\ w_4^{0} & w_4^{1} &w_4^{2} & w_4^{3} \\ w_4^{0} & w_4^{2} &w_4^{4} & w_4^{6} \\ w_4^{0} & w_4^{3} &w_4^{6} & w_4^{9} \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix} \end{eqnarray}$ $\begin{eqnarray} \begin{pmatrix} f_0\\f_1\\f_2\\f_3\end{pmatrix}= \begin{pmatrix} 1&1&1&1 \\ 1&+i&-1&-i \\ 1&-1&+1&-1 \\ 1&-i&-1&+i \end{pmatrix} \begin{pmatrix} a_0 \\ a_1 \\ a_2 \\ a_3 \end{pmatrix} \end{eqnarray}$ Damit ergibt sich für die konkrete Angabe hier $\begin{eqnarray} \begin{pmatrix} f_0\\f_1\\f_2\\f_3\end{pmatrix}= \begin{pmatrix} 1&1&1&1 \\ 1&+i&-1&-i \\ 1&-1&+1&-1 \\ 1&-i&-1&+i \end{pmatrix} \begin{pmatrix} 1 \\ -1 \\ i\\ -i \end{pmatrix} = \begin{pmatrix} 0 \\ -2i \\ 2+2i \\ 2 \end{pmatrix} \end{eqnarray}$ Nun das ganze mit dem FFT-Algorithmus: $\begin{eqnarray} \begin{array} {\|c\|\|c\|c\|c\|\|c\|} \hline \text{j} & \beta_j & \beta_j^{(1)} & \beta_j^{(2)} & \text{k} \\ \hline \hline 0 & 1& 1+i & 0 & 0 \\ \hline 1 & -1 & -1-i & 2+2i & 2 \\ \hline 2 & i & 1-i & -2i & 1\\ \hline 3 & -i & (-1+i)\omega_4 & -1-i & 3 \\ \hline \end{array} \end{eqnarray}$ Nach der bit-Umkehr erhalten wir also die gesuchte Lösung: $\begin{eqnarray} \begin{pmatrix} 0 \\ -2i \\ 2+2i \\ 2 \end{pmatrix} \end{eqnarray}$
24.01.2009, 01:02	tigerbine	Auf diesen Beitrag antworten »
7.2 Multiplikation komplexer Zahlen Notieren wir uns das Pordukt zunächst unter der Verwendung des Distribitivgesetzes: $\begin{eqnarray} f(x)g(x)=\underbrace{ac}_{1}x^2 + (\underbrace{ad}_{3} +\underbrace{bc}_{4})x + \underbrace{bd}_{2} \end{eqnarray}$ Wir werden um (1)(2) nicht herum kommen, also müssen wir versuchen (3)(4) auf diese zurückzuführen. Dies gelingt wie folgt: $\begin{eqnarray} (a+b)(c+d)=ac+ad+bc+db \end{eqnarray}$ $\begin{eqnarray} ad + bc = \underbrace{(a+b)(c+d)}_{3}-ac-bd \end{eqnarray}$
24.01.2009, 12:43	tigerbine	Auf diesen Beitrag antworten »
7.3 trig. Polynome Betrachten wir das trig. Polynom $\begin{eqnarray} p(x):=\sum_{k=0}^n~\alpha_k \cdot \exp(i \cdot kx) \end{eqnarray}$ Dies werten wir in den äquidistanden Stützstellen aus: $\begin{eqnarray} x_j=\frac{j}{n+1}\cdot 2\pi,~j=0,...,n \end{eqnarray}$ So ergibt sich für das Polynom p eine Darstellung mit den (n+1)-ten Einheitswurzeln: $\begin{eqnarray} p(x_j):=\sum_{k=0}^n~\alpha_k \cdot \exp(i \cdot kx_j) =\sum_{k=0}^n~\alpha_k \cdot \omega_{n+1}^{kj} \end{eqnarray}$ Unter Abschnittspolynomen wollen wir folgendes verstehen: $\begin{eqnarray} p_s(x)=\sum_{k=0}^s~\alpha_k \cdot \exp(i \cdot kx),\quad q(x)=\sum_{k=0}^s~\beta_k \cdot \exp(i \cdot kx) \end{eqnarray}$ Auch diese werten wir in obigen Stellen aus und erhalten: $\begin{eqnarray} p_s(x_j)=\sum_{k=0}^s~\alpha_k \cdot \omega_{n+1}^{kj},\quad q(x_j)=\sum_{k=0}^s~\beta_k \cdot \omega_{n+1}^{kj}, \quad j=0,...,n \end{eqnarray}$ Nun interessieren wir uns für die Fehlerquadratsumme in diesen Stellen: $\begin{eqnarray} S(q):=\sum_{j=0}^n ~\\|p(x_j)-q(x_j)\\|^2 \end{eqnarray}$ Dabei gilt für die einzelnen Summanden: $\begin{eqnarray} \\|p(x_j)-q(x_j)\\|^2 = \langle p(x_j)-q(x_j), p(x_j)-q(x_j) \rangle \end{eqnarray}$ Die Behauptung folgt aus der Orthogonalität der Einheitswurzeln.
24.01.2009, 14:36	tigerbine	Auf diesen Beitrag antworten »
7.4 Schnelle Matrixmultiplikation nach Strassen - Teil 1 Bilden wir das Produkt der Blockmatrizen, so erhalten wir: $\begin{eqnarray} C_{11} = A_{11}B_{11} + A_{12}B_{21},\quad \quad C_{12} = A_{11}B_{12} + A_{12}B_{22} \end{eqnarray}$ $\begin{eqnarray} C_{21} = A_{21}B_{11} + A_{22}B_{21},\quad \quad C_{22} = A_{21}B_{12} + A_{22}B_{22} \end{eqnarray}$ Nun überprüfen wir durch Einsetzen die Identitäten: $\begin{eqnarray} C_{11} && = Q_1+Q_4-Q_5+Q_7 \\ && = (A_{11}+A_{22})(B_{11}+B_{22}) + A_{22}(-B_{11}+B_{21})-(A_{11}+A_{12})B_{22} + (A_{12}-A_{22})(B_{21}+B_{22}) \\&& = A_{11}B_{11} + A_{11}B_{22} + A_{22}B_{11} + A_{22}B_{22} - A_{22}B_{11} +A_{22}B_{21} -A_{11}B_{22} - A_{12}B_{22} + (A_{12}-A_{22})(B_{21}+B_{22}) \\&& =A_{11}B_{11} +A_{22}B_{22}+A_{22}B_{21}-A_{12}B_{22} + A_{12}B_{21} + A_{12}B_{22} - A_{22}B_{21} - A_{22}B_{22} \\&& =A_{11}B_{11} + A_{12}B_{21} \end{eqnarray}$ $\begin{eqnarray} C_{12} && = Q_1 + Q_5 \\ &&= A_{11}(B_{12}-B_{22}) + (A_{11}+A_{12})B_{22} \\ && = A_{11}B_{12} - A_{11}B_{22} + A_{11}B_{22} + A_{12}B_{22} \\&& =A_{11}B_{12}+A_{12}B_{22} \end{eqnarray}$ $\begin{eqnarray} C_{21} && = Q_2 + Q_4 \\&& = (A_{21}+A_{22})B_{11} + A_{22}(-B_{11}+B_{21}) \\&& = A_{21}B_{11}+A_{22}B_{11} -A_{22}B_{11}+A_{22}B_{21} \\&& = A_{21}B_{11} +A_{22}B_{21} \end{eqnarray}$ $\begin{eqnarray} C_{22} && = Q_1+Q_3-Q_2+Q_6 \\&& = (A_{11}+A_{22})(B_{11} + B_{22}) +A_{11}(B_{12}-B_{22})-(A_{21}+A_{22})B_{11}+(-A_{11}+A_{21})(B_{11}+B_{12}) \\&& = A_{21}B_{12} + A_{22}B_{22} \end{eqnarray}$
25.01.2009, 00:43	tigerbine	Auf diesen Beitrag antworten »
7.4 Schnelle Matrixmultiplikation nach Strassen - Teil 2 In der Aufgabenstellung sind $\begin{eqnarray} k \times k \end{eqnarray}$ durch $\begin{eqnarray} (k-1) \times (k-1) \end{eqnarray}$ zu ersetzen. Wie gut ist nun dieser Algorithmus. Betrachten wir die Multiplikation zweier 2x2 Matrizen. $\begin{eqnarray} \begin{pmatrix}a_{11} & a_{12} \\ a_{21} & a_{22} \end{pmatrix}\begin{pmatrix} b_{11} & b_{12} \\ b_{21} & b_{22} \end{pmatrix} = \begin{pmatrix} c_{11} & c_{12} \\ c_{21} & c_{22} \end{pmatrix} \end{eqnarray}$ Würde man dies konventionell tun, so wären 8 Multiplikationen und 4 Additionen nötig. Mit dem Schema von Strassen ergeben sich für die Berechnung der Qs 10 Additionen und 7 Multiplikationen. Für die Berechnung der Cs kommen dann noch 8 Additionen hinzu. Unterm Strich ergeben sich also 25 Skalaroperationen (18 Additionen und 7 Multiplikationen). Somit kommen wir für k=1 auf den Wert der angegeben Formel. Wie würde man nun bei einer 4x4 Matrix vorgehen? Sobald wir auf ein Matrixprodukt treffen, greifen wir auf den um 1 reduzierten Algorithmus zurück. So ergeben sich für die Q Matrizen folgende Operationen: $\begin{eqnarray} 7 \cdot [25] + 10 \cdot [2]^2 \end{eqnarray}$ Für die Matrizen C ergibt sich ein Aufwand von: $\begin{eqnarray} 8 \cdot [2]^2 \end{eqnarray}$ Somit erzielen wir auch auf diese Rechenweise den Wert $\begin{eqnarray} S(2^2)=247 =7 \cdot [25] + 18 \cdot [2]^2 \end{eqnarray}$ Ohne weiteres können wir diese Vorgehensweise für den Induktionsschluss verwenden. Sei also die Formel richtig für (k-1), so ergibt ich der Wert der Wert für k wie folgt: $\begin{eqnarray} 7 \cdot [S(2^{k-1})] + 18\cdot [2^{k-1}]^2 &&= 7\cdot [7\cdot(2^{k-1})^{\log_2(7)} -6\cdot (2^{k-1})^2] + 18\cdot [2^{k-1}]^2 \\ &&= 7 \cdot (2^k)^{\log_2(7)} - 6 \cdot (2^k)^2 \end{eqnarray}$ Ab wann nutzt das Verfahren? $\begin{eqnarray} S(n)=7(n)^{\log_2(7)} - 6n^2 \end{eqnarray}$ $\begin{eqnarray} M(n)=n^3 + n^2(n-1) = 2n^3+n^2 \end{eqnarray}$ $\begin{eqnarray} 7(n)^{\log_2(7)} - 6n^2 < 2n^3+n^2 \end{eqnarray}$ $\begin{eqnarray} 7(n)^{\log_2(7)} < 2n^3+ 7n^2 \end{eqnarray}$ $\begin{eqnarray} n>655 \end{eqnarray}$
Anzeige

30.01.2009, 23:02	tigerbine	Auf diesen Beitrag antworten »
Hier geht es weiter: [Numerik I] - Übung 8 *

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »