From 47005c5fccd02f13fadc2202a539bc7ffbf7504a Mon Sep 17 00:00:00 2001 From: Adrian Kummerlaender Date: Wed, 2 Aug 2017 11:48:59 +0200 Subject: Start _Numerik 2_ digest wth section on Eigenvalues --- README.md | 2 +- common/commands.tex | 1 + content/numerik_2.tex | 123 ++++++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 125 insertions(+), 1 deletion(-) create mode 100644 content/numerik_2.tex diff --git a/README.md b/README.md index 21cc286..97a32c7 100644 --- a/README.md +++ b/README.md @@ -8,7 +8,7 @@ Zum Ende meines nunmehr schon dritten Semesters stehen zusätzlich Zusammenfassu Die resultierenden PDF der in _LaTeX_ gesetzten Quellen der [Analysis](https://static.kummerlaender.eu/media/ana12_zusammenfassung.pdf), [Lineare Algebra](https://static.kummerlaender.eu/media/la12_zusammenfassung.pdf), [Numerik 1](https://static.kummerlaender.eu/media/numa1_zusammenfassung.pdf) sowie [Analysis 3](https://static.kummerlaender.eu/media/ana3_zusammenfassung.pdf) Kurzzusammenfassungen stehen auf meiner Webseite zum Download bereit. -Zusammenfassungen der Vorlesungen _Einführung in die Algebra und Zahlentheorie_, _Markov-Ketten_ sowie _Analysis IV (Funktionentheorie, Gewöhnliche DGL)_ sind in Arbeit. +Zusammenfassungen der Vorlesungen _Einführung in die Algebra und Zahlentheorie_, _Markov-Ketten_, _Analysis IV (Funktionentheorie, Gewöhnliche DGL)_ sowie _Numerik 2 (Eigenwerte, Nichtlineare Gleichungen, Integration)_ sind in Arbeit. ## Generierung diff --git a/common/commands.tex b/common/commands.tex index 0162f8e..9954560 100644 --- a/common/commands.tex +++ b/common/commands.tex @@ -1,4 +1,5 @@ \newcommand{\R}{\mathbb{R}} +\newcommand{\C}{\mathbb{C}} \newcommand{\N}{\mathbb{N}} \newcommand{\K}{\mathbb{K}} \newcommand{\Q}{\mathbb{Q}} diff --git a/content/numerik_2.tex b/content/numerik_2.tex new file mode 100644 index 0000000..1e6559b --- /dev/null +++ b/content/numerik_2.tex @@ -0,0 +1,123 @@ +\section*{Eigenwerte} + +Sei $A \in \C^{n \times n}$. Ein $\lambda \in \C$ ist \emph{Eigenwert} von $A$, wenn $\exists v \in \C^n\setminus\{0\} : Av = \lambda v$. + +\subsection*{Satz von Gerschgorin} + +$$\mathcal{K}_i := \left\{ z \in \C \middle| |z-a_{i,i}| \leq \sum_{k=1, k\neq i}^n |a_{i,k}| =: r_i \right\}, \ 1 \leq i \leq n$$ + +Die Vereinigung der Kreisscheiben $\mathcal{K}_i$ enthält alle Eigenwerte von $A \in \C^{n \times n}$: $\sigma(A) \subset \bigcup_{i=1}^n \mathcal{K}_i$ + +\spacing + +Ist $M_1 = \bigcup_{j=1}^k \mathcal{K}_{i_j}$ disjunkt von der Vereinigung $M_2$ der übrigen Kreise, so enthält $M_1$ genau $k$ und $M_2$ genau $n-k$ Eigenwerte gezählt entsprechend der algebraischen Vielfachheit. + +\subsection*{Störung des Eigenwertproblems} + +Sei $A$ diagonalisierbar mit $A= TDT^{-1}$, $\Delta A \in \C^{n \times n}$ beliebig: $\forall \lambda(A+\Delta A) \in \sigma(A+\Delta A) \ \exists \lambda(A) \in \sigma(A) : |\lambda(A+\Delta A) - \lambda(A)| \leq \kappa_p(T) \|\Delta A\|_p$ mit $1 \leq p \leq \infty$. + +\spacing + +Entsprechend lautet die Kondition der Bestimmung von Eigenwerten $\lambda \neq 0$ bzgl. der $p$-Norm: + +$$\kappa_p(\lambda) \leq \frac{\|A\|_p}{|\lambda|} \kappa_p(T)$$ + +\subsection*{Mögliche Eigenwertlöser} + +Das Eigenwertproblem ist äquivalent zur Bestimmung der Nullstellen des char. Polynoms. + +Nach dem \emph{Satz von Abel} existiert für Polynome von Grad $\geq 5$ bzw. Matrizen von Dimension $\geq 5\times5$ kein exakt arbeitender Eigenwertlöser welcher in endlicher Zeit die Eigenwerte bestimmt. + +d.h. alle Eigenwertlöser sind iterativ. + +\subsection*{Potenzmethode} + +In $A^k$ dominiert der betragsgrößte Eigenwert und diese Dominanz nimmt mit $k$ zu. Somit ist an $A^k v$ der betragsgrößte Eigenwert ablesbar. + +Für $k = 1, 2, \dots$ und Startvektor $x^0 \in \C^n$: + +\vspace*{-2mm} +$$z^k := Ax^{k-1}, \ x^k := \frac{z^k}{\|z^k\|}$$ + +Der approx. betragsgrößte Eigenwert ergibt sich: + +\vspace*{-2mm} +$$\tilde\lambda = \langle Ax^k,x^k \rangle_2$$ + +Potenzmethode konvergiert nicht zwingend gegen einen EV des betragsgrößten EW sondern hat Häufungspunkte welche EV zu diesem EW sind. + +\subsubsection*{Inverse Potenzmethode} + +Die Konvergenzgeschwindigkeit der Potenzmethode hängt von $|\frac{\lambda_{r+1}}{\lambda_1}|$, also dem Quotienten des ersten nicht betragsmaximalen Eigenwerts und des betragsmaximalen Eigenwertes ab. + +Langsame Konvergenz liegt bei $|\frac{\lambda_{r+1}}{\lambda_1}| \approx 1$ vor. + +\spacing + +Sei $\tilde\lambda$ Schätzwert für $\lambda_i \in \sigma(A)$ d.h. $|\tilde\lambda - \lambda_i| < |\tilde\lambda - \lambda_j|, \ j \neq i$. Die inverse Potenzmethode: + +\vspace*{-2mm} +$$(A-\tilde\lambda Id_n)z^k = x^{k-1}, \ x^k = \frac{z^k}{\|z^k\|_2}$$ + +Zur Lösung des linearen Systems wird die LR-Zerlegung von $A- \tilde\lambda Id_n$ bestimmt. Konvergenz: + +\vspace*{-2mm} +$$\lim_{k\to\infty} \langle Ax^k,x^k \rangle_2 = \lambda_i$$ + +Wird die Approximation $\tilde\lambda$ in jedem Iterationsschritt durch die gefundene Approx. verbessert, so approx. das Verfahren einen EV zum EW $\lambda_i$. + +\subsection*{Hessenberg- / Tridiagonalgestalt} + +Eigenwertlöser beginnen i.A. mit der Äquivalenz-umformung von $A \in \C^{n \times n}$ in obere Hessenberg- bzw. Tridiagonalgestalt $\mathcal{H}$. Danach wird $\mathcal{H}$ in eine obere Dreiecks- bzw. Diagonalmatrix äquivalent umgeformt. Die Hauptdiagonale einer solchen Matrix besteht dann aus den Eigenwerten von $A$. + +\subsection*{QR-Algorithmus} + +Sei $A = QR$ eine QR-Zerlegung von $A \in \R^{n \times n}$. + +Eine \emph{QR-Transformation} ist $A \mapsto A':=RQ$. + +\spacing + +$A'$ ist orthogonalähnlich zu $A$ und $\sigma(A) = \sigma(A')$. + +Ist $A$ eine obere Hessenberg- oder symmetrische Tridiagonalmatrix, so hat $A'$ dieselbe Struktur. + +\spacing + +Transformiere $A$ in obere Hessenberg- bzw. symmetrische Tridiagonalgestalt. Setze dann $A_0 := A$ und iteriere: + +$A_k =: Q_kR_k, \ A_{k+1} := R_kQ_k$ für $k = 0,1,2,\dots$. + +\subsubsection*{QR-Identitäten} + +Sei $A \in \R^{n \times n}$. Dann gelten für $\{A_k\}_k$: + +\begin{enumerate}[label=(\alph*)] + \item $A_{k+1} = Q_k^T A_k Q_k$ + \item $A_{k+1} = Q_{k+1}^T A Q_{k+1}$ mit $Q_{k+1} := Q_0 \cdots Q_k$ + \item $A^{k+1} = Q_{k+1} R_{k+1}$ mit $R_{k+1} := R_k \cdots R_0$ +\end{enumerate} + +Diese begründen den Zusammenhang von QR-Algorithmus und Potenzmethode. + +\subsubsection*{QR mit Spektralverschiebung} + +Der ursprüngliche QR-Algorithmus konvergiert langsam. Dies lässt sich mit Anwendung auf $\tilde A = A - \mu I_n$ (Shift / Spektralverschiebung) verbessern. + +\spacing + +Transformiere $A$ in obere Hessenberg- bzw. symmetrische Tridiagonalgestalt. Setze dann $A_0 := A$ und iteriere: $A_k - \mu_k I_n =: Q_kR_k, \ A_{k+1} := R_kQ_k + \mu_k I_n$ für $k = 0,1,2,\dots$. + +\spacing + +Bewährte Shift-Strategie: $\mu_k := (A_k)_{nn}$ + +$|(A_{k+1})_{n,n-1}| \leq c |(A_k)_{n,n-1}|^2$ (quadratische Konv.) + +\subsubsection*{Bestimmung der Eigenvektoren} + +Auf die obere Hessenberg-Form $A_0 = P^T A P$ lässt sich die inverse Potenzmethode mit den berechneten Eigenwertnäherungen als Schätzwert anwenden. Das auftretende LGS $A_0 - \tilde\lambda I_n$ lässt sich effizient mit $n-1$ Givens-Rotationen lösen. + +\section*{Nichtlineare Gleichungssysteme} + +\section*{Numerische Integration} -- cgit v1.2.3