SOR-Verfahren

In der numerischen Mathematik ist das Sucessive Over Relaxation-Verfahren, auch SOR-Vefahren genannt, ein Algorithmus zur näherungsweisen Lösung von linearen Gleichungssystemen $Ax=b$. Es ist, wie das Gauß-Seidel-Verfahren, ein spezielles Splitting-Verfahren.

Gegeben ist ein lineares Gleichungssystem mit n Variablen mit n Gleichungen.

${\begin{matrix}a_{1;1}\cdot x_{1}+\dots +a_{1;n}\cdot x_{n}&=&b_{1}\\a_{2;1}\cdot x_{1}+\dots +a_{2;n}\cdot x_{n}&=&b_{2}\\&\vdots &\\a_{n;1}\cdot x_{1}+\dots +a_{n;n}\cdot x_{n}&=&b_{n}\\\end{matrix}}$

Der Algorithmus verwendet eine Matrix ${\tilde {A}}=({\tilde {a}}_{ij})$ mit ${\tilde {a}}_{ij}={-{\frac {a_{ij}}{a_{ii}}}w}$ falls $i\neq j$, bzw. ${\tilde {a}}_{ij}=1-w$ falls $i\neq j$ und den Vektor $c_{i}={\frac {b_{i}}{a_{ii}}}w$ mit $i=1,2,\ldots ,n$. Dabei ist $w$ ein reeller Überrelaxtionsparameter. Für $w=1$ erhält man wieder ein Einzelschrittvervahren. Das Verfahren konvergiert für jedes $w\in (0,2)$, falls A symmetrisch positiv definit ist. Um das Gleichungssystem zu lösen, wird die i-te Gleichung nach der i-ten Variable x_i aufgelöst,

$x_{i}^{m+1}=\sum \limits _{j=1}^{i-1}{{\tilde {a}}_{ij}}x_{j}^{m+1}+\sum \limits _{j=1}^{n}{{\tilde {a}}_{ij}}x_{j}^{m}+c_{i}$.

Algorithmus

• Wähle $x^{0}$
• Für $m=0,1,\ldots$ berechne
  • Für $i=0,1,\ldots ,n$ berechne

$x_{i}^{m+1}=\sum \limits _{j=1}^{i-1}{{\tilde {a}}_{ij}}x_{j}^{m+1}+\sum \limits _{j=1}^{n}{{\tilde {a}}_{ij}}x_{j}^{m}+c_{i}$.

Konsistenzbeweis

$A=L+D+R$
$M_{\omega }=(D+\omega \,L)^{-1}\,((1-\omega )\,D-\omega \,R)$
$N_{\omega }=\omega \,(D+\omega \,L)^{-1}$

Zeige: $x=A^{-1}\,b$ ist ein Fixpunkt von

$\Psi (x)=M_{\omega }\,x+N_{\omega }\,b$

$x=M_{\omega }\,x+N_{\omega }\,b$
$\Leftrightarrow (D+\omega \,L)\,x=((1-\omega )\,D-\omega \,R)\,x+\omega \,(D+L+R)\,x=D\,x+\omega \,L\,x$

gilt für alle x $\Rightarrow$ x ist ein Fixpunkt.