Sie sind hier: Numerik > Numerik der linearen Algebra > Iterative Verfahren > Eigenwerte symmetrisch, positiv ...

Eigenwerte symmetrisch, positiv definiter Matrizen

Freitag 05. Januar 2007 von
Simon Praetorius
Eigenwertprobleme gehören zu einem wichtigen Anwendungsgebiet der Linearen Algera. Für Eigenwerte (EW) λ einer Matrix A mit zugehörigen Eigenvektoren (EV) v, gilt die Definition: λ ist EW von A ⇔ A*λ = v*λ. Zur Berechnung dieser Werte werden üblicherweise die Nullstellen des charakteristischen Polynoms det(A-λ*E) (für E = Einheitsmatrix) untersucht. In der Numerik verwendet man andere (iterative) Verfahren. Hier wird eines für den Spezialfall symmetrisch positiv-definiter tridiagonaler Matrizen beschrieben.
Für Matrizen mit den Eigenschaften "symmetrisch" und "positiv definit" gilt:
Wenn A ∈ ℝnxn, A=(aij)i,j=1...n positiv definit, dann folgt daraus:

1. A ist invertierbar
2. aii > 0 (i=1...n)
3. max |aij| = max aii

Es gibt sicher noch einige weitere Eigenschaften, die aus der positiv Definitheit folgen. Siehe dazu Wikipedia.

Im Folgenden möchte ich einen Spezialfall von Matrizen betrachten: Tridiagonale Matrizen, das sind Matrizen, die nur auf der Haupt und den ersten Nebendiagonalen Werte von Null verschieden stehen haben können. Der Rest der Matrix ist 0, oder etwas genau:
A ∈ ℝnxn ist tridiagonal ⇔ A=(aij)i,j=1...n mit aij=0 für |i-j|>1
Heinz Rutishauser, ein Schweizer Mathematik aus dem 20.Jh hat ein Verfahren entwickelt, um die Eigenwerte solcher Matrizen auszurechnen.

Algorithmus:
A0 = A
FÜR i=1,2,...
  Zerlege Ai in Ai = L*LT
  Ai+1 = LT*L
ENDE

Ergebnis: limk→∞ Ak = diag(λ1, ... λn)
Bei hinreichend langer Iteration entsteht eine Matrix, die auf der Hauptdiagonale die Eigenwerte hat und sonst nur Nullen. Die Zerlegung wird hier nach Cholesky vorgenommen. Die folgende Implementierung stammt von Florian Kuhlmann und mit freundliche Genehmigung darf ich sie hier veröffentlichen:

matlab Code
  • function [ a ] = rutishauser( a,b,prez )
  • %RUTISHAUSER - Verfahren zur Bestimmung von Eigenwerten symmetrischer positif definiter Matrizen
  • % Die Funktion ist fuer den Spezialfall tridiagonaler Matrizen implementiert.
  • % Aufruf: Eigenvalues = rutishauser(Hauptdiagonale,Nebendiagonale,Genauigkeit*);
  • % "Hautp-/Nebendiagonale" sind (Zeilen-)Vektoren mit den Elementen der jeweiligen Diagonale
  • % Genauigkeit ist ein optionaler Parameter, Standardgenauigkeit ist eps
  •  
  • if(nargin<3)
  • prez=eps;
  • end
  •  
  • % Nebendiagonale wird quadriert
  • b=[0 b.^2];
  • N=length(a);
  •  
  • while true
  •  
  • % Cholesky-Zerlegung in L*(L^T)
  • for k=1:N-1
  • a(k)=a(k)-b(k);
  • b(k+1)=b(k+1)/a(k);
  • end
  • a(N)=a(N)-b(N);
  •  
  • % (L^T)*L
  • for k=1:N-1
  • a(k)=a(k)+b(k+1);
  • b(k+1)=a(k+1)*b(k+1);
  • end
  • a(N)=a(N);
  •  
  • % jedes Element von b <= prez
  • % -->Diagonalgestalt erreicht
  • if(b<=prez)
  • break
  • end
  • end
  •  
  • % a ist Vektor mit Eigenwerten - wird zurueckgegeben

Das Besondere an der Implementierung ist, dass von vornherein die Nebendiagonalen quadriert werden und auch die Quadrate mitgeführt werden. Dadurch spart man bei der Implementierung der Cholesky-Zerlegung und der anschließenden Multiplikation zum Einen das Wurzelziehen und auch einige Quadraturen.
Besucher: 15269 | Permalink | Kategorie: Numerik
Tags: , , , ,

Kommentar hinzufügen

Dieses Feld bitten nicht ausfüllen: