Direkt zum Inhalt

Lexikon der Mathematik: Davidson-Verfahren

Verfahren zur Berechnung des k-ten Eigenwertes einer großen, sparsen, symmetrischen (n × n)-Matrix A.

Ausgehend von m orthonormalen Vektoren u1, …, um ∈ ℝn, mk, welche den Eigenraum zu den k größten Eigenwerten von A aufspannen, berechnet das Davidson-Verfahren:

bilde Um = [u1,u2, …, um] ∈ ℝn×m

berechne \({U}_{m}^{T}A|{U}_{m}\)

berechne die Eigenwerte λ1 ≥ λ2 ≥ … ≥ λm und zugehörige Eigenvektoren z1, …, zm von Hm wähle λk und den zugehörgen Eigenvektor xk aus

berechne z = Umxk

berechne r = Az – λkz

solange ||r|| ≠ 0 Wiederhole

berechne t = (diag(A) – λkI)–1r

orthonormiere t gegen u1, …, um und nenne das Ergebnis um+1

bilde Um+1 = [u1,u2, …,um+1]

berechne \({H}_{m+1}={U}_{m+1}^{T}A{U}_{m+1}\)

berechne die Eigenwerte λ1 ≥ λ2≥ … ≥ λm+1 und die zugehörigen Eigenvektoren von Hm+1

wähle λk und den zugehörgen Eigenvektor xk aus

berechne z = Umxk

berechne r = Az – λkz setze m = m + 1 ende Wiederhole

Die Zahl λk ist dann der gesuchte Eigenwert. Die in jedem Schritt erforderliche Orthonormalisierung kann mittels des Gram-Schmidt-Verfahrens oder mittels der QR-Zerlegung von [u1, u2, …, um, t] berechnet werden.

Soll anschließend der (k+1)-te Eigenwert berechnet werden, so bilden die ersten Spalten, > k+1 der bei der Berechnung von λk erzeugten Matrix Um häufig einen geeigneten Eigenraum.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.