Study Guides / Lineare Algebra / Übungsstunde 13
ÜBUNGSSTUNDE 13 · ETH ZURICH · HS19 · linalg

Eigenwerte, Diagonalisierbarkeit und Singulärwertzerlegung

Eigenwert & Eigenvektor, charakteristisches Polynom, Spur, Singulärwertzerlegung (SVD)

SB
Steven Battilana Quant · ex-ETH

Eigenwerte und Eigenvektoren

Sei in diesem Abschnitt VV ein Vektorraum über E\mathbb{E}, dim(V)=n<∞\text{dim}(V)=n<\infty, A∈En×nA \in \mathbb{E}^{n \times n}.

Definition
  • λ∈E\lambda \in \mathbb{E} heisst Eigenwert (EW) von A⇔∃v∈V∖{0}:Av=λvA \quad \Leftrightarrow \quad \exists v \in V \setminus \{0\}: \quad Av=\lambda v.
  • v∈V∖{0}v \in V \setminus \{0\} heisst dann Eigenvektor (EV) von AA zum Eigenwert λ\lambda.
  • Eλ(A)={v∈V∣Av=λv}E_\lambda(A) = \{v \in V | Av=\lambda v\} heisst Eigenraum von AA zum Eigenwert λ\lambda.
  • σ(A):={λ  ∣  λ Eigenwerte von A}\sigma(A) := \{\lambda\; |\; \lambda \text{ Eigenwerte von } A \} heisst Spektrum von AA.
Bemerkung

Eλ(A)=ker(A−λ𝟙)E_\lambda(A)=\text{ker}(A-\lambda \text{𝟙}) ist ein nichttrivialer Untervektorraum von VV, d.h. es gilt:

{0}⊊Eλ(A)(echt gro¨sser als nur der Nullraum)\{0\} \subsetneq E_\lambda(A) \quad \text{(echt grösser als nur der Nullraum)}
Bemerkung

Diese Definition lässt sich analog für eine lineare Abbildung F:V→VF: V \to V führen. Es gilt:

λ ist ein Eigenwert von F,  v ist ein Eigenvektor von F⇔λ ist ein Eigenwert von A,  v ist ein Eigenvektor von A,wobei A die Abbildungsmatrix von F bezeichnet.\begin{aligned} &\lambda \text{ ist ein Eigenwert von } F, \; v \text{ ist ein Eigenvektor von } F\\ \Leftrightarrow \quad &\lambda \text{ ist ein Eigenwert von } A, \; v \text{ ist ein Eigenvektor von } A,\\ &\text{wobei } A \text{ die Abbildungsmatrix von } F \text{ bezeichnet}. \end{aligned}
Bemerkung Herleitung des charakteristischen Polynoms χ_A

Betrachte

Av=λv⇔Av−λv=0⇔(A−λ𝟙)v=0(1)\begin{aligned} Av=\lambda v \quad &\Leftrightarrow \quad Av - \lambda v = 0\\ & \Leftrightarrow \quad (A- \lambda \text{𝟙})v = 0 \qquad\qquad\qquad\qquad (1) \end{aligned}

v=0v=0 löst (1)(1), aber v=0v=0 ist als Eigenvektor nicht zugelassen. Wir fordern mehr Lösungen, d.h. ∞\infty viele Lösungen (da ein LGS immer 0,10,1 oder ∞\infty viele Lösungen hat). Gemäss dem Satz aus der Erinnerung können wir dies erreichen, indem wir det(A−λ𝟙)=!0\text{det}(A-\lambda \text{𝟙}) \overset{!}{=}0 setzen, weil

det(A−λ𝟙)=0⇔SatzA−λ𝟙 singula¨r⇒(A−λ𝟙)v=0 hat ∞ viele Lo¨sungen, da v=0 nicht zugelassen ist.\begin{aligned} \text{det}(A-\lambda \text{𝟙})=0 \quad &\overset{\text{Satz}}{\Leftrightarrow} \quad A-\lambda \text{𝟙} \text{ singulär}\\ &\Rightarrow \quad (A- \lambda \text{𝟙})v = 0 \text{ hat } \infty \text{ viele Lösungen, da } v=0 \text{ nicht zugelassen ist.} \end{aligned}
Definition

χA(λ)=det(A−λ𝟙)\chi_A(\lambda) = \text{det}(A-\lambda \text{𝟙}) heisst charakteristisches Polynom.

Bemerkung
  • χA(λ)\chi_A(\lambda) hat Grad nn
  • λ\lambda ist ein Eigenwert von AA
    ⇔λ\Leftrightarrow \lambda ist eine Nullstelle (NST) des charakteristischen Polynoms χA(λ)\chi_A(\lambda).
Bemerkung

Mitternachtsformel (auswendig)

ax2+bx+c=0⇒x1,2=−b±b2−4ac2a\begin{aligned} ax^2 + bx + c &= 0\\ \Rightarrow \quad x_{1,2} &= \frac{-b \pm \sqrt{b^2 -4ac}}{2a} \end{aligned}
Algorithmus Berechnung von Eigenwerten und Eigenvektoren

Gegeben: A∈En×nA \in \mathbb{E}^{n \times n}
(falls F:V→VF: V \to V lineare Abbildung gegeben ist, finde zuerst die Abbildungsmatrix AA)
Gesucht: σ(A)\sigma(A) (d.h. ∀\forall Eigenwerte von AA), Eλ(A)E_\lambda(A) mit ∀λ∈σ(A)\forall \lambda \in \sigma(A)

  1. Berechne χA(λ)=det(A−λ𝟙)\chi_A(\lambda) = \text{det}(A-\lambda \text{𝟙})

  2. Setze χA(λ)=!0\chi_A(\lambda) \overset{!}{=} 0:

    ⇒n Nullstellen λ1,...,λn⇒σ(A)={λ1,...,λn}\begin{aligned} &\Rightarrow n \text{ Nullstellen } \lambda_1, ..., \lambda_n\\ &\Rightarrow \sigma(A) = \{\lambda_1, ..., \lambda_n \} \end{aligned}

    Bemerkung. λ1,...,λn\lambda_1, ..., \lambda_n sind nicht zwingend verschieden, sondern mit Nullstellenvielfachheit gezählt.

  3. Für jeden verschiedenen Eigenwert λk\lambda_k bestimme die Basis von Eλk(A)=ker(A−λk𝟙)E_{\lambda_k}(A) = \text{ker}(A-\lambda_k \text{𝟙}) mit Hilfe von der Gauss-Elimination.

  4. Die Menge der Eigenvektoren ist

    ⋃k(Eλk(A)∖{0})\bigcup_k \left( E_{\lambda_k}(A) \setminus \{0\} \right)

    (Wir vereinigen alle Eigenräume minus den Nullvektor)

Beispiel 1

Gegeben:

A=(123432005)A= \begin{pmatrix} 1 & 2 & 3\\ 4 & 3 & 2\\ 0 & 0 & 5 \end{pmatrix}

Gesucht: Eigenwerte, Eigenvektoren von AA

Lösung anzeigenLösung ausblenden
  1. χA(λ)=det(A−λ𝟙)=det((1−λ)234(3−λ)200(5−λ))=(1−λ)(3−λ)(5−λ)−(5−λ)⋅4⋅2=(5−λ)[(1−λ)(3−λ)−4⋅2]=(5−λ)[3−3λ−λ+λ2−8]=(5−λ)[λ2−4λ−5]=(5−λ)(λ−5)(λ+1)(allenfalls mit Hilfe der Mitternachtsformel)=−(λ−5)(λ−5)(λ+1)=−(λ−5)2(λ+1)\begin{aligned} \chi_A(\lambda) &= \text{det}(A-\lambda \text{𝟙})\\ &= \text{det} \begin{pmatrix} (1-\lambda) & 2 & 3\\ 4 & (3-\lambda) & 2\\ 0 & 0 & (5-\lambda) \end{pmatrix}\\ &= (1-\lambda)(3-\lambda)(5-\lambda) - (5-\lambda)\cdot 4 \cdot 2\\ &= (5-\lambda)[(1-\lambda)(3-\lambda) - 4 \cdot 2]\\ &= (5-\lambda)[3-3\lambda-\lambda+\lambda^2 - 8]\\ &= (5-\lambda)[\lambda^2-4\lambda-5]\\ &= (5-\lambda)(\lambda-5)(\lambda+1) \quad \text{(allenfalls mit Hilfe der Mitternachtsformel)}\\ &= -(\lambda-5)(\lambda-5)(\lambda+1)\\ &= -(\lambda-5)^2(\lambda+1) \end{aligned}
  2. χA(λ)=!0⇔−(λ−5)2(λ+1)=0⇒λ1=λ2=5(Spa¨ter: algebraische Vielfachheit von 5 ist 2)λ3=−1⇒σ(A)={5,−1}\begin{aligned} \chi_A(\lambda) &\overset{!}{=} 0\\ \Leftrightarrow \quad -(\lambda-5)^2(\lambda+1) &= 0\\ \Rightarrow \qquad \lambda_1 &= \lambda_2 = 5 \qquad \text{(Später: algebraische Vielfachheit von 5 ist 2)}\\ \lambda_3 &= -1\\ \Rightarrow \qquad \sigma(A) &= \{5,-1\} \end{aligned}
    • λ1=λ2=5\lambda_1 = \lambda_2 = 5:

      E5(A)=ker(A−5⋅𝟙)=ker(−4234−22000)E_5(A) = \text{ker}(A - 5 \cdot \text{𝟙}) = \text{ker} \begin{pmatrix} -4 & 2 & 3\\ 4 & -2 & 2\\ 0 & 0 & 0 \end{pmatrix} ⇝"Gaussen"ker(2−10001000)=span{(120)}\overset{\text{"Gaussen"}}{\leadsto} \text{ker} \begin{pmatrix} 2 & -1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{pmatrix} = \text{span} \left\{ \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix} \right\}
    • λ3=−1\lambda_3 = -1:

      E−1(A)=ker(A−(−1)⋅𝟙)=ker(223442006)E_{-1}(A) = \text{ker}(A - (-1) \cdot \text{𝟙}) = \text{ker} \begin{pmatrix} 2 & 2 & 3\\ 4 & 4 & 2\\ 0 & 0 & 6 \end{pmatrix} ⇝"Gaussen"ker(110001000)=span{(1−10)}\overset{\text{"Gaussen"}}{\leadsto} \text{ker} \begin{pmatrix} 1 & 1 & 0\\ 0 & 0 & 1\\ 0 & 0 & 0 \end{pmatrix} = \text{span} \left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} \right\}
  3. Menge der Eigenvektoren:

    span{(120),(1−10)}∖{(000)}\text{span} \left\{ \begin{pmatrix} 1\\ 2\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix} \right\} \setminus \left\{ \begin{pmatrix} 0\\ 0\\ 0 \end{pmatrix} \right\}
Bemerkung

Es wäre mathematisch unpräzis in Beispiel 1 zu sagen: "Die Eigenvektoren sind (1,2,0)T(1,2,0)^T und (1,−1,0)T(1,-1,0)^T". Denn es gibt ∞\infty viele Eigenvektoren.
Sei zum Beispiel vv ein Eigenvektor von AA zum Eigenwert λ\lambda, d.h. Av=λvAv = \lambda v
⇒c⋅v\Rightarrow c \cdot v ist ein Eigenvektor von AA zu λ\lambda für alle c∈E∖{0}c \in \mathbb{E} \setminus \{0\}, da auch A(cv)=λ(cv)A(cv) = \lambda (cv) gilt.
Meist genügt es trotzdem, einen Basisvektor v∈Eλ(A)∖{0}v \in E_\lambda(A) \setminus \{0\} als "repräsentativen Eigenvektor" zu nehmen.

Spektralzerlegung, Diagonalisierbarkeit

Definition

Sei λ\lambda ein Eigenwert von A∈En×nA \in \mathbb{E}^{n \times n}.

  • Algebraische Vielfachheit von λ\lambda:

    aλ:="Nullstellenvielfachheit von λ in χA(λ)"a_\lambda := \text{"Nullstellenvielfachheit von } \lambda \text{ in } \chi_A(\lambda) \text{"}
  • Geometrische Vielfachheit:

    gλ:=dim(Eλ(A))=dim(ker(A−λ𝟙))=n−rang(A−λ𝟙)\begin{aligned} g_\lambda &:= \text{dim}(E_\lambda(A))\\ &= \text{dim}(\text{ker}(A-\lambda \text{𝟙}))\\ &= n - \text{rang}(A-\lambda \text{𝟙}) \end{aligned}
Definition

AA heisst diagonalisierbar (es existiert eine Spektralzerlegung)

⇔∃V∈En×n,  Λ∈En×n, mit V regula¨r, Λ diagonal, so dass A=VΛV−1\begin{aligned} \Leftrightarrow \quad &\exists V \in \mathbb{E}^{n \times n}, \; \Lambda \in \mathbb{E}^{n \times n}, \text{ mit } V \text{ regulär, } \Lambda \text{ diagonal, so dass }\\ &A = V \Lambda V^{-1} \end{aligned}

Man sagt auch: "AA ist ähnlich zu einer Diagonalmatrix".

Satz

AA ist diagonalisierbar
⇔\Leftrightarrow Die Eigenvektoren von AA bilden eine Basis von VV
⇔\Leftrightarrow Für alle Eigenwerte λ\lambda von AA gilt gλ=aλg_\lambda = a_\lambda.

Bemerkung

Eine Diagonalisierung ist ein Basiswechsel mit Transformationsmatrizen VV und V−1V^{-1}.

Satz

Bei Ähnlichkeitstransformation bleibt erhalten:

  • Eigenwerte und deren algebraische und geometrische Vielfachheit
  • Rang
  • Determinante
  • Spur
  • Charakteristisches Polynom χA(t)\chi_A(t)
  • nicht die Eigenvektoren!
Algorithmus Berechnung der Diagonalmatrix

Gegeben: A∈En×nA \in \mathbb{E}^{n \times n} diagonalisierbar
Gesucht: V,Λ∈En×nV, \Lambda \in \mathbb{E}^{n \times n}

  1. Finde die Eigenwerte λ1,...,λn\lambda_1, ..., \lambda_n und finde die dazugehörigen Eigenvektoren v1,...,vnv_1, ..., v_n von AA (wobei vi∈Eλi(A)v_i \in E_{\lambda_i}(A) und {vi}i=1n\{v_i\}_{i=1}^n linear unabhängig).

  2. Definiere die Diagonalmatrix wie folgt:

    Λ=(λ10⋯00⋱⋱⋮⋮⋱⋱00⋯0λn)mit λ1≥...≥λn\Lambda = \begin{pmatrix} \lambda_1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & \lambda_n \end{pmatrix} \quad\quad \text{mit } \lambda_1 \geq ... \geq \lambda_n
  3. Schreibe die Eigenvektoren vi∈Eλi(A)v_i \in E_{\lambda_i}(A) in eine Matrix:

    V=(v1|⋯|vn)V = \left( v_1 \middle| \cdots \middle| v_n \right)
  4. Test: A=?VΛV−1A \overset{?}{=} V \Lambda V^{-1}

Beispiel 1 fortgesetzt …

Sei

A=(123432005) wie in Beispiel 3 mit χA(λ)=−(λ−5)2(λ+1)A= \begin{pmatrix} 1 & 2 & 3\\ 4 & 3 & 2\\ 0 & 0 & 5 \end{pmatrix} \qquad \text{ wie in Beispiel 3 mit } \chi_A(\lambda) = -(\lambda-5)^2(\lambda+1)

Gesucht: Algebraische und geometrische Vielfachheit

Lösung anzeigenLösung ausblenden
  • Algebraische Vielfachheit:

    λ1=5 mit a5=2undλ2=−1 mit a−1=1\lambda_1 = 5 \text{ mit } a_5 = 2 \quad \text{und} \quad \lambda_2 = -1 \text{ mit } a_{-1} = 1
  • Geometrische Vielfachheit:

    g5= dim(E5(A))=1≠a5=2g−1= dim(E−1(A))=1=a−1=1\begin{aligned} g_5 &= \text{ dim}(E_5(A)) = 1 \quad \neq a_5 = 2\\ g_{-1} &= \text{ dim}(E_{-1}(A)) = 1 \quad = a_{-1} = 1 \end{aligned}

Da g5≠a5⇒Ag_5 \neq a_5 \Rightarrow A ist nicht diagonalisierbar.

Beispiel 2

Gegeben:

A=(0−11−3−23−2−23)A= \begin{pmatrix} 0 & -1 & 1\\ -3 & -2 & 3\\ -2 & -2 & 3 \end{pmatrix}

Gesucht: Finde die Spektralzerlegung.

Lösung anzeigenLösung ausblenden
    1. χA(λ)=det(A−λ𝟙)=∣−λ−11−3−2−λ3−2−23−λ∣=−λ(−2−λ)(3−λ)+(−1)⋅3⋅(−2)+1⋅(−3)⋅(−2)        −(−2)⋅(−2−λ)⋅1−(−2)⋅3⋅(−λ)−(3−λ)⋅(−3)⋅(−1)=6λ+3λ2−2λ2−λ3+6+6−4−2λ−6λ−9+3λ=−λ3+λ2+λ−1\begin{aligned} \chi_A(\lambda) &= \text{det}(A-\lambda \text{𝟙})\\ &= \begin{vmatrix} -\lambda & -1 & 1\\ -3 & -2-\lambda & 3\\ -2 & -2 & 3-\lambda \end{vmatrix}\\ &= -\lambda(-2-\lambda)(3-\lambda) + (-1) \cdot 3 \cdot (-2) + 1 \cdot (-3) \cdot (-2)\\ &\;\;\;\;- (-2) \cdot (-2-\lambda) \cdot 1 - (-2) \cdot 3 \cdot (-\lambda) - (3-\lambda) \cdot (-3) \cdot (-1)\\ &= 6\lambda + 3\lambda^2 -2\lambda^2 -\lambda^3 + 6 + 6 - 4 -2\lambda -6\lambda -9 +3\lambda\\ &= -\lambda^3 +\lambda^2 +\lambda-1 \end{aligned}

      Bemerkung. Hier müsst ihr einen Trick verwenden, indem ihr die Nullstelle erratet (teste: 1,−1,2,−21,-1,2,-2, etc.) und dann eine Polynomdivision durchführt.

      λ1=1\lambda_1 = 1 ist eine Nullstelle:

      (−t3+t2+t−1):(t−1)=−t2+1(-t^3+t^2+t-1) : (t-1) = -t^2+1−t3+t2+t−1−(−t3+t2)0+t−1−(t−1)0\begin{array}{rrrr} -t^3 & +t^2 & +t & -1 \\ -(-t^3 & +t^2) & & \\ \hline & 0 & +t & -1 \\ & & -(t & -1) \\ \hline & & & 0 \end{array}⇒χA(λ)=(λ−1)(1−λ2)=(λ−1)(1−λ)(1+λ)=−(λ−1)(λ−1)(λ+1)=−(λ−1)2(λ+1)\begin{aligned} \Rightarrow \quad \chi_A(\lambda) &= (\lambda-1)(1-\lambda^2)\\ &= (\lambda-1)(1-\lambda)(1+\lambda)\\ &= -(\lambda-1)(\lambda-1)(\lambda+1)\\ &= -(\lambda-1)^2(\lambda+1) \end{aligned}
    2. χA(λ)=!0⇔0=−(λ−1)2(λ+1)⇒λ1=λ2=1,    a1=2λ3=−1,    a−1=1⇒σ(A)={−1,1}\begin{aligned} \chi_A(\lambda) &\overset{!}{=} 0\\ \Leftrightarrow 0 &= -(\lambda-1)^2(\lambda+1)\\ \Rightarrow \quad \lambda_1 &= \lambda_2 = 1, \;\; a_1 = 2\\ \lambda_3 &= -1, \;\; a_{-1} = 1\\ \Rightarrow \quad \sigma(A) &= \{-1,1\} \end{aligned}
      • λ1=λ2=1\lambda_1=\lambda_2 = 1:

        E1(A)=ker(A−𝟙)=ker(−1−11−3−33−2−22)⇝"Gaussen"ker(−1−11000000)=span{(1−10),(101)}⇒g1=2\begin{aligned} E_1(A) &= \text{ker}(A-\text{𝟙})\\ &= \text{ker} \begin{pmatrix} -1 & -1 & 1\\ -3 & -3 & 3\\ -2 & -2 & 2 \end{pmatrix}\\ &\overset{\text{"Gaussen"}}{\leadsto} \text{ker} \begin{pmatrix} -1 & -1 & 1\\ 0 & 0 & 0\\ 0 & 0 & 0 \end{pmatrix} = \text{span}\left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix} \right\}\\ \Rightarrow \quad g_1 &= 2 \end{aligned}
      • λ3=−1\lambda_3 = -1:

        E−1(A)=ker(A+𝟙)=ker(1−11−3−13−2−24)⇝"Gaussen"ker(1−110−460−46)⇝"Gaussen"ker(1−1102−3000)=span{(132)}⇒g−1=1\begin{aligned} E_{-1}(A) &= \text{ker}(A+\text{𝟙})\\ &= \text{ker} \begin{pmatrix} 1 & -1 & 1\\ -3 & -1 & 3\\ -2 & -2 & 4 \end{pmatrix}\\ &\overset{\text{"Gaussen"}}{\leadsto} \text{ker} \begin{pmatrix} 1 & -1 & 1\\ 0 & -4 & 6\\ 0 & -4 & 6 \end{pmatrix}\\ &\overset{\text{"Gaussen"}}{\leadsto} \text{ker} \begin{pmatrix} 1 & -1 & 1\\ 0 & 2 & -3\\ 0 & 0 & 0 \end{pmatrix} = \text{span}\left\{ \begin{pmatrix} 1\\ 3\\ 2 \end{pmatrix} \right\}\\ \Rightarrow \quad g_{-1} &= 1 \end{aligned}

      ⟹a1=g1\Longrightarrow \quad \quad a_1=g_1 und a−1=g−1⇒Aa_{-1}=g_{-1} \Rightarrow A ist diagonalisierbar.

    3. Menge der Eigenvektoren:

      span{(1−10),(101),(132)}\text{span} \left\{ \begin{pmatrix} 1\\ -1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ 1 \end{pmatrix}, \begin{pmatrix} 1\\ 3\\ 2 \end{pmatrix} \right\}
  1. Λ=(10001000−1)\Lambda = \begin{pmatrix} 1 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1 \end{pmatrix}
  2. V=(111−103012),V−1=(3212−32−1−121212−12),V = \begin{pmatrix} 1 & 1 & 1\\ -1 & 0 & 3\\ 0 & 1 & 2 \end{pmatrix}, \quad V^{-1} = \begin{pmatrix} \frac{3}{2} & \frac{1}{2} & -\frac{3}{2}\\ -1 & -1 & 2\\ \frac{1}{2} & \frac{1}{2} & -\frac{1}{2} \end{pmatrix},

    wobei ihr die Inverse V−1V^{-1} mit dem üblichen Rezept berechnet.

  3. Test: A=VΛV−1✓\quad\quad A= V \Lambda V^{-1} \checkmark

Bemerkung

Komplexwertige Nullstellen des charakteristischen Polynoms mit reellen Koeffizienten treten immer paarweise auf, und zwar ist mit λ∈C\lambda \in \mathbb{C} auch λ‾\overline{\lambda} eine Nullstelle. Somit muss eine orthogonale Matrix von ungerader Dimension mindestens einen reellen Eigenwert ±1\pm1 besitzen.

Definition

Die Summe der Diagonalelemente von A∈En×nA \in \mathbb{E}^{n \times n} nennt man Spur von AA:

spur(A):=∑i=1naii=a11+...+ann.\text{spur}(A) := \sum_{i=1}^n a_{ii} = a_{11} + ... + a_{nn}.
Lemma 9.6

Eine (quadratische) Matrix AA ist genau dann singulär, wenn sie 00 als Eigenwert hat:

A singula¨r⇔0∈σ(A).A \text{ singulär} \quad \Leftrightarrow \quad 0 \in \sigma(A).
Satz 9.11

Eigenvektoren zu verschiedenen Eigenwerten sind linear unabhängig.

Korollar 9.12

Sind die n Eigenwerte von F:V→VF : V \to V (mit n=dim(V)n = \text{dim}(V)) verschieden, so gibt es eine Basis von Eigenvektoren und die entsprechende Abbildungsmatrix ist diagonal.

Satz 9.15

Ist A∈Cn×nA \in \mathbb{C}^{n \times n} hermitesch, so gilt:

  1. Alle Eigenwerte λ1,...,λn\lambda_1, ..., \lambda_n sind reell.
  2. Die Eigenvektoren zu verschiedenen Eigenwerten sind paarweise orthogonal in Cn\mathbb{C}^n.
  3. Es gibt eine orthonormale Basis des Cn\mathbb{C}^n aus Eigenvektoren u1,...,unu_1, ..., u_n von AA.
  4. Für die unitäre Matrix U:=(u1,...,un)U:=(u_1, ..., u_n) gilt: UHAU=Λ=diag(λ1,...,λn).U^H A U = \Lambda = diag(\lambda_1, ..., \lambda_n).

Singulärwertzerlegung

Satz

Sei A∈En×nA \in \mathbb{E}^{n \times n} symmetrisch (AT=A)(A^T=A) oder hermitesch (AH=A‾T=AT‾=A)(A^H= \overline{A}^T = \overline{A^T}=A), dann gilt:

  1. AA hat nur reelle Eigenwerte
  2. Eigenvektoren zu verschiedenen Eigenwerten sind paarweise orthogonal
Bemerkung 1

Um eine Orthonormalbasis aus Eigenvektoren einer symmetrischen/hermiteschen Matrix zu erhalten, muss man die Eigenvektoren nur normieren und gegebenenfalls mit Gram-Schmidt orthogonalisieren (macht man falls es einen Eigenwert mit geometrischer Vielfachheit >1> 1 gibt).

Satz Singulärwertzerlegung

Sei A∈Em×nA \in \mathbb{E}^{m \times n}, rang(A)=:r≤min{m,n}\text{rang}(A)=: r \leq \text{min}\{m,n\}. Dann existieren U∈Em×mU \in \mathbb{E}^{m \times m} orthogonal/unitär, V∈En×nV \in \mathbb{E}^{n \times n} orthogonal/unitär, Σ∈Rm×n\Sigma \in \mathbb{R}^{m \times n}, wobei

Σ=(Σr00⏟r0⏟n−r)[0]}r[00]}m−r,mit Σr=(σ10⋯00⋱⋱⋮⋮⋱⋱00⋯0σr),σ1≥...≥σr>0\Sigma = \begin{pmatrix} \Sigma_r & \boldsymbol{0}\\ \underbrace{\boldsymbol{0}}_r & \underbrace{\boldsymbol{0}}_{n-r} \end{pmatrix} \begin{matrix} \left.\vphantom{\begin{bmatrix} 0 \end{bmatrix}}\right\} r \\ \left.\vphantom{\begin{bmatrix} 0\\ 0 \end{bmatrix}}\right\} m-r \end{matrix}, \qquad \text{mit } \Sigma_r = \begin{pmatrix} \sigma_1 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots\\ \vdots & \ddots & \ddots & 0\\ 0 & \cdots & 0 & \sigma_r \end{pmatrix}, \quad \sigma_1 \geq ... \geq \sigma_r > 0

eine verallgemeinerte Diagonalmatrix mit Singulärwerten σ1,...,σr\sigma_1, ..., \sigma_r ist, so dass A=UΣVHA=U \Sigma V^H, d.h. AA besitzt eine Singulärwertzerlegung.

Satz

Sei A∈Em×nA \in \mathbb{E}^{m \times n}.

AHA=(UΣVH)HUΣVH=VΣH⏟=ΣTUHU⏟=𝟙m da U unita¨rΣVH=VΣTΣVH\begin{aligned} A^HA &= (U \Sigma V^H)^H U \Sigma V^H\\ &= V \underbrace{\Sigma^H}_{= \Sigma^T} \quad \underbrace{U^HU}_{=\text{𝟙}_m \text{ da } U \text{ unitär}} \Sigma V^H\\ &= V \Sigma^T \Sigma V^H \end{aligned}

⇒AHA\Rightarrow A^HA ist ähnlich (im Sinne von unitärer Spektralzerlegung) zu

ΣTΣ=(σ120⋯00⋯00⋱⋱⋮⋮⋮⋮⋱⋱0⋮⋮0⋯0σr20⋯00⋯⋯00⋯0⋮⋮⋮⋮0⋯⋯00⋯0)∈Rn×n\Sigma^T \Sigma = \begin{pmatrix} \sigma_1^2 & 0 & \cdots & 0 & 0 & \cdots & 0\\ 0 & \ddots & \ddots & \vdots & \vdots & & \vdots\\ \vdots & \ddots & \ddots & 0 & \vdots & & \vdots\\ 0 & \cdots & 0 & \sigma_r^2 & 0 & \cdots & 0\\ 0 & \cdots & \cdots & 0 & 0 & \cdots & 0\\ \vdots & & & \vdots & \vdots & & \vdots\\ 0 & \cdots & \cdots & 0 & 0 & \cdots & 0 \end{pmatrix} \in \mathbb{R}^{n \times n}

⇒σi=λi\Rightarrow \sigma_i = \sqrt{\lambda_i}, wobei λi\lambda_i die positiven reellen Eigenwerte von AHAA^HA sind.

Bemerkung Anwendung
  1. Die Singulärwertzerlegung ist gewissermassen eine Verallgemeinerung von der Spektralzerlegung für Rechtecksmatrizen.
  2. Singuläre LGS und Ausgleichsprobleme (kleinste Quadrate) lösen.
  3. Bildkompressionsverfahren. Dabei wird ein Bild als Matrix von Farbwerten betrachtet, wovon die Singulärwertzerlegung berechnet wird. Bei der Rücktransformation von UΣVHU \Sigma V^H nach AA werden aber nur noch die "stark von 00 abweichenden" Singulärwerte gespeichert, im Betrag kleine Singulärwerte werden vernachlässigt.
Algorithmus Singulärwertzerlegung

Gegeben: A∈Em×n,    m≥nA \in \mathbb{E}^{m \times n}, \;\; m \geq n (sonst betrachte AHA^H)
Gesucht: U∈Em×m,Σ∈Rm×n,V∈En×nU \in \mathbb{E}^{m \times m}, \Sigma \in \mathbb{R}^{m \times n}, V \in \mathbb{E}^{n \times n}

  1. Berechne B=AHA∈En×nB = A^HA \in \mathbb{E}^{n \times n}

  2. Berechne die Eigenwerte von BB, "nummeriere" sie der Grösse nach:

    λ1≥...≥λr>λr+1=...=λn=0,\lambda_1 \geq ... \geq \lambda_r > \lambda_{r+1} = ... = \lambda_n = 0,

    wobei r=rang(B)=rang(AHA)r = \text{rang}(B) = \text{rang}(A^HA)

  3. Σij={σi=λi,i=j0,    sonst\Sigma_{ij} = \begin{cases} \sigma_i = \sqrt{\lambda_i}, \quad i=j\\ 0, \qquad\qquad\;\; \text{sonst} \end{cases}
  4. Bilde die Orthonormalbasis {w1,...,wn}\{ w_1, ..., w_n \} mit Gram-Schmidt mit Eigenvektoren {v1,...,vn}\{v_1, ..., v_n\} von BB. (Betrachte B=AHAB=A^HA ist hermitesch, d.h. verwende Bemerkung 1)

    ⇒V=(w1∣⋯∣wn)\Rightarrow \quad V = ( w_1 | \cdots | w_n)
  5. ∀i∈{1,...,r}    definiere     ui:=1σiAwi⇒ui sind orthonormal/unita¨r\forall i \in \{1, ..., r \} \;\; \text{definiere } \;\; u_i := \frac{1}{\sigma_i} A w_i \quad \Rightarrow \quad u_i \text{ sind orthonormal/unitär}

    Ergänze {u1,...,ur}\{u_1, ..., u_r \} zu einer Orthonormalbasis von Em\mathbb{E}^{m} mit Gram-Schmidt

    ⇒U=(u1∣...∣um)\Rightarrow \quad U=(u_1 | ... | u_m)
  6. Test: A=?UΣVH✓\quad A \overset{?}{=} U \Sigma V^H \quad \checkmark

Beispiel 3

Gegeben:

A=(102101)A = \begin{pmatrix} 1 & 0\\ 2 & 1\\ 0 & 1 \end{pmatrix}

Gesucht: U,Σ,VU, \Sigma, V so dass A=UΣVHA=U \Sigma V^H; Zusatzfrage: Beschreibe die vier Fundamentalräume gemäss Satz 11.1 (siehe Skript).

Lösung anzeigenLösung ausblenden
  1. B=AHA=ATA=(5222)B = A^HA = A^TA = \begin{pmatrix} 5 & 2\\ 2 & 2 \end{pmatrix}
  2. Eigenwerte berechnen von BB:

    χB(λ)=∣5−λ222−λ∣=(5−λ)(2−λ)−4=10−2λ−5λ+λ2−4=λ2−7λ+6=(λ−1)(λ−6)=!0⇒λ1=6>λ2=1\begin{aligned} \chi_B(\lambda) &= \begin{vmatrix} 5-\lambda & 2\\ 2 & 2 -\lambda \end{vmatrix}\\ &= (5-\lambda)(2-\lambda) -4\\ &= 10 - 2\lambda - 5\lambda + \lambda^2 -4\\ &= \lambda^2 - 7\lambda + 6\\ &= (\lambda -1)(\lambda -6) \overset{!}{=} 0\\ \Rightarrow \quad \lambda_1 &= 6 > \lambda_2 = 1 \end{aligned}
  3. σ1=6,    σ2=1=1⇒Σ=(600100)\sigma_1 = \sqrt{6}, \;\; \sigma_2 = \sqrt{1} = 1 \quad \Rightarrow \quad \Sigma = \begin{pmatrix} \sqrt{6} & 0\\ 0 & 1\\ 0 & 0 \end{pmatrix}
  4. E6=ker(B−6𝟙)=span{(21)}⇒v1=(21)⇝normierenw1=15(21)E_6 = \text{ker}(B-6\text{𝟙}) = \text{span} \left\{ \begin{pmatrix} 2\\ 1 \end{pmatrix} \right\} \Rightarrow v_1 = \begin{pmatrix} 2\\ 1 \end{pmatrix} \overset{\text{normieren}}{\leadsto} w_1 = \frac{1}{\sqrt{5}} \begin{pmatrix} 2\\ 1 \end{pmatrix} E1=ker(B−𝟙)=span{(1−2)}⇒v2=(1−2)⇝normierenw2=15(1−2)E_1 = \text{ker}(B-\text{𝟙}) = \text{span} \left\{ \begin{pmatrix} 1\\ -2 \end{pmatrix} \right\} \Rightarrow v_2 = \begin{pmatrix} 1\\ -2 \end{pmatrix} \overset{\text{normieren}}{\leadsto} w_2 = \frac{1}{\sqrt{5}} \begin{pmatrix} 1\\ -2 \end{pmatrix} ⇒V=15(211−2)\Rightarrow \quad V = \frac{1}{\sqrt{5}} \begin{pmatrix} 2 & 1\\ 1 & -2 \end{pmatrix}
  5. u1=1615(102101)(21)=130(251)u_1 = \frac{1}{\sqrt{6}} \frac{1}{\sqrt{5}} \begin{pmatrix} 1 & 0\\ 2 & 1\\ 0 & 1 \end{pmatrix} \begin{pmatrix} 2\\ 1 \end{pmatrix} = \frac{1}{\sqrt{30}} \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} u2=1115(102101)(1−2)=15(10−2)u_2 = \frac{1}{\sqrt{1}} \frac{1}{\sqrt{5}} \begin{pmatrix} 1 & 0\\ 2 & 1\\ 0 & 1 \end{pmatrix} \begin{pmatrix} 1\\ -2 \end{pmatrix} = \frac{1}{\sqrt{5}} \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix} u3~=e2−⟨e2,u1⟩u1−⟨e2,u2⟩u2=(010)−130130⟨(010),(251)⟩(251)−1515⟨(010),(10−2)⟩(10−2)=(010)−530(251)−0⋅(10−2)=(010)−16(251)=16(−21−1)\begin{aligned} \widetilde{u_3} &= e_2 - \langle e_2,u_1 \rangle u_1 - \langle e_2,u_2 \rangle u_2\\ &= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} - \frac{1}{\sqrt{30}} \frac{1}{\sqrt{30}} \langle \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} \rangle \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} - \frac{1}{\sqrt{5}} \frac{1}{\sqrt{5}} \langle \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix}, \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix} \rangle \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix}\\ &= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} - \frac{5}{30} \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix} - 0 \cdot \begin{pmatrix} 1\\ 0\\ -2 \end{pmatrix}\\ &= \begin{pmatrix} 0\\ 1\\ 0 \end{pmatrix} - \frac{1}{6} \begin{pmatrix} 2\\ 5\\ 1 \end{pmatrix}\\ &= \frac{1}{6} \begin{pmatrix} -2\\ 1\\ -1 \end{pmatrix} \end{aligned} u3=u3~∥u3~∥=16(−21−1)u_3 = \frac{\widetilde{u_3}}{\left\lVert \widetilde{u_3} \right\rVert} = \frac{1}{\sqrt{6}} \begin{pmatrix} -2\\ 1\\ -1 \end{pmatrix} ⇒U=(23015−26530016130−25−16)\Rightarrow U = \begin{pmatrix} \frac{2}{\sqrt{30}} & \frac{1}{\sqrt{5}} & -\frac{2}{\sqrt{6}}\\ \frac{5}{\sqrt{30}} & 0 & \frac{1}{\sqrt{6}}\\ \frac{1}{\sqrt{30}} & -\frac{2}{\sqrt{5}} & -\frac{1}{\sqrt{6}} \end{pmatrix}
  6. Test: A=UΣVH✓A = U \Sigma V^H \quad \checkmark

  7. Die vier Fundamentalräume:

    im(A)={u1,u2}im(AH)={w1,w2}ker(AH)={u3}ker(A)={}\begin{aligned} \text{im}(A) &= \{u_1, u_2\}\\ \text{im}(A^H) &= \{w_1, w_2\}\\ \text{ker}(A^H) &= \{u_3\}\\ \text{ker}(A) &= \{\} \end{aligned}
Beispiel 4

Gegeben:

A=(1011−11)A = \begin{pmatrix} 1 & 0\\ 1 & 1\\ -1 & 1 \end{pmatrix}

Gesucht: U,Σ,VU, \Sigma, V so dass A=UΣVHA=U \Sigma V^H

Lösung anzeigenLösung ausblenden Σ=(300200),V=(1001)=𝟙2,U=(130261312−16−131216)\Sigma = \begin{pmatrix} \sqrt{3} & 0\\ 0 & \sqrt{2}\\ 0 & 0 \end{pmatrix}, \quad V = \begin{pmatrix} 1 & 0\\ 0 & 1 \end{pmatrix} = \text{𝟙}_2, \quad U = \begin{pmatrix} \frac{1}{\sqrt{3}} & 0 & \frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{6}}\\ -\frac{1}{\sqrt{3}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{6}} \end{pmatrix}