Satz von Courant-Fischer

Der Satz v​on Courant-Fischer (auch Minimum-Maximum-Prinzip) i​st ein mathematischer Satz a​us der linearen Algebra, d​er eine variationelle Charakterisierung d​er Eigenwerte e​iner symmetrischen o​der hermiteschen Matrix ermöglicht. Jeder Eigenwert w​ird dabei a​ls minimaler beziehungsweise maximaler Rayleigh-Quotient v​on Vektoren a​us Untervektorräumen m​it bestimmten Dimensionen dargestellt. Der Satz i​st nach d​en Mathematikern Richard Courant u​nd Ernst Fischer benannt. Er d​ient unter anderem z​ur Eigenwertabschätzung u​nd zur Analyse numerischer Eigenwertverfahren.

Satz

Ist ${\displaystyle A\in {\mathbb {K} }^{n\times n}}$ eine symmetrische Matrix (falls ${\displaystyle {\mathbb {K} }=\mathbb {R} }$) oder hermitesche Matrix (falls ${\displaystyle {\mathbb {K} }=\mathbb {C} }$) mit aufsteigend sortierten Eigenwerten ${\displaystyle \lambda _{1}\leq \ldots \leq \lambda _{n}}$ und bezeichnet ${\displaystyle X_{i}}$ die Menge der ${\displaystyle i}$-dimensionalen Untervektorräume von ${\displaystyle {\mathbb {K} }^{n}}$, ${\displaystyle i=1,\ldots ,n}$, dann hat der ${\displaystyle i}$-te Eigenwert von ${\displaystyle A}$ die Darstellung

${\displaystyle \lambda _{i}=\min _{X\in X_{i}}\max _{x\in X \atop x\neq 0}{\frac {\langle x,Ax\rangle }{\langle x,x\rangle }}=\max _{X\in X_{n-i+1}}\min _{x\in X \atop x\neq 0}{\frac {\langle x,Ax\rangle }{\langle x,x\rangle }}}$,

wobei ${\displaystyle \langle \cdot ,\cdot \rangle }$ das reelle oder komplexe Standardskalarprodukt ist. Wird der Satz von Courant-Fischer mit absteigend sortierten Eigenwerten angegeben, dann vertauschen sich jeweils Minimum und Maximum.[1]

Anschauliches Beispiel

Der Satz von Courant-Fischer charakterisiert die Eigenwerte einer symmetrischen positiv definiten (3 × 3)-Matrix über Extrempunkte auf einem Ellipsoid

Für eine symmetrische positiv definite ${\displaystyle (3\times 3)}$-Matrix ${\displaystyle A\in \mathbb {R} ^{3\times 3}}$ lässt sich der Satz von Courant-Fischer folgendermaßen veranschaulichen. Da die Eigenwerte von ${\displaystyle A^{T}A}$ die Quadrate der stets positiven Eigenwerte von ${\displaystyle A}$ sind und ${\displaystyle \langle x,A^{T}Ax\rangle =\langle Ax,Ax\rangle }$ gilt, hat der ${\displaystyle i}$-te Eigenwert von ${\displaystyle A}$ die Darstellung

${\displaystyle \lambda _{i}=\min _{X\in X_{i}}\max _{x\in X \atop x\neq 0}{\frac {\|Ax\|}{\|x\|}}=\min _{X\in X_{i}}\max _{x\in X \atop \|x\|=1}\|Ax\|}$,

wobei ${\displaystyle \|\cdot \|}$ die euklidische Norm ist. Die Menge ${\displaystyle \left\{Ax\in \mathbb {R} ^{3}\mid \|x\|=1\right\}}$ hat die Form eines Ellipsoids im dreidimensionalen Raum mit den Halbachsen ${\displaystyle \lambda _{1}}$, ${\displaystyle \lambda _{2}}$ und ${\displaystyle \lambda _{3}}$. Der Satz von Courant-Fischer charakterisiert nun die Eigenwerte von ${\displaystyle A}$ über bestimmte Extrempunkte auf diesem Ellipsoid:

• Für den kleinsten Eigenwert ${\displaystyle \lambda _{1}}$ werden alle eindimensionalen Untervektorräume, also alle Ursprungsgeraden, betrachtet. Jede dieser Ursprungsgeraden schneidet das Ellipsoid an zwei diametral gegenüberliegenden Punkten. Von all diesen Punkten wird einer derjenigen mit dem kleinsten Abstand zum Ursprung ausgewählt.
• Für den zweitkleinsten Eigenwert ${\displaystyle \lambda _{2}}$ werden alle zweidimensionalen Untervektorräume, also alle Ursprungsebenen, betrachtet. Jede dieser Ursprungsebenen schneidet das Ellipsoid in einer Ellipse. Auf jeder dieser Ellipsen wird einer der Punkte mit dem größten Abstand zum Ursprung gesucht und von all diesen Punkten einer derjenigen mit dem kleinsten Abstand zum Ursprung ausgewählt.
• Für den größten Eigenwert ${\displaystyle \lambda _{3}}$ wird der ganze Raum betrachtet und einer der Punkte auf dem Ellipsoid mit dem größten Abstand zum Ursprung ausgewählt.

Der Ortsvektor e​ines auf d​iese Weise ausgewählten Punkts i​st dann e​in Eigenvektor d​er Matrix u​nd die Länge dieses Vektors d​er zugehörige Eigenwert.

Beweis

Der Satz v​on Courant-Fischer stellt d​ie Eigenwerte e​iner symmetrischen o​der hermiteschen Matrix a​ls minimale beziehungsweise maximale Rayleigh-Quotienten

${\displaystyle R_{A}(x)={\frac {\langle x,Ax\rangle }{\langle x,x\rangle }}}$

dar. Im Folgenden wird eine obere und eine untere Schranke für den ersten Teil der Behauptung ermittelt. Die zweite Gleichung folgt analog durch Betrachtung von ${\displaystyle -A}$ und der entsprechenden Komplementärräume.

Obere Schranke

Nachdem ${\displaystyle A}$ symmetrisch oder hermitesch ist, lässt sich eine Orthonormalbasis ${\displaystyle \{x_{1},\ldots ,x_{n}\}}$ aus Eigenvektoren jeweils zu den Eigenwerten ${\displaystyle \lambda _{1},\ldots ,\lambda _{n}}$ finden. Bezeichnet

${\displaystyle V_{i}=\operatorname {span} (x_{i},\ldots ,x_{n})}$

die lineare Hülle derjenigen Eigenvektoren, deren Indizes mindestens ${\displaystyle i}$ sind. Der Schnitt von ${\displaystyle V_{i}}$ mit einem ${\displaystyle i}$-dimensionalen Untervektorraum ${\displaystyle X\in X_{i}}$ ist nicht ${\displaystyle \{0\}}$, denn mit der Dimensionsformel gilt

${\displaystyle \dim(X\cap V_{i})=\dim X+\dim V_{i}-\dim(X+V_{i})=i+(n-i+1)-\dim(X+V_{i})\geq 1}$.

Daher gibt es einen Vektor ${\displaystyle v\in X\cap V_{i}}$ mit ${\displaystyle v\neq 0}$, der eine Basisdarstellung

${\displaystyle v=c_{i}x_{i}+\ldots +c_{n}x_{n}}$

mit Koeffizienten ${\displaystyle c_{i},\ldots ,c_{n}\in {\mathbb {K} }}$ besitzt. Für einen solchen Vektor ${\displaystyle v}$ gilt nun

${\displaystyle \langle v,Av\rangle =\lambda _{i}c_{i}^{2}+\ldots +\lambda _{n}c_{n}^{2}\geq \lambda _{i}(c_{i}^{2}+\ldots +c_{n}^{2})=\lambda _{i}\langle v,v\rangle }$.

Für die Vektoren ${\displaystyle x\in X}$ eines beliebigen ${\displaystyle i}$-dimensionalen Untervektorraums ${\displaystyle X\in X_{i}}$ ist daher der maximale Rayleigh-Quotient ${\displaystyle R_{A}(x)\geq \lambda _{i}}$ und demnach gilt auch

${\displaystyle \min _{X\in X_{i}}\max _{x\in X \atop x\neq 0}R_{A}(x)\geq \lambda _{i}}$.

Untere Schranke

Bezeichne nun

${\displaystyle W_{i}=\operatorname {span} (x_{1},\ldots ,x_{i})}$

die lineare Hülle derjenigen Eigenvektoren, deren Indizes höchstens ${\displaystyle i}$ sind. Für einen Vektor ${\displaystyle w\in W_{i}}$ mit ${\displaystyle w\neq 0}$ und der Darstellung

${\displaystyle w=c_{1}x_{1}+\ldots +c_{i}x_{i}}$

gilt nun

${\displaystyle \langle w,Aw\rangle =\lambda _{1}c_{1}^{2}+\ldots +\lambda _{i}c_{i}^{2}\leq \lambda _{i}(c_{1}^{2}+\ldots +c_{i}^{2})=\lambda _{i}\langle w,w\rangle }$.

Der maximale Rayleigh-Quotient aller Vektoren ${\displaystyle x\in W_{i}}$ ist also ${\displaystyle R_{A}(x)=\lambda _{i}}$ und demnach gilt

${\displaystyle \min _{X\in X_{i}}\max _{x\in X \atop x\neq 0}R_{A}(x)\leq \max _{x\in W_{i} \atop x\neq 0}R_{A}(x)=\lambda _{i}}$.

Durch Zusammenfassung d​er beiden Schranken f​olgt dann d​er erste Teil d​er Behauptung.[1]

Verwendung

Eine direkte Konsequenz a​us dem Satz v​on Courant-Fischer i​st die Abschätzung

${\displaystyle \lambda _{\min }\leq R_{A}(x)\leq \lambda _{\max }}$

für den kleinsten und den größten Eigenwert einer symmetrischen oder hermiteschen Matrix ${\displaystyle A}$. Gleichheit gilt dabei jeweils genau dann, wenn ${\displaystyle x}$ ein Eigenvektor zum jeweiligen Eigenwert ist. Der kleinste und der größte Eigenwert können demnach durch Minimierung beziehungsweise Maximierung des Rayleigh-Quotienten ermittelt werden.

Eine weitere Anwendung besteht in numerischen Stabilitätsaussagen für Eigenwertverfahren. Sind ${\displaystyle A,B\in {\mathbb {K} }^{n\times n}}$ zwei symmetrische oder hermitesche Matrizen mit aufsteigend sortierten Eigenwerten ${\displaystyle \lambda _{1}(A)\leq \ldots \leq \lambda _{n}(A)}$ und ${\displaystyle \lambda _{1}(B)\leq \ldots \leq \lambda _{n}(B)}$, dann gilt

${\displaystyle |\lambda _{i}(A)-\lambda _{i}(B)|\leq \|A-B\|}$

für alle ${\displaystyle i=1,\ldots ,n}$, wobei ${\displaystyle \|\cdot \|}$ eine beliebige natürliche Matrixnorm ist. Wird demnach eine Matrix ${\displaystyle A}$ durch eine Matrix ${\displaystyle B}$ angenähert (deren Eigenwerte einfacher zu berechnen sind), dann ist der dadurch entstehende Fehler durch die Norm der Differenz der beiden Matrizen beschränkt.[2]

Varianten

Von dem Satz von Courant-Fischer existiert auch folgende Variante zur Darstellung der Singulärwerte einer Matrix. Ist ${\displaystyle A\in {\mathbb {K} }^{m\times n}}$ eine (nicht notwendigerweise quadratische) Matrix mit aufsteigend sortierten Singulärwerten ${\displaystyle \sigma _{1}\leq \ldots \leq \sigma _{\min\{m,n\}}}$ und bezeichnet ${\displaystyle \|\cdot \|}$ die euklidische Norm, dann hat der ${\displaystyle i}$-te Singulärwert von ${\displaystyle A}$ die Darstellung

${\displaystyle \sigma _{i}=\min _{X\in X_{i}}\max _{x\in X \atop \|x\|=1}\|Ax\|=\max _{X\in X_{n-i+1}}\min _{x\in X \atop \|x\|=1}\|Ax\|}$,

wobei ${\displaystyle X_{i}}$ wieder die Menge der ${\displaystyle i}$-dimensionalen Untervektorräume von ${\displaystyle {\mathbb {K} }^{n}}$ ist. Dieses Resultat folgt aus dem Satz von Courant-Fischer über die Darstellung der Singulärwerte von ${\displaystyle A}$ als Wurzeln der Eigenwerte von ${\displaystyle A^{H}A}$ beziehungsweise ${\displaystyle AA^{H}}$.[3]

Verallgemeinerungen dieser Aussage existieren a​uch zur Darstellung d​es Spektrums selbstadjungierter Operatoren a​uf Hilberträumen, w​as zum Beispiel b​eim Rayleigh-Ritz-Prinzip eingesetzt wird.

Siehe auch

• Gerschgorin-Kreise, eine Möglichkeit zur Abschätzung der Eigenwerte einer quadratischen Matrix

Literatur

• Harry Dym: Linear Algebra in Action. 2. Auflage. American Mathematical Society, 2013, ISBN 978-1-4704-0908-1.
• Roger A. Horn: Topics in Matrix Analysis. Cambridge University Press, 1994, ISBN 0-521-46713-6.
• Robert Schaback, Holger Wendland: Numerische Mathematik. Springer, 2006, ISBN 978-3-540-26705-8.

Originalarbeiten

• Ernst Fischer: Über quadratische Formen mit reellen Koeffizienten. In: Monatshefte für Mathematik und Physik. Band 16, 1905, S. 234–249.
• Richard Courant: Über die Eigenwerte bei den Differentialgleichungen der mathematischen Physik. In: Mathematische Zeitschrift. Band 7, Nr. 1–4, 1920, S. 1–57.

Einzelnachweise

1. Harry Dym: Linear Algebra in Action. 2. Auflage. American Mathematical Society, 2013, S. 224–225.
2. Robert Schaback, Holger Wendland: Numerische Mathematik. Springer, 2006, S. 270.
3. Roger A. Horn: Topics in Matrix Analysis. Cambridge University Press, 1994, S. 148.