Direktes Verfahren

Direkte Verfahren sind numerische Methoden, die direkt eine Lösung liefern, im Gegensatz zu iterativen Verfahren, die schrittweise eine Anfangsnäherung verbessern. Hierbei ist zu beachten, dass für sehr viele Probleme keine direkten Verfahren existieren, dazu gehören insbesondere fast alle nichtlinearen Gleichungssysteme. Eine wichtige Klasse für die direkte Verfahren bekannt sind, sind lineare Gleichungssysteme.

Gegeben ist dazu ein Gleichungssystem Ax = b mit einer Matrix $A\in\mathbb{R}^{n\times n}$ und der rechten Seiten b_i in einem Vektor $b\in\mathbb{R}^{n}$. Die Aufgabe besteht nun darin, die Matrix so umzuformen, dass die Gesuchte also $x:=x_j\in\mathbb{R}^{n}$ möglichst einfach auszurechnen ist. Dies ist der Fall, wenn durch diese Operationen A in eine obere Dreiecksmatrix umgeformt worden ist, das heißt alle Elemente unterhalb der Hauptdiagonalen (das sind die a_ii) sind gleich null. Das erreicht man auf verschiedenen Wegen.

Beim Gaußschen Eliminationsverfahren werden dazu A und b mit einer Matrix L multipliziert, die folgendermaßen aussieht:

$L=l_{ij}=a_{ij}/a_{jj} \qquad falls \quad j\le i,\quad l_{ij}=0 \quad sonst. \quad L\cdot A$ hat dann Diagonalgestalt und die x_j können dann von j=n bis j=1 aus $L\cdot A x=L\cdot b$ rückwärts ausgerechnet werden.

Weitere direkte Verfahren sind das Householderverfahren bei dem die zu multiplizierende Matrix L orthogonal ist, oder das Verfahren durch Givens-Rotationen, bei dem die Nullen dadurch erzeugt werden, dass Vektoren in einem zweidimensionalen Unterraum des $\mathbb{R}^n$ gedreht werden, so dass immer eine Komponente Null wird.

Darüber hinaus gibt es Verfahren, die spezielle Eigenschaften des Systems ausnutzen. Ein Beispiel ist die Cholesky-Zerlegung für positiv definite Systeme oder Verfahren zur Lösung von dünnbesetzten Systemen.

Literatur

• A. Meister: Numerik linearer Gleichungssysteme, 2. Auflage, Vieweg 2005, ISBN 3528131357