Rayleigh-Quotient

Rayleigh-Quotient
Für eine hermitesche positiv definite Matrix S sind die Extremwerte des
sogenannten Rayleigh-Quotienten
rS (x) =
x ∗ Sx
,
x ∗x
x 6= 0 ,
der kleinste und größte Eigenwert von S.
Rayleigh-Quotient
1-1
Rayleigh-Quotient
Für eine hermitesche positiv definite Matrix S sind die Extremwerte des
sogenannten Rayleigh-Quotienten
rS (x) =
x ∗ Sx
,
x ∗x
x 6= 0 ,
der kleinste und größte Eigenwert von S.
Insbesondere gilt für die der euklidischen Norm zugeordneten Matrix-Norm
kSk = max rS (x) = λmax ,
x
kS −1 k−1 = min rS (x) = λmin .
x
Rayleigh-Quotient
1-2
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
Rayleigh-Quotient
2-1
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
Rayleigh-Quotient
2-2
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
λi =
ui∗ Sui
ui∗ λui
=
>0
ui∗ ui
ui∗ ui
Rayleigh-Quotient
2-3
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
λi =
ui∗ Sui
ui∗ λui
=
>0
ui∗ ui
ui∗ ui
und o.B.d.A. λ1 ≥ · · · ≥ λn
Rayleigh-Quotient
2-4
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
λi =
ui∗ Sui
ui∗ λui
=
>0
ui∗ ui
ui∗ ui
und o.B.d.A. λ1 ≥ · · · ≥ λn
Substitution von S = UDU ∗ und x = Uy
Rayleigh-Quotient
2-5
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
λi =
ui∗ Sui
ui∗ λui
=
>0
ui∗ ui
ui∗ ui
und o.B.d.A. λ1 ≥ · · · ≥ λn
Substitution von S = UDU ∗ und x = Uy
P
λi |yi |2
y ∗ Dy
rS (y ) = ∗ ∗
= Pi
2
y (U U)y
i |yi |
Rayleigh-Quotient
2-6
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
λi =
ui∗ Sui
ui∗ λui
=
>0
ui∗ ui
ui∗ ui
und o.B.d.A. λ1 ≥ · · · ≥ λn
Substitution von S = UDU ∗ und x = Uy
P
λi |yi |2
y ∗ Dy
rS (y ) = ∗ ∗
= Pi
2
y (U U)y
i |yi |
λi > 0 =⇒
λmin ≤ rS (y ) ≤ λmax
Rayleigh-Quotient
2-7
Beweis:
Transformation auf Diagonalform mit unitärer Matrix U = (u1 , · · · , un )
aus Eigenvektoren:
U ∗ SU = D,
D = diag(λ1 , . . . , λn ),
Sui = λi ui
mit λi ∈ R
S positiv definit =⇒
λi =
ui∗ Sui
ui∗ λui
=
>0
ui∗ ui
ui∗ ui
und o.B.d.A. λ1 ≥ · · · ≥ λn
Substitution von S = UDU ∗ und x = Uy
P
λi |yi |2
y ∗ Dy
rS (y ) = ∗ ∗
= Pi
2
y (U U)y
i |yi |
λi > 0 =⇒
λmin ≤ rS (y ) ≤ λmax
mit Gleichheit für y = en und y = e1
Rayleigh-Quotient
2-8
Beispel:
S=
3 2
2 3
Rayleigh-Quotient
3-1
Beispel:
S=
3 2
2 3
Invariant des Rayleigh-Quotienten rs (x) unter Skalierung x → λx
o.B.d.A. x = (cos t, sin t)t
Rayleigh-Quotient
3-2
Beispel:
S=
3 2
2 3
Invariant des Rayleigh-Quotienten rs (x) unter Skalierung x → λx
o.B.d.A. x = (cos t, sin t)t
r (x) = 3 cos2 t + 4 cos t sin t + 3 sin2 t = 3 + 2 sin(2t)
Rayleigh-Quotient
3-3
Beispel:
S=
3 2
2 3
Invariant des Rayleigh-Quotienten rs (x) unter Skalierung x → λx
o.B.d.A. x = (cos t, sin t)t
r (x) = 3 cos2 t + 4 cos t sin t + 3 sin2 t = 3 + 2 sin(2t)
Extrema
!
0 = 4 cos(2t)
=⇒
t=±
π
4
Rayleigh-Quotient
3-4
Beispel:
S=
3 2
2 3
Invariant des Rayleigh-Quotienten rs (x) unter Skalierung x → λx
o.B.d.A. x = (cos t, sin t)t
r (x) = 3 cos2 t + 4 cos t sin t + 3 sin2 t = 3 + 2 sin(2t)
Extrema
!
0 = 4 cos(2t)
=⇒
t=±
π
4
kleinster und größer Eigenwert
λ± = 3 + 2 sin(±π/2),
d.h. λ+ = 5, λ− = 1
Rayleigh-Quotient
3-5
Beispel:
S=
3 2
2 3
Invariant des Rayleigh-Quotienten rs (x) unter Skalierung x → λx
o.B.d.A. x = (cos t, sin t)t
r (x) = 3 cos2 t + 4 cos t sin t + 3 sin2 t = 3 + 2 sin(2t)
Extrema
!
0 = 4 cos(2t)
=⇒
t=±
π
4
kleinster und größer Eigenwert
λ± = 3 + 2 sin(±π/2),
d.h. λ+ = 5, λ− = 1
zur Kontrolle:
det S = 9 − 4 = 5 · 1,
Spur S = 3 + 3 = 5 + 1
Rayleigh-Quotient
3-6