06.2 – Eigenwertproblem als Nullstellenproblem mit Newton

 

Es sei A \in {\mathbb{R}^{n \times n}} eine invertierbare Matrix mit n verschiedenen Eigenwerten.

a )

Zeigen Sie, dass für jeden der Eigenwerte \lambda von A mit dazugehörigem Eigenvektor v die Matrix A-\lambda I-\alpha v{v^T} für alle \alpha \ne 0 invertierbar ist.

b )

Zeigen Sie, dass sich das Eigenwertproblem

“Finde v \in {\mathbb{R}^n}\backslash \left\{ 0 \right\} und \lambda mit Av = \lambda v“

in das Nullstellenproblem

F\left( {v,\lambda } \right): = \left[ {\begin{array}{*{20}{c}}{Av-\lambda v} \\{0.5\left( {{\lambda ^2}-{v^T}v} \right)} \\\end{array} } \right] = 0

überführen lässt. Zeigen Sie, dass die Jacobi-Matrix an den Nullstellen von F invertierbar ist und formulieren Sie das Newton-Verfahren zur Lösung des Nullstellenproblems

Lösung

a )

Wenn es n verschiedene Eigenwerte gibt, dann existiert eine Basis aus Eigenvektoren \left\{ {{v_1}, \ldots ,{v_n}} \right\},\:\:\left\| {{v_i}} \right\| = 1. Sei \lambda beliebiger Eigenwert mit dazugehörigem Eigenvektor, ohne Beschränkung der Allgemeinheit \lambda = {\lambda _1}. Dann gilt:

B{v_k} = A{v_k}-{\lambda _1}{v_k}-\alpha {v_1}v_1^T{v_k} = \left( {{\lambda _k}-{\lambda _1}} \right){v_k}-\alpha \beta {v_1},\quad \beta = v_1^T{v_k}

Für k = 1 fällt der Term in der Klammer weg. Außerdem wird \beta = 1. Es folgt also:

k = 1\quad \Rightarrow \quad B{v_1} = -\alpha {v_1} \ne 0

Für k \ne 1:

Da {v_1} und {v_k} linear unabhängig sind und {\lambda _k} \ne {\lambda _1}, folgt:

k \ne 1\quad \Rightarrow \quad B{v_k} \ne 0

Aus B{v_k} = \left( {{\lambda _k}-{\lambda _1}} \right){v_k}-\alpha \beta {v_1},\quad \beta = v_1^T{v_k} folgt, dass B{v_k},\:\:k = 1, \ldots ,n linear unabhängig.

Daher: rang\left( B \right) = n\quad \Rightarrow \quad B ist invertierbar

b )

Av = \lambda v\quad \Rightarrow \quad \left( {A-\lambda I} \right)v = 0

Da A invertierbar ist, ist 0 kein Eigenwert. Wähle einen Eigenvektor v:\left\| v \right\| = \lambda, also {v^T}v = {\lambda ^2}.

Daraus folgen zwei Gleichungen:

I:\quad Av = \lambda v

II:\quad 0.5\left( {{\lambda ^2}-{v^T}v} \right) = 0

Dies ist ein nichtlineares Gleichungssystem für \lambda und v.

Für das Newton-Verfahren brauchen wir die Jacobi-Matrix:

J = \left( {\begin{array}{*{20}{c}} {{\partial _v}{F_1}} & {{\partial _\lambda }{F_1}} \\ {{\partial _v}{F_2}} & {{\partial _\lambda }{F_2}} \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} {A-\lambda I} & {-v} \\ {-{v^T}} & \lambda \\ \end{array} } \right)

Wir erzeugen in der letzten Zeile \left( {\begin{array}{*{20}{c}} 0 & \lambda \\ \end{array} } \right), indem wir \frac{1}{\lambda }{v_i}\left( {\begin{array}{*{20}{c}} {-v} \\ \lambda \\ \end{array} } \right) zur i-ten Spalte addieren ({v_i} ist die i-te Komponente des Vektors) für i = 1, \ldots ,n. Das ergibt die Matrix:

\left( {\begin{array}{*{20}{c}} {A-\lambda I-\frac{1}{\lambda }v{v^T}} & {-v} \\ 0 & \lambda \\ \end{array} } \right)

Nach Aufgabenteil a) ist A-\lambda I-\frac{1}{\lambda }v{v^T} invertierbar. Da \lambda immer ungleich 0 ist, folgt daraus, dass die Jacobi-Matrix invertierbar ist.

Das Newton-Verfahren ist dann:

\left( {\begin{array}{*{20}{c}} {{v_{k+1}}} \\ {{\lambda _{k+1}}} \\ \end{array} } \right) = \left( {\begin{array}{*{20}{c}} {{v_k}} \\ {{\lambda _k}} \\ \end{array} } \right)+{\left( {\begin{array}{*{20}{c}} {A-{\lambda _k}I} & {-{v_k}} \\ {-v_k^T} & {{\lambda _k}} \\ \end{array} } \right)^{-1}}\left( {\begin{array}{*{20}{c}} {A{v_k}-{\lambda _k}{v_k}} \\ {0.5\left( {\lambda _k^2-v_k^T{v_k}} \right)} \\ \end{array} } \right)