10.5 Idee des Verfahrens von Jacobi und Givens

Idee des Verfahrens von Jacobi und Givens
174
10.5
Idee des Verfahrens von Jacobi und Givens
10.5.1
Vorüberlegung
Wir betrachten eine reell-symmetrische 2 × 2-Matrix
a11 a12
A=
mit a12 = a21 und aij ∈ IR .
a21 a22
Wir wollen jetzt eine Ähnlichkeitstransformation mit einer Rotationsmatrix
cos ϕ − sin ϕ
c −s
Ω12 =
=
sin ϕ cos ϕ
s c
durchführen. Die Matrix Ω12 ist unitär, also ist
c s
∗
−1
Ω12 = Ω12 =
.
−s c
Die Idee ist dabei, ϕ so zu bestimmen, daß
0
a11 0
∗
Ω12 AΩ12 =
0 a022
gilt. Dies bedeutet gerade
a011 = c2 a11 + s2 a22 + 2csa12
a021 = a012 = −cs(a11 − a22 ) + (c2 − s2 )a12 = 0
a022
2
(10.21)
2
= s a11 + c a22 − 2csa12 ,
und dies wird erreicht für
tan 2ϕ =
10.5.2
2cs
2a12
=
2
−s
a11 − a22
c2
(|ϕ| ≤
π
)
4
(10.22)
Der allgemeine reell-symmetrische Fall
Sei jetzt A ∈ IRN,N reell-symmetrisch. Dann betrachten wir die Ähnlichkeitstransformation
A(n+1) = Ω∗jk A(n) Ωjk
Idee des Verfahrens von Jacobi und Givens
175
mit

Ωjk










=










1
..
0
.










 ,









1
−s
c
1
..
.
1
s
c
1
..
0
.
1
wobei nur in der j-ten und k-ten Zeile mit Einträgen jeweils in der j-ten und
k-ten Spalte von der Einheitsmatrix verschiedene Elemente auftauchen. Im
folgenden benutzen wir der Einfachheit halber die Bezeichnungen
A(n) = A = (aij )
A(n+1) = A0 = (a0ij ) .
Damit können wir A(n+1) schreiben als
 0
a11 · · · a01j · · ·
..
 ..
..
 .
.
.
 0
 aj1 · · · a0jj · · ·


..
(n+1)
A
=  ...
···
.
···
 0
0
 a
 k1 · · · akj · · ·
 .
..
 ..
···
.
···
a0N 1 · · · a0N j · · ·
a01k
..
.
···
a0jk
..
.
···
a0kk
..
.
···
···
..
.
a0N k · · ·

a01N
.. 
. 

0
ajN 

..  .
. 

0
akN 

.. 
. 
0
aN N
Wir interessieren uns jetzt für die j-te und k-te Zeile und Spalte von A(n+1) ,
denn Ωjk verändert gegenüber A(n) nur diese beiden Zeilen und Spalten.
Das Ziel der Transformation ist es, a0jk = 0 und a0kj = 0 zu erhalten. Für
j 6= r 6= k hat man
a0jr = a0rj
= carj + sark
a0rk
= −sarj + cark
=
a0kr
Idee des Verfahrens von Jacobi und Givens
176
sowie die Beziehungen (10.21) mit
a0jj statt a011 ,
a0kk statt a022 ,
a0jk statt a012 ,
und dem Winkel ϕ wie in (10.22) bzw. (“stabiler”)
ϑ = cot 2ϕ =
10.5.3
a11 − a22
2a12
(10.23)
Verfahrensablauf
Das Verfahren besteht darin, derartige Ωjk -Schritte durchzuführen, z.B. in
der Reihenfolge
Ω12 , Ω13 , · · ·
Ω1N
Ω23 , · · ·
Ω2N
..
..
.
.
ΩN −1,N
mit zyklischer Wiederholung. Letztere ist notwendig, weil die in den vorangegangenen Schritten erzeugten Nullen nicht erhalten bleiben.
10.5.4
Aussagen zur Konvergenz
Bei zyklischer Wiederholung der Schritte gilt

λ1

(n)
..
A →D=
.
0
0


 .
λN
Die Quadratsumme der Nichtdiagonalelemente
X (n)
S(A(n) ) =
|ajk |2
j6=k
ist ein Maß für die Konvergenz dieses Verfahrens gegen eine Diagonalmatrix.
Aus den Formeln in Abschnitt 10.5.2 folgt sofort
(n)
0 ≤ S(A(n+1) ) = S(A(n) ) − 2|ajk |2 ≤ S(A(n) ) .
Wir haben also eine monoton fallende Folge.
Ohne Beweis vermerken wir:
• Es gilt S(A(n) ) → 0.
Idee des Verfahrens von Jacobi und Givens
177
• Unter besonderen Umständen (A hat nur einfache Eigenwerte) erhält
man sogar quadratische Konvergenz
S(A(n+m) ) ≤
(S(A(n) ))2
δ
mit m = N (N2−1) (dies entspricht gerade einem Durchlauf, vgl. Abschnitt 10.5.3) und mit
δ = min |λi (A) − λj (A)| > 0 .
i6=j
Eine Variante dieses Verfahrens besteht darin, die Schritte nicht in einer festen Reihenfolge mit zyklischer Wiederholung durchzuführen, sondern stattdessen jeweils das betragsgrößte Element ajk mit j 6= k zu Null zu machen.
Dieser Ansatz führt zu einer Konvergenzbeschleunigung.
10.5.5
Verfahren von Givens
Das Verfahren von Givens ist ein finites Verfahren. Es beruht auf der gleichen
Idee wie das Jacobi-Verfahren (Ähnlichkeitstransformationen durch Rotationen), aber hier sorgt man dafür, daß einmal erzeugte Nullen nicht wieder ungleich Null werden. Damit besteht das Verfahren (im Gegensatz zum
Jacobi-Verfahren) nur aus endlich vielen Schritten. Bei diesem Verfahren
gelangt man allerdings nicht zu einer Diagonalmatrix, sondern nur zu einer
Tridiagonalmatrix. Die Reihenfolge der Rotationen bei diesem Verfahren ist
Ω23 , Ω24 , · · ·
Ω34 , · · ·
..
.
Ω2N
Ω3N
..
.
.
ΩN −1,N
Allerdings wird hier durch die Transformation mit Ωjk nicht das Element ajk
zu Null transformiert, sondern (durch geeignete Wahl von ϕ) das Element
ak,j−1 und damit auch aj−1,k (im reell-symmetrischen Fall).
Beispiel 10.1 Als Beispiel betrachten

a11 a12
 a21 a22
A=
 a31 a32
a41 a42
wir den Fall einer 4 × 4-Matrix

a13 a14
a23 a24 
 .
a33 a34 
a43 a44
Idee des Verfahrens von Jacobi und Givens
178
Die Reihenfolge der Rotationen ist dann
Ω23 , Ω24
Ω34
.
Durch die Transformation mit Ω23 werden die Matrixelemente a31 und a13
auf Null gebracht, Ω24 führt dann auf eine Matrix der Gestalt


∗ ∗ 0 0
 ∗ ∗ ∗ ∗ 


 0 ∗ ∗ ∗ 
0 ∗ ∗ ∗
und Ω34 bringt dies dann auf Tridiagonalgestalt


∗ ∗ 0 0
 ∗ ∗ ∗ 0 


 0 ∗ ∗ ∗  ,
0 0 ∗ ∗
da die einmal erzeugten Nullen erhalten bleiben.
Allgemein entsteht bei diesem Verfahren im Sinne der obigen Reihenfolge
−2)
eine Tridiagonalmatrix nach (N −1)(N
Schritten.
2
Eine Verfeinerung des Verfahrens von Givens ist das Householder-Verfahren
(vgl. Stoer-Bulirsch).
10.6
Eigenwertabschätzungen
Eigenwertabschätzungen können theoretisch sehr ausführlich behandelt werden (vgl. z.B. Stoer/Bulirsch). Sie sind in vielen Feldern, darunter Funktionalanalysis und Quantenmechanik von grundsätzlicher Bedeutung. Auch wir
haben im Zusammenhang mit dem Spektralradius bereits einige Eigenwertabschätzungen kennengelernt. So war etwa für eine Iterationsmatrix M
p
ρ(M ) = lim n kM n k
n→∞
= inf {kM k : k · k passend}
ρ(M ) ≤ kM k ,
k · k passend.
oder
Idee des Verfahrens von Jacobi und Givens
10.6.1
179
Der klassische Satz von Gerschgorin
Die Diagonalelemente einer Matrix sind Näherungen für die Eigenwerte, und
zwar umso besser, je stärker diagonaldominant die Matrix ist. Dies ist die
zentrale Aussage des Satzes von Gerschgorin. Genau lautet er:
Satz 10.9 (Satz von Gerschgorin). Es sei A ∈ CN ×N . Bilden wir die
Kreise von Gerschgorin
Zi := {µ ∈ C : |µ − aii | ≤ zi }
Sj := {µ ∈ C : |µ − ajj | ≤ sj }
mit
zi
=
X0
|aik | =
=
X0
|aik |,
k=1
k6=i
k
sj
N
X
|akj | =
k
N
X
|akj |,
k=1
k6=j
dann gilt:
(1) Jeder Eigenwert von A liegt in Z :=
SN
i=1 Zi .
(2) Jede Zusammenhangskomponente von Z enthält so viele Nullstellen
des charakteristischen Polynoms von A, wie Kreise Zi an ihr beteiligt
sind.
S
(3) Diese Aussagen gelten entsprechend für Sj , S := N
j=1 Sj .
Beweis: Wir zeigen hier nur (1); für (2) und (3) vgl. etwa Stoer/Bulirsch.
Sei λ Eigenwert von A und k · k = k · k∞ . Sei ϕ ein zugehöriger Eigenvektor
zum Eigenwert λ. D bezeichne die “Diagonalmatrix” von A. Ferner sei λ 6=
aii (für alle i). Dann ist
(A − D)ϕ = (λI − D)ϕ
mit (λI − D) regulär wegen λ 6= aii .
Es gilt
(λI − D)−1 (A − D)ϕ = ϕ.
Der Übergang zur Norm liefert
k(λI − D)−1 (A − D)k∞ kϕk∞ ≥ kϕk∞
Idee des Verfahrens von Jacobi und Givens
180
(mit k · k passend), d.h.
k(λI − D)−1 (A − D)k∞ ≥ 1.
Hieraus folgt sofort
P0
|aik |
≥ 1.
1≤i≤N |λ − aii |
Obiges Maximum wird für ein i angenommen, so daß
k
max
|λ − aii | ≤
0
X
|aik |.
k
Dies bedeutet, λ liegt in einem der Gerschgorin-Kreise, und hieraus folgt die
Aussage (1) des Satzes.
Die Aussage (2) folgt mit Stetigkeitsargumenten. Man betrachtet dazu
die Schar von Matrizen
At = D + t(A − D)
mit At=0 = D
und At=1 = A
und benutzt die Tatsache, daß die Eigenwerte stetig von t abhängen (vgl.
Stoer/Bulirsch II).
Bemerkung 10.7 Im Falle lauter disjunkter Kreise liefert der Satz brauchbare Abschätzungen. Diese sind z.B. anwendbar, wenn A bereits eine gute
Näherung für eine Diagonalmatrix ist. Man kann diese Aussagen auch als
Abbruchkriterium verwenden (z.B. im Jacobi-Verfahren).
10.6.2
Rayleigh-Quotienten
Satz 10.10 (ohne Beweis).
A ∈ CN ×N sei hermitesch. Die (reellen) Eigenwerte von A seien so angeordnet, daß
λ1 ≥ λ2 ≥ · · · ≥ λN .
Dann ist
hAx, xi
x∈CN , x6=0 hx, xi
hAx, xi
=
min
.
N
x∈C , x6=0 hx, xi
λ1 =
λN
max
und
Allgemeiner gilt sogar
λk+1 =
min
y1 ,...,yk
∈CN
max
x∈CN , x6=0
(x,yκ )=0 für κ≤k
hAx, xi
.
hx, xi
Idee des Verfahrens von Jacobi und Givens
10.7
181
Rekapitulation
Bzgl. eines zusammenfassenden Überblicks auf Verfahren zu Eigenwertberechnungen verweisen wir auf Abbildung 10.2.
A:
H:
T:
D:
D’:
Ausgangsmatrix (allgemeine quadratische Matrix)
Hessenbergform
Tridiagonalform
Dreiecksmatrix
Diagonalmatrix
D'
A
D':
< He >
(LR)
(QR)
H
LR
QR
La
LR
QR
D
La
T
Ho :
He :
La :
Gi :
Ja :
Verfahren
Verfahren
Verfahren
Verfahren
Verfahren
von
von
von
von
von
<
: Verf. setzt A als hermitesch voraus
> : finites Verfahren
Householder (vgl. Stoer-Bulirsch)
Hessenberg
Lanczos
Givens
Jacobi
Abbildung 10.2: Überblick über klassische Verfahren zur Bestimmung von
Eigenwerten einer Matrix A.

Download Report