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.