4.3.5.5 Konvergenzfaktor und Iterationszahl

Die Matrixnorm $\Vert{\bf B}\Vert$, $\Vert{\bf B}'\Vert$ oder $\Vert{\bf B}'(\omega)\Vert$ eines Iterationsverfahrens heißt auch Konvergenzfaktor, denn wir wissen nach Gl. (4.132), daß der relative Fehler der Lösung mit der Iterationszahl $k$ wie

\begin{displaymath}
\frac{\Vert{\bf u}-{\bf u}^{(k)}\Vert}{\Vert{\bf u}\Vert} \:\!\leq\:\! \Vert{\bf B}\Vert^k
\end{displaymath} (4.228)

abnimmt.

Gibt man sich umgekehrt für die Lösung eine bestimmte relative Genauigkeit $\varepsilon$ vor, so folgt aus dieser Beziehung, daß die zur Erreichung der gewünschten Genauigkeit erforderliche minimale Iterationszahl $k$

\begin{displaymath}
\Vert{\bf B}\Vert^k \:\!\leq\:\! \varepsilon
\end{displaymath} (4.229)

oder
\begin{displaymath}
k\ln\Vert{\bf B}\Vert \:\!\leq\:\! \ln\varepsilon
\end{displaymath} (4.230)

erfüllen muß. Da $\ln\Vert{\bf B}\Vert<0$ ist (es ist ja $\Vert{\bf B}\Vert<1$) und eine Ungleichung sich bei Division durch eine negative Zahl umkehrt, kann bei bekanntem $\Vert{\bf B}\Vert$ also $k$ aus
\begin{displaymath}
\fbox{$\displaystyle
k \:\!\geq\:\! \frac{\ln\varepsilon}{\ln\Vert{\bf B}\Vert}
$}
\end{displaymath} (4.231)

bestimmt werden. (Das ist freilich nur eine Abschätzung für den ,,schlimmsten Fall``, denn in der Praxis kann die gewünschte Genauigkeit natürlich auch schon früher erreicht werden.)

Bei unserem Modellproblem Poisson-Gleichung ergibt sich daraus z.B. für Jacobi-Iteration mit Unterrelaxation und optimalem Mischungsparameter

\begin{displaymath}
\ln\Vert{\bf B}'(\omega_{\rm opt})\Vert
\approx \ln\left(1-\frac{2\pi^2}{N^2}\right)
\approx -\,\frac{2\pi^2}{N^2},
\end{displaymath} (4.232)

also (wegen $\varepsilon\ll1$ ist $\ln\varepsilon<0$)
\begin{displaymath}
k \:\!\geq\:\! \frac{-\ln\varepsilon}{2\pi^2}\,N^2.
\end{displaymath} (4.233)

Für das Gauß-Seidel- und das SOR-Verfahren (letzteres ebenfalls mit optimalem Extrapolationsparameter) findet man analog die in Tabelle 4.1 angegebenen Ausdrücke.

Verfahren Iterationszahl
Jacobi mit Unterrelaxation $(\omega=\omega_{\rm opt})$ $\displaystyle k\:\!\geq\:\!\frac{-\ln\varepsilon}{2\pi^2}\,N^2$
Gauß-Seidel $\displaystyle k\:\!\geq\:\!\frac{-\ln\varepsilon}{4\pi^2}\,N^2$
SOR $(\omega=\omega_{\rm opt})$ $\displaystyle k\:\!\geq\:\!\frac{-\ln\varepsilon}{\pi}\,N$


Tabelle 4.1: Minimale Iterationszahl $k$ zur Erreichung einer vorgegebenen relativen Genauigkeit $\varepsilon$ bei der Lösung der eindimensionalen Poisson-Gleichung mit periodischen Randbedingungen auf $N$ Stützpunkten.

Bemerkenswert ist hier die Tatsache, daß sowohl für das Jacobi- als auch für das Gauß-Seidel-Verfahren die Iterationszahl quadratisch mit der Anzahl der Stützpunkte $N$ steigt, d.h. bei Verdopplung der räumlichen Auflösung vervierfacht sich die Iterationszahl. Gauß-Seidel-Iteration konvergiert zwar doppelt so schnell wie Jacobi, dennoch führen beide Verfahren bei feiner Auflösung (und insbesondere in höheren Dimensionen) schnell zu enormen Rechenzeiten. Im Gegensatz dazu steigt die Anzahl der Iterationen bei SOR--vorausgesetzt, der optimale Relaxationsparameter ist bekannt--nur linear mit $N$. Da dieses Verfahren nur unwesentlich komplizierter zu implementieren ist als Jacobi oder Gauß-Seidel, wird es also in der Praxis unbedingt vorzuziehen sein.

  $N=20$ $N=100$
Verfahren $\omega_{\rm opt}$ $\Vert{\bf B}\Vert$ $k$ $\omega_{\rm opt}$ $\Vert{\bf B}\Vert$ $k$
Jacobi mit Unterrelaxation 0.976113 0.952226 188 0.999014 0.998029 4668
Gauß-Seidel - 0.914483 103 - 0.996077 2343
SOR 1.523381 0.854081 58 1.881784 0.969067 293


Tabelle 4.2: Konvergenzfaktor $\Vert{\bf B}\Vert$ und minimale Iterationszahl $k$ zur Erreichung einer relativen Genauigkeit von $\varepsilon=10^{-4}$ bei der Lösung der eindimensionalen Poisson-Gleichung mit periodischen Randbedingungen auf $N=20$ bzw. $N=100$ Stützpukten.

Tabelle 4.2 vergleicht für das Modellproblem die konkreten Werte der Konvergenzfaktoren und Iterationszahlen für zwei verschiedene Auflösungen. Die Proportionalität von $k$ zu $N^2$ bzw. $N$ ist deutlich zu sehen.