8. Vorlesung, 21. Mai 2015 170 004 Numerische Methoden I Fouriertransform - mögliche Prüfungsfragen Eigenwerte und Eigenvektoren 1 Fouriertransform - mögliche Prüfungsfragen Fouriertransfomierte 3 2.5 • Im folgenden Bild ist die Fouriertransformierte abgebildet. Wie zugehörige könnte die Funktion aussehen: Amplitude 2 1.5 1 0.5 0 0 2 4 6 8 10 Omega • Können Sie den Begriff Alising erklären. 2 Eigenwerte und Eigenvektoren Es sei A eine n × n-Matrix, x ein vom Nullvektor verschiedener Vektor und λ ein Skalar. Erfüllen A, λ und x 6= 0 die Beziehung Ax = λx , so nennt man λ Eigenwert von A und x Eigenvektor von A zum Eigenwert λ. Anwendungen: Schwingungen, Hauptträgheitsachsen starrer Körper, Spannungstensor, Stabilitätstheorie, Hauptkomponentenanalyse, Quantenmechanik. . . 3 Eigenwerte und Eigenvektoren, anschaulich • Der Hauptberuf einer Matrix ist, Vektoren zu multiplizieren!“ ” • m × n- Matrix beschreibt allgemein lineare Abbildung Rn → Rm • y = Ax: Matrix, angewandt auf Vektor x, gibt neuen Vektor y. Der zeigt normalerweise in andere Richtung, hat andere Länge und eventuell sogar andere Dimension. • Jede n × n-Matrix hat aber ganz spezielle Eigenvektoren. Für sie ändert sich bei Multiplikation nur die Länge, aber die Richtung bleibt gleich (oder entgegengesetzt). • siehe Matlab-Demo EIGSHOW! 4 Beispiel: Erreichbarkeit in einem Netzwerk Ein Netzwerk (Verkehrsverbindungen, verlinkte Seiten im Internet, soziales Netz. . . , mathematisch: ein Graph) lässt sich durch seine Adjazenzmatrix beschreiben  10 2 11 6 9 5   A=   0 1 0 1 1 0 .. . 1 0 0 0 0 1 .. . 0 0 0 0 1 0 .. . 1 0 0 0 0 0 .. . 1 0 1 0 0 0 .. . 0 1 0 0 0 0 .. . 1 0 0 0 0 0 .. . 0 0 1 1 0 1 .. . ... ... ... ... ... ... ...       14 3 Welcher Knoten ist am besten erreichbar? 13 1 15 8 Internet: welche Seite listet Google als erste? 12 4 7 5 Beispiel: Erreichbarkeit in einem Netzwerk Eigenwertaufgabe Ax = λx −→ Der Eigenvektor x zum größtem Eigenwert λ liefert Bewertung!  10 2 11 6 9 5 14 3 13 1 15 8        x=        74 27 41 64 56 45 32 72 56 38 46 44 100 60 22                 12 4 7 6 Beispiel: Schwingungen der frei hängenden Kette 2 Das Eigenwertproblem A · x = ℓω x beschreibt die Schwingungsformen einer (idealing sierten) n-gliedrigen freihängenden Kette (Bild: erste und zweite Oberschwingung)  1 −1  A=   .. . 0 −1 3 −2 ··· ··· −2 5 −3 −3 7 ... ... ... 1−n 0 .. . 1−n 2n − 1       -0.4 -0.2 1 1 0.8 0.8 0.6 0.6 0.4 0.4 0.2 0.2 0.2 0.4 -0.4 -0.2 0.2 0.4 Schwingungen (Saiten, Membrane, Balken, Platten, Schall,. . . ) führen typischerweise zu Eigenwertaufgaben. 7 Methoden • Nullstellen im charakteristische Polynom bestimmen (klassisch, ineffizient bei voller Matrix, gut für Tridiagonalmatrix!) • Vektoriteration (langsam!), inverse Iteration • QR-Verfahren, Jacobi-Methode (Standard) • Lanczos-Verfahren (schwach besetzte Matrix) 8 MATLAB-Befehle eig und eigs: Beispiele d = eig(A) liefert Vektor von Eigenwerten [V,D] = eig(A) Spalten von V sind Eigenvektoren, Diagonalelemente von D sind Eigenwerte. d = eigs(A), d = eigs(A) analoge Befehle für schwach besetzte Matrizen. Liefern die sechs betragsgrößten Eigenwerte und zugeh. Eigenvektoren. 9 Eigenwerte und Eigenvektoren Wichtige Feststellungen zur Eigenwertaufgabe Ax = λx: • Eigenwerte sind Nullstellen des charakteristischen Polynoms det(A − λI) • Eine n × n-Matrix hat n reelle oder komplexe Eigenwerte (bei entsprechender Zählung) • Eigenwerte symmetrischer Matrizen sind immer reell. • ∀ Ew. λ von A gilt: λ + s Ew. von von A + sI (Verschiebung um s) 1/λ ist Ew. von A−1 . • X −1AX und A haben die gleichen Eigenwerte (Ähnlichkeitstransformation). • Symmetrische Matrizen sind durch orthogonale Transformation diagonalisierbar, A = QDQT . 10 Vektoriteration bestimmt den betragsgrößten Eigenwert Iterationsverfahren nach Richard von Mises und Hilda Pollaczek-Geiringer Gegeben eine n × n-Matrix A, ein Startvektor x(0) 6= 0 und ein fix gewähltes i ∈ {1, . . . , n} Iteriere für k = 1, 2, . . . berechne y(k) = Ax(k−1) (k) setze λ(k) = yi (i-te Komponente von y(k)) setze x(k) = y(k)/λ(k) (Skalierung) Falls ein reeller Eigenwert betragsmäßig größer ist als alle anderen Eigenwerte und ein zugehöriger Eigenvektor in Komponente i ungleich 0 ist, konvergieren die λ(k) und die x(k) . Varianten dieses Verfahrens verwenden unterschiedliche Skalierungsvorschriften. 11 Vektoriteration mit Inverser → betragskleinster Eigenwert Inverse Iteration mit Verschiebung → beliebige Eigenwerte Subtraktion von sI verschiebt Eigenwerte λ von A zu λ − s. Dadurch wird jener Eigenwert, der s am nächsten liegt, zum betragskleinsten von A − sI. Iteriere für k = 1, 2, . . . berechne y(k) als Lösung von (A − sI)y(k) = x(k−1) (k) setze µ(k) = yi (i-te Komponente von y(k)) setze x(k) = y(k)/µ(k) (Skalierung) Die Werte s + 1/µ(k) konvergieren gegen den am nächsten bei s liegenden Eigenwert von A, die Vektoren x(k) zu einem entsprechenden Eigenvektor. 12 Das QR-Verfahren bestimmt alle Eigenwerte einer Matrix A durch eine Folge orthogonaler Transformationen Iteriere bis zur Konvergenz berechne QR-Zerlegung A = Q · R setze A = R · Q (Ähnlichkeitstransform. A → QT · A · Q) Das Verfahren konvergiert (unter gew. Voraussetzungen und u.U. sehr langsam) zu einer Matrix in oberer Dreiecksform. Deren Hauptdiagonale enthält die Eigenwerte. Für den praktischen Einsatz wird das Verfahren durch gezielte Verschiebungen der Art Ã = A + sI beschleunigt. 13