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 ${\displaystyle Ax=b}$ mit einer Matrix ${\displaystyle A\in \mathbb {R} ^{n\times n}}$ und den rechten Seiten ${\displaystyle b_{i}}$ in einem Vektor ${\displaystyle b\in \mathbb {R} ^{n}}$. Die Aufgabe besteht nun darin, die Matrix so umzuformen, dass die Gesuchte, also ${\displaystyle x:=x_{j}\in \mathbb {R} ^{n}}$, möglichst einfach auszurechnen ist. Dies ist der Fall, wenn durch diese Operationen ${\displaystyle A}$ in eine obere Dreiecksmatrix umgeformt worden ist, das heißt alle Elemente unterhalb der Hauptdiagonalen sind gleich null. Das erreicht man auf verschiedenen Wegen.

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

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

Weitere direkte Verfahren sind das Householderverfahren, bei dem die zu multiplizierende Matrix ${\displaystyle L}$ orthogonal ist, oder das Verfahren durch Givens-Rotationen, bei dem die Nullen dadurch erzeugt werden, dass Vektoren in einem zweidimensionalen Untervektorraum des ${\displaystyle \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.