05.3 – Analyse des relaxierten Jacobi-Verfahrens

 

Gegeben sei das lineare Gleichungssystem Ax = b mit einer positiv definiten und symmetrischen Matrix A \in {\mathbb{R}^{n \times n}}.

Beim relaxierten Jacobi-Verfahren wird die Iteration durchgeführt nach der Vorschrift

\frac{1}{\omega }D{x_{k+1}}+\left( {A-\frac{1}{\omega }D} \right){x_k} = b,\quad 0 < \omega \leq 1

  1. Zeigen Sie: Das relaxierte Jacobi-Verfahren konvergiert für jede beliebige Startnäherung {x_0} unter der Voraussetzung, dass für die eigenwerte {\alpha _1}, \ldots ,{a_n} von {D^{-1}}A gilt:

    0 < {\alpha _i} < \frac{2}{\omega },\quad i = 1, \ldots ,n

  2. Die Iterationsmatrix {M_J} des Jacobi-Verfahrens habe die Eigenwerte {\lambda _1} \leq \ldots \leq {\lambda _n} und es gelte \rho \left( {{M_J}} \right) < 1. Zeigen Sie, dass die Iterationsmatrix {M_J}\left( \omega \right) des relaxierten Jacobi-Verfahrens die Eigenwerte

    {\mu _i} = 1-\omega +\omega {\lambda _i},\quad i = 1, \ldots ,n

    hat und dass gilt

    {\omega _{opt}} = \frac{2}{{2-{\lambda _1}-{\lambda _n}}}

Lösung

a )

{x_{k+1}} = \omega {D^{-1}}\left( {b-\left( {A-\frac{1}{\omega }D} \right){x_k}} \right)

= {x_k}+\omega {D^{-1}}\left( {b-A{x_k}} \right)

= \left( {I-\omega {D^{-1}}A} \right){x_k}+\omega {D^{-1}}b

Aus der Vorlesung wissen wir, dass Konvergenz aus \left\| {I-\omega {D^{-1}}A} \right\| < 1 folgt.

Sei M_J^\omega : = I-\omega {D^{-1}}A, seien {a_i} die Eigenwerte von {D^{-1}}A und {v_i} die dazugehörigen Eigenvektoren. Dann folgt:

M_J^\omega {v_i} = \left( {I-\omega {D^{-1}}A} \right){v_i}

= {v_i}-\omega {D^{-1}}A{v_i}

= {v_i}-\omega {\alpha _i}{v_i}

= \left( {1-\omega {\alpha _i}} \right){v_i}

Daraus folgt:

{v_i} ist Eigenvektor von M_J^\omega zum Eigenwert 1-\omega {\alpha _i}.

\rho \left( {M_J^\omega } \right) < 1

\quad \Rightarrow \quad \left| {1-\omega {\alpha _i}} \right| < 1

\quad \Rightarrow \quad -1 < 1-\omega {\alpha _i} < 1

\quad \Rightarrow \quad -2 < -\omega {\alpha _i} < 0

\quad \Rightarrow \quad 0 < {\alpha _i} < \frac{2}{\omega }

Je kleiner der Betrag des Spektralradius ist, desto besser konvergiert das Verfahren. Daher wollen wir nun das \omega so wählen, dass der Spektralradius minimiert wird.

b )

{M_J} sei die Iterationsmatrix des Jacobi-Verfahrens mit den Eigenwerten {\lambda _1}, \ldots ,{\lambda _n}.

Für den Spektralradius gelte \rho \left( {{M_J}} \right) < 1.

Seien {\mu _i} die Eigenwerte von {M_J} = I-{D^{-1}}A.

M_J^\omega {\mu _i} = \left( {I-\omega {D^{-1}}A} \right){\mu _i}

= \left( {I-\omega I+\omega \left( {I-{D^{-1}}A} \right)} \right){\mu _i}

= \left( {\left( {1-\omega } \right)I+\omega {\lambda _i}} \right){\mu _i}

= \left( {1-\omega +\omega {\lambda _i}} \right){\mu _i}

Wir wollen nun {\omega _{opt}} bestimmen, d.h. wir wählen {\omega _{opt}} so, dass \rho \left( {M_J^{{\omega _{opt}}}} \right) minimiert wird.
Der maximale Betrag, den ein Eigenwert haben kann, muss also möglichst klein sein.

Relaxationsfunktion: {f_\omega }:\mathbb{R} \to \mathbb{R},\quad \lambda \to 1-\omega +\omega \lambda

Für \omega > 0 gilt:

{\mu _1} \leq {\mu _2} \leq \ldots \leq {\mu _n} (wegen {\lambda _1} \leq {\lambda _2} \leq \ldots \leq {\lambda _n})

Optimierung des Parameters Omega, Geraden und Eigenwerte

Blau: {f_{\frac{1}{2}}}\left( \lambda \right) = \frac{1}{2}+\frac{1}{2}\lambda, Grün: {f_{\frac{3}{2}}}\left( \lambda \right) = -\frac{1}{2}+\frac{3}{2}\lambda, Orange: {f_{\frac{4}{3}}}\left( \lambda \right) = -\frac{1}{3}+\frac{4}{3}\lambda

Die Gerade kann nach oben und unten verschoben, sowie verdreht werden. Wir sehen:

{\mu _n}\left( {{\omega _{opt}}} \right) = {f_{{\omega _{opt}}}}\left( {{\lambda _n}} \right) = -{f_{{\omega _{opt}}}}\left( {{\lambda _1}} \right) = -{\mu _1}\left( {{\omega _{opt}}} \right)

\quad \Rightarrow \quad 1-{\omega _{opt}}+{\omega _{opt}}{\lambda _n} = -\left( {1-{\omega _{opt}}+{\omega _{opt}}{\lambda _1}} \right)

\quad \Rightarrow \quad {\omega _{opt}}\left( {-2+{\lambda _n}+{\lambda _1}} \right) = -2

\quad \Rightarrow \quad {\omega _{opt}} = \frac{2}{{2-{\lambda _n}-{\lambda _1}}}

In der Praxis kennt man die Eigenwerte nicht genau, kann sie aber abschätzen.

Wir zeigen nun, dass das gefundene {\omega _{opt}} tatsächlich optimal ist:

Sei \omega > {\omega _{opt}}. Dann folgt:

{\mu _1}\left( \omega \right) = 1-\omega \underbrace {\left( {1-{\lambda _1}} \right)}_{ > 0\:da\:\rho \left( {{M_J}} \right) < 1} < 1-{\omega _{opt}}\left( {1-{\lambda _1}} \right)

= {\mu _1}\left( {{\omega _{opt}}} \right) = 1-\underbrace {\frac{{2-{\lambda _1}-{\lambda _1}}}{{2-{\lambda _1}-{\lambda _n}}}}_{ > 1\:da\:{\lambda _1} \leq {\lambda _n}} < 0

\quad \Rightarrow \quad \rho \left( {M_J^\omega } \right) \geq \left| {{\mu _1}\left( \omega \right) > \left| {{\mu _1}\left( {{\omega _{opt}}} \right)} \right|} \right| = \rho \left( {M_J^{{\omega _{opt}}}} \right)

Mit einer analogen Betrachtung für \omega < {\omega _{opt}} und {\mu _n}\left( \omega \right),\:{\mu _n}\left( {{\omega _{opt}}} \right) folgt insgesamt:

{\omega _{opt}} = \arg \min \limits_{\omega \in {\mathbb{R}^+}} \rho \left( {M_J^\omega } \right)